TL;DR
This paper introduces a method to efficiently sum scores of all nonprojective dependency trees for a sentence, enabling the definition of conditional probability distributions over these trees. This allows for more flexible training and decoding techniques, such as conditional maximum likelihood estimation and minimum Bayes-risk decoding, leading to competitive results on nonprojective languages.
What Problem Does This Paper Address?
Statistical dependency parsing aims to determine the syntactic structure of a sentence by identifying head-dependent relationships. While significant progress has been made, a key challenge has been the lack of proper conditional probability distributions over nonprojective dependency trees. Nonprojective trees, where dependencies can cross each other, are common in many languages. Existing state-of-the-art parsers often use discriminative models that score trees without explicitly defining a probability distribution, limiting their ability to perform marginalization over trees or employ certain training and decoding strategies. This paper addresses this gap by providing a principled way to define and work with probabilistic models of nonprojective dependency trees.
Methods
The core of the paper's contribution lies in exploiting the Matrix Tree Theorem to efficiently compute the sum of scores of all possible nonprojective dependency trees for a given sentence. This sum, denoted as $Z(x)$, is crucial for defining a conditional log-linear model, where the probability of a tree $y$ given a sentence $x$ is $p(y|x) = \frac{\exp(f(x,y))}{Z(x)}$.
The authors derive an algorithm that computes $Z(x)$ in $O(n^3)$ time using the determinant of a Kirchoff matrix. This matrix is constructed from edge scores, where each edge score is derived from a feature function $f(x, y)$. The paper also shows how to efficiently compute the gradient of the log-likelihood function, which is necessary for training these models. This gradient calculation leverages the inverse of the Kirchoff matrix, making the overall process computationally tractable.
Datasets
The experiments were conducted on four languages known to exhibit nonprojective phenomena:
- Arabic (Hajič et al., 2004)
- Czech (Böhmová et al., 2003)
- Danish (Kromann, 2003)
- Dutch (van der Beek et al., 2002)
The Danish and Dutch datasets were prepared for the CoNLL 2006 shared task, while Arabic and Czech were from the 2007 shared task. The paper focuses on unlabeled dependency parsing.
Key Insights and Ideas
- The Matrix Tree Theorem is a powerful tool for dependency parsing: The paper demonstrates that this theorem, traditionally used in graph theory, can be effectively applied to sum over all possible dependency trees, a problem that was previously computationally challenging for nonprojective structures.
- Conditional probability distributions unlock new possibilities: By enabling the definition of $p(y|x)$, the authors open the door to techniques like:
- Marginalization: Computing probabilities of specific dependency relations, regardless of the overall best parse.
- Minimum Bayes-Risk Decoding: A more robust decoding strategy than maximum a posteriori (MAP) decoding, especially when the model's assumptions don't perfectly align with the loss function.
- Hidden Variable Training: Allowing for more sophisticated learning by incorporating latent variables.
- Edge-factored models are key: The approach relies on edge-factored models, where dependencies are conditionally independent given the sentence. This tractability is crucial for the efficiency of the Matrix Tree Theorem approach.
- Conditional training can be competitive: The paper shows that conditional training, enabled by their summing algorithm, achieves performance comparable to state-of-the-art discriminative methods like MIRA.
Key Results
- The proposed method allows for conditional maximum likelihood estimation of nonprojective dependency models.
- Competitive experimental results were achieved on four nonprojective languages for unlabeled dependency parsing.
- The paper demonstrates the utility of the approach for minimum Bayes-risk decoding, showing it can improve performance for conditionally trained models and is a valuable technique for non-edge-factored models.
- Experiments with hidden variable training were also explored, though improvements were modest.
- Training and inference are efficient, with the summing algorithm running in $O(n^3)$ time.
Limitations and Future Work
- Hidden Variable Training Modesty: While explored, adding latent features (clusters) to edge features did not yield significant improvements. The authors suggest this might be due to needing more clusters, improved clustering methods, or the inherent structural limitations of edge-factored models in capturing complex dependencies.
- Minimum Bayes-Risk Decoding: While beneficial, its impact on conditionally trained models was less pronounced than expected, possibly due to the edge-factored nature of the model where edges are conditionally independent.
- Future Work: The authors suggest exploring approximations for $Z(x)$ when dealing with richer, non-edge-factored models, and investigating variational approaches for conditional estimation with latent variables. They also propose further research into incorporating soft clusters and exploring word token clustering.
Summary updated