from S and would like to estimate the probability that the
next symbol takes on a particular value.
One way to estimate the probability that the next symbol takes some value s Î S is to use the relative frequency
of its occurrence in x, i.e., if s occurs frequently in x we
expect its probability of appearing next to be high as well.
Assuming that x is long enough, doing this will be better than giving equal probability to all symbols in S. Let us
denote by N(s) the number of occurrences of s in x. Our estimate of the probability of s being the next symbol is then
. The function G is a discrete
distribution over the elements of S: it assigns a non-negative
number G(s) to each symbol s signifying the probability of
observing s, with the numbers summing to one over S.
Of course, this approach is only reasonable if the process
generating x has no history dependence (e.g., if x is produced by a sequence of tosses of a biased coin). It is highly
unsatisfying if there are contextual dependencies which
we can exploit. If we start accounting for context, we can
quickly improve the quality of the predictions we make. For
instance, why not take into account the preceding symbol?
Let u be another symbol. If the last symbol in x is u, then we
can estimate the probability of the next symbol being s by
counting the number of times s occurs after u in x. As before,
we can be more precise and define
to be the estimated probability of s occurring after u, where
N(us) is the number of occurrences of the subsequence us in x.
The function Gu is again a discrete distribution over the symbols in S, but it is now a conditional distribution as the probability assigned to each symbol s depends on the context u.
3. mAXimum LiKeLiHooD
Some readers may realize that the counting procedure
described above corresponds to a ubiquitous statistical estimation technique called maximum likelihood
(ML) estimation. The general ML estimation setup is
as follows: we observe some data x which is assumed to
have been generated by some underlying stochastic process and wish to estimate parameters Q for a probabilistic model of this process. A probabilistic model defines
a distribution P(x|Q) over x parameterized by Q, and the
ML estimator is the value of Q maximizing P(x|Q). In our
a It is straightforward to consider multiple sequences in our setting, we
consider being given only one sequence in this paper for simplicity.
92 communicAtions of tHe Acm | FEBRUARY 2011 | voL. 54 | No. 2
case, the data consists of the observed sequence, and the
parameters are the conditional distributions Gu for some
set of u’s.
In a sense, ML is an optimistic procedure, in that it
assumes that x is an accurate reflection of the true underlying process that generated it, so that the ML parameters will be an accurate estimate of the true parameters.
It is this very optimism that is its Achilles heel, since
it becomes overly confident about its estimates. This
situation is often referred to as overfitting. To elaborate
on this point, consider the situation in which we have
long contexts. The denominator of ( 1) counts the number
of times that the context u occurs in x. Since x is of finite
length, when u is reasonably long, the chance that u never
occurs at all in x can be quite high, so ( 1) becomes undefined with a zero denominator. More pernicious still is if
we are “lucky” and u did occur once or a few times in x. In
this case ( 1) will assign high probability to the few symbols
that just by chance did follow u in x, and zero probability
to other symbols. Does it mean that these are the only symbols we expect to see in the future following u, or does it
mean that the amount of data we have in x is insufficient to
characterize the conditional distribution Gu Given a complex process with many parameters the latter is often the
case, leading to ML estimates that sharpen far too much
around the exact observations and don’t reflect our true
Obviously, if one uses models that consider only short
context lengths, this problem can largely be avoided if one
has enough data to estimate some (relatively) smaller number of conditional distributions. This is precisely what is typically done: one makes a fixed-order Markov assumption and
restricts oneself to estimating collections of distributions
conditioned on short contexts (for instance, an nth-order
Markov model, or an m-gram language model). The consequence of doing this is that ML estimation becomes
feasible, but longer-range dependencies are discarded. By
assumption and design, they cannot be accounted for by
such restrictive models.
Even having imposed such a restriction, overfitting often
remains an issue. This has led to the development of creative
approaches to its avoidance. The language modeling and
text compression communities have generally called these
smoothing or back-off methodologies (see Chen and Goodman3
and references therein). In the following, we will propose a
Bayesian approach that retains uncertainty in parameter estimation and thus avoids overconfident estimates.
4. BAyesiAn moDeLinG
As opposed to ML, the Bayesian approach is inherently
conservative. Rather than trusting the data fully, Bayesian
parameter estimation incorporates both evidence from the
data as well as from prior knowledge of the underlying process. Furthermore, uncertainty in estimation is taken into
account by treating the parameters Q as random, endowed
with a prior distribution P(Q) reflecting the prior knowledge
we have about the true data generating process. The prior
distribution is then combined with the likelihood P(x|Q) to
yield, via Bayes’ Theorem (the namesake of the approach),