New version page

Berkeley COMPSCI 188 - Logical agents and knowledge representation

Documents in this Course
CSP

CSP

42 pages

Metrics

Metrics

4 pages

HMMs II

HMMs II

19 pages

NLP

NLP

23 pages

Midterm

Midterm

9 pages

Agents

Agents

8 pages

Lecture 4

Lecture 4

53 pages

CSPs

CSPs

16 pages

Midterm

Midterm

6 pages

MDPs

MDPs

20 pages

mdps

mdps

2 pages

Games II

Games II

18 pages

Load more
Upgrade to remove ads

This preview shows page 1-2-3-18-19-37-38-39 out of 39 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

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 MooreAnnouncementsAssignment 3 up this morningDue 2/21, 11:59 PM, written no codingCovers logical agentsProperties of quantifiersx y is the same as y xx y is the same as y x x y is not the same as y xx 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 otherx Likes(x,IceCream) x Likes(x,IceCream)x Likes(x,Broccoli) x Likes(x,Broccoli)Some examples of FOL sentencesHow expressive is FOL?Some examples from natural languageEvery gardener likes the sun.x gardener(x) => likes (x, Sun) You can fool some of the people all of the timex (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)Equalityterm1 = term2 is true under a given interpretation if and only if term1 and term2 refer to the same objectE.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 siblingsx,y Brother(x,y)  Sibling(x,y)One's mother is one's female parentm,c Mother(c) = m  (Female(m)  Parent(m,c))“Sibling” is symmetricx,y Sibling(x,y)  Sibling(y,x)Interacting with FOL KBsSuppose 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 gE.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 continuedUI can be applied several times to add new sentencesthe new KB is logically equivalent to the oldEI can be applied once to replace the existential sentencethe new KB is not equivalent to the oldbut 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 resultProblem: 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 inferenceUnification Resolution with search heuristics.Backward Chaining/ Prolog ParamodulationThere is a technology of theorem proving.What you need to knowBasic concepts of logicEntailment, validity, satisfiabilityLogical equivalence in propositional logic (rewrite


View Full Document
Download Logical agents and knowledge representation
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 Logical agents and knowledge representation 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 Logical agents and knowledge representation 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?