Intro to Artificial IntelligenceCOMP 307 #24 11 Oct 2007: Intro to Artificial Intelligence COMP 307 #24 11 Oct 2007


Menu: Menu Syntax DCG grammar rules Administrivia A4 due next Monday 10am, worth 5% Tutorial: this Friday 12-1 MY102


Representing Syntactic Knowledge: Representing Syntactic Knowledge Syntactic knowledge: Syntactic Categories: e.g. Noun, Sentence. Grammatical features: e.g. Singular, Plural Grammar rules. Why bother?


Parts of language: Parts of language Regard sentences as being built out of constituents Two types of constituents: words (simple constituents), which have lexical categories like noun, verb, etc. phrases (compound constituents), like noun phrases, verb phrases, etc. How to store syntactic knowledge? lexicon grammar rules


Words: Lexical Categories (Parts of Speech): Words: Lexical Categories (Parts of Speech) Noun (N): Jack, tree, house, cannon Verb (V): build, walk, kill Adjective (Adj): big, red, unpleasant Determiner (Det): the, a, which, that Jack built {the, a, that} big, red house; Which house did Jack build? Preposition (Prep): with, for, in, from, to, through, via, under


Words: Lexical Categories (ctd): Words: Lexical Categories (ctd) Pronoun (Pro): her, him, she, itself, that, it I saw the man in the park with the telescope Don't do that to him Conjunction (Conj): and, or, but. Two kinds of lexical categories: 1. Open categories (“content words”): N, V, Adj 2. Closed categories (“function words”): Det, Prep, Pro, Conj


Compound Constituents: Compound Constituents Sentence (S): Jack built the house. Noun Phrase (NP): John; the big, red house; the house that Jack built; the destruction of the city. Verb Phrase (VP): built the house quickly; saw the man in the park. Prepositional Phrase (PP): with the telescope; on the table


A Simple Grammar: A Simple Grammar S  NP VP VP  V NP NP  Proper_N NP  det N Proper_N  John Proper_N  Mary N  cake V  loves V  ate det  the Sentences in this language: “John loves Mary” “John ate the cake” “John loves the cake”


Definite Clause Grammars (DCGs): Definite Clause Grammars (DCGs) The above grammar can be simply implemented in DCG notation as follows: s --> np, vp. vp --> v, np. np --> proper_n. np --> det, n. proper_n --> [john]. proper_n --> [mary]. n --> [cake]. v --> [loves]. v --> [ate]. det --> [the].


Grammatical vs Ungrammatical sentences: Grammatical vs Ungrammatical sentences ungrammatical (syntactically incorrect) sentences The John eats the hamburger. John eat the hamburger. John died Mary. A hostages ate the hamburgers. Him ate him. syntactically correct sentences: John eats the hamburger. The people eat the hamburgers. Hostages eat hamburgers. Hamburgers killed John. Cholesterol killed John.


Some Grammatical Features.: Some Grammatical Features. We can use the idea of grammatical features to solve this problem: Number: singular, plural: hamburger, hamburgers Person: 1st, 2nd, or 3rd: eat, eats Proper noun: true or false: John, hamburger Mass noun: true (bread) or false (bun): compare “a bread” & “a bun” Transitivity: transitive or intransitive: give, die Case: subjective (I, he, she, they), objective (me, him, her, them)


Modifying a DCG to handle case: Modifying a DCG to handle case s --> np_sub, vp. vp --> v, np_obj. vp --> v. pp --> prep, np_obj. np_obj -> pro_obj. np_obj –> det, n. np_sub -> pro_sub. np_sub –> det, n. pro_sub --> [i]. pro_sub --> [you]. pro_sub --> [he]. pro_sub --> [she]. pro_obj --> [me]. pro_obj --> [you]. pro_obj --> [him]. pro_obj --> [her]. Examples He saw her. She saw him. You gave it to me. I gave them to you. They gave it to them. They gave them it.


Augmenting a DCG to handle case: Augmenting a DCG to handle case There are other grammatical features we need to match, and if we keep making more specialized grammar rules, we will end up with exponential number of rules. Alternative is to augment grammar. s --> np(sub), vp. vp --> v, np(obj). vp --> v. pp --> prep, np(obj). np(Case) -> pro(Case). np(_) --> det, n. pro(Case) -> [Pro],{pro(Pro,Case)}. % Lexical entries: pro(i, sub). pro(you, sub). pro(he, sub). pro(she, sub). pro(me, obj). pro(you, obj). pro(him, obj). pro(her, obj).


Subject-verb agreement: Subject-verb agreement In English, number and person of the subject must agree with the verb: “I am” / “she is” / “they are” Person Number Pronoun Verb examples… –––––––––––––––––––––––––––––––––––––––––– 1st sing I eat am have 2nd – you eat are have 3rd sing he/she/it eats is has 1st plur we eat are have 3rd plur they eat are have


Implementing subject-verb agreement: Implementing subject-verb agreement Can combine checking subject-verb agreement in person/number with case checking: % subject must agree with verb s --> np(Per, Num, sub), vp(Per, Num). % person and number of object doesn’t matter vp(Per, Num) --> v(Per, Num), np(_, _, obj). vp(Per, Num) --> v(Per, Num). % look up V, retrieve its person and number v(Per, Num) --> [V], {v(V, Per, Num)}. % person, number and case comes from pronoun np(Per, Num, Case) --> pro(Per, Num, Case).


Implementing subject-verb agreement: Implementing subject-verb agreement % look up person, number and case of pronoun pro(Per, Num, Case) --> [Pro], {pro(Pro, Per, Num, Case)}. % lexical entries pro(she, second, sing, obj). v(eats, third, sing).


Agreement for nouns & determiners: Agreement for nouns & determiners Articles (a type of determiner) have restrictions based on number and whether the noun is mass or count Article Number Def/Indef Example ––––––––––––––––––––––––––––––––––––– a/an singular indefinite a man saw …  plural indefinite men saw… the singular definite the man saw … the plural definite the men saw… Mass nouns (bread, money, water) take no article when used in the indefinite, and go with a verb in the singular


Determiners: Determiners Determiners can be quite complicated: can involve numbers (& many other things) Definite Indefinite ––––––––––––––––––––––––––– the dog a dog the red dogs blue dogs the three dogs three dogs my uncle Bob’s friend’s dog every dog every pink large dog all but three of the red dogs Proper nouns take no determiners


Noun/determiner agreement: Noun/determiner agreement Mass nouns Count nouns –––––––––––––––––––––––––––––––––––– the bread tastes good. the loaf tastes good. *a bread taste good. (don’t use indef article with mass nouns) bread tastes good. a loaf tastes good. *bread taste good loaves taste good. (mass nouns go with sing. verb) the money is heavy. the coins are heavy. the coin is heavy. money buys power. a coin buys … coins buy icecreams *the three bread … the three loaves cost $4 *three bread … three loaves cost $4 (can’t use numbers with mass nouns)


DCG rules for noun/determiner agreement: DCG rules for noun/determiner agreement % Proper nouns are noun-phrases np(Number, _Person, _Case) --> proper_n(Number, _). % Mass nouns need no determiners np(sing, _Person, _Case) --> n1(N, sing, mass). % Determiner-Noun (can’t have indef % determiner + mass noun) np(Number, _, _) --> det(Number, Definite), n1(Number, Mass), {\+ (Mass=mass, Definite=indef)}. n1(Number, Mass) --> adj, n1(Number, Mass). n1(Number, Mass) --> n(Number, Mass).


DCG rules for noun/ determiner agreement (ctd): DCG rules for noun/ determiner agreement (ctd) n(Number, Mass) --> [N], {noun(N, Number, Mass)}. proper_n(Number, Mass) --> [N],{proper_noun(N, Number, Mass)}. det(Number, Definite) --> [], {det([], Number, Definite)}. det(Number, Definite) --> [Det], {det(Det, Number, Definite)}. proper_noun(john, sing, count). noun(loaf, sing, count). noun(loaves, plur, count). noun(bread, sing, mass). det(a, sing, indef). det([], plur, indef). det(the, _, def).