CS 460, Sessions 14-151Knowledge Representation• Knowledge engineering: principles and pitfalls• Ontologies•ExamplesCS 460, Sessions 14-152Knowledge Engineer• Populates KB with facts and relations• Must study and understand domain to pick important objects and relationships• Main steps:Decide what to talk aboutDecide on vocabulary of predicates, functions & constantsEncode general knowledge about domainEncode description of specific problem instancePose queries to inference procedure and get answersCS 460, Sessions 14-153Knowledge engineering vs. programmingKnowledge Engineering Programming1. Choosing a logic Choosing programming language2. Building knowledge base Writing program3. Implementing proof theory Choosing/writing compiler4. Inferring new facts Running programWhy knowledge engineering rather than programming?Less work: just specify objects and relationships known to be true, but leave it to the inference engine to figure out how to solve a problem using the known facts.CS 460, Sessions 14-154Properties of good knowledge bases• Expressive•Concise• Unambiguous• Context-insensitive• Effective•Clear•Correct•…Trade-offs: e.g., sacrifice some correctness if it enhances brevity.CS 460, Sessions 14-155Efficiency• Ideally: Not the knowledge engineer’s problemThe inference procedure should obtain same answers no matter how knowledge is implemented.• In practice:- use automated optimization- knowledge engineer should have some understanding of how inference is doneCS 460, Sessions 14-156Pitfall: design KB for human readers• KB should be designed primarily for inference procedure!• e.g.,VeryLongNamepredicates:BearOfVerySmallBrain(Pooh) does not allow inference procedure to infer that Pooh is a bear, an animal, or that he has a very small brain, …Rather, use:Bear(Pooh)∀ b, Bear(b) ⇒ Animal(b)∀ a, Animal(a) ⇒PhysicalThing(a)…[See AIMA pp. 220-221 for full example]In other words:BearOfVerySmallBrain(pooh) = x(pooh)CS 460, Sessions 14-157Debugging• In principle, easier than debugging a program,because we can look at each logic sentence in isolation and tellwhether it is correct.Example:∀ x, Animal(x) ⇒∃ b, BrainOf(x) = bmeans “there is some object that is the value of the BrainOf function applied to an animal”and can be corrected to mean “every animal has a brain”without looking at other sentences.CS 460, Sessions 14-158Ontology• Collection of concepts and inter-relationships• Widely used in the database community to “translate” queries and concepts from one database to another, so that multiple databases can be used conjointly (database federation)CS 460, Sessions 14-159Ontology ExampleKhan & McLeod, 2000CS 460, Sessions 14-1510Towards a general ontologyDevelop good representations for:-categories-measures- composite objects- time, space and change- events and processes- physical objects- substances- mental objects and beliefs-…CS 460, Sessions 14-1511Representing Categories• We interact with individual objects, but…much of reasoning takes place at the level of categories.• Representing categories in FOL:-use unary predicatese.g., Tomato(x)- reification: turn a predicate or function into an objecte.g., use constant symbol Tomatoes to refer to set of all tomatoes“xis a tomato” expressed as “x∈Tomatoes”• Strong property of reification: can make assertions about reified category itself rather than its memberse.g., Population(Humans)= 5e9-in a table form (small set of objects)-based on its propertiesCS 460, Sessions 14-1512Categories: inheritance• Allow to organize and simplify knowledge basee.g., if all members of category Foodare edibleand Fruitsis a subclass of Foodand Applesis a subclass of Fruitsthen we know (through inheritance) that apples are edible.• Taxonomy: hierarchy of subclasses• Because categories are sets, we handle them as such.e.g., two categories are disjoint if they have no member in commona disjoint exhaustive decomposition is called a partitionetc…CS 460, Sessions 14-1513Example: Taxonomy of hand/arm movementsHand/arm movementGestures Unintentional MovementsManipulative CommunicativeActs SymbolsMimetic Deictic Referential ModalizingQuek,1994, 1995.CS 460, Sessions 14-1514Measures• Can be represented using units functionse.g., Length(L1) = Inches(1.5) = Centimeters(3.81)• Measures can be used to describe objectse.g., Mass(Tomato12) = Kilograms(0.16)• Caution: be careful to distinguish between measures and objectse.g., ∀b, b∈DollarBills ⇒ CashValue(b) = $(1.00)CS 460, Sessions 14-1515Composite Objects• One object can be part of another.• PartOf relation is transitive and reflexive:e.g., PartOf(Bucharest, Romania)PartOf(Romania, EasternEurope)PartOf(EasternEurope, Europe)Then we can infer Part Of(Bucharest, Europe)• Composite object: any object that has partsCS 460, Sessions 14-1516Composite Objects (cont.)• Categories of composite objects often characterized by their structure, i.e., what the parts are and how they relate.e.g., ∀a Biped(a) ⇒∃ ll, lr, b Leg(ll) ∧ Leg(lr) ∧ Body(b) ∧PartOf(ll, a) ∧ PartOf(lr, a) ∧ PartOf(b, a) ∧Attached(ll, b) ∧ Attached(lr, b) ∧ll ≠ lr ∧∀x Leg(x) ∧ PartOf(x, a) ⇒ (x = ll ∨ x = lr)• Such description can be used to describe any objects, including events. We then talk about schemas and scripts.CS 460, Sessions 14-1517Events• Chunks of spatio-temporal universee.g., consider the event WorldWarIIit has parts or sub-events: SubEvent(BattleOfBritain, WorldWarII)it can be a sub-event: SubEvent(WorldWarII, TwentiethCentury)• Intervals: events that include as sub-events all events occurring in a given time period (thus they are temporal sections of the entire spatial universe).• Cf. situation calculus: fact true in particular situationevent calculus: event occurs during particular intervalCS 460, Sessions 14-1518Events (cont.)• Places: spatial sections of the spatio-temporal universe that extend through time• Use In(x) to denote subevent relation between places; e.g. In(NewYork, USA)• Location function: maps an object to the smallest place that contains it:∀x,l Location(x) = l ⇔ At(x, l) ∧∀ll At(x, ll) ⇒ In(l, ll)CS 460, Sessions 14-1519Times, Intervals and Actions• Time intervals can be partitioned between moments (=zero duration) and extended intervals:• Absolute times can then be derived from defining a time scale (e.g., seconds since