Efficient Incremental Beam-Search Parsing with Generative and Discriminative Models
This talk will present several issues related to incremental (left-to-right) beam-search parsing of natural language using generative or discriminative models, either individually or in combination. The first part of the talk will provide background in incremental top-down and (selective) left-corner beam-search parsing algorithms, and in stochastic models for such derivation strategies. Next, the relative benefits and drawbacks of generative and discriminative models with respect to heuristic pruning and search will be discussed. A range of methods for using multiple models during incremental parsing will be detailed. Finally, we will discuss the potential for effective use of fast, finite-state processing, e.g. part-of-speech tagging, to reduce the parsing search space without accuracy loss. POS-tagging is shown to improve efficiency by as much as 20-25 percent with the same accuracy, largely due to the treatment of unknown words. In contrast, an 'islands-of-certainty' approach, which quickly annotates labeled bracketing over low-ambiguity word sequences, is shown to provide little or no efficiency gain over the existing beam-search.