Learning Generative Models of Similarity Matrices

Rómer Rosales, Brendan J. FreyUAI 2003

TL;DR

This paper introduces a probabilistic framework for learning similarity matrices, moving beyond traditional spectral clustering. By modeling noise and learning the similarity scale parameter, their method achieves more robust and accurate clustering, especially on challenging datasets where spectral clustering falters.

What Problem Does This Paper Address?

Spectral clustering (SC) is a popular technique for identifying clusters in data, particularly those with irregular shapes. It relies on an input similarity matrix between all data points. However, SC struggles when clusters are noisy, not well-separated, or when the crucial "scale parameter" (which determines how distances translate to similarities) is not set correctly. Existing SC methods often require manual tuning of this parameter or extensive grid searches, and lack a clear understanding of their applicability. This paper aims to address these limitations by developing a generative probabilistic model that can learn the similarity matrix and its parameters, offering a more principled approach to clustering.

Methods

The authors propose two families of probabilistic models:

  • Latent Feature Representation Models: These models assume each data point has an unobserved, low-dimensional "latent feature" vector. The similarity matrix is then modeled as a function of these latent features. They show that greedy inference in this model, under specific choices of conditional distributions, is equivalent to standard spectral clustering. This provides a probabilistic interpretation for SC and opens avenues for approximate inference techniques.
  • Latent Graph Representation Models: This approach models the transitive similarity relationships as a latent graph. This allows for a more generalized view of clustering, enabling the estimation of class-dependent similarity scale parameters and accounting for noisy or overlapping clusters. A key contribution here is the development of an approximate inference algorithm for finding the cluster assignments and parameters, which involves finding minimum spanning trees.

Datasets

The paper evaluates their method on several synthetic datasets, illustrated in Figures 2 and 4. These datasets are designed to highlight the weaknesses of spectral clustering, particularly in cases with varying cluster scales, noise, and overlapping clusters. No new benchmarks are introduced; rather, existing challenging scenarios are used to demonstrate the superiority of their approach.

Key Insights and Ideas

  • Probabilistic Foundation for Spectral Clustering: By framing spectral clustering within a generative probabilistic model, the authors provide a theoretical justification and a path towards more robust algorithms.
  • Learning the Scale Parameter: A significant insight is that the scale parameter, crucial for SC, can be learned from data within their probabilistic framework, eliminating the need for manual tuning.
  • Handling Noise and Overlap: The latent graph representation model explicitly accounts for noise and overlapping clusters, which are known weaknesses of traditional SC.
  • Minimum Spanning Tree Equivalence: The surprising result that inferring cluster assignments in their latent graph model can be reduced to finding minimum spanning trees offers an efficient inference mechanism.
  • Class-Dependent Similarity Measures: The ability to infer different similarity measures for different clusters is a key advantage, allowing for more accurate clustering in heterogeneous data.

Key Results

The paper demonstrates through experimental results (Figures 4 and 5) that their proposed method significantly outperforms spectral clustering (Figure 2) on challenging datasets. Specifically, their method successfully identifies clusters in scenarios where SC fails, such as:

  • Clusters with different intrinsic similarity scales.
  • Noisy and overlapping clusters.
  • Data with non-uniform point density.

While quantitative metrics like accuracy are not explicitly detailed with numbers, the visual results strongly suggest superior performance. The authors also note that their algorithm's complexity scales well with dimensionality and is efficient for clustering.

Limitations and Future Work

  • Computational Complexity: While the proposed inference is approximate, exact inference in their models can still be computationally intractable, especially for large datasets.
  • Parameter Choice in Neighborhood Priors: For certain neighborhood prior choices (e.g., fixed K neighbors), finding the optimal parameter K can still be challenging.
  • Future Work: The authors suggest extensions to semi-supervised clustering by incorporating known labels. They also envision using approximate inference techniques (like variational inference) for more complex models and exploring alternative likelihood functions. The potential for generalizing spectral clustering by replacing specific equations with more problem-dependent choices is also highlighted.

Summary updated

BibTeX
@inproceedings{rosales2003learning,
  author = {Rómer Rosales and Brendan J. Frey},
  title = {{Learning Generative Models of Similarity Matrices}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2003},
}

Loading related content...

Figure