Incremental and Predictive Dependency Parsing under Real-Time Conditions

Proceedings of Recent Advances in Natural Language Processing, pages 373–381, Hissar, Bulgaria, 7-13 September 2013. Incremental and Predictive Dependency Parsing under Real-Time Conditions Arne K¨ohn and Wolfgang Menzel Fachbereich Informatik Universit¨at Hamburg {koehn, menzel}@informatik.uni-hamburg.de Abstract We present an incremental dependency parser which derives predictions about the upcoming structure in a parse-as-you- type mode. Drawing on the inherent strong anytime property of the underlying transformation-based approach, an exist- ing system, jwcdg, has been modified to make it truly interruptible. A speed-up was achieved by means of parallel pro- cessing. In addition, MaltParser is used to bootstrap the search which increases ac- curacy under tight time constraints. With these changes, jwcdg can effectively uti- lize the full time span until the next word becomes available which results in an op- timal quality-time trade-off. 1 Introduction Users prefer incremental dialogue systems to their non-incremental counterparts (Aist et al., 2007). For a syntactic parser to contribute to an incre- mental dialogue system or any other incremental NLP application, it also needs to work incremen- tally. However, parsers usually operate on whole sentences only and few parsers exist that are capa- ble of incremental parsing or are even optimized for it. This paper focuses on using a parser as part of an incremental pipeline that requires timely re- sponse to natural language input. In such a sce- nario, delay imposed by a parser’s lookahead is more severe than delay caused by parsing speed since the parsing speed is capped by the user’s input speed. Depending on the input method, the maximum typing speed varies between 0.75 seconds per word (qwerty keyboard) and 6 sec- onds per word (mobile 12-key multi-tap) (Arif and Stuerzlinger, 2009) and is usually lower if the sen- tence has to be phrased while typing. In such a scenario, the objective of the parser is to yield high quality results and produce them as soon as they are needed by a subsequent compo- nent. It is rarely known beforehand when the next word will be available for processing. Therefore, in an incremental pipeline a) computation should continue until the next word occurs if this might contribute to a better result, and b) a new word should be included immediately to avoid delays. A parser which works pull-based, i.e. processes one prefix until it is deemed finished and then pulls the next word, is insufficient under conditions, since it would require to determine the time used for processing before the processing can even start. Either the estimated processing time will be too short, violating a), or it will be too long, violating b). In contrast, push-based architectures can meet both requirements since the processing of the pre- fix can be interrupted when new input is available. Beuck et al. (2011) showed that Weighted Con- straint Dependency Grammar-based parsers are capable of producing high-quality incremental re- sults but neglected the processing time needed for each increment. In this paper, we will use jwcdg1, a reimplementation of the WCDG parser written in Java. jwcdg uses …

Content truncated to 500 words