Abstracts

Most tasks in natural language processing (NLP) try to map structured input (e.g., sentence or word sequence) to some form of structured output (tag sequence, parse tree, semantic graph, translated/paraphrased/compressed sentence), a problem known as structured prediction. While various learning algorithms such as the perceptron, maximum entropy, and expectation-maximization have been extended to the structured setting (and thus applicable to NLP problems), directly applying them as is to NLP tasks remains challenging for the following reasons. First, the prohibitively large search space in NLP makes exact search intractable, and in practice inexact search methods like beam search are routinely used instead. Second, the output structures are usually partially, rather than completely, annotated, which requires structured latent variables. However, the introduction of inexact search and latent components violates some key theoretical properties (such as convergence) of conventional structured learning algorithms, and requires us to develop new algorithms suitable for scalable structured learning with latent variables. In this thesis, we first investigate new theoretical properties for these structured learning algorithms with inexact search and latent variables, and then also demonstrate that structured learning with latent variables is a powerful modeling tool for many NLP tasks with less strict annotation requirements, and can be generalized to neural models.Advisors/Committee Members: Huang, Liang (advisor), Tadepalli, Prasad (committee member).