Much of the information contained within this document comes from work completed by Mark McVea as part of a special problems course.

# CBR - Case Based Reasoning

## What Is CBR

As the name implies; it is Reasoning, Based on Cases.

From Webster's Dictionary -

• Reasoning - The drawing of inferences or conclusions through the use of facts or other intelligible information.
• Based - Grounded in known theory, knowledge or information.
• Case - Similar set of related facts or information.

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.

## A Little History

CBR has grown, in part, out of the more general field of artificial intelligence. A.I. is distinct from general computing due to its base premise of attempting to solve a general purpose problem. Most computers and application code are designed to move and manipulate numbers, `number crunchers'. On the other hand, the ultimate expression of artificial intelligence is to develop computer code that mimics and can implement the general mechanisms underlying human intelligence. In other words, develop a computer program that generates solution(s) to new problems based on first principles of logic. First principles are a logical discourse on topic matter that leads to a solution of the problem, given in terms a knowledgable human can understand. No a-priori knowledge of the problem domain or other solutions of similar problems is required.

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.

## Thought and a Real World Example

The process of thinking and reasoning requires an understanding of more than just the immediate facts. Thought requires the user to have and understand the explanation of the situation that is being presented. This seems to be quite cumbersome in terms of the number of problems a typical individual is faced with each and every day. One method to explain the obvious lack of a complete understanding of each and every event an individual is faced with is to review a simple example.

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.

## How Does This Apply To CBR

In a similar fashion CBR techniques are consider domain dependent. Meaning that any CBR system created is limited in scope to some known problem domain and its attendant knowledge base is optimized for these type of problems. Similarly the new problems presented to the CBR for analysis and matching will likewise be limited to an appropriate subset of all problems. This is advantageous, since a CBR system must contain enough cases within its knowledge base to provide diverse enough domain knowledge to solve new problems.

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.

## What's The Difference Between CBR And KBS

Knowledge based systems use rules to guide their decision processes. Typically a knowledge engineer works with a domain `expert' to derive the heuristics that, the expert uses when solving a problem. Whereas, case based reasoning `looks' for similarities between the current needs and previous examples of similar problems and their attendant solutions. Rule base programming is currently very popular and well developed. Most `experts' will expound on the rules they use to solve either everyday or very difficult and detailed problems. However research into human problem solving has determined that in almost all cases the `rules' used by experts have been in part derived from a cause and effect relationship derived from previous experiences - cases.

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.

## Memory Organization Packages, MOPs

Knowledge within a CBR system is very dynamic in nature. Case base reasoners use dynamic memory to model a changing situation as the problem solution develops. The problem posed to a CBR system is typically static in nature, however as a solution develops by matching previous, similar cases to the new problem definition, the system must determine if the current match is `good enough' to be used to derive a complete solution to the problem at hand. As the system reasons about the state of partial match it has to modify its solution strategy to determine how this current case fits into the required solution. Knowledge is represented in discrete and distinctive packets called Memory Organization Packages or MOPs. Each of these represents the basic format and knowledge representation developed in the scripts morphology. However in the scripts morphology the knowledge and its representation were dynamic, that is they could not be reformulated and represented to better suit the existing problem. Also there was no mechanism provided for inter-linking them with other packets of information. MOPs, on the other hand, provide the necessary mechanism for linking information and dynamic representation.

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:

1. Planning the trip, destination, mode of transport, etc.
2. Ensuring enough money is available for the trip.
3. Getting tickets, reservations, confirmations, etc.
4. Obtaining information about things to be done, etc.

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.

## A Simple Problem

Problem Statement
1. You want to get away with your wife and child for awhile
2. You have saved \$800.00
3. You have five days off from work

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.