GeneralizedIterativeScaling

From Cohen Courses
Jump to navigationJump to search

This is one of the earliest methods used for inference in log-linear models. Though more sophisticated and faster methods have evolved, this method provides an insight in log linear models.

What problem does it address

The objective of this method is to find a probability function of the form

satisfying the constraints

where is an index set; the probability distribution over which has to be determined, is a probability distribution and is a subprobability function (adds to 1 but for any ); is constant.

Since is linear in and , belongs to the log linear family.

Existence of a solution

If of form (1) exists satisfying (2), then it minimizes

and is unique. Since are constant; it essentially boils down to the following statement.

Maximum entropy

If there exists a positive probability function of the form

satisfying (2), then it maximizes the entropy

This statement is equivalent to saying that if there are a set of features whose expected value is known, then the probability distribution (if there exists one) that maximizes the entropy (makes minimum assumptions) is of the form (1).

Algorithm

Given that constraints (2) is satisfied by atleast one sub-probability function (this condition is also known as consistency of constraints), then (1) and (2) can be expressed as

where

Define

Iterate

where

Used in

Frietag 2000 Maximum Entropy Markov Models for Information Extraction and Segmentation

References

J. N. Darroch and D. Ratcliff, Generalized Iterative Scaling for log linear models.