Introduction to AI - Week 7 Knowledge Representation II * Natural Language + Syntax and Parsing + Semantics + Pragmatics * Logic + Translation NL to Logic * Semantic Nets and Defaults + Multiple Inheritance + Non-monotonic Reasoning _________________________________________________________________________________________________________ Natural Language Understanding - Parsing Sentences are parsed according to rules, which form a grammar. A simple subset of English grammar is: 1. S-> NP VP (A sentence is a noun phrase followed by a verb phrase.) 2. NP-> N (A noun phrase is a noun.) 3. NP-> DET N (A noun phrase is a determiner (article) followed by a noun.) 4. VP-> V (A verb phrase is a verb.) 5. VP-> V NP (A verb phrase is a verb followed by a noun phrase.) 6. PP-> PROP NP (A propositional phrase is a proposition followed by a noun phrase.) _________________________________________________________________________________________________________ Lexicon In addition to the grammatical rules, we need a lexicon which contains the terminal symbols for our grammar. A small subset is: 1. DET-> a ("a" is a determiner.) 2. DET-> the ("the" is a determiner.) 3. N-> man ("man" is a noun.) 4. N-> woman ("woman" is a noun.) 5. V-> saw ("saw" is a verb.) _________________________________________________________________________________________________________ Example of Parsing * The effective dosage varies considerably. [Hodges, p.78] [exparse1.jpg] _________________________________________________________________________________________________________ Example of Parsing (Cont'd) * The effective dosage varies considerably. [Hodges, p.78] [exparse2.jpg] _________________________________________________________________________________________________________ Example of Parsing (Cont'd) * The effective dosage varies considerably. [Hodges, p.78] [exparse3.jpg] _________________________________________________________________________________________________________ Example of Parsing (Cont'd) * The effective dosage varies considerably. [Hodges, p.78] [exparse4.jpg] _________________________________________________________________________________________________________ Natural Language Understanding - Parsing Meaning depends on parsing: -------- ------------- ------------- John saw the boy in the park with a telescope [parsing1.jpg] John saw the boy in the park with a dog [parsing2.jpg] John saw the boy in the park with a statue [parsing3.jpg] -------- ------------- ------------- _________________________________________________________________________________________________________ Parse the Following Sentence * The man must be rich or young and good-looking. [Hodges, p.78] Find two reading and focus on the main difference. _________________________________________________________________________________________________________ Parse the Following Sentence (Cont'd) [exparse5.jpg] _________________________________________________________________________________________________________ Parse the Following Sentence (Cont'd) [exparse6.jpg] _________________________________________________________________________________________________________ Semantics Tarzan kissed Jane 1. Parsing [tarzan1.jpg] _________________________________________________________________________________________________________ Semantics (Cont'd) Tarzan kissed Jane 2. Semantic Interpretation [tarzan2.jpg] _________________________________________________________________________________________________________ Semantics (Cont'd) 3. Contextual/world knowledge interpretation [tarzan3.jpg] _________________________________________________________________________________________________________ Semantics (Cont'd) The semantic analysis of a piece of text is essential for a good performance with various tasks such as: * Understanding * Question answering * Summarisation * Translation to other languages _________________________________________________________________________________________________________ Pragmatics Pragmatics is the study of ways in which language is used and its effects on the listener. Assume a system that should automatically perform hotel bookings. * Costumer: Is the double room for £ 22 available on 9 November? * Computer: No. The answer "No" is syntactically and (let's assume so) semantically correct, but does not fulfil the intention the computer should have, namely to sell. A better answer would be * Computer: No, but I can offer you our suite, which is normally £ 50 for only £ 25 on 9 November. It's a real treat and unbeatably competitive. _________________________________________________________________________________________________________ Natural Language Understanding Syntax, Semantics, Pragmatics Distinguish: * Syntactic analysis: "Boy the go the to store." rejected as syntactically incorrect. * Semantic analysis: "Colourless green ideas sleep furiously." rejected as semantically anomalous. * Pragmatic analysis: "Do you know the time?", answer: "Yes, I do." pragmatically incorrect, since it disregards the intension of the request. _________________________________________________________________________________________________________ Knowledge Representation in First-Order Logic Examples: (a) man(Pat) (d) man(Jan) | woman(Jan) (b) married(Pat,Jan) (e) FORALL x. EXISTS y. [person(x) -> has_mother(x,y)] (c) FORALL x. FORALL y. [[married(x,y) & man(x)] -> ~ man(y)] Read: logic | & -> ~ FORALL EXISTS -------- ------------- ------------- nat. lang. or and implies not forall exists Properties of First-Order Logic: * very expressive as well as unambiguous syntax and semantics * no generally efficient procedure for processing knowledge Correct: raining raining -> street_wet -------- ------------- ------------- street_wet Incorrect: raining raining -> street_wet -------- ------------- ------------- elephant_hungry _________________________________________________________________________________________________________ How to translate? * Sam is a tall man. man(sam) & tall(sam) * Every human is mortal. FORALL x. human(x) -> mortal(x) * Some girl is happy. EXISTS x. girl(x) & happy(x) Larger sentences are parsed and decomposed into smaller parts which can be translated piecewise. _________________________________________________________________________________________________________ Encode If the Millennium Dome is at least as high as the Royal Albert Hall, then every concert hall which is at least as high as the Millennium Dome is at least as high as the Royal Albert Hall. Higher(Millenium-Dome,Royal-Albert-Hall) -> (FORALL x. ( (Concert-Hall(x) & Higher(x,Millenium-Dome)) -> Higher(x,Royal-Albert-Hall))) _________________________________________________________________________________________________________ Examples Translate to first-order logic: * If Sam loves everybody then Sam loves himself. (FORALL x. Loves(sam,x)) -> Loves(sam,sam) * If God was not created by anything then it is false that God created everything. (~EXISTS x. Created(x, god)) -> (~FORALL y. Created( god,y)) * If only doctors or hospital administrators are eligible and Mrs Miller is eligible then Mrs Miller is a doctor or a hospital administrator. ( (FORALL x. Eligible(x) -> Doc(x) | Admin(x))) & Eligible( MrsMiller)) -> ( Doctor( MrsMiller) | Admin( MrsMiller)) _________________________________________________________________________________________________________ Example (Cont'd) Translate to first-order logic: * You may fool all the people some of the time; you can even fool some of the people all the time; but you can't fool all of the people all the time. [Abraham Lincoln] Use P(x) standing for "x is a person", T(y) for "y is a moment of time", and Fool(x,y) for "x can be fooled at y." (EXISTS y. T(y) & (FORALL x. P(x) -> Fool(x,y))) & (EXISTS x. P(x) & (FORALL y. T(y) -> Fool(x,y))) & (~(FORALL x. P(x) -> (FORALL y. T(y) -> Fool(x,y)))) _________________________________________________________________________________________________________ Example (Cont'd) Note there is an ambiguity in the sentence: You may fool all the people some of the time. There are two possible ways to interpret it: * There are times when you may fool all the people. EXISTS y. T(y) & (FORALL x. P(x) -> Fool(x,y)) * You may fool any person some of the time. FORALL x. P(x) -> (EXISTS y. T(y) & Fool(x,y)) _________________________________________________________________________________________________________ Problem How to formalise Mickey is a big mouse? mouse(mickey) & big(mickey) How to formalise Jumbo is a little elephant? elephant(jumbo) & little(jumbo) BUT: A big mouse is smaller than a little elephant. More sophisticated representation necessary. _________________________________________________________________________________________________________ Default Values * Thinking always begins with suggestive but imperfect plans and images; these are progressively replaced by better - but usually still imperfect - ideas. (Minsky) Use default value when no concrete information is available default value = typical value (not average value) Examples: * Typically birds can fly. * Typically humans have two legs. * The typical height of an adult male is 180cm. * The typical maximal temperature of a November day is 12^ oC. _________________________________________________________________________________________________________ Defaults Slots can be overridden, hence they can be taken to represent properties that follow only typically. [default.jpg] The net above can be read: * Typically elephants are grey. * Clyde is an elephant. * Clyde is white. I.e., Clyde is an exception with respect to colour, but inherits the other properties of elephants. _________________________________________________________________________________________________________ Defaults (Cont'd) Slots can be overridden, hence they can be taken to represent properties that follow typically only. [inheritance1.jpg] The net can be read: * Typically elephants are grey. * Clyde is an elephant. * Clyde is white. What should be derivable? _________________________________________________________________________________________________________ Multiple Inheritance Nixon Diamond [nixon.jpg] Assume knowledge: * Nixon is a Quaker. * Quakers are typically pacifists. * Nixon is a Republican. * Republicans are typically not pacifists. What to conclude? * "Nixon is a pacifist." or * "Nixon is not a pacifist."? _________________________________________________________________________________________________________ Non-monotonic Reasoning In the light of default values a fundamental property of standard logic does not hold any more, monotonicity. Monotonicity means: If a statement A can be concluded from a set of facts set, then A can also be concluded from any larger set which contains set as a subset. (Formally: set |= A then set union set' |= A.) This is no longer the case for defaults. _________________________________________________________________________________________________________ Non-monotonic Reasoning (Cont'd) Assume knowledge: FORALL x. Bird(x) -> Can_Fly(x) Bird(Tweety) -------- ------------- ------------- Can_Fly(Tweety) This is not correct, however. If we learn in addition that Tweety is a penguin, we don't want to conclude any longer that Tweety can fly. Thus FORALL x. Bird(x) unless abnormal Bird(x) -> Can_Fly(x) Bird(Tweety) -------- ------------- ------------- Can_Fly(Tweety) is a better form of reasoning (default reasoning). We would also have FORALL x. Penguin(x) -> abnormal Bird(x) With the additional knowledge Penguin(Tweety) it is not possible to derive Can_Fly(Tweety) any more. _________________________________________________________________________________________________________ Non-monotonic Reasoning (Cont'd) FORALL x. P(x) unless abnormal P(x) -> Q(x) P(c) abnormal P(c) cannot be derived -------- ------------- ------------- Q(c) Question: How to derive that P(c) is not abnormal. Use negation as failure as in Prolog, that is, in the example, if it is not possible to derive that Tweety is a penguin, then assume that it is not a penguin, then assume that Tweety is a "normal" bird, then conclude that Tweety can fly. _________________________________________________________________________________________________________ Example Represent: "A good student of whom nothing is known to the contrary will study hard. A party person of whom nothing else is known to the contrary will not study hard. A good student who studies hard will graduate. David is a good student." What follows? What follows, when we learn in addition: "David is a party person." How to formalise? _________________________________________________________________________________________________________ Formalisation FORALL x. good_student(x) & unless abnormal study_hard(x) -> graduates(x) FORALL y. party_person(y) & unless abnormal not study_hard(x) -> not graduates(x) good_student(david) party_person(david) _________________________________________________________________________________________________________ Summary * Natural Language: + Very powerful representation formalism. + Ambiguity in representation. + Difficult to parse. + Difficult to find semantics. + Pragmatics important in application. * Logic: + Clear syntax and semantics. + Easy to parse. + Restricted expressive power (e.g., no defaults). + No account of pragmatics. _________________________________________________________________________________________________________ Summary (Cont'd) * Semantic Nets/Defaults: + Structured Representation. + Semantic status may be unclear. + Efficient reasoning possible (depending on exact format). + Default values and non-monotonic reasoning. There is no single best knowledge representation formalism. _________________________________________________________________________________________________________ _________________________________________________________________________________________________________ © Manfred Kerber, 2004, Introduction to AI 24.4.2005 The URL of this page is http://www.cs.bham.ac.uk/~mmk/Teaching/AI/Teaching/AI/l7.html. URL of module [1]http://www.cs.bham.ac.uk/~mmk/Teaching/AI/ References 1. http://www.cs.bham.ac.uk/~mmk/Teaching/AI/