Abstract
Zied Bouraoui, Shoaib Jameel, Steven Schockaert. Proceedings of the 27th International Conference on Computational Linguistics.
2018.
Introduction
Word embeddings are renowned for capturing semantic relationships through vector arithmetic, famously exemplified by the analogy "king is to queen as man is to woman." However, while these embeddings excel at solving specific analogies, they often struggle with relation induction—the task of identifying all word pairs that satisfy a given relationship within a large vocabulary.
The authors identify two primary challenges in this domain:
- The Needle in a Haystack Problem: In a typical vocabulary, the number of incorrect pairs vastly outweighs the correct ones. Even models with high average accuracy can be overwhelmed by false positives when searching through billions of potential pairs.
- Dimension Irrelevance: Standard vector arithmetic treats all dimensions equally, whereas specific relations (e.g., "capital of") may only depend on a small subset of features, with the rest acting as noise.
Methodology
To address these issues, this paper proposes moving from deterministic arithmetic to probabilistic modeling. Two distinct approaches are introduced:
Probabilistic Translation Model
This model assumes that a relation is a translation between two regions of the vector space. It introduces two key components:
- Type Constraints: The "source space" and "target space" are modeled as Gaussian distributions. This ensures that for a geographic relation, the model only considers pairs where the source "looks like" a city and the target "looks like" a country.
- Gaussian Translations: Instead of a fixed offset vector, the relationship is modeled as a Gaussian distribution. This allows the model to automatically down-weight dimensions that exhibit high variance across training examples.
Bayesian Linear Regression Model
A more flexible approach assumes a linear mapping $t = Ws$. To prevent overfitting in high-dimensional spaces with limited data, the authors use Singular Value Decomposition (SVD) to project source words into a lower-dimensional subspace before performing the regression.
Evaluation and Results
The models were tested across four word embeddings (Skip-gram and GloVe) and three benchmarks: the Google Analogy Test Set, BATS, and DiffVec.
Key Performance Metrics
The proposed Translation model (Trans) consistently outperformed standard baselines like 3CosAvg (3CA) and Support Vector Machines (SVM) across nearly all datasets in terms of F1 score and Mean Average Precision (MAP).
As shown in the results table, the Translation model achieved a MAP of 0.906 on the Google dataset (using SG-Wiki embeddings), a significant improvement over the 0.736 achieved by the 3CosAvg baseline. The Regression model (Regr) proved particularly effective on datasets like DiffVec, where larger training sets allowed it to learn more complex mappings.
Conclusion
The study demonstrates that modeling the "type" of words involved in a relation is as critical as modeling the relationship itself. By incorporating soft constraints and probabilistic variance, these models achieve greater robustness against the "false positive" problem inherent in large-scale relation induction. Future work will explore low-rank approximations for covariance matrices and the use of hierarchical priors to improve performance on data-sparse relations.
Summary updated