Source-linked AI summary
Deep clustering: On the link between discriminative models and K-means
Mohammed Jabi, Marco Pedersoli, Amar Mitiche, Ismail Ben Ayed
TL;DR
Recent discriminative deep-clustering objectives based on mutual information or KL divergence can seem unrelated to K-means, despite their prevalence and reported performance. This paper connects these formulations to K-means, proving an equivalence for logistic-regression posteriors under L2 regularization and approximate ADM. It also reports competitive results for a resulting soft, regularized deep K-means algorithm on image-clustering benchmarks.
Problem
Several recent MI- and KL-based discriminative deep-clustering models may appear unrelated to K-means, although discriminative models are commonly viewed as more flexible and better-performing than generative approaches.
Source: §1 · p. 2Method
The paper analyzes the objectives and proves that maximizing L2-regularized mutual information with logistic-regression posteriors via approximate ADM is equivalent to a soft, regularized K-means loss.
Source: §1 · p. 2Results
The paper connects several prevalent discriminative models to K-means, and its soft, regularized deep K-means algorithm achieved competitive results on several image-clustering benchmarks.
Source: §6 · p. 9Takeaways & Limitations
The analysis shows that several discriminative formulations can be understood as K-means-related under mild conditions and commonly used posterior models and regularization.
Source: §6 · p. 9The authors leave analysis of MI-ADM optimality and convergence under alternative distance measures and penalty methods for future work.
Source: §6 · p. 9
Abstract
from arXiv · showhide
In the context of recent deep clustering studies, discriminative models dominate the literature and report the most competitive performances. These models learn a deep discriminative neural network classifier in which the labels are latent. Typically, they use multinomial logistic regression posteriors and parameter regularization, as is very common in supervised learning. It is generally acknowledged that discriminative objective functions (e.g., those based on the mutual information or the KL divergence) are more flexible than generative approaches (e.g., K-means) in the sense that they make fewer assumptions about the data distributions and, typically, yield much better unsupervised deep learning results. On the surface, several recent discriminative models may seem unrelated to K-means. This study shows that these models are, in fact, equivalent to K-means under mild conditions and common posterior models and parameter regularization. We prove that, for the commonly used logistic regression posteriors, maximizing the $L_2$ regularized mutual information via an approximate alternating direction method (ADM) is equivalent to a soft and regularized K-means loss. Our theoretical analysis not only connects directly several recent state-of-the-art discriminative models to K-means, but also leads to a new soft and regularized deep K-means algorithm, which yields competitive performance on several image clustering benchmarks.
1 INTRODUCTION
Deep clustering seeks useful groupings of unlabeled, often high-dimensional data, and recent work commonly learns representations and latent assignments jointly. Although discriminative objectives are often viewed as more flexible and better-performing than generative approaches such as K-means, this paper connects several discriminative formulations to K-means.
1 INTRODUCTION
- Recent deep-clustering studies jointly learn feature embeddings and latent cluster assignments, often combining a clustering loss with reconstruction-based regularization.The paper notes that discriminative objectives dominate this literature and report the most competitive performances.Source: §1 · p. 1
- Discriminative approaches are commonly considered more flexible and better-performing, yet recent MI- and KL-based models may appear unrelated to K-means.The paper cites a 14% accuracy difference between DEPICT and the deep K-means model in.Source: §1 · p. 2
- The study proves that maximizing L2-regularized mutual information with logistic-regression posteriors via approximate ADM is equivalent to a soft, regularized K-means loss.The result is stated for commonly used logistic-regression posteriors and parameter regularization.Source: §1 · p. 2
- It links KL-based models such as DEPICT to mutual-information objectives used in other recent deep-clustering work,.With a balancing term, optimizing the KL objective can be viewed as an approximate ADM solution for optimizing mutual information.Source: §1 · p. 2
- The analysis motivates a soft, regularized deep K-means algorithm with competitive performance on several benchmarks.The paper describes its performance as approximately matching state-of-the-art discriminative algorithms.Source: §1 · p. 2
2 DEEP DISCRIMINATIVE CLUSTERING MODELS
This section describes deep discriminative clustering objectives and connects KL-based auxiliary-target models to mutual-information maximization. It then explains how the two alternating updates approximate that optimization.
2 DEEP DISCRIMINATIVE CLUSTERING MODELS
- Deep clustering jointly learns a lower-dimensional feature embedding and latent cluster assignments, often adding reconstruction loss as data-dependent regularization against overfitting.The section focuses on clustering losses and defers fuller discussion of reconstruction loss to Section 5.Source: §2 · p. 2
2.1 Mutual information
- Mutual-information clustering combines low conditional entropy, which favors confident point assignments, with marginal-label entropy, which biases assignments toward balanced partitions.Using conditional entropy alone in the unsupervised setting can yield degenerate solutions with removed decision boundaries.Source: §2.1 · pp. 2–3
2.2 The KL divergence and auxiliary targets
- KL-based models introduce auxiliary probability targets and alternate target estimation with classifier-parameter learning; the latter becomes cross-entropy training with fixed targets as labels.The target-estimation step uses a closed-form solution, and the alternating procedure adds O(NK) target-update work, described as marginal relative to SGD training.Source: §2.2 · p. 3
- The paper views DEPICT's alternating steps as an approximate ADM decomposition of mutual-information maximization using auxiliary targets constrained to match the posteriors.Replacing the targets with the posteriors when Q=P recovers the mutual-information objective.Source: §2.2 · p. 3
- The resulting MI-ADM objective approximates DEPICT: its additional target-entropy term favors peaked assignments and reportedly has almost no effect on performance.The first two terms correspond to DEPICT for γ = 1/2, while the added entropy term favors simplex-vertex targets.Source: §2.2 · p. 4
3 DEEP K-MEANS
The section derives SR-K-means from regularized mutual-information optimization and describes its soft assignments and alternating updates.
3 DEEP K-MEANS
- Under balanced partitions and multiclass logistic regression posteriors, ADM maximization of regularized mutual information is equivalent to minimizing a regularized soft K-means loss.With optimal biases substituted, the KL term vanishes and the objective becomes regularized soft K-means.Source: §3 · pp. 4–5
- The soft K-means objective relaxes binary assignments to simplex-valued assignments, while a negative-entropy term favors assignment softness.At hard binary assignments, the objective becomes the hard K-means loss.Source: §3 · pp. 4–5
- Assuming an approximately uniform empirical label distribution, the derivation rewrites the objective using a KL term that vanishes at the optimal biases.The negative entropy of the label marginals favors balanced partitions, with its global minimum at a uniform clustering.Source: §3 · p. 5
- SR-K-means alternates over assignments, soft prototypes, and network parameters, with prototype and assignment updates corresponding to soft versions of standard K-means updates.Unlike DEPICT and MI-ADM, its prototype updates are closed-form rather than performed through network training.Source: §3 · p. 5
- The balancing term disappears from SR-K-means because standard K-means has an implicit bias toward balanced partitions.Source: §3 · p. 5
4 PROPERTIES OF ADM OPTIMIZATION FOR THE MUTUAL INFORMATION
The section establishes that ADM optimization does not decrease mutual information, relates its bound interpretation to SR-K-means, and discusses KL and quadratic penalties.
4.1 Bound-optimization interpretation
- Mutual information is non-decreasing across iterations of the two-step mixed-variable ADM optimization.Source: §4.1 · p. 6
- SR-K-means is also a mutual-information bound optimizer, using a prototype-based auxiliary function distinct from the one used by discriminative ADM.Its two-step process updates prototypes and assignments.Source: §4.1 · p. 6
4.2 Other optimization alternatives and the link between KL and quadratic penalties for simplex variables
- For simplex variables, KL penalties upper-bound quadratic penalties, and their entropy barrier avoids extra constraint projections and dual iterations.The authors note these computational advantages matter more for large datasets.Source: §4.2 · p. 7
5 EXPERIMENTS
The experiments evaluate MI-ADM and soft regularized deep K-means against related clustering methods, then compare MI-ADM with direct mutual-information maximization. MI-ADM and SR-K-means can yield comparable results, while MI-ADM outperforms direct maximization on FRGC and CMU-PIE.
5.1 Reconstruction loss and implementation details
- The experiments use a convolutional denoising autoencoder and add reconstruction loss to MI-ADM and SR-K-means objectives.The network is initialized using the autoencoder, and soft K-means supplies initial targets.Source: §5.1 · p. 7
5.2.1 Data sets
- The experiments compare MI-ADM and SR-K-means on two handwriting datasets and three face datasets.The datasets are USPS, MNIST, YouTube-Face, CMU-PIE, and FRGC.Source: §5.2.1 · p. 8
5.2.3 Evaluation of clustering algorithms
- MI-ADM and SR-K-means may yield comparable results even on unbalanced data, while SR-K-means differs substantially from DCN, which uses a hard K-means loss.The reported performance difference between regularized soft K-means and DCN is 11%.Source: §5.2.3 · p. 8
5.2.4 Direct maximization of the mutual information
- MI-ADM and MI-D perform practically the same on most datasets, but MI-ADM outperforms MI-D on FRGC and CMU-PIE in ACC and NMI.The authors caution that these results do not establish MI-ADM as a generally better optimizer.Source: §5.2.4 · p. 8
- MI-D directly maximizes mutual information using SGD, with a reconstruction term added when learning network parameters.The authors note that the results do not establish a generally better optimizer because neither method provides optimality guarantees for these non-convex deep-network problems.Source: §5.2.4 · p. 8
- On FRGC, Fig. 1 plots mutual information across iterations for MI-ADM and MI-D; the reported MI does not increase during either optimization.The authors report the same MI-ADM evolution pattern on the remaining datasets.Source: §5.2.4 · p. 8, Figure 1 · p. 8
6 CONCLUSION
The paper connects prevalent discriminative deep-clustering models to K-means under mild conditions and derives a soft, regularized deep K-means algorithm. It reports competitive results on image-clustering benchmarks and identifies alternative objectives and convergence analyses for future work.
6 CONCLUSION
- For standard logistic-regression posteriors, maximizing L2-regularized mutual information via ADM is equivalent to a soft, regularized K-means loss.The analysis connects several recent discriminative formulations to K-means and motivates a deep soft regularized K-means algorithm with competitive results on image-clustering benchmarks.Source: §6 · p. 9
- For manifold-structured, high-dimensional inputs, the authors suggest investigating K-modes or normalized-cut objectives in place of K-means components.They also identify links between mutual information and those objectives’ loss functions as a topic for future work.Source: §6 · p. 9
- The optimality and convergence of MI-ADM with alternative distance measures and penalty methods remain topics for future analysis.The conclusion names the Bhattacharyya family and generalized quadratic penalties as examples.Source: §6 · p. 9
APPENDIX A
The appendix approximation assumes an approximately uniform empirical label distribution.
APPENDIX A
- The approximation assumes the empirical label distribution is approximately uniform.The passage expresses this condition as q̂_k = 1, but does not provide the remainder of the expression.Source: Appendix A · p. 9