Learning random walk models for inducing word dependency distributions

ABSTRACT

Many NLP tasks rely on accurately estimating word dependency probabilities P(ω1|ω2), where the words w1 and w2 have a particular relationship (such as verb-object). Because of the sparseness of counts of such dependencies, smoothing and the ability to use multiple sources of knowledge are important challenges. For example, if the probability P(N|V) of noun N being the subject of verb V is high, and V takes similar objects to V', and V' is synonymous to V", then we want to conclude that P(N|V") should also be reasonably high---even when those words did not cooccur in the training data.To capture these higher order relationships, we propose a Markov chain model, whose stationary distribution is used to give word probability estimates. Unlike the manually defined random walks used in some link analysis algorithms, we show how to automatically learn a rich set of parameters for the Markov chain's transition probabilities. We apply this model to the task of prepositional phrase attachment, obtaining an accuracy of 87.54%.

REFERENCES

• 1: Bikel, D. M. (2003). Intricacies of Collins' parsing model (Technical Report TR No. MS-CIS-03-11). University of Pennsylvania.
• 2: Brémaud, P. (1999). Markov chains: Gibbs fields, monte carlo simulation, and queues. Springer-Verlag.
• 3: Eric Brill , Philip Resnik, A rule-based approach to prepositional phrase attachment disambiguation, Proceedings of the 15th conference on Computational linguistics, August 05-09, 1994, Kyoto, Japan [doi>10.3115/991250.991346]
• 4: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 5: Charniak, E. (1997). Statistical parsing with a context-free grammar and word statistics. Proc. 14th National Conference on Artificial Intelligence (pp. 598--603).
• 6: Eugene Charniak, A maximum-entropy-inspired parser, Proceedings of the first conference on North American chapter of the Association for Computational Linguistics, p.132-139, April 29-May 04, 2000, Seattle, Washington
• 7: Michael John Collins , Mitchell P. Marcus, Head-driven statistical models for natural language parsing, 1999
• 8: Collins, M., & Brooks, J. (1995). Prepositional attachment through a backed-off model. Proceedings of the Third Workshop on Very Large Corpora (pp. 27--38).
• 9: Ido Dagan , Lillian Lee , Fernando C. N. Pereira, Similarity-Based Models of Word Cooccurrence Probabilities, Machine Learning, v.34 n.1-3, p.43-69, Feb. 1999
• 10: Essen, U., & Steinbiss, V. (1992). Cooccurrence smoothing for stochastic language modeling. ICASSP (pp. 161--164).
• 11: Goodman, J. T. (2001). A bit of progress in language modeling. MSR Technical Report MSR-TR-2001-72.
• 12: Sanda M. Harabagiu , Marius Pasca, Integrating Symbolic and Statistical Methods for Prepositional Phrase Attachment, Proceedings of the Twelfth International Florida Artificial Intelligence Research Society Conference, p.303-307, May 01-05, 1999
• 13: Donald Hindle , Mats Rooth, Structural ambiguity and lexical relations, Computational Linguistics, v.19 n.1, March 1993
• 14: David A. Hull, Stemming algorithms: a case study for detailed evaluation, Journal of the American Society for Information Science, v.47 n.1, p.70-84, Jan. 1996 [doi>10.1002/(SICI)1097-4571(199601)47:1<70::AID-ASI7>3.3.CO;2-Q]
• 15: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 16: John Lafferty , Chengxiang Zhai, Document language models, query models, and risk minimization for information retrieval, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.111-119, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383970]
• 17: Lillian Lee, Measures of distributional similarity, Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, p.25-32, June 20-26, 1999, College Park, Maryland [doi>10.3115/1034678.1034693]
• 18: Ng, A. Y., Zheng, A. X., & Jordan, M. (2001). Link analysis, eigenvectors, and stability. Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI-01).
• 19: Patrick Pantel , Dekang Lin, An unsupervised approach to prepositional phrase attachment using contextually similar words, Proceedings of the 38th Annual Meeting on Association for Computational Linguistics, p.101-108, October 03-06, 2000, Hong Kong [doi>10.3115/1075218.1075232]
• 20: Rao, R. C. (1982). Diversity: Its measurement, decomposition, aportionment and analysis. The Indian Journal of Statistics, 44, 1--22.
• 21: Adwait Ratnaparkhi , Jeff Reynar , Salim Roukos, A maximum entropy model for prepositional phrase attachment, Proceedings of the workshop on Human Language Technology, March 08-11, 1994, Plainsboro, NJ [doi>10.3115/1075812.1075868]
• 22: Stetina, J., & Nagao, M. (1997). Corpus based PP attachment ambiguity resolution with a semantic dictionary. Proc. 5th Workshop on Very Large Corpora (pp. 66--80).