underlying multinomial distributions of words $n$ associated with label
variables $l$. Usually the instances of text are documents and the label
variables are classes, document identifiers, or clusters, depending on the
task. The label-dependent multinomial distributions $p_{l}(n)$ are called
conditional distributions, and are combined with a categorical prior
distribution $p(l)$ of the label variables. A common intuitive explanation is
a “generative process”, where documents are generated by first sampling a
label from the categorical distribution, and then sampling words from the
multinomial associated with the label.

A generative model in ML terminology is a model of the joint distribution
$p(\bm{w},l)$ of input and output variables (Bishop, 2006; Klinger and
Tomanek, 2007; Sutton and McCallum, 2007). For MNB the inputs are word vectors
$\bm{w}$ and the outputs are document labels $l$. A generative Bayes model
factorizes the joint distribution as
$p(\bm{w},l|\bm{\theta})=p_{l}(\bm{w}|\bm{\lambda})p(l|\bm{\pi})$, so that the
parameters $\bm{\theta}$ are assumed to factorize into parameters
$\bm{\lambda}$ for the _conditionals_ $p_{l}(\bm{w}|\bm{\lambda})$ and
$\bm{\pi}$ for the _prior_ $p(l|\bm{\pi})$. Posterior inference can be done by
applying Bayes theorem: $p(l|\bm{w})=p(\bm{w}|l)p(l)/p(\bm{w})$, where
$p(l|\bm{w})$ is called the _posterior_ and $p(\bm{w})=\sum_{l}p(\bm{w},l)$
the _marginal_. For ranking and classification, the marginal can be omitted
and the inference done by maximizing the _joint_ $p(\bm{w},l)$ instead. In
classification, the optimization becomes
$\operatornamewithlimits{argmax}_{l}p_{l}(\bm{w})p(l)$. Regression can be
performed with continuous variables for labels (Frank et al., 1998).

A problem with Bayes classifiers is estimating the dependencies of the input
variables or features $n$ for computing $p_{l}(\bm{w})$. By making
independence assumptions, computing $p_{l}(\bm{w})$ can be simplified. A
common assumption is “naive independence’, which assumes that the conditional
probabilities $p_{l}(n,w_{n})$ are independent, that is,
$p_{l}(\bm{w})=\prod_{n}p_{l}(n,w_{n})$. Models of this type are commonly
called NB models. The parameterization of $p_{l}(\bm{w})$ can take many forms.
A common type of NB model is the multivariate Bernoulli NB (Maron, 1961),
where the counts $w_{n}$ are restricted to binary values
$\forall_{n}:w_{n}\in\\{0,1\\}$ and each class conditional probability
$p_{l}(n,w_{n})$ is modeled by a Bernoulli distribution. The Bernoulli
distribution models biased “coin-flip” outcomes of a variable by using a
single parameter describing how biased the coin flips are. For example, with
parameter $\lambda_{ln}=\log(0.1)$, the probability of the word $n$ occurring
in a document for label $l$ would be $0.1$. The Bernoulli parameters can be
estimated simply by counting the training documents $\bm{w}^{(i)}$ for label
$l$ with the word $n$, and dividing by the number of documents for that label.

The multivariate Bernoulli model for NB (Maron, 1961; Robertson and Jones,
1976; Domingos and Pazzani, 1997; Lewis, 1998; McCallum and Nigam, 1998;
Craven et al., 2000) is also known as the Binary Independence Model and
Bernoulli NB, and was the first type of NB model suggested for text mining
(Maron, 1961). Other possible models for $p_{l}(\bm{w})$ in text mining
include Gaussian (Domingos and Pazzani, 1997), multinomial (Lewis, 1998;
McCallum and Nigam, 1998; Craven et al., 2000; Rennie et al., 2003; Schneider,
2005; Frank and Bouckaert, 2006; Puurula, 2012b), Poisson (Church and Gale,
1995; Kim et al., 2006; Li and Zha, 2006), Von Mises-Fisher (Banerjee et al.,
2005), asymmetric distributions (Bennett, 2003), kernel densities (Ciarelli et
al., 2009), and finite mixtures of distributions (Church and Gale, 1995;
Banerjee et al., 2005; Li and Zha, 2006).

For most text mining uses the multivariate Bernoulli model has been replaced
by the multinomial model of text and its extensions. A multinomial
distribution can be seen as a generalization of the Bernoulli distribution
into multiple coin-flip outcomes and multiple coin tosses, much like multiple
rolls of a biased dice with $N$ sides. A multinomial models the sums of $n$
possible outcomes from $J=\sum_{n}w_{n}$ dice rolls. The exact order of the
dice rolls in a sequence of $J$ rolls $\underline{w}_{j}$ is not needed for
counting the sums of outcomes $w_{n}$. The probability mass function for a
label-conditional multinomial distribution of word vectors becomes
$p_{l}(\bm{w})=Z(\bm{w})\prod_{n}p_{l}(n)^{w_{n}}$. The normalizer
$Z(\bm{w})=\frac{(\sum_{n}w_{n})!}{\prod_{n}w_{n}!}$ takes into account that
word vectors can correspond to a number of different word sequences. As it is
constant for a given word vector, it can be omitted in most uses. A common
special case of the multinomial is the binomial distribution $N=2$. Another
special case of note is the categorical distribution $\sum_{n}w_{n}=1$.

Using multinomials for Bayes model conditional distributions, we get the joint
probability distribution for MNB:

$\displaystyle p(\bm{w},l)=$ $\displaystyle p(l)p_{l}(\bm{w})$
$\displaystyle=$ $\displaystyle p(l)Z(\bm{w})\prod_{n}p_{l}(\bm{w})^{w_{n}},$
(1)

where $p(l)$ and $p_{l}(\bm{w})$ are parameterized with a categorical and a
multinomial, respectively.

Since document lengths $J$ vary, models are defined over all possible lengths,
and the multinomials for different lengths have shared parameters. The shared
parameters are “tied”, since they are constrained to be equal regardless of
length. In addition, a distribution such as Poisson must be assumed for
generating different document lengths, so that the model can generate the
joint distribution over documents of all lengths. The length factor has no
practical effect in most applications, and is omitted for posterior inference
uses such as clustering, ranking and classification. Therefore both the length
factor and the multinomial parameter tying are commonly omitted in the MNB
literature (McCallum and Nigam, 1998).

A problem with varying document lengths is that the posterior probabilities
for MNB models get increasingly close to either $0$ or $1$ as the document
length increases, since the conditional probability $p_{l}(\bm{w})$ is
computed by multiplying the $N$ probabilities $p_{l}(\bm{w})$ independently
(Frank et al., 1998; Monti and Cooper, 1999; Bennett, 2000; Craven et al.,
2000). This scale distortion of the posteriors does not affect classification,
ranking or hard clustering, since the rank-order of probabilities for
different labels is preserved. For uses such as soft clustering the posterior
probabilities can be improved with feature transforms (Pavlov et al., 2004),
feature selection (Rigouste et al., 2007; Pinto et al., 2007), and using KL-
divergence instead of posterior probabilities to correct for the document
lengths (Craven et al., 2000; Schneider, 2005; Pinto et al., 2007).
Nevertheless, for some applications the indirectly estimated posterior
probabilities from MNB can be insufficient, and a model directly optimizing
the posterior probabilities is preferred, such as LR.

####  3 Estimation

Estimation of MNB parameters is commonly done by applying maximum likelihood
estimation (McCallum, 1999; Rennie, 2001; Juan and Ney, 2002; Vilar et al.,
2004; Madsen et al., 2005; Frank and Bouckaert, 2006). Due to the data
sparsity problem with text data, various smoothing methods are commonly used
to correct maximum likelihood parameter estimates. In some cases the smoothed
estimation is presented as maximum a posteriori estimation (Rennie, 2001;
Schneider, 2005; Smucker and Allan, 2007). Despite the name “Bayes”, NB models
are commonly not Bayesian in the sense of Bayesian estimation, where a
distribution over parameters is maintained instead of a point estimate of
parameters. A fully Bayesian version of MNB has been proposed, but shown to be
less suitable than maximum likelihood point estimates (Rennie, 2001). The most
common type of estimation is supervised estimation, where a training dataset
$D$ consists of $I$ pairs $D^{(i)}=(\bm{w}^{(i)},l^{(i)})$ of word vectors and
labels, assumed to be independent and identically distributed (IID). The
unsmoothed maximum likelihood estimation approach for the supervised case is
described next.

The maximum likelihood method of statistical estimation selects a vector of
parameters for a model that maximizes the likelihood of the parameters given
the data $\mathcal{L}({\bm{\theta}}|D)$. This equals the probability of the
data given the parameters $p(D|{\bm{\theta}})$. A conceptual difference
between these two is that likelihood is a function of parameters for given
training data, whereas probability assumes a model with parameters and can
refer to both seen and future data. The MNB likelihood function can be
derived:

$\displaystyle\mathcal{L}({\bm{\theta}}|D)$ $\displaystyle=p(D|{\bm{\theta}})$
$\displaystyle=\prod_{i}p(l^{(i)}|{\bm{\theta}})p_{l^{(i)}}(\bm{w}^{(i)}|{\bm{\theta}})$
IID data assumption
$\displaystyle=\prod_{i}p(l^{(i)}|\bm{\lambda})p_{l^{(i)}}(\bm{w}^{(i)}|\bm{\pi})$
Bayes model
$\displaystyle=\prod_{i}p(l^{(i)}|\bm{\pi})\prod_{n}p_{l^{(i)}}(n|\bm{\lambda})^{w^{(i)}_{n}}\frac{(\sum_{n}w^{(i)}_{n})!}{\prod_{n}w^{(i)}_{n}!}$
Multinomial conditional (2)

Maximizing the likelihood can be simplified by noting that the log of the
likelihood has the same maximum, but is easier to handle computationally. The
MNB log-likelihood decomposes into terms that can be separately optimized. The
maximization of the log-likelihood function can be derived:

$\displaystyle\operatornamewithlimits{argmax}_{\bm{\theta}}(\mathcal{L}(\bm{\theta}|D))=\operatornamewithlimits{argmax}_{\bm{\theta}}(\log\mathcal{L}({\bm{\theta}}|D))=\operatornamewithlimits{argmax}_{\bm{\theta}}(\log
p(D|{\bm{\theta}}))$
$\displaystyle=\operatornamewithlimits{argmax}_{(\bm{\lambda},\bm{\pi})}(\log(\prod_{i}p(l^{(i)}|\bm{\pi})\prod_{n}p_{l^{(i)}}(n|\bm{\lambda})^{w^{(i)}_{n}}\frac{(\sum_{n}w^{(i)}_{n})!}{\prod_{n}w^{(i)}_{n}!}))$
$\displaystyle=\operatornamewithlimits{argmax}_{(\bm{\lambda},\bm{\pi})}(\sum_{i}(\log
p(l^{(i)}|\bm{\pi})+\sum_{n}w^{(i)}_{n}\log
p_{l^{(i)}}(n|\bm{\lambda})+\log(\frac{(\sum_{n}w^{(i)}_{n})!}{\prod_{n}w^{(i)}_{n}!})))$
$\displaystyle=\operatornamewithlimits{argmax}_{(\bm{\lambda},\bm{\pi})}(\sum_{i}\log
p(l^{(i)}|\bm{\pi})+\sum_{i}\sum_{n}w^{(i)}_{n}\log
p_{l^{(i)}}(n|\bm{\lambda}))$
$\displaystyle=\operatornamewithlimits{argmax}_{(\bm{\lambda},\bm{\pi})}(\sum_{l}C(l)\log
p(l|\bm{\pi})+\sum_{l}\sum_{n}C(l,n)\log p_{l}(n|\bm{\lambda})),$ (3)

where $C(l)$ and $C(l,n)$ refer to the accumulated counts of the variables in
the training data.

Optimizing the parameters for the prior and conditionals can now be done
separately, and for both cases this consists of choosing the vector of
parameters that most likely generated the accumulated vector of counts. The
maximum likelihood solution to this estimation of a categorical distribution
$p(l|\bm{\pi})$ is the relative frequency estimate
$C(l)/\sum_{l^{\prime}}C(l^{\prime})$:
$\pi_{l}=\log(C(l)/\sum_{l^{\prime}}C(l^{\prime}))$ and
$\lambda_{ln}=\log(C(l,n)/\sum_{n^{\prime}}C(l,n^{\prime}))$. This is a
standard result in statistics and commonly proven using the method of Lagrange
multipliers (Bilmes, 1998; Juan and Ney, 2002).

In practice, estimating the MNB model consists of accumulating the counts in
training data and normalizing by the sums of counts, with time complexity
$O(IN)$ and space complexity $O(LN)$. Taking sparsity into account, the space
complexity of estimation is reduced to
$O(L+\sum_{l}\sum_{n:\exp(\lambda_{ln})>0}1)$ and time complexity to
$O(\sum_{i}|\bm{w}^{(i)}|_{0})$. The parameters can be represented efficiently
using sparse matrix representations. A hash table with $(l,n)$ pairs as keys
and parameters as values is one popular choice, with amortized constant time
complexities for updating the counts. Another common choice is sparse vectors
of word counts and periodic merging of the accumulated vectors with list merge
operations. With large-scale datasets this can be done using the map-reduce
framework (Dean and Ghemawat, 2008).

Given labeled training data, maximum likelihood estimation of parameters for
MNB can be done 1) exactly, 2) with a closed form solution, 3) as online
learning, and 4) in linear time complexity in terms of features, documents and
classes. These four advantages make MNB highly useful in practical
applications. The maximum likelihood estimates are exact, so there are no
approximations required, and any system using MNB does not have to consider
possible errors from approximations. The closed form solution means that the
estimates can be computed by applying elementary mathematical operators, such
as summation and division. The estimation can be done as online learning from
streams of text documents, and the effect of older documents can be removed
from the estimates trivially. Lastly, the maximum likelihood estimation has
linear complexities in all relevant dimensions. Among the common text mining
methods, only Centroid and K-nearest Neighbours classifiers have the same
scalability in training.

Extending MNB estimation to weighted data can be done by weighting the
accumulated counts from each document. In some cases documents are softly
labeled, by using a distribution of weights over labels instead of a single
label. Extending the estimation to soft labeling can be done similarly, by
weighting the counts by the label weights. In case of unsupervised and semi-
supervised estimation, the expectation maximization (EM) algorithm (Dempster
et al., 1977; Bailey and Elkan, 1994; Bilmes, 1998; Zhong and Ghosh, 2005;
Nigam et al., 2006; Gupta and Chen, 2011) can be used to estimate parameters.
This consists of initialization of parameters followed by EM-iterations of
computing the soft labeling $p(l|\bm{w}^{(i)})$ (expectation step) and re-
estimating the model from the soft labeling (maximization step). Each
iteration improves the log-likelihood until a stationary point of the
likelihood function is reached. Combining EM with multiple random
initializations reduces the probability of not reaching a global optimum of
the likelihood. Improvements of EM such as online EM (Liang and Klein, 2009)
can be used to estimate parameters from stream data and reduce the required
amount of EM-iterations.

###  2 Generative Models Extending MNB

####  1 Mixture Models

Mixture modeling techniques are commonly used to extend MNB and multinomial
models of text, providing both improved modeling precision and a means for
incorporating structure into the models. The use of mixtures enables the
modeling of multi-modal distributions, with accuracy increasing as a function
of the number of added components and the amount of available data to estimate
the components.

A basic type of mixture is the Finite Mixture Model (Pearson, 1894). This
models data as being generated by a normalized linear combination of $L$
component distributions, so that for each component $l$ a weight $p(l)$ and a
component-conditional distribution $p_{l}()$ is estimated. The component
weights are constrained $0\leq p(l)\leq 1$ and $\sum_{l}p(l)=1$. For example,
a finite mixture of multinomials takes the form:

$\displaystyle p(\bm{w})=\sum_{l}p(l)Z(\bm{w})\prod_{n}p_{l}(n)^{w_{n}}$ (4)

By replacing the component variable with the label variable in the MNB model
of Equation 1, supervised Bayes models can be viewed as mixture models with
known component probabilities $p(m|\bm{w}^{(i)})$ for each training document
(McCallum and Nigam, 1998; Novovicova and Malik, 2003; Nigam et al., 2006).
Commonly the components are unknown variables which are estimated in training
using approximate algorithms such as EM and optimization on held-out data.
Depending on the application and the type of mixture modeling, different
optimization algorithms and constraints on the parameters can be used to
simplify the estimation problem.

Multinomial models of text can be extended by adding mixtures over both
documents and words. Document-clustering mixtures treat documents as being
generated by a mixture, with each component corresponding to a prototypical
document. Word-clustering mixtures treat words similarly, with each component
corresponding to a prototypical word. The document-clustering components can
be called _themes_ , while word-clustering components can be called _topics_
(Keller and Bengio, 2004). Combination and extension of these two basic types
of mixture for text data result in the various mixture and topic models of
text.

The earliest proposed document-clustering mixture extension of MNB conditions
the label variables on the components (Kontkanen et al., 1996; Monti and
Cooper, 1999). In this use the mixture components cluster the training data
into soft partitions:

$\displaystyle
p(\bm{w},l)=\sum_{m}p(m)p_{m}(l)Z(\bm{w})\prod_{n}p_{ml}(n)^{w_{n}}$ (5)

Replacing each conditional multinomial $p_{l}(\bm{w})$ in MNB by a finite
mixture of $M$ multinomial components produces the more common Multinomial
Mixture Bayes Model (Monti and Cooper, 1999; Novovicova and Malik, 2003; Nigam
et al., 2006):

$\displaystyle
p(\bm{w},l)=p(l)\sum_{m}p_{l}(m)Z(\bm{w})\prod_{n}p_{lm}(n)^{w_{n}}$ (6)

Word-clustering mixtures are used in topic models and multi-label mixture
models (Li and Yamanishi, 1997; Hofmann, 1999; Li and Yamanishi, 2000; Blei et
al., 2003; McCallum, 1999; Ueda and Saito, 2002a). A basic model of this type
extends the multinomial:

$\displaystyle p(\bm{w})=Z(\bm{w})\prod_{n}(\sum_{m}p(m)p_{m}(n))^{w_{n}}$ (7)

The earliest proposed topic model of this form (Li and Yamanishi, 1997)
replaced the multinomial in MNB, using hard clustering of words to form shared
components $p_{m}(n)$, with separate distributions $p_{l}(m)$. A related model
called the Stochastic Topic Model (Li and Yamanishi, 2000) used this type of
modeling without label variables, performing inference using the components
directly for topic segmentation and analysis. Multi-label classification
models use this type of topic model as well, but learn the components from
multi-label data. The Multi-label Mixture Model (McCallum, 1999) uses Equation
7, but performs inference by greedily adding label components $l$ and
estimates $p_{l}(m)$ for each document, using a prior $p(\bm{c})$ over the
labelsets $\bm{c}=[1,...,l,...,L]$ instead of labels. Parametric Mixture Model
(Ueda and Saito, 2002a) is similar, but uses a uniform distributions for
$p_{l}(m)$ and the labelset prior $p(\bm{c})$. Further multi-label mixture
models have built on these two models (Ueda and Saito, 2002b; Kaneda et al.,
2004; Sato and Nakagawa, 2007; Wang et al., 2008; Ramage et al., 2009).

Probabilistic topic models became more widely known with Probabilistic Latent
Semantic Analysis (Hofmann, 1999). This uses a unique label variable for each
document, so that the joint probability becomes:

$\displaystyle p(\bm{w},l)\propto
p(l)\prod_{n}(\sum_{m}p_{l}(m)p_{m}(n))^{w_{n}}$ (8)

Although popular, the Probabilistic Latent Semantic Analysis model is not a
fully generative model of documents (Blei et al., 2003; Keller and Bengio,
2004), since it does not generate new document variables $l$. The number of
components $M$ needs to be optimized, and $L$ is tied to the number of
training set documents. Thus the model is not very scalable and is prone to
overfitting (Blei et al., 2003). To address these issues, a model called
Latent Dirichlet Allocation (Blei et al., 2003; Minka and Lafferty, 2002) was
proposed by replacing the document variables in Probabilistic Latent Semantic
Analysis with a Dirichlet distribution $p(\bm{\omega})$ of the component
weights $p(m|\bm{\omega})=\omega_{m}$:

$\displaystyle p(\bm{w})=\int
p(\bm{\omega}|\bm{\tau})Z(\bm{w})\prod_{n}(\sum_{m}p(m|\bm{\omega})p_{m}(n))^{w_{n}}d\bm{\omega},$
(9)

where $p(\bm{\omega}|\bm{\tau})$ is modeled by a Dirichlet distribution, given
by:

$\displaystyle
p(\bm{\omega}|\bm{\tau})\propto\frac{\Gamma(\sum_{m}\tau_{m})}{\prod_{m}\Gamma(\tau_{m})}\prod_{m}\omega^{\tau_{m}}_{m},$
(10)

where $\bm{\tau}$ are the parameters for the Dirichlet distribution and
$\Gamma$ is the gamma function.

The integration over possible component weight vectors has no closed form
solution, and must be approximated using algorithms such as variational Bayes,
Gibbs sampling, and expectation propagation (Minka and Lafferty, 2002;
Asuncion et al., 2009). The Latent Dirichlet Allocation model proved
exceptionally popular and turned probabilistic topic modeling into an active
field of research (Griffiths and Steyvers, 2004; Blei and Lafferty, 2006; Li
and McCallum, 2006; Asuncion et al., 2009; Blei, 2012).

A substantial literature exists on various models based on Latent Dirichlet
Allocation. One conceptually useful model is the Theme Topic Mixture Model
(Keller and Bengio, 2004). This presents a discretized version of Latent
Dirichlet Allocation that does not require approximate inference. The
Dirichlet over component weights is replaced by a document-clustering mixture:

$\displaystyle
p(\bm{w})=\sum_{l}p(l)Z(\bm{w})\prod_{n}(\sum_{m}p_{l}(m)p_{m}(n))^{w_{n}}$
(11)

Theme Topic Mixture Model presents a direct combination of the document
clustering and word clustering finite mixture models. Combinations and
extensions of these two types of mixture modeling are used throughout text
mining applications, both with multinomial models and distributions other than
the multinomial.

####  2 N-grams and Hidden Markov Models

The multinomial model of text considers words within documents to be
distributed independent of their context. Consequently all phrase- and
sentence-level information present in the documents is left unmodeled. This
sequence information is crucial for many applications of generative models of
text, including machine translation, speech recognition, optical character
recognition and text compression. Even in tasks where multinomial text models
are considered sufficient, sequence modeling has been shown to be beneficial
(Song and Croft, 1999; Miller et al., 1999; Peng and Schuurmans, 2003;
Medlock, 2006). Incorporating sequence information is most commonly done using
higher order sequential models called n-grams, also known as Markov chain
models. These models originate from the early days of computer science, and
aside from the many practical uses they have been instrumental in the
development of computer science and information theory (Shannon, 1948;
Chomsky, 1956; Markov, 1971).

An n-gram model generalizes the multinomial model to take the preceding
sequence of $M-1$ words into account, where $M$ is the order of the n-gram.
Each _history_ of preceding $M-1$ words models a separate categorical. The
models of the first three orders are commonly called unigram, bigram and
trigram models, corresponding to zeroth, first and second order Markov chain
models, respectively. Over the last decades higher order models such as
4-grams and 5-grams have become standard, with the availability of web-scale
text datasets and the development of computer processors and memory. A full
n-gram model of order $M$ and vocabulary size of $N$ requires $N^{M}$
parameters, i.e. counts, for the $N^{M-1}$ categorical distributions. Due to
the Zipf-law distribution of text data, the models will be extremely sparse,
and only a fraction of these counts will be seen in any amount of training
data. For these reasons the main foci in n-gram research have been efficiency
of implementation (Siivola et al., 2007; Brants et al., 2007; Watanabe et al.,
2009; Pauls and Klein, 2011) and methods for smoothing high order n-grams with
lower order estimates (Jelinek and Mercer, 1980; Ney et al., 1994; Chen and
Goodman, 1996, 1999; Goodman, 2000; Huang and Renals, 2010; Schütze, 2011).

Let $\underline{\bm{w}}$ denote any word sequence that corresponds to the
counts in the word vector $\bm{w}$: $w_{n}=\sum_{j:\underline{w}_{j}=n}1$. Let
$\underline{w}_{j-M+1}...\underline{w}_{j}$ denote a subsequence of $M$ words
ending at word $j$. The history or context of an n-gram is the sequence
$\underline{w}_{j-M+1}...\underline{w}_{j-1}$ of preceding $M-1$ words, a
sequence of 0 words in the unigram case $M=1$. The probability of a word
sequence is given by:

$\displaystyle p(\underline{\bm{w}})$
$\displaystyle=\prod_{j}p_{M}(w_{j}|j,\underline{\bm{w}})$
$\displaystyle=\prod_{j}p_{M}(w_{j}|\underline{w}_{1}...\underline{w}_{j-1})$
Markov chain
$\displaystyle=\prod_{j}p_{M}(w_{j}|\underline{w}_{j-M+1}...\underline{w}_{j-1})$
finite history (12)

The probabilities for the first $M-1$ n-grams are undefined, since their
histories would span over the word sequence boundaries. To correct this, the
sequence can be “padded” by adding start symbols “<s>” at the beginning of the
sequence. Sequence end symbols “</s>” can be added, and both of these improve
modeling accuracy at the boundaries.

There is a considerable literature on methods for smoothing the n-gram
language models. Virtually all of these interpolate n-grams hierarchically
with lower order n-grams (Chen and Goodman, 1999). Let $p_{m}()$ denote the
smoothed $m$-th order model in the hierarchy and $p_{m}^{u}()$ denote the
unsmoothed model of the same order. The interpolation smoothed n-gram
probabilities can be expressed as:

$\displaystyle p_{m}(w_{j}|\underline{w}_{j-m+1}...\underline{w}_{j-1})=$
$\displaystyle(1-\alpha_{m})p_{m}^{u}(\underline{w}_{j}|\underline{w}_{j-m+1}...\underline{w}_{j-1})$
$\displaystyle+\alpha_{m}\>p_{m-1}(\underline{w}_{j}|\underline{w}_{j-m+2}...\underline{w}_{j-1}),$
(13)

where $\alpha_{m}$ are backoff weights for order $m$ chosen by the smoothing
method. With Jelinek-Mercer smoothing (Jelinek and Mercer, 1980; Chen and
Goodman, 1999), $\alpha_{m}$ are simply fixed parameters estimated on held-out
data.

Often a uniform zerogram model is included to end the recursion. Without a
zerogram, the different n-grams in hierarchical interpolation methods form a
hierarchy of smoothing with $M$ levels. The smoothing weights can be expanded:

$\displaystyle p(\underline{\bm{w}})$
$\displaystyle=\prod_{j}p_{M}(\underline{w}_{j}|\underline{w}_{j-M+1}...\underline{w}_{j-1})$
$\displaystyle=\prod_{j}\sum_{m}p(m)p^{u}_{m}(\underline{w}_{j}|\underline{w}_{j-m+1}...\underline{w}_{j-1})$
$\displaystyle=\prod_{j}\sum_{m}(\prod_{m^{\prime}=m+1}^{M}\alpha_{m^{\prime}}-\prod_{m^{\prime}=m}^{M}\alpha_{m^{\prime}})p^{u}_{m}(\underline{w}_{j}|\underline{w}_{j-m+1}...\underline{w}_{j-1}),$
(14)

In this form it is seen that n-gram smoothing methods utilize a word-level
mixture, generating each word in a sequence as a finite mixture model of the
different order models. Hierarchical smoothing means that the mixture
component weights are generated dynamically as a product of the higher order
back-off weights:
$p(m)=\prod_{m^{\prime}=m+1}^{M}\alpha_{m^{\prime}}-\prod_{m^{\prime}=m}^{M}\alpha_{m^{\prime}}$
(Bell et al., 1989). Writing a word-clustering mixture of Equation 7 in the
sequence form shows a further surprising connection:

$\displaystyle p(\underline{\bm{w}})$
$\displaystyle=\prod_{j}\sum_{m}p(m)p_{m}(\underline{w}_{j})$ (15)

Comparing the word-clustering mixture in this form to the expanded n-gram
model of Equation 14, we can note the similarity between topic models and
hierarchically smoothed n-grams. Both models generate words as a mixture of
components. In topic modeling the components correspond to topics, and weights
are generated by the chosen topic modeling method. In n-gram modeling the
components correspond to the n-gram smoothing hierarchy, and weights are
generated dynamically by the chosen smoothing method.

Unlike mixture models, n-gram models have no hidden (unknown) variables in
estimation and are efficiently estimated by normalizing the known count
statistics. Extending n-grams with hidden variables leads to a more powerful
class of models called Hidden Markov Models (HMM) (Baum and Petrie, 1966;
Rabiner, 1989; Bilmes, 1998; Miller et al., 1999). A categorical HMM considers
text to be generated as categorical outputs of a hidden Markov chain model, so
that only the outputs $\underline{w}_{j}$ of the Markov chain are seen. A HMM
can be seen as an extension of a mixture model, so that the weights of each
component become dependent on the history of the last $M-1$ components that
generated an output. In HMM terminology the outputs are called emissions or
observations, and the hidden variables are called states. In text modeling the
outputs are commonly words, and the hidden variables are structural variables
such as parts of speech, named entities, sections, topics and authors that are
to be discovered using the HMM.

Due to the abundance of applications for HMMs, a number of variants exist that
can be mentioned. Arc-emission HMMs output a variable on each transition to a
state, whereas state-emission HMMs have the output variables attached to the
states. Historically HMMs were defined more commonly as arc-emission HMMs,
rather than state-emission HMMs. These two types of HMMs are equivalent, in
the sense that either can be transformed to the other. In many applications
the output distributions are Gaussian or mixture models, instead of
categoricals. Epsilon or $\epsilon$-states can be used, that have no attached
output distribution. HMMs of this type are called $\epsilon$-transition HMMs
and are more powerful in the distributions that can be represented, since
$\epsilon$-states can be used to model complex sequences of hidden variables
behind each output. But these also pose problems for inference, since each
output word can be generated by arbitrarily long loops of
$\epsilon$-transitions.

Let $\underline{\bm{k}}$ denote a hidden state sequence of states $m$
corresponding to a word sequence $\underline{\bm{w}}$. Let $M$ be the number
of hidden states, $p_{\underline{k}_{j}}(\underline{w}_{j})$ the categorical
output distribution of state ${\underline{k}_{j}}$, and
$p({\underline{k}_{j}}|\underline{k}_{j-1})$ the transition probability to
state $\underline{k}_{j}$ given the previous state $\underline{k}_{j-1}$. A
first-order categorical state-emission HMM without $\epsilon$-transitions
produces the joint probabilities:

$\displaystyle p(\underline{\bm{w}},\underline{\bm{k}})$
$\displaystyle=\prod_{j}p(\underline{k}_{j}|\underline{k}_{j-1})p_{\underline{k}_{j}}(\underline{w}_{j}),$
(16)

where the hidden $p(\underline{k}_{1}|\underline{k}_{0})=p(\underline{k}_{1})$
is provided by a categorical distribution $p(\underline{k}_{1})$ for the
initial states $\underline{k}_{1}$. Alternatively, the sequence can be padded
with boundary symbols the same way as with n-gram models.

####  3 Directed Graphical Models

MNB and the discussed extensions can be described in the general framework of
graphical models (Pearl, 1986; Lauritzen and Spiegelhalter, 1988; Loeliger,
2004; Frey and Jojic, 2005; Klinger and Tomanek, 2007; Parikh and Drezde,
2007; Sutton and McCallum, 2007) as generative directed graphical models. A
graphical model is a model of a joint distribution of variables that
factorizes according to an underlying graph. Commonly this is an _independency
graph_ that encodes the independence assumptions of the model. Nodes in an
independency graph represent the variables, and lack of an edge between two
variables indicates an independence assumption. Since computation is only
required for related variables, factorizing a joint distribution according to
the assumptions greatly simplifies modeling. Algorithms developed for the
estimation and inference of graphical models are applicable to new types of
models, reducing the time required for research and development, while the
graphical representation reduces the time required for presentation of new
models.

$\bm{w}$$l$ (a) Multinomial Naive Bayes

$\bm{w}$$l$ (b) Logistic Regression

Figure 1: Independency graphs for a Multinomial Naive Bayes and Logistic
Regression models. Multinomial Naive Bayes is a directed graphical model,
Logistic Regression is an undirected graphical model

The various types of graphical models use different factorizations and
graphical notations. Traditionally, graphical models come from two types,
called Bayesian Networks (Pearl, 1986) and Markov Random Fields (Kindermann
and Snell, 1980). Both types visualize the variable nodes in the graph with a
circle, and encode the independence assumptions in a model by omissions of
edges. Both represent the assumptions using an independency graph $G=(V,E)$ of
variable nodes $V$ and edges $E$. Bayesian Networks are called _directed
graphical models_ , as the edges, depicted as arrows, encode a directional
conditionality of variables. Markov Random Fields are called _undirected
graphical models_ , and the undirected edges imply dependency, but not
directionality. The two types of models are different in the distributions
they can represent and the used algorithms. MNB forms a basic directed
graphical model, while LR is a corresponding undirected graphical model.
Figure 1 shows a comparison of MNB and LR using elementary independency graph
notation, with the word vector $\bm{w}$ and label variables $l$ forming the
variable nodes $\bm{x}$ of the graph.

Graphical models factorize a joint distribution $p(\bm{x})$ to $T$ factors
$\Psi_{t}$: $p(\bm{x})=\prod_{t}\Psi_{t}(\text{nd}(t))$, where $\text{nd}(t)$
is the subset of the variable nodes $x_{t}$ connected to factor $\Psi_{t}$.
The factors for undirected graphical models are also called cliques, and are
constrained to be arbitrary non-negative functions $\Psi_{t}\geq 0$, where
$\Psi_{0}=Z=1/\sum\Psi_{t=1}^{T}(\text{nd}(t))$ is an additional normalization
factor, also called the partition function. The factors for a directed
graphical model are conditional probability distributions of the form
$\Psi_{t}(\text{nd}(t))=p(x_{t}|\text{nd}(t))$ for each node $t$, with the
special case $\text{nd}(t)=\emptyset$ producing marginal probability
distributions $p(x_{t})$. No additional normalization factor is required for
directed graphs, as the conditional distributions are normalized
probabilities. Since the factors for directed graphs are defined for each node
$t$, the factorization can be read directly from the graph, whereas the clique
factors for undirected graphs are visualized less directly by the independency
graph notation.

The notation for graphical models is ongoing constant evolution, and
additional notation has been introduced (Minka and Winn, 2008; Dietz, 2010;
Andres et al., 2012). Usually shaded nodes represent known variables, and
clear nodes represent hidden ones. Additional plate notation is standard for
repeating parts in graphical models, such as repeated segments in variable
sequences. This represents “unrolling” of the graph, so that the segment is
repeated a certain number of times. Nevertheless, in practice the plate
notation is inconvenient for representing dependencies in sequences.
Visualizations of sequence graphical models depict repeated fragments of the
models instead (Murphy, 2002; Deviren et al., 2004, 2005; Frey and Jojic,
2005; Wiggers and Rothkrantz, 2006; Sutton and McCallum, 2007; Parikh and
Drezde, 2007; Klinger and Tomanek, 2007), sometimes indicating the repetition
by use of ellipses, or combining the fragment notation with the plate notation
(Wang et al., 2007).

$\bm{w}$$l$

$\underline{w}_{j}$$l$$j=1..J$

$\underline{w}_{j}$$l$$j=1..J$$J$

$\underline{w}_{j}$$l$$j=1..J$$J$$i=1..I$

Figure 2: Independency graph notations for illustrating MNB, with an
increasing degree of explicitness from left to right. The label variable $l$
is considered known for estimation on training data and unknown for inference
on test data. Edge from variable $J$ to the plate indicates the plate is
unrolled $J$ times

As an example of a directed graphical model, we can first take the MNB
$p(l,\bm{w})=\Psi_{1}(l)\Psi_{2}(l,\bm{w})$. In this case the factors are
categoricals $\Psi_{1}(l)=p(l)$ and multinomials
$\Psi_{2}(l,\bm{w})=p_{l}(\bm{w})$. An equivalent definition can be done using
sequence variables and graph unrolling. In this case
$p(l,\bm{\underline{w}})=\prod_{t}\Psi_{t}(\text{nd}(t))$, where
$\Psi_{1}(l)=p(l)$ is categorical and
$\Psi_{t+1}(l,\underline{w}_{t})=p_{l}(\underline{w}_{t})$ for $2\leq t\leq
J+1$ are categorical draws from the multinomial, corresponding to the unrolled
variables. Figure 2 shows directed independency graph notations for MNB, with
varying degrees of explicitness.

$\underline{w}_{j}$$l$$j=1..J$ (a) Document mixture

$\underline{w}_{j}$$\underline{k}_{j}$$j=1..J$ (b) Word mixture

$\underline{w}_{j}$$\underline{k}_{j}$$l$$j=1..J$ (c) Theme-topic mixture

Figure 3: Comparison of the basic mixture model extensions of multinomials
using directed independency graph notation

Graphical model notations are most useful for expressing an overview of a
statistical model, compared to similar models. The mixture models discussed in
this section are compared Figure 3. When some properties of the model are not
crucial for presenting the main modeling ideas, they can be omitted from the
illustration. For example, the models discussed in this chapter all share
common modeling ideas, such as the use of categorical distributions and
assumption of IID data. Inclusion of these types of properties in the
visualization would cause the graphical notations to be less accessible.

$\underline{w}_{j}$$\underline{w}_{j-m}$$m=1..M$$j=1..J$ (a) N-gram

$\underline{w}_{j}$$\underline{k}_{j}$$\underline{k}_{j-m}$$m=1..M$$j=1..J$
(b) HMM

$\underline{w}_{j}$$\underline{w}_{j-m}$$\underline{k}_{j}$$\underline{k}_{j-m}$$m=1..M$$j=1..J$
(c) DBN1

$\underline{w}_{j}$$\underline{w}_{j-m}$$\underline{k}_{j}$$\underline{k^{\prime}}_{j}$$\underline{k}_{j+m^{\prime}}$$m=1..M$$m^{\prime}=1..M^{\prime}$$j=1..J$
(d) DBN2

Figure 4: Comparison of the sequence model extensions of multinomials using
directed graphical model notation. N-gram and HMM are $M$-order models. DBN1
combines the n-gram and HMM. DBN2 is a highly connected example of a DBN, with
a second hidden variable type $\underline{m^{\prime}}_{j}$, and
$\underline{w}_{j}$ conditioning $M^{\prime}$ future hidden variables
$\underline{k}_{j+m^{\prime}}$.

The use of unrolled Bayes Networks for sequence modeling has been called
Dynamic Bayes Network models (DBN) (Deviren et al., 2004, 2005; Wiggers and
Rothkrantz, 2006). Graph unrolling enables describing sequence models such as
topic models, HMMs, and n-grams in the notation of directed graphical models.
Topic variables, HMM hidden states and n-gram order interpolation weights can
be described as variables in the graph. For example, a categorical HMM can be
expressed as
$p(\underline{\bm{w}},\underline{\bm{k}})=\prod_{t}\Psi(\text{nd}(t))$, where
$\Psi_{t}(\text{nd}(t))=p_{\underline{k}_{t}}(\underline{w}_{t})$ for $1\leq
t\leq J$ and
$\Psi_{t}(\text{nd}(t))=p(\underline{k}_{t\%M}|\underline{k}_{t\%M-1})$ for
$J+1\leq t\leq(J+1)M$, where $M$ is the number of HMM hidden states $m$.

DBNs extend this graphical model view of HMMs, so that a number of hidden
variables can underlie an observed word output, instead of a single hidden
state variable. For example, a model of text can have topic variables, dialog
types, word history, word clusters, parts of speech etc. as the hidden
variables (Deviren et al., 2004, 2005; Wiggers and Rothkrantz, 2006).
Including some of these variable types can considerably improve over simple
n-gram models of text. Interpolated n-gram models can be included in DBNs by
linking to each word the different n-gram order nodes, and an interpolation
variable node that outputs the n-gram order mixture weights. With DBNs any
conceivable variables can be used to condition the sequence variables, as long
as the conditioning does not form cycles in the graph. Figure 4 shows a
comparison of the sequence model extensions of multinomials.

####  4 Factor Graphs and Gates

Graphical models using both directed and undirected edges include chain graphs
(Frydenberg, 1990) and ancestral graph Markov models (Richardson and Spirtes,
2002). More recently, factor graphs (Kschischang et al., 2001; Frey, 2003;
Loeliger, 2004; Frey and Jojic, 2005; Lazic et al., 2013) has been proposed as
a superset of the earlier frameworks. The original formalism itself has been
followed by a number of extensions (Loeliger, 2004; Frey, 2003; Minka and
Winn, 2008; McCallum et al., 2009; Dietz, 2010; Andres et al., 2012), such as
directed factors (Frey, 2003; Dietz, 2010), gates (Frey, 2003; Minka and Winn,
2008; Dietz, 2010; Oberhoff et al., 2011) and factor templates (McCallum et
al., 2009).

$\bm{w}$$p(\bm{w}|l)$$l$$p(l)$ Figure 5: Multinomial Naive Bayes illustrated
using factor graph notation, with the factors
$p(l,\bm{w})=\Psi_{1}(l)\Psi_{2}(l,\bm{w})$

The factor graph notation visualizes any graphical model using a graph
$G=(V,F,E)$ of variable nodes $V$, factor nodes $F$ and edges $E$. The graph
is bipartite, so that each edge connects a variable node to a factor node. The
variable nodes are visualized using circles, the factor nodes using small
squares and the edges using lines. Figure 5 shows MNB as a factor graph.
Factor graphs are a strict superset of undirected and directed graphical
models, since both types of models can be represented as factor graphs, while
many factor graphs cannot be represented by either types of models (Frey,
2003).

Gates are a proposed extension of factor graph notation that allows more
explicit visualization of mixture models and context-dependent models (Minka
and Winn, 2008; Winn, 2012). Gates notation uses a gate or switch function
(Frey, 2003) to select the behaviour of a sub-graph based on a key variable,
such as a mixture model component indicator. For example, labels for MNB can
be written as a vector of variables $\bm{c}$: $\forall l:0\leq c_{l}\leq 1$,
and $\sum_{l}c_{l}=1$. The joint distribution for MNB can then be rewritten as
a gate:

$\displaystyle p(\bm{w},\bm{c})=\prod_{l}(p(\bm{w},l))^{c_{l}}$ (17)

The label indicator variables $c_{l}$ in Equation 17 performs the role of a
switch, changing the output of the gate to $1$ for all labels $l$ with key
value $c_{l}=0$. The gate formalism enables expression of factor graphs where
more general functions are used for the key variables, such as context-
dependent variables. For a given key value, only the parts of the gated sub-
graph with key value $c_{l}>0$ need to be computed.

$\bm{w}$$p(\bm{w}|l)$$l$$p(l)$ (a) Gates

$\bm{w}$$p(\bm{w}|l=1)$$p(l=1)$$p(\bm{w}|l=2)$$p(l=2)$$l$$l=1$$l=2$ (b)
Expanded gates, for a model with L=2

Figure 6: Multinomial Naive Bayes illustrated using gated factor graph
notation, with the gate $p(\bm{w},\bm{c})=\prod_{l}(p(\bm{w},l))^{c_{l}}$ for
factors $p(l,\bm{w})=\Psi_{1}(l)\Psi_{2}(l,\bm{w})$

Gates are visualized using dashed rectangles, either as a single rectangle
similar to a plate, or in an expanded form with separate rectangles for the
different values of the key. The latter is useful in complex cases, when the
key values result in different types of computations within the gate. The key
variable is shown connected to the gate rectangle by a line. Figure 6 shows
gated factor graphs for MNB with gates and expanded gates. The gate notation
is unnecessary for simple models such as MNB, but becomes useful for
illustrating inference in more complex graphical models, as will be shown in
Chapter 5 of the thesis.

####  5 Inference and Estimation with Directed Generative Models

##### Overview of Algorithms

Directed generative models commonly have efficient algorithms for both
inference and estimation. MNB has linear time and space complexity algorithms
for both, as do constrained extensions of multinomials such as n-grams.
Mixture extensions generally complicate the estimation, and multiply the
inference complexities by the number of components in each mixture. Dynamic
programming (Bellman, 1952; Viterbi, 1967) is an algorithmic innovation that
can be used to reduce the complexities for HMM and DBN extensions. Latent
Dirichlet Allocation and some of the more complex directed graphical models
require other approximate algorithms for both inference and estimation, such
as Variational Bayes and Gibbs Sampling (Asuncion et al., 2009; Blei, 2012).

The joint $p(\bm{w},l)$ for MNB is computed by the product
$p(l)\prod_{n}p_{l}(n)^{w_{n}}$ over the prior and the label conditionals, and
the naive inference algorithm for this is a trivial product over the terms.
Inferring the marginal $p(\bm{w})$ from the joint and posterior $p(l|\bm{w})$
with the Bayes rule can be done with the closed form operations of sums and
products. The naive inference time and space complexities for the MNB
posterior $p(l|\bm{w})$ is $O(|\bm{w}|_{0}L)$ (Manning et al., 2008).
Document-clustering mixtures introduce sums over documents, and word-
clustering mixtures introduce sums over words; both multiply the space and
time complexities of inference by the number of components $J$. Replacing the
multinomial in MNB with a HMM introduces a sum over all possible hidden state
sequences. This can be reduced using dynamic programming techniques. Inference
on more complex directed graphical models can require other algorithms, such
as the approximate algorithms for Latent Dirichlet Allocation (Asuncion et
al., 2009; Blei, 2012).

MNB is estimated by gathering and normalizing the sufficient statistics of
counts. When sparsity is utilized, this has the time complexity
$O(\sum_{i}|\bm{w}^{(i)}|_{0})$ and space complexity
$O(L+\sum_{l}\sum_{n:\exp(\lambda_{ln})>0}1)$. Extension with mixtures
complicates the estimation, due to a sum in the likelihood function that does
not decompose into separate optimizations. A common practical solution to this
problem is the EM algorithm based on dynamic programming. This treats the
mixture components as random variables, iteratively optimizing the expected
conditional log-likelihood until a stationary point of the likelihood function
is reached. As with inference, more complex graphical model extensions can
require approximations such as Variational Bayes and Gibbs Sampling. Aside
from parameter estimation, sometimes the graphical model structure itself is
unknown and learned using a variety of approximate methods (Friedman et al.,
1997; Lazic et al., 2013).

Additional meta-optimization in estimation is commonly required, to choose the
meta-parameters required by the models, and to avoid bad local minima of the
EM-estimated likelihood function. Meta-parameters required by the models can
include the number of components in the mixtures and smoothing parameters.
Basic solutions for setting these are heuristic values and grid searches.
Local minima are encountered with complex multimodal likelihood functions,
such as those for mixture models. A basic solution is random restarts for
lowering the probability of a low quality local optima. Chapter 6 of the
thesis describes a Gaussian random search algorithm that can be used to solve
the meta-optimization problem in a principled manner.

##### Dynamic Programming

Dynamic programming (Bellman, 1952) is an algorithmic innovation that can be
used to solve problems with overlapping subproblems efficiently. The
application of dynamic programming makes HMMs practical, by lowering the
complexity of the required computations. These are next described in brief for
the case of a first-order categorical HMM. The probability of a word sequence
$\underline{\bm{w}}$ for the HMM of Equation 16 can be marginalized:

$\displaystyle p(\underline{\bm{w}})$
$\displaystyle=\sum_{\underline{\bm{k}}}\prod_{j}p(\underline{k}_{j}|\underline{k}_{j-1})p_{\underline{k}_{j}}(\underline{w}_{j})$
(18)

Marginalizing $p(\underline{\bm{w}})$ by summation over the possible state
sequences is not usually feasible, as there are $M^{J}$ possible state
sequences. Computing this observation state probability efficiently is
considered the first of the three main computational problems with HMMs
(Rabiner, 1989). The second problem is optimizing
$\operatornamewithlimits{argmax}_{\underline{\bm{k}}}p(\underline{\bm{k}}|\underline{\bm{w}})$,
used for segmenting data to the hidden state sequences. The third problem is
estimating the model, given that the hidden states are unknown in training
data.

The summation over the state sequences $\sum_{\underline{\bm{k}}}$ in
computing $p(\underline{\bm{w}})$ can be considered a brute-force solution to
the problem. A dynamic programming solution is computing the probabilities
$p(\underline{\bm{w}})$ over the sequence indices $j$ instead, summing for
each possible state $m$ the probability of all sequences leading to the state,
called the forward probability $\xi_{j}(m)$. This is known as the forward
algorithm. Using the forward variables, the marginal probability for the HMM
can be rewritten in a recursive form:

$\displaystyle p(\underline{\bm{w}})$
$\displaystyle=\sum_{\underline{\bm{k}}}\prod_{j}p(\underline{k}_{j}|\underline{k}_{j-1})p_{\underline{k}_{j}}(\underline{w}_{j})$
$\displaystyle=\sum_{m}\xi_{J}(m)$ $\displaystyle\xi_{j}(m)$
$\displaystyle=\begin{cases}p(m)p_{m}(\underline{w}_{j}),&\text{if $j=1$}\\\
\sum_{m^{\prime}}(\xi_{j-1}(m^{\prime})p(m|m^{\prime}))p_{m}(\underline{w}_{j}),&\text{otherwise},\\\
\end{cases}$ (19)

where $p(m)=p(\underline{k}_{j})$ and
$p_{m}(\underline{w}_{j})=p_{\underline{k}_{j}}(\underline{w}_{j})$.

The forward algorithm solves $p(\underline{\bm{w}})$ recursively by computing
$\xi_{j}(m)$ from $j=1$ to $j=J$, reducing the time complexity from
$O(JM^{J})$ to $O(JM^{2})$. The space complexity is also reduced to $O(2K)$,
since only the forward variables for the current and previous sequence index
need to be kept in memory. Alternatively, the algorithm can be run in the
reverse order. This is called the backward algorithm and it produces exactly
the same results. These algorithms can be extended to virtually all types of
HMMs. The zeroth order HMM can be shown to be a special case, requiring only
$O(JM)$:

$\displaystyle p(\underline{\bm{w}})$ $\displaystyle=\sum_{m}\xi_{J}(m)$
$\displaystyle=\sum_{m}\sum_{m^{\prime}}((\xi_{J-1}(m^{\prime})p(m))p_{m}(\underline{w}_{J}))$
$\displaystyle=\sum_{m^{\prime}}(\xi_{J-1}(m^{\prime}))\sum_{m}(p(m)p_{m}(\underline{w}_{J}))$
$\displaystyle=\prod_{j}\sum_{m}p(m)p_{m}(\underline{w}_{j}))$ (20)

Related dynamic programming algorithms are used for solving the other two
problems with HMMs. Changing the sum over $m$ in Equation 20 to a max returns
the probability of the word sequence by the single most likely sequence of
states, solving the second problem. This is known as the Viterbi algorithm
(Viterbi, 1967) and its efficient implementations underlie many of the
applications of HMMs into sequence classification. Lastly, the forward and
backward algorithms can be combined to compute the posterior probabilities
$p(\underline{k}_{j}|\bm{\underline{w}})$ of each state $\underline{k}_{j}$
for each sequence index $j$. This is known as the forward-backward algorithm,
and the posteriors can be used for the Expectation step in EM estimation (Baum
et al., 1970; Rabiner, 1989; Bilmes, 1998).

In case a directed graphical model has no cycles of edges, efficient exact
dynamic programming inference is possible using extensions of the forward,
Viterbi and forward-backward algorithms to general graphs (Pearl, 1986;
Kschischang et al., 2001; Loeliger, 2004). For more complex graphical models a
variety of less efficient exact and approximate inference algorithms exist.
Most of these build on the idea of variable elimination (Zhang and Poole,
1994), that works by marginalizing variables away to arrive at the inferred
probability distribution. The generalized case of forward algorithm to graphs
is the sum-product algorithm or belief propagation. Analogously the
generalized case of Viterbi algorithm is the max-product algorithm. These
extend the use of the forward and maximum variables $\xi_{j}(m)$, so that a
message variable is computed for each node in the graph and the inference is
done by passing the messages in an efficient order.

##### Expectation Maximization

The training data for the HMM of Equation 16 consists of instances
$D^{(i)}=(\underline{\bm{w}}^{(i)},\underline{\bm{k}}^{(i)})$ of known and
hidden variables, where $\underline{\bm{w}}^{(i)}$ is the known sequence and
$\underline{\bm{k}}^{(i)}$ is unknown variables for the $i$-th instance of
training data. The likelihood function becomes:

$\displaystyle\mathcal{L}(\bm{\theta}|D)$ $\displaystyle=p(D|{\bm{\theta}})$
$\displaystyle=\prod_{i}\sum_{\underline{\bm{k}}^{(i)}}p(\underline{\bm{w}}^{(i)},\underline{\bm{k}}^{(i)}|\bm{\theta})$
$\displaystyle=\prod_{i}\sum_{\underline{\bm{k}}^{(i)}}\prod_{j}(p(\underline{k}_{j}^{(i)}|\underline{k}_{(j-1)}^{(i)},\bm{\theta})\>p_{\underline{k}_{j}^{(i)}}(\underline{w}^{(i)}_{j}|\bm{\theta}))$
(21)

The summation over components causes a problem for optimizing the log-
likelihood of the model, since the log-likelihood no longer factorizes into
parts that can be separately optimized. If the hidden states were known and
each word was generated by a single component, the log-likelihood function
would factorize easily. In this case the likelihood function is:

$\displaystyle\mathcal{L}(\bm{\theta}|D)$
$\displaystyle=\prod_{i}p(\underline{\bm{w}}^{(i)},\underline{\bm{k}}^{(i)}|\bm{\theta})$
$\displaystyle=\prod_{i}\prod_{j}(p(\underline{k}_{j}^{(i)}|\underline{k}_{(j-1)}^{(i)},\bm{\theta})\>p_{\underline{k}_{j}^{(i)}}(\underline{w}^{(i)}_{j}|\bm{\theta}))$
(22)

In most cases the hidden states are not known. With mixture models and HMMs
the main solution to this problem is using the EM algorithm to estimate the
model. Instead of attempting to maximize the log-likelihood, the EM algorithm
treats the components as random variables and iteratively optimizes the
conditional expectation of the log-likelihood
$Q(\bm{\theta}|D,\bm{\hat{\theta}})$. Let
$p(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})$
indicate the expectation of a hidden variable sequence
$\underline{\bm{k}}^{(i)}$ for word sequence $\underline{\bm{w}}^{(i)}$
according to some prior parameters $\bm{\hat{\theta}}$:
$p(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})=p(\underline{\bm{k}}^{(i)},\underline{\bm{w}}^{(i)}|\bm{\hat{\theta}})/\sum_{\underline{\bm{k}}^{(i)}}p(\underline{\bm{k}}^{(i)},\underline{\bm{w}}^{(i)}|\bm{\hat{\theta}})$
The Q-function becomes:

$\displaystyle Q(\bm{\theta}|D,\bm{\hat{\theta}})$
$\displaystyle=E(\log(\mathcal{L}(\bm{\theta}|D,\bm{\hat{\theta}})))$
$\displaystyle=\sum_{i}\sum_{\underline{\bm{k}}^{(i)}}{p(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})}\log(p(\underline{\bm{w}}^{(i)},\underline{\bm{k}}^{(i)}|\bm{\theta}))$
$\displaystyle=\sum_{i}\sum_{\underline{\bm{k}}^{(i)}}\sum_{j}p(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})\log(p(\underline{k}_{j}^{(i)}|\underline{k}_{(j-1)}^{(i)},\bm{\theta})\>p_{\underline{k}_{j}^{(i)}}(\underline{w}^{(i)}_{j}|\bm{\theta})))$
(23)

Since $p(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})$
is treated as a random variable, $Q(\bm{\theta}|D,\bm{\hat{\theta}})$ becomes
a random variable as well. With random variables the sum of expectations
equals the expectation of the sum, so that for computing
$\mathcal{L}(\bm{\theta}|D,\bm{\hat{\theta}}))$ the expectation can be pushed
inside the sums, placing the expectation
$p(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})$ as a
weight for each possible hidden state sequence. Let $\bm{\lambda}_{m}$
indicate the conditional parameters for component $m$, $\bm{\lambda}$ the
conditional parameters for all components and $\bm{\alpha}$ the parameters for
component weights. The conditional log-likelihood can be optimized:

$\displaystyle\operatornamewithlimits{argmax}_{\bm{\theta}}(Q(\bm{\theta}|D,\bm{\hat{\theta}}))$
$\displaystyle=\operatornamewithlimits{argmax}_{(\bm{\lambda},\bm{\alpha})}(\sum_{i}\sum_{\underline{\bm{k}}^{(i)}}\sum_{j}p(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})\log(p(\underline{k}_{j}^{(i)}|\underline{k}_{(j-1)}^{(i)},\bm{\alpha})\>p_{\underline{k}_{j}^{(i)}}(\underline{w}^{(i)}_{j}|\bm{\lambda})))$
$\displaystyle=\operatornamewithlimits{argmax}_{(\bm{\lambda},\bm{\alpha})}(\sum_{i}\sum_{\underline{\bm{k}}^{(i)}}\sum_{j}p(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})\log(p(\underline{k}_{j}^{(i)}|\underline{k}_{(j-1)}^{(i)},\bm{\alpha}))$
$\displaystyle+\sum_{i}\sum_{\underline{\bm{k}}^{(i)}}\sum_{j}p(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})\log(p_{\underline{k}_{j}^{(i)}}(\underline{w}^{(i)}_{j}|\bm{\lambda})))$
(24)

Replacing the current set of parameters $\bm{\hat{\theta}}$ with the estimated
parameters
$\bm{\hat{\theta}}^{\prime}=\operatornamewithlimits{argmax}_{\bm{\theta}}(Q(\bm{\theta}|D,\bm{\hat{\theta}}))$
and repeating the optimization until
$Q(\bm{\theta}|D,\bm{\hat{\theta}})=Q(\bm{\theta}|D,\bm{\hat{\theta}}^{\prime})$
produces the EM-estimated stationary point of the likelihood function.
Depending on the likelihood function and initialization, the stationary point
can remain far from a global optimum, and EM is often repeated with randomly
sampled initial parameters. Other practical variants include online versions
of EM (Liang and Klein, 2009) and combination with genetic algorithms
(Martínez and Virtriá, 2000; Pernkopf and Bouchaffra, 2005; Puurula and
Compernolle, 2010).

For more scalable algorithmic implementation, EM is implemented using the
forward-backward variables
$p(\underline{k}^{(i)}_{j}|\bm{\underline{w}^{(i)}},\bm{\hat{\theta}})$
instead of the state sequence variables
$p(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})$.
Summing these weighted posterior probabilities produces expected counts
$E(C())$ in place of the counts $C()$ used in Equation 3. Using the forward-
backward algorithm, the posteriors can be computed in the same time complexity
as the forward algorithm, but require $O(JM)$ in space complexity, as the full
$JM$ matrix needs to be stored for estimating with the weights.

##  Chapter 7 Reformalizing Multinomial Naive Bayes

This chapter presents a thorough reformalization of Multinomial Naive Bayes
(MNB) as a probabilistic model. The issue of smoothing is first discussed,
noting that most of the multinomial smoothing methods necessary for MNB are
not correctly formalized under maximum likelihood estimation. A unifying
framework for the methods is proposed, and a two-state Hidden Markov Model
(HMM) formalization is shown to derive the smoothed parameter estimates.
Feature weighting is formalized for both estimation and inference as well-
defined approximation with expected log-probabilities, given probabilistically
weighted word sequences. A formalization of MNB is defined that takes these
corrections into account, followed by a more general graphical model extension
that includes label-conditional document length modeling, and scaling the
influence of label priors.

###  1 Formalizing Smoothing

####  1 Smoothing Methods for Multinomials

The sparsity of text data causes problems for maximum likelihood estimation of
multinomials. Words occurring zero times for a label will cause the
corresponding parameter estimates to be zero as well, resulting in
0-probabilities when computing the probabilities with _unsmoothed models_
$p_{l}^{u}(\bm{w}|\bm{\lambda}^{u})$. This complication is known as the zero-
frequency problem in statistics, and smoothing methods for solving this
problem have been extensively researched. However, the _smoothed models_
$p_{l}(\bm{w}|\bm{\lambda})$ are no longer justified by maximum likelihood,
and only a subset of the smoothing methods can be formalized under other
principles, such as maximum a posteriori (MacKay and Peto, 1995; Rennie,
2001). This section proposes a unified framework for smoothing generative
models of text, and shows that practically all of the smoothing methods for
multinomials can be formalized as approximate maximum likelihood estimation on
a constrained Hidden Markov Model (HMM).

An early solution to the zero-frequency problem dates two centuries and is
known as Laplace correction (Laplace, 1814). On discussing the probability of
the sun rising tomorrow, Laplace argued that despite the event of the sun not
rising has never been seen, it should still have a probability assigned to it.
The proposed Laplace correction adds a single count to each possible event,
thereby avoiding the zero frequency problem. In language modeling this
correction is known as Laplace smoothing, and a parametric generalization
adding a fractional count $\mu$ instead was proposed by Lidstone in 1920
(Lidstone, 1920). By further multiplying the added count by a prior background
model $p^{u}(n)$, this correction becomes the Dirichlet prior method for
smoothing.

Maximum a posteriori estimation of multinomials with a Dirichlet prior takes
the form:

$\displaystyle\lambda_{ln}=\log(\frac{C(l,n)+\mu\>p^{u}(n)}{\sum_{n^{\prime}}C(l,n^{\prime})+\mu\>p^{u}(n^{\prime})}),$
(1)

where the special case $p^{u}(n)=1/N$ is Lidstone smoothing and
$p^{u}(n)=1/N$, $\mu=N$ is Laplace correction (Rennie, 2001; Smucker and
Allan, 2007).

Another basic way to avoid the zero-frequency problem is to linearly
interpolate parameter estimates with a background model. This is known as
Jelinek-Mercer smoothing (Jelinek and Mercer, 1980), and takes the form:

$\displaystyle\lambda_{ln}=\log((1-\beta)\frac{C(l,n)}{\sum_{n^{\prime}}C(l,n^{\prime})}+\beta\>p^{u}(n))$
(2)

Dirichlet prior and Jelinek-Mercer differ only in how the weight for the
background model is chosen. A general interpolation function covers both types
of smoothing (Johnson, 1932; Smucker and Allan, 2007):

$\displaystyle\lambda_{ln}=\log((1-\alpha_{l})p^{u}_{l}(n)+\alpha_{l}p^{u}(n)),$
(3)

where $p^{u}_{l}(n)$ is the unsmoothed label-conditional multinomial for label
$l$. Fixing $\alpha_{l}$ to a pre-determined value $\alpha_{l}=\beta$ produces
Jelinek-Mercer smoothing. Fixing
$\alpha_{l}=\frac{\mu}{\mu+\sum_{n}C(l,n)}=1-\frac{\sum_{n}C(l,n)}{\mu+\sum_{n}C(l,n)}$
produces Dirichlet prior smoothing. Combining these as
$\alpha_{l}=1-\frac{\sum_{n}(C(l,n)-\beta C(l,n))}{\mu+\sum_{n}C(l,n)}$
results in two-stage smoothing, a smoothing method suggested for information
retrieval (Zhai and Lafferty, 2001a; Smucker and Allan, 2007).

The background model is commonly a uniform distribution
$p^{u}(n)=\frac{1}{N}$, or a label-independent collection model
$p^{u}(n)=\frac{\sum_{l}C(l,n)}{\sum_{n^{\prime}}\sum_{l}C(l,n^{\prime})}$. A
uniform-smoothed collection model with smoothing weight $\Upsilon$
interpolates between a uniform and a collection model:
$p^{u}(n)=(1-\Upsilon)\frac{\sum_{l}C(l,n)}{\sum_{n^{\prime}}\sum_{l}C(l,n^{\prime})}+\Upsilon\frac{1}{N}$.
In n-gram language modeling literature the uniform background model is called
the zerogram, and the collection model is called the unigram background model
(Chen and Goodman, 1999). Alternatively, if several documents per label exist,
the counts from each document can be normalized by length, or weighted
according to usefulness. External datasets can likewise be used to estimate
the background model, such as large text datasets of the same language. The
choice of background model can also be motivated by the task, such as using a
collection model to introduce relevance information in ranked retrieval (Zhai
and Lafferty, 2001a).

Jelinek-Mercer and Dirichlet prior are the two most common types of smoothing
for MNB models. One view of smoothing is that smoothing methods discount seen
occurrences of words in order to redistribute the subtracted probability mass
$a_{l}$ to the background model. Under this view both of these discount the
seen counts linearly by $\alpha_{l}$. A third basic type of smoothing is
called is called absolute discounting (Ney et al., 1994; Chen and Goodman,
1996, 1999; Zhai and Lafferty, 2001b, 2004). This works similar to Jelinek-
Mercer smoothing, but subtracts a parameter value $\delta:0\leq\delta\leq 1$
from all counts for a label, and uses the subtracted probability mass for
choosing the smoothing coefficient. The discounted counts can be denoted
$C^{\prime}(l,n)=C(l,n)-\delta$. Using Equation 3 and choosing
$p^{u}_{l}(n)=\frac{C^{\prime}(l,n)}{\sum_{n^{\prime}}C^{\prime}(l,n^{\prime})}$,
and $\alpha_{l}=1-\frac{\sum_{n}C^{\prime}(l,n)}{\sum_{n}C(l,n)}$ produces
absolute discounting.

A problem with absolute discounting is that usually separate discount values
are optimal for different counts, with higher discounts for higher counts (Ney
et al., 1994). Empirical analyses (Chen and Goodman, 1999; Durrett and Klein,
2011; Schütze, 2011; Neubig, 2012) have shown that optimal discount values
seem to follow a power-law distribution, rather than the constant ones in
absolute discounting. A recent improvement over absolute discounting is power-
law discounting (Momtazi and Klakow, 2010; Momtazi, 2010; Huang and Renals,
2010). This method discounts according to a power function
$C^{\prime}(l,n)=C(l,n)-\delta C(l,n)^{\delta}$, with $0\leq\delta\leq 1$.
Combining this with a Dirichlet prior and reorganizing terms produces Pitman-
Yor smoothing, with $p^{u}_{l}(n)=\frac{C(l,n)-\delta
C(l,n)^{\delta}}{\sum_{n^{\prime}}(C(l,n^{\prime})-\delta
C(l,n^{\prime})^{\delta})}$ and $\alpha_{l}=1-\frac{\sum_{n}(C(l,n)-\delta
C(l,n)^{\delta})}{\mu+\sum_{n}C(l,n)}$, that approximates inference on a
Pitman-Yor process (Momtazi and Klakow, 2010; Momtazi, 2010; Huang and Renals,
2010).

Table 1: Smoothing methods used with MNB models. Parameter estimation formulas for smoothing weights $\alpha_{l}$ and unsmoothed multinomials $p^{u}_{l}(n)$. Smoothing method | Smoothing weight $\alpha_{l}$ | Multinomial $p_{l}^{u}(n)$
---|---|---
Jelinek-Mercer | $\beta$ | $\frac{C(l,n)}{\sum_{n^{\prime}}C(l,n^{\prime})}$
Dirichlet prior | $1-\frac{\sum_{n}C(l,n)}{\mu+\sum_{n}C(l,n)}$ | $\frac{C(l,n)}{\sum_{n^{\prime}}C(l,n^{\prime})}$
Two-stage smoothing | $1-\frac{\sum_{n}(C(l,n)-\beta C(l,n))}{\mu+\sum_{n}C(l,n)}$ | $\frac{C(l,n)}{\sum_{n^{\prime}}C(l,n^{\prime})}$
Absolute discounting | $1-\frac{\sum_{n}(C(l,n)-\delta)}{\sum_{n}C(l,n)}$ | $\frac{C(l,n)-\delta}{\sum_{n^{\prime}}(C(l,n^{\prime})-\delta)}$
Power-law discounting | $1-\frac{\sum_{n}(C(l,n)-\delta C(l,n)^{\delta})}{\sum_{n}C(l,n)}$ | $\frac{C(l,n)-\delta C(l,n)^{\delta}}{\sum_{n^{\prime}}(C(l,n^{\prime})-\delta C(l,n^{\prime})^{\delta})}$
Pitman-Yor approx. | $1-\frac{\sum_{n}(C(l,n)-\delta C(l,n)^{\delta})}{\mu+\sum_{n}C(l,n)}$ | $\frac{C(l,n)-\delta C(l,n)^{\delta}}{\sum_{n^{\prime}}(C(l,n^{\prime})-\delta C(l,n^{\prime})^{\delta})}$
Generalized smoothing | $1-\frac{\sum_{n}(C(l,n)-D(l,n))}{\mu+\sum_{n}C(l,n)}$ | $\frac{C(l,n)-D(l,n)}{\sum_{n^{\prime}}(C(l,n^{\prime})-D(l,n^{\prime}))}$

The discussed smoothing methods can be covered by a general function that is
called here generalized smoothing. By choosing
$\alpha_{l}=1-\frac{\sum_{n}(C(l,n)-D(l,n))}{\mu+\sum_{n}C(l,n)}$ and
$p^{u}_{l}(n)=\frac{C(l,n)-D(l,n)}{\sum_{n^{\prime}}(C(l,n^{\prime})-D(l,n^{\prime}))}$,
and $D(l,n)$ according to the chosen discounting, we recover all of the
smoothing methods as special cases of Equation 3. Generalized smoothing with
$\mu=0$ and $D(l,n)=\beta C(l,n)$ implements Jelinek-Mercer smoothing as
linear discounting, $D(l,n)=C(l,n)-\delta$ implements absolute discounting and
$D(l,n)=\delta C(l,n)^{\delta}$ implements power-law discounting. A
discounting function combining Jelinek-Mercer and power-law discounting can be
defined as: $D(l,n)=\delta C(l,n)^{\delta}+\beta C^{\prime}(l,n)$, where
$C^{\prime}(l,n)=C(l,n)-\delta C(l,n)^{\delta}$. Chapter 6 of the thesis
experiments with this combined discounting function. Table 1 summarizes the
smoothing methods in terms of smoothing weights $a_{l}$ and unsmoothed
multinomials $p^{u}_{l}(n)$.

The parameters can be chosen to maximize the likelihood of held-out data, or a
performance measure related to the task. Closed form approximations requiring
no held-out data are possible for some parameters. The discounting parameter
$\delta$ for absolute and power-law discounting can be approximated using a
leave-one-out likelihood estimate (Ney et al., 1994). Denoting the frequency
of 1-counts as $n_{1}=\sum_{n:(\sum_{l}C(l,n))=1}1$ and 2-counts as
$n_{2}=\sum_{n:(\sum_{l}C(l,n))=2}1$, the discount parameters can be
approximated as $\delta=n_{1}/(n_{1}+2n_{2})$ (Ney et al., 1994; Chen and
Goodman, 1999; Huang and Renals, 2010; Zhang and Chiang, 2014). This Kneser-
Ney estimate provides an approximate upper bound of the optimal discount
value, and has been demonstrated to work well in practice (Chen and Goodman,
1999; Goodman, 2000; Vilar et al., 2004; Zhang and Chiang, 2014).

The smoothing methods for multinomial text models can be extended into the
smoothing methods used for higher-order n-gram language models. A substantial
literature exists for advanced n-gram smoothing techniques (Chen and Goodman,
1999; Rosenfeld, 2000). These extend the multinomial smoothing techniques
hierarchically, by placing the lower-order $m-1$ n-gram as the background
model for each order $m$. For example, Witten-Bell smoothing (Moffat, 1990) is
hierarchical linear interpolation with a nonparametric estimate for the
interpolation weights (Chen and Goodman, 1999). Using the label-conditional
model as a higher order model and the background distribution as a lower-order
model, the Witten-Bell estimate for the smoothing weight is
$\alpha_{l}=1-\frac{\sum_{n}C(l,n)}{\sum_{n:C(l,n)>0}1+\sum_{n}C(l,n)}$. We
can note that Witten-Bell smoothing is a case of Dirichlet prior smoothing
with a heuristic estimate for the Dirichlet parameter:
$\mu_{l}=\sum_{n:C(l,n)>0}1=\sum_{n}\min(1,C(l,n))$. Witten-Bell smoothing
originates from text compression modelling, where linearly interpolated n-gram
models are known as Prediction by Partial Matching (PPM) models (Cleary and
Witten, 1984). The Witten-Bell smoothed PPM is known as PPM-C and has been a
baseline for text compression for over two decades. In general applications of
n-grams more effective smoothing methods can be applied.

Interpolated Kneser-Ney smoothing (Chen and Goodman, 1999; James, 2000;
Goodman, 2000; Siivola and Pellom, 2005; Goldwater et al., 2006; Teh, 2006;
Heafield et al., 2013) has been the standard LM smoothing method for n-grams
for over a decade. This combines n-grams hierarchically using absolute
discounting, but replaces the lower order $m<M$ estimates of counts by the
number of contexts the count occurs in (Kneser and Ney, 1995). For a
multinomial, the modified background model becomes
$p^{u}(n)=\frac{\sum_{l:C(l,n)>0}1}{\sum_{n^{\prime}}\sum_{l:C(l,n^{\prime})>0}1}$.
A common example for this method is the phrase “San Francisco”. A unigram-
model estimate for “Francisco” could be very high, but since the unigram is
likely to occur in only this one context, the bigram Kneser-Ney estimate for
this lower-order n-gram count would likely be 1. The modified model would
correctly consider the unigram “Francisco” as very unlikely to occur outside
this context. All but the highest-order unsmoothed models are replaced by the
modified counts before discounting, providing a considerable improvement in
modeling precision (Chen and Goodman, 1999; James, 2000).

Some improvements over interpolated Kneser-Ney have been suggested over the
years, with limited acceptance. Modified Kneser-Ney smoothing (Chen and
Goodman, 1999; Siivola and Pellom, 2005; Heafield et al., 2013; Zhang and
Chiang, 2014) replaces the discount for each order with three different
discounts for counts 1, 2 and 3+, optimized together on held-out data for
perplexity (Chen and Goodman, 1999; Siivola and Pellom, 2005). For both
interpolated and modified Kneser-Ney, the discount parameters can be estimated
on held-out data, or approximated with heuristics such as the discussed
discount estimate $\delta=n_{1}/(n_{1}+2n_{2})$. Power-law discounting LM
(Huang and Renals, 2010) replaces the absolute discounting in interpolated
Kneser-Ney with Pitman-Yor Process smoothing.

Smoothing the parameter estimates directly as in Equation 3 would cause zero-
value parameters to become non-zeros, resulting in loss of the parameter
sparsity. The parameter estimates $p^{u}_{l}(n)=\lambda_{ln}^{u}$ and
$p^{u}(n)=\lambda_{n}^{u}$ are often kept separate, so that the complexity of
storing $p_{l}(n)$ is not increased. The space complexity of estimation for a
smoothed MNB model is $O(L+N+\sum_{l}|\bm{\lambda}_{l}^{u}|_{0})$ and the time
complexity is $O(\sum_{i}|\bm{w}^{(i)}|_{0})$.

####  2 Formalizing Smoothing with Two-State Hidden Markov Models

Parameter interpolation is the standard formalization of parameter smoothing
for multinomial and n-gram language models (Jelinek and Mercer, 1980; Chen and
Goodman, 1996, 1999; Zhai and Lafferty, 2001b, 2004; Smucker and Allan, 2007).
Although parameter interpolation provides a principled method for estimating
multinomial parameters, the estimated parameters are not strictly speaking
maximum likelihood estimates of the multinomial model, but rather ad-hoc
estimates (Hiemstra et al., 2004). The parameter interpolation introduced in
Equation 3 and Table 1 shows that all smoothing methods can be expressed as a
normalized mixture of an unsmoothed multinomial and a background distribution.
This analysis is extended next by showing that the smoothing methods can be
formulated as maximum expected log-likelihood estimation on a constrained
generative model. The proof proceeds by showing that the interpolated
parameters used in the smoothed multinomials can be implemented by a
categorical HMM, and that constraining the HMM appropriately in parameter
estimation reproduces a model with the same joint probabilities as the
smoothed multinomial. Compared to formalization of smoothing methods as
approximate inference on a Pitman-Yor process and other Bayesian models
(MacKay and Peto, 1995; Teh, 2006; Goldwater et al., 2006; Neubig, 2012), the
proposed HMM formalization has the advantage that inference using the
estimated models is exact.

An early formulation of smoothed document models for IR used a two-state HMM
for formalizing Jelinek-Mercer smoothing (Miller et al., 1999). This model
used a HMM with one hidden state for the document distribution and one for
collection smoothing (Miller et al., 1999; Xu and Weischedel, 2000). In
addition, this work showed how to integrate bigram models, feature weighting,
translation models and relevance feedback using the HMM model. However, the
parameter estimation for this model was not well defined, the model was
considered to be very different and unrelated to multinomial LMs, and model
smoothing was limited to Jelinek-Mercer smoothing. The connection to LMs was
discovered shortly afterwards (Hiemstra, 2001), as was the need to use
constraints such as parameter tying and fixed parameters for the formalization
(Hiemstra, 2001). Using parameter tying, Jelinek-Mercer smoothed higher-order
LMs could be implemented as HMMs (Manning and Schütze, 1999). Despite
considerable interest at the time, the two-state HMM model never became
popular in IR, nor was its connection to LM smoothing methods explored. We
show in the following that this model can be used to formalize all of the
discussed smoothing methods in the maximum likelihood framework.

Let $l$ be a label variable indicating one of the $L$ multinomials sharing a
background model. Let $\underline{\bm{w}}$ be any sequence of $J$ words, and
$\underline{w}_{j}:1\leq\underline{w}_{j}\leq N$ correspond to the words
counted in $\bm{w}$, so that $w_{n}=\sum_{j:\underline{w}_{j}=n}1$. Let
$\underline{\bm{k}}$ be an unknown sequence of $M=2$ hidden states
$\underline{k}_{j}:1\leq\underline{k}_{j}\leq M$ generating the sequence
$\underline{\bm{w}}$. A probability model over the joint probabilities
$(l,\underline{\bm{w}},\underline{\bm{k}})$ can be defined:

$\displaystyle p(l,\underline{\bm{w}},\underline{\bm{k}})$
$\displaystyle=p(l)\prod_{j}p_{l}(\underline{k}_{j})p^{u}_{l\underline{k}_{j}}(\underline{w}_{j}),$
(4)

where $p_{l}(\underline{k}_{j})$ is a categorical and
$p^{u}_{l\underline{k}_{j}}(\underline{w}_{j})$ is a categorical conditional
on the label $l$ and the hidden state $\underline{k}_{j}$.

$\underline{w}_{j}$$\underline{k}_{j}$$l$$j=1..J$$i=1..I$ Figure 1: Graphical
model for the two-state HMM. The hidden variables $\underline{k}_{j}$ for
smoothing components are unknown and the context label variables $l$ are known
in estimation

The model of Equation 4 is a special case of a 0th order categorical HMM,
where $p(l)$ correspond to initial state probabilities,
$p_{l}(\underline{k}_{j})$ to HMM state transition probabilities, and
$p^{u}_{l\underline{k}_{j}}(\underline{w}_{j})$ to state emission
probabilities. Transitions between the label-conditional states are not
allowed, so that each word sequence is produced by a single label. Figure 1
shows the graphical model for the two-state HMM.

The conditional probabilities $p_{l}(\bm{w})$ for the model can be derived:

$\displaystyle p_{l}(\bm{w})$
$\displaystyle=Z(\bm{w})\sum_{\underline{\bm{k}}}\prod_{j}p_{l}(\underline{k}_{j})p^{u}_{l\underline{k}_{j}}(\underline{w}_{j})$
$\displaystyle=Z(\bm{w})\prod_{j}\sum_{m}(p_{l}(m)p^{u}_{lm}(\underline{w}_{j}))$
$\displaystyle=Z(\bm{w})\prod_{n}(\sum_{m}p_{l}(m)p^{u}_{lm}(n))^{w_{n}},$ (5)

where $p_{l}(m)=p_{l}(\underline{k}_{j})$,
$p^{u}_{lm}(n)=p^{u}_{l\underline{k}_{j}}(\underline{w}_{j})$, and $Z(\bm{w})$
is the multinomial normalizer.

The multinomial normalizer
$Z(\bm{w})=\frac{(\sum_{n}w_{n})!}{\prod_{n}w_{n}!}$ accounts for the fact
that a count vector $\bm{w}$ can be generated by the number $Z(\bm{w})$ of
permutations of the sequence $\underline{\bm{w}}$. As discussed in Chapter 3,
computing the product of sums $\prod_{j}\sum_{m}$ corresponds to the forward
algorithm, whereas computing the equivalent sum of products
$\sum_{\underline{\bm{k}}}\prod_{j}$ gives the brute-force solution to the
same problem (Rabiner, 1989).

The conditional probabilities
$p_{l}(\bm{w})=Z(\bm{w})\prod_{n}(\sum_{m}p_{l}(m)p^{u}_{lm}(n))^{w_{n}}$ can
be implemented by a multinomial
$p_{l}(\bm{w}|\bm{\lambda})=Z(\bm{w})\prod_{n}\exp(\lambda_{ln})^{w_{n}}$,
with parameter vector $\bm{\lambda}_{l}$:
$\lambda_{ln}=\log(\sum_{m}p_{l}(m)p^{u}_{lm}(n))$. From this form it can
readily be seen that all of the smoothing methods can be implemented with the
two-state HMM of Equation 4, by choosing $p^{u}_{lm=1}(n)=p^{u}_{l}(n)$,
$p^{u}_{lm=2}(n)=p^{u}(n)$, and $p_{l}(m=2)=\alpha_{l}$ as the smoothing
weight.

The training data for model of Equation 4 consists of documents
$D^{(i)}=(\underline{\bm{w}}^{(i)},l^{(i)},\underline{\bm{k}}^{(i)})$, where
$\underline{\bm{w}}^{(i)}$ are known word sequences, $l^{(i)}$ are label
indicators, and $\underline{\bm{k}}^{(i)}$ are unknown component assignments
for the $i$-th document of training data. The likelihood function becomes:

$\displaystyle\mathcal{L}(\bm{\theta}|D)$ $\displaystyle=p(D|{\bm{\theta}})$
$\displaystyle=\prod_{i}p(l^{(i)}|\bm{\theta})\sum_{\underline{\bm{k}}^{(i)}}p_{l^{(i)}}(\underline{\bm{w}}^{(i)},\underline{\bm{k}}^{(i)}|\bm{\theta})$
$\displaystyle=\prod_{i}p(l^{(i)}|\bm{\theta})\sum_{\underline{\bm{k}}^{(i)}}\prod_{j}p_{l^{(i)}}(\underline{k}_{j}^{(i)}|\bm{\theta})\>p^{u}_{l^{(i)}\underline{k}_{j}^{(i)}}(\underline{w}^{(i)}_{j}|\bm{\theta})$
$\displaystyle=\prod_{i}p(l^{(i)}|\bm{\theta})\prod_{j}\sum_{m}p_{l^{(i)}}(m|\bm{\theta})\>p^{u}_{l^{(i)}m}(\underline{w}^{(i)}_{j}|\bm{\theta})$
(6)

This is difficult to optimize, due to the sum within the product. Similarly to
the EM-algorithm, $\underline{\bm{k}}$ can be treated as random variables.
Given an initial distribution over component assignments
$p_{l^{(i)}}(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})$,
the conditional expectation of the log-likelihood becomes:

$\displaystyle Q(\bm{\theta}|D,\bm{\hat{\theta}})=$ $\displaystyle
E(\log(\mathcal{L}(\bm{\theta}|D,\bm{\hat{\theta}})))$
$\displaystyle=\sum_{i}\log(p(l^{(i)}|\bm{\theta}))+\sum_{\underline{\bm{k}}^{(i)}}{p_{l^{(i)}}(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})}\log(p_{l^{(i)}}(\underline{\bm{w}}^{(i)},\underline{\bm{k}}^{(i)}|\bm{\theta}))$
$\displaystyle=\sum_{i}\log(p(l^{(i)}|\bm{\theta}))$
$\displaystyle+\sum_{\underline{\bm{k}}^{(i)}}\sum_{j}p_{l^{(i)}}(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})\log(p_{l^{(i)}}(\underline{k}_{j}^{(i)}|\bm{\theta})\>p^{u}_{l^{(i)}\underline{k}_{j}^{(i)}}(\underline{w}^{(i)}_{j}|\bm{\theta}))$
(7)

Maximizing the conditional expected likelihood parameters for the unsmoothed
multinomial $p^{u}_{lm=1}(n)$, background model $p^{u}_{lm=2}(n)$, and weights
$p_{l}(m)$ decouples into separate optimizations, given the distribution over
component assignments
$p_{l^{(i)}}(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})$.
Let $\bm{\lambda}_{lm}=[\lambda_{l1},...,\lambda_{lN}]$ indicate the
conditional parameters for component $m$ of label $l$,
$\bm{\alpha}_{lm}=[a_{l1},...,a_{lM}]$ the parameters for component weights of
label $l$, and $\bm{\pi}=[\pi_{1},...,\pi_{L}]$ parameters for the label
priors. Let $\bm{\lambda}$ and $\bm{\alpha}$ indicate the combined parameters
for the label-conditionals and component weights. Given
$p_{l^{(i)}}(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})$,
the maximization decouples:

$\displaystyle\operatornamewithlimits{argmax}_{\bm{\theta}}(Q(\bm{\theta}|D,\bm{\hat{\theta}}))$
$\displaystyle=$
$\displaystyle\operatornamewithlimits{argmax}_{(\bm{\lambda},\bm{\alpha},\bm{\pi})}(\sum_{i}\log(p(l^{(i)}|\bm{\pi}))$
$\displaystyle+\sum_{i}\sum_{\underline{\bm{k}}^{(i)}}\sum_{j}p_{l^{(i)}}(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})\log(p_{l^{(i)}}(\underline{k}_{j}^{(i)}|\bm{\alpha})\>p^{u}_{l^{(i)}\underline{k}_{j}^{(i)}}(\underline{w}^{(i)}_{j}|\bm{\lambda}))$
$\displaystyle=$
$\displaystyle\operatornamewithlimits{argmax}_{(\bm{\lambda},\bm{\alpha},\bm{\pi})}(\sum_{i}\log(p(l^{(i)}|\bm{\pi}))$
$\displaystyle+\sum_{i}\sum_{\underline{\bm{k}}^{(i)}}\sum_{j}p_{l^{(i)}}(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})\log(p_{l^{(i)}}(\underline{k}_{j}^{(i)}|\bm{\alpha}))$
$\displaystyle+\sum_{i}\sum_{\underline{\bm{k}}^{(i)}}\sum_{j}p_{l^{(i)}}(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})\log(p^{u}_{l^{(i)}\underline{k}_{j}^{(i)}}(\underline{w}^{(i)}_{j}|\bm{\lambda})))$
(8)

The parameter estimates for the smoothing methods derive from different
assumed distributions
$p_{l^{(i)}}(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})$,
except the background model for some smoothing methods. Both discounting and
linear interpolation imply distributing the expected count mass from a label-
conditional model to a background model. Estimation of a shared background
model requires further tying of parameters, removing the label-conditional
dependency for the second component: $\forall l:p^{u}_{lm=2}(n)=p^{u}(n)$. The
label-conditional unsmoothed models $p^{u}_{lm=1}(n)$ and the shared
background model $p^{u}(n)$ become estimated from the count mass distributed
by
$p_{l^{(i)}}(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})$,
while the smoothing weight $p_{l}(m=2)$ equals the proportion of count mass
distributed to the background model for the label $l$.

Table 2: Two-state HMM parameter estimates with different assumptions for $p_{l^{(i)}}(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})$, with the unsmoothed label-conditional probabilities $p^{u}_{lm=1}(n)$, smoothing weights $p_{l}(m=2)$, and shared background model probabilities $p^{u}_{lm=2}(n)=p^{u}(n)$ $p_{l^{(i)}}(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})$ | $p^{u}_{lm=1}(n)$ | $p_{l}(m=2)$ | $p^{u}(n)$
---|---|---|---
Jelinek-Mercer | $\frac{C(l,n)}{\sum_{n^{\prime}}C(l,n^{\prime})}$ | $\beta$ | $\frac{\sum_{l^{\prime}}C(l^{\prime},n)}{\sum_{n^{\prime}}\sum_{l^{\prime}}C(l^{\prime},n^{\prime})}$
Absolute disc. | $\frac{C(l,n)-\delta}{\sum_{n^{\prime}}(C(l,n^{\prime})-\delta)}$ | $1-\frac{\sum_{n}(C(l,n)-\delta)}{\sum_{n}C(l,n)}$ | $\frac{\sum_{l:C(l,n)>0}1}{\sum_{n^{\prime}}\sum_{l:C(l,n^{\prime})>0}1}$
Power-law disc. | $\frac{C(l,n)-\delta C(l,n)^{\delta}}{\sum_{n^{\prime}}(C(l,n^{\prime})-\delta C(l,n^{\prime})^{\delta})}$ | $1-\frac{\sum_{n}(C(l,n)-\delta C(l,n)^{\delta})}{\sum_{n}C(l,n)}$ | $\frac{\sum_{l^{\prime}}\delta C(l^{\prime},n)^{\delta}}{\sum_{n^{\prime}}\sum_{l^{\prime}}\delta C(l^{\prime},n^{\prime})^{\delta}}$

For some common smoothing methods, the background model is correctly estimated
as derived from the two-state HMM formalization. Table 2 shows parameter
estimates, when
$p_{l^{(i)}}(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})$
distributes to form the parameter estimates for Jelinek-Mercer smoothing,
absolute discounting and power-law discounting. With Jelinek-Mercer, the
collection model estimates derive as the background model. With absolute
discounting and power-law discounting, the derived background model estimates
equal the modified background models (Kneser and Ney, 1995; Huang and Renals,
2010) proposed for these methods. These modified background models were
proposed to satisfy marginal constraints of interpolating a single background
model to label-conditional models, but are commonly used to form all $M-1$
order background models in hierarchical n-gram smoothing (Goodman, 2000; Zhang
and Chiang, 2014). According to the two-state HMM derivation, the models for
$M-2$ orders should be estimated from the expected count mass recursively
distributed from the higher order models, instead of observed counts (Goodman,
2000), or expected counts (Zhang and Chiang, 2014) of each order
independently.

Smoothing methods including a Dirichlet prior will result in untypical
background models, since a Dirichlet prior gives weight to the background
model in proportion of the sum of counts:
$\alpha_{l}=1-\frac{\sum_{n}C(l,n)}{\mu+\sum_{n}C(l,n)}$. This distributes the
residual count mass for estimating $p^{u}(n)$ unevenly, so that labels with
more accumulated counts contribute less to the background model:
$p^{u}(n)=\frac{\sum_{l}\alpha_{l}C(l,n)}{\sum_{n^{\prime}}\sum_{l}\alpha_{l}C(l,n^{\prime})}$.
Using a uniform background model will analogously imply untypical label-
conditional models. A uniform background model would distribute the same count
mass for each word type $n$ from the label-conditional models. Discounting a
fraction $\delta$ from the first observation of a word would result in a
uniform background model, as would discounting uniformly from each observation
of a word: $D(l,n)=\delta/\sum_{l^{\prime}}C(l^{\prime},n)$. A uniform
background model constrains the choices for the label-conditional and
smoothing weight. For example, if a single smoothing weight is used for all
labels, the weight will be upper bound by the proportion of discounted count
mass:
$p_{l}(m=2)\leq\operatornamewithlimits{argmin}_{n}(\sum_{l^{\prime}}D(l^{\prime},n))/(\sum_{l^{\prime}}C(l^{\prime},n))$.
Common practice chooses the background model as either a collection or uniform
distribution, regardless of the label-conditional models and smoothing
weights. Alternatively, the background model and the smoothing method
hyperparameters can be optimized together for a performance measure of the
task (Puurula, 2012b).

Maximizing the expected conditional likelihood corresponds to a single
iteration of the EM algorithm on the HMM. Full EM estimation of the parameters
would replace $\bm{\hat{\theta}}$ by $\bm{\theta}$, and iterate the
expectation step of computing
$p_{l^{(i)}}(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})$
and the maximization step of solving Equation 8 with the updated expectation
(Hiemstra et al., 2004). Nevertheless, the EM parameter estimates would not
necessarily reach a global optimum of the model likelihood (Baum et al., 1970;
Rabiner, 1989; Bilmes, 1998). The Q-function parameters estimates can be exact
maximum likelihood estimates in some cases, and exact closed form estimates
can exist for some sets of constraints. For example, if segmentations of words
into states $\underline{\bm{k}}^{(i)}$ are provided, the parameters are exact
maximum likelihood estimates. The case of linear interpolation with the
background model and smoothing parameters fixed has a closed form exact
maximum likelihood solution (Zhang and Xu, 2008).

The HMM framework for formalizing smoothed multinomials can be extended for
formalizing smoothing in more structured generative models. This involves
constraining the transitions according to the model (Miller et al., 1999;
Manning and Schütze, 1999; Hiemstra, 2001), but the approximate maximum
likelihood estimation remains the same. Due to tied parameters, the resulting
HMM topologies can become complicated, especially if the model structure and
parameter tying is complex. Visualizing the HMMs can be simplified by
presenting label-dependent parts of the HMM topology separately (Miller et
al., 1999) and illustrating fragments of the model (Manning and Schütze, 1999;
Hiemstra, 2001).

###  2 Extending MNB for Fractional Counts

####  1 TF-IDF and Feature Transforms with MNB

Parameter smoothing constitutes the primary means for correcting assumptions
in models for text such as MNB. In some fields of text mining this is seen as
sufficient. For example, in information retrieval the common view is that
collection smoothing performs the same task as Inverse Document Frequency
(IDF) weighting, and as such integration of IDF to LMs is not necessary (Zhai
and Lafferty, 2001a; Hiemstra et al., 2004; Zhai, 2008). This has been
challenged by both experimental results (Smucker and Allan, 2006; Momtazi et
al., 2010; Puurula, 2013) and analyses of IDF compared to collection smoothing
(Robertson, 2004). In text classification and clustering, MNB has been
combined with Term Frequency (TF) and IDF transforms (TF-IDF) (Rennie et al.,
2003; Kibriya et al., 2004; Pavlov et al., 2004; Frank and Bouckaert, 2006;
Puurula, 2012b).

Various versions of both IDF and TF-IDF have been proposed for text data
(Robertson and Jones, 1976; Salton and Buckley, 1988). TF-IDF functions
comprise three transforms: term count normalization, document length
normalization and document frequency weighting. The first two are commonly
performed with a combined function and form the TF-part of feature weighting.
Document frequency weighting is usually considered an independent factor, and
forms the IDF-part of TF-IDF. A combined TF-IDF feature transform is given by:

$w_{n}=\log(1+\frac{w^{\prime}_{n}}{|\bm{w}^{\prime}|_{0}})\log\frac{I}{I_{n}},$
(9)

where $\bm{w}^{\prime}$ is the original unweighted word vector, and $I_{n}$ is
the number of collection documents having the word $n$.

The choice of log1+ transform for TF normalization can be justified as a
correction to multinomials for better modeling the power-law distributions
seen in text data (Rennie et al., 2003). The use of “L0 norm” or the number of
non-zeros in the word vector is called unique length normalization, and has
been shown to be robust across datasets (Singhal et al., 1996). The IDF factor
$\log\frac{I}{I_{n}}$ is called Robertson-Walker IDF (Robertson, 2004), and
forms the most commonly used version of IDF.

A large number of variations exist for each of the three components and for
how they are combined. Term count normalization can be omitted, or use
stronger damping (Singhal et al., 1998). Length normalization can use L1 norm
or L2 norm, and can be applied before or after term count normalization.
Document frequency weighting by IDF can take a number of forms, one common
variant being Croft-Harper IDF (Croft and Harper, 1979), which downweights
common words more severely. Parameterized versions also exist, adding
versatility to the transforms (Lee, 2007). A generalized version of Equation 9
can be defined (Puurula, 2012b):

$w_{n}=\frac{\log(1+\frac{w^{\prime}_{n}}{|\bm{w}^{\prime}|_{0}^{\phi}})}{|\bm{w}|_{0}^{1-\phi}}\log(\max(1,\upsilon+\frac{I}{I_{n}})),$
(10)

where $\phi$ controls length scaling and $\upsilon$ IDF lifting. $\phi=1$
performs length normalization before term count normalization, $\phi=0$
performs it after. Values $0<\phi<1$ produce smooth combinations of term count
and length normalization, while $\phi>1$ and $\phi<0$ produce more extreme
normalizations. $\upsilon=0$ produces Robertson-Walker IDF, while
$\upsilon=-1$ produces unsmoothed Croft-Harper IDF. Values $\upsilon>1$
produce weaker IDF normalizations, while $\upsilon<-1$ produces stronger IDF
normalizations.

####  2 Methods for Fractional Counts with Multinomial Models

Transforming data is standard practice for correcting model assumptions in
statistical modeling. This enables the use of well-understood simple models
with complex data. Common transforms include flooring and ceiling values to
accepted bounds, binning, log transforms, and standard score normalization.
Feature transforms are less commonly used in text modeling since the models
are defined on count data, and most normalizations of count data would produce
fractional counts that are undefined for multinomial and categorical models
(Juan and Ney, 2002; Vilar et al., 2004; Tam and Schultz, 2008; Bisani and
Ney, 2008; Zhang and Chiang, 2014). This means that the common use of TF-IDF
with MNB produces models that are not well-defined in a probabilistic sense.
However, there are a few methods in common use that allow fractional counts in
restricted uses.

For inference uses, a method commonly used to weight words in ranking is the
Kullback-Leibler (KL) divergence (Zhai and Lafferty, 2001c). In ranking, KL-
divergence is mostly used to incorporate feedback information into test
documents, but it has also been used to integrate IDF weighting of words
(Smucker and Allan, 2006; Momtazi et al., 2010; Momtazi, 2010). In soft
classification it has been used to correct differences in scores caused by
varying document lengths (Craven et al., 2000; Schneider, 2005). KL-divergence
is a measure between two probability functions. For the case of two
multinomial distributions $p_{l}(\bm{w})$ and $p^{\prime}(\bm{w})$, the
negative KL-divergence is:

$\displaystyle-D(p_{l}(\bm{w})||p^{\prime}(\bm{w}))$
$\displaystyle=-\sum_{n}p^{\prime}(n)\log\frac{p^{\prime}(n)}{p_{l}(n)}$
$\displaystyle=\sum_{n}p^{\prime}(n)\log p_{l}(n)-\sum_{n}p^{\prime}(n)\log
p^{\prime}(n)$ (11)

The second term $-\sum_{n}p^{\prime}(n)\log p^{\prime}(n)$ is the entropy for
model $p^{\prime}(\bm{w})$. When KL-divergence is used for ranking or
posterior scoring, the model $p^{\prime}(\bm{w})$ is the test document or
query model, and its entropy can be omitted since it has constant effect on
each label model $p_{l}(\bm{w})$. If the model $p^{\prime}(\bm{w})$ is
estimated as the unsmoothed estimate
$p^{\prime}(\bm{w})=\frac{w_{n}}{\sum_{n}w_{n}}$ for a test document, then
scoring by negative KL-divergence gives rank-equivalent scores to the
posterior log-probabilities
$-D(p_{l}(\bm{w})||p^{\prime}(\bm{w}))\overset{rank}{=}\log(p(l))\sum_{n}w_{n}\log(p_{l}(n))$.

KL-divergence thus provides a framework for generalizing posterior inferences
$p(l|\bm{w})$ by replacing the counts for a test document by model parameters.
A common use is to incorporate pseudo-feedback information from the top ranked
labels to the document (Zhai and Lafferty, 2001c), in order to rerank the
document with the updated model. A more recent use is transforming features
(Smucker and Allan, 2006; Momtazi et al., 2010), so that parameters are
weighted and renormalized, according to a weighting such as Inverse Collection
Frequency (Smucker and Allan, 2006; Momtazi et al., 2010) or IDF (Momtazi et
al., 2010). For example, using IDF would replace the test document model as
$p^{\prime}(n)=Z\>w_{n}\>IDF(n)$, where $Z$ is a normalization term and
$IDF(n)$ the IDF-weight of word $n$. A problem with the KL-divergence
framework is that it is not probabilistic in a strict sense, since the KL-
divergence scores are not probabilities. In addition, it cannot be used to
incorporate feature transforms or normalizations in model estimation.

A fully probabilistic alternative to KL-divergence is to define a model that
directly uses feature weights. The query term weighting model has been
proposed (Momtazi, 2010) for weighting MNB conditional probabilities, so that
$p(\underline{\bm{w}}|l,\underline{\bm{r}})=Z_{\underline{\bm{r}}}\prod_{j}p_{l}(\underline{w}_{j})^{\underline{r}_{j}}$,
$Z_{\underline{\bm{r}}}$ is a document-dependent normalizer and
$\underline{r}_{j}$ is an arbitrary non-negative weight, for example
$\underline{r}_{j}=IDF(\underline{w}_{j})$. This can be seen as a log-linear
model (Darroch and Ratcliff, 1972), where the weights for each feature in the
sequence are fixed. The same method was demonstrated earlier for the two-state
categorical HMM models in IR, for the special case of weighting query
sections, without considering normalization (Miller et al., 1999). This method
presents a simple modification that provides well-defined posterior
probabilities for infererence. Like KL-divergence inference, this method
cannot be used for model estimation.

For model estimation, static model interpolation (Stolcke, 2002) enables
weighting of training data for n-gram LMs. This works identically to Jelinek-
Mercer method used for smoothing, but combines weighted components from
different training data sources. For example, using $K$ component datasets
with multinomial parameters $p_{k}(n)$ and weights $p(k)$, the interpolated
parameters would be $p(n)=\sum_{k}p(k)p_{k}(n)$. Basic linear interpolation
can be equally implemented by weighting and storing fractional counts from
each dataset. Details of the interpolation can vary, and some smoothing
heuristics such as the Kneser-Ney discounting estimate require integer count
information (Ney et al., 1994; Zhang and Chiang, 2014). In general this method
allows integration of fractional counts in estimation, while maintaining the
probabilistic framework.

####  3 Formalizing Feature Transforms and Fractional Counts with
Probabilistic Data

A method that enables transformed features for both estimation and inference
is the formalization of fractional counts as probabilistic data. Concurrent
research in estimation of n-grams for machine translation has formalized
fractional counts as expectations of counts, given a probability distribution
over possible word sequences (Zhang and Chiang, 2014). This method can be
extended for estimation and inference of generative models in a variety of
applications, as discussed next in detail.

A weight sequence
$\underline{\bm{r}}=[\underline{r}_{1},...,\underline{r}_{J}]$ matching a word
sequence $\underline{\bm{w}}$ can be interpreted as probabilities of words
occurring, similar to the distribution over hidden components provided by the
EM-algorithm. Each weight $\underline{r}_{j}$ indicates the probability of the
corresponding word $\underline{w}_{j}$ to have occurred in the data, so that
the weights define a distribution over possible word sequences. A possible
word sequence $\underline{\bm{\hat{w}}}$ given $\underline{\bm{w}}$ and
$\underline{\bm{r}}$ can be called a _realization_ , a special case being a
realization with no words $\underline{\bm{\hat{w}}}=\epsilon$. A sequence of
binary indicator variables $\underline{\bm{\hat{r}}}$ called an _occurrence
sequence_ indicates a draw from distribution defined by the weight variables
$\underline{\bm{r}}$. A realization can be generated by different occurrence
sequences, and the mapping can be denoted
$\underline{\bm{\hat{w}}}=d(\underline{\bm{\hat{r}}},\underline{\bm{w}})$.

Table 3: Statistics for a word sequence weighted by probabilities

j | $\underline{w}_{j}$ | $\underline{r}_{j}$
---|---|---
$1$ | $1$ | $0.7$
$2$ | $2$ | $0.8$
$3$ | $1$ | $0.9$
(a) Document word sequence $\underline{\bm{w}}$ with weights
$\underline{\bm{r}}$

$\underline{\bm{\hat{w}}}$ | $p(\underline{\bm{\hat{w}}})$
---|---
$\epsilon$ | $0.006$
$1$ | $0.068$
$2$ | $0.024$
$12$ | $0.056$
$11$ | $0.126$
$21$ | $0.216$
$121$ | $0.504$
(b) Realizations $\underline{\bm{\hat{w}}}$ and probabilities
$p(\underline{\bm{\hat{w}}})$

| $c=1$ | $c=2$ | $c>0$
---|---|---|---
$p(w_{1}=c)$ | $0.34$ | $0.63$ | $0.97$
$p(w_{2}=c)$ | $0.80$ | $0.00$ | $0.80$
$E(\sum_{n:w_{n}=c}1)$ | $1.14$ | $0.63$ |
(c) Probabilities of counts $p(w_{n}=c)$ and expectations of count frequencies
$E(\sum_{n:w_{n}=c}1)$

$E(w_{1})$ | $1.6$
---|---
$E(w_{2})$ | $0.8$
(d) Expected fractional counts $E(\bm{w}_{n})$

The probability of an occurrence sequence $\underline{\bm{\hat{r}}}$ can be
computed by multiplying the weights:
$p(\underline{\bm{\hat{r}}}|\underline{\bm{w}},\underline{\bm{r}})=\prod_{j}\underline{r}_{j}^{\underline{\hat{r}}_{j}}(1-\underline{r}_{j})^{|\underline{\hat{r}}_{j}-1|}$.
The probability of each realization $p(\underline{\bm{\hat{w}}})$ can be
computed by summing its occurrence sequences:
$p(\underline{\bm{\hat{w}}}|\underline{\bm{w}},\underline{\bm{r}})=\sum_{\underline{\bm{\hat{w}}}=d(\underline{\bm{\hat{r}}},\underline{\bm{w}})}p(\underline{\bm{\hat{r}}}|\underline{\bm{w}},\underline{\bm{r}})$.
Assuming the words occur independently, the probabilities of counts
$p(w_{n}=c)$ are distributed according to a Poisson-binomial distribution:
$p(w_{n}=c)=\sum_{j:\underline{w}_{j}=n}\underline{r}_{j}$. The expectations
of count frequencies $E(\sum_{n:w_{n}=c}1)$ can then be computed with a
recursive algorithm (Zhang and Chiang, 2014). Table 4(d) summarizes these
basic statistics that can be computed by treating weights for words as
probabilities.

The method proposed by Zhang and Chiang (2014) uses the expectations of count
frequencies $E(\sum_{n:w_{n}=c}1)$ in place of the $n_{1}$ and $n_{2}$
statistics for the Kneser-Ney estimate, and the expected counts $E(w_{n})$ in
place of the counts $w_{n}$. The resulting LMs maximize the expected
conditional likelihood given the distribution over realizations, similarly to
the two-state HMMs in Section 2. Let training data $D$ for a multinomial
distribution consist of word and weight sequences:
$D^{(i)}=(\underline{\bm{w}}^{(i)},\underline{\bm{r}}^{(i)})$. The expected
conditional log-likelihood can be written:

$\displaystyle Q(\bm{\theta}|D,\bm{\hat{\theta}})$
$\displaystyle=E(\log(\mathcal{L}(\bm{\theta}|D,\bm{\hat{\theta}})))$
$\displaystyle=\sum_{i}\sum_{\underline{\bm{\hat{w}}}^{(i)}}p(\underline{\bm{\hat{w}}}^{(i)}|\underline{\bm{w}}^{(i)},\underline{\bm{r}}^{(i)})\log(p(\underline{\bm{\hat{w}}}^{(i)}))$
$\displaystyle=\sum_{i}\sum_{\underline{\bm{\hat{w}}}^{(i)}}\sum_{\underline{\hat{w}}_{j}^{(i)}}p(\underline{\bm{\hat{w}}}^{(i)}|\underline{\bm{w}}^{(i)},\underline{\bm{r}}^{(i)})\log(p(\underline{\hat{w}}_{j}^{(i)}))$
$\displaystyle=\sum_{n}E(C(n)|D)\log(p(n))$ (12)

This method formalizes the use of fractional counts for estimation, but
contains one flaw. With higher order n-grams different realizations have
different word histories, since omission of a word causes an n-gram history to
skip a word. For example, with a realization $\underline{\bm{\hat{w}}}=[93]$
for a weighted word sequence $\underline{\bm{w}}=[92453]$, the subsequence
$[245]$ would not be realized, and an n-gram history for the last word
$\underline{w}_{5}=3$ in the sequence would have to start with
$\underline{w}_{1}=9$. Different realizations will yield different sets of
n-gram histories, and assuming fixed histories would become increasingly
incorrect with long word sequences and low weights $\underline{r}_{j}$.
Correct estimation should take the differing histories into account. The
method presented by Zhang and Chiang (2014) sidesteps this issue by allowing
weighting only at the level of sentences. Nevertheless, experimental
improvements are demonstrated from the expected Kneser-Ney smoothing (Zhang
and Chiang, 2014).

Probabilistic data can be applied equally for inference. The expectation of
log-probability $E(\log(p(\underline{\bm{w}})))$ equals the Q-function for a
single document:

$\displaystyle E(\log(p(\underline{\bm{w}})))$
$\displaystyle=\sum_{\underline{\bm{\hat{w}}}}p(\underline{\bm{\hat{w}}}|\underline{\bm{w}},\underline{\bm{r}})\log(p(\underline{\bm{\hat{w}}}))$
$\displaystyle=\sum_{\underline{\bm{\hat{w}}}}\sum_{j=1}^{|\underline{\bm{\hat{w}}}|}p(\underline{\bm{\hat{w}}}|\underline{\bm{w}},\underline{\bm{r}})\log(p(\underline{{\hat{w}}}_{j}))$
$\displaystyle=\sum_{j}\underline{r}_{j}\log(p(\underline{w}_{j}))$ (13)

The expectation of probability $E(p(\underline{\bm{w}}))$ takes the form:

$\displaystyle E(p(\underline{\bm{w}}))$
$\displaystyle=\sum_{\underline{\bm{\hat{w}}}}p(\underline{\bm{\hat{w}}}|\underline{\bm{w}},\underline{\bm{r}})p(\underline{\bm{\hat{w}}})$
$\displaystyle=\sum_{\underline{\bm{\hat{w}}}}p(\underline{\bm{\hat{w}}}|\underline{\bm{w}},\underline{\bm{r}})\prod_{j=1}^{|\underline{\bm{\hat{w}}}|}p(\underline{{\hat{w}}}_{j})$
$\displaystyle=\sum_{\underline{\bm{\hat{r}}}}\prod_{j}p(\underline{\hat{r}}_{j})\prod_{j}p(\underline{w}_{j})^{\underline{\hat{r}}_{j}}$
$\displaystyle=\sum_{\underline{\bm{\hat{r}}}}\prod_{j}p(\underline{\hat{r}}_{j})p(\underline{w}_{j})^{\underline{\hat{r}}_{j}}$
(14)

These two are not necessarily equivalent, as demonstrated by Jensen’s
inequality:
$E(\log(p(\underline{\bm{w}})))\leq\log(E(p(\underline{\bm{w}})))$. It is not
clear which one to use for inference. $E(p(\underline{\bm{w}}))$ seems to be
the natural choice, since it equals the mean of the probability over the
distribution. If a model is estimated using the Q-function of equation
LABEL:expected_Q, then $E(\log(p(\underline{\bm{w}})))$ is consistent with the
estimation. $E(\log(p(\underline{\bm{w}})))$ is trivially computed from the
weighted counts, whereas $E(p(\underline{\bm{w}}))$ is more complicated, but
can be computed using the forward algorithm from the word and weight sequences
in time linear to the sequence length. For this thesis, we will use
$E(\log(p(\underline{\bm{w}})))$, since it gives results that equal the use of
fractional counts in existing literature, while no results using
$E(p(\underline{\bm{w}}))$ exist.

###  3 Formalizing MNB as a Generative Directed Graphical Model

The present chapter has formalized the smoothing and feature weighting
commonly used with MNB, but there are several omissions in the standard
descriptions of MNB. It can be argued that the MNB model is not multinomial,
naive, or Bayesian:

1)

MNB is usually not a Bayesian model since no distribution over parameters is
kept, but rather a generative model using the Bayes rule for posterior
inference.

2)

MNB is not a Naive Bayes model, since the conditional distribution is modeled
by a single multinomial, not by conditionally independent models for each
feature.

3)

The conditional multinomials in MNB are in fact tied multinomials with
parameters shared for all possible documents lengths, combined with a length-
generating distribution such as Poisson.

4)

The conditional multinomials themselves have not been formalized correctly,
but using a variety of smoothing methods with no connection to maximum
likelihood.

5)

Feature weighting such as TF-IDF has not been generally formalized for either
the training or test set documents, despite being very commonly used with MNB.

Given the common misconceptions about MNB, it is useful to formalize it with a
precise definition. We can redefine MNB as a generative model over sequences
that factorizes into distributions for labels, word sequence lengths and
2-state HMMs for label-conditionals. Feature weighting can be formalized as
estimation and inference using expectations of log likelihoods and log
probabilities over probabilistic data. The joint probability for the model
factorizes as:

$\displaystyle p(\underline{\bm{w}},l,\underline{\bm{k}})$
$\displaystyle=p(l)p(J)p(\underline{\bm{w}},\underline{\bm{k}}|\>l,J)$
$\displaystyle=p(l)p(J)\prod_{j}p_{l}(\underline{k}_{j})p^{u}_{l\underline{k}_{j}}(\underline{w}_{j}),$
(15)

where the prior $p(l)$ is categorical, the length generation factor $p(J)$ is
Poisson and label-conditionals
$p(\underline{\bm{w}},\underline{\bm{k}}|\>l,J)$ are modeled by the 2-state
HMMs with $M=2$ and categoricals $p_{l}(\underline{k}_{j})$ for each $l$, and
$p_{l\underline{k}_{j}}(\underline{w}_{j})$ for each $l$ and $m$.

$\underline{w}_{j}$$\underline{k}_{j}$$l$$j=1..J$$J$$i=1..I$ Figure 2:
Graphical model for Multinomial Naive Bayes, formalizing multinomial smoothing
as a 2-state Hidden Markov Model

The two-state HMM terms correspond to the original MNB terms:
$p^{u}_{lm=1}(n)=p^{u}_{l}(n)$ for the label-conditional models,
$p^{u}_{lm=2}(n)=p^{u}(n)$ for the shared background model, and
$p(m=2)=\alpha_{l}$ for the smoothing weight. Figure 2 shows the graphical
model notation for the correctly formalized MNB.

The hidden states can be marginalized away:

$\displaystyle p(\underline{\bm{w}},l)$
$\displaystyle=p(l)p(J)\sum_{\underline{\bm{k}}}\prod_{j}(p_{l}(\underline{k}_{j})p^{u}_{l\underline{k}_{j}}(\underline{w}_{j}))$
$\displaystyle=p(l)p(J)\prod_{j}\sum_{m}(p_{l}(m)p^{u}_{lm}(\underline{w}_{j}))$
$\displaystyle=p(l)p(J)\prod_{n}((1-\alpha_{l})p^{u}_{l}(n)+\alpha_{l}\>p^{u}(n))^{w_{n}}$
(16)

The label posterior $p(l|\underline{\bm{w}})$ given a word sequence becomes:

$\displaystyle p(l|\underline{\bm{w}})$
$\displaystyle=\frac{p(\underline{\bm{w}},l)}{\sum_{l^{\prime}}p(\underline{\bm{w}},l^{\prime})}$
$\displaystyle\propto
p(l)\prod_{n}((1-\alpha_{l})p^{u}_{l}(n)+\alpha_{l}\>p^{u}(n))^{w_{n}}$ (17)

The label posterior $p(l|\bm{w})$ given a word vector becomes:

$\displaystyle p(l|\bm{w})$
$\displaystyle=\frac{p(l)p(J)Z(\bm{w})\prod_{j}\sum_{m}(p_{l}(m)p^{u}_{lm}(\underline{w}_{j}))}{\sum_{l^{\prime}}p(l^{\prime})p(J)Z(\bm{w})\prod_{j}\sum_{m}(p_{l^{\prime}}(m)p^{u}_{l^{\prime}k}(\underline{w}_{j}))}$
$\displaystyle\propto
p(l)\prod_{n}((1-\alpha_{l})p^{u}_{l}(n)+\alpha_{l}\>p^{u}(n))^{w_{n}},$ (18)

where $Z(\bm{w})$ is the multinomial normalizer.

The word vectors can be used to compute exactly the same label posteriors,
meaning that for posterior inference only the word vectors are required, and
not the word sequence information. The joint can be marginalized to produce
the probability of a word sequence:

$\displaystyle p(\underline{\bm{w}})$
$\displaystyle=\sum_{l}\sum_{\underline{\bm{k}}}p(\underline{\bm{w}},l,\underline{\bm{k}})$
$\displaystyle=p(J)\sum_{l}p(l)\sum_{\underline{\bm{k}}}p_{l}(\underline{\bm{w}},\underline{\bm{k}})$
$\displaystyle=p(J)\sum_{l}p(l)\prod_{n}((1-\alpha_{l})p^{u}_{l}(n)+\alpha_{l}\>p^{u}(n))^{w_{n}}$
(19)

From the marginal probabilities MNB can be seen as a mixture of label-
conditional models (McCallum and Nigam, 1998; Novovicova and Malik, 2003;
Nigam et al., 2006), where the label variables are known for each document in
a training dataset. The MNB factorization is simplified by a number of
independence assumptions. The length factor $p(J)$ is assumed to be mutually
independent with the other factors (Juan and Ney, 2002).

The training data consists of documents
$D^{(i)}=(l^{(i)},\underline{\bm{w}}^{(i)},\underline{\bm{k}}^{(i)})$, where
$l^{(i)}$ and $\underline{\bm{w}}^{(i)}$ are known, and
$\underline{\bm{k}}^{(i)}$ is unknown. The likelihood function is:

$\displaystyle\mathcal{L}({\bm{\theta}}|D)$ $\displaystyle=p(D|{\bm{\theta}})$
$\displaystyle=\prod_{i}p(l^{(i)}|\bm{\pi})p(|\underline{\bm{w}}|_{0}^{(i)}|\bm{\chi})\sum_{\underline{\bm{k}}^{(i)}}\prod_{j}p_{l^{(i)}}(\underline{k}_{j}^{(i)}|\bm{\alpha})\>p^{u}_{l^{(i)}\underline{k}_{j}^{(i)}}(\underline{w}^{(i)}_{j}|\bm{\lambda})$
(20)

Treating $\underline{\bm{k}}$ as a random variable distributed according to a
prior distribution
$p_{l^{(i)}}(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})$,
the conditional expectation of the log-likelihood becomes:

$\displaystyle Q(\bm{\theta}|D,\bm{\hat{\theta}})$
$\displaystyle=E(\log(\mathcal{L}(\bm{\theta}|D,\bm{\hat{\theta}})))$
$\displaystyle=\sum_{i}(\log(p(l^{(i)}|\bm{\theta}))+\log(p(|\underline{\bm{w}}|_{0}^{(i)}|\bm{\theta}))$
$\displaystyle+\sum_{\underline{\bm{k}}^{(i)}}\sum_{j}p_{l^{(i)}}(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})\log(p_{l^{(i)}}(\underline{k}_{j}^{(i)}|\bm{\theta})\>p^{u}_{l^{(i)}\underline{k}_{j}^{(i)}}(\underline{w}^{(i)}_{j}|\bm{\theta})))$
(21)

The maximization decouples into separate optimizations:

$\displaystyle\operatornamewithlimits{argmax}_{\bm{\theta}}(Q(\bm{\theta}|D,\bm{\hat{\theta}})))$
$\displaystyle=\operatornamewithlimits{argmax}_{(\bm{\pi},\bm{\lambda},\bm{\alpha},\bm{\chi})}(\sum_{i}\log(p(l^{(i)}|\bm{\pi}))$
$\displaystyle+\sum_{i}\log(p(|\underline{\bm{w}}|_{0}^{(i)}|\bm{\chi}))$
$\displaystyle+\sum_{i}\sum_{\underline{\bm{k}}^{(i)}}\sum_{j}p_{l^{(i)}}(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})\log(p_{l^{(i)}}(\underline{k}_{j}^{(i)}|\bm{\alpha}))$
$\displaystyle+\sum_{i}\sum_{\underline{\bm{k}}^{(i)}}\sum_{j}p_{l^{(i)}}(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})\log(p^{u}_{l^{(i)}\underline{k}_{j}^{(i)}}(\underline{w}^{(i)}_{j}|\bm{\lambda})))$
(22)

The parameters $\bm{\pi}$ and $\bm{\chi}$ are invariant to the expectation
over the hidden states, and are therefore exact maximum likelihood estimates.
For many uses the parameters $\bm{\chi}$ for word sequence lengths can be
omitted, since these have no effect on the posterior probabilities. The
parameters $\bm{\lambda}$ and $\bm{\alpha}$ are expected log-likelihood
estimates given
$p_{l^{(i)}}(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})$,
as discussed in Section 2. Choosing
$p_{l^{(i)}}(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})$
and a form for the shared background model $p^{u}(n)$ implements smoothing.

Feature weighting is incorporated by performing estimation and inference over
probabilistic data, as described in Section 3. Given a probabilistic weight
sequence $\underline{\bm{r}}$ matching the word sequence $\underline{\bm{w}}$,
probabilities can be approximated by the expectations of log-probabilities
given $\underline{\bm{r}}$. For both inference and estimation, this reproduces
the results that come from simply using fractional counts in algorithms
instead of integer counts, as has been done with applications of MNB using
weighted words. In Equations 16, 17, 18, and 19, approximation with expected
log-probabilities replaces the integer vector $\bm{w}$ by the fractional
expected counts $E(\bm{w}|\underline{\bm{r}})$, that are provided by any
chosen feature weighting function. Maximum expected log-likelihood estimation
introduces the weight terms $r_{j}$ to Equations 21 and 22. The multinomials
for the two-state HMM become weighted by both the distribution of
occurring/non-occurring terms defined by $\underline{\bm{r}}$, and the assumed
distribution over the HMM component assignments
$p_{l^{(i)}}(\underline{\bm{k}}^{(i)}|\underline{\bm{w}}^{(i)},\bm{\hat{\theta}})$.
The length-modeling factor $p(|\underline{\bm{w}}|_{0}^{(i)}|\bm{\chi}))$
should also take the weighted distribution over occurring word sequences into
account, unless the length model is approximated by ignoring weights. Further
derivation of Poisson length model estimation on expected sequence lengths is
omitted, as the experiments conducted in the thesis evaluate length modeling
separately to feature weighting.

###  4 Extending MNB with Prior Scaling and Document Length Modeling

The extension of MNB so far has formalized smoothing methods as a directed
graphical model. Further useful extensions to MNB can be defined by modifying
the graphical model factorization. Two such extensions are label-conditional
document length modeling and scaling of the label prior.

Document lengths in MNB are assumed to be generated by a shared distribution
such as Poisson (McCallum and Nigam, 1998; Blei et al., 2003), that can be
omitted for most uses. Use of label-conditional distributions has been
suggested in the literature (McCallum and Nigam, 1998), but has not
experimented. Since document lengths are known to be among the strongest
features for some tasks, such as automatic essay scoring (Larkey, 1998),
explicit length modeling could prove useful.

Prior scaling is applied to LMs in uses such as speech recognition, where a LM
models the prior distribution of possible word sequences in a Naive Bayes
framework (Gales and Young, 2007). In these uses the prior has a very
different scale than the conditional distribution, and a scaling factor is
applied to match the contributions of the prior and conditional optimally.
Prior scaling can be applied to TM tasks equally, but this has not been
attempted.

An Extended MNB incorporating prior scaling and document length modeling can
be defined as:

$\displaystyle p(\underline{\bm{w}},l,\underline{\bm{k}})$
$\displaystyle=p(l)p(J|l)p(\underline{\bm{w}},\underline{\bm{k}}|\>l,J)$
$\displaystyle=p(l)p(J|l)\prod_{j}p_{l}(\underline{k}_{j})p^{u}_{l\underline{k}_{j}}(\underline{w}_{j}),$
(23)

where the label prior $p(l)$ and length model $p(J|l)$ are scaled and
renormalized versions of the original distributions $p^{\prime}(l)$ and
$p^{\prime}(J|l)$ : $p(l)=Z(\vartheta)\>p^{\prime}(l)^{\vartheta}$ and
$p(J|l)=Z(\varsigma)\>p^{\prime}(J|l)^{\varsigma}$. $Z(\vartheta)$ and
$Z(\varsigma)$ normalize the factors to be probability distributions, and
$\vartheta$ and $\varsigma$ are meta-parameters to be estimated on held-out
data.

$\underline{w}_{j}$$\underline{k}_{j}$$l$$j=1..J$$J$$i=1..I$ Figure 3:
Graphical model for the Extended MNB, with label-conditional document length
modeling, but without scaling of the factors for $p(l)$ and $p(J|l)$.

The Extended MNB model with fixed scaling factors $\vartheta=1$ and
$\varsigma=1$ constitutes a directed generative model, and the corresponding
graphical model is illustrated in Figure 3. With scaling weights other than 1
and 0, the parameter estimates of the scaled factors no longer derive from a
directed factorization. One solution to formalize the model is to consider the
combination of factors as a type of log-linear model combination (Klakow,
1998; Hinton, 2002; Bouchard and Triggs, 2004; Suzuki et al., 2007):

$\displaystyle p(\underline{\bm{w}},l,\underline{\bm{k}})$
$\displaystyle=Z\>p^{\prime}(l)^{\vartheta}\>p^{\prime}(J|l)^{\varsigma}\>p(\underline{\bm{w}},\underline{\bm{k}}|\>l,J)$
(24)

With the log-linear model of Equation 24, the factors for label priors,
document lengths and label-conditional word distributions become feature
functions combined using the log-linear weights $\vartheta$ and $\varsigma$.
Maximum likelihood estimation of the model becomes complicated. One
approximate solution is to keep the maximum likelihood estimates for the
directed model, and directly optimize the new parameters $\vartheta$ and
$\varsigma$ for a performance measure on held-out development data (Metzler
and Croft, 2005). This approximation is used for the experiments conducted in
Chapter 6. It maintains the simplicity of directed models, while allowing the
additional parameters to improve model performance.

##  Chapter 8 Sparse Inference

This chapter proposes computation based on sparse model representations for
scalable inference. This reduces the time and space complexity of inference
for a variety of linear models and structural extensions. First a basic case
of sparse posterior inference is derived for uses such as Multinomial Naive
Bayes (MNB) classification, ranking and clustering. This is extended into a
more general case of joint inference on hierarchically smoothed sequence
models, and further into joint inference on mixtures of such models.
Additional efficiency improvements for the inference are discussed, and a
structural extension of MNB benefiting from sparse inference is proposed,
called Tied Document Mixture.

###  1 Basic Case: Sparse Posterior Inference

Once estimated, a generative model such as Multinomial Naive Bayes (MNB) can
be used for several types of inference, depending on the task and application.
The most common types are classification in text categorization, ranking in
information retrieval, soft classification in document clustering, and model
combination. All of these perform inference related to the posterior
$p(l|\bm{w})$. In classification, the most likely label to generate a document
is selected: $\operatornamewithlimits{argmax}_{l}p(l|\bm{w})$. In ranking,
scores are computed for each label:
$y(\bm{\theta}_{l},\bm{w})\overset{rank}{=}p(l|\bm{w})$. In soft
classification and model combination, the posterior is used directly.

The time and space complexity of the inference is crucial in many applications
of MNB, since this determines the scalability of the model to large-scale
tasks. The numbers of labels, words and training documents can exceed millions
in many practical tasks involving web-scale text datasets. The required
computation can be reduced depending on the type of inference. For example,
for posterior inference the multinomial normalizer can be omitted, since
$p(l|\bm{w})=\frac{Z\>p(l)\prod_{n}p(w_{n}|l)}{\sum_{l}Z\>p(l)\prod_{n}p(w_{n}|l)}=\frac{\>p(l)\prod_{n}p(w_{n}|l)}{\sum_{l}\>p(l)\prod_{n}p(w_{n}|l)}$.

A naive algorithm for performing posterior inference with MNB computes
$p(l|\bm{w})=\frac{p(l,\bm{w})}{\sum_{l^{\prime}}p(l^{\prime},\bm{w})}=Z\>p(l)\prod_{n:w_{n}\neq
0}p_{l}(n)^{w_{n}}$ for each label $l$ by computing the joint probabilities
$p(l,\bm{w})$ as a product over terms $n$ for each label $l$, and normalizing
by the sum over the joints $Z=\sum_{l^{\prime}}p(l^{\prime},\bm{w})$. This has
complexity $O(|\bm{w}|_{0}L)$, and this is widely considered to be optimal for
linear models (Manning et al., 2008). However, the time complexity for
posterior inference can be substantially reduced by taking into account
sparsity in the parameters. Earlier work with inverted indices has shown that
classifier scores for Centroid classifier (Shanks et al., 2003) and K-nearest
Neighbours (Yang, 1994) can be done as a function of sparsity. The posteriors
for MNB with uniform priors can be computed similarly (Hiemstra, 1998; Zhai
and Lafferty, 2001b), for both Jelinek-Mercer (Hiemstra, 1998) and other basic
smoothing methods (Zhai and Lafferty, 2001b). The _sparse inference_ proposed
here generalizes this inference to MNB with categorical priors, a variety of
linear models and structural extensions. A basic sparse posterior inference
algorithm for MNB is described next. It combines three techniques for
efficient computation:

Log-domain computation

refers to use of log probability values, a standard practice with large-scale
statistical models. This changes products into sums and exponents into
products in the log-domain, which are much cheaper to compute with modern
processors. For example,
$\log(p(l)p_{l}(\bm{w}))=\log(p(l))+\log(p_{l}(\bm{w}))$ and
$\log(p_{l}(n)^{w_{n}})=\log(p_{l}(n))w_{n}$. Another benefit of log-
computation is reducing numerical inaccuracy that comes from computing with
small probabilities. Alternatives such as scaling (Rabiner, 1989) for
correcting inaccuracy with large-scale models are less useful in general.

Precomputing

organizes an algorithm and necessary data structures so that less computation
is necessary when the algorithm is used. A basic sparse posterior inference
algorithm computes first the smoothing distribution probabilities $p^{u}(n)$,
and then updates these for each $l$ by multiplying with
$\frac{(1-\alpha_{l})p_{l}^{u}(n)+\alpha_{l}p^{u}(n)}{p^{u}(n)}$. The original
parameter values $p^{u}_{l}(n)$ can be replaced by precomputed ones, since for
computing $p(l,\bm{w})$, $p^{u}_{l}(n)$ are only needed for updating
$p^{u}(n)$ for each $l$. The parameters for $p(l)$, $p^{u}(n)$, $\alpha_{l}$
and $p^{u}_{l}(n)$ can be replaced by the precomputed log values
$p^{\prime}(l)=\log p(l)$, $p^{\prime u}(n)=\log(p^{u}(n))$,
$\alpha^{\prime}_{l}=\log(\alpha_{l})$, and $p^{\prime
u}_{l}(n)=\log((1-\alpha_{l})p_{l}^{u}(n)+\alpha_{l}p^{u}(n))-\alpha^{\prime}_{l}-p^{\prime
u}(n)$ for all $p^{u}_{l}(n)>0$.

Inverted index

data structures have formed the core technique of information retrieval for
the last decades (Zobel and Moffat, 2006). An inverted index uses a vector
$\bm{\zeta}$ of _postings lists_ for each word, so that for each word a list
$\bm{\zeta}_{n}$ of occurrence information can be accessed in constant time.
For sparse inference with MNB, it is sufficient to maintain the label and
parameter in the postings, so that each posting is a pair $(l,p^{\prime
u}_{l}(n))$. $p_{l}(n)$ can first be computed by $p^{u}(n)$, and updated for
each $l$ with $p_{l}^{u}(n)\neq 0$. Using an inverted index, the set of
parameters to update can be retrieved with a time complexity
$O(|\bm{w}|_{0}+\sum_{n}\sum_{l:p^{u}_{l}(n)\neq 0}1)$ instead of
$O(L|\bm{w}|_{0})$.

A basic sparse posterior inference algorithm computes $p^{\prime u}(\bm{w})$,
updates this for all $l$ with $p^{\prime}(l)$ and $p^{\prime u}_{l}(\bm{w})$,
and normalizes to obtain the posterior $p(l|\bm{w})$. This has the time
complexity $O(L+|\bm{w}|_{0}+\sum_{n}\sum_{l:p^{u}_{l}(n)\neq 0}1)$. Using the
precomputed values, we can compute joint probabilities as
$p(\bm{w},l)\propto\exp(p^{\prime}(l)+\sum_{n}w_{n}(p^{\prime
u}(n)+\alpha^{\prime}_{l})+\sum_{n:p^{u}_{l}(n)\neq 0}w_{n}p^{\prime
u}_{l}(n)))$. The posterior can be computed by normalizing
$p(l|\bm{w})=p(\bm{w},l)/\sum_{l^{\prime}}p(\bm{w},l^{\prime})$. A key
algorithmic idea here is that the conditional probabilities $p(\bm{w}|l)$
decompose into separately computed terms for the smoothing distribution, the
smoothing weight, and the label-conditional:
$p(\bm{w}|l)\propto\exp(\sum_{n:w_{n}\neq 0}p^{\prime
u}(n)+|\bm{w}|_{1}\alpha^{\prime}_{l}+\sum_{n:p^{u}(n)\neq 0}p^{\prime
u}_{l}(n))$.

Algorithm 1 Sparse Posterior Inference for MNB

1:$smooth\\_logprob=0$

2:for all $n:w_{n}\neq 0$ do

3: $smooth\\_logprob+=p^{\prime u}(n)*w_{n}$

4:for all $l$ do

5:
$logprobs_{l}=p^{\prime}(l)+|\bm{w}|_{1}\alpha^{\prime}_{l}+smooth\\_logprob$

6:for all $n:w_{n}\neq 0$ do

7: for all $(l,p^{\prime u}_{l}(n))\in\bm{\zeta}_{n}$ do

8: $logprobs_{l}+=p^{\prime u}_{l}(n)*w_{n}$

9:$normalizer=-1000000$

10:for all $l$ do

11: $normalizer=log(exp(normalizer)+exp(logprobs_{l}))$

12:for all $l$ do

13: $logprobs_{l}-=normalizer$ return $logprobs$

Pseudo-code for the resulting sparse posterior inference algorithm returning
$p(l|\bm{w})$ is given in Algorithm 1. Although the sparse inference algorithm
is described here for MNB posterior inference, it is applicable to any linear
model. The inference algorithm with precompiled values corresponds to a
sparsely computed dot product
$y(\bm{\theta},\bm{w})=\theta_{0}+\sum_{n=1}^{N}\theta_{n}w_{n}$, which is
used for all linear classifiers, including Centroid, Perceptron, Logistic
Regression and Support Vector Machine classifiers. Moreover, it can be
generalized into structured models such as hierarchical mixture models.
Therefore the textbook statement (Manning et al., 2008) on optimality of