Elamur Research
☰
home / papers / 1994 / A Maximum Entropy Model for Prepositional Phrase Attachment

A Maximum Entropy Model for Prepositional Phrase Attachment

What it is about

The paper models the noun-or-verb attachment of a prepositional phrase with a maximum-entropy classifier over four head words: the verb, the first noun, the preposition and the second noun. Features are questions on single words, on word classes, and on both; the word classes come from a binary tree of mutual-information clusters. Features are chosen greedily by a ranking of log-likelihood gain, not by exhaustive search. On the Wall Street Journal test events the model scores 81.6% with words and classes (77.7% with words only, 79.1% with classes only); on computer-manual text it scores 84.1%. Humans given the same four head words score 88.2%, and humans who read the whole sentence score 93.2%, so the authors locate the gap in the sentence context.

Ideas

For Mova

The code is en/src/parse.rs, en/src/ptag.rs and en/src/ctx.rs. The chapters are languages/en/22-phrases.md and 23-complementation.md. Measure first: the PP-attachment accuracy of the current en parser on EWT test against the paper's 81.6 and its human 93.2 with the sentence, so that the room is clear before any change.

Library summary

The Research library's own summary of the paper, in our words — not the paper's text.

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/H94-1048.pdf

Summary

The paper addresses prepositional phrase attachment: deciding whether a PP modifies the object noun or the verb in a verb phrase. The authors frame this as a binary decision. Each event is described by four head words: the verb (V), the object noun (N1), the preposition (P) and the noun inside the PP (N2). They model it with a conditional Maximum Entropy (exponential) model trained via Generalized Iterative Scaling.

Features are binary questions of three kinds:

  • word n-grams over the four heads;
  • bits of word paths in a mutual-information clustering tree;
  • mixtures of the two.

A greedy search picks features by their estimated gain in training log-likelihood. After each pick, the candidate pool is enlarged with more specific class-based variants of the chosen feature.

Experiments use the IBM-Lancaster Computer Manuals treebank and the Penn WSJ treebank. The best configurations reach about 84% and 82% accuracy, respectively, slightly above a decision tree built on the same inputs. Human studies show that expert treebankers do much better, but non-experts given only head words do worse than the model. The work is an early demonstration that ME feature selection suits attachment ambiguities in parsing.

Key points

  • Data: Computer Manuals has 8,264 training and 943 test events; WSJ has 20,801 training and 3,097 test events.

  • ME model accuracy (Computer Manuals / WSJ), with roughly 200 selected features:

    Feature setComputer ManualsWSJ
    Words Only82.2%77.7%
    Classes Only84.5%79.1%
    Words and Classes84.1%81.6%

  • Decision tree baseline (same head words and class bits): 79.5% on Computer Manuals and 77.7% on WSJ.

  • Expert treebankers on 300 WSJ events:

    • 88.2% with head words only;
    • 93.2% with the full sentence;
    • the ME model scores 78.0% on the same events.

  • Consensus subset: on the 274 events where all experts agreed, the original WSJ treebank matches 95.7% and the ME model 80.7%.

  • Non-experts on 200 Computer Manuals events: 77.3%, compared with 83.5% for the model.

Interesting ideas

  • Greedy likelihood-based selection with a growing pool. Candidates are ranked by approximate log-likelihood gain, fitting only the new weight while existing weights stay fixed. The candidate set then expands only around the most recently accepted feature. The pool grows linearly instead of exploding combinatorially, which suits any sparse log-linear model with conjunctive features.
  • Words as bit strings from a clustering tree. Each word's path in a hierarchical cluster tree, padded to equal length, becomes a bit string that features can query at any position. This gives graded back-off from exact words to coarse classes, helpful for rare words in low-resource languages.
  • Complement and null features. A "fires when nothing else does" feature plus a prior-matching feature guarantee sensible behaviour on uncovered inputs. This is a cheap safeguard for any feature-based classifier.
  • Monitoring test entropy during feature addition. Training entropy keeps falling, while test entropy reaches a minimum where accuracy tends to peak. This curve gives a natural stopping point for feature selection.
  • Human ceilings under matched information. Annotators were tested with exactly the model's input (head words only) and with full context, and a consensus subset served as a cleaner truth set. This separates model weakness from missing information and from label noise, a useful evaluation design for new treebanks or annotation projects.

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.3115/1075812.1075868

@inproceedings{ratnaparkhi1994maximum,
  title = {{A Maximum Entropy Model for Prepositional Phrase Attachment}},
  author = {Ratnaparkhi, Adwait and Reynar, Jeff and Roukos, Salim},
  booktitle = {Human Language Technology: Proceedings of a Workshop held at Plainsboro, New Jersey, March 8-11, 1994},
  year = {1994},
  doi = {10.3115/1075812.1075868},
  url = {https://doi.org/10.3115/1075812.1075868}
}

References

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

  1. Jaynes, E. T., "Information Theory and Statistical Mechanics." Phys. Rev. 106, pp. 620-630, 1957. find
  2. Kullback, S., Information Theory in Statistics. Wiley, New York, 1959. find
  3. Darroch, J.N. and Ratcliff, D., "Generalized Iterative Scaling for Log-Linear Models", The Annals of Mathematical Statistics, Vol. 43, pp 1470-1480, 1972. find
  4. Delia Pietra,S., Della Pietra, V., Mercer, R. L., Roukos, S., "Adaptive Language Modeling Using Minimum Discriminant Estimation," Proceedings oflCASSP-92, pp. 1-633-636, San Francisco, March 1992. find
  5. Black, E., Garside, R., and Leech, G., 1993. Statistically-driven Computer Grammars of English: The IBM/Lancaster Approach. Rodopi. Atlanta, Georgia. find
  6. Black, E., Jelinek, F., Lafferty, J., Magerman, D. M., Mercer, R., and Roukos, S., 1993. Towards History-based Grammars: Using Richer Models for Probabilistic Parsing. In Proceedings of the Association for Computational Linguistics, 1993. Columbus, Ohio. find
  7. Breiman, L., Friedman, J. H., Olshen, R. A., and Stone, C. J., 1984. Classification and Regression Trees. Wadsworth and Brooks. Pacific Grove, California. find
  8. Brown, P. F., Della Pietra, V. J., deSouza, P. V., Lai, J. C., and Mercer, R. L. Class-based n-gram Models of Natural Language. In Proceedings of the IBM Natural Language 1TL, March, 1990. Paris, France. find
  9. Hindle, D. and Rooth, M. 1990. Structural Ambiguity and Lexical Relations. In Proceedings of the June 1990 DARPA Speech and Natural Language Workshop. Hidden Valley, Pennsylvania. find
  10. Magerman, D., 1994. Natural Language Parsing as Statistical Pattern Recognition. Ph.D. dissertation, Stanford University, California. find