PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Representation for Clustering via Prototype Scattering and Positive Sampling

Zhizhong Huang, Jie Chen, Junping Zhang, Hongming Shan

arXiv:2111.11821v2cs.CV

TL;DR

Deep clustering must balance the uniformity gained from contrastive negatives against their class-collision risk and the clustering collapse associated with non-contrastive representations. ProPos combines prototype scattering and positive sampling alignment in an end-to-end EM framework, and experiments report significant gains over state-of-the-art methods, especially on large-scale datasets.

  • Problem

    Contrastive deep clustering risks class collision from negative pairs, whereas non-contrastive learning avoids that issue but may produce non-uniform representations and clustering collapse.

  • Method

    ProPos combines prototype scattering loss for between-cluster separation with positive sampling alignment for within-cluster compactness, optimized in an expectation-maximization framework.

  • Results

    ProPos outperforms existing state-of-the-art methods by a significant margin, especially on large-scale datasets.

  • Takeaways & Limitations

    The method combines avoidable class collision, uniform representations, well-separated clusters, and improved within-cluster compactness.

  • Takeaways & Limitations

    Prototype quality depends on sufficient mini-batch samples, increasing GPU-memory requirements when datasets contain many clusters.

Abstract

from arXiv · show

Existing deep clustering methods rely on either contrastive or non-contrastive representation learning for downstream clustering task. Contrastive-based methods thanks to negative pairs learn uniform representations for clustering, in which negative pairs, however, may inevitably lead to the class collision issue and consequently compromise the clustering performance. Non-contrastive-based methods, on the other hand, avoid class collision issue, but the resulting non-uniform representations may cause the collapse of clustering. To enjoy the strengths of both worlds, this paper presents a novel end-to-end deep clustering method with prototype scattering and positive sampling, termed ProPos. Specifically, we first maximize the distance between prototypical representations, named prototype scattering loss, which improves the uniformity of representations. Second, we align one augmented view of instance with the sampled neighbors of another view -- assumed to be truly positive pair in the embedding space -- to improve the within-cluster compactness, termed positive sampling alignment. The strengths of ProPos are avoidable class collision issue, uniform representations, well-separated clusters, and within-cluster compactness. By optimizing ProPos in an end-to-end expectation-maximization framework, extensive experimental results demonstrate that ProPos achieves competing performance on moderate-scale clustering benchmark datasets and establishes new state-of-the-art performance on large-scale datasets. Source code is available at \url{https://github.com/Hzzone/ProPos}.

1 INTRODUCTION

ProPos addresses a tension in deep clustering: contrastive learning provides uniformity but risks class collision, while non-contrastive learning avoids collision but can produce non-uniform representations. It combines prototype scattering and positive sampling alignment in an end-to-end EM framework.

  • Motivation: Contrastive methods use negative pairs for uniform representations, but semantically similar instances may be incorrectly pushed apart as class collisions.The uniformity term separates instances on the unit hypersphere, even when constructed negatives are from the same class.
  • Motivation: Non-contrastive methods avoid negative-pair class collisions but may learn non-uniform representations that collapse downstream clustering.The collapse can worsen when non-contrastive learning is combined with additional clustering losses.
  • ProPos: Prototype scattering loss aligns views of prototypes and maximizes between-cluster distance to encourage uniform representations and well-separated clusters.It treats different prototypes as truly negative pairs while preserving alignment between augmented views of the same prototype.
  • ProPos: Positive sampling alignment matches one instance view with sampled neighbors from another view, improving within-cluster compactness.The neighbors are assumed to be truly positive pairs in the embedding space.
  • Optimization: ProPos is optimized in an expectation-maximization framework, alternating pseudo-label estimation by spherical k-means with loss minimization.The E-step estimates instance pseudo-labels, while the M-step minimizes the proposed losses.
  • Results: Experimental results report that ProPos outperforms existing state-of-the-art methods by a significant margin, especially on large-scale datasets.The method is presented as an end-to-end deep clustering approach combining the strengths of contrastive and non-contrastive learning.

2 RELATED WORK

The related work frames deep clustering around self-supervised representation learning, contrasting contrastive methods that risk class collision with non-contrastive methods that can suffer clustering collapse. ProPos is presented as addressing both drawbacks.

  • Contrastive learning: Contrastive representation learning separates instances using many negative examples, but semantic neighbors can be pushed apart through class collision.Large batches, memory queues, or memory banks may be required to construct negative pairs.
  • Non-contrastive learning: Non-contrastive methods remove the need for negative examples and avoid class collision, but their non-uniform representations can cause downstream clustering collapse.The related work describes these methods as producing inferior deep-clustering results for this reason.
  • Self-supervised learning: Self-supervised learning methods primarily target transferable representations for supervised downstream tasks rather than grouping data into semantic classes.The paper distinguishes this emphasis from the goals of deep clustering.
  • Deep clustering: Deep clustering methods commonly use contrastive representations either as pre-trained features or jointly with clustering optimization.Examples include methods that obtain pseudo-labels from pre-trained SimCLR or combine instance discrimination with clustering.
  • ProPos: ProPos addresses these drawbacks with prototype scattering for between-cluster separation and positive sampling alignment for within-cluster compactness.The paper characterizes the resulting approach as combining avoidable class collision with uniform representations.

3 PRELIMINARY

The preliminary discussion separates contrastive learning into alignment and uniformity components and explains the complementary failure modes of contrastive and non-contrastive objectives. Figure 1 previews ProPos’s two corresponding techniques.

  • Contrastive Learning: Contrastive learning pulls together augmented views of one instance and pushes the instance away from dataset negatives on a unit hypersphere.The temperature controls the concentration level of normalized representations.
  • Contrastive Learning: The contrastive objective can be viewed as instance alignment plus instance uniformity, with uniformity helping prevent representation collapse.Negative examples are made uniformly distributed on the unit hypersphere, but may introduce class collision.
  • Non-Contrastive Learning: Non-contrastive learning matches representations from two augmented views without negative pairs, using online, target, and predictor networks with stop-gradient operations.This avoids class collision while relying on architectural mechanisms to prevent representation collapse.
  • ProPos overview: Figure 1 contrasts prototype scattering, which maximizes between-cluster distance, with positive sampling alignment, which improves within-cluster compactness.The two techniques correspond to separation across clusters and alignment among sampled neighbors.
  • Non-Contrastive Learning: Non-contrastive methods tend to produce non-uniform representations that can destabilize deep clustering through downstream clustering collapse.The preliminary section refers to later experiments for this behavior.

4 METHOD

ProPos combines prototype-level scattering with positive sampling alignment to learn separated, compact clusters. An EM procedure alternates pseudo-label estimation with optimization of these losses.

  • Overview: ProPos advances deep clustering with prototype scattering loss (PSL) and positive sampling alignment (PSA).The method is presented as an end-to-end approach for jointly learning representations and clustering.
  • Prototype Scattering Loss: PSL aligns prototypes across augmented views while uniformly distributing them on a unit hypersphere to maximize inter-cluster distance.Because different prototypes represent different clusters, they provide definite negative pairs for the prototype-level contrastive objective.
  • Prototype Scattering Loss: PSL computes cluster centers from assignment posterior probabilities within each mini-batch and masks empty clusters when K exceeds batch coverage.The cluster centers are computed for online and target-network views, and inaccurate early centers motivate delayed PSL training.
  • Positive Sampling Alignment: PSA samples neighbors around one augmented view in embedding space and aligns them with another view to improve within-cluster compactness without constructed negatives.Neighbors are sampled from a Gaussian perturbation using v = f(x) + σϵ, with reparameterization enabling backpropagation.
  • EM Framework: ProPos optimizes PSL and PSA in an EM framework, using spherical k-means in the E-step and loss minimization in the M-step.The procedure uses target-network features for pseudo-label estimation and updates the target network by momentum averaging.
  • Combined Objective: PSL separates clusters while PSA pulls sampled neighboring examples together, combining complementary objectives for well-separated and compact clusters.The combined losses are intended to provide uniform representations, clustering stability, and improved within-cluster compactness.

5 EXPERIMENTS

Experiments evaluate ProPos on seven benchmark datasets and compare its representation uniformity, cluster balance, neighbor quality, and clustering performance. The reported results show more stable representations, more balanced clusters, semantically preserved sampled neighbors, and strong benchmark performance.

  • Experimental Setup: Experiments cover seven benchmark datasets, including moderate-scale datasets and the large-scale ImageNet-1k benchmark.The study reports backbone choices and training settings for fair comparisons across dataset scales.
  • The Role of PSL: ProPos produces higher and more stable feature standard deviations than BYOL, indicating more uniform ℓ2-normalized representations.The study uses feature standard deviation as its uniformity measure and interprets values closer to 1/√d as more uniform.
  • The Role of PSL: ProPos yields more balanced k-means clusters than BYOL, whose clusters become highly imbalanced as representations become less uniform.The cluster imbalance ratio compares the smallest and largest clusters, with higher values indicating more balanced assignments.
  • The Role of PSL: ProPos achieves higher and more stable NMI than BYOL, while directly applying BYOL suffers clustering collapse from non-uniform representations.The comparison links PSL-based uniformity with better-clustered samples in this CIFAR-10 analysis.
  • The Role of PSA: For σ < 0.005, sampled neighbors largely preserve their original semantic classes, whereas preservation decreases at σ = 0.01.Qualitative visualizations also show sampled neighbors sharing the input class at the 100th training epoch.

5.3 Main Results

ProPos improves clustering across moderate- and large-scale benchmarks, with especially strong results as dataset scale and class count increase. It also outperforms competitors in ImageNet-1k linear evaluation under fair conditions.

  • ProPos achieves significant performance improvements across five moderate-scale benchmark datasets.
  • On ImageNet-Dogs, ProPos improves by almost 20% over previous state-of-the-art work.
  • ProPos demonstrates generalization ability on complex datasets with large numbers of clusters, including Tiny-ImageNet and ImageNet-1k.
  • ProPos outperforms other competitors by a clear margin in ImageNet-1k linear evaluation under fair conditions.

5.4 Ablation Study

Ablations show that PSL is the primary driver of clustering gains, while PSA complements it by improving within-cluster compactness. Their combination produces the best clustering results and remains effective across cluster-count settings.

  • Quantitative ablation study: PSL produces large clustering gains, whereas removing it leaves only marginal improvements over the baseline.
  • Quantitative ablation study: PSA improves stability and clustering performance, especially as the number of semantic classes increases, and complements PSL by pulling neighboring examples together.
  • Quantitative ablation study: The combination of PSL and PSA achieves the best clustering results by maximizing inter-cluster distance and improving within-cluster compactness.
  • PSL analysis: PSL uniformity provides the significant performance gain, while its alignment term mainly stabilizes training when the number of clusters is larger.
  • Effect of predefined number of clusters: For predefined cluster counts K in {5, 10, 20, 30, 40, 50}, ProPos produces large improvements over BYOL with the same K.

5.5 Hyperparameter Analysis

ProPos is robust to several hyperparameter choices, although performance depends on the clustering interval, positive-sampling strength, PSL weight, projection dimension, backbone depth, and augmentations. Its additional k-means cost is reported as limited.

  • Clustering interval: ProPos remains robust when k-means clustering is performed less frequently, with r suggested in to reduce computation cost.
  • Positive-sampling strength: Positive sampling slightly lowers CIFAR-10 performance but improves stability, while increasing CIFAR-20 performance and reducing its standard deviation.
  • PSL weight: The suggested PSL weight λ_psl in [0.01, 0.1] provides superior performance on both CIFAR-10 and CIFAR-20.
  • Architecture choices: ProPos consistently improves over the baseline across projection dimensions and achieves stronger, more stable clustering with deeper ResNet networks.
  • Data augmentation: Removing data augmentations reduces performance for both methods, but ProPos remains more stable and robust to augmentation choices.
  • Computational cost: ProPos does not introduce much additional computational cost despite its k-means clustering procedure.

5.8 Long-tail Dataset

ProPos is evaluated on long-tailed datasets and with memory queues, where avoiding negative examples addresses class collision and additional prototype samples can improve performance. However, excessively large queues may reduce performance.

  • Long-tailed datasets: ProPos is evaluated on long-tailed CIFAR-10 and CIFAR-20 datasets constructed with an imbalance ratio of 0.1.These datasets contain many more samples in head classes than tail classes.
  • Long-tailed datasets: MoCo v2 performs poorly on long-tailed data because negative pairs push head-class samples apart and mix tail-class samples.BYOL and ProPos avoid negative examples and therefore outperform MoCo v2 by a large margin.
  • Long-tailed datasets: Adding PSA and PSL further improves BYOL’s clustering performance on the long-tailed datasets.The passage attributes the additional improvement to ProPos’s positive sampling alignment and prototype scattering loss.
  • Memory queue: Although sufficient per-class samples would increase GPU-memory requirements, ProPos generalizes on Tiny-ImageNet and ImageNet-1k with mini-batch size 256.The reported settings correspond to about 1 sample per class for Tiny-ImageNet and 0.25 sample per class for ImageNet-1k.
  • Memory queue: Prototypes can be updated from both the mini-batch and a memory queue to compute class prototypes more accurately with small batches.The queue stores representations from the momentum-updated encoder.
  • Memory queue: On Tiny-ImageNet, performance improves as more samples are used for prototypes but can drop when the memory queue becomes too large, such as 4,096.The experiment uses Tiny-ImageNet’s 200 classes and repeats each run three times with mean and standard deviation reported.

6 DISCUSSION

The discussion contrasts ProPos with class-level and graph-based alternatives, emphasizing that PSL promotes inter-cluster separation while PSA improves within-cluster compactness without requiring negative examples or graph construction.

  • Relation to CC: PSL contrasts cluster-center representations, whereas CC contrasts cluster probabilities and can lose semantic information useful for representation learning.PSL uses pseudo-labels from k-means and operates directly on cluster-center representations.
  • Relation to CC: PSL encourages cluster uniformity directly, while CC still needs instance-wise contrastive learning that can introduce class collision.In the same BYOL framework, BYOL+CC drops performance and becomes unstable, whereas ProPos significantly improves over BYOL+CC.
  • Relation to GCC and WCL: GCC and WCL select pseudo-positive neighbors from graphs or stored examples, whereas PSA samples neighbors in the embedding space assumed to be truly positive.The graph-based methods incur additional graph-construction cost, while ProPos samples one embedding-space example more cheaply.
  • Relation to GCC and WCL: GCC and WCL can suffer positive class collision because selected pseudo-positive examples may not be truly positive.These methods also retain negative examples for instance-wise contrastive learning, exposing them to negative class collision.
  • Relation to PCL: ProPos avoids class collision by using BYOL without negative examples, whereas PCL relies on instance-wise contrastive learning with negative examples.The comparison identifies negative-example dependence as the distinguishing source of class-collision risk.
  • Relation to PCL: PSL maximizes inter-cluster distance and uniformity, while PSA supplies the within-cluster compactness that ProtoNCE targets.Pure PSL can work for deep clustering, whereas ProtoNCE requires another InfoNCE term to form a uniformly distributed space.
  • Relation to PCL: In the EM formulation, ProPos uses a prototypes-to-prototypes PSL in the M-step and additionally samples positive examples around each instance.The discussion presents these choices as the basis for improved clustering performance and within-cluster compactness.
  • Interpretation of PSL: The alignment term of PSL is an instance-reweighted contrastive loss whose weights retain same-cluster pairs and exclude different-cluster pairs.Its uniformity term maximizes distances between instances in different clusters.

7 CONCLUSION

ProPos combines positive sampling alignment with prototype scattering loss in an end-to-end deep clustering method. The paper reports improved within-cluster compactness, well-separated clusters, and state-of-the-art performance, while identifying newer self-supervised methods as future work.

  • Conclusion: ProPos combines contrastive- and non-contrastive-based strengths through positive sampling alignment and prototype scattering loss.The paper associates these components with within-cluster compactness and well-separated clusters.
  • Conclusion: The authors report that ProPos outperforms state-of-the-art methods by a significant margin.They also note that current state-of-the-art methods benefit largely from self-supervised representation learning.
  • Conclusion: The paper identifies newer trends such as MAE as future directions for improving downstream deep-clustering performance.This is presented as an area deserving further study rather than as an evaluated result of ProPos.

8 EM FRAMEWORK

ProPos derives an EM objective for spherical feature distributions, using spherical k-means in the E-step and loss optimization in the M-step. Prototype scattering is introduced to preserve uniformity while improving cluster separation, and the EM updates yield a nondecreasing likelihood sequence.

  • Distribution and objective: The framework models ℓ2-normalized features with the von Mises-Fisher distribution on a hypersphere.The distribution uses mean direction µ and concentration κ; κ = 0 represents a uniform hyperspherical distribution.
  • Distribution and objective: The EM objective is based on the marginal likelihood of N observations associated with K latent cluster variables and model parameters θ.Because direct log-likelihood optimization is difficult, the derivation introduces an inference distribution q(k) and the ELBO.
  • EM framework: The E-step estimates pseudo-label probabilities with spherical k-means using target-network features, which are treated as more stable and consistent.The M-step then optimizes θ with the E-step assignments fixed.
  • EM framework: With a uniform prior and hard E-step labels, the cluster likelihood uses vMF components with cluster centers µk and temperature τ = 1/κ.The resulting objective minimizes a negative log-likelihood based on pseudo-labels y(n).
  • Prototype scattering loss: Directly optimizing the likelihood improves compactness but can compromise BYOL stability because it lacks a uniformity term.PSL addresses this by applying cluster-level contrastive learning to cluster centers treated as prototypes.
  • Implementation: When the number of clusters exceeds the mini-batch size, losses and logits for empty clusters are set to zero for that iteration.This handles batches that do not cover all clusters.
  • Prototype scattering loss: PSL aligns prototypes across augmented views while maximizing prototypical uniformity and inter-cluster distance.The prototypes come from target and online networks and are empirically estimated within the mini-batch.
  • Convergence: The EM updates satisfy log p(x; θt+1) ≥ ELBO(qt+1, x; θt+1) ≥ ELBO(qt+1, x; θt) = log p(x; θt), guaranteeing convergence.The E-step reaches the current log-likelihood, and the M-step does not decrease the ELBO.

9 ADDITIONAL EXPERIMENTAL RESULTS

Additional experiments visualize ProPos’s representation learning process, outliers, and behavior under underestimated cluster counts, while fair comparisons show clearer improvements on larger datasets.

  • Baseline behavior: Compared to PCL+BYOL, PCL+MoCo clusters more stably and maintains a more uniform representation distribution.The comparison uses NMI and the standard deviation of ℓ2-normalized features on CIFAR-10.
  • Representation visualization: ProPos progressively separates semantic classes during training, whereas randomly initialized features initially mix instances across classes.The t-SNE visualization spans four training epochs on CIFAR-10.
  • Outlier analysis: The CIFAR-10 outlier points produced at the 1000-th epoch are visualized with t-SNE.
  • Fair comparisons: Significant improvements are observed on ImageNet-10 and ImageNet-Dogs, while CIFAR-10 and CIFAR-20 show no clear margin across dataset splits.The fair comparison excludes the test set, uses original image size 224 for the ImageNet datasets, and trains all results with ResNet-34.
  • Underestimated cluster count: With underestimated K = 5 on CIFAR-10, t-SNE visualizations compare k-means pseudo-labels against true semantic classes.The pseudo-label view annotates the corresponding true semantic classes.
Loading 2111.11821v2…