Next: Basic model construction Up: Algorithms for Inductive Learning Previous: Algorithms for Inductive Learning

## Motivation

We begin by specifying a large collection of candidate features. We do not require a priori that these features are actually relevant or useful. Instead, we let the pool be as large as practically possible. Only a small subset of this collection of features will eventually be employed in our final model. In short, we would like to include in the model only a subset of the full set of candidate features . We will call the set of active features. The choice of must capture as much information about the random process as possible, yet only include features whose expected values can be reliably estimated.

With each one might associate a Bernoulli random variable with the following (``objectivist'' or ``non-Bayesian'') interpretation. Imagine that the set of pairs comprising were drawn from an imaginary, infinite distribution of pairs. In this imaginary distribution, f is active ( ) with some probability , and inactive ( ) with probability .

(A Bayesian would prefer to put a distribution over the possible values of , informed both by some empirical evidence--such as the fraction of times in the sample --and also by some outside knowledge of what one miht expect to be. This line of reasoning forms the basis of ``fuzzy maximum entropy,'' which is a quite intriguing line of investigation we shall not pursue here.)

As a Bernoulli variable, f is subject to the law of large numbers, which asserts that for any :

That is, by increasing the number (N) of examples , the fraction for which approaches the constant . More succinctly, . Unfortunately, is not infinite, and the empirical estimate for each is not guaranteed to lie close to its ``true'' value . However, a subset of will exhibit . And of these, a fraction will have a non-negligeable bearing on the likelihood of the model. The goal of the inductive learning process is to identify this subset and construct a conditional model from it.

Searching exhaustively for this subset is hopeless for all but the most restricted problems. Even a priori fixing its size doesn't help much: there are unique outcomes of this selection process. For concreteness, a typical set of figures in documented experiments involving maxent modeling are and , meaning possible sets of 25 active features. Viewed as a pure search problem, finding the optimal set of features is computationally inconceivable.

To find , we adopt an incremental approach to feature selection. The idea is to build up by successively adding features. The choice of feature to add at each step is determined by the training data. Let us denote the set of models determined by the feature set as . ``Adding'' a feature f is shorthand for requiring that the set of allowable models all satisfy the equality . Only some members of will satisfy this equality; the ones that do we denote by .

Thus, each time a candidate feature is adjoined to , another linear constraint is imposed on the space of models allowed by the features in . As a result, shrinks; the model in with the greatest entropy reflects ever-increasing knowledge and thus, hopefully, becomes a more accurate representation of the process. This narrowing of the space of permissible models was represented in figure 1 by a series of intersecting lines (hyperplanes, in general) in a probability simplex. Perhaps more intuitively, we could represent it by a series of nested subsets of , as in figure 2.

As an aside, the intractability of the ``all at once'' optimization problem is not unique to or an indictment of the exponential approach. Decision trees, for example, are typically constructed recursively using a greedy algorithm. And in designing a neural network representation of an arbitrary distribution, one typically either fixes the network topology in advance or performs a restricted search within a neighborhood of possible topologies for the optimal configuration, because the complete search over parameters and topologies is intractable.

Figure 2: A nested sequence of subsets of corresponding to increasingly large sets of features

Next: Basic model construction Up: Algorithms for Inductive Learning Previous: Algorithms for Inductive Learning