Modeling GrammaticalityWord trigrams: A good model of English?Why it does okay …Why it does okay … but isn’t perfect.Slide 5Grammatical English sentencesWhat happens as you increase the amount of training text?Slide 8Are n-gram models enough?Can we avoid the systematic problems with n-gram models?Finite-state modelsContext-free grammarsWrite a grammar of EnglishNow write a grammar of EnglishSlide 15Slide 16Slide 17600.465 - Intro to NLP - J. Eisner 1Modeling Grammaticality[mostly a blackboard lecture]600.465 - Intro to NLP - J. Eisner 2Word trigrams: A good model of English?namesallformshashis housewassamehasshassWhich sentences are grammatical????no main verbWhy it does okay …We never see “the go of” in our training text.So our dice will never generate “the go of.”That trigram has probability 0.Why it does okay … but isn’t perfect.We never see “the go of” in our training text.So our dice will never generate “the go of.”That trigram has probability 0.But we still got some ungrammatical sentences …All their 3-grams are “attested” in the training text, but still the sentence isn’t good.You shouldn’t eat these chickens because these chickens eat arsenic and bone meal …Training sentences… eat these chickens eat …3-gram modelWhy it does okay … but isn’t perfect.We never see “the go of” in our training text.So our dice will never generate “the go of.”That trigram has probability 0.But we still got some ungrammatical sentences …All their 3-grams are “attested” in the training text, but still the sentence isn’t good.Could we rule these bad sentences out?4-grams, 5-grams, … 50-grams?Would we now generate only grammatical English?Grammatical English sentencesTraining sentencesPossible under trained 3-gram model(can be built from observed 3-grams by rolling dice)Possible under trained 4-gram modelPossible undertrained 50-grammodel ?What happens as you increase the amount of training text?Training sentencesPossible under trained 3-gram model(can be built from observed 3-grams by rolling dice)Possible under trained 4-gram modelPossible undertrained 50-grammodel ?What happens as you increase the amount of training text?Training sentences (all of English!)Now where are the 3-gram, 4-gram, 50-gram boxes?Is the 50-gram box now perfect?(Can any model of language be perfect?)Can you name some non-blue sentences in the 50-gram box?Are n-gram models enough?Can we make a list of (say) 3-grams that combine into all the grammatical sentences of English?Ok, how about only the grammatical sentences?How about all and only?Can we avoid the systematic problems with n-gram models?Remembering things from arbitrarily far back in the sentenceWas the subject singular or plural?Have we had a verb yet?Formal language equivalent:A language that allows strings having the forms a x* b and c x* d (x* means “0 or more x’s”)Can we check grammaticality using a 50-gram model?No? Then what can we use instead?Finite-state modelsRegular expression: a x* b | c x* d Finite-state acceptor:xxa bcdMust remember whether first letter was a or c. Where does the FSA do that?Context-free grammarsSentence Noun Verb NounS N V NN MaryV likesHow many sentences? Let’s add: N JohnLet’s add: V sleeps, S N VWrite a grammar of English What’s a grammar? 1 S NP VP .1 VP VerbT NP20 NP Det N’1 NP Proper20 N’ Noun1 N’ N’ PP1 PP Prep NPSyntactic rules.You have a week. Now write a grammar of English1 Noun castle1 Noun king …1 Proper Arthur1 Proper Guinevere …1 Det a1 Det every …1 VerbT covers1 VerbT rides …1 Misc that1 Misc bloodier1 Misc does …1 S NP VP .1 VP VerbT NP20 NP Det N’1 NP Proper20 N’ Noun1 N’ N’ PP1 PP Prep NPSyntactic rules.Lexical rules.Now write a grammar of EnglishHere’s one to start with.S1NP VP .1 S NP VP .1 VP VerbT NP20 NP Det N’1 NP Proper20 N’ Noun1 N’ N’ PP1 PP Prep NPNow write a grammar of EnglishHere’s one to start with.SNP VP .Det N’20/211/211 S NP VP .1 VP VerbT NP20 NP Det N’1 NP Proper20 N’ Noun1 N’ N’ PP1 PP Prep NPNow write a grammar of EnglishHere’s one to start with.SNP VP .Det N’Nouneverycastledrinks [[Arthur [across the [coconut in the castle]]] [above another chalice]]1 S NP VP .1 VP VerbT NP20 NP Det N’1 NP Proper20 N’ Noun1 N’ N’ PP1 PP Prep
View Full Document