练习与参考文献

练习¶

E.1 实现 CKY 算法。

E.2 修改第 19 章把文法转换为乔姆斯基范式（CNF）的算法，使其正确处理规则概率。确保所得 CNF 为每棵分析树赋予的总概率保持不变。

E.3 第 13.3 题要求直接扩展 CKY 以处理一元产生式，而不是先把它们转换为 CNF。请把这一修改推广到概率 CKY。

E.4 补全图 E.4 中概率 CKY 表格的其余部分。

E.5 概述需要怎样扩展 CKY 算法才能处理词汇化概率。

E.6 实现你提出的 CKY 词汇化扩展。

参考文献¶

Abney, S. P., R. E. Schapire, and Y. Singer. 1999. Boosting applied to tagging and PP attachment. EMNLP/VLC.

Baker, J. K. 1979. Trainable grammars for speech recognition. Speech Communication Papers for the 97th Meeting of the Acoustical Society of America.

Bangalore, S. and A. K. Joshi. 1999. Supertagging: An approach to almost parsing. Computational Linguistics, 25(2):237–265.

Black, E., F. Jelinek, J. D. Lafferty, D. M. Magerman, R. L. Mercer, and S. Roukos. 1992. Towards history-based grammars: Using richer models for probabilistic parsing. HLT.

Bod, R. 1993. Using an annotated corpus as a stochastic grammar. EACL.

Booth, T. L. 1969. Probabilistic representation of formal languages. IEEE Conference Record of the 1969 Tenth Annual Symposium on Switching and Automata Theory.

Booth, T. L. and R. A. Thompson. 1973. Applying probability measures to abstract languages. IEEE Transactions on Computers, C-22(5):442–450.

Bresnan, J., ed. 1982. The Mental Representation of Grammatical Relations. MIT Press.

Brill, E. and P. Resnik. 1994. A rule-based approach to prepositional phrase attachment disambiguation. COLING.

Briscoe, T. and J. Carroll. 1993. Generalized probabilistic LR parsing of natural language (corpora) with unification-based grammars. Computational Linguistics, 19(1):25–59.

Charniak, E. 1997. Statistical parsing with a context-free grammar and word statistics. AAAI.

Chelba, C. and F. Jelinek. 2000. Structured language modeling. Computer Speech and Language, 14:283–332.

Collins, M. 1996. A new statistical parser based on bigram lexical dependencies. ACL.

Collins, M. 1999. Head-Driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania.

Francis, H. S., M. L. Gregory, and L. A. Michaelis. 1999. Are lexical subjects deviant? CLS-99.

Franz, A. 1997. Independence assumptions considered harmful. ACL.

Givón, T. 1990. Syntax: A Functional Typological Introduction. John Benjamins.

Hindle, D. and M. Rooth. 1990. Structural ambiguity and lexical relations. Speech and Natural Language Workshop.

Hindle, D. and M. Rooth. 1991. Structural ambiguity and lexical relations. ACL.

Jelinek, F. and J. D. Lafferty. 1991. Computation of the probability of initial substring generation by stochastic context-free grammars. Computational Linguistics, 17(3):315–323.

Jelinek, F., J. D. Lafferty, D. M. Magerman, R. L. Mercer, A. Ratnaparkhi, and S. Roukos. 1994. Decision tree parsing using a hidden derivation model. ARPA Human Language Technologies Workshop.

Johnson, M. 1998. PCFG models of linguistic tree representations. Computational Linguistics, 24(4):613–632.

Joshi, A. K. 1985. Tree adjoining grammars: How much context-sensitivity is required to provide reasonable structural descriptions? In Natural Language Parsing, 206–250. Cambridge University Press.

Joshi, A. K. and B. Srinivas. 1994. Disambiguation of super parts of speech (or supertags): Almost parsing. COLING.

Klein, D. and C. D. Manning. 2001. Parsing and hypergraphs. IWPT-01.

Klein, D. and C. D. Manning. 2003a. A* parsing: Fast exact Viterbi parse selection. HLT-NAACL.

Klein, D. and C. D. Manning. 2003b. Accurate unlexicalized parsing. HLT-NAACL.

Lafferty, J. D., D. Sleator, and D. Temperley. 1992. Grammatical trigrams: A probabilistic model of link grammar. AAAI Fall Symposium on Probabilistic Approaches to Natural Language.

Lari, K. and S. J. Young. 1990. The estimation of stochastic context-free grammars using the Inside-Outside algorithm. Computer Speech and Language, 4:35–56.

Magerman, D. M. and M. P. Marcus. 1991. Pearl: A probabilistic chart parser. EACL.

Manning, C. D. and H. Schütze. 1999. Foundations of Statistical Natural Language Processing. MIT Press.

Marcus, M. P. 1990. Summary of session 9: Automatic acquisition of linguistic structure. Speech and Natural Language Workshop.

Ney, H. 1991. Dynamic programming parsing for context-free grammars in continuous speech recognition. IEEE Transactions on Signal Processing, 39(2):336–340.

Petrov, S., L. Barrett, R. Thibaux, and D. Klein. 2006. Learning accurate, compact, and interpretable tree annotation. COLING/ACL.

Pollard, C. and I. A. Sag. 1994. Head-Driven Phrase Structure Grammar. University of Chicago Press.

Ratnaparkhi, A., J. C. Reynar, and S. Roukos. 1994. A maximum entropy model for prepositional phrase attachment. ARPA Human Language Technologies Workshop.

Resnik, P. 1992. Probabilistic tree-adjoining grammar as a framework for statistical natural language processing. COLING.

Salomaa, A. 1969. Probabilistic and weighted grammars. Information and Control, 15:529–544.

Schabes, Y. 1990. Mathematical and Computational Aspects of Lexicalized Grammars. Ph.D. thesis, University of Pennsylvania.

Schabes, Y. 1992. Stochastic lexicalized tree-adjoining grammars. COLING.

Schabes, Y., A. Abeillé, and A. K. Joshi. 1988. Parsing strategies with “lexicalized” grammars: Applications to Tree Adjoining Grammars. COLING.

Stetina, J. and M. Nagao. 1997. Corpus based PP attachment ambiguity resolution with a semantic dictionary. Proceedings of the Fifth Workshop on Very Large Corpora.

Stolcke, A. 1995. An efficient probabilistic context-free parsing algorithm that computes prefix probabilities. Computational Linguistics, 21(2):165–202.

Zavrel, J. and W. Daelemans. 1997. Memory-based learning: Using similarity for smoothing. ACL.