Learning the Structure of Similarity

Joshua B. TenenbaumNeurIPS 1995 · OpenReview

Abstract: This paper introduces a statistically rigorous Expectation-Maximization (EM) framework for the Additive Clustering (ADCLUS) model, which represents object similarity as a weighted sum of shared features. By treating cluster memberships as hidden variables rather than fixed parameters, the new algorithm outperforms previous heuristic methods, discovering cleaner and more psychologically plausible structures in complex datasets.

The Challenge of Modeling Similarity

How do we represent the "mental map" of similarity? In cognitive science, there are two traditional ways to model how people judge the similarity between objects:

  1. Spatial Models: Objects are points in a multi-dimensional space (like a color space), and similarity is the inverse of distance.
  2. Set-Theoretic Models: Objects are defined by sets of features, and similarity is a measure of shared versus distinctive traits.

The Additive Clustering (ADCLUS) model is a powerful set-theoretic approach because it allows for "overlapping" clusters. For example, the number "9" might belong to the cluster of "odd numbers," "multiples of three," and "large single digits" simultaneously.

However, fitting the ADCLUS model to data is a notorious combinatorial optimization nightmare. Previous attempts (like the original 1979 ADCLUS and 1980 MAPCLUS) relied on ad-hoc heuristics that often got stuck in local optima or produced messy, uninterpretable results. This paper seeks to replace those "black box" heuristics with a principled probabilistic algorithm.

A Probabilistic Generative Model

The author reformulates ADCLUS as a generative model where similarities are generated by the interaction of independent underlying causes (features).

  • Probabilistic Formulation: The model treats cluster weights as parameters and the unknown cluster memberships as hidden variables. It assumes the observed similarity is a Gaussian distribution centered on the weighted sum of shared features.
  • The EM Algorithm:
    • E-Step: Instead of picking the single "best" cluster configuration, the algorithm calculates the expected value of cluster memberships across all possible configurations. Because the number of possible configurations is astronomical, the author uses Gibbs sampling (a Monte Carlo method) to approximate this expectation.
  • M-Step: Given the expectations from the E-step, finding the optimal weights becomes a straightforward (constrained) linear least-squares problem.
  • Simulated Annealing: To avoid getting stuck in local maxima and to speed up the Gibbs sampler, the algorithm "anneals" the variance. It starts with a high variance (searching broadly) and gradually cools down to the target model variance.

Key Insights and Structural Versatility

A major conceptual shift in this paper is treating similarity as Multiple-Cause Learning. The paper argues that similarity isn't a single dimension but the result of many independent "causes," aligning ADCLUS with modern unsupervised learning techniques used in neural computation.

Furthermore, by utilizing "soft" assignments—treating cluster membership as a probability during the learning process rather than a hard 0 or 1—the algorithm explores the landscape of possible structures much more effectively than previous "greedy" search methods.

This leads to remarkable structural versatility. ADCLUS isn't just for overlapping sets; depending on the data, the same algorithm can naturally recover hierarchical structures (like phoneme families) or dimensional structures (like numerical magnitude) without needing to be told which one to look for.

Datasets and Key Results

The algorithm was evaluated on three distinct types of data: artificial data (to verify ground-truth recovery), integer similarity (0-9), and consonant phoneme confusability.

Superior Fit and Interpretability (Integer Data) On the classic integer similarity data, the new algorithm found a solution with only 8 clusters that accounted for 90.9% of the variance. For comparison, the original ADCLUS algorithm required 10 clusters to reach only 83.1% variance. The clusters found for integers were highly intuitive, cleanly identifying concepts like "powers of two," "multiples of three," and "small numbers."

Clusters discovered for integer similarity (0-9)

Recovering Missing Features (Phoneme Data) In the Miller & Nicely phoneme dataset, the algorithm successfully identified a distinct cluster for "nasals" (/m/, /n/). Previous state-of-the-art methods (like MAPCLUS) famously failed to recover this cluster, which is considered a cornerstone of phonological theory.

Clusters discovered for consonant phonemes

Robustness In artificial tests, the algorithm successfully recovered the correct structure even when the number of assumed clusters was set higher than the true number, effectively "zeroing out" the extra clusters.

Limitations and Future Work

While highly effective, the approach has limitations:

  • Computational Complexity: Gibbs sampling is computationally expensive. As the number of stimuli and clusters grows, the algorithm may become slow.
  • Mean-Field Approximations: To address speed, future versions could use "mean-field" approximations—a faster way to estimate the E-step without full Monte Carlo sampling.
  • Priors: The current model uses uniform priors. Incorporating "significant prior structure" (biasing the model toward certain types of clusters) could further improve results in specific domains.

Summary updated

Abstract

The additive clustering (ADCL US) model (Shepard & Arabie, 1979) treats the similarity of two stimuli as a weighted additive measure of their common features. Inspired by recent work in unsupervised learning with multiple cause models, we propose anew, statistically well-motivated algorithm for discovering the structure of natural stimulus classes using the ADCLUS model, which promises substan(cid:173) tial gains in conceptual simplicity, practical efficiency, and solution quality over earlier efforts. We also present preliminary results with artificial data and two classic similarity data sets.
BibTeX
@inproceedings{tenenbaum1995learning,
  author = {Joshua B. Tenenbaum},
  title = {{Learning the Structure of Similarity}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1995},
  url = {https://openreview.net/forum?id=Bk-43d-u-H},
}
Figure