Generalized Iterative Scaling

The Method and When to Use it

The Generalized Iterative Scaling (GIS) is a method that searches the exponential family of a Maximum Entropy solution of the form:

$P(x)=\prod _{i}\mu _{i}^{f_{i}(x)}$

where the $\mu _{i}$'s are some unknown constants to be found, that guarantees to converge to a solution. The $\mu _{i}$'s of the solution would be such that will make $P(x)$ satisfy all the constraints $K_{i}$, of the equation:

$E_{P}f_{i}{\overset {\underset {\mathrm {def} }{}}{=}}\sum _{x}P(x)f_{i}(x)=K_{i}$

GIS was proposed by Darroch Ratclif and is similar in form and computational cost to the expectation-maximization algorithm. Previous methods to estimate the maximum likelihood were limited to the restriction $f_{i}(x)\in {0,1}$ so, GIS, as the name states, generalized so that these functions could be any real number.

The Algorithm

GIS starts with arbitrary $\mu _{i}^{(0)}$ values, wich define the initial probability estimate:

$P^{(0)}(x){\overset {\underset {\mathrm {def} }{}}{=}}\prod _{i}\mu _{i}^{(0)f_{i}(x)}$

Each next iteration is intended to create an estimate, that will match the constraints better than the last one. Each $j$ iteration follows the steps:

• (1) Compute the expectations of all the $f_{i}$'s under the current estimate function, i.e., $\sum _{x}P^{(j)}(x)f_{i}(x)$

• (2) Compare the present values with the desired ones, updating the $\mu _{i}$'s in the following manner:

$\mu _{i}^{(j+1)}=\mu _{i}^{(j)}.{\frac {K_{i}}{E_{P^{(j)}}f_{i}}}$

• (3) Set the new estimate function:

$P^{(j+1)}{\overset {\underset {\mathrm {def} }{}}{=}}\prod _{i}\mu _{i}^{(j+1)f_{i}(x)}$

• (4) If convergence or near-convergence is reached stop; otherwise go back to step (1)

Intrinsic characteristics

GIS has three advantages when compared to other methods: it is able to incorporate feature selection, scales up well in number of features and is resilient to feature dependence.

On the other hand GIS has problems with smoothing and is relatively slow in training when compared to other classification methods.

Related Papers

John N. Darroch, and Douglas Ratcliff. (1972). "Generalized Iterative Scaling for Log-Linear Models." In: The Annals of Mathematical Statistics, 43(5). [1]

Adwait Ratnaparkhi. (1996). "A Maximum Entropy Model for Part-of-Speech Tagging." In: Proceedings of EMNLP Conference (EMNLP 1996). [2]

Andrew McCallum, Dayne Freitag, and Fernando Pereira. (2000). "Maximum Entropy Markov Models for Information Extraction and Segmentation." In: Proceedings of ICML-2000. [3]

Raymond Lau, Ronald Rosenfeld and Salim Roukos. "Adaptive Language Modeling Using the Maximum Entropy Principle". In Proceedings of the ARPA Human Language Technology Workshop, published as Human Language Technology, pages 108–113. Morgan Kaufmann, March 1993.