Elamur Research
☰
home / papers / 1996 / A Maximum Entropy Approach to Natural Language Processing

A Maximum Entropy Approach to Natural Language Processing

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/J96-1002.pdf

Summary

Statistical NLP models have two linked tasks: decide which statistics of the data matter (feature selection), then build a predictive model that respects them (model selection). Berger and the Della Pietras handle both with the maximum entropy principle. Among all conditional distributions p(y|x) whose expected feature values match those in the training sample, the method chooses the one that is otherwise most uniform. They show this solution belongs to an exponential (log-linear) family with one weight per constraint. It also coincides with the maximum-likelihood model in that family, so entropy-based and likelihood-based reasoning lead to the same answer. They describe an iterative algorithm for fitting the weights, plus a greedy procedure that adds features one at a time from a large candidate pool, with shortcuts that make it practical. They test the framework on components of IBM's Candide French–English translation system: translation-sense disambiguation, sentence segmentation and word reordering. The paper helped make log-linear "MaxEnt" classifiers a standard NLP tool.

Key points

  • Features are binary functions of (context x, output y). A constraint is a separate idea: it requires the model's expected feature value to equal the value observed in the training data.
  • The solution has the form p(y|x) ∝ exp(Σ λᵢ fᵢ(x, y)). Maximizing entropy under the constraints and maximizing likelihood within this exponential family give the same model.
  • Features are chosen automatically and incrementally from template-generated candidates. At each step the algorithm adds the feature that most improves likelihood, using approximations to keep the search fast.
  • On French NOUN de NOUN reordering (e.g., taux d'intérêt → "interest rate"), the model was trained on 10,000 Hansard corpus events and ended up with 358 constraints.
  • On 71,555 test phrases, overall accuracy rose from 70.2% (a baseline that never swaps) to 80.4%. Accuracy on phrases that should be swapped went from 0% to 49.2%, while accuracy on phrases that should stay in order fell from 100% to 93.5%.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Natural language processing

Cited by

568 papers of our library cite it (of the 140673 whose bibliographies we read); 8 of them have a page here, 560 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work.

@article{berger1996maximum,
  title = {{A Maximum Entropy Approach to Natural Language Processing}},
  author = {Berger, Adam L. and Pietra, Stephen A. Della and Pietra, Vincent J. Della},
  journal = {Computational Linguistics},
  year = {1996},
  url = {https://aclanthology.org/J96-1002/}
}

References

22 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Bahl, L.; Brown, P.; de Souza, P.; and Mercer, R. (1989). A tree-based statistical language model for natural language speech recognition. IEEE Transactions on Acoustics, Speech, and Signal Processing, 37(7). find
  2. Berger, A.; Brown, P.; Della Pietra, S.; Della Pietra, V.; Gillett, J.; Lafferty, J.; Printz, H.; and Urea, L. (1994). The Candide System for Machine Translation. In Proceedings, ARPA Conference on Human Language Technology, Plainsborough, New Jersey. find
  3. Black, E.; Jelinek, E; Lafferty, J.; Magerman, D.; Mercer, R.; and Roukos, S. (1992). Towards History-based Grammars: Using Richer Models for Probabilistic Parsing. In Proceedings, DARPA Speech and Natural Language Workshop, Arden House, New York. find
  4. Brown, D. (1959). A Note on Approximations to Discrete Probability Distributions. Information and Control, 2:386-392. find
  5. Brown, P.; Della Pietra, S.; Della Pietra, V.; and Mercer, R. (1993). The Mathematics of Statistical Machine Translation: Parameter Estimation. Computational Linguistics, 19(2):263--311. find
  6. Brown, P.; Cocke, J.; Della Pietra, S.; Della Pietra, V.; Jelinek, E; Lafferty, J.; Mercer, R.; and Roossin, P. (1990). A Statistical Approach to Machine Translation. Computational Linguistics, 16:79-85. find
  7. Brown, P.; Della Pietra, V.; de Souza, P.; and Mercer, R. (1990). Class-based N-Gram Models of Natural Language. Proceedings, IBM Natural Language ITL, 283-298. find
  8. Brown, P.; Della Pietra, S.; Della Pietra, V.; and Mercer, R. (1991). A Statistical Approach to Sense Disambiguation in Machine Translation. In Proceedings, DARPA Speech and Natural Language Workshop, 146-151. find
  9. Cover, T. and Thomas, J. (1991). Elements of Information Theory. John Wiley & Sons. find
  10. Csiszdr, I. (1975). I-Divergence Geometry of Probability Distributions and Minimization Problems, The Annals of Probability, 3(1):146-158. ibid. (1989). A Geometric Interpretation of Darroch and Ratcliff's Generalized Iterative Scaling. The Annals of Statistics, 17(3):1409-1413. find
  11. Csisz~ir, L. and Tusn~idy, G. (1984). Information Geometry and Alternating Minimization Procedures. Statistics & Decisions, Supplemental Issue, no. 1, 205-237. find
  12. Darroch, J. N. and Ratcliff, D. (1972). Generalized Iterative Scaling for Log-linear Models. Annals of Mathematical Statistics, no. 43, 1470-1480. find
  13. Della Pietra, S.; Della Pietra, V.; Gillett, J.; Lafferty, J.; Printz, H.; and Urea, L. (1994). "Inference and Estimation of a Long-range Trigram Model." In Lecture Notes in Artificfal Intelligence, 862. Springer-Verlag, 78-92. find
  14. Della Pietra, S.; Della Pietra, V.; and Lafferty, J. (1995). "Inducing features of random fields" CMU Technical Report CMU-CS-95-144. find
  15. Dempster, A. P.; Laird, N. M.; and Rubin, D. B. (1977). Maximum Likelihood from Incomplete Data via the EM Algorithm. Journal of the Royal Statistical Society, 39(B):1-38. find
  16. Guiasu, S. and Shenitzer, A. (1985). The Principle of Maximum Entropy. The Mathematical Intelligencer , 7(1). find
  17. Jaynes, E. T. (1990) "Notes on Present Status and Future Prospects." In Maximum Entropy and Bayesian Methods, edited by W. T. Grandy and L. H. Schick. Kluwer, 1-13. find
  18. Jelinek, F. and Mercer, R. L. (1980). Interpolated Estimation of Markov Source Parameters from Sparse Data. In Proceedings, Workshop on Pattern Recognition in Practice, Amsterdam, The Netherlands. find
  19. Lucassen, J. and Mercer, R. (1984). An Information Theoretic Approach to Automatic Determination of Phonemic Baseforms. In Proceedings, IEEE International Conference on Acoustics, Speech and Signal Processing, San Diego, CA, 42.5.1-42.5.4. find
  20. Merialdo, B. (1990). Tagging Text with a Probabilistic Model. In Proceedings, IBM Natural Language ITL, Paris, France, 161-172. find
  21. Nddas, A.; Mercer, R.; Bahl, L.; Bakis, R.; Cohen, P.; Cole, A.-; Jelinek, F.; and Lewis, B. (1981). Continuous Speech Recognition with Automatically Selected Acoustic Prototypes Obtained by either Bootstrapping or Clustering. In Proceedings, IEEE International Conference on Acoustics, Speech and Si… find
  22. Sokolnikoff, I. S. and Redheffer, R. M. (1966). Mathematics of Physics and Modern Engineering, Second Edition, McGraw-Hill Book Company. find