Inducing Features of Random Fields.
AbstractWe present a technique for constructing random fields from a set of training samples. The learning paradigm builds increasingly complex fields by allowing potential functions, or features, that are supported by increasingly large subgraphs. Each feature has a weight that is trained by minimizing the Kullback-Leibler divergence between the model and the empirical distribution of the training data. A greedy algorithm determines how features are incrementally added to the field and an iterative scaling algorithm is used to estimate the optimal values of the weights. The random field models and techniques introduced in this paper differ from those common to much of the computer vision literature in that the underlying random fields are non-Markovian and have a large number of parameters that must be estimated. Relations to other learning approaches, including decision trees, are given. As a demonstration of the method, we describe its application to the problem of automatic word classification in natural language processing.
INTRODUCTION
I
this paper we present a method for incrementally constructing
random fields. Our method builds increasingly complex
fields to approximate the empirical distribution of a set of training
examples by allowing potential functions, or features, that
are supported by increasingly large subgraphs. Each feature is
assigned a weight, and the weights are trained to minimize the
Kullback-Leibler divergence between the field and the empirical
distribution of the training data. Features are incrementally
added to the field using a top-down greedy algorithm, with the
intent of capturing the salient properties of the empirical sample
while allowing generalization to new configurations. The
general problem that the methods we propose address is that of
discovering the structure inherent in a set of sample patterns. As
one of the fundamental aims of statistical inference and learn-
ing, this problem is central to a wide range of tasks including
classification, compression, and prediction.
To illustrate the nature of our approach, suppose we wish
to automatically characterize spellings of words according to a
statistical model; this is the application we develop in Section
5. A field with no features is simply a uniform distribution on
ASCII strings (where we take the distribution of string lengths as
given). The most conspicuous feature of English spellings is that
they are most commonly comprised of lower-case letters. The
induction algorithm makes this observation by first constructing
the field
e
where - is an indicator function and the weight - [a\Gammaz] associated
with the feature that a character is lower-case is chosen to be
approximately 1:944. This means that a string with a lowercase
letter in some position is about 7 - e 1:944 times more likely than
Stephen and Vincent Della Pietra are with Renaissance Technologies, Stony
Brook, NY, 11790. E-mail: [sdella,vdella]@rentec.com
John Lafferty is with the Computer Science Department of the School of
Computer Science, Carnegie Mellon University, Pittsburgh, PA, 15213. E-mail:
lafferty@cs.cmu.edu
the same string without a lowercase letter in that position. The
following collection of strings was generated from the resulting
field by Gibbs sampling. (As for all of the examples that will be
shown, this sample was generated with annealing, to concentrate
the distribution on the more probable strings.)
m, r, xevo, ijjiir, b, to, jz, gsr, wq, vf, x, ga,
msmGh, pcp, d, oziVlal, hzagh, yzop, io, advzmxnv,
ijv_bolft, x, emx, kayerf, mlj, rawzyb, jp, ag,
ctdnnnbg, wgdw, t, kguv, cy, spxcq, uzflbbf,
dxtkkn, cxwx, jpd, ztzh, lv, zhpkvnu, l-, r, qee,
nynrx, atze4n, ik, se, w, lrh, hp+, yrqyka'h,
zcngotcnx, igcump, zjcjs, lqpWiqu, cefmfhc, o, lb,
fdcY, tzby, yopxmvk, by, fz,, t, govyccm,
ijyiduwfzo, 6xr, duh, ejv, pk, pjw, l, fl, w
The second most important feature, according to the algorithm, is
that two adjacent lower-case characters are extremely common.
The second-order field now becomes
e
where the weight - [a\Gammaz][a\Gammaz] associated with adjacent lower-case
letters is approximately 1:80.
The first 1000 features that the algorithm induces include the
strings s>, <re, ly>, and ing>, where the character "<" denotes
beginning-of-string and the character ">" denotes end-of-
string. In addition, the first 1000 features include the regular expressions
(with weight 9:15) and [a-z][A-Z]
(with weight \Gamma5:81) in addition to the first two features [a-z]
and [a-z][a-z]. A set of strings obtained by Gibbs sampling
from the resulting field is shown here:
was, reaser, in, there, to, will, ,, was, by,
homes, thing, be, reloverated, ther, which,
conists, at, fores, anditing, with, Mr., proveral,
the, ,, *, on't, prolling, prothere, ,, mento,
at, yaou, 1, chestraing, for, have, to, intrally,
of, qut, ., best, compers, *, cluseliment, uster,
of, is, deveral, this, thise, of, offect, inatever,
thifer, constranded, stater, vill, in, thase, in,
youse, menttering, and, ., of, in, verate, of, to
These examples are discussed in detail in Section 5.
The induction algorithm that we present has two parts: feature
selection and parameter estimation. The greediness of the
algorithm arises in feature selection. In this step each feature in
a pool of candidate features is evaluated by estimating the reduction
in the Kullback-Leibler divergence that would result from
adding the feature to the field. This reduction is approximated
as a function of a single parameter, and the largest value of this
function is called the gain of the candidate. This approximation
is one of the key elements of our approach, making it practical
to evaluate a large number of candidate features at each stage of
the induction algorithm. The candidate with the largest gain is
added to the field. In the parameter estimation step, the parameters
of the field are estimated using an iterative scaling algorithm.
The algorithm we use is a new statistical estimation algorithm
IEEE TRANSACTIONS PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19, NO. 4, APRIL 1997
that we call Improved Iterative Scaling. It is an improvement
of the Generalized Iterative Scaling algorithm of Darroch and
Ratcliff [12] in that it does not require that the features sum to
a constant. The improved algorithm is easier to implement than
the Darroch and Ratcliff algorithm, and can lead to an increase
in the rate of convergence by increasing the size of the step taken
toward the maximum at each iteration. In Section 4 we give a
simple, self-contained proof of the convergence of the improved
algorithm that does not make use of the Kuhn-Tucker theorem
or other machinery of constrained optimization. Moreover, our
proof does not rely on the convergence of alternating I-projection
as in Csisz-ar's proof [10] of the Darroch-Ratcliff procedure.
Both the feature selection step and the parameter estimation
step require the solution of certain algebraic equations whose
coefficients are determined as expectation values with respect
to the field. In many applications these expectations cannot be
computed exactly because they involve a sum over an exponentially
large number of configurations. This is true of the application
that we develop in Section 5. In such cases it is possible
to approximate the equations that must be solved using Monte
Carlo techniques to compute expectations of random variables.
The application that we present uses Gibbs sampling to compute
expectations, and the resulting equations are then solved using
Newton's method.
Our method can be viewed in terms of the principle of maximum
entropy [19], which instructs us to assume an exponential
form for our distributions, with the parameters viewed as
Lagrange multipliers. The techniques that we develop in this
paper apply to exponential models in general. We formulate
our approach in terms of random fields because this provides a
convenient framework within which to work, and because our
main application is naturally cast in these terms.
Our method differs from the most common applications of
statistical techniques in computer vision and natural language
processing. In contrast to many applications in computer vision,
which involve only a few free parameters, the typical application
of our method involves the estimation of thousands of free
parameters. In addition, our methods apply to general exponential
models and random fields-there is no underlying Markov
assumption made. In contrast to the statistical techniques common
to natural language processing, in typical applications of
our method there is no probabilistic finite-state or push-down
automaton on which the statistical model is built.
In the following section we describe the form of the random
field models considered in this paper and the general learning
algorithm. In Section 3 we discuss the feature selection step of
the algorithm and briefly address cases when the equations need
to be estimated using Monte Carlo methods. In Section 4 we
present the Improved Iterative Scaling algorithm for estimating
the parameters, and prove the convergence of this algorithm.
In Section 5 we present the application of inducing features of
spellings, and finally in Section 6we discuss the relation between
our methods and other learning approaches, as well as possible
extensions of our method.
II. THE LEARNING PARADIGM
In this section we present the basic algorithm for building
up a random field from elementary features. The basic idea
is to incrementally construct an increasingly detailed field to
approximate a reference distribution -
p. Typically the distribution
p is obtained as the empirical distribution of a set of training
examples. After establishing our notation and defining the form
of the random field models we consider, we present the training
problem as a statement of two equivalent optimization problems.
We then discuss the notions of a candidate feature and the gain
of a candidate. Finally, we give a statement of the induction
algorithm.
A. Form of the random field models
be a finite graph with vertex set V and edge
set E, and let A be a finite alphabet. The configuration space
W is the set of all labelings of the vertices in V by letters in
A. If C ae V and ! 2 W is a configuration, then !C denotes
the configuration restricted to C . A random field on G is a
probability distribution on W. The set of all random fields is
nothing more than the simplex D of all probability distributions
on W. If f then the support of f , written supp(f),
is the smallest vertex subset C ae V having the property that
C then
We consider random fields that are given by Gibbs distributions
of the form
e
are functions with supp(V C
C. The field is Markov if whenever VC 6= 0 then C is a clique,
or totally connected subset of V . This property is expressed in
terms of conditional probabilities as
E)
where u and v are arbitrary vertices. We assume that each C is
a path-connected subset of V and that
1g. We say that the values - C
are the parameters of the field and that the functions f C
i are the
features of the field. In the following, it will often be convenient
to use notation that disregards the dependence of the features
and parameters on a vertex subset C , expressing the field in the
e
For every random field (E; V; f- of the above form, there
is a field that is Markovian, obtained by completing
the edge set E to ensure that for each i, the subgraph
generated by the vertex subset totally connected

If we impose the constraint - on two parameters - i and
then we say that these parameters are tied. If - i and - j are
tied, then we can write
is a non-binary feature. In general, we can
collapse any number of tied parameters onto a single parameter
DELLA PIETRA, DELLA PIETRA, AND LAFFERTY: INDUCING FEATURES OF RANDOM FIELDS 3
associated with a non-binary feature. Having tied parameters is
often natural for a particular problem, but the presence of non-binary
features generally makes the estimation of parameters
more difficult.
An automorphism oe of a graph is a permutation of the vertices
that takes edges to edges: (u; v) 2 E if and only if (oeu; oev) 2 E.
A random field (E; V; f- is said to have homogeneous
features if for each feature f i and automorphism oe of the graph
there is a feature f j such that f j
W. If in addition - then the field is said to
be homogeneous. Roughly speaking, a homogeneous feature
contributes the same weight to the distribution no matter where
in the graph it appears. Homogeneous features arise naturally in
the application of Section 5.
The methods that we describe in this paper apply to exponential
models in general; that is, it is not essential that there is
an underlying graph structure. However, it will be convenient
to express our approach in terms of the random field models
described above.
B. Two optimization problems
Suppose that we are given an initial model q 0 2 D, a reference
distribution -
p, and a set of features In
practice, it is often the case that -
p is the empirical distribution of
a set of training samples ! (1) and is thus given
by
c(!)
is the number of times that
configuration ! appears among the training samples.
We wish to construct a probability distribution q ? 2 D that
accounts for these data, in the sense that it approximates -
but
does not deviate too far from q 0 . We measure distance between
probability distributions p and q in D using the Kullback-Leibler
divergence
p(!) log p(!)
Throughout this paper we use the notation
for the expectation of a function g : W ! R with respect to
the probability distribution p. For a function h : W ! R and a
distribution q, we use both the notation h ffi q and q h to denote the
generalized Gibbs distribution given by
Note that Z q (h) is not the usual partition function. It is a normalization
constant determined by the requirement that (h ffi q)(!)
sums to 1 over !, and can be written as an expectation:
There are two natural sets of probability distributions determined
by the data -
. The first is the set P(f; -
p) of
all distributions that agree with -
p as to the expected value of the
feature function f :
The second is the set Q(f; q 0 ) of generalized Gibbs distributions
based on q 0 with feature function f :
We let -
the closure of Q(f; q 0 ) in D (with respect
to the topology it inherits as a subset of Euclidean space).
There are two natural criteria for choosing an element q ? from
these sets:
ffl Maximum Likelihood Gibbs Distribution. Choose q ? to
be a distribution in -
likelihood with
respect to -
p:
ffl Maximum Entropy Constrained Distribution. Choose q ?
to be a distribution in P(f; -
p) that has maximum entropy
relative to q
Although these criteria are different, they determine the same
? . Moreover, this distribution is
the unique element of the intersection P(f; -
discuss in detail in Section 4.1 and Appendix A.
When -
p is the empirical distribution of a set of training examples
is equivalent to
maximizing the probability that the field p assigns to the training
data, given by
Y
Y
With sufficiently many parameters it is a simple matter to construct
a field for which D( -
arbitrarily small. This is the
classic problem of over training. The idea behind the method
proposed in this paper is to incrementally construct a field that
captures the salient properties of -
by incorporating an increasingly
detailed collection of features, allowing generalization to
new configurations; the resulting distributions are not absolutely
continuous with respect to the empirical distribution of the training
sample. The maximum entropy framework for parameter
estimation tempers the over training problem; however, the basic
problem remains, and is out of the scope of the present paper.
We now present the random field induction paradigm.
C. Inducing field interactions
We begin by supposing that we have a set of atomic features
each of which is supported by a single vertex. We use atomic
features to incrementally build up more complicated features.
The following definition specifies how we shall allow a field to
be incrementally constructed, or induced.
4 IEEE TRANSACTIONS PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19, NO. 4, APRIL 1997
Definition 1: Suppose that the field q is given by
f) . The features f i are called the active features of q. A
feature g is a candidate for q if either g 2 F atomic , or if g is of the
for an atomic feature a and an active
The set of candidate
features of q is denoted C(q).
In other words, candidate features are obtained by conjoining
atomic features with existing features. The condition on supports
ensures that each feature is supported by a path-connected subset
of G.
If g 2 C(q) is a candidate feature of q, then we call the 1-
parameter family of random fields q the induction
of q by g. We also define
G q (ff;
We think of G q (ff; g) as the improvement that feature g brings
to the model when it has weight ff. As we show in the following
section, G q (ff; g) is "-convex in ff. (We use the suggestive
notation "-convex and [-convex in place of the less mnemonic
concave and convex terminology.) We define G q (g) to be the
greatest improvement that feature g can give to the model while
keeping all of the other features' parameters fixed:
ff
We refer to G q (g) as the gain of the candidate g.
D. Incremental construction of random fields
We can now describe our algorithm for incrementally constructing
fields.
Field Induction Algorithm.
Initial
A reference distribution -
p and an initial model q 0 .
Output:
A field q ? with active features f
arg min
Algorithm:
(1) For each candidate g 2 C(q (n) ) compute the gain
G q (n) (g).
G q (n) (g) be the feature with the
largest gain.
(3) Compute
and go to step (1).
This induction algorithm has two parts: feature selection and
parameter estimation. Feature selection is carried out in steps (1)
and (2), where the feature yielding the largest gain is incorporated
into the model. Parameter estimation is carried out in step (3),
where the parameters are adjusted to best represent the reference
distribution. These two computations are discussed in more
detail in the following two sections.
III. FEATURE SELECTION
The feature selection step of our induction algorithm is based
upon an approximation. We approximate the improvement due
to adding a single candidate feature, measured by the reduction
in Kullback-Leibler divergence, by adjusting only the weight
of the candidate and keeping all of the other parameters of the
field fixed. In general this is only an estimate, since it may well
be that adding a feature will require significant adjustments to
all of the parameters in the new model. From a computational
perspective, approximating the improvement in this way can
enable the simultaneous evaluation of thousands of candidate
features, and makes the algorithm practical. In this section we
present explain the feature selection step in detail.
Proposition 1: Let G q (ff; g), defined in (2), be the approximate
improvement obtained by adding feature g with parameter
ff to the field q. Then if g is not constant, G q (ff; g) is strictly
"-convex in ff and attains its maximum at the unique point -
ff
satisfying
Proof: Using the definition (1) of the Kullback-Leibler divergence
we can write
G q (ff;
p(!) log
\Theta
e ffg
\Theta e ffg
Thus
@
@ff
G q (ff;
Moreover,
q[ge ffg
Hence, @ 2
so that G q (ff; g) is "-convex in ff. If
g is not constant, then @ 2
which is minus the variance
of g with respect to q ffg , is strictly negative, so that G q (ff; g) is
strictly convex.
When g is binary-valued, its gain can be expressed in a particularly
nice form. This is stated in the following proposition,
whose proof is a simple calculation.
Proposition 2: Suppose that the candidate g is binary-valued.
Then G q (ff; g) is maximized at
and at this value,
DELLA PIETRA, DELLA PIETRA, AND LAFFERTY: INDUCING FEATURES OF RANDOM FIELDS 5
are Bernoulli random variables given by
For features that are not binary-valued, but instead take values
in the non-negative integers, the parameter -
ff that solves (3) and
thus maximizes G q (ff; g) cannot, in general, be determined in
closed form. This is the case for tied binary features, and it
applies to the application we describe in Section 5. For these
cases it is convenient to rewrite (3) slightly. Let
be the total probability assigned to the event that the feature g
takes the value k. Then (3) becomes
@
G q (log fi;
This equation lends itself well to numerical solution. The general
shape of the curve fi 7! fi@=@fi G q (log fi; g) is shown in

Figure

1.
Fig. 1. Derivative of the gain
The limiting value of fi@G q (log fi; g)=@fi as
N . The solution to equation (4) can be found using Newton's
method, which in practice converges rapidly for such functions.
When the configuration space W is large, so that the coefficients
k cannot be calculated by summing over all configura-
tions, Monte Carlo techniques may be used to estimate them.
It is important to emphasize that the same set of random configurations
can be used to estimate the coefficients g k for each
candidate g simultaneously. Rather than discuss the details of
Monte Carlo techniques for this problem we refer to the extensive
literature on this topic. We have obtained good results using
the standard technique of Gibbs sampling [17] for the problem
we describe in Section 5.
IV. PARAMETER ESTIMATION
In this section we present an algorithm for selecting the parameters
associated with the features of a random field. The
algorithm is a generalization of the Generalized Iterative Scaling
algorithm of Darroch and Ratcliff [12]. It reduces to the
algorithm when the features sum to a constant;
however, the new algorithm does not make this restriction.
Throughout this section we hold the set of features
the initial model q 0 and the reference distribution
fixed, and we simplify the notation accordingly. In
particular, we write fl ffi q instead of (fl \Delta f) ffi q for fl 2 R n . We
assume that -
This condition is
commonly written -
it is equivalent to D( -
A description of the algorithm requires an additional piece of
notation. Let
If the features are binary, then f # (!) is the total number of
features that are "on" for the configuration !.
Improved Iterative Scaling.
Initial
A reference distribution -
p and an initial model q 0 , with
non-negative features f
Output:
The distribution q
Algorithm:
(1) For each i let fl (k)
be the unique solution of
(3) If q (k) has converged, set q
go to step (1).
In other words, this algorithm constructs a distribution q
lim
i is determined
as the solution to the equation
When used in the n-th iteration of the field induction algorithm,
where a candidate feature is added to the field
choose the initial distribution q 0 to be q
ffg , where -
ff is the
parameter that maximizes the gain of g. In practice, this provides
a good starting point from which to begin iterative scaling. In
fact, we can view this distribution as the result of applying one
iteration of an Iterative Proportional Fitting Procedure [5], [9]
to project q ffg onto the linear family of distributions with g-
marginals constrained to -
p[g].
Our main result in this section is
Proposition 3: Suppose q (k) is the sequence in D determined
by the Improved Iterative Scaling algorithm. Then D( -
decreases monotonically to D( -
converges to q
arg min
In the remainder of this section we present a self-contained
proof of the convergence of the algorithm. The key idea of
the proof is to express the incremental step of the algorithm in
terms of an auxiliary function which bounds from below the
log-likelihood objective function. This technique is the standard
means of analyzing the EM algorithm [13], but it has not previously
been applied to iterative scaling. Our analysis of iterative
scaling is different and simpler than previous treatments. In
particular, in contrast to Csisz-ar's proof of the Darroch-Ratcliff
6 IEEE TRANSACTIONS PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19, NO. 4, APRIL 1997
procedure [10], our proof does not rely upon the convergence of
alternating I-projection [9].
We begin by formulating the basic duality theorem which
states that the maximum likelihood problem for a Gibbs distribution
and the maximum entropy problem subject to linear
constraints have the same solution. We then turn to the task of
computing this solution. After introducing auxiliary functions in
a general setting, we apply this method to prove convergence of
the Improved Iterative Scaling algorithm. We finish the section
by discussing Monte Carlo methods for estimating the equations
when the size of the configuration space prevents the explicit
calculation of feature expectations.
A. Duality
The duality between the maximum likelihood and maximum
entropy problems is expressed in the following Proposition.
Proposition 4: Suppose that -
. Then there exists a
Moreover, any of these four properties determines q ? uniquely.
This result is well known, although perhaps not quite in this
packaging. In the language of constrained optimization, it expresses
the fact that the maximum likelihood problem for Gibbs
distributions is the convex dual to the maximum entropy problem
for linear constraints. Property (2) is called the Pythagorean
property since it resembles the Pythagorean theorem if we imagine
that D(p k q) is the square of Euclidean distance and (p; q
are the vertices of a right triangle.
We include a proof of this result in Appendix A to make this
paper self-contained and also to carefully address the technical
issues arising from the fact that Q is not closed. The proposition
would not be true if we replaced -
Q with Q; in fact,
might be empty. Our proof is elementary and does not rely
on the Kuhn-Tucker theorem or other machinery of constrained
optimization.
B. Auxiliary functions
We now turn to the task of computing q ? . Fix -
p and let
R be the log-likelihood objective function
Definition 2: A function A : R n \Theta D ! R is an auxiliary
function for L if
(1) For all q 2 D and fl 2 R n
(2) A(fl; q) is continuous in q 2 D and C 1 in fl 2 R n with
d
dt
d
dt
We can use an auxiliary function A to construct an iterative
algorithm for maximizing L. We start with q
recursively define q (k+1) by
It is clear from property (1) of the definition that each step of
this procedure increases L. The following proposition implies
that in fact the sequence q (k) will reach the maximum of L.
Proposition 5: Suppose q (k) is any sequence in D with
where
increases monotonically to max
L(q) and q (k)
converges to q
L(q).
Equation (6) assumes that the supremum sup fl A(fl; q (k) ) is
achieved at finite fl. In Appendix B, under slightly stronger
assumptions, we present an extension that allows some components
of fl (k) to take the value \Gamma1.
To use the proposition to construct a practical algorithm we
must determine an auxiliary function A(fl; q) for which fl (k)
satisfying the required condition can be determined efficiently.
In Section 4.3 we present a choice of auxiliary function which
yields the Improved Iterative Scaling updates.
To prove Proposition 5 we first prove three lemmas.
Lemma 1: If m 2 D is a cluster point of q (k) , then A(fl; m) -
Proof: Let q (k l ) be a sub-sequence converging to m. Then
for any fl
The first inequality follows from property (6) of fl (nk ) . The second
and third inequalities are a consequence of the monotonicity
of L(q (k) ). The lemma follows by taking limits and using the
fact that L and A are continuous.
Lemma 2: If m 2 D is a cluster point of q (k) , then
d
Proof: By the previous lemma, A(fl; m) - 0 for all fl. Since
means that is a maximum of A(fl; m)
so that
d
dt
d
dt
Lemma 3: Supposefq (k) g is any sequence with only one cluster
point q   . Then q (k) converges to q   .
Proof: Suppose not. Then there exists an open set B containing
q   and a subsequence q (nk ) 62 B. Since D is compact, q (nk )
has a cluster point q 0
62 B. This contradicts the assumption that
has a unique cluster point.
Proof of Proposition 5: Suppose that m is a cluster point of
q (k) . Then it follows from Lemma 2 that d
0, and so
Q by Lemma 2 of Appendix A. But q ? is the
only point in
Proposition 4. It follows from Lemma 3
that q (k) converges to q ? .
In

Appendix

B we prove an extension of Proposition 5 that
allows the components of fl to equal \Gamma1. For this extension,
we assume that all the components of the feature function f are
non-negative:
This is not a practical restriction since we can replace f i by
C. Improved Iterative Scaling
We now prove the monotonicity and convergence of the Improved
Iterative Scaling algorithm by applying Proposition 5 to
a particular choice of auxiliary function. We now assume that
each component of the feature function f is non-negative.
For
. It is easy to check that A extends to a
continuous function on (R [ \Gamma1) n \Theta D.
Lemma 4: A(fl; q) is an extended auxiliary function for L(q).
The key ingredient in the proof of the lemma is the "-convexity
of the logarithm and the [-convexity of the exponential, as expressed
in the inequalities
e
log x -
Proof of Lemma 4: Because A extends to a continuous function
on (R [ \Gamma1) n \Theta D, it suffices to prove that it satisfies
properties (1) and (2) of Definition 2. To prove property (1) note
that
Equality (10) is a simple calculation. Inequality (11) follows
from inequality (9). Inequality (12) follows from the definition
of f # and Jensen's inequality (8). Property (2) of Definition 2 is
straightforward to verify.
Proposition 3 follows immediately from the above lemma and
the extended Proposition 5. Indeed, it is easy to check that fl (k)
defined in Proposition 3 achieves the maximum of A(fl; q (k) ),
so that it satisfies the condition of Proposition 5 in Appendix B.
D. Monte Carlo methods
The Improved Iterative Scaling algorithm described in the
previous section is well-suited to numerical techniques since all
of the features take non-negative values. In each iteration of this
algorithm it is necessary to solve a polynomial equation for each
feature f i . That is, we can express equation 5 in the form
a
where M is the largest value of f #
a
where q (k) is the field for the k-th iteration and fi
i . This
equation has no solution precisely when a (k)
Otherwise, it can be efficiently solved using Newton's method
since all of the coefficients a (k)
are non-negative. When
Monte Carlo methods are to be used because the configuration
space W is large, the coefficients a (k)
m;i can be simultaneously
estimated for all i and m by generating a single set of samples
from the distribution q (k) .
V. APPLICATION: WORD MORPHOLOGY
Word clustering algorithms are useful for many natural language
processing tasks. One such algorithm [6], called mutual
information clustering, is based upon the construction of simple
bigram language models using the maximum likelihood crite-
rion. The algorithm gives a hierarchical binary classification of
words that has been used for a variety of purposes, including the
construction of decision tree language and parsing models, and
sense disambiguation for machine translation [7].
A fundamental shortcoming of the mutual information word
clustering algorithm given in [6] is that it takes as fundamental
the word spellings themselves. This increases the severity of
the problem of small counts that is present in virtually every
statistical learning algorithm. For example, the word "Hamil-
tonianism" appears only once in the 365,893,263-word corpus
used to collect bigrams for the clustering experiments described
in [6]. Clearly this is insufficient evidence on which to base a
statistical clustering decision. The basic motivation behind the
feature-based approach is that by querying features of spellings,
a clustering algorithm could notice that such a word begins with
a capital letter, ends in "ism" or contains "ian," and profit from
how these features are used for other words in similar contexts.
In this section we describe how we applied the random field
induction algorithm to discover morphological features of words,
and we present sample results. This application demonstrates
how our technique gradually sharpens the probability mass from
the enormous set of all possible configurations, in this case ASCII
strings, onto a set of configurations that is increasingly similar to
those in the training sample. It achieves this by introducing both
"positive" features which many of the training samples exhibit,
as well as "negative" features which do not appear in the sample,
or appear only rarely. A description of how the resulting features
8 IEEE TRANSACTIONS PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19, NO. 4, APRIL 1997
were used to improve mutual information clustering is given in
[20], and is beyond the scope of the present paper; we refer the
reader to [6], [20] for a more detailed treatment of this topic.
In Section 5.1 we formulate the problem in terms of the notation
and results of Sections 2, 3, and 4. In Section 5.2 we
describe how the field induction algorithm is actually carried out
in this application. In Section 5.3 we explain the results of the
induction algorithm by presenting a series of examples.
A. Problem formulation
To discover features of spellings we take as configuration
space the set of all strings in the ASCII alphabet A. We
construct a probability distribution p(!) on W by first predicting
the length j ! j, and then predicting the actual spelling; thus,
l is the length distribution
and p s is the spelling distribution. We take the length distribution
as given. We model the spelling distribution p s
of length l as a random field. Let W l be the configuration space
of all ASCII strings of length l. Then j W l since each
is an ASCII character.
To reduce the number of parameters, we tie features, as described
in Section 2.1, so that a feature has the same weight
independent of where it appears in the string. Because of this it
is natural to view the graph underlyingW l as a regular l-gon. The
group of automorphisms of this graph is the set of all rotations,
and the resulting field is homogeneous as defined in Section 2.
Not only is each field p s homogeneous, but in addition, we tie
features across fields for different values of l. Thus, the weight
- f of a feature is independent of l. To introduce a dependence
on the length, as well as on whether or not a feature applies at
the beginning or end of a string, we adopt the following artificial
construction. We take as the graph of W l an (l + 1)-gon rather
than an l-gon, and label a distinguished vertex by the length,
keeping this label held fixed.
To complete the description of the fields that are induced, we
need to specify the set of atomic features. The atomic features
that we allow fall into three types. The first type is the class of
features of the form
where c is any ASCII character, and v denotes an arbitrary character
position in the string. The second type of atomic features
involve the special vertex   that carries the length of the string.
These are the features
The atomic feature f v;<> introduces a dependence on whether a
string of characters lies at the beginning or end of the string, and
the atomic features f v;l introduce a dependence on the length of
the string. To tie together the length dependence for long strings,
we also introduce an atomic feature f v;7+ for strings of length 7
or greater.
The final type of atomic feature asks whether a character lies
in one of four sets, [a-z], [A-Z], [0-9], [@-&], denoting
arbitrary lowercase letters, uppercase letters, digits, and punctu-
ation. For example, the atomic feature
tests whether or not a character is lowercase.
To illustrate the notation that we use, let us suppose that the the
following features are active for a field: "ends in ism," "a string
of at least 7 characters beginning with a capital letter" and "con-
tains ian." Then the probability of the word "Hamiltonianism"
would be given as
l
l (14)Z 14
Here the -'s are the parameters of the appropriate features, and
we use the characters < and > to denote the beginning and ending
of a string (more common regular expression notation would be
- and $). The notation 7+<[A-Z] thus means "a string of at
least 7 characters that begins with a capital letter," corresponding
to the feature
where u and v are adjacent positions in the string, recalling
from Definition 2.1 that we require the support of a feature to be
a connected subgraph. Similarly, ism> means "ends in -ism"
and corresponds to the feature
where u; v; w; x are adjacent positions in the string and ian
means "contains ian," corresponding to the feature
B. Description of the algorithm
We begin the random field induction algorithm with a model
that assigns uniform probabilityto all strings. We then incrementally
add features to a random field model in order to minimize
the Kullback-Leibler divergence between the field and the unigram
distribution of the vocabulary obtained from a training
corpus. The length distribution is taken according to the lengths
of words in the empirical distribution of the training data. The
improvement to the model made by a candidate feature is evaluated
by the reduction in relative entropy, with respect to the
unigram distribution, that adding the new feature yields, keeping
the other parameters of the model fixed. Our learning algorithm
incrementally constructs a random field to describe those
features of spellings that are most informative.
At each stage in the induction algorithm, a set of candidate
features is constructed. Because the fields are homogeneous, the
set of candidate features can be viewed as follows. Each active
feature can be expressed in the form
substring s appears in !
where s is a string in the extended alphabet A of ASCII characters
together with the macros [a-z], [A-Z], [0-9], [@-&], and
DELLA PIETRA, DELLA PIETRA, AND LAFFERTY: INDUCING FEATURES OF RANDOM FIELDS 9
the length labels   and <>. If ff s g s2S is the set of active
features, (including ffl, the empty string) using this repre-
sentation, then the set of candidate features is precisely the set
concatenation of strings.
As required by Definition 2, each such candidate increases the
support of an active feature by a single adjacent vertex.
Since the model assigns probability to arbitrary word strings,
the partition function Z l can be computed exactly for only the
smallest string lengths l. We therefore compute feature expectations
using a random sampling algorithm. Specifically, we
use the Gibbs sampler to generate 10,000 spellings of random
lengths. When computing the gain G q (g) of a candidate fea-
ture, we use these spellings to estimate the probability g k that
the candidate feature g occurs k times in a spelling (see equation
(4)-for example, the feature f v;[a-z] occurs two times in
the string The), and then solve for the corresponding fi using
Newton's method for each candidate feature. It should be emphasized
that only a single set of random spellings needs to be
generated; the same set can be used to estimate g k for each
candidate g. After adding the best candidate to the field, all of
the feature weights are readjusted using the Improved Iterative
Scaling algorithm. To carry out this algorithm, random spellings
are again generated, this time incorporating the new feature,
yielding Monte Carlo estimates of the coefficients a (k)
m;i . Recall
that a (k)
m;i is the expected number of times that feature i appears
(under the substring representation for homogeneous features)
in a string for which there is a total of m active features (see
equation 14)). Given estimates for these coefficients, Newton's
method is again used to solve equation (14), to complete a single
iteration of the iterative scaling algorithm. After convergence of
the Kullback-Leibler divergence, the inductive step is complete,
and a new set of candidate features is considered.
C. Sample results
We began with a uniform field, that is, a field with no features
at all. For this field, all ASCII strings of a given length are equally
likely, and the lengths are drawn from a fixed distribution. Here
is a sample of strings drawn from this distribution:
-, mo, !ZP*@, m/TLL, ks;cm 3, *LQdR, D, aWf,
5&TL|4, tc, ?!@, sNeiO+, wHo8zBr", pQlV, m, H!&,
Y-:Du:, 1xCl, 1!'J#F*u., w=idHnM), -, 2, 2leW2,
T, -(sOc1+2ADe, &, np9oH, i;, $6, qgO+[, xEv, #U,
O)[83COF, =|B|7%cR, Mqq, ?!mv, n=7G, $i9GAJ D, 5,
,=, +u6@I9:, +, =D, 2E#vz@3-nu;.+s, 3xJ, GDWeqL,
R,3R, !7v, FX,@y, 4p cY2hU, -
It comes as no surprise that the first feature the induction algorithm
chooses is [a-z]; it simply observes that characters
should be lowercase. The maximum likelihood (maximum en-
tropy) weight for this feature is This means
that a string with a lowercase letter in some position is about 7
times more likely than the same string without a lowercase letter
in that position.
When we now draw strings from the new distribution (using
annealing to concentrate the distribution on the more probable
strings), we obtain spellings that are primarily made up of lowercase
letters, but that certainly do not resemble English words:
m, r, xevo, ijjiir, b, to, jz, gsr, wq, vf, x, ga,
msmGh, pcp, d, oziVlal, hzagh, yzop, io, advzmxnv,
ijv bolft, x, emx, kayerf, mlj, rawzyb, jp, ag,
ctdnnnbg, wgdw, t, kguv, cy, spxcq, uzflbbf,
dxtkkn, cxwx, jpd, ztzh, lv, zhpkvnu, l - , r, qee,
nynrx, atze4n, ik, se, w, lrh, hp+, yrqyka'h,
zcngotcnx, igcump, zjcjs, lqpWiqu, cefmfhc, o, lb,
fdcY, tzby, yopxmvk, by, fz,, t, govyccm,
ijyiduwfzo, 6xr, duh, ejv, pk, pjw, l, fl, w
In the following table we show the first 10 features that the
algorithm induced, together with their associated parameters.
Several things are worth noticing. The second feature chosen was
[a-z][a-z], which denotes adjacent lowercase characters.
The third feature added was the letter e, which is the most
common letter. The weight for this feature is
The next feature introduces the first dependence on the length of
the string: [a-z]>1 denotes the feature "a one character word
ending with a lowercase letter." Notice that this feature has a
small weight of 0.04, corresponding to our intuition that such
words are uncommon. Similarly, the features z, q, j, and x
are uncommon, and thus receive small weights. The appearance
of the feature * is explained by the fact that the vocabulary for
our corpus is restricted to the most frequent 100,000 spellings,
and all other words receive the "unknown word" spelling *,
which is rather frequent. (The "end-of-sentence" marker, which
makes its appearance later, is given the spelling |.)
feature [a-z] [a-z][a-z] e [a-z]>1 t
feature * z q j x
Shown below are spellings obtained by Gibbs sampling from the
resulting collection of fields.
frk, et, egeit, edet, eutdmeeet, ppge, A, dtgd,
falawe, etci, eese, ye, epemtbn, tegoeed, ee, *mp,
temou, enrteunt, ore, erveelew, heyu, rht, *,
lkaeu, lutoee, tee, mmo, eobwtit, weethtw, 7, ee,
teet, gre, /, *, eeeteetue, hgtte, om, he, *,
stmenu, ec, ter, eedgtue, iu, ec, reett, *,
ivtcmeee, vt, eets, tidpt, lttv, *, etttvti, ecte,
X, see, *, pi, rlet, tt, *, eot, leef, ke, *,
tet, iwteeiwbeie, yeee, et, etf, *, ov
After inducing 100 features, the model finally begins to be
concentrated on spellings that resemble actual words to some
extent, particularly for short strings. At this point the algorithm
has discovered, for example, that the is a very common 3-letter
word, that many words end in ed, and that long words often end
in ion. A sample of 10 of the first 100 features induced, with
their appropriate weights is shown in the table below.
. ,>1 3<the tion 4<th y> ed> ion>7+ ent 7+<c
22.36
thed, and, thed, toftion, |, ieention, cention, |,
ceetion, ant, is, seieeet, cinention, and, .,
tloned, uointe, feredten, iined, sonention,
inathed, other, the, id, and, ,, of, is, of, of, ,,
lcers, ,, ceeecion, ,, roferented, |, ioner, ,, |,
the, the, the, centention, ionent, asers, ,,
ctention, |, of, thed, of, uentie, of, and, ttentt,
in, rerey, and, |, sotth, cheent, is, and, of,
thed, rontion, that, seoftr
A sample of the first 1000 features induced is shown in the
table below, together with randomly generated spellings. No-
tice, for example, that the feature [0-9][0-9] appears with a
surprisingly high weight of 9382.93. This is due to the fact that
if a string contains one digit, then it's very likely to contain two
digits. But since digits are relatively rare in general, the feature
[0-9] is assigned a small weight of 0.038. Also, according to
the model, a lowercase letter followed by an uppercase letter is
rare.
s> <re ght> 3<[A-Z] ly> al>7+ ing>
[a-z][A-Z] 't> ed>7+ er>7+ ity ent>7+ [0-9][0-9]
qu ex ae ment ies <wh ate
was, reaser, in, there, to, will, ,, was, by,
homes, thing, be, reloverated, ther, which,
conists, at, fores, anditing, with, Mr., proveral,
the, ,, *, on't, prolling, prothere, ,, mento,
at, yaou, 1, chestraing, for, have, to, intrally,
of, qut, ., best, compers, *, cluseliment, uster,
of, is, deveral, this, thise, of, offect, inatever,
thifer, constranded, stater, vill, in, thase, in,
youse, menttering, and, ., of, in, verate, of, to
Finally, we visit the state of the model after inducing 1500
features to describe words. At this point the model is making
more refined judgements regarding what is to be considered a
word and what is not. The appearance of the features {}>
and \[@-&]{, is explained by the fact that in preparing our
corpus, certain characters were assigned special "macro" strings.
For example, the punctuation characters $, _, %, and & are
represented in our corpus as \${}, \_{}, \%{}, and \&{}.
As the following sampled spellings demonstrate, the model has
at this point recognized the existence of macros, but has not yet
discerned their proper use.
7+<inte prov <der <wh 19 ons>7+ ugh ic>
4.23 5.08 0.03 2.05 2.59 4.49 5.84 7.76
sys ally 7+<con ide nal {}> qui \[@-&]{
4.78 6.10 5.25 4.39 2.91 120.56 18.18 913.22
iz IB <inc <im iong $ ive>7+ <un
the, you, to, by, conthing, the, ., not, have,
devened, been, of, |, F., in, have, -, ,,
intering, *, ation, said, prouned, *,
suparthere, in, mentter, prement, intever, you, .,
and, B., gover, producits, alase, not, conting,
comment, but, |, that, of, is, are, by, from, here,
incements, contive, ., evined, agents, and, be, -,
thent, distements, all, -, has, will, said,
resting, had, this, was, intevent, IBM, whree,
acalinate, herned, are, *, O., |, 1980, but,
will, *, is, ., to, becoment, ., with, recall,
has, |, nother, ments, was, the, to, of,
stounicallity, with, camanfined, in, this,
intations, it, conanament, out, they, you
While clearly the model still has much to learn, it has at this point
compiled a significant collection of morphological observations,
and has traveled a long way toward its goal of statistically characterizing
English spellings.
VI. EXTENSIONS AND RELATIONS TO OTHER APPROACHES
In this section we briefly discuss some relations between our
incremental feature induction algorithm for random fields and
other statistical learning paradigms. We also present some possible
extensions and improvements of our method.
A. Conditional exponential models
Almost all of what we have presented here carries over to
the more general setting of conditional exponential models, including
the Improved Iterative Scaling algorithm. For general
conditional there may be no underlyingran-
dom field, but with features defined as binary functions f(x; y),
the same general approach is applicable. The feature induction
method for conditional exponential models is demonstrated for
several problems in statistical machine translation in [3], where
it is presented in terms of the principle of maximum entropy.
B. Decision trees
Our feature induction paradigm also bears some resemblence
to various methods for growing classification and regression
trees. Like decision trees, our method builds a top-down classification
that refines features. However, decision trees correspond
to constructing features that have disjoint support.
To explain, recall that a decision tree determines a partition -
of a context random variable X 2 X in order to predict the actual
class of the context, represented by a random variable Y 2 Y.
Each leaf in the tree corresponds to a sequence of binary features
where n" denotes the parent of node n, each feature f n is a question
which splits X , and where each f n is the negation :fn of the
question asked at its sibling node. The distribution assigned to
a leaf l is simply the empirical distribution on Y determined by
the training samples (x; y) 2 X \Theta Y for which Each
leaf l is characterized by the conjunction of these features, and
different leaves correspond to conjunctionswith disjoint support.
In contrast, our feature induction algorithm generally results in
features that have overlapping support. The criterion of evaluating
questions in terms of the amount by which they reduce the
conditional entropy of Y corresponds to our criterion of maximizing
the reduction in Kullback-Leibler divergence, G q (g),
over all candidate features g for a field q.
By modifying our induction algorithm in the following way,
we obtain an algorithm closely related to standard methods for
growing binary decision trees. Instead of considering the 1-
parameter family of fields q -;g to determine the best candidate
we consider the 2-parameter family of fields given by
Since the features a - f and (:a) - f have disjoint support, the
improvement obtained by adding both of them is given byG q (a-
In general, the resulting distribution is not
absolutely continuous with respect to the empirical distribution.
If the random variable Y can take on M values y
the standard decision tree algorithm is obtained if at the n-th stage
DELLA PIETRA, DELLA PIETRA, AND LAFFERTY: INDUCING FEATURES OF RANDOM FIELDS 11
we add the 2M (disjoint) features f n
. Maximum likelihood training of the
parameters of these features recovers the empirical distribution
of the data at node n.
C. Extensions
As mentioned in Section 1, our approach differs from the
most common applications of statistical techniques in computer
vision, since a typical application of our method involves the
estimation of thousands of free parameters. Yet the induction
technique may not scale well to large 2-dimensional image prob-
lems. One potential difficulty is that the degree of the polynomials
in the Improved Iterative Scaling algorithm could be quite
large, and it could be difficult to obtain reliable estimates of
the coefficients since Monte Carlo sampling might not exhibit
sufficiently many instances of the desired features. The extent
to which this is a significant problem is primarily an empirical
issue, dependent on the particular domain to which the method
is applied.
The random field induction method presented in this paper
is not definitive; there are many possible variations on the basic
theme, which is to incrementally construct an increasingly
detailed exponential model to approximate the reference distribution
p. Because the basic technique is based on a greedy algo-
rithm, there are of course many ways for improving the search
for a good set of features. The algorithm presented in Section 2
is in some respects the most simple possible within the general
framework. But it is also computationally intensive. A natural
modification would be to add several of the top candidates
at each stage. While this should increase the overall speed of
the induction algorithm, it would also potentially result in more
redundancy among the features, since the top candidates could
be correlated. Another modification of the algorithm would be
to add only the best candidate at each step, but then to carry out
parameter estimation only after several new features had been
added to the field. It would also be natural to establish a more
Bayesian framework in which a prior distribution on features
and parameters is incorporated. This could enable a principled
approach for deciding when the feature induction is complete.
While there is a natural class of conjugate priors for the class of
exponential models that we use [14], the problem of incorporating
prior knowledge about the set of candiate features is more
challenging.




I. DUALITY
In this Appendix we prove Proposition 4 restated here.
Proposition 4: Suppose that -
. Then there exists a
Moreover, any of these four properties determines q ? uniquely.
Our proof of the proposition will use a few lemmas. The first
two lemmas we state without proof.
Lemma 1:
(1) D(p k q) is a non-negative, extended real-valued function
on D \Theta D.
strictly convex in p and q separately.
Lemma 2:
(1) The map (fl; p) 7! fl ffi p is smooth in (fl; p) 2 R n \Theta D.
(2) The derivative of D(p k - ffi q) with respect to - is
d
dt
Lemma 3: If -
Q is nonempty.
Proof: Define q ? by property (3) of Proposition 4; that is,
To see that this makes sense, note
that since -
k q) is not identically 1 on -
Q. Also,
is continuous and strictly convex as a function of q.
Thus, since -
Q is closed, D( -
attains its minimum at a unique
point
Q. We will show that q ? is also in P. Since -
Q is
closed under the action of R n , -
Q for any -. Thus
by the definition of q ? , is a minimum of the function
Taking derivatives with respect to - and
using Lemma A.2 we conclude q ? [f
Lemma 4: If q
Q then for any p 2 P and q 2 -
Proof: A straightforward calculation shows that
for any p 1 It follows from this
identity and the continuity of D that
Q. The lemma follows by taking
Proof of Proposition 4: Choose q ? to be any point in
Q.
Such a q ? exists by Lemma A.3. It satisfies property (1) by
definition, and it satisfies property (2) by Lemma A.4. As a
consequence of property (2), it also satisfies properties (3) and
(4). To check property (3), for instance, note that if q is any point
in -
Q, then D( -
It remains to prove that each of the four properties (1)-(4)
determines q ? uniquely. In other words, we need to show that
if m is any point in D satisfying any of the four properties
. Suppose that m satisfies property (1).
Then by property (2) for q ? with
the same argument with q ? and m reversed again proves that
. Suppose that m satisfies property (3). Then
where the second equality follows from property (2) for q ? . Thus
similar proof shows that once again
II. DEALING WITH 1
In this Appendix we prove an extension of Proposition 5 that
allows the components of fl to equal \Gamma1. For this extension,
we assume that all of the components of the feature function f
are non-negative: f i (!) - 0 for all i and all !. This can be
assumed with no loss of generality since we can replace f i by
necessary.
denote the partially extended real numbers with
the usual topology. The operations of addition and exponentiation
extend continuously to R [ \Gamma1. Let S be the open subset
of (R [ \Gamma1) n \Theta D defined by
Observe that R n \Theta D is a dense subset of S. The map (fl; q) 7!
which up to this point we defined only for finite fl, extends
uniquely to a continuous map from all of S to D. (The condition
on (fl; q) 2 S ensures that the normalization in the definition of
even if fl is not finite.)
Definition 3: We call a function A an extended
auxiliary function for L if when restricted to R n \Theta D it is
an ordinary auxiliary function in the sense of Definition 2, and
if, in addition, it satisfies property (1) of Definition 2 for any
even if fl is not finite.
Note that if an ordinary auxiliary function extends to a continuous
function on S , then the extension is an extended auxiliary
function.
We have the following extension of Proposition 5:
Proposition 5: Suppose the feature function f satisfies the
non-negativity condition 7 and suppose A is an extended auxiliary
function for L. Then the conclusion of Proposition5 continues
to hold if the condition on fl (k) is replaced by: (fl
S and A(fl
Lemma 1 is valid under the altered condition on
since A(fl; q) satisfies property (1) of Definition 2 for all
As a consequence, Lemma 2 also is valid, and the
proof of Proposition 5 goes through without change.
III.

ACKNOWLEDGEMENTS

Part of the research presented in this paper was carried out
while the authors were with the IBM Thomas J. Watson Re-search
Center in Yorktown Heights, New York. Stephen Della
Pietra and Vincent Della Pietra's work was partially supported
by ARPA under grant N00014-91-C-0135. John Lafferty's work
was partially supported by NSF and ARPA under grants IRI-
9314969 and N00014-92-C-0189.



--R

"A variational method for estimating the parameters of MRF from complete or incomplete data,"
"Noncausal Gauss Markovrandom fields: Parameter structure and estimation,"
"A maximum entropy approach to natural language processing,"
Classification and Regression Trees
"A note on approximations to discrete probability distributions,"
"Class-based n-gram models of natural language,"
"A statistical approach to machine translation,"
"An iterative Gibbsian technique for reconstruction of m-ary images,"
"I-Divergence geometry of probability distributions and minimization problems,"
"A geometric interpretation of Darroch and Ratcliff's generalized iterative scaling,"
"Information geometry and alternating minimization procedures,"
"Generalized iterative scaling for log-linear models,"
"Maximum likelihood from incomplete data via the EM algorithm,"
"Conjugate priors for exponential families,"
"Convergence of some partially parallel Gibbs samplers with annealing,"
"Optimal spectral structure of reversible stochastic matrices, Monte Carlo methods and the simulation of Markov random fields,"
"Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images,"
"ConstrainedMonte Carlo maximum likelihood for dependent data (with discussion)"

"Automatic word classification using features of spellings,"
"Partition function estimation of Gibbs random field images using Monte Carlo simulations,"
"Estimation and annealing for Gibbsian fields,"
--TR

--CTR
Wei Li , Andrew McCallum, Rapid development of Hindi named entity recognition using conditional random fields and feature induction, ACM Transactions on Asian Language Information Processing (TALIP), v.2 n.3, p.290-294, September
Victor Lavrenko , Jeremy Pickens, Music modeling with random fields, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada
S. Dharanipragada , M. Franz , J. S. McCarley , T. Ward , W.-J. Zhu, Segmentation and detection at IBM: hybrid statistical models and two-tiered clustering, Topic detection and tracking: event-based information organization, Kluwer Academic Publishers, Norwell, MA, 2002
Fuchun Peng , Fangfang Feng , Andrew McCallum, Chinese segmentation and new word detection using conditional random fields, Proceedings of the 20th international conference on Computational Linguistics, p.562-es, August 23-27, 2004, Geneva, Switzerland
Iain Murray , Zoubin Ghahramani, Bayesian learning in undirected graphical models: approximate MCMC algorithms, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.392-399, July 07-11, 2004, Banff, Canada
Andrew McCallum , Wei Li, Early results for named entity recognition with conditional random fields, feature induction and web-enhanced lexicons, Proceedings of the seventh conference on Natural language learning at HLT-NAACL 2003, p.188-191, May 31, 2003, Edmonton, Canada
Takehito Utsuro , Manabu Sassano , Kiyotaka Uchimoto, Combining outputs of multiple Japanese named entity chunkers by stacking, Proceedings of the ACL-02 conference on Empirical methods in natural language processing, p.281-288, July 06, 2002
Kishore Papineni, Why inverse document frequency?, Second meeting of the North American Chapter of the Association for Computational Linguistics on Language technologies 2001, p.1-8, June 01-07, 2001, Pittsburgh, Pennsylvania
Rob Koeling, Chunking with maximum entropy models, Proceedings of the 2nd workshop on Learning language in logic and the 4th conference on Computational natural language learning, September 13-14, 2000, Lisbon, Portugal
Karl-Michael Schneider, Information extraction from calls for papers with conditional random fields and layout features, Artificial Intelligence Review, v.25 n.1-2, p.67-77, April     2006
Jeremy Pickens , Andrew MacFarlane, Term context models for information retrieval, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
Jason Eisner, Parameter estimation for probabilistic finite-state transducers, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania
Andrew Smith , Trevor Cohn , Miles Osborne, Logarithmic opinion pools for conditional random fields, Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, p.18-25, June 25-30, 2005, Ann Arbor, Michigan
Doug Beeferman , Adam Berger , John Lafferty, A model of lexical attraction and repulsion, Proceedings of the eighth conference on European chapter of the Association for Computational Linguistics, p.373-380, July 07-12, 1997, Madrid, Spain
Iain Bancarz , Miles Osborne, Improved iterative scaling can yield multiple globally optimal models with radically differing performance levels, Proceedings of the 19th international conference on Computational linguistics, p.1-7, August 24-September 01, 2002, Taipei, Taiwan
Jianfeng Gao , Andi Wu , Mu Li , Chang-Ning Huang , Hongqiao Li , Xinsong Xia , Haowei Qin, Adaptive Chinese word segmentation, Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics, p.462-es, July 21-26, 2004, Barcelona, Spain
Takehito Utsuro , Takashi Miyata , Yuji Matsumoto, General-to-specific model selection for subcategorization preference, Proceedings of the 17th international conference on Computational linguistics, p.1314-1320, August 10-14, 1998, Montreal, Quebec, Canada
A. L. Yuille , Anand Rangarajan, The concave-convex procedure, Neural Computation, v.15 n.4, p.915-936, April
Robert Malouf, Markov models for language-independent named entity recognition, proceeding of the 6th conference on Natural language learning, p.1-4, August 31, 2002
Yumao Lu , Fuchun Peng , Xin Li , Nawaaz Ahmed, Coupling feature selection and machine learning methods for navigational query identification, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
Nicola Ueffing , Hermann Ney, Using POS information for statistical machine translation into morphologically rich languages, Proceedings of the tenth conference on European chapter of the Association for Computational Linguistics, April 12-17, 2003, Budapest, Hungary
Amir Globerson , Naftali Tishby, The minimum information principle for discriminative learning, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.193-200, July 07-11, 2004, Banff, Canada
Doug Beeferman , Adam Berger , John Lafferty, Statistical Models for Text Segmentation, Machine Learning, v.34 n.1-3, p.177-210, Feb. 1999
Vincent Ng, Learning noun phrase anaphoricity to improve coreference resolution: issues in representation and optimization, Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics, p.151-es, July 21-26, 2004, Barcelona, Spain
Stefan Riezler , Jonas Kuhn , Detlef Prescher , Mark Johnson, Lexicalized stochastic modeling of constraint-based grammars using log-linear measures and EM training, Proceedings of the 38th Annual Meeting on Association for Computational Linguistics, p.480-487, October 03-06, 2000, Hong Kong
Victor Lavrenko , Jeremy Pickens, Polyphonic music modeling with random fields, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA
Hai Leong Chieu , Hwee Tou Ng, Named entity recognition with a maximum entropy approach, Proceedings of the seventh conference on Natural language learning at HLT-NAACL 2003, p.160-163, May 31, 2003, Edmonton, Canada
Hai Leong Chieu , Hwee Tou Ng, Named entity recognition: a maximum entropy approach using global information, Proceedings of the 19th international conference on Computational linguistics, p.1-7, August 24-September 01, 2002, Taipei, Taiwan
Stanley Kok , Pedro Domingos, Learning the structure of Markov logic networks, Proceedings of the 22nd international conference on Machine learning, p.441-448, August 07-11, 2005, Bonn, Germany
John Lafferty , Xiaojin Zhu , Yan Liu, Kernel conditional random fields: representation and clique selection, Proceedings of the twenty-first international conference on Machine learning, p.64, July 04-08, 2004, Banff, Alberta, Canada
Zhihua Zhang , James T. Kwok , Dit-Yan Yeung, Surrogate maximization/minimization algorithms for AdaBoost and the logistic regression model, Proceedings of the twenty-first international conference on Machine learning, p.117, July 04-08, 2004, Banff, Alberta, Canada
Pang , Lillian Lee , Shivakumar Vaithyanathan, Thumbs up?: sentiment classification using machine learning techniques, Proceedings of the ACL-02 conference on Empirical methods in natural language processing, p.79-86, July 06, 2002
Hai Leong Chieu , Hwee Tou Ng, A maximum entropy approach to information extraction from semi-structured and free text, Eighteenth national conference on Artificial intelligence, p.786-791, July 28-August 01, 2002, Edmonton, Alberta, Canada
Qi Zhang , Fuliang Weng , Zhe Feng, A progressive feature selection algorithm for ultra large feature spaces, Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the ACL, p.561-568, July 17-18, 2006, Sydney, Australia
Mark Johnson, Joint and conditional estimation of tagging and parsing models, Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, p.322-329, July 06-11, 2001, Toulouse, France
Donald Metzler , W. Bruce Croft, Analysis of Statistical Question Classification for Fact-Based Questions, Information Retrieval, v.8 n.3, p.481-504, May 2005
Shenghuo Zhu , Xiang Ji , Wei Xu , Yihong Gong, Multi-labelled classification using maximum entropy method, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil
David J. Miller , Siddharth Pal, Transductive Methods for the Distributed Ensemble Classification Problem, Neural Computation, v.19 n.3, p.856-884, March 2007
Steven J. Phillips , Miroslav Dudk , Robert E. Schapire, A maximum entropy approach to species distribution modeling, Proceedings of the twenty-first international conference on Machine learning, p.83, July 04-08, 2004, Banff, Alberta, Canada
Michael Collins , Brian Roark, Incremental parsing with the perceptron algorithm, Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics, p.111-es, July 21-26, 2004, Barcelona, Spain
Tzu-Kuo Huang , Chih-Jen Lin , Ruby C. Weng, Ranking individuals by group comparisons, Proceedings of the 23rd international conference on Machine learning, p.425-432, June 25-29, 2006, Pittsburgh, Pennsylvania
Ismael Garca-Varea , Francisco Casacuberta, Maximum Entropy Modeling: A Suitable Framework to Learn Context-Dependent Lexicon Models for Statistical Machine Translation, Machine Learning, v.60 n.1-3, p.135-158, September 2005
Joshua Goodman, Sequential conditional Generalized Iterative Scaling, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania
Hai Leong Chieu , Hwee Tou Ng, Teaching a weaker classifier: named entity recognition on upper case text, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania
James Cussens, Parameter Estimation in Stochastic Logic Programs, Machine Learning, v.44 n.3, p.245-271, September 2001
Zhiyi Chi, Statistical properties of probabilistic context-free grammars, Computational Linguistics, v.25 n.1, p.131-160, March 1999
Stephen Clark , James R. Curran, Log-linear models for wide-coverage CCG parsing, Proceedings of the conference on Empirical methods in natural language processing, p.97-104, July 11,
Minwoo Jeong , Gary Geunbae Lee, Exploiting non-local features for spoken language understanding, Proceedings of the COLING/ACL on Main conference poster sessions, p.412-419, July 17-18, 2006, Sydney, Australia
Jenny Rose Finkel , Trond Grenager , Christopher Manning, Incorporating non-local information into information extraction systems by Gibbs sampling, Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, p.363-370, June 25-30, 2005, Ann Arbor, Michigan
Amir Globerson , Naftali Tishby, Most informative dimension reduction, Eighteenth national conference on Artificial intelligence, p.1024-1029, July 28-August 01, 2002, Edmonton, Alberta, Canada
Jyrki Kivinen , Manfred K. Warmuth, Boosting as entropy projection, Proceedings of the twelfth annual conference on Computational learning theory, p.134-144, July 07-09, 1999, Santa Cruz, California, United States
Ella Bingham , Heikki Mannila , Jouni K. Seppnen, Topics in 0--1 data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
Miles Osborne, Estimation of stochastic attribute-value grammars using an informative sample, Proceedings of the 18th conference on Computational linguistics, p.586-592, July 31-August
Le Zhang , Jingbo Zhu , Tianshun Yao, An evaluation of statistical spam filtering techniques, ACM Transactions on Asian Language Information Processing (TALIP), v.3 n.4, p.243-269, December 2004
David McAllester , Michael Collins , Fernando Pereira, Case-factor diagrams for structured probabilistic modeling, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.382-391, July 07-11, 2004, Banff, Canada
Yee Whye Teh , Max Welling , Simon Osindero , Geoffrey E. Hinton, Energy-based models for sparse overcomplete representations, The Journal of Machine Learning Research, v.4 n.7-8, p.1235-1260, October 1 - November 15, 2004
James R. Curran , Stephen Clark, Investigating GIS and smoothing for maximum entropy taggers, Proceedings of the tenth conference on European chapter of the Association for Computational Linguistics, April 12-17, 2003, Budapest, Hungary
Erin L. Allwein , Robert E. Schapire , Yoram Singer, Reducing multiclass to binary: a unifying approach for margin classifiers, The Journal of Machine Learning Research, 1, p.113-141, 9/1/2001
Zhihua Zhang , James T. Kwok , Dit-Yan Yeung, Surrogate maximization/minimization algorithms and extensions, Machine Learning, v.69 n.1, p.1-33, October   2007
Yee Whye Teh , Max Welling , Simon Osindero , Geoffrey E. Hinton, Energy-based models for sparse overcomplete representations, The Journal of Machine Learning Research, 4, 12/1/2003
John Debenham , Simeon Simoff, Intelligent agents for multi-issue auctions and bidding, Proceedings of the 24th IASTED international conference on Artificial intelligence and applications, p.468-473, February 13-16, 2006, Innsbruck, Austria
Christoph Tillmann , Tong Zhang, A block bigram prediction model for statistical machine translation, ACM Transactions on Speech and Language Processing (TSLP), v.4 n.3, p.6-es, July 2007
Siddharth Pal , David J. Miller, An Extension of Iterative Scaling for Decision and Data Aggregation in Ensemble Classification, Journal of VLSI Signal Processing Systems, v.48 n.1-2, p.21-37, August    2007
Amir Globerson , Naftali Tishby, Sufficient dimensionality reduction, The Journal of Machine Learning Research, 3, 3/1/2003
Changki Lee , Gary Geunbae Lee, Information gain and divergence-based feature selection for machine learning-based text categorization, Information Processing and Management: an International Journal, v.42 n.1, p.155-165, January 2006
Miles Osborne, Using maximum entropy for sentence extraction, Proceedings of the ACL-02 Workshop on Automatic Summarization, p.1-8, July 11-12, 2002, Phildadelphia, Pennsylvania
Michael Collins, Ranking algorithms for named-entity extraction: boosting and the voted perceptron, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania
Rong Jin , Huan Liu, Robust feature induction for support vector machines, Proceedings of the twenty-first international conference on Machine learning, p.57, July 04-08, 2004, Banff, Alberta, Canada
Warren R. Greiff , Jay M. Ponte, The maximum entropy approach and probabilistic IR models, ACM Transactions on Information Systems (TOIS), v.18 n.3, p.246-287, July 2000
Jun'Ichi Kazama , Jun'Ichi Tsujii, Maximum Entropy Models with Inequality Constraints: A Case Study on Text Categorization, Machine Learning, v.60 n.1-3, p.159-194, September 2005
Hyo-Jung Oh , Sung Hyon Myaeng , Myung-Gil Jang, Semantic passage segmentation based on sentence topics for question answering, Information Sciences: an International Journal, v.177 n.18, p.3696-3717, September, 2007
Yu Gu , Andrew McCallum , Don Towsley, Detecting anomalies in network traffic using maximum entropy estimation, Proceedings of the Internet Measurement Conference 2005 on Internet Measurement Conference, p.32-32, October 19-21, 2005, Berkeley, CA
James R. Curran , Stephen Clark , David Vadas, Multi-tagging for lexicalized-grammar parsing, Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the ACL, p.697-704, July 17-18, 2006, Sydney, Australia
Ismael Garca Varea , Franz J. Och , Hermann Ney , Francisco Casacuberta, Improving alignment quality in statistical machine translation using context-dependent maximum entropy models, Proceedings of the 19th international conference on Computational linguistics, p.1-7, August 24-September 01, 2002, Taipei, Taiwan
Fei Sha , Fernando Pereira, Shallow parsing with conditional random fields, Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology, p.134-141, May 27-June 01, 2003, Edmonton, Canada
Robert Malouf, A comparison of algorithms for maximum entropy parameter estimation, proceeding of the 6th conference on Natural language learning, p.1-7, August 31, 2002
John Browning , David J. Miller, A Maximum Entropy Approach for Collaborative Filtering, Journal of VLSI Signal Processing Systems, v.37 n.2-3, p.199-209, June-July 2004
Noam Slonim , Gill Bejerano , Shai Fine , Naftali Tishby, Discriminative feature selection via multiclass variable memory Markov model, EURASIP Journal on Applied Signal Processing, v.2003 n.1, p.93-102, January
Chih-Jen Lin , Ruby C. Weng , S. Sathiya Keerthi, Trust region Newton methods for large-scale logistic regression, Proceedings of the 24th international conference on Machine learning, p.561-568, June 20-24, 2007, Corvalis, Oregon
John Lafferty, Additive models, boosting, and inference for generalized divergences, Proceedings of the twelfth annual conference on Computational learning theory, p.125-133, July 07-09, 1999, Santa Cruz, California, United States
Michael Collins , Robert E. Schapire , Yoram Singer, Logistic Regression, AdaBoost and Bregman Distances, Machine Learning, v.48 n.1-3, p.253-285, 2002
Shaojun Wang , Dale Schuurmans , Fuchun Peng , Yunxin Zhao, Combining Statistical Language Models via the Latent Maximum Entropy Principle, Machine Learning, v.60 n.1-3, p.229-250, September 2005
Adwait Ratnaparkhi, Learning to Parse Natural Language with Maximum Entropy Models, Machine Learning, v.34 n.1-3, p.151-175, Feb. 1999
Ling Tan , David Taniar, Adaptive estimated maximum-entropy distribution model, Information Sciences: an International Journal, v.177 n.15, p.3110-3128, August, 2007
Jun'ichi Kazama , Jun'ichi Tsujii, Evaluation and extension of maximum entropy models with inequality constraints, Proceedings of the conference on Empirical methods in natural language processing, p.137-144, July 11,
Ismael Garca Varea , Franz J. Och , Hermann Ney , Francisco Casacuberta, Refined lexicon models for statistical machine translation using a maximum entropy approach, Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, p.204-211, July 06-11, 2001, Toulouse, France
selection for English-Korean statistical machine translation, Proceedings of the 18th conference on Computational linguistics, p.439-445, July 31-August
Matthew Richardson , Pedro Domingos, Markov logic networks, Machine Learning, v.62 n.1-2, p.107-136, February  2006
Sunita Sarawagi, User-cognizant multidimensional analysis, The VLDB Journal  The International Journal on Very Large Data Bases, v.10 n.2-3, p.224-239, September 2001
Jianfeng Gao , Mu Li , Andi Wu , Chang-Ning Huang, Chinese Word Segmentation and Named Entity Recognition: A Pragmatic Approach, Computational Linguistics, v.31 n.4, p.531-574, December 2005
Michael Collins, Parameter estimation for statistical parsing models: theory and practice of distribution-free methods, New developments in parsing technology, Kluwer Academic Publishers, Norwell, MA, 2004
Michael Collins , Terry Koo, Discriminative Reranking for Natural Language Parsing, Computational Linguistics, v.31 n.1, p.25-70, March 2005
Fuchun Peng , Andrew McCallum, Information extraction from research papers using conditional random fields, Information Processing and Management: an International Journal, v.42 n.4, p.963-979, July 2006
Pieter Abbeel , Daphne Koller , Andrew Y. Ng, Learning Factor Graphs in Polynomial Time and Sample Complexity, The Journal of Machine Learning Research, 7, p.1743-1788, 12/1/2006
Martin J. Wainwright, Estimating the "Wrong" Graphical Model: Benefits in the Computation-Limited Setting, The Journal of Machine Learning Research, 7, p.1829-1859, 12/1/2006
Bingjun Sun , Qingzhao Tan , Prasenjit Mitra , C. Lee Giles, Extraction and search of chemical formulae in text documents on the web, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada
Gang Liang , Nina Taft , Bin Yu, A fast lightweight approach to origin-destination IP traffic estimation using partial measurements, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2634-2648, June 2006
Phan , Le-Minh Nguyen , Tu-Bao Ho , Susumu Horiguchi, Improving discriminative sequential learning with rare--but--important associations, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
Donald Metzler , W. Bruce Croft, Linear feature-based models for information retrieval, Information Retrieval, v.10 n.3, p.257-274, June      2007
Ruofei Zhang , Ramesh Sarukkai , Jyh-Herng Chow , Wei Dai , Zhongfei Zhang, Joint categorization of queries and clips for web-based video search, Proceedings of the 8th ACM international workshop on Multimedia information retrieval, October 26-27, 2006, Santa Barbara, California, USA
Phan , Le-Minh Nguyen , Yasushi Inoguchi , Tu-Bao Ho , Susumu Horiguchi, Improving discriminative sequential learning by discovering important association of statistics, ACM Transactions on Asian Language Information Processing (TALIP), v.5 n.4, p.413-438, December 2006
Daniel Gildea , Daniel Jurafsky, Automatic labeling of semantic roles, Computational Linguistics, v.28 n.3, p.245-288, September 2002
Ron Meir , Gunnar Rtsch, An introduction to boosting and leveraging, Advanced lectures on machine learning, Springer-Verlag New York, Inc., New York, NY,
Gunnar Rtsch , Sebastian Mika , Bernhard Schlkopf , Klaus-Robert Mller, Constructing Boosting Algorithms from SVMs: An Application to One-Class Classification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.9, p.1184-1199, September 2002
Nicola Orio, Music retrieval: a tutorial and review, Foundations and Trends in Information Retrieval, v.1 n.1, p.1-96, January 2006
David A. Forsyth , Okan Arikan , Leslie Ikemoto , James O'Brien , Deva Ramanan, Computational studies of human motion: part 1, tracking and motion synthesis, Foundations and Trends in Computer Graphics and Vision, v.1 n.2, p.77-254, July 2006
clustering;word morphology;iterative scaling;kullback-leibler divergence;statistical learning;natural language processing;EM algorithm;random field;maximum entropy