1Case-Based Reasoning6.871: Knowledge-Based Application SystemsSpring 2004Lecture 176.871 - Lecture 172What is Case-Based Reasoning (CBR)Case-based reasoning is […] remembering.Leake, 1996A case-based reasoner solves new problems by adapting solutions that were used to solve old problems. Riesbeck & Schank, 1989Case-based reasoning is a recent approach to problem-solving and learning […]. Aamodt & Plaza, 1994Case-based reasoning is both […] the ways people use cases to solve problems and the ways we can make machines use them. Kolodner, 19936.871 - Lecture 173What is Case-Based Reasoning?• A methodology to model human reasoning• A methodology for building intelligent systems•CBR:– Store previous experience (cases) in memory– Solve new problems by•Retrieving experience about similar situations•Reusing the experience in context of new situation: use all or part, or adapt,test•Storing new experience in memory, i.e. learn6.871 - Lecture 174WhyCase-Based Reasoning?• It's pervasive– Law, medicine, design, politics, common sense• It's intuitive– Seems to match our experience•It's powerful–One or two order of magnitudespeedup• It provides a natural means to learn from experience– An almost effortless side-effect of problem solving• It can work in partially understood domains– When we don't have a good theory/model• It provides a way to avoid mistakes– Can save additional time6.871 - Lecture 175So …• Is it THE ANSWER?• Isn't this just another name for frames?6.871 - Lecture 177A Simple Example: Diagnosis of Car Faults• Given: Symptoms e.g. engine doesn’t startand measured values e.g. battery voltage = 6.3V• Goal: Find cause for fault e.g. dead batteryand repair strategye.g. charge battery26.871 - Lecture 178Example Cases Problem & Features• Problem: Front light not working• Car: VW Golf, 2.0L• Year: 1999• Battery voltage: 13.6V• State of lights: OK• State of light switch: OKSolution• Diagnosis: Front light fuse defect• Repair: Replace front light fuseSolution• Diagnosis: Front light fuse defect• Repair: Replace front light fuseCase 1Problem & Features• Problem: Front light not working• Car: Passat• Year: 2000• Battery voltage: 12.6V• State of lights: surface damaged• State of light switch: OKSolution• Diagnosis: Bulb defect• Repair: Replace front lightSolution• Diagnosis: Bulb defect• Repair: Replace front lightCase 26.871 - Lecture 179New Problem Problem & Features• Problem: Brake light not working• Car: Passat V6• Year: 2002• Battery voltage: 12.9V• State of lights: OK• State of light switch: ? • Observations define a new problem• Not all feature values maybe known• New problem = case withoutsolution6.871 - Lecture 1710Find Similar Case Case xSimilar ?New Problem6.871 - Lecture 1711Find Similar Case • Compare similarity of each feature• But some features may be more importantCase xSimilar ?New Problem6.871 - Lecture 1712Compare with Case 1 Problem & Features• Problem: Brake light not working• Car: Passat V6• Year: 2002• Battery voltage: 12.9V• State of lights: OK• State of light switch: ? Problem & Features• Problem: Front light not working• Car: VW Golf, 2.0L• Year: 1999• Battery voltage: 13.6V• State of lights: OK• State of light switch: OKSolution• Diagnosis: Front light fuse defect• Repair: Replace front light fuseSolution• Diagnosis: Front light fuse defect• Repair: Replace front light fuseCase 1very importantless important6.871 - Lecture 1713Compare with Case 1 Problem & Features• Problem: Brake light not working• Car: Passat V6• Year: 2002• Battery voltage: 12.9V• State of lights: OK• State of light switch: ? Problem & Features• Problem: Front light not working• Car: VW Golf, 2.0L• Year: 1999• Battery voltage: 13.6V• State of lights: OK• State of light switch: OKSolution• Diagnosis: Front light fuse defect• Repair: Replace front light fuseSolution• Diagnosis: Front light fuse defect• Repair: Replace front light fuseCase 1very important wt of 6less important wt of 10.80.40.70.91.0Similarity by wted avg = 1/20 (6*0.8 + 1*0.4 + 1*0.7 + 6*0.9 + 6*1.0) = 0.8736.871 - Lecture 1714Compare with Case 2 Problem & Features• Problem: Brake light not working• Car: Passat V6• Year: 2002• Battery voltage: 12.9V• State of lights: OK• State of light switch: ? very important wt of 6less important wt of 10.80.80.80.90.0Similarity by wted avg = 1/20 (6*0.8 + 1*0.8 + 1*0.8 + 6*0.9 + 6*0.0) = 0.59Problem & Features• Problem: Front light not working• Car: Passat• Year: 2000• Battery voltage: 12.6V• State of lights: surface damaged• State of light switch: OKSolution• Diagnosis: Bulb defect• Repair: Replace front lightSolution• Diagnosis: Bulb defect• Repair: Replace front lightCase 26.871 - Lecture 1715Reuse Case 1 Problem & Features• Problem: Brake light not working• …Problem & Features• Problem: Front light not working• …Solution• Diagnosis: Front light fuse defect• Repair: Replace front light fuseCase 1New Solution• Diagnosis: Brake light fuse defect• Repair: Replace Brake light fuseAdapt6.871 - Lecture 1716Store New Case Problem & Features• Problem: Brake light not working• Car: Passat V6• Year: 2002• Battery voltage: 12.9V• State of lights: OK• State of light switch: OKSolution• Diagnosis: Bulb defect• Repair: Replace front lightSolution• Diagnosis: Brake light fuse defect• Repair: Replace brake lightCase 36.871 - Lecture 1717Case-Based Diagnosis • A case represents one diagnostic situation:–symptoms– failure and cause– feature values– repair strategies– outcome: implicit assumption failure fixed • Problem solving:– store collection of cases– find similar case, adapt if necessary, suggest repair strategies•Learning:– observe outcome, store new case6.871 - Lecture 1718Case-Based Reasoning• Retrieve• Reuse: adapt/repair• Store/Learn6.871 - Lecture 1719• Retrieve–How?– Selecting indexes• Determine case utility/lessons• Describe circumstances where it will be useful• Represent those circumstances (features)• GeneralizeCase-Based Reasoning46.871 - Lecture 1720• Retrieval: Indexing– "Look at the tasks a case might be used for and choose as indexes those sets of its features that describe when it can be useful for