Unformatted text preview:

Slide 1Taxonomy of Problem SolvingClassification TasksRestaurant ExampleClassification ApproximationDiagnosisCBR: DefinitionProblem-Solving with CBRCBR: First ExampleSome Interrelations between TopicsCBR: Outstanding IssuesCBR: HistoryTaxonomy of Problem Solving and CBRHomework (next class)About PresentationsTopicsSlide 17Taxonomy of Problem Solving and Case-Based Reasoning (CBR)Sources:–www.iiia.csic.es/People/enric/AICom.html–www.ai-cbr.org–www.aic.nrl.navy.mil/~aha/slides/Taxonomy of Problem Solving•Synthesis:constructing a solution Methods: planning, configuration•Analysis:interpreting a solution Methods: classification, diagnosisClassification TasksProperties:•Problem domain consists of two disjoint sets of domain objects:A set of Observations, SA set of Classes, C•Problem description, P: set of observations (subset of S)•Solution, c: a class (an element of C )•A collection of problem descriptions: P•A classifier is a function:class: P  CRestaurant exampleRestaurant ExampleEx’ple Bar Fri Hun Pat Alt Type wait x1 no no yes some yes French yes x4 no yes yes full yes Thai yes x5 no yes no full yes French no x6 yes no yes some no Italian yes x7 yes no no none no Burger no x8 no no yes some no Thai yes x9 yes yes no full no Burger no x10 yes yes yes full yes Italian no x11 no No no none no Thai noClassification Approximation•Classification Approximation:Input: A collection of pairs problem-solution (P1,c1), (P2,c2), …, (Pn,cn). These pairs are a subset of an unknown classifier: class: P  COutput: a hypothesis classifier H such that:1.For each Pi, H(Pi) = class(Pi)2.H is “close” to class for other P in PDiagnosis•Diagnosis is a generalization of a classification problem in which not all observations are known in advance•As part of the diagnosis process all the relevant observations are determined•Example:Help-desk operators query the customer about the malfunctions in the service/productcase-based reasoning (CBR) can be used for diagnosis tasksCBR: DefinitionA problem-solving methodology where solutions to similar, previous problems are reused to solve new problems.A problem-solving methodology where solutions to similar, previous problems are reused to solve new problems.Notes: •Intuitive•AI focus (e.g., search, representation, knowledge)•Case = <problem, solution>•Lazy approach (e.g., to learning)Notes: •Intuitive•AI focus (e.g., search, representation, knowledge)•Case = <problem, solution>•Lazy approach (e.g., to learning)Courtesy of David W. AhaProblem-Solving with CBRProblem SpaceSolution Spacep2p1s1s2p3CBR(problem) = solutions4p?p?s?s3Courtesy of David W. AhaCBR: First ExampleExample: Slide CreationExample: Slide CreationRepository of Presentations:-5/9/00: ONR review-8/20/00: EWCBR talk-4/25/01: DARPA reviewSpecificationRevised talk 3. ReviseSlides ofTalks w/SimilarContent1. Retrieve5. RetainNew Case4. ReviewNew Slides- 7/28/12: class@ 335First draft2. Reuseclass@CSE335Courtesy of David W. AhaSome Interrelations between Topics•Retrieval–Information gain–Similarity metrics–Indexing•Reuse–Rule-based systems•Revise & Review–Constraint-satisfaction systems•Retain–Induction of decision treesCBR: Outstanding Issues1. Sometimes natural (e.g., law, diagnosis)1. Sometimes natural (e.g., law, diagnosis)2. Cases simplify knowledge acquisition•Easier to obtain than rules•Captures/shares people’s experiences2. Cases simplify knowledge acquisition•Easier to obtain than rules•Captures/shares people’s experiences3. Good for some types of tasks•When perfect models are not available•Dynamic physical systems •Legal reasoning•When small disjuncts are prevalent•Language learning 3. Good for some types of tasks•When perfect models are not available•Dynamic physical systems •Legal reasoning•When small disjuncts are prevalent•Language learning 4. Commercial application•Help-desk systems (e.g., Inference corp.: +700 clients)•e-commerce (e.g., Analog Device)4. Commercial application•Help-desk systems (e.g., Inference corp.: +700 clients)•e-commerce (e.g., Analog Device)CBR: History1982-1993: Roger Schank’s group, initially at Yale•Modeling cognitive problem solving (Kolodner, 1993)•New topics: Case adaptation, argument analysis, …1993: European emergence (EWCBR’93)•Expert systems, empirical/application focus1995: First international conference (ICCBR’95)•Knowledge containers (M. Richter)•First IJCAI Best Paper Award (Smyth & Keane: Competence models)1993-1998: INRECA ESPRIT projects 1997-: Textual CBR (Lenz, Ashley, others)1997-: Case-based maintenance1997-: Knowledge management1999-: e-Commerce2003-: Readings in CBR1990: First substantive deployed application (Lockheed)1992: Derivational analogy (Veloso, Carbonell)1991-: Help-desk market niche (Inference/eGain)1995-: Well established ICCBR conferencesTaxonomy of Problem Solving and CBR•Synthesis:constructing a solution Methods: planning, configuration•Analysis:interpreting a solution Methods: classification, diagnosisMoreapplicationsresearchUse CBR?Homework (next class)Read Chapter 2 of the Experience Management book and answer the following questions:• Provide an example of something that is data but not information, something that is information but not knowledge, and something that is knowledge• Give an example of experience. Why can’t experience be general knowledge?• What is the relation between experience management and CBR? What is/are the difference(s)?• Provide an example for each of the 4 phases of the CBR cycle for a domain of your own (can’t be the restaurant example). First you would need to think what is the task that you are trying to solve. Please specify. Is this a classification or a synthesis task? Please specifyAbout Presentations•You are welcomed to suggest your own topicsThe first two topics (next page) came from conversations with students•E-mail me your topic of choiceFirst person to email me the topic is his/hers•Only for 400-level students present•Prepare for a full class presentation (50 minutes)•Need to meet me one week before the presentation Have the PowerPoint presentation ready so I can go over it•All presentations will take place in the second half of the semesterWill


View Full Document

LEHIGH CSE 335 - Taxonomy of Problem Solving

Download Taxonomy of Problem Solving
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Taxonomy of Problem Solving and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Taxonomy of Problem Solving 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?