CS 188: Artificial Intelligence Spring 2007AnnouncementsProperties of quantifiersSome examples of FOL sentencesEqualityUsing FOLInteracting with FOL KBsInference in FOLUniversal instantiation (UI)Existential instantiation (EI)Existential Instantiation continuedReduction to propositional inferenceReduction contd.Slide 20Problems with propositionalizationMethods to speed up inferenceWhat you need to knowKnowledge engineering in FOLKnowledge RepresentationOntology: Origins and HistoryA possible upper ontologyA special purpose ontologyCategories and objectsCategory organizationFOL and categoriesSo whatSemantic WebWhere we are Today: the Syntactic WebImpossible using the Syntactic Web…A Layered WebOntology Working Language (OWL)A Pizza ontologyCurrent StatusSlide 40Buying a book : Actions in FOLNecessary and Sufficient conditionsStructure of conceptsSummaryA (Short) History of AICS 188: Artificial IntelligenceSpring 2007Lecture 10: Logical agents and knowledge representation 2/15/2007Srini Narayanan – ICSI and UC BerkeleyMany slides over the course adapted from Dan Klein, Stuart Russell or Andrew MooreAnnouncementsAssignment 3 up this morningDue 2/21, 11:59 PM, written no codingCovers logical agentsProperties of quantifiersx y is the same as y xx y is the same as y x x y is not the same as y xx y Loves(x,y)“There is a person who loves everyone in the world”y x Loves(x,y)“Everyone in the world is loved by at least one person”Quantifier duality: each can be expressed using the otherx Likes(x,IceCream) x Likes(x,IceCream)x Likes(x,Broccoli) x Likes(x,Broccoli)Some examples of FOL sentencesHow expressive is FOL?Some examples from natural languageEvery gardener likes the sun.x gardener(x) => likes (x, Sun) You can fool some of the people all of the timex (person(x) ^ ( t) (time(t) => can-fool(x,t))) You can fool all of the people some of the time.x (person(x) => ( t) (time(t) ^ can-fool(x,t))) No purple mushroom is poisonous.~ x purple(x) ^ mushroom(x) ^ poisonous(x) or, equivalently, x (mushroom(x) ^ purple(x)) => ~poisonous(x)Equalityterm1 = term2 is true under a given interpretation if and only if term1 and term2 refer to the same objectE.g., definition of Sibling in terms of Parent:x,y Sibling(x,y) [(x = y) m,f (m = f) Parent(m,x) Parent(f,x) Parent(m,y) Parent(f,y)]Using FOLThe kinship domain:Brothers are siblingsx,y Brother(x,y) Sibling(x,y)One's mother is one's female parentm,c Mother(c) = m (Female(m) Parent(m,c))“Sibling” is symmetricx,y Sibling(x,y) Sibling(y,x)Interacting with FOL KBsSuppose a wumpus-world agent is using an FOL KB and perceives a smell and a breeze (but no glitter) at t=5:Tell(KB,Percept([Smell,Breeze,None],5))Ask(KB,a BestAction(a,5))I.e., does the KB entail some best action at t=5?Answer: Yes, {a/Shoot} ← substitution (binding list)Given a sentence S and a substitution σ,Sσ denotes the result of plugging σ into S; e.g.,S = Smarter(x,y)σ = {x/Hillary,y/Bill}Sσ = Smarter(Hillary,Bill)Ask(KB,S) returns some/all Sσ such that KB╞ σInference in FOLUniversal instantiation (UI)Every instantiation of a universally quantified sentence is entailed by it:v αSubst({v/g}, α)for any variable v and ground term gE.g., x King(x) Greedy(x) Evil(x) yields any or all of:King(John) Greedy(John) Evil(John)King(Richard) Greedy(Richard) Evil(Richard)King(Father(John)) Greedy(Father(John)) Evil(Father(John))…Existential instantiation (EI)For any sentence α, variable v, and constant symbol k that does not appear elsewhere in the knowledge base:v αSubst({v/k}, α)E.g., x Crown(x) OnHead(x,John) yields:Crown(C1) OnHead(C1,John)provided C1 is a new constant symbol, called a Skolem constantExistential Instantiation continuedUI can be applied several times to add new sentencesthe new KB is logically equivalent to the oldEI can be applied once to replace the existential sentencethe new KB is not equivalent to the oldbut a sentence is entailed by the old KB iff it is entailed by the new KB.Reduction to propositional inferenceSuppose the KB contains just the following:x King(x) Greedy(x) Evil(x)King(John)Greedy(John)Brother(Richard,John)Instantiating the universal sentence in all possible ways, we have:King(John) Greedy(John) Evil(John)King(Richard) Greedy(Richard) Evil(Richard)King(John)Greedy(John)Brother(Richard,John)The new KB is propositionalized: proposition symbols are King(John), Greedy(John), Evil(John), King(Richard), etc.Reduction contd.Claim: Every FOL KB can be propositionalized so as to preserve entailment(A ground sentence is entailed by new KB iff entailed by original KB)Idea: propositionalize KB and query, apply resolution, return resultProblem: with function symbols, there are infinitely many ground terms,e.g., Father(Father(Father(John)))Reduction contd.Theorem: Herbrand (1930). If a sentence α is entailed by an FOL KB, it is entailed by a finite subset of the propositionalized KBIdea: For n = 0 to ∞ do create a propositional KB by instantiating with depth-n terms see if α is entailed by this KBProblem: works if α is entailed, keeps instantiating and doesn’t terminate if α is not entailedTheorem: Turing (1936), Church (1936) Entailment for FOL is semidecidable (algorithms exist that say yes to every entailed sentence, but no algorithm exists that also says no to every nonentailed sentence.)Problems with propositionalization1. Propositionalization seems to generate lots of irrelevant sentences.E.g., from:x King(x) Greedy(x) Evil(x)King(John)y Greedy(y)Brother(Richard,John)it seems obvious that Evil(John), but propositionalization produces lots of facts such as Greedy(Richard) that are irrelevant1. With p k-ary predicates and n constants, there are p·nk instantiations.-With function symbols, it gets worse!Methods to speed up inferenceUnification Resolution with search heuristics.Backward Chaining/ Prolog ParamodulationThere is a technology of theorem proving.What you need to knowBasic concepts of logicEntailment, validity, satisfiabilityLogical equivalence in propositional logic (rewrite
View Full Document
Unlocking...