Summer term 2018
Lecturer: Helmut Horacek
Time and place: Wed. 16-18, Seminar room 001, bldg. E1.7
Begin: 11.4.
Attention: no lectures on 9.5., 16.5., 13.6., and 27.6
Extra lecture on 28.5. 8.30-10, same room
Extra lectures on 19.6. and 10.7. 14-16, room 008
The area of heuristic search offers a variety of effective procedures which have been applied to a number of tasks in automated natural language processing. A main problem with applying search methods effectively to automated natural language processing lies in the discrepancy between the homogenous search spaces that search procedures require and typically heterogeneous representations of linguistic descriptions. In this lecture, we will discuss methods for bridging this discrepancy through suitable modeling and compromises in system architecture design. I will treat the following issues:
Probabilistic syntactic analysis
Computerlinguistik und Sprachtechnologie. K.-U. Carstensen et al. (ed.), Spektrum Lehrbuch, 2001.
Speech and Language Processing. Jurafsky and Martin, Prentice Hall, 2000.
Robert Dale (1989). Cooking up referring expressions. Annual Meeting of the ACL Proceedings of the 27th annual meeting on Association for Computational Linguistics, pp. 68-75
Ehud Reiter (1990). The computational complexity of avoiding conversational implicatures Proceedings of the 28th annual meeting on Association for Computational Linguistics, pp. 97 - 104
Robert Dale and Nicholas Haddock (1991) Generating referring expressions involving relations Proceedings of the 1991 Meeting of the European Chapter of the Association for Computational Linguistics, pp. 161-166
R. Dale, E. Reiter. Computational Interpretations of the Gricean Maxims in the Generation of Referring Expressions. Cognitive Science 18, pp. 233-263, 1995.
C. Gardent. Generating Minimal Definite Descriptions. In Proc. of ACL-2002, pp. 96-103, 2002.
K. van Deemter. Generating Referring Expressions: Boolean Extensions of the Incremental Algorithm. Computational Linguistics, 28(1), pp. 37-52, 2002.
H. Horacek. A Best-First Search Algorithm for Generating Referring Expressions. In Proc. of EACL'2003, pp. 206-213, 2003.
Bernd Bohnet and Robert Dale. (2005) Viewing Referring Expression Generation as a Search Problem. Nineteenth International Joint Conference on Artifical Intelligence (IJCAI). Edinburgh.
Collins, M. (2003). Head-driven statistical models for natural language parsing. Computational Linguistics, 29(4), 589--637.
Bernd Kiefer, Hans-Ulrich Krieger, John Carroll, and Rob Malouf. A Bag of Useful Techniques for Efficient and Robust Parsing Proceedings of the ACL-99: the 37th Annual Meeting of the Association for Computational Linguistics, University of Maryland, 1999.
Whitelock, Peter (1988): Shake-and-Bake Generation. In Proc. of COLING 88, Budapest.
Shieber, Stuart/Pereira, Fernando/van Noord, Gertjan/Moore, Robert (1990): Semantic-Head-Driven Generation. Computational Linguistics 16, 30-42.
Kay, Martin (1996): Chart Generation. In Proc. of ACL-96, Santa Cruz, CA, pp. 200-204.
Carroll, John/Copestake, Ann/Flickinger, Dan/Poznanski, Victor (1999): An Efficient Generator for (Semi-)Lexicalist Grammars. In Proc. of the 7th European Workshop on Natural Language Generation, Toulouse, France, pp. 86-95.
Michael White. Efficient Realization of Coordinate Structures in Combinatory Categorial Grammar. Research on Language and Computation, Volume 4, Number 1, June 2006, pp. 39-75
Youngmin Yi, Chao-Yue Lai, Slav Petrov, Kurt Keutzer. Efficient Parallel CKY Parsing on GPUs. Proceedings of the 12th International Conference on Parsing Technologies, Dublin, Ireland, pp. 175-185.
Brian Roark, Kristy Hollingshead, Nathan Bodenstab. Finite-State Chart Constraints for Reduced Complexity Context-Free Parsing Pipelines. Computational Linguistics 38, 2012, pp. 719-753.
Beale, Stephen (1997): Hunter-Gatherer: Applying Constraint Satsifaction, Branch-and-Bound and Solution Synthesis to Computational Semantics. Ph. Dissertation, School of Computer Science, Carnegie-Mellon University.
U. Germann, M. Jahr, K. Knight, D. Marcu, and K. Yamada (2001). Fast Decoding and Optimal Decoding for Machine Translation Proc. of the Conference of the Association for Computational Linguistics (ACL).
K. Yamada and K. Knight), 2002. A Decoder for Syntax-Based Statistical MT. Proc. of the Conference of the Association for Computational Linguistics (ACL).
Franz Josef Och, Nicola Ueffing, Hermann Ney (2001). An Efficient A* Search Algorithm for Statistical Machine Translation Data-Driven Machine Translation Workshop, pp. 55-62.
Philipp Koehn. Pharaoh: A Beam Decoder for Phrase-Based Statistical Machine Translation Models. Available at http://www.isi.edu/licensed-sw/pharaoh/
What Can Syntax-based MT Learn from Phrase-based MT? Steve De Neefe and Kevin Knight, Wei Wang and Daniel Marcu, Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 755-763, Prague, June 2007.
An Efficient Shift-Reduce Decoding Algorithm for Phrased-Based Machine Translation. Yang Feng, Haitao Mi, Yang Liu and Qun Liu Coling 2010: Poster Volume, pages 285-293, Beijing, August 2010
String-to-Dependency Statistical Machine Translation. Libin Shen, Jinxi Xu, Ralph Weischedel. Computational Linguistics Volume 36, Number 4, 649-671. 2010 Association for Computational Linguistics
Daniel Marcu (2000). The Rhetorical Parsing of Unrestricted Texts: A Surface-Based Approach. Computational Linguistics, 26 (3), pages 395-448
Huong Thang Le, Geetha Abeysinghe, and Christian Huyck (2004). Generating Discourse Structures for Written Texts. Proceedings of the 20th International Conference on Computational Linguistics (COLING 2004).
Ziheng Lin, Min-Yen Kan, Hwee Tou Ng (2009). Recognizing implicit discourse relations in the Penn Discourse Treebank. In Proceedings of the 2009 Conference on Emprical Methods in Natural Language Processing, Volume 1, EMNLP'09, pages 343-351.
Hugo Hernault, Danushka Bollegala, and Mitsuru Ishizuka (2010). HILDA: A discourse parser using support vector machine classification. Dialogue and Discourse 1(3): 1-33.
Vanessa Feng and Graeme Hirst (2012). Text-level discourse parsing with rich linguistic features. Proc. of the Conference of the Association for Computational Linguistics (ACL).
Robin, Jacques/Mc Keown, Kathleen (1996): Empirically Designing and Evaluating a New Revision-Based Model for Summary Generation. Artificial Intelligence 85, Special Issue on Empirical Methods.
James Shaw. Segregatory Coordination and Ellipsis in Text Generation. In Proc. of the 36th Association for Computational Linguistics and the 17th International Conference on Computational Linguistics, pages 1220-1226, Montreal, Canada
Helmut Horacek. Handling Dependencies in Reorganizing Content Specifications: A Case Study of Case Analysis Research on Language and Computation, Volume 4, Number 1, June 2006, pp. 111-139
Joint lecture cmputer science/computational linguistics
Oral exam
Computer science 4, CL Diploma 2, CL Bachelor 3
E-mail Helmut Horacek