📄 Experiments with a Multilanguage Non-Projective Dependency Parser

Summary

The paper presents a fast, multilingual dependency parser built for the CoNLL-X shared task. It targets two practical issues: the high training cost of accurate classifiers such as SVM, and the trees with crossing arcs (non-projective trees) that ordinary Shift/Reduce parsers cannot build. Attardi extends the deterministic bottom-up parser of Yamada and Matsumoto (2003) in two ways. First, it predicts dependency labels during parsing. Second, it adds six new actions (Right2/Left2, Right3/Left3, Extract/Insert) that link or temporarily set aside tokens deeper in the stack, so non-projective arcs are built directly instead of through pseudo-projective pre- and post-processing. The submitted runs used a custom C++ Maximum Entropy classifier with no external resources. Features were drawn from lemmas, coarse POS tags, a compact morphology token and previous actions. The parser processes about 200 sentences per second and needs minutes to hours to train. Memory Based Learning gives up to 5% higher accuracy but parses far more slowly. The work shows that a cheap, modular transition parser can cover all non-projectivity seen in the PDT and still stay practical.

Key points

• The new actions cover every non-projective case in the Czech training data. Of 28,081 such relations, 26,346 are handled by Left2/Right2, 1,683 by Left3/Right3, and only 52 require Extract/Insert.
• With Maximum Entropy, training takes about 15 minutes for the Portuguese treebank and about 4 hours for Czech. Parsing averages roughly 200 sentences per second.
• SVM (TinySVM, LIBSVM) was impractical. It could not be trained on the larger corpora, and on Portuguese it ran over 4 days and produced an unusable model. MBL trained faster and was up to 5% more accurate, but parsing was much slower.
• Among the extra features tested, only including the previous parser action helped. Splitting the decision across two or three specialized classifiers brought no gain.
• Assigning a default per-language label to the root raised LAS. The Snowball stemmer supplied LEMMA values for Danish, German and Swedish, which improved both accuracy and speed.

Interesting ideas

• I1. Extend the action set instead of transforming the data. Adding reduce actions that reach the second or third stack element handles crossing arcs inside the parser itself. This avoids the lift-and-restore pipeline and could suit any transition system for free-word-order languages such as Ukrainian.
• I2. Measure how often each mechanism is needed. Counting which action each gold non-projective arc requires shows where effort pays off: most cases need only depth-2 actions. A coverage check of this kind is a cheap way to justify design choices in any structured predictor.
• I3. Use a fast learner as a feature-engineering testbed. Because one Maximum Entropy experiment on Portuguese took under 15 minutes, many feature sets could be tried quickly. The conclusions could then be carried over to slower, more accurate learners.
• I4. Try a simple post-hoc fix. Labelling the root with a per-language default gave a measurable LAS gain for almost no work. Similar targeted repairs could pay off elsewhere, for example stripping the PDT coordination and apposition suffixes (_Co, _Ap, _Pa) before training and restoring them afterwards.
• I5. Give rare phenomena their own training data. Non-projective arcs are too rare for a general classifier to learn well. The author suggests a dedicated second classifier and tested training on only the sentences with crossing arcs, which reached 65.28% LAS and 76.20% UAS on Czech with MBL. The same approach could help other rare structures or low-resource cases.