Much of the information contained within this document comes from work completed by Mark McVea as part of a special problems course.
From Webster's Dictionary -
Thus Case-Based Reasoning is the act of developing solutions to unsolved problems based on pre-existing solutions of a similar nature.
This is analogous to being presented with a problem that you have to solve. During the time you spend thinking about the problem in order to gain a more complete understanding and start to develop a solution strategy, most people will naturally think about other, similar problems they have encountered. During this mental review of previous problems and associated solutions, the problem solver is actually performing CBR.
Within your mental picture of the current problem, and as you start to formulate a solution, you typically review other mental pictures and determine to what extent they relate to the current problem. If a previous problem/solution pair are fairly close to the current problem, then the solution to the previous problem is applied to the current problem. As the current problem and previous solution are compared for functionality and operational characteristics, the problem solver is actually determining how well the retrieved case matches the current needs. If the match is not completely acceptable, but close, then the problem solver starts to reason about the solution and how it must be modified to accommodate the new problem.
During research into the human ability to solve problems, researchers realized that most people derive solutions based on previous experience(s) with similar situations. It has been observed that people even discuss problems and solutions in terms of previous experiences. Thus, it appears obvious that, complete solutions derived solely from first principles is fairly rare. Instead, most problem solvers approach new problems and their associated solution(s) by relating both the problem and the solution to previous experiences. Thus, they build a new solution from information gained from previous experiences, coupled with some reasoning from first principles.
Expert Systems or Knowledge Based Systems (KBS) are a subset of CBR, and are based on a more limited problem domain (domain knowledge). This has evolved in this manner largely because a general problem solver was too broad based of a task to be accomplished.
According to the general theory of human thought, an individual must fully understand the problem to be solved and have a complete explanation of the situation around him, prior to attempting a solution. As a simple example, think about the requirement of sustenance, eating, add to that requirement the constraint that you are not going to prepare the food yourself. According to the general theory, one is required to fully understand the problem, the requirement of nourishing food or food supplements, used to sustain bodily functions. Also, one must understand the surrounding environment: The food chain, food preparation, probable location of food or food supplements, how to obtain and ingest them, etc.
All this, as you might expect, does not typically occur when one wishes to dine-out. Instead, you usually just go to a restaurant and order and entree, wait for it to be served and then eat it, etc. So, what's wrong with the theory? First, it is not inherently incorrect, just incomplete. What needs to be added is provisions for what the A.I. community calls `scripts'.
Scripts are a common understanding of expected events on the part of all parties involved. Suppose of a moment you wanted someone to provide food for you. Typically you go to a restaurant and order something appealing. The server realizes that what you ordered, you want delivered to your table with the appropriate silverware and napkin, etc. such that you can consume it. After it is delivered, you are expected to consume it, and show your appreciation by paying for it and leaving a tip for the server. All these events are mutually understood by both parties. To further the example, think about the events if instead of ordering food, you were to order, let's say, your shirt dry-cleaned.
First, the restaurant is probably not set-up to do dry-cleaning, which would present a certain problematic situation to be addressed. More importantly though, the server, the cook and the owner of the restaurant are not there to dry-clean shirts, thus your request would cause a certain amount of confusion to say the least.
This is in part why computers have not yet reached the stage of `general problem solvers'. Their experience base is extremely limited in comparison to humans. That is why one of the current hot-beds of A.I. activity is in KBS and CBR or domain dependent problems. This approach limits the scope of the base knowledge required of the system and further refines the problem statement prior to system activity. In other words, the system has a basic idea of the nature of the problem a user will likely pose - You won't be expecting to have your shirt dry-cleaned in a restaurant.
So what really is CBR - As stated it is matching similar problems and their solutions to new problems, and/or reasoning about solutions to new problems based on an understanding of previous solution methods and techniques. Sounds fairly straight forward and possibly it is. However, what happens when there is no perfect match to a new problem, from the domain knowledge of existing problems? What is the system suppose to do and how is it to achieve this goal?
Let's review what a human problem solver would do in a similar situation. Back to the restaurant example; Suppose a customer ordered a grilled swordfish entree with a vegetable side dish. Further suppose, the server realizes that this particular restaurant does not serve swordfish in its normal business routine, what to do? Typically, prior to informing the customer of the dilemma, the server mentally runs through all the possible solutions to the situation.
First he could inform the customer that this particular restaurant does not serve this dish, but the restaurant just down the street in fact does. This course of action fully satisfies the customer but the server would lose his tip and the restaurant that employs him, some business - not a good choice.
Second, he could take the order and then go and discuss the situation with the cook. The cook could obvious prepare the swordfish dish, since this restaurant does in fact have a number of seafood offering on the current menu. Possibly the server or the cook could `go out the back door' to the restaurant down the street and buy a swordfish entree and serve it as if they had prepared it. Again this satisfies the customer, but in the first case puts an added burden on the chef and possibly a time delay while the raw swordfish is purchased. The second option, going next door, would again satisfy the customer, but would not provide any margin of profit for the restaurant and stakes the reputation of this restaurant solely on someone else. Again not an acceptable choice.
Another alternative would be to simply tell the customer that he really didn't want swordfish and that what he would be happiest with is a nice, thick steak - silly customer, ordering something he really didn't want anyway. As you can see, this would likely have an adverse effect on business, not only from this customer, but from all the other people he told about the bazaar behavior of the servers they hire. Not a good choice.
A final alternative would be for the server to simply inform the customer that this restaurant does not serve swordfish, but that mahi-mahi, which is on the menu, is avery good substitute for swordfish. If the server is knowledgable in both the restaurant policy, server etiquette and food tastes (in this case, that mahi-mahi is similar to swordfish), he can work with the given situation and derive an acceptable solution.
In the final case, the server reviewed the current problem requirements - the customer wants a swordfish entree, and then the immediate domain knowledge - this restaurant does not serve swordfish, and then the pertinent domain knowledge - mahi-mahi tastes similar to swordfish. Finally the server con- cludes a solution - to suggest to the patron that swordfish is not available but an acceptable alternative is mahi-mahi, of which the chef does an incredible job in preparing (it is always good to `sell' an idea).
Again, how does this example relate to CBR techniques? This example highlighted the fact that in most cases, there will not be an exact match for the current problem to use as a solution model. This example also showed what to do in cases of a similar nature. First the server, using specific and general domain knowledge, reviewed all possible situations in which similar circumstances had occurred. Possibly another customer at one point in time had order another dish that this restaurant did not serve. Then determined the optimal solution for all parties involved. In this case the customer chose an acceptable entree and the restaurant kept the patronage of this individual. However, no exact match of current problem and previous solution existed, what happened. Well in this simple example the server remembered a similar situation from another customer requesting a dish that this restaurant did not offer. In that situation, the server had also suggested a close substitute for the requested item. In this example the server used that solution strategy and substituted swordfish for the requirement and mahi-mahi for the solution. In essence the server used a partial match (the previous request and substitution) and domain specific knowledge (that mahi-mahi is close, in terms of taste, to swordfish) to solve the current problem.
At some point in the past, this server was new to the restaurant business. In that case he most likely asked a fellow employee, with hopefully more experience, for advice on how to deal with the situation. The more experienced employee suggested the substitution strategy and possible items to substitute for the unavailable, requested item. Taking a further step back in time, at some point where no prior experience specific to restaurants existed, the server may have used other experiences to formulate the substitution strategy or developed this strategy by trial and error or reasoning from first principles.
CBR is as well a partial matching strategy for problem resolution - break the problem down hierarchically and progress from the most minute detail to more general solution strategies until a match can be formulated and then substitute domain specific knowledge for the non-matching portions of the current problem and previous solution technique.
In short, the most significant difference between CBR and KBS problem solving techniques, is that in the KBS paradigm, the rules are more concrete and tangible. Whereas in CBR the solution methodology is a process of comparison and evaluation of current needs with existing situations. However, the `rules' approach is solidly grounded in cause and effect derivation of the reasons for doing specific tasks given a certain situation.
MOPs are used to represent knowledge about events. An event can either be a representation of a full event or more typically some significant portion of a complete case. These events within a MOP are useful in partial matching, in that the required information from a specific case can be used to further a solution state without utilizing the entire case, which may not be a perfect match.
The information contained within a MOP is organized and classified by norms. Norms contain basic features of a MOP and are used to structure it. A MOP containing the event `going on a trip', would have norms for planning and what is required to plan, getting tickets and where to go to purchase them, etc. Norms are a listing or classification of expected information or action associated with the event, stored within the MOP.
Finally, a MOP can have a specialization which makes the given information more unique. To further the above example; Suppose you were going on a trip, all of your previous experiences of `going on a trip' would be stored within a MOP, or dynamically linked to this particular MOP. The norms in this event would be:
At this point there can be specialization within the overall MOP of `going on a trip'. The traveler knows ahead of time what type of trip this is to be; a business trip, with business contacts, meetings, etc., or a vacation with sight-seeing, entertainment, etc. From this point in the development of the solution to the problem of going on a trip, more specific information, regarding what type of trip it will be, is required. This more explicit information is considered a specialization of the MOP `going on a trip'.
To complete the example; If one were going on a vacation, he would need to know points of interest in the area and develop a plan to visit the interesting ones. This plan would require knowledge of location, times the attraction is open, cost of admittance, etc. This information, although different in specifics from that of a business trip (i.e. location company as opposed to attraction, time a specific person is available to meet the traveler as opposed to time the attraction is open, etc.) has the same general structure (time, place, admittance, etc.), thus it can be modeled by the same MOP.
Given Information
Dest. Travel Travel Lodging Attraction Business
Cost Time Cost Cost Contacts
(for 3) (days) (for 3) (for 3)
Tampa air - $520 0.5 $55 $60 none
Florida bus - $350 1.0 $80
car - $220 1.5
St. Paul air - $480 0.5 $45 $30 none
Minnesota bus - $300 1.0 $75
car - $160 1.0
Columbus air - $179 0.5 $40 $18 Bill
Ohio bus - $190 1.0 $55
car - $75 0.5
Dallas air - $470 0.5 $75 none Tom
Texas car - $210 1.5 $110
New York air - $850 1.0 $110 $33 Jim
New York bus - $600 2.0 $150 Kevin
car - $330 2.5
Experience Information
Destination Comments
Tampa Had a great time at Disney and Sea World. Florida Good relaxation. St. Paul Mall of America was neat, but trip Minnesota was rushed, hectic Columbus Sea World was wonderful, not much else to do - Ohio good time. Had to meet Bill at the airport - difficult meeting - expensive Dallas Crowded and busy, hot and humid, lots to see Texas Tom is easy going and accomplished alot, would like to go back New York Hot, humid, busy - Expensive New York Most interesting City I've ever been in
CLIPS could be used to represent/store the information in the two tables above. The most efficient way would be to create templates using the CLIPS deftemplate command and store the data ("cases") from the tables as copies of this/these templates.
CLIPS rules that search the above "cases" could then be developed that utilize CLIPS ability to perform pattern matching. One would need to decide how to implement partial matches within these rules (e.g. which items to be matched are most important if a full match can't be achieved). Such partial matches are generally specific to each problem and thus must be coded each time.
Note this is NOT a homework problem to be completed.