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] SS SS 10 001 000 00 000 00 1001 00 000 00 000 00 1001 00 000 00 000 00 100 100 000 100 000 000 100 001 000 001 001 00 100 00 000 00 001 00 000 00 000 00 001 00 000 00 000 01 001 100110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001110001 THE EFFECTIVE DOSAGE VARIES CONSIDERABLY _________________________________________________________________________________________________________ Example of Parsing (Cont'd) * The effective dosage varies considerably. [Hodges, p.78] SS SS 10 00 00 1000 100 1001 000 0001 000 000 001 000 100 000 000 000 000 1000 000 1001 000 11 000 NP VP 1 1 1 0000 0000 000 100 00 000 100 000 100 0000 1001 000 100 1000 001 000 100 000 000 001 001 000 000 1001 001 0001 100 100 00 000 0001100000000000000000000000000000000000000110001 10011000000000000000000000000000000000001110001 THE EFFECTIVE DOSAGE VARIES CONSIDERABLY _________________________________________________________________________________________________________ Example of Parsing (Cont'd) * The effective dosage varies considerably. [Hodges, p.78] S 110 000 001 000 100 1001 000 0001 000 000 001 000 100 000 000 11 001 NP VP 100 0 0 101 00 0 00 001 01 0 0001 00 01 10 1000 00 001 00 000 00 00 00 0001 000 00 01 1000 00 00 1 DET NP V ADV 0 0 0 0 01 00 0 0 0 10 01 0 0 0 00 10 0 0 0 0 00 0 0 0 00 00 0 0 0 01 0 0 0 0 10 00 0 0 0 01 00 0 1 0 01 11100111100001111000001110 the EFFECTIVE DOSAGE varies considerably _________________________________________________________________________________________________________ Example of Parsing (Cont'd) * The effective dosage varies considerably. [Hodges, p.78] S 110 000 001 000 100 1001 000 0001 000 000 001 000 100 000 000 11 001 NP VP 100 0 0 101 00 0 00 001 01 0 0001 00 01 10 1000 00 001 00 000 00 00 00 0001 000 00 01 1000 00 00 1 DET NP V ADV 0 0 0 0 01 00 0 0 0 10 01 0 0 0 00 10 0 0 0 0 00 0 0 0 00 00 0 0 0 01 0 0 0 0 10 00 0 0 0 01 00 0 1 0 01 the ADJ N varies considerably 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 effective dosage _________________________________________________________________________________________________________ Natural Language Understanding - Parsing Meaning depends on parsing: -------- ------------- ------------- John saw the boy in the park with a telescope S 0 0 11 0 01 0 00 00 00 101 00 00 100 00 00 00 00 001 00 00 00 0 NP VP 0 0 0 0 1001 0 00 0 1000001 0 001 0 000000 0 00 0 1000001 0 00 0 000000 0 00 0 000000 0 100 0 1000001 0 00 0 0000001 0 0 0 1000000 John saw NP PP 00 0 10 00 01 000 00 0 000 00 00 01 1000 101 00 100 01 1000 00 0 00 01 0001 01 00 00 01 000 00 00 001 01 000 0 10 10 01 000 00 00 00 10 00 DET N 00 0 000000000000000000000000001 PP 0 0 00 with a telescope 0 01 00 00 0 01 00 0 0 01 00 00 0 01 00 00 0 01 00 10 0 01 01 00 0 01 00 00 0 01 0 01 0 0 100000000000000000000000000 the boy in the park John saw the boy in the park with a dog S 00 0 10 0 00 00 00 101 001 00 00 00 00 00 00 001 100 00 00 00 NP VP 10 10 10 0 10 00 0 10 00 0 10 00 0 10 100 0 10 00 0 10 00 0 10 101 0 10 00 0 John saw NP 001 0 1000000 00 0 000100001 00 0 100 100000 00 0 000 1000001 101 0 000 100000 00 0 000 000001 00 0 000 100000 001 0 1000 000000 00 0 0000 1000001 0 10 0000 DET N PP PP 11 0 000 0 01 00 0 00 00 00 00 00 0 00 00 0 0 00 0 100 0 00 00 00 0 00 00 10 10 00 0 100 00 00 01 00 0 00 0 00 00 00 0 01 00 00 10 00 0 00 0 00 00 11 0 0000000000000000000000000000 10100000000000000000000000010 the boy in the park with a dog John saw the boy in the park with a statue S 1001 10 0 00 101 00 00 101 00 00 00 00 001 00 00 100 00 00 100 00 00 000 00 0 1 NP VP 10 0 00 0 0 00 01 0 00 0 0 00 0 0 100 0 0 00 0 0 00 0 0 00 0 0 00 0 0 00 0 10 00 0 01 John saw NP 1 00 0 1000 00 0 1000 00 0 0000 101 0 0000 00 0 0001 00 0 0001 101 0 000 00 0 000 00 0 000 00 0 1000 00 0 0000 0 000 DET N PP 0 0 0000 0 0 100 00 0 0 00 00 0 0 00 00 0 0 00 10 0 0 00 00 0 0 00 00 0 0 00 00 0 0 00 00 0 0 01 00 0 0 00 10 0 0 000100000000000000000000000000001000 0 the boy in the park 01 00 00 101 00 00 00 001 00 00 001 001 00 00 00 00 00 00 01 00 00 100 10 00000000000000000000000000000000000 with a statue -------- ------------- ------------- _________________________________________________________________________________________________________ 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) S 01101000 0000 00001 10001 10001 0001 000 NP VP 1 01 0 0 001 00 0 0 001 00 0 0 000 101 0 01 100 100 0 10 00 00 111111111111 01 1 THE MAN V ADJP 00 0000 0 0 00 0 0000 0 0 00 0 0000 0 0 0 0 0001 0 0 00 0 0001 011111111 00 00 0 0001 MUST BE ADJ CON ADJP 0 0 00 0 0 011 00 0 0 00 0 100 0 0 10 0 00 0 0 01 0 00 0 0 00 0 001 0 1 1 1 rich or ADJ CON ADJ 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 young and good-looking _________________________________________________________________________________________________________ Parse the Following Sentence (Cont'd) S 110 001 0000 10001 0000 0000 0000 10001 1001 1000 NP VP 1 1 01 01 000 00 10 10 000 00 10 0 100 001 10 0 001 100 10 0 000 00 10 01 000 00 011111111111101 100 00 THE MAN V ADJP 00 00001 0 0 00 0 000 0 0 01 0 10001 0 0 00 0 1000 0 0 00 01 1000 0 0 10 00 1000 00110001111110 01 11 1000 MUST BE ADJP CON ADJ 0 0 0101 0 0 00 0 100 0 0 00 0 00 0 0 101 0 001 0 0 01 0 100 0 0 00 0 00 0 0 0 0 1 0 0 1 1 1 0 0 ADJ CON ADJ and good-looking 0 0 0 11 0 0 11 0 0 11 0 0 11 0 0 11 0 0 11 0 0 00 0 rich or young _________________________________________________________________________________________________________ Semantics Tarzan kissed Jane 1. Parsing S 1 100000 000001 00000000 100000001 100000001 100000001 00000001 000000001 10000001 10000001 NP VP 1 00 100 0 10 00 0 00 001 0 00 000 0 01 100 0 00 00 0 10 00 0 00 001 1 00 000 N V NP 0 0 0 10 0 0 10 0 0 10 0 0 10 0 0 10 0 0 10 0 0 10 0 0 10 0 0 10 Tarzan kissed N 0 0 0 0 0 0 0 0 0 Jane _________________________________________________________________________________________________________ Semantics (Cont'd) Tarzan kissed Jane 2. Semantic Interpretation 1111111111111111111111111111111111111111111111111111 11111111111111111111111111111111111111111111111 1 0 0 1 1 PERSON: TARZAN 0 0 PERSON: JANE 1 1 0 0 0 0111111111111111111111111000011111111111111111111100 11111111111111111111111111101111111111111111111 0 0 0 0 0 0 0 0 0 0 0 0 11 011111 11 0 1111 111111 111111 111111 11111 11 11 0111111111111111110 11 111 1 1 1 1 1 1 0 AGENT 000000000000010 KISS 01000000000000000 OBJECT 0 0 0 1 1 0 0 1 11 00011111 1111111111 11 11 101 101 0 10 11 11111111111111111 0 11111111111111111 0 0 0 0 111 0 11111111111 11111111111 1111 1111 1111111111111111111 11 1 11 0 1 1 INSTRUMENT 100000000000010 LIPS 1 11 11 0 1 11 11 0000010010011111000 1 1 11111111 11111111 11 11111111 _________________________________________________________________________________________________________ Semantics (Cont'd) 3. Contextual/world knowledge interpretation 1111111111 111111111 1111 1111 100000000000000000000000000000000000000000000000001 1 1 0 0 0 POSSESS 00000000000000010 PET: CHEETAH 0 11 11 0 0 1111 1111 100000011111111111000111111111111111111111111000000 11111111111111111111111 0 10000000000000000000010 0 0 111111 0 1111111111111111111111111 111111 111111 0 1111 1111 1101110000000000011 11 11 0 111 1 0 0 1 1 0 0000 EXPERIENCER 000000000010 LOVE 01000000000000 OBJECT 0 0 101 01 0 1 0 0 1 1 0 1 1 0111111111111111110 11 11 0 111111111111111111111111 111 111 0 1 11111011111111 0 0 0 01000 0 0 0 0 0 0 0 0 1 1 0 11101000000000000010010000111111000000000000000001 111111111111111111111111101111111111111111111 0 0 0 0 0 PERSON: TARZAN 0 0 PERSON: JANE 0 0 0 0 0 010111111111111111111100000011111111111111111110001 111011111111111111111111110111111111111111111 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1111111111111 11111101111111 0 0 1111 111 111111111111111111 1111 1111 0 0 11 11 01 11 11 11 0 0 0 1 1 1 1 1 0 0 0 AGENT 01000000000010 KISS 0100000000000010 OBJECT 0 0 0 1 0 111 11 1 1 0 0 11 111 111111 0 1111111 11 11 0 0 11111 11111 0 111111 111111 0 0 11111111 0 11111111 0 0 0 0 0 0 0 0 0 0 0 0 0 0 111111111111111111111111111 0 0 1111 1111 11111111111111111 0 000000000000000001 11 1 01 01 0 1 0 INSTRUMENT 00000000000010 LISPS 0 0 0 11 11 01 10 0 0 1 11 11 1 011111110011 11000 0 0 11111111111111111111111 0 0 0 0 000000000000001 1 0 11111101111111 0 1111111 1111111 1111111110111111111111 111 111 1000000000000000000001 1111 11111 0 1 1 0 11 11 0 LOCATION 100000000010 JUNGLE 01000000001 LOCATION 1 111 111 1 0 11 11 111111 111111 1000111111100111111111 111 111 111111111111 11111111 11111 11111111 _________________________________________________________________________________________________________ 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. 11111111111111111111 COLOUR 11111111111111111111 10001 1000 10001 10001 00 100 111111 001 00 0 0 0 0 0 01 0 ELEPHANT 011111111111111111 0 01111111111111010 GREY 0 0 ELEPHANT 1 0 0 0 1 0 GREY 0 0 10 0 0 01 0 100 001 11 0 11 100 001 00001 10001 0 00001 11000 1100000011110000001 1 1000000110100001011 0 1 0 1 0 1 0 1 0 1 1 11 0 0 1 0 1 0 1 0 1 0 1 CANCEL 0 INSTANCE 1 1 11 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 100000 0001000001 1 1 11 000001 100000 100000010001000100 100 000 1 100001 10000 01 01 011101111 001 000 0 CLYDE 0 0 1 00 0 0 CLYDE 10000000000000000010 01000000000000000011 WHITE 0 0 0 0 1 0 WHITE 0 10 00 010000010 0 11 1000 0001 001 001 1000000111 1110000001 10001 1000 1 COLOUR 111111111111111111111 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. 000 000 1 000 GREY 11000 GREY 1001 000 01 0 01 10 00 1 01 0 01 1 00 0 0 1 0 0 0 0 1 0 000 1 00 0 10001 ELEPHANT 0000000000 0000 ELEPHANT 1000000000 1 1 1 0 0 0 0 11 111 0 111 0 10 1101001 0 0 0 010110 10 1 10 0 101011 10 1 00 0 10001 100 001 010 00 000 011000 ROYAL ELEPHANT 0 000 ROYAL ELEPHANT 000 0 100 10 00 10101 0 1 00101 0 1 1010101 0 1 100111 0010101 000 001 111 11 0001 CIRCUS ELEPHANT 0000 1 1 CIRCUS ELEPHANT 0 0 111 10 0 1 0 1 10 10 0000 CLYDE 0000 CLYDE 001 00 (A) (B) The net can be read: * Typically elephants are grey. * Clyde is an elephant. * Clyde is white. What should be derivable? _________________________________________________________________________________________________________ Multiple Inheritance Nixon Diamond PACIFIST 100001 000000 0000 0 0 000 000 01 000 00 00 00 101 1 00 00 00 10 00 00 0 000 0 000 0 00 10 01 00 00 01 00 00 00 00 00 0 1 0000 1001 000000 REPUBLICAN QUAKER 000000 00000 100000 1 11 0 00 000 000 100 1 0 10 01 00 00 00 00 00 10 00 00 00 00 01 00 0 01 0 00 10 00 00 10 0 0000 000000 00001 NIXON 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 22.12.2004 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/