05 Aug 2016 - Mike Lewis: Seminar
Recursive neural models perform well for many structured prediction problems, in part due to their ability to learn representations that depend globally on all parts of the output structures. However, global models of this sort are incompatible with existing exact inference algorithms, since they do not de-compose over substructures in a way that allows effective dynamic programming. Existing work has therefore used greedy inference techniques such as beam search or reranking. We introduce the first global recursive neural parsing approach with optimality guarantees for decoding and use it to build a state-of-the-art CCG parser. To support global features, we give up dynamic programs and instead search directly in the space of all possible subtrees. Although this space is exponentially large in the sentence length, we show it is possible to learn an efficient A* parser. We augment existing parsing models, which have informative bounds on the outside score, with a global model that has loose bounds but only needs to model non-local phenomena. To train the global model, we define a new loss function over agenda states, which encourages the parser to explore a tiny fraction of the search space. The approach is applied to CCG parsing, and achieves new state-of-the-art results. The parser finds the optimal parse for 99.9% of held-out sentences, exploring on average only 190 subtrees.
Mike Lewis is a postdoc at the University of Washington, working with Luke Zettlemoyer on semantic parsing. In late 2016, he will join Facebook AI Research. Previously, he received an Undergraduate Masters degree in Computer Science from Oxford University, worked as a software engineer at Metaswitch Networks, completed an internship at Google Research (working with Yasemin Altun), and has a PhD from the University of Edinburgh (supervised by Mark Steedman). http://homes.cs.washington.edu/~mlewis/