CaseBasedReasoning

1、1Case Based ReasoningPKB - Antonie2Faced this situation before? Oops the car stopped. What could have gone wrong? Aah. Last time it happened, there was no petrol. Is there petrol? Yes. Oh but wait I remember the tyre was punctured (ban bocor) This is the normal thought process of a human when faced

2、with a problem which is similar to a problem he/she had faced before.3How do we solve problems? By knowing the steps to apply from symptoms/gejala to a plausible diagnosis But not always applying causal knowledge sebab - akibat How does an expert solve problems? uses same “book learning” as a novice

3、 but quickly selects the right knowledge to apply Heuristic knowledge (“rules of thumb”) “I dont know why this works but it does and so Ill use it again!” difficult to elicit4So what? Reuse the solution experience when faced with a similar problem. This is Case Based Reasoning (CBR)! memory-based pr

4、oblem-solving re-using past experiences Experts often find it easier to relate stories about past cases than to formulate rules5Whats CBR? To solve a new problem by remembering a previous similar situation and by reusing information and knowledge of that situation Ex: Medicine doctor remembers previ

5、ous patients especially for rare combinations of symptoms Ex: Law English/US law depends on precedence case histories are consulted Ex: Management decisions are often based on past rulings Ex: Financial performance is predicted by past results6Definitions of CBR Case-based reasoning is reasoning by

6、remembering - Leake, 1996 A case-based reasoner solves new problems by adapting solutions that were used to solve old problems - Riesbeck & Schank, 1989 Case-based reasoning is a recent approach to problem solving and learning - Aamodt & Plaza, 1994 7History Roots of CBR is found in the work

7、s of Roger Shank on dynamic memory. Other trails into the CBR field has come from Analogical reasoning Problem solving and experimental learning within philosophy and psychology The first CBR system, CYRUS developed by Janet Kolodner at Yale university.8The Limitations of Rules The success of rule-b

8、ased expert systems is due to several factors: They can mimic some human problem-solving strategies Rules are a part of everyday life, so people can relate to them However, a significant limitation is the knowledge elicitation bottleneck Experts may be unable to articulate their expertise Heuristic

9、knowledge is particularly difficult Experts may be too busy9CBR Cycle10R4 Cyclepropose solutions from retrieved casesadapt and repairproposed solutionCBRintegrate incase-basefind similar problems11CBR System Components Case-base database of previous cases (experience) Retrieval of relevant cases ind

10、ex for cases in library matching most similar case(s) retrieving the solution(s) from these case(s) Adaptation of solution alter the retrieved solution(s) to reflect differences between new case and retrieved case(s)12CBR Assumption(s) The main assumption is that: Similar problems have similar solut

11、ions: e.g., an aspirin can be taken for any mild pain Two other assumptions: The world is a regular place: what holds true today will probably hold true tomorrow (e.g., if you have a headache, you take aspirin, because it has always helped) Situations repeat: if they do not, there is no point in rem

12、embering them (e.g., it helps to remember how you found a parking space near that restaurant)13Two big tasks of CBR Classification tasks (good for CBR)Diagnosis - what type of fault is this?Prediction / estimation - what happened when we saw this pattern before? Synthesis tasks (harder for CBR) Engi

13、neering Design Planning Scheduling14Technical Diagnosis of Car Faults15Case Representation Flat feature-value list Object Oriented representation Graph representation The choice of representation is Dependent on requirements of domain and task Structure of already available case data16Problem to be

14、solved17How CBR solves problems New problem can be solved by retrieving similar problems adapting retrieved solutions Similar problems have similar solutions?SSSSSSSSSPPPPPPPPPX18CBR Knowledge Containers Cases lesson to be learned context in which lesson applies Description Language features and val

15、ues of problem/solution Retrieval Knowledge features used to index cases relative importance of features used for similarity Adaptation Knowledge circumstances when adaptation is needed alteration to apply19Corporate Memory Cases from database, archive, . . . Issues case bias? coverage? description

16、language e.g. agreement on terms Case-base cannot contain all formulations good coverage prototypical and exceptional cases Opportunity for multiple sources shared knowledge across companies20New Car Diagnosis Problem A new problem is a case without a solution part Not all problem features must be k

17、nown same for cases Problem Symptom: brakelight does not work Car: Ford Fiesta Year: 1997 Battery: 9.2v Headlights: undamaged HeadlightSwitch: ?FeatureValueNew21 Compare new problem to each case Select most similar Similarity is most important concept in CBR When are two cases similar? How are cases

18、 ranked according to similarity? Similarity of cases Similarity for each feature Depends on feature valuesRetrieving A Car Diagnosis CaseNew ProblemCase Case Case Case Case Case Case Case 1Similar?22Similarity Computation for case 1Figure Credit: R. Bergmann, University of Kaiserslautern23Similarity

19、 Computation for case 2Figure Credit: R. Bergmann, University of Kaiserslautern24Similarity Measurement Purpose: To select the most relevant case Basic Assumption: Similar problems have similar solutions Similarity value between 0 and 1 are assigned for feature value pairs E.g.: Feature: ProblemFron

20、t Light does not work Break Light does not work .8Front Light does not work Engine doesnt start.425Similarity Measurement Feature: Battery Voltage Different features have different importance Two kinds of Similarity Measures Local Similarity similarity on feature level Global Similarity - similarity

21、 on case or object level12.6 13.612.6 6.7.9.126Calculating Feature Similarity Distances between values of individual features problem and case have values p and c for feature f Distance for Numeric features df(problem,case) = |p - c|/(max difference) Distance for Symbolic features df(problem,case) =

22、 0 if p = c = 1 otherwise Similarityf(problem,case) = 1 - d Degree of similarity is between 0 and 127Reuse Solution from Case 1 New Problem Symptom: brakelight does not work Car: Ford Fiesta Year: 1997 Battery: 9.2v Headlights: undamaged HeadlightSwitch: ? Problem Symptom: headlight does not work So

23、lution Diagnosis: headlight fuse blown Repair: replace headlight fuse Solution to New Problem Diagnosis: headlight fuse blown Repair: replace headlight fuse After Adaptation Diagnosis: brakelight fuse blown Repair: replace brakelight fuseCase 128Matching strings exact match: two strings are similar

24、if they are spelled the same way spelling check: compares the number of letters which are the same in two strings (Useful for strings consisting of one word only) word-count: counts the number of matching words of two cases. (Useful for strings consisting of several words).29Indexing: Why do we want

25、 an index? Efficiency if similarity matching is computationally expensive Relevancy of cases for similarity matching Cases are pre-selected from case-baseHighLow200010030030What to index?Client Ref #: 64Client Name: John SmithAddress: 39 Union StreetTel: 01224 665544Photo:Age: 37Occupation: IT Analy

26、stIncome: 20000Unindexed featuresIndexed featuresCase Features are:- Indexed - Unindexed31HighLow2000100300Decision Trees as an IndexSolubility?Dose?lowhigh20032Re-Using Retrieved Solutions Single retrieved solution Re-use this solution Multiple retrieved solutions Vote/average of retrieved solution

27、s Weighted according to Ranking Similarity Iterative retrieval Solve components of the solution one at a time33How to Adapt the Solution Adaptation alters proposed solution: Null adaptation - copy retrieved solution Used by CBR-Lite systems Manual or interactive adaptation User adapts the retrieved

28、solution (Adapting is easier than solving?) Automated adaptation CBR system is able to adapt the retrieved solution Adaptation knowledge required34Automated Adaptation Methods Substitution change some part(s) of the retrieved solution simplest and most common form of adaptation Transformation alters

29、 the structure of the solution Generative replays the method of deriving the retrieved solution on the new problem most complex form of adaptation35Examples of Adaptation CHEF CBR system to plan Szechuan recipes Hammond (1990) Substitution adaptation substitute ingredients in the retrieved recipe to

30、 match the menu Retrieved recipe contains beef and broccoli New menu requires chicken and snowpeas Replace chicken for beef, snowpeas for broccoli Transformation adaptation Add, change or remove steps in the recipe Skinning step added for chicken, not done for beef 36Examples of Adaptation Car diagn

31、osis example Symptoms, faults and repairs for brake lights are analogous to those for headlight Substitution: brake light fuse Planning example Train journeys and flights are analogous Transformation: flights need check-in step added37Retention What can be learned New experience to be retained as new case Representing the new case Contents of new case Indexing of new case Forgetting cases For efficiency or because out of date Deleting an old case Old is not necessarily bad Does it leave a gap?38Pros & Cons of CBR Advantages solutions are qui