Case Representation Cont d Sources Chapter 3 www iiia csic es People enric AICom html www ai cbr org Attribute Value Case Representation Case a collection of attribute value pairs Example Each row in the wait restaurant table is a case Examples in the IDT context correspond to cases Attributes can be the same for all cases or vary from case to case Each attribute is from a certain type For example Integer all integers or an interval Real all numbers or an interval Symbol finite set of alternatives e g Thai Italian Hypertext HTML Formalization Attributes A1 A2 An Types T1 T2 Tn Unknown values is the main difference between a case and an example in the sense of IDT Values a1 in T1 a2 in T2 an in Tn A case is defined as follows If all cases have the same number of attributes a case is a vector a1 an in T1 unknown Tn unknown If cases have a varying number of attributes a case is a set Ap ap Ak ak attributes that are not in the set are considered unknown Selection of Attributes Situation description Independence Attributes should represent independent features whenever possible ex type of restaurant versus week day not always possible patrons and day of the week are related Completeness the attributes should be sufficient to determine if the case can be reused in a new situation ex Not including Patrons may make it impossible to learn a hypothesis function Minimalist The only attributes that should be included in a case are those used in to compute similarity ex name of the waitress is not a relevant attribute Selection of the Types Selection of the types is defined by the elements needed to compute similarity Symbols Ideal for a small number of alternatives e g type of restaurant Integer Real Ideal for measures and other numeric values Computation of similarity Text Ideal for unstructured information Computation of similarity can be very difficult Example Case 1 Symptoms Front light doesn t work Car type Golf II 1 6 Year 1993 Batteries 13 6V Symbol Symbol work doesn t work doesn twork work Symbol Symbol Golf Golf Mercedes Mercedes Symbol Symbol 1960 1960 2002 2002 Real Real 1V 1V 30V 30V Solution Diagnosis Symbol Symbol ok ok broken broken Front lights safeguard broken Help measures Replace front lights safeguard Text Text Assignment I Monday October 9th 1 Select a machine that you feel particularly familiar with it e g your PC the graphic card of your pc Obtain at least 10 attributes and their types that you feel are relevant to make a diagnosis of a failure for that machine CSE 335 435 2 Proof that Vertex cover is NP complete formulate decision problem proof that is in NP reduce Clique into Vertex Cover CSE 435 Vertex Cover Given a graph G a vertex cover V is a collection of nodes in G such that for every arc w v either w is in V or v is in V or both 10 B H 16 9 12 A 4 20 G C 8 F 6 13 D 6 24 E 20 Vertex Cover Problem Given a graph find the vertexcover containing the minimum number of nodes Contents of a Case Generally a case contains specific knowledge about a previous problem solving experience Typically a case contains the following information Problem Situation Solution Annotations about situations where reusing Adequacy the case didn t help or was very helpful Scope of the information Complete solution partial solution Detail or abstracted solution Representation formalism Attribute value pairs example help desk systems Structured representation objects trees High order predicate logic plans example planning Object Oriented Representation Objects are described as a fixed collection of attributes A case consists of a collection of objects There are relations between objects in a case Each object belongs to a class of objects example in OOP instance vs classes Classes of objects are ordered in a inheritance hierarchy Subclasses inherit properties of the superclass example in OOP this or self and super Tree Representation Structured representations are needed when there are multiple relations between elements of the problem Objects and Classes An object class describes the structure of an object through a finite collection of attributes and their types An instance or an object of an object class assigns values of the corresponding type for each attribute in the class Example Objects and Classes Class Class Symptoms Symptoms Front light Front light symbol symbol Car type Car type symbol symbol Year Year Symbol Symbol Batteries Batteries Real Real Instance Instance Entry Entry 314 314 Front light Front light doesn t doesn twork work Car type Car type Golf GolfII II 1 6 1 6 Year Year 1993 1993 Batteries Batteries 13 6V 13 6V Relations Between Objects Relations between objects are important Typical kinds of relations Taxonomical relations is a kind of indicates abstraction refinement relations between objects example car is a kind of transportation means Compositional relations is a part of indicates that objects are parts of other objects example motor is a part of a car Compositional Relations Car Fuel system Motor Electrical system Carburetor Exhaust Compositional relations are described through relational attributes Relational Attributes are attributes whose values are objects Example Compositional Relation Class Class CarC CarC Model Model symbol symbol Make Make symbol symbol Year Year Symbol Symbol Motor Motor MotorC MotorC Instance Instance Toyota ToyotaTercel Tercel Model Model Tercel Tercel Make Make Toyota Toyota Year Year 1991 1991 Motor Motor Class Class MotorC MotorC SerialN SerialN int int Liter Liter real real Carburator Carburator CarbC CarbC Instance Instance SerialN SerialN 1263455233 1263455233 Liter Liter 1 5 1 5 Carburator Carburator Taxonomical Relations Transportation Means Air trans Land trans Sea trans car Sport utility Taxonomical relations are explicitly represented The subclass inherits all the attributes of the superclass Example Taxonomical Relation Class Class Land LandTransport Transport Max Maxspeed speed int int horseP horseP int int Class Class CarC CarC Model Model symbol symbol Make Make symbol symbol Year Year Symbol Symbol Price Price int int instance instance ToyotaTercel ToyotaTercel Max Maxspeed speed 100 100mph mph horseP horseP Model Model Tercel Tercel Make Make Toyota Toyota Year Year 1991 1991 Price Price 2000 2000 Analysis of Object Oriented Case Representations Advantages Structured and natural in many domains Relations between objects are explicitly represented More compact storage as with attribute values Structured relations can