Slide 1HomeworkSlide 3Slide 4Next Word PredictionSlide 6Human Word PredictionMore ExamplesClaimApplicationsN-Gram Models of LanguageCorporaCounting Words in CorporaTerminologySimple N-GramsComputing the Probability of a Word SequenceBigram ModelUsing N-GramsTraining and TestingA Simple ExampleA Bigram Grammar Fragment from BERPSlide 22Slide 23BERP Bigram CountsBERP Bigram ProbabilitiesWhat do we learn about the language?Slide 27Approximating ShakespeareSlide 29Slide 30N-Gram Training SensitivityThe wall street journal is not shakespearePerplexity and EntropyComparison with FSAsSome Useful Empirical ObservationsSome Important ConceptsSlide 37Smoothing TechniquesAdd-one SmoothingSlide 40Witten-Bell DiscountingSlide 42Good-Turing DiscountingBackoff methods (e.g. Katz ‘87)Class-based ModelsGoogle N-Gram ReleaseGoogle N-Gram ReleaseSummaryCS 4705N-Grams and Corpus LinguisticsRegular expressions for asking questions about the stock market from stock reportsDue midnight, Sept. 29thUse Perl or Java reg-ex packageHW focus is on writing the “grammar” or FSA for question and answer matchingThe files are the kind of input you can expect. You are given files for “training” your program. When we grade, we will run your program on similar “test” files. Questions?Homework“But it must be recognized that the notion of “probability of a sentence” is an entirely useless one, under any known interpretation of this term.” Noam Chomsky (1969)“Anytime a linguist leaves the group the recognition rate goes up.”Fred Jelinek (1988)From a NY Times story...◦Stocks ...◦Stocks plunged this ….◦Stocks plunged this morning, despite a cut in interest rates◦Stocks plunged this morning, despite a cut in interest rates by the Federal Reserve, as Wall ...◦Stocks plunged this morning, despite a cut in interest rates by the Federal Reserve, as Wall Street beganNext Word Prediction◦Stocks plunged this morning, despite a cut in interest rates by the Federal Reserve, as Wall Street began trading for the first time since last …◦Stocks plunged this morning, despite a cut in interest rates by the Federal Reserve, as Wall Street began trading for the first time since last Tuesday's terrorist attacks.Clearly, at least some of us have the ability to predict future words in an utterance.How?◦Domain knowledge◦Syntactic knowledge◦Lexical knowledgeHuman Word PredictionThe stock exchange posted a gainThe stock exchange took a lossStock prices surged at the start of the dayStock prices got off to a strong startI set the table (American)I lay the table (British)More ExamplesA useful part of the knowledge needed to allow Word Prediction can be captured using simple statistical techniquesIn particular, we'll rely on the notion of the probability of a sequence (of letters, words,…)ClaimWhy do we want to predict a word, given some preceding words?◦Rank the likelihood of sequences containing various alternative hypotheses, e.g. for ASRTheatre owners say popcorn/unicorn sales have doubled...◦Assess the likelihood/goodness of a sentence, e.g. for text generation or machine translationEl doctor recommendó una exploración del gato.The doctor recommended a cat scan.The doctor recommended a scan of the cat.ApplicationsUse the previous N-1 words in a sequence to predict the next wordLanguage Model (LM)◦unigrams, bigrams, trigrams,…How do we train these models?◦Very large corporaN-Gram Models of LanguageCorpora are online collections of text and speech◦Brown Corpus◦Wall Street Journal◦AP newswire◦Hansards◦DARPA/NIST text/speech corpora (Call Home, ATIS, switchboard, Broadcast News, TDT, Communicator)◦TRAINS, Radio NewsCorporaWhat is a word? ◦e.g., are cat and cats the same word?◦September and Sept?◦zero and oh?◦Is _ a word? * ? ‘(‘ ?◦How many words are there in don’t ? Gonna ?◦In Japanese and Chinese text -- how do we identify a word?Counting Words in CorporaSentence: unit of written languageUtterance: unit of spoken languageWord Form: the inflected form as it actually appears in the corpusLemma: an abstract form, shared by word forms having the same stem, part of speech, and word sense – stands for the class of words with stemTypes: number of distinct words in a corpus (vocabulary size)Tokens: total number of wordsTerminologyAssume a language has T word types in its lexicon, how likely is word x to follow word y?◦Simplest model of word probability: 1/T◦Alternative 1: estimate likelihood of x occurring in new text based on its general frequency of occurrence estimated from a corpus (unigram probability)popcorn is more likely to occur than unicorn◦Alternative 2: condition the likelihood of x occurring in the context of previous words (bigrams, trigrams,…)mythical unicorn is more likely than mythical popcornSimple N-GramsCompute the product of component conditional probabilities?◦P(the mythical unicorn) = P(the) P(mythical|the) * P(unicorn|the mythical)The longer the sequence, the less likely we are to find it in a training corpus P(Most biologists and folklore specialists believe that in fact the mythical unicorn horns derived from the narwhal)Solution: approximate using n-gramsComputing the Probability of a Word SequenceApproximate by ◦P(unicorn|the mythical) by P(unicorn|mythical)Markov assumption: the probability of a word depends only on the probability of a limited historyGeneralization: the probability of a word depends only on the probability of the n previous words◦trigrams, 4-grams, …◦the higher n is, the more data needed to train. Thus backoff models…Bigram Model)11|(nnwwP)|(1nnwwPFor N-gram models◦  ◦P(wn-1,wn) = P(wn | wn-1) P(wn-1)◦By the Chain Rule we can decompose a joint probability, e.g. P(w1,w2,w3)P(w1,w2, ...,wn) = P(w1|w2,w3,...,wn) P(w2|w3, ...,wn) … P(wn-1|wn) P(wn)For bigrams then, the probability of a sequence is just the product of the conditional probabilities of its bigramsP(the,mythical,unicorn) = P(unicorn|mythical) P(mythical|the) P(the|<start>)Using N-Grams)11|(nnwwP)11|(nNnnwwPnkkknwwPwP111)|()(N-Gram probabilities come from a training corpus◦overly narrow corpus: probabilities don't generalize◦overly general corpus: probabilities don't reflect task or domainA separate test corpus is used to evaluate the model,