Visualizing Similarity Data with a Mixture of Maps.

James Cook, Ilya Sutskever, Andriy Mnih, Geoffrey E. HintonAISTATS 2007 · OpenReview

Abstract

We show how to visualize a set of pairwise similarities between objects by using several different two-dimensional maps, each of which captures different aspects of the similarity structure. When the similarity data is ambiguous, a single map cannot avoid placing unrelated objects close to each other. By using a mixture of maps, we can represent each object as a point in each map and assign it a map-specific mixing proportion. This allows the different meanings of a polysemous object to be captured by its locations in different maps. We also describe a robust version of Stochastic Neighbor Embedding (SNE) that uses a uniform background distribution to ensure that every pair of objects has a baseline similarity, which helps to prevent the "crowding problem" in low-dimensional visualizations.

Introduction

Visualizing high-dimensional similarity data in 2D is a fundamental challenge in data science. Traditional methods like Principal Component Analysis (PCA) or Metric Multidimensional Scaling (MDS) focus on preserving large distances, which often results in the loss of local manifold structure. While newer methods like Stochastic Neighbor Embedding (SNE) or Locally Linear Embedding (LLE) prioritize local neighborhoods, they face two significant geometric hurdles:

  1. Polysemy (Ambiguity): Objects often belong to multiple distinct neighborhoods. For instance, the word "bank" relates to both "river" and "finance." In a single 2D map, placing "bank" near both forces "river" and "finance" to be close to each other, creating a false relationship.
  2. The Crowding Problem: High-dimensional space has vastly more volume than 2D space. When projecting high-dimensional clusters into 2D, points in the center are crushed together, while peripheral points are pushed too far apart. This often results in "curdled" maps where distinct clusters bleed into one another.

Methodology: Aspect Maps and UNI-SNE

The authors build upon Stochastic Neighbor Embedding (SNE), which converts high-dimensional distances into conditional probabilities—the likelihood that point $i$ would select point $j$ as its neighbor. The goal is to match these with low-dimensional probabilities by minimizing the Kullback-Leibler (KL) divergence.

The Spring Analogy

This optimization can be conceptualized as a physical system of springs connecting points. The stiffness of each spring is determined by the mismatch between high-dimensional and low-dimensional probabilities. If the low-dimensional distance is too large, the spring pulls the points together; if it is too small, it pushes them apart.

The spring analogy: SNE optimization can be viewed as a system of springs where stiffness depends on the mismatch between high-dimensional and low-dimensional similarities.

Aspect Maps (AMSNE)

To address polysemy, the model introduces Aspect Maps. Instead of a single 2D projection, the model uses a mixture of several maps. Each object is assigned a "mixing proportion" for each map. Two objects will have a high similarity score if they are close together in at least one map where they both have high mixing proportions. This allows a word like "fire" to be adjacent to "wood" in one map and "job" in another, without forcing "wood" and "job" to be neighbors.

Aspect Maps: This synthetic example demonstrates how two distinct 2D maps (top row) can be reconstructed correctly from a single set of pairwise similarities.

UNI-SNE (Robust SNE)

To solve the crowding problem, the authors propose UNI-SNE. This variant uses two maps: a standard "foreground" map and a "background" map where all objects are forced to be equidistant (a uniform distribution). This background map ensures every pair of points has a baseline, non-zero similarity. In the spring analogy, this acts as a weak, constant repulsive force between distant objects, providing the physical space needed for clusters to separate cleanly in the foreground map.

Experimental Results

Disentangling Meanings

Using the University of South Florida Word Association Data, Aspect Maps successfully separated ambiguous words. For example, the word "field" was modeled across two maps: one clustering it with sports-related terms like "baseball" and "game," and another clustering it with agricultural terms like "farm" and "corn."

MNIST Handwritten Digits

Standard SNE often fails to separate similar digit classes (e.g., 4, 7, and 9). By allocating 20% of the probability mass to a uniform background, UNI-SNE dramatically expanded the map. This cleanly separated the digit clusters and reduced the KL divergence cost function from 2.47 to 1.48.

Semantic Geometry

On the AP Newswire corpus, UNI-SNE naturally organized words into logical clusters. It preserved structural geometry; for instance, the quadrilateral formed by "is," "was," "are," and "were" maintained a specific handedness that modeled both singular/plural and present/past distinctions simultaneously.

Conclusion

By treating visualization as a mixture model and introducing a uniform background distribution, the authors provide a robust framework for mapping complex, high-dimensional data. While the non-convex nature of the cost function requires careful iterative optimization, the resulting visualizations offer significantly higher interpretability and structural fidelity than traditional single-map embeddings.

Summary updated

Abstract

We show how to visualize a set of pairwise similarities between objects by using several different two-dimensional maps, each of which captures different aspects of the similarity structure. When t...
BibTeX
@inproceedings{cook2007visualizing,
  author = {James Cook and Ilya Sutskever and Andriy Mnih and Geoffrey E. Hinton},
  title = {{Visualizing Similarity Data with a Mixture of Maps.}},
  booktitle = {AISTATS},
  year = {2007},
  url = {https://openreview.net/forum?id=_a-SpURmbi},
}
Figure