Induction of Greedy Controllers for Deterministic Treebank Parsers

Induction of Greedy Controllers for Deterministic Treebank Parsers Tom Kalt Department of Computer Science University of Massachusetts Amherst, MA 01003-9264 kalt@cs.umass.edu Abstract Most statistical parsers have used the gram- mar induction approach, in which a stochastic grammar is induced from a treebank. An alter- native approach is to induce a controller for a given parsing automaton. Such controllers may be stochastic; here, we focus on greedy con- trollers, which result in deterministic parsers. We use decision trees to learn the controllers. The resulting parsers are surprisingly accurate and robust, considering their speed and simplic- ity. They are almost as fast as current part-of- speech taggers, and considerably more accurate than a basic unlexicalized PCFG parser. We also describe Markov parsing models, a general framework for parser modeling and control, of which the parsers reported here are a special case. 1 Introduction A fundamental result of formal language the- ory is that the languages defined by context-free grammars are the same as those accepted by push-down automata. This result was recently extended to the stochastic case (Abney, et al., 1999). There are thus two main approaches to training a statistical parser: inducing stochastic grammars and inducing stochastic automata. Most recent work has employed grammar induc- tion (Collins, 1999; Charniak, 2000). Examples of the automaton-induction approach are Her- mjakob (1997), which described a determinis- tic parser, and Ratnaparkhi (1998), which de- scribed a stochastic parser. The deterministic parsers reported in this pa- per are greedy versions of stochastic parsers based on Markov parsing models, described in section 3.3. A greedy parser takes the single most probable action at every choice point. It thus does the minimum amount of search pos- sible. There will always be a tradeoff between speed on the one hand and accuracy and robust- ness on the other. Our aim, in studying greedy parsers, is to find out what levels of coverage and accuracy can be attained at the high-speed extreme of this tradeoff. There is no guarantee that a greedy parser will find the best parse, or indeed any complete parse. So the accuracy and coverage of greedy parsers are both interesting empirical questions. We find that they are al- most as fast as current part-of-speech taggers, and they outperform basic unlexicalized PCFG parsers. While coverage is a concern, it is quite high (over 99%) for some of our parsers. 2 Previous work Markov parsing models are an example of the history-based parsing approach (Black, et al., 1992). History-based parsing, broadly interpreted, includes most statistical parsers. Markov parsing models take a more automaton- oriented (or control-oriented) view of what his- tory means, compared to the more grammar- oriented view of the original paper and most subsequent work. Hermjakob (1997) described a deterministic shift-reduce parser. The control is learned by a hybrid of decision trees and decision lists. This work also used a rich hand-crafted semantic on- tology. The state representation contained over 200 features, although it still worked rather well when this was reduced to 12. A notable …

Content truncated to 500 words