TL;DR
This paper introduces the AI-KU system, which enhances dependency parsing by incorporating unsupervised word features derived from contextual, morphological, and orthographic properties. By representing words as vectors on a 25-dimensional sphere, the system achieves improved parsing accuracy for several languages, demonstrating the value of these novel, data-driven features.
What Problem Does This Paper Address?
Dependency parsing aims to understand the grammatical structure of sentences by identifying relationships between words. Traditional parsers often rely on hand-crafted features or features extracted from annotated data. However, for morphologically rich languages (languages with complex word structures and many inflections), creating effective features can be challenging and labor-intensive. This paper addresses the need for robust, unsupervised features that can improve dependency parsing performance, especially for these complex languages, without requiring extensive manual annotation.
Methods
The AI-KU system generates unsupervised features through a multi-step process:
- Substitute Vectors: For each target word, the system identifies its most likely substitute words within a given context using a statistical language model (specifically, a 4-gram model built with SRILM). These substitute words and their probabilities form a "substitute vector."
- Morphological and Orthographic Features: Morphological features are induced using an unsupervised HMM-based model (Morfessor), which segments words into morphemes. Orthographic features capture properties like capitalization, presence of hyphens, and apostrophes.
- Co-occurrence Embedding (S-CODE): The core of the feature generation is the Spherical Co-occurrence Data Embedding (S-CODE) framework. This method positions word tokens, their sampled substitutes, and their morphological/orthographic features onto a 25-dimensional sphere. Words with similar contextual, morphological, and orthographic properties are placed closer together on this sphere, creating a dense representation.
- Integration with Parsers: These generated 25-dimensional word embeddings are then used as auxiliary features for dependency parsers, specifically MaltParser and MaltOptimizer. The parsers are configured to utilize these new features. The authors explore three ways to use these embeddings:
- Real-valued vectors: Using the raw 25-dimensional vectors directly.
- Discretization: Binning each dimension of the vectors into a fixed number of bins.
- Clustering: Applying a modified k-means algorithm to cluster the word embeddings, using the cluster ID as a feature.
Datasets
The paper utilizes several unlabeled corpora for feature induction and evaluation:
- Europarl Corpus: Used for French, Hungarian, Polish, and Swedish.
- CONLL-X German Corpus: Used for German.
- HaAretz and Arutz 7 corpora: Combined for Hebrew.
The evaluation is performed on the SPMRL 2013 Shared Task datasets, which include gold-standard annotations for dependency parsing.
Key Insights and Ideas
- Contextual Substitutes as Rich Features: The idea of using likely word substitutes derived from a language model as a proxy for contextual meaning is a powerful way to capture semantic similarity without explicit word embeddings like Word2Vec (which were less common or accessible at the time).
- Unsupervised Morphological Induction: Leveraging unsupervised methods like Morfessor to extract morphological information is crucial for handling morphologically rich languages, where word forms can vary significantly.
- Spherical Embeddings for Co-occurrence: The S-CODE framework's application to word features is novel. Placing these features on a sphere allows for a geometrically intuitive representation of relationships, potentially capturing nuanced similarities.
- Clustering Outperforms Other Methods: The experiments consistently show that clustering the word embeddings yields the best results, suggesting that discrete word categories derived from these embeddings are more beneficial for dependency parsing than raw or binned vectors.
Key Results
The AI-KU system showed improvements for several languages in the SPMRL 2013 Shared Task:
- German (MaltParser): Real-valued embeddings showed slight improvements over the baseline.
- German (MaltOptimizer): Clustering provided the best results, outperforming the baseline, though not always significantly.
- French, Hungarian, Polish, Swedish, Hebrew: The paper reports results for their AI-KU systems. For Polish, the AI-KU system significantly outperformed the MaltOptimizer baseline. For other languages, the performance was comparable or slightly better than the baseline.
- Multi-Word Expressions (French): The AI-KU system demonstrated significantly better performance in capturing Multi-Word Expressions compared to the MaltOptimizer baseline.
Limitations and Future Work
- Fixed Parameter Settings: The authors acknowledge that using the same number of clusters and embedding dimensions across all languages might not be optimal. They suggest that finding language-specific optimal settings is a promising future direction.
- Feature Function Exploration: The paper used a limited set of feature functions (Input and Stack). Exploring other feature function configurations could lead to further improvements.
- Parameter Optimization for Induction: The parameters for co-occurrence embedding and morphological induction were adopted from previous work and might not be optimal for this specific task. Finding optimal parameters for these induction steps is suggested as future work.
- Real-valued Embeddings for MaltOptimizer: The paper suggests using real-valued word embeddings and unsupervised word categories as auxiliary features in the training phase of MaltOptimizer as a future direction.
Summary updated