Learning Nonstructural Distance Metric by Minimum Cluster Distortion

Daichi Mochihashi, Gen-ichiro Kikui, Kenji KitaEMNLP 2004

Introduction

In Natural Language Processing (NLP), representing text as high-dimensional vectors is standard practice. However, measuring the similarity between these vectors using traditional metrics like Euclidean distance or cosine similarity often falls short. These methods typically treat every feature (e.g., a word) as independent, ignoring semantic correlations (like "car" and "automobile"). Furthermore, they rely on heuristic weighting schemes like tf-idf that are not mathematically optimized for specific tasks. This paper proposes a novel approach: learning an "optimal" distance metric by minimizing cluster distortion in training data, effectively accounting for feature correlations and optimal weighting.

Methodology: Minimizing Cluster Distortion

The authors propose a global distance metric based on the Mahalanobis distance, parameterized by a matrix $M$. The core objective is to find an $M$ that minimizes the sum of squared distances between data points and their respective cluster centroids across a training set.

Unlike many previous metric learning approaches that require iterative, computationally expensive optimization, this method derives a closed-form solution. The optimal matrix $M$ is found to be proportional to the inverse of the sum of within-cluster scatter matrices. To handle the high-dimensional and sparse nature of linguistic data, the authors utilize the Moore-Penrose pseudoinverse and apply Singular Value Decomposition (SVD) for dimensionality reduction.

Geometry of the Feature Space

The fundamental intuition behind this approach is a geometric transformation of the feature space. In the original space, clusters of related items (e.g., synonymous sentences) often form elongated ellipsoids due to strong correlations between features. By learning the metric $M$, the algorithm "warps" this space so that these ellipsoids are transformed into spheres.

The transformation from the original feature space (a), where clusters are ellipsoidal due to covariance, to the mapped space (b), where clusters become spherical under the learned metric.

As shown in the figure above, this mapping makes distance measurements more meaningful by normalizing variance and accounting for covariance across dimensions. This global metric can then be applied to new, unseen data within the same domain.

Experimental Results

The researchers evaluated the proposed metric on tasks including synonymous sentence retrieval (using a large Japanese-English paraphrase corpus), document retrieval (20-Newsgroups), and general clustering (UCI datasets).

Performance and Robustness

A key finding was a 33% increase in 11-point average precision for sentence retrieval compared to a standard Euclidean/tf-idf baseline. Qualitatively, the learned metric was much better at identifying relevant paraphrases based on semantic content rather than just superficial word overlap.

Comparison of precision between the proposed metric distance and standard Euclidean distance across different levels of dimensionality reduction.

The metric also demonstrated remarkable robustness to data compression. As illustrated in the figure above, the precision of the learned metric remains significantly higher than the Euclidean baseline even when the dimensionality is reduced to just 5% of the original feature set. This suggests that the metric successfully captures the most important structural relationships in the data.

Conclusion and Future Directions

By moving beyond "ad hoc" distance measures, this research provides a mathematically grounded way to learn similarity from data. While highly effective, the authors note that future work could improve the model by incorporating "cluster confidence" weights or extending the approach to non-linear spaces using kernel methods. Overall, minimizing cluster distortion offers a powerful tool for improving retrieval and clustering performance in complex, high-dimensional domains like NLP.

Summary updated

BibTeX
@inproceedings{mochihashi2004learning,
  author = {Daichi Mochihashi and Gen-ichiro Kikui and Kenji Kita},
  title = {{Learning Nonstructural Distance Metric by Minimum Cluster Distortion}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2004},
}
Figure