Generalized Iterative Scaling

The method

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. The $\mu _{i}$'s of the solution would be such that will make $P(x)$ satisfy all the constraints $K_{i}$, of the equation:

$\sum _{x}P(x)f_{i}(x)=K_{i}$

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)$

the circumstances under which it is meant to be used

you are expected to explain clearly what the method is

and list papers that use it

things the method is comparable to.

Explain what motivations or assumptions underlie the method

Intrinsic characteristics

GIS has three advantages when compared to other methods: it is able to incorporate feature selection, scales up well in numbers 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