Sequential Conditional Generalized Iterative Scaling

Sequential Conditional Generalized Iterative Scaling Joshua Goodman Microsoft Research One Microsoft Way Redmond, WA 98052 joshuago@microsoft.com Abstract We describe a speedup for training conditional maxi- mumentropymodels. Thealgorithmisasimplevari- ation on Generalized Iterative Scaling, but converges roughly an order of magnitude faster, depending on the number of constraints, and the way speed is mea- sured. Rather than attempting to train all model pa- rameters simultaneously, the algorithm trains them sequentially. The algorithm is easy to implement, typically uses only slightly more memory, and will lead to improvements for most maximum entropy problems. 1 Introduction Conditional Maximum Entropy models have been used for a variety of natural language tasks, includ- ing Language Modeling (Rosenfeld, 1994), part- of-speech tagging, prepositional phrase attachment, and parsing (Ratnaparkhi, 1998), word selection for machine translation (Berger et al., 1996), and find- ing sentence boundaries (Reynar and Ratnaparkhi, 1997). Unfortunately, although maximum entropy (maxent) models can be applied very generally, the typical training algorithm for maxent, Generalized Iterative Scaling (GIS) (Darroch and Ratcliff, 1972), can be extremely slow. We have personally used up to a month of computer time to train a single model. There have been several attempts to speed up max- ent training (Della Pietra et al., 1997; Wu and Khu- danpur, 2000; Goodman, 2001). However, as we describe later, each of these has suffered from appli- cability to a limited number of applications. Darroch and Ratcliff (1972) describe GIS for joint probabil- ities, and mention a fast variation, which appears to have been missed by the conditional maxent com- munity. We show that this fast variation can also be used for conditional probabilities, and that it is useful for a larger range of problems than traditional speedup techniques. It achieves good speedups for all but the simplest models, and speedups of an order of magnitude or more for typical problems. It has only one disadvantage: when there are many possi- ble output values, the memory needed is prohibitive. By combining this technique with another speedup technique (Goodman, 2001), this disadvantage can be eliminated. Conditional maxent models are of the form P(y|x) = exp � i λifi(x, y) � y′ exp � i λifi(x, y′) (1) where x is an input vector, y is an output, the fi are the so-called indicator functions or feature values that are true if a particular property of x, y is true, and λi is a weight for the indicator fi. For instance, if trying to do word sense disambiguation for the word “bank”, x would be the context around an oc- currence of the word; y would be a particular sense, e.g. financial or river; fi(x, y) could be 1 if the con- text includes the word “money” and y is the financial sense; and λi would be a large positive number. Maxent models have several valuable proper- ties. The most important is constraint satisfaction. For a given fi, we can count how many times fi was observed in the training data, observed[i] = � j fi(xj, yj). For a …

Content truncated to 500 words