Knowledge-based AI
In Artificial Intelligence, Knowledge-Based systems have been around for quite a while and gained heavily in popularity in the 1980’s. Much work has progressed on the application of this subject since. Knowledge-based systems operate off the principle that intelligence is a reapplication of past knowledge. Similar to expert systems, knowledge-based systems keep a mapping of input observation and output action. Unlike expert systems, though, knowledge-base systems are not pre-programmed by a group of experts. Instead, they learn over time by mapping the output back to the input to determine desired actions by correcting for failures. Ideally, if a knowledge base can build up enough knowledge about all possible situations it is required to operate within, it will act as an autonomous intelligent agent. However, knowledge-based systems are difficult to realize in all but the most confined and narrow-scoped problem domains both because of the limited scalability of the knowledge base as well as the algorithms and heuristics needed to correct for and learn new experiences and knowledge.
Case-Based Reasoning
Knowledge-based systems come in many forms and names, but all are very similar. The most famous type of knowledge-based system is called case-based reasoning (CBR). CBR has had great success in a variety of areas, specifically robotic control.The basics of a CBR system is the knowledge base, the input systems (sensors), the output, or action taking systems (actuators), and finally, the algorithms that decide which action to take given the input sequence as well as the learning system to correct for bad actions.
Learning is often done via an external agent, often human, to decide if an action was right or wrong. The decision algorithm is classically based on a similarity function that helps determine how close a newly observed situation is to situations already stored in the case base. Since all observations are likely to be taken from different angles, have slightly different parameters and environmental agents surrounding them, or are just noisy, they will all be observed and modeled differently than other situations of the same type.
The CBR decision maker must determine how close the observation is to all previous observations to correct for the ambiguity.For example, a speech recognition system in a coffee shop will always have a unique model of an order for a latte because of the ambient noise of the pseudo-intellectuals discussing Ginsberg and Ferlinghetti.
For a great example of Case-Based Reasoning, visit ALICE at www.alicebot.org (Artificial Linguistic Internet Computer Entity).
A chat with ALICE will find out what makes her work.
Human: Who are you?
ALICE: I am ALICE. Who are you?
Human: What makes you tick?
ALICE: Some people call my technology "Case Based Reasoning" or CBR.
Human: What is case based reasoning?
She's pretty good, so challenge her and see how far you can get before you stump her.
Case-Based Decision Theory
Case-Based Decision Theory (CBDT) is a similar algorithm to CBR; however, unlike CBR which came out of AI theory, CBDT came from economic optimization research. the closest case in the case-base. Unlike CBR, CBDT also uses a utility function in its look-up procedure. The added dimension allows cases to be chosen not only by how close the situations are, but also how well the situations work. If a past situation did not work very well, maybe we can apply the actions to a slightly less similar situation that worked very well. The added dimensionality also introduces added complexity. We not only require a similarity function, but we also need a utility function as well as some method to combine the two functions to retrieve the best case from memory.
Cased-Base Decision Theory with Genetic Algorithms
Our research interest in CBDT is to act as the decision maker used to initialize a genetic algorithm (GA). The theory is that while a GA is useful in finding optimized solutions to very complicated problems, it can often be slow to converge. By building up knowledge over time, we can help prime the GA’s population from the first generation with solutions from previous, similar problems.
We are currently applying this theory to test its validity to a classic optimization problem called the knapsack problem, which is often used to benchmark genetic algorithms.
The following figure shows a block diagram of the CBDT/GA system. The CBDT system takes the new input and computes the similarity and utility functions. The best combination of the two functions determines the case that is picked. The case is then sent to the GA to initialize the population. The clock on the GA indicates there is a finite amount of time for the GA to process, so optimization may not complete during this time. The solution is then sent back to the memory, or case-base, to remember the latest solution to that input. Later, if the same input is observed, the GA can iterate on this solution to try to improve the performance.
