Créer une présentation
Télécharger la présentation

Télécharger la présentation
## Overview of Statistical Language Models

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**Overview of Statistical Language Models**ChengXiang Zhai Department of Computer Science University of Illinois, Urbana-Champaign**Outline**• What is a statistical language model (SLM)? • Brief history of SLM • Types of SLM • Applications of SLM**What is a Statistical Language Model (LM)?**• A probability distribution over word sequences • p(“Today is Wednesday”) 0.001 • p(“Today Wednesday is”) 0.0000000000001 • p(“The eigenvalue is positive”) 0.00001 • Context-dependent! • Can also be regarded as a probabilistic mechanism for “generating” text, thus also called a “generative” model Today is Wednesday Today Wednesday is … The eigenvalue is positive**Definition of a SLM**• Vocabulary set: V={t1, t2, …, tN}, N terms • Sequence of M terms: s= w1 w2 …wM , wiV • Probability of sequence s: • p(s)=p(w1 w2 … wM)=? • How do we compute this probability? How do we “generate” a sequence using a probabilistic model? • Option 1: Assume each sequence is generated as a “whole unit” • Option 2: Assume each sequence is generated by generating one word each time • Each word is generated independently • Option 3: ??**Brief History of SLMs**• 1950s~1980:Early work, mostly done by the IR community • Main applications are to select indexing terms and rank documents • Language model-based approaches “lost” to vector space approaches in empirical IR evaluation • Limited models developed • 1980~2000:Major progress made mostly by the speech recognition community and NLP community • Language model was recognized as an important component in statistical approaches to speech recognition and machine translation • Improved language models led to reduced speech recognition errors and improved machine translation results • Many models developed!**Brief History of SLMs**• 1998~2010: Progress made on using language models for IR and for text analysis/mining • Success of LMs in speech recognition inspired more research in using LMs for IR • Language model-based retrieval models are at least as competitive as vector space models with more guidance on parameter optimization • Topic language model (PLSA & LDA) proposed and extensively studied • 2010~ present: Neural language models emerging and attracting much attention • Addressing the data sparsity challenge in “traditional” language model • Representation learning (word embedding)**Types of SLM**• “Standard” SLMs all attempt to formally define p(s) =p(w1….wM) • Different ways to refine this definition lead to different types of LMs (= different ways to “generate” text data) • Pure statistical vs. Linguistically motivated • Many variants come from different ways to capture dependency between words • “Non-standard” SLMs may attempt to define a probability on a transformed form of a text object • Only model presence or absence of terms in a text sequence without worrying about different frequencies • Model co-occurring word pairs in text • …**The Simplest Language Model: Unigram LM**• Generate text by generating each word INDEPENDENTLY • Thus, p(w1 w2 ... wn)=p(w1)p(w2)…p(wn) • Parameters: {p(ti)} p(t1)+…+p(tN)=1 (N is voc. size) • Text = sample drawn according to this word distribution Wednesday p(“today is Wed”) = p(“today”)p(“is”)p(“Wed”) = 0.0002 0.001 0.000015 today … eigenvalue**More Sophisticated LMs**• N-gramlanguage models • In general, p(w1 w2 ... wn)=p(w1)p(w2|w1)…p(wn|w1 …wn-1) • n-gram: conditioned only on the past n-1 words • E.g., bigram: p(w1 ... wn)=p(w1)p(w2|w1) p(w3|w2) …p(wn|wn-1) • Exponential language models (e.g., Maximum Entropy model) • P(w|history) as a function with features defined on “(w, history)” • Features are weighted with parameters (fewer parameters!) • Structured language models: generate text based a latent (linguistic) structure (e.g., probabilistic context-free grammar) • Neural language models (e.g., recurrent neural networks, word embedding): model p(w|history) as a neural network**Applications of SLMs**• As a prior for Bayesian inference when the random variable to infer is text • As the “likelihood part” in Bayesian inference when the observed data is text • As a way to “understand” text data and obtain a more meaningful representation of text for a particular application (Text Mining)**Application 1: As Prior in Bayesian Inference:**Transmitter (encoder) Receiver (decoder) Noisy Channel Source Destination X Y X’ P(X) P(X|Y)=? P(Y|X) (Bayes Rule) When X is text, p(X) is a language model Many Examples: Speech recognition: X=Word sequence Y=Speech signal Machine translation: X=English sentence Y=Chinese sentence OCR Error Correction: X=Correct word Y= Erroneous word Information Retrieval: X=Document Y=Query Summarization: X=Summary Y=Document**Application 2: As Likelihood in Bayesian Inference**Transmitter (encoder) Receiver (decoder) Noisy Channel Source Destination X Y X’ P(X) P(X|Y)=? P(Y|X) (Bayes Rule) When Y is text, p(Y|X) is a (conditional) language model Many Examples: Text categorization: X=Topic Category Y=Text document Machine translation: X=English sentence Y=Chinese sentence Sentiment tagging: X=Sentiment label Y= Text object**Application 3: Language Model for Text Mining**• More interested in the parameters of a language model than the accuracy of the language model itself • Parameter values estimated based on a text object or a set of text objects can be directly useful for a task (e.g., topics covered in the text data) • Parameter values may serve as a “model-based representation” of text objects to further support downstream applications (e.g., dimension reduction due to representing text by a set of topics rather than a set of words) • Examples • discovery of frequent sequential patterns in text data by fitting an n-gram language model to the text data • Part-of-speech tagging & parsing with a SLM**Using Language Models for POS Tagging**This is a new sentence Det Aux Det Adj N “This is a new sentence” Method 1: Independent assignment Most common tag This is a new sentence Det Det Det Det Det … … Det Aux Det Adj N … … V2 V2 V2 V2 V2 Consider all possibilities, and pick the one with the highest probability Method 2: Partial dependency Training data (Annotated text) This sentence serves as an example of Det N V1 P Det N P annotated text… V2 N POS Tagger w1=“this”, w2=“is”, …. t1=Det, t2=Det, …,**Using SLM for Parsing (Probabilistic Context-Free Grammar)**Probability of this tree=0.000015 1.0 0.3 0.4 0.3 … … 1.0 0.01 0.003 … … roller skates S S NP VP NP Det BNP NP BNP NP NP PP BNP N VP V VP Aux V NP VP VP PP PP P NP V chasing Aux is N dog N boy N playground Det the Det a P on NP VP Det BNP VP PP Grammar A N Aux V NP P NP chasing on dog is a boy the playground Generate S Choose a tree with highest prob…. NP VP Det NP BNP Aux V Lexicon PP A NP N is chasing NP P dog a boy on the playground Can also be treated as a classification/decision problem…**Importance ofUnigram Models for Text Retrieval and Analysis**• Words are meaningful units designed by humans and often sufficient for retrieval and analysis tasks • Difficulty in moving toward more complex models • They involve more parameters, so need more data to estimate (A doc is an extremely small sample) • They increase the computational complexity significantly, both in time and space • Capturing word order or structure may not add so much value for “topical inference”, though using more sophisticated models can still be expected to improve performance • It’s often easy to extend a method using a unigram LM to using an n-gram LM**Evaluation of SLMs**• Direct evaluation criterion: How well does the model fit the data to be modeled? • Example measures: Data likelihood, perplexity, cross entropy, Kullback-Leibler divergence (mostly equivalent) • Indirect evaluation criterion: Does the model help improve the performance of the task? • Specific measure is task dependent • For retrieval, we look at whether a model helps improve retrieval accuracy, whereas for speech recognition, we look at the impact of language model on recognition errors • We hope more “reasonable” LMs would achieve better task performance (e.g., higher retrieval accuracy or lower recognition error rate)**What You Should Know**• What is a statistical language model? • What is a unigram language model? • What is an N-gram language model? What assumptions are made in an N-gram language model? • What are the major types of language models? • What are the three ways that a language model can be used in an application?