Colloquium Details
Linear-time Algorithms in Natural Language Understanding and Learning
| Author: | Liang Huang, Assistant Professor City University of New York (CUNY) |
|---|---|
| Date: | February 17, 2015 |
| Time: | 15:30 |
| Location: | 220 Deschutes |
Abstract
Why are computers so bad at understanding natural language and why are human-beings so much better at it? Can we build a model to simulate human language processing so that computers can process human language the same way we humans do, i.e., fast, incremental (left-to-right) and accurate?
In this talk I'll present a linear-time dynamic programming model for incremental parsing inspired by human sentence processing (from psycholinguistics) as well as compiler theory (LR parsing). This model, being linear-time, is much faster than, but also as accurate as, the dominant cubic-time algorithms. It overcomes the ambiguity explosion problem by approximate dynamic programming, which corresponds to local ambiguity packing in psycholinguistics.
But how do we efficiently learn such a parsing model with approximate inference from huge amounts of data? We propose a general structured machine learning framework based on the structured perceptron that is guaranteed to succeed with inexact search and works well in practice. Our new learning algorithm can learn a large-scale state-of-the-art parsing model with dramatically reduced training time, thus having the potential to scaling up to the whole Web. More importantly, our learning algorithms are widely applicable to other structured domains such as bioinformatics.
Biography
Liang Huang is currently an Assistant Professor at the City University of New York (CUNY) and a part-time Research Scientist at IBM T. J. Watson Research Center. He graduated in 2008 from Penn and has worked as a Research Scientist at Google and a Research Assistant Professor at USC/ISI. Most of his work develops fast algorithms and provable theory to speedup large-scale natural language processing and structured machine learning. He has received a Best Paper Award at ACL 2008, several best paper nominations (ACL 2007, EMNLP 2008, and ACL 2010), two Google Faculty Research Awards (2010 and 2013), and a University Teaching Prize at Penn (2005).