Probabilistic Clustering using Maximal Matrix Norm Couplings

David Qiu, Anuran Makur, Lizhong Zheng

Abstract

Traditional clustering methods often rely on Euclidean distances in vector spaces, which can be ill-suited for data naturally represented as co-occurrence matrices. This paper introduces a local information-theoretic framework for probabilistic clustering by maximizing the "coupling" between data items and clusters. By approximating mutual information using matrix norms—specifically the Frobenius and Nuclear norms—the authors transform a difficult optimization problem into a manageable one. This approach allows for the direct learning of soft-clustering transition kernels that outperform traditional spectral and embedding-based methods in both accuracy and parameter efficiency.

Introduction

Clustering is a cornerstone of unsupervised learning, yet popular algorithms like $k$-means are fundamentally metric-based. In many real-world scenarios, such as users interacting with items or words appearing in documents, data is better represented as a joint probability distribution or a co-occurrence matrix.

The goal of probabilistic clustering is to maximize the mutual information between data items ($X$) and assigned clusters ($Z$). However, direct maximization of mutual information is computationally grueling and often NP-hard. Most existing approaches take a two-step detour: first learning a low-dimensional embedding and then applying a clustering algorithm. This paper proposes a single optimization framework to learn the clustering transition kernel directly.

Methodology

The Divergence Transition Matrix (DTM)

The authors introduce the Divergence Transition Matrix (DTM), a normalized version of the co-occurrence matrix that captures the "divergence" of the data from a neutral, independent state. This matrix serves as the foundation for the proposed norm-based approximations.

Frobenius Norm Formulation

Using a Taylor expansion, the authors prove that maximizing mutual information is locally equivalent to maximizing the Frobenius norm of the DTM. This reformulation results in a non-convex quadratic program (QP). To solve this, the authors propose a heuristic Gradient Ascent algorithm designed to find high-quality local optima.

Algorithm 1: Gradient Ascent for the Frobenius Norm Formulation

Nuclear Norm Relaxation

To further simplify the problem and remove the need for prior knowledge of cluster distributions, the authors propose a relaxation using the Nuclear norm (the sum of singular values). This version is solved using an Alternating Maximization algorithm, which is particularly effective for large-scale datasets.

Theoretical Insights

The authors highlight a deep link between their DTM and the symmetric normalized graph Laplacians used in spectral graph theory. This provides a theoretical "sanity check," grounding the information-theoretic approach in established linear algebra. Furthermore, the formulation allows for the integration of prior knowledge about cluster sizes, which can significantly stabilize the learning process.

The behavior of the squared Frobenius norm objective as a function of the parameter s.

Experimental Results

The approach was validated across three distinct domains:

  • Word Embeddings (MSR Sentence Completion): The DTM-based model achieved 53.94% accuracy, outperforming the popular Skip-gram model (48.0%) and remaining competitive with complex Recurrent Neural Network Language Models (55.4%).
  • Document Clustering (Reuters21578): On this benchmark, the algorithm achieved an accuracy of approximately 70% for $k=10$ clusters, significantly outperforming previous state-of-the-art results which hovered around 44%.
  • Qualitative Analysis (MovieLens 100K): The model successfully grouped movies into intuitive clusters based on genre and popularity, such as grouping high-rated classics like "The Godfather" and "Pulp Fiction."

Conclusion and Future Work

By learning the transition kernel ($P_{Z|Y}$) directly, this framework avoids the information loss inherent in intermediate embedding steps. The model is also highly parameter-efficient, as its complexity scales with the number of clusters rather than the number of features.

While the current algorithms are heuristics for an NP-hard problem, they demonstrate superior performance in practice. Future work includes addressing noise sensitivity in datasets with missing observations and extending the framework to co-clustering, where both items and features are clustered simultaneously within the same matrix norm framework.

Summary updated

BibTeX
@inproceedings{qiu2018probabilistic,
  author = {David Qiu and Anuran Makur and Lizhong Zheng},
  title = {{Probabilistic Clustering using Maximal Matrix Norm Couplings}},
  booktitle = {Allerton},
  year = {2018},
  url = {https://openreview.net/forum?id=yXceCrl84R},
}
Figure