A Constraint Satisfaction Approach to Dependency Parsing

Sander Canisius, Erik Tjong Kim SangEMNLP 2007

TL;DR

This paper introduces a novel dependency parsing method that frames the problem as a weighted constraint satisfaction problem (W-CSP). By training classifiers to predict weighted "soft" constraints on different aspects of dependency trees, they can leverage existing W-CSP solvers to find the optimal parse, achieving promising results across ten languages.

What Problem Does This Paper Address?

Dependency parsing aims to determine the grammatical relationships between words in a sentence, often represented as a tree structure. While various machine learning approaches exist, this paper tackles the challenge of effectively integrating global structural information into the parsing process. Traditional methods often make local decisions without a clear mechanism to ensure the overall coherence and validity of the resulting dependency tree. The authors propose using constraint satisfaction, a well-established AI technique for solving problems with interdependent variables, to address this by ensuring the entire tree structure satisfies a set of learned constraints.

Methods

The core of the paper is the adaptation of a constraint satisfaction inference method for dependency trees. They formulate dependency parsing as a Weighted Constraint Satisfaction Problem (W-CSP), defined by variables (each token in the sentence), domains (possible dependency relations and head tokens), constraints (learned relationships between tokens), and weights (confidence scores from classifiers).

Three types of classifiers are trained to predict these constraints:

  • Cdep (head, modifier, relation): Predicts the type of dependency relation between a head and a modifier. This is the primary constraint type, similar to previous work.
  • Cdir (modifier, direction): Predicts the relative position (left/right) of a modifier to its head.
  • Cmod (head, relation): Predicts the type of relation by which a head is modified.

These classifiers predict "soft" constraints, meaning they have associated weights reflecting the confidence of the prediction. The W-CSP solver then aims to find an assignment of values to variables that maximizes the sum of weights of satisfied constraints, effectively producing the best dependency tree. To efficiently find the optimal solution, they employ the CKY algorithm, which has cubic time complexity and implicitly enforces projectivity and acyclicity, desirable properties of dependency trees.

Datasets

The system was evaluated on all ten datasets from the CoNLL-2007 shared task on dependency parsing. The paper does not introduce new datasets but rather applies the proposed method to existing benchmark data.

Key Insights and Ideas

  • Framing Parsing as Constraint Satisfaction: The paper demonstrates that dependency parsing can be effectively modeled as a W-CSP, allowing the leverage of powerful general-purpose solvers.
  • Combining Local Classifiers for Global Structure: By training classifiers to predict overlapping "soft" constraints on different aspects of the dependency tree, the system can implicitly capture global structural properties even though the classifiers operate locally.
  • The Power of Soft Constraints: The use of weighted constraints allows the system to tolerate some prediction errors from individual classifiers. Conflicting constraints are resolved by choosing the assignment that maximizes the total weight of satisfied constraints, making the system robust to imperfect predictions.
  • Importance of Cdir and Cmod Constraints: The results suggest that adding Cdir and Cmod constraints, beyond the basic Cdep constraints, generally improves performance, indicating their value in capturing important structural information.
  • Cdep Classifier as a Bottleneck: The Cdep classifier, which also defines the domains of variables, is identified as a potential bottleneck. Its recall significantly impacts the number of out-of-domain errors, highlighting the importance of its accuracy.

Key Results

  • The proposed system achieved consistent improvements over the baseline parser (Canisius et al., 2006a) across most of the ten languages, with increases in labelled attachment score typically between 1.0 and 2.0 percent.
  • Supplementing the Cdep-only parser with hard constraints for acyclicity and projectivity (via CKY) already yielded performance improvements.
  • Adding Cmod and Cdir constraints further boosted performance for most languages, with the full system (all constraints) working best for all but Turkish and Hungarian.
  • For English, the system achieved its highest score, correlating with a high recall (90%) from the Cdep classifier, suggesting that high recall can compensate for lower precision in the W-CSP framework.

Limitations and Future Work

  • No Extensive Optimization: The authors acknowledge that no extensive parameter optimization or feature engineering was performed, suggesting that further tuning could lead to even better scores.
  • Cdep Classifier Performance: The Cdep classifier is identified as a potential bottleneck, and its performance (especially recall) significantly influences the overall system.
  • Future Work: Future work will focus on tuning the numerous parameters of the system and exploring different types of constraints to supplement or replace the current ones. Experimenting with different constraint configurations and further improving the Cdep classifier are also promising directions.

Summary updated

BibTeX
@inproceedings{canisius2007constraint,
  author = {Sander Canisius and Erik Tjong Kim Sang},
  title = {{A Constraint Satisfaction Approach to Dependency Parsing}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2007},
}
Figure