Slide 1Attribute-Value Case RepresentationFormalizationSelection of AttributesSelection of the TypesExampleAssignment (I): Monday, October 9thVertex-CoverContents of a CaseObject-Oriented RepresentationTree RepresentationObjects and ClassesExample (Objects and Classes)Relations Between ObjectsCompositional RelationsExample (Compositional Relation)Taxonomical RelationsExample (Taxonomical Relation)Analysis of Object-Oriented Case RepresentationsPredicate Logic RepresentationPredicate Logic Representation (cont’d)Predicate Logic Representation (cont’d)Formulas (SAT): DefinitionGraph RepresentationAnalysis of Graph RepresentationsGraphs: DefinitionSubgraphsGraph-Subgraph IsomorphismAssignment (CSE 435 – Attention: Due on Friday October 8!)Case Representation Cont’dSources:–Chapter 3–www.iiia.csic.es/People/enric/AICom.html–www.ai-cbr.orgAttribute-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•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•Attributes can be the same for all cases or vary from case to caseFormalization•Attributes: A1, A2, .., An•Types: T1, T2, …, Tn•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)Unknown values is the main difference between a case and an example in the sense of IDTSelection of Attributes•Situation description:Independence: Attributes should represent independent features whenever possibleCompleteness: the attributes should be sufficient to determine if the case can be reused in a new situationMinimalist: The only attributes that should be included in a case are those used in to compute similarity(ex: type of restaurant versus week day)(not always possible: patrons and day of the week are related)(ex: Not including Patrons may make it impossible to learn a hypothesis function)(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 difficultExampleCase 1•Front-light = doesn’t work•Car-type = Golf II, 1.6•Year = 1993•Batteries = 13.6V•…Symptoms:Solution:•Diagnosis: Front-lights-safeguard = broken•Help measures: “Replace front lights safeguard”Symbol: work,doesn’t workSymbol: work,doesn’t workSymbol: Golf, Mercedes,…Symbol: Golf, Mercedes,…Symbol: 1960, …, 2002Symbol: 1960, …, 2002Real: 1V … 30VReal: 1V … 30VTextTextSymbol: ok, brokenSymbol: ok, brokenAssignment (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 2. Proof that Vertex-cover is NP-complete (formulate decision problem; proof that is in NP; reduce Clique into Vertex-Cover)(CSE 435)(CSE 335/435)Vertex-CoverACBDFGEH1020164682420691312Given 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 bothVertex-Cover Problem: Given a graph, find the vertex-cover containing the minimum number of nodesContents 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Adequacy•Scope of the information:Complete solution/partial solution Detail or abstracted solution•Representation formalism:Attribute-value pairsStructured representation: objects, trees High-order: predicate logic, plans(example: help-desk systems)(example: planning)Annotations about situations where reusing the case didn’t help or was very helpfulObject-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•Classes of objects are ordered in a inheritance hierarchySubclasses inherit properties of the superclass(example in OOP: instance vs classes)(example in OOP: “this” or “self” and “super”)Tree RepresentationStructured representations are needed when there are multiple relations between elements of the problemObjects 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 classExample (Objects and Classes)•Front-light = doesn’t work•Car-type = Golf II, 1.6•Year = 1993•Batteries = 13.6V•…•Front-light = doesn’t work•Car-type = Golf II, 1.6•Year = 1993•Batteries = 13.6V•…Instance: Entry # 314Instance: Entry # 314•Front-light: symbol•Car-type : symbol•Year: Symbol•Batteries: Real•…•Front-light: symbol•Car-type : symbol•Year: Symbol•Batteries: Real•…Class: SymptomsClass: SymptomsRelations Between Objects•Relations between objects are important•Typical kinds of relations:Taxonomical relations: “is-a-kind-of” indicates abstraction/refinement relations between objectsCompositional relations: “is-a-part-of” indicates that objects are parts of other objects(example: car is a kind of transportation means)(example: motor is a part of a car)Compositional RelationsCarFuel system Motor Electrical systemCarburatorExhaust…•Compositional relations are described through relational attributes• Relational Attributes are attributes whose values are objectsExample (Compositional Relation)•Model: symbol•Make : symbol•Year: Symbol•Motor: MotorC•…•Model: