Abstract
This paper introduces X-Supervised Discriminative Clustering (XSDC), a unified framework that bridges the gap between unsupervised clustering and supervised classification. By integrating deep representation learning with a discriminative clustering objective, XSDC provides a principled way to leverage any amount of labeled data—from zero to a full training set—to improve feature learning and data partitioning. The method utilizes a novel convex relaxation for cluster assignment and a "forward prediction" objective, outperforming standard supervised baselines when labeled data is scarce and providing a flexible way to incorporate domain-specific constraints.
Introduction
In machine learning, clustering (unsupervised) and classification (supervised) are often treated as distinct paradigms. However, real-world scenarios frequently fall between these extremes: datasets may have massive amounts of unlabeled data with only a handful of labels, or perhaps only "must-link" constraints (knowing two items belong together without knowing their category). Existing semi-supervised methods often combine these objectives in an ad-hoc manner, leading to optimization challenges due to the fundamentally different structures of clustering (e.g., $k$-means) and deep learning objectives.
XSDC addresses this by providing a single, principled objective function that naturally reduces to clustering when labels are absent and classification when they are present. This allows for a seamless transition across any ratio of labeled to unlabeled data.
Methodology: The XSDC Framework
XSDC extends DIFFRAC, a discriminative clustering method, by replacing linear mappings with a deep neural network ($\phi_V$). The core of the approach relies on representing cluster assignments through an equivalence matrix.
Key Technical Innovations
- Forward Prediction Objective: Unlike the "reverse prediction" used in $k$-means (reconstructing features from cluster centers), XSDC predicts cluster assignments from features. This objective is mathematically "smoother" (Lipschitz continuous), making it significantly more stable for gradient descent optimization in deep networks.
- Matrix Balancing via Entropic Regularization: Assigning points to clusters is typically NP-hard. XSDC employs a convex relaxation using entropic regularization, transforming the assignment step into a "matrix balancing" problem solvable via efficient Sinkhorn-style algorithms. This allows the model to enforce cluster size constraints and prevent degenerate solutions where all data is assigned to a single cluster.
- Unified Optimization: The model uses a stochastic gradient algorithm (ULR-SGO) that alternates between updating cluster assignments (the "labels") and the network parameters.
Experimental Evaluation
The method was evaluated on four standard benchmarks: MNIST, CIFAR-10, Gisette, and MAGIC. The authors specifically tested these datasets by varying the number of labeled samples from 0 to 500 to observe how the model interpolates between unsupervised and supervised regimes.
Key Results
- Performance with Scarce Labels: On MNIST with only 50 labeled samples, XSDC achieved approximately 90% accuracy, significantly outperforming a standard supervised baseline which reached only 80%.
- Superiority over Semi-Supervised k-means: XSDC consistently outperformed semi-supervised variants of $k$-means, particularly on complex image data like CIFAR-10.
- Unlabeled Data as a Regularizer: Results suggest that including unlabeled data in the clustering objective acts as a powerful regularizer, helping the network learn a geometric structure that purely supervised models might miss.
Conclusion and Future Work
XSDC provides a robust, principled framework for discriminative clustering that scales from zero to full supervision. While highly effective, the current implementation requires relatively large batch sizes for the matrix balancing step to be effective. Future work may involve developing "streaming" versions of the algorithm for larger-scale applications and extending the framework to handle discrete structures like ordinal data. Additionally, tuning hyperparameters in purely unsupervised settings remains an open challenge for the field.
Summary updated