0 Grammar Communication Outline COMMUNICATION AND LANGUAG change the actions of other agents Communication Communication
Communication and Language Chapter 22 Chapter 22 1 Outline ♦ Communication ♦ Grammar ♦ Syntactic analysis ♦ Problems Chapter 22 2 Communication “Classical” view (pre-1953): language consists of sentences that are true/false (cf. logic) “Modern” view (post-1953): language is a form of action Wittgenstein (1953) Philosophical Investigations Austin (1962) How to Do Things with Words Searle (1969) Speech Acts Why? Chapter 22 3 Communication “Classical” view (pre-1953): language consists of sentences that are true/false (cf. logic) “Modern” view (post-1953): language is a form of action Wittgenstein (1953) Philosophical Investigations Austin (1962) How to Do Things with Words Searle (1969) Speech Acts Why? Chapter 22 4 Communication “Classical” view (pre-1953): language consists of sentences that are true/false (cf. logic) “Modern” view (post-1953): language is a form of action Wittgenstein (1953) Philosophical Investigations Austin (1962) How to Do Things with Words Searle (1969) Speech Acts Why? Chapter 22 5 Communication “Classical” view (pre-1953): language consists of sentences that are true/false (cf. logic) “Modern” view (post-1953): language is a form of action Wittgenstein (1953) Philosophical Investigations Austin (1962) How to Do Things with Words Searle (1969) Speech Acts T Why? o change the actions of other agents Chapter 22 6
How coul this go wrong? 1 SITUATION H incorporates P into KB Stages in communication (informing) Stages in communication (informing) Speech acts ↓ Hear : Context-i Contet-oe pus pit stench breese Wumpus lexicon Grammar types The gammar isa set of rewrite rules,e. A formal language is aset of strings of terminal symbols nicable prop Grammar Boston UCB|PAJCI east south back . nearby ahe left east south|back|smelly , el shoot feel ati pits gold east glitter nothing nalson right-hand sid Here S is the sentence symbol,NP and VP are nonterminal Each string in the language can be/generated by the gramm
Speech acts SITUATION Speaker Utterance Hearer Speech acts achieve the speaker’s goals: Inform “There’s a pit in front of you” Query “Can you see the gold?” Command “Pick it up” Promise “I’ll share the gold with you” Acknowledge “OK” Speech act planning requires knowledge of – Situation – Semantic and syntactic conventions – Hearer’s goals, knowledge base, and rationality Chapter 22 7 Stages in communication (informing) Intention S wants to inform H that P Generation S selects words W to express P in context C Synthesis S utters words W Perception H perceives W0 in context C 0 Analysis H infers possible meanings P1, . . . Pn Disambiguation H infers intended meaning Pi Incorporation H incorporates Pi into KB How could this go wrong? Chapter 22 8 Stages in communication (informing) Intention S wants to inform H that P Generation S selects words W to express P in context C Synthesis S utters words W Perception H perceives W0 in context C 0 Analysis H infers possible meanings P1, . . . Pn Disambiguation H infers intended meaning Pi Incorporation H incorporates Pi into KB How could this go wrong? – Insincerity (S doesn’t believe P) – Speech wreck ignition failure – Ambiguous utterance – Differing understanding of current context (C 6= C 0 ) Chapter 22 9 Grammar Vervet monkeys, antelopes etc. use isolated symbols for sentences ⇒ restricted set of communicable propositions, no generative capacity (Chomsky (1957): Syntactic Structures) Grammar specifies the compositional structure of complex messages e.g., speech (linear), text (linear), music (two-dimensional) A formal language is a set of strings of terminal symbols Each string in the language can be analyzed/generated by the grammar The grammar is a set of rewrite rules, e.g., S → NP VP Article → the | a | an | . . . Here S is the sentence symbol, NP and VP are nonterminals Chapter 22 10 Grammar types Regular: nonterminal → terminal[nonterminal] S → aS S → Λ Context-free: nonterminal → anything S → aSb Context-sensitive: more nonterminals on right-hand side ASB → AAaBB Recursively enumerable: no constraints Related to Post systems and Kleene systems of rewrite rules Natural languages probably context-free, parsable in real time! Chapter 22 11 Wumpus lexicon Noun → stench | breeze | glitter | nothing | wumpus | pit | pits | gold | east | . . . Verb → is | see | smell | shoot | feel | stinks | go | grab | carry | kill | turn | . . . Adjective → right | left | east | south | back | smelly | . . . Adverb → here | there | nearby | ahead | right | left | east | south | back | . . . Pronoun → me | you | I | it | . . . Name → John | Mary | Boston | UCB | P AJC | . . . Article → the | a | an | . . . Preposition → to | in | on | near | . . . Conjunction → and | or | but | . . . Digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Divided into closed and open classes Chapter 22 12
Adjusting to agree learing problem Divided into dsed and oper 育 Grammaticality judgements the al an hn|Mary|Boston UCB PAJCI.. I youl it S/HE Y'ALL. Wumpus lexicon Parse trees ot the grammatcal structure of a senteno Parse trees Exhibit the grammatical sructure of a sentence Parse trees
Wumpus lexicon Noun → stench | breeze | glitter | nothing | wumpus | pit | pits | gold | east | . . . Verb → is | see | smell | shoot | feel | stinks | go | grab | carry | kill | turn | . . . Adjective → right | left | east | south | back | smelly | . . . Adverb → here | there | nearby | ahead | right | left | east | south | back | . . . Pronoun → me | you | I | it | S/HE | Y ALL 0 . . . Name → John | Mary | Boston | UCB | P AJC | . . . Article → the | a | an | . . . Preposition → to | in | on | near | . . . Conjunction → and | or | but | . . . Digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Divided into closed and open classes Chapter 22 13 Wumpus grammar S → NP VP I + feel a breeze | S Conjunction S I feel a breeze + and + I smell a wumpus NP → Pronoun I | Noun pits | Article Noun the + wumpus | Digit Digit 3 4 | NP PP the wumpus + to the east | NP RelClause the wumpus + that is smelly VP → Verb stinks | VP NP feel + a breeze | VP Adjective is + smelly | VP PP turn + to the east | VP Adverb go + ahead PP → Preposition NP to + the east RelClause → that VP that + is smelly Chapter 22 14 Grammaticality judgements Formal language L1 may differ from natural language L2 L1 L2 positives false negatives false Adjusting L1 to agree with L2 is a learning problem! * the gold grab the wumpus * I smell the wumpus the gold I give the wumpus the gold * I donate the wumpus the gold Intersubjective agreement somewhat reliable, independent of semantics! Real grammars 10–500 pages, insufficient even for “proper” English Chapter 22 15 Parse trees Exhibit the grammatical structure of a sentence I shoot the wumpus Chapter 22 16 Parse trees Exhibit the grammatical structure of a sentence I shoot the wumpus Pronoun Verb Article Noun Chapter 22 17 Parse trees Exhibit the grammatical structure of a sentence I shoot the wumpus Pronoun Verb Article Noun NP VP NP Chapter 22 18
1111 Syntax in NLP Parse trees Exhibit the grammatical structure of a sentence Parse trees d me that he had soen "Woukn't the Most view X(s)means that string scan be interpreted as an if quotation marks had be Logical grammars Context-free parsing en placed before Fish,and b "And since I was not informed-as a matter of fact,since I did not know sential step towards meaning: Syntax in NLP
Parse trees Exhibit the grammatical structure of a sentence I shoot the wumpus Pronoun Verb Article Noun NP VP NP VP Chapter 22 19 Parse trees Exhibit the grammatical structure of a sentence I shoot the wumpus Pronoun Verb Article Noun NP VP NP VP S Chapter 22 20 Syntax in NLP Most view syntactic structure as an essential step towards meaning; “Mary hit John” 6= “John hit Mary” “And since I was not informed—as a matter of fact, since I did not know that there were excess funds until we, ourselves, in that checkup after the whole thing blew up, and that was, if you’ll remember, that was the incident in which the attorney general came to me and told me that he had seen a memo that indicated that there were no more funds.” Chapter 22 21 Syntax in NLP Most view syntactic structure as an essential step towards meaning; “Mary hit John” 6= “John hit Mary” “And since I was not informed—as a matter of fact, since I did not know that there were excess funds until we, ourselves, in that checkup after the whole thing blew up, and that was, if you’ll remember, that was the incident in which the attorney general came to me and told me that he had seen a memo that indicated that there were no more funds.” “Wouldn’t the sentence ’I want to put a hyphen between the words Fish and And and And and Chips in my Fish-And-Chips sign’ have been clearer if quotation marks had been placed before Fish, and between Fish and and, and and and And, and And and and, and and and And, and And and and, and and and Chips, as well as after Chips?” Chapter 22 22 Context-free parsing Bottom-up parsing works by replacing any substring that matches RHS of a rule with the rule’s LHS Efficient algorithms (e.g., chart parsing, Section 22.3) O(n 3 ) for context-free, run at several thousand words/sec for real grammars Context-free parsing ≡ Boolean matrix multiplication (Lee, 2002) ⇒ unlikely to find faster practical algorithms Chapter 22 23 Logical grammars BNF notation for grammars too restrictive: – difficult to add “side conditions” (number agreement, etc.) – difficult to connect syntax to semantics Idea: express grammar rules as logic X → YZ becomes Y (s1) ∧ Z(s2) ⇒ X(Append(s1, s2)) X → word becomes X([“word”]) X → Y | Z becomes Y (s) ⇒ X(s) Z(s) ⇒ X(s) Here, X(s) means that string s can be interpreted as an X Chapter 22 24
Ask(K B.S(r)) Now it's easy to augment the nes Ambiguity e many problems for NLP Real language (Can add extra arguments to retum the parse structure,semantics) NP(Append(s.who"] Logical grammars contd. Squad helps dog bite victim Ambiguity Ambiguity Ambiguity
Logical grammars contd. Now it’s easy to augment the rules NP(s1) ∧ EatsBreakfast(Ref(s1)) ∧ V P(s2) ⇒ NP(Append(s1, [“who”], s2)) NP(s1) ∧ Number(s1, n) ∧ V P(s2) ∧ Number(s2, n) ⇒ S(Append(s1, s2)) Parsing is reduced to logical inference: Ask(KB, S([“I” “am” “a” “wumpus”])) (Can add extra arguments to return the parse structure, semantics) Generation simply requires a query with uninstantiated variables: Ask K( B, S(x)) If we add arguments to nonterminals to construct sentence semantics, NLP generation can be done from a given logical sentence: Ask(KB, S(x, At(Robot, [1, 1])) Chapter 22 25 Real language Real human languages provide many problems for NLP: ♦ ambiguity ♦ anaphora ♦ indexicality ♦ vagueness ♦ discourse structure ♦ metonymy ♦ metaphor ♦ noncompositionality Chapter 22 26 Ambiguity Squad helps dog bite victim Chapter 22 27 Ambiguity Squad helps dog bite victim Helicopter powered by human flies Chapter 22 28 Ambiguity Squad helps dog bite victim Helicopter powered by human flies American pushes bottle up Germans Chapter 22 29 Ambiguity Squad helps dog bite victim Helicopter powered by human flies American pushes bottle up Germans I ate spaghetti with meatballs Chapter 22 30
Squad helps dog bite victim Ambiguity Ambiguity Ambiguity After Mary propos sed to hn.they found a preacher and got married Anaphora Ambiguity Ambiguity
Ambiguity Squad helps dog bite victim Helicopter powered by human flies American pushes bottle up Germans I ate spaghetti with salad meatballs Chapter 22 31 Ambiguity Squad helps dog bite victim Helicopter powered by human flies American pushes bottle up Germans I ate spaghetti with abandon salad meatballs Chapter 22 32 Ambiguity Squad helps dog bite victim Helicopter powered by human flies American pushes bottle up Germans I ate spaghetti with a abandon salad meatballs fork Chapter 22 33 Ambiguity Squad helps dog bite victim Helicopter powered by human flies American pushes bottle up Germans I ate spaghetti with a abandon salad meatballs fork a friend Chapter 22 34 Ambiguity Squad helps dog bite victim Helicopter powered by human flies American pushes bottle up Germans I ate spaghetti with a abandon salad meatballs fork a friend Ambiguity can be lexical (polysemy), syntactic, semantic, referential Chapter 22 35 Anaphora Using pronouns to refer back to entities already introduced in the text After Mary proposed to John, they found a preacher and got married. Chapter 22 36
threw arock at the window and brokeit Mary prop to hn,they found a preacher and got ma Anaphora Using pronouns to refer back to entities aready introduced in the text Anaphora For the honeymoon.they went to Hawali After,they found a Using pronouns to refer back to entitsaready introduced in the text Anaphora tried kiing but iton't die.Its parent keeps it alive "Non-iterafrsandysec I've read Shakespeare Metaphor Using one noun phrase to stand for anothe I am over here Metonymy Indexical sentences refer to utterance situation(pace,time.S/H.etc.) Indexicality
Anaphora Using pronouns to refer back to entities already introduced in the text After Mary proposed to John, they found a preacher and got married. For the honeymoon, they went to Hawaii Chapter 22 37 Anaphora Using pronouns to refer back to entities already introduced in the text After Mary proposed to John, they found a preacher and got married. For the honeymoon, they went to Hawaii Mary saw a ring through the window and asked John for it Chapter 22 38 Anaphora Using pronouns to refer back to entities already introduced in the text After Mary proposed to John, they found a preacher and got married. For the honeymoon, they went to Hawaii Mary saw a ring through the window and asked John for it Mary threw a rock at the window and broke it Chapter 22 39 Indexicality Indexical sentences refer to utterance situation (place, time, S/H, etc.) I am over here Why did you do that? Chapter 22 40 Metonymy Using one noun phrase to stand for another I’ve read Shakespeare Chrysler announced record profits The ham sandwich on Table 4 wants another beer Chapter 22 41 Metaphor “Non-literal” usage of words and phrases, often systematic: I’ve tried killing the process but it won’t die. Its parent keeps it alive. Chapter 22 42
basket ball shoes ositionality Noncompositionality
Noncompositionality basketball shoes Chapter 22 43 Noncompositionality basketball shoes baby shoes Chapter 22 44 Noncompositionality basketball shoes baby shoes alligator shoes Chapter 22 45 Noncompositionality basketball shoes baby shoes alligator shoes designer shoes Chapter 22 46 Noncompositionality basketball shoes baby shoes alligator shoes designer shoes brake shoes Chapter 22 47 Noncompositionality basketball shoes baby shoes alligator shoes designer shoes brake shoes red book Chapter 22 48
itionality 进鞭 ositionality Noncompositionality
Noncompositionality basketball shoes baby shoes alligator shoes designer shoes brake shoes red book red pen Chapter 22 49 Noncompositionality basketball shoes baby shoes alligator shoes designer shoes brake shoes red book red pen red hair Chapter 22 50 Noncompositionality basketball shoes baby shoes alligator shoes designer shoes brake shoes red book red pen red hair red herring Chapter 22 51 Noncompositionality basketball shoes baby shoes alligator shoes designer shoes brake shoes red book red pen red hair red herring small moon Chapter 22 52 Noncompositionality basketball shoes baby shoes alligator shoes designer shoes brake shoes red book red pen red hair red herring small moon large molecule Chapter 22 53 Noncompositionality basketball shoes baby shoes alligator shoes designer shoes brake shoes red book red pen red hair red herring small moon large molecule mere child Chapter 22 54
L是果 Noncompositionality Noncompositionality
Noncompositionality basketball shoes baby shoes alligator shoes designer shoes brake shoes red book red pen red hair red herring small moon large molecule mere child alleged murderer Chapter 22 55 Noncompositionality basketball shoes baby shoes alligator shoes designer shoes brake shoes red book red pen red hair red herring small moon large molecule mere child alleged murderer real leather Chapter 22 56 Noncompositionality basketball shoes baby shoes alligator shoes designer shoes brake shoes red book red pen red hair red herring small moon large molecule mere child alleged murderer real leather artificial grass Chapter 22 57