Automatic Discovery of Feature Sets for Dependency Parsing

Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 824–832, Beijing, August 2010 Automatic Discovery of Feature Sets for Dependency Parsing Peter Nilsson Pierre Nugues Department of Computer Science Lund University peter.nilsson.lund@telia.com Pierre.Nugues@cs.lth.se Abstract This paper describes a search procedure to discover optimal feature sets for depen- dency parsers. The search applies to the shift–reduce algorithm and the feature sets are extracted from the parser configura- tion. The initial feature is limited to the first word in the input queue. Then, the procedure uses a set of rules founded on the assumption that topological neighbors of significant features in the dependency graph may also have a significant contri- bution. The search can be fully automated and the level of greediness adjusted with the number of features examined at each iteration of the discovery procedure. Using our automated feature discovery on two corpora, the Swedish corpus in CoNLL-X and the English corpus in CoNLL 2008, and a single parser system, we could reach results comparable or bet- ter than the best scores reported in these evaluations. The CoNLL 2008 test set contains, in addition to a Wall Street Jour- nal (WSJ) section, an out-of-domain sam- ple from the Brown corpus. With sets of 15 features, we obtained a labeled attach- ment score of 84.21 for Swedish, 88.11 on the WSJ test set, and 81.33 on the Brown test set. 1 Introduction The selection of relevant feature sets is crucial to the performance of dependency parsers and this process is still in large part manual. More- over, feature sets are specific to the languages be- ing analyzed and a set optimal for, say, English can yield poor results in Chinese. With depen- dency parsers being applied today to dozens of languages, this makes the parametrization of a parser both a tedious and time-consuming opera- tion. Incidentally, the advent of machine-learning methods seems to have shifted the tuning steps in parsing from polishing up grammar rules to the optimization of feature sets. And as with the writ- ing of a grammar, the selection of features is a challenging task that often requires a good deal of effort and inspiration. Most automatic procedures to build feature sets resort to greedy algorithms. Forward selection constructs a set by adding incrementally features from a predetermined superset while backward elimination removes them from the superset (At- tardi et al., 2007). Both methods are sometimes combined (Nivre et al., 2006b). The selection pro- cedures evaluate the relevance of a candidate fea- ture in a set by its impact on the overall parsing score: Does this candidate improve or decrease the performance of the set? Greedy search, although it simplifies the design of feature sets, shows a major drawback as it starts from a closed superset of what are believed to be the relevant features. There is a broad consen- sus on a common feature set including the words close to the top of the stack or the beginning of the queue, for the shift–reduce algorithm, …

Content truncated to 500 words