Language model

From Wikipedia, the free encyclopedia

A statistical language model assigns a probability to a sequence of m words $P(w_{1},\ldots ,w_{m})$ by means of a probability distribution.

Language modeling is used in many natural language processing applications such as speech recognition, machine translation, part-of-speech tagging, parsing and information retrieval.

In speech recognition and in data compression, such a model tries to capture the properties of a language, and to predict the next word in a speech sequence.

When used in information retrieval, a language model is associated with a document in a collection. With query Q as input, retrieved documents are ranked based on the probability that the document's language model would generate the terms of the query, P(Q|M_d). The method to use language models in information retrieval is the query likelihood model.

In practice, unigram language models are most commonly used in information retrieval, as they are sufficient to determine the topic from a piece of text. Unigram models only calculate the probability of hitting an isolated word, without considering any influence from the words before or after the target. This leads to the Bag of words model, and turns out to generate a multinomial distribution over words.

Estimating the probability of sequences can become difficult in corpora, in which phrases or sentences can be arbitrarily long and hence some sequences are not observed during training of the language model (data sparseness problem of overfitting). For that reason these models are often approximated using smoothed N-gram models.

Unigram models

A unigram model used in information retrieval can be treated as the combination of several one-state finite automata.^[1] It splits the probabilities of different terms in a context, e.g. from $P(t_{1}t_{2}t_{3})=P(t_{1})P(t_{2}|t_{1})P(t_{3}|t_{1}t_{2})$ to $P_{{uni}}(t_{1}t_{2}t_{3})=P(t_{1})P(t_{2})P(t_{3})$ .

In this model, the probability to hit each word all depends on its own, so we only have one-state finite automata as units. For each automaton, we only have one way to hit its only state, assigned with one probability. Viewing from the whole model, the sum of all the one-state-hitting probabilities should be 1. Followed is an illustration of an unigram model of a document.

Terms	Probability in doc
a	0.1
world	0.2
likes	0.05
we	0.05
share	0.3
...	...

$\sum _{{term\ in\ doc}}P(term)=1$

The probability generated for a specific query is calculated as

$P(query)=\prod _{{term\ in\ query}}P(term)$

For different documents, we can build their own unigram models, with different hitting probabilities of words in it. And we use probabilities from different documents to generate different hitting probabilities for a query. Then we can rank documents for a query according to the generating probabilities. Next is an example of two unigram models of two documents.

Terms	Probability in Doc1	Probability in Doc2
a	0.1	0.3
world	0.2	0.1
likes	0.05	0.03
we	0.05	0.02
share	0.3	0.2
...	...	...

In information retrieval contexts, unigram language models are often smoothed to avoid instances where $P(term)=0$ . A common approach is to generate a maximum-likelihood model for the entire collection and linearly interpolate the collection model with a maximum-likelihood model for each document to create a smoothed document model.^[2]

N-gram models

Main article: N-gram

In an n-gram model, the probability $P(w_{1},\ldots ,w_{m})$ of observing the sentence w₁,...,w_m is approximated as

$P(w_{1},\ldots ,w_{m})=\prod _{{i=1}}^{m}P(w_{i}|w_{1},\ldots ,w_{{i-1}})\approx \prod _{{i=1}}^{m}P(w_{i}|w_{{i-(n-1)}},\ldots ,w_{{i-1}})$

Here, it is assumed that the probability of observing the i^th word w_i in the context history of the preceding i-1 words can be approximated by the probability of observing it in the shortened context history of the preceding n-1 words (n^th order Markov property).

The conditional probability can be calculated from n-gram frequency counts: $P(w_{i}|w_{{i-(n-1)}},\ldots ,w_{{i-1}})={\frac {count(w_{{i-(n-1)}},\ldots ,w_{{i-1}},w_{i})}{count(w_{{i-(n-1)}},\ldots ,w_{{i-1}})}}$

The words bigram and trigram language model denote n-gram language models with n=2 and n=3, respectively.^[3]

Typically, however, the n-gram probabilities are not derived directly from the frequency counts, because models derived this way have severe problems when confronted with any n-grams that have not explicitly been seen before. Instead, some form of smoothing is necessary, assigning some of the total probability mass to unseen words or N-grams. Various methods are used, from simple "add-one" smoothing (assign a count of 1 to unseen N-grams) to more sophisticated models, such as Good-Turing discounting or back-off models.

Example

In a bigram (n=2) language model, the probability of the sentence I saw the red house is approximated as

whereas in a trigram (n=3) language model, the approximation is

Note that the context of the first $n-1$ N-grams is filled with start-of-sentence markers, typically denoted <s>.

Additionally, without an end-of-sentence marker, the probability of an ungrammatical sequence *I saw the would always be higher than that of the longer sentence I saw the red house.

Other models

A positional language model^[4] is one that describes the probability of given words occurring close to one another in a text, not necessarily immediately adjacent. Similarly, bag-of-concepts models^[5] leverage on the semantics associated with multi-word expressions such as buy_christmas_present, even when they are used in information-rich sentences like "today I bought a lot of very nice Christmas presents".

References

↑ Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze: An Introduction to Information Retrieval, pages 237-240. Cambridge University Press, 2009
↑ Buttcher, Clarke, and Cormack. Information Retrieval: Implementing and Evaluating Search Engines. pg. 289-291. MIT Press.
↑ Craig Trim, What is Language Modeling?, April 26th, 2013.
↑ Yuanhua Lv and ChengXiang Zhai, Positional Language Models for Information Retrieval, in Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval (SIGIR), 2009.
↑ E. Cambria and A. Hussain. Sentic Computing: Techniques, Tools, and Applications. Dordrecht, Netherlands: Springer, ISBN 978-94-007-5069-2 (2012)

External links

LMSharp - Free language model toolkit for Kneser-Ney smoothed n-gram model and recurrent neural network model
DALM - Fast, Free software for language model queries
IRSTLM - Free software for language modeling
KenLM - Fast, Free software for language modeling
MITLM - MIT Language Modeling toolkit. Free software
OpenGrm NGram library - Free software for language modeling. Built on OpenFst.
Positional Language Model
RandLM - Free software for randomised language modeling
SRILM - Proprietary software for language modeling
VariKN - Free software for creating, growing and pruning Kneser-Ney smoothed n-gram models.

Language models trained on newswire data

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.