Elamur Research⌕
☰
home / papers / 1998 / Generalizing Case Frames Using a Thesaurus and the MDL Principle

Generalizing Case Frames Using a Thesaurus and the MDL Principle

Summary

The paper addresses how to generalize the nouns observed in one case frame slot of a verb, such as the subject of fly, so that unseen but plausible fillers also receive sensible probability. Word-level estimates suffer badly from data sparseness. The authors treat slot generalization as estimating a conditional distribution over a partition of nouns into classes. To keep the search tractable, they allow only partitions that are "cuts" through an existing thesaurus tree. The task then becomes selecting a "tree cut model", and they choose it with the Minimum Description Length (MDL) principle, which weighs model complexity against fit to the data. They give an efficient algorithm that provably finds the MDL-optimal cut for a slot's frequency data. The learned case frame patterns were applied to PP-attachment disambiguation, where they outperformed or roughly matched existing methods. The work matters because it gives class-based selectional modelling a clear statistical-estimation foundation, which earlier heuristics such as Resnik's selectional association lacked.

Key points

  • Input data are (verb, slot_name, slot_value) triples extracted automatically from corpora. Their counts form co-occurrence data used to estimate P(n | v, r).
  • Word-based models need O(N·V·R) parameters. Plain MLE leaves most of these at zero; in the toy fly example, swallow gets 0, eagle 0.2 and bird 0.4.
  • A tree cut model pairs a cut through the thesaurus with one probability per class. Nouns inside a class share that class's probability uniformly. The small example thesaurus (ANIMAL, BIRD, INSECT) admits five cuts.
  • Word-sense ambiguity is handled with a simple heuristic: each noun occurrence is split equally among its possible senses. The authors argue that MDL's robustness to noise limits the harm.
  • The method belongs to the thesaurus-based family of approaches. It is compared against Resnik's selectional association and similarity-based smoothing. The reference list includes WordNet and the Penn Treebank.

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: AI & machine learning

Cite

Cite as Hang Li and Naoki Abe. 1998. Generalizing Case Frames Using a Thesaurus and the MDL Principle.

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

@misc{li1998generalizing,
  title = {{Generalizing Case Frames Using a Thesaurus and the MDL Principle}},
  author = {Hang Li and Naoki Abe},
  year = {1998},
  url = {https://aclanthology.org/J98-2002/}
}

References

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

  1. Abe, Naoki and Hang Li. 1996. Learning word association norms using tree cut pair models. Proceedings of the Thirteenth International Conference on Machine Learning, pages 3-11. find
  2. Almuallim, Hussein, Yasuhiro Akiba, Takefumi Yamazaki, Akio Yokoo, and Shigeo Kaneda. 1994. Two methods for ALT-J/E translation rules from examples and a semantic hierarchy. Proceedings of the Fifteenth International Conference on L~nin (MTi, ST i ), (20) find
  3. Alshawi, Hiyan and David Carter. 1994. Training and scaling preference functions for disambiguation. Computational Linguistics, 20(4):635-648. find
  4. Barron, Andrew R. and Thomas M. Cover. 1991. Minimum complexity density estimation. IEEE Transaction on Information Theory, 37(4):1034–1054. find
  5. Brent, Michael R. 1993. From grammar to lexicon: Unsupervised learning of lexical syntax. Computational Linguistics, 19(2):243-262. find
  6. Brent, Michael R. and Timothy A. Cartwright. 1996. Distributional regularity and phonotactic constraints are useful for segmentation. Cognition, 61:93-125. find
  7. Brent, Michael R., Sreerama K. Murthy, and Andrew Lundberg. 1995. Discovering morphemic suffixes: A case study in minimum description length induction. find
  8. Proceedings of the Fifth International Workshop on Artificial Intelligence and Statistics. find
  9. Brill, Eric. 1995. Transformation-based error-driven learning and natural language processing: A case study in part-of-speech tagging. Computational Linguistics, 21(4):543-565. our card
  10. Brill, Eric and Philip Resnik. 1994. A rule-based approach to prepositional phrase attachment disambiguation. find
  11. Proceedings of the Fifteenth International Conference on Computational Linguistics, pages 1198-1204. find
  12. Briscoe, Ted and John Carroll. 1997. Automatic extraction of subcategorization from corpora. Proceedings of the Fifth Conference on Applied Natural Language Processing. our card
  13. Brown, Peter E, Vincent J. Della Pietra, Peter V. deSouza, Jenifer C. Lai, and Robert L. Mercer. 1992. Class-based n-gram models of natural language. Computational Linguistics, 18(4):283-298. find
  14. Cartwright, Timothy A. and Michael R. Brent. 1994. Segmenting speech without a lexicon: The roles of phonotactics and speech source. Proceedings of the First Meeting of the ACL Special Interest Group in Computational Phonology, pages 83-90. find
  15. Chang, Jing-Shin, Yih-Fen Luo, and Keh-Yih Su. 1992. GPSM: A generalized probabilistic semantic model for ambiguity resolution. Proceedings of the 30th Annual Meeting, pages 177-184. Association for Computational Linguistics. find
  16. Collins, Michael and James Brooks. 1995. Prepositional phrase attachment through a backed-off model. Proceedings of the Third Workshop on Very Large Corpora. our card
  17. Cover, Thomas M. and Joy A. Thomas. 1991. Elements of Information Theory. John Wiley & Sons Inc., New York. find
  18. CucchiareUi, Alessandro and Paola Velardi. 1997. Automatic selection of class labels from a thesaurus for an effective semantic tagging of corpora. Proceedings of the Fifth Conference on Applied Natural Language Processing, pages 380-387. find
  19. Dagan, Ido, Shaul Marcus, and Shaul Makovitch. 1992. Contextual word similarity and estimation from sparse data. Proceedings of the 30th Annual Meeting, pages 164-171. Association for Computational Linguistics. find
  20. Dagan, Ido, Fernando Pereira, and Lillian Lee. 1994. Similarity-based estimation of word cooccurrence probabilities. find
  21. Proceedings of the 32nd Annual Meeting, pages 272-278. Association for Computational Linguistics. find
  22. Ellison, T. Mark. 1991. Discovering planar segregations. Proceedings of AAAI Spring Symposium on Machine Learning of Natural Language and Ontology, pages 42-47. find
  23. Ellison, T. Mark. 1992. Discovering vowel harmony. In Walter Daelmans and David Powers, editors, Background and Experiments in Machine Learning of Natural Language, pages 205-207. find
  24. Framis, Francesc Ribas. 1994. An experiment on learning appropriate selectional restrictions from a parsed corpus. Proceedings of the Fifteenth International Conference on Computational Linguistics, pages 769-774. find
  25. Grefenstette, Gregory. 1994. Explorations in Automatic Thesaurus Discovery. Kluwer Academic Publishers, Boston. find
  26. Grishman, Ralph and John Sterling. 1992. Acquisition of selectional patterns. find
  27. Proceedings of the Fourteenth International Conference on Computational Linguistics, pages 658-664. find
  28. Grishman, Ralph and John Sterling. 1994. Generalizing automatically generated selectional patterns. Proceedings of the • Fifteenth International Conference on Computational Linguistics, pages 742-747. find
  29. Grunwald, Peter. 1996. A minimum description length approach to grammar inference. In S. Wemter, E. Riloff, and G. Scheler, editors, Symbolic, Connectionist and Statistical Approaches to Learning for Natural Language Processing, Lecture Note in AI. Springer Verlag, pages 203-216. find
  30. Hindle, Donald and Mats Rooth. 1991. Structural ambiguity and lexical relations. our card
  31. Proceedings of the 29th Annual Meeting, pages 229-236. Association for Computational Linguistics. find
  32. Hindle, Donald and Mats Rooth. 1993. Structural ambiguity and lexical relations. Computational Linguistics, 19(1):103-120. our card
  33. Hobbs, Jerry R. and John Bear. 1990. Two principles of parse preference. Proceedings of the Thirteenth International Conference on Computational Linguistics, pages 162-167. find
  34. Lakoff, George. 1987. Women, Fire, and Dangerous Things: What Categories Reveal about the Mind. The University of Chicago Press. find
  35. Li, Hang and Naoki Abe. 1995. Generalizing case frames using a thesaurus and the MDL principle. Proceedings of Recent Advances in Natural Language Processing, pages 239-248. find
  36. Li, Hang and Naoki Abe. 1996. Learning dependencies between case frame slots. find
  37. Proceedings of the Sixteenth International Conference on Computational Linguistics, pages 10-15. find
  38. Manning, Christopher D. 1992. Automatic acquisition of a large subcategorization dictionary from corpora. Proceedings of the 30th Annual Meeting, pages 235-242. Association for Computational Linguistics. find
  39. Marcus, Mitchell P., Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19(1):313-330. our card
  40. Miller, George A. 1995. WordNet: A lexical database for English. Communications of the ACM, pages 39-41. our card
  41. Nomiyama, Hiroshi. 1992. Machine translation by case generalization. find
  42. Proceedings of the Fourteenth International Conference on Computational Linguistics, pages 714-720. find
  43. Pereira, Fernando, Naftali Tishby, and Lillian Lee. 1993. Distributional clustering of English words. Proceedings of the 31st Annual Meeting, pages 183-190. Association for Computational Linguistics. our card
  44. Quinlan, J. Ross and Ronald L. Rivest. 1989. Inferring decision trees using the minimum description length principle. Information and Computation, 80:227-248. find
  45. Ratnaparkhi, Adwait, Jeff Reynar, and Salim Roukos. 1994. A maximum entropy model for prepositional phrase attachment. our card
  46. Proceedings of ARPA Workshop on Human Language Technology, pages 250-255. find
  47. Resnik, Philip. 1992. WordNet and distributional analysis: A class-based approach to lexical discovery. Proceedings of AAAI Workshop on Statistically-based NLP Techniques. find
  48. Resnik, Philip. 1993a. Selection and Information: A Class-based Approach to Lexical Relationships. Ph.D. Thesis, Univ. of Pennsylvania. find
  49. Resnik, Philip. 1993b. Semantic classes and syntactic ambiguity. Proceedings of ARPA Workshop on Human Language Technology. find
  50. Rissanen, Jorma. 1978. Modeling by shortest data description. Automatic, 14:37-38. find
  51. Rissanen, Jorma. 1983. A universal prior for integers and estimation by minimum description length. The Annals of Statistics, 11(2):416–431. find
  52. Rissanen, Jorma. 1984. Universal coding, information, predication and estimation. find
  53. IEEE Transaction on Information Theory, 30(4):629-636. find
  54. Rissanen, Jorma. 1986. Stochastic complexity and modeling. The Annals of Statistics, 14(3):1080-1100. find
  55. Rissanen, Jorma. 1989. Stochastic Complexity in Statistical Inquiry. World Scientific Publishing Co., Singapore. find
  56. Rissanen, Jorma. 1995. Stochastic complexity in learning. Proceedings of the Second European Conference on Computational Learning Theory (Euro Colt'95), pages 196-210. find
  57. Ristad, Eric Sven and Robert G. Thomas. 1995. New techniques for context modeling. Proceedings of the 33rd Annual Meeting. Association for Computational Linguistics. find
  58. Schwarz, G. 1978. Estimation of the dimension of a model. Annals of Statistics, 6:416-446. find
  59. Sekine, Satoshi, Jeremy J. Carroll, Sofia Ananiadou, and Jun'ichi Tsujii. 1992. Automatic learning for semantic collocation. Proceedings of the Third Conference on Applied Natural Language Processing, pages 104-110. find
  60. Smadja, Frank. 1993. Retrieving collocations from text: Xtract. Computational Linguistics, 19(1):143-177. our card
  61. Solomonoff, R.J. 1964. A formal theory of inductive inference 1 and 2. Information and Control, 7:1-22;224-254. find
  62. Stolcke, Andreas and Stephen Omohundro. 1994. Inducing probabilistic grammars by bayesian model merging. In Rafael C. Carrasco and Jose Oncina, editors, Grammatical Inference and Applications. find
  63. Tanaka, Hideki. 1994. Verbal case frame acquisition from a bilingual corpus: Gradual knowledge acquisition. find
  64. Proceedings of the Fifteenth International Conference on Computational Linguistics, pages 727-731. find
  65. Tanaka, Hideki. 1996. Decision tree learning algorithm with structured attributes: Application to verbal case frame acquisition. Proceedings of the Sixteenth International Conference on Computational Linguistics, pages 943-948. find
  66. Utsuro, Takehito and Yuji Matsumoto. 1997. Learning probabilistic subcategorization preference by identifying case dependencies and optimal noun class generalization level. Proceedings of the Fifth Conference on Applied Natural Language Processing, pages 364-371. find
  67. Utsuro, Takehito, Yuji Matsumoto, and Makoto Nagao. 1992. Lexical knowledge acquisition from bilingual corpora. find
  68. Proceedings of the Fourteenth International Conference on Computational Linguistics, pages 581-587. find
  69. Velardi, Paola, Maria Teresa Pazienza, and Michela Fasolo. 1991. How to encode semantic knowledge: A method for meaning representation and computer-aided acquisition. Computational Linguistics, 17(2):153-170. find
  70. Wallace, C. and D. M. Boulton. 1968. An information measure for classification. Computer Journal, 11:185-195. find
  71. Wallace, C. and P. Freeman. 1992. Single-factor analysis by minimum message length estimation. Journal of Royal Statistical Society, B, 54:195-209. find
  72. Webster, Mort and Mitch Marcus. 1989. Automatic acquisition of the lexical semantics of verbs from sentence frames. find
  73. Proceedings of the 27th Annual Meeting, pages 177-184. Association for Computational Linguistics. find
  74. Whittemore, Greg, Kathleen Ferrara, and Hans Brunner. 1990. Empirical study of predictive powers of simple attachment schemes for post-modifier prepositional phrases. Proceedings of the 28th Annual Meeting, pages 23-30. Association for Computational Linguistics. find
  75. Yamanishi, Kenji. 1992. A learning criterion for stochastic rules. Machine Learning, 9:165-203. find
  76. Yarowsky, David. 1992. Word-sense disambiguation using statistical models of Roger's categories trained on large corpora. Proceedings of the fourteenth International Conference on Computational Linguistics, pages 454-460. find
  77. Yarowsky, David. 1994. Decision lists for lexical ambiguity resolution: Application to accent restoration in Spanish and French. Proceedings of the 32nd Annual Meeting, pages 88-95. Association for Computational Linguistics. our card

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/li-1998-generalizing-case-frames-thesaurus-mdl/