Supervised Word Mover's Distance

Gao Huang, Chuan Guo, Matt J. Kusner, Yu Sun, Fei Sha, Kilian Q. WeinbergerNeurIPS 2016 · OpenReview

TL;DR

The Word Mover’s Distance (WMD) is a powerful unsupervised metric for document similarity, but it lacks the ability to adapt to specific tasks. Supervised Word Mover’s Distance (S-WMD) fixes this by learning a task-specific metric that transforms word embeddings and re-weights word importance, significantly outperforming unsupervised WMD and dozens of other baselines in document classification.

What Problem Does This Paper Address?

Measuring the "distance" between two documents is fundamental to search engines, recommendation systems, and text classification. Traditional methods like Bag-of-Words (BOW) or TF-IDF often fail because they treat words as discrete tokens; if two documents use different words to describe the same concept (e.g., "physician" vs. "doctor"), BOW sees them as entirely different.

The Word Mover’s Distance (WMD) solved this by using word embeddings (like word2vec) to calculate the "cost" of transforming one document into another based on the semantic distance between their words. However, WMD is unsupervised. It assumes that the semantic relationships in pre-trained embeddings are perfectly suited for every task. In reality, a "distance" that works for sentiment analysis (where "good" and "bad" are far apart) might be terrible for topic classification (where "good" and "bad" might both appear in movie reviews).

Methods

The authors propose S-WMD, which introduces supervision into the WMD framework through two primary learnable components:

  1. Linear Transformation ($A$): Instead of using raw word embeddings, the model learns a matrix $A$ that transforms the embedding space ($x_i \to Ax_i$). This allows the model to "stretch" or "compress" dimensions of the word vectors that are most relevant to the specific classification task.
  2. Word Importance Weights ($w$): Not all words are equally informative. S-WMD learns a weight vector $w$ that re-scales the word frequencies in a document, effectively learning which words are "signal" and which are "noise" for a given label.

The Technical Secret Sauce:

  • NCA Framework: To train these parameters, the authors use Neighborhood Components Analysis (NCA). This minimizes the "stochastic leave-one-out" classification error, essentially training the metric so that a document's nearest neighbors are likely to share its label.
  • Sinkhorn Distance: Calculating the exact WMD gradient is computationally expensive ($O(q^3 \log q)$). The authors utilize the Sinkhorn distance, an entropy-regularized version of optimal transport, to provide a fast, differentiable approximation ($O(q^2)$) that makes training feasible on large datasets.
  • Smart Initialization: They initialize the matrix $A$ using a simpler, faster metric called Supervised Word Centroid Distance (S-WCD), which gives the optimization a significant head start.

Datasets

The authors evaluated S-WMD on 8 real-world text datasets covering various tasks:

  • Topic Categorization: BBCSPORT, REUTERS, 20NEWS.
  • Sentiment Analysis: TWITTER, AMAZON.
  • Specialized Domains: RECIPE (origin), OHSUMED (medical abstracts), CLASSIC (academic publishers).

They compared S-WMD against 26 competitive baselines, including various combinations of BOW, TF-IDF, LSI, LDA, and mSDA, paired with metric learning algorithms like LMNN and ITML.

Key Insights and Ideas

  • Supervision is a Force Multiplier: While unsupervised WMD is already strong, adding task-specific supervision allows it to ignore irrelevant semantic similarities. For example, in sentiment analysis, "happy" and "sad" are semantically related but should be far apart; S-WMD learns to enforce this.
  • The "Word Importance" Vector is Crucial: By learning $w$, the model can automatically down-weight stop words or domain-specific "chatter" that doesn't help distinguish between classes.
  • Approximation is Better Than Perfection: The use of the Sinkhorn relaxation proves that you don't need an exact solution to the optimal transport problem to compute effective gradients for metric learning.
  • Efficiency via Pruning: To speed up training, the authors only compute NCA probabilities for the $M$ nearest neighbors (defined by the cheaper WCD distance), which prevents the complexity from exploding as the number of documents increases.

Key Results

  • State-of-the-Art Performance: S-WMD achieved the lowest kNN test error on 5 out of 8 datasets.
  • Superior Average Rank: Across all 26 baselines, S-WMD maintained the best average rank (2.4), significantly outperforming the original unsupervised WMD (6.1).
kNN Test Error Comparison
  • Visual Clustering: t-SNE visualizations show that S-WMD creates much tighter, more distinct clusters of document classes compared to the unsupervised version.
t-SNE Visualizations of WMD vs S-WMD
  • Significant Error Reduction: On the OHSUMED dataset, S-WMD reduced the error of the previous state-of-the-art (LSI) by 22%.

Limitations and Future Work

  • Computational Cost: Even with Sinkhorn and neighbor pruning, S-WMD is more computationally intensive than simple linear models or BOW-based methods. Training on the 20NEWS dataset took nearly 2 hours.
  • Pre-trained Dependency: The method relies heavily on the quality of the initial word embeddings. If the underlying embeddings (e.g., word2vec) haven't captured a specific technical vocabulary, the affine transformation $A$ might struggle to compensate.
  • Euclidean Assumption: The authors note that S-WMD uses squared Euclidean distance between transformed vectors. For some datasets (like CLASSIC), this might be sub-optimal compared to other distance measures, suggesting that exploring non-Euclidean ground metrics could be a future direction.

Summary updated

Abstract

Accurately measuring the similarity between text documents lies at the core of many real world applications of machine learning. These include web-search ranking, document recommendation, multi-lingual document matching, and article categorization. Recently, a new document metric, the word mover's distance (WMD), has been proposed with unprecedented results on kNN-based document classification. The WMD elevates high quality word embeddings to document metrics by formulating the distance between two documents as an optimal transport problem between the embedded words. However, the document distances are entirely unsupervised and lack a mechanism to incorporate supervision when available. In this paper we propose an efficient technique to learn a supervised metric, which we call the Supervised WMD (S-WMD) metric. Our algorithm learns document distances that measure the underlying semantic differences between documents by leveraging semantic differences between individual words discovered during supervised training. This is achieved with an linear transformation of the underlying word embedding space and tailored word-specific weights, learned to minimize the stochastic leave-one-out nearest neighbor classification error on a per-document level. We evaluate our metric on eight real-world text classification tasks on which S-WMD consistently outperforms almost all of our 26 competitive baselines.
BibTeX
@inproceedings{huang2016supervised,
  author = {Gao Huang and Chuan Guo and Matt J. Kusner and Yu Sun and Fei Sha and Kilian Q. Weinberger},
  title = {{Supervised Word Mover's Distance}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2016},
  url = {https://openreview.net/forum?id=B1Zc5LWu-H},
}
Figure