Giving Over-Clustering Somewhere to Go: Two-Level Repulsive Mixtures with Collapsed Gibbs Sampling

Bayesian mixture models are good at estimating the shape of a data distribution, but they are bad at answering the question people usually care about: how many groups are there? A Dirichlet process mixture is a clustering model that lets the number of clusters grow with the data. Even when the data come from a single normal distribution, it splits them into many small clusters, and the probability of the correct answer goes to zero as data accumulate (Miller and Harrison). A worse failure appears when cluster shapes are even slightly non-Gaussian. Any mixture, finite or infinite, keeps adding components, because extra Gaussians really do fit a skewed or heavy-tailed cluster better (Cai, Campbell and Broderick). Repulsive priors, which penalize cluster centers that sit too close together, restore parsimony when the component shapes are correct (Xie and Xu; Petralia et al.). Under misspecification, though, they face a forced choice: either give up density fit or keep splitting.

We propose to stop fighting the extra components and give them a designated place instead. The model is a two-level tree. Top-level nodes are the clusters, and their centers repel one another. Each top-level node owns an unbounded set of child components that are pulled toward their parent and are free to multiply, so they can patch skewness and tails. Children absorb the density-fitting pressure, which leaves the count of top-level nodes free to be consistent. Because the children are conjugate given their parent, their parameters can be integrated out analytically. The result is a collapsed Gibbs sampler: a Markov chain that samples only the discrete assignments with the continuous parameters marginalized. The repulsion touches only the few top-level centers, so sampling stays cheap.

Core Claim

The file identifies a gap it cannot fill: no current mechanism separates splitting for a real sub-population from splitting to correct the density shape. We claim that a tree constraint with asymmetric priors across levels supplies that mechanism. Siblings at the top level repel, and children within a parent attract. With that structure, the posterior number of top-level nodes can concentrate on the true number of clusters even when component shapes are misspecified. Flat repulsive mixtures, plain Dirichlet process mixtures, and post-hoc merging should all degrade as the sample size grows in that regime.

This differs from the closest work in specific ways. Xie and Xu combine repulsion with a blocked-collapsed sampler on a flat mixture, and they name nested extensions as open. Their model still has to split a skewed cluster or distort its fit. Hierarchical topic models with the nested Chinese restaurant process and GraphLDA use collapsed Gibbs samplers over trees and directed acyclic graphs. They branch with unpenalized processes at every level, so the over-partitioning compounds instead of being contained. In our model the tree is not a discovered taxonomy. It is a device that assigns different jobs to different levels.

Model and Sampler

Let $k = 1, \dots, K$ index top-level clusters with centers $\mu_k$. The centers share a repulsive joint prior $h_K(\mu_1, \dots, \mu_K)$ of the product-of-distances form in Xie and Xu, with repulsion scale $\tau$. Each cluster $k$ carries its own Dirichlet process over children $j$. Each child has a mean $m_{kj}$ and a within-child covariance $\Sigma_w$. An observation $x_i$ assigned to parent $c_i$ and child $z_i$ is generated as

$$ m_{kj} \sim \mathcal{N}(\mu_k, \Sigma_b), \qquad x_i \mid c_i = k, z_i = j \sim \mathcal{N}(m_{kj}, \Sigma_w), $$

where $\Sigma_b$ controls how far children may drift from their parent. The ratio of $\tau$ to the scale of $\Sigma_b$ is the model's stated resolution: groups closer than this are treated as one cluster with a complicated shape. We think making this resolution explicit is more honest than leaving it implicit in a concentration parameter. We will give $\Sigma_b$ a hyperprior with bounded support, so children cannot drift far enough to impersonate separate clusters.

Given $\mu_k$, each child mean is Normal–Normal conjugate and can be integrated out. The data in child $(k,j)$, with count $n_{kj}$ and mean $\bar x_{kj}$, then have a closed-form Gaussian marginal. The sampler has three moves. The first reassigns each point to an existing or new child under any parent, using standard collapsed predictive probabilities. The second is a blocked move that transfers an entire child, meaning all of its points, to another parent or to a new parent. The acceptance ratio of that move includes the repulsion term. The third updates the small set of top-level centers $\mu_{1:K}$ by Metropolis–Hastings on

$$ p(\mu_{1:K} \mid \text{assignments}, X) \propto h_K(\mu_{1:K}) \prod_{k} \mathcal{N}(\mu_k; \mu_0, \Sigma_0) \prod_{j} \mathcal{N}\big(\bar x_{kj}; \mu_k, \Sigma_b + \Sigma_w / n_{kj}\big), $$

where $\mu_0$ and $\Sigma_0$ are the base prior's mean and covariance. The partial collapse is where the conjugacy obstacle in the file's Gap 2 is defused. Repulsion couples only $K$ low-dimensional centers, and every high-cardinality quantity stays marginalized. The blocked child-transfer move matters for a second reason. Matza and Bistritz document that spurious small clusters attract noise and resist pruning, and moving whole children between parents is designed to break that trap.

On theory, we will try to adapt the shrinkage argument of Xie and Xu to a kernel that is itself a nonparametric mixture centered at $\mu_k$. The target statement is that the posterior on $K$ concentrates at the true number of clusters $K_0$ when each true cluster lies within the support of one parent's child-mixture and true clusters are separated beyond the resolution. We present this as a conjecture to prove, not a result.

Baselines

The naive reference is a standard Dirichlet process Gaussian mixture fitted by collapsed Gibbs sampling. On Miller and Harrison's single-normal example, its posterior on cluster count centers around 8 to 10 at n = 2000. On the 10-dimensional simulation of Xie and Xu, it estimated 23 clusters where the truth was 3. Beating it on well-specified data is necessary but says little.

The strongest existing competitor is the flat repulsive Gaussian mixture of Xie and Xu. It identified exactly three clusters with high posterior probability on their 10-dimensional simulation, and it reached that answer within 100 sampler iterations, against over 500 for reversible-jump samplers. On Old Faithful it isolated an outlier group as a fourth component, whereas the repulsive models based on determinantal point processes, whose repulsion comes from a determinant kernel over cluster centers, merged those outliers into larger clusters. The file gives no numeric log-predictive value for that benchmark. We will also report the repulsive prior of Petralia et al., which reports misclassification of 0.00 against 0.09 for the non-repulsive model in scenario IIIb.

All methods get the same data and the same number of sampler iterations. Each gets an equal grid-search budget over its resolution-setting hyperparameters: concentration for the Dirichlet process, $\tau$ for the repulsive models, and $\tau$ together with the $\Sigma_b$ hyperprior for ours. Every method is tuned on a validation configuration separate from the reported one. Beating the flat repulsive mixture means three things on misspecified data. It needs to post a higher posterior probability of $K_0$ that rises with n, where the baseline's probability flat-lines or falls. It needs to reach an equal or better held-out log predictive density. And it needs to match the baseline on well-specified data.

Three ablations isolate the ingredients. The first keeps the two-level tree but removes top-level repulsion, which is essentially a nested Dirichlet process. It tests whether the tree alone contains over-partitioning, and we expect it to fragment at the top level as Miller and Harrison predict. The second keeps repulsion but fixes each parent to a single child, which recovers the flat repulsive mixture. The third keeps the model but samples child means explicitly instead of collapsing them, which measures what collapsing buys in mixing.

Why not just…?

Why not just fit a Dirichlet process mixture and merge components afterward? This is the most serious threat, especially with a merge rule such as "merge two Gaussians whose union is unimodal." Some evidence counts against it. Petralia et al. report that fixed distance thresholds do not adapt across density scales. Matza and Bistritz show that spurious clusters absorb noise during sampling, which can make them look non-mergeable. But neither result rules out a good merge rule on misspecified data. We will therefore run two merge rules on every posterior sample of the naive baseline: a distance threshold and a unimodality test. If merging matches our model on the probability of $K_0$ and on adjusted Rand index across the n-scaling sweep, then the tree is not earning its complexity, and we will say so. The advantage we expect is posterior uncertainty over K that remains calibrated, which merging after the fact cannot provide.

Why not just put a hyperprior on the concentration parameter, or use a finite mixture with a prior on K? Lawless et al. show that Pitman–Yor mixtures stay inconsistent with a prior on precision when the discount is fixed. Alamichel et al. synthesize inconsistency across nonparametric priors. We found no result on Lacuna for the Dirichlet process with a concentration hyperprior, so it enters as a baseline and not as a dismissed alternative. The decisive point is Cai, Campbell and Broderick: under misspecification, even correct priors on K fail, because extra components raise the likelihood. No prior on a flat count can fix that. The misspecified sweep will show whether this alternative breaks where theory says it should.

Why not just use a more flexible component family, such as skew or heavy-tailed densities? This works when the analyst guesses the right family, and we will include a skew-t mixture baseline. But the child-mixture is nonparametric and handles shapes no parametric family anticipates, such as curved or internally lumpy clusters. We will include such shapes, where the parametric fix should split and ours should not.

Why not use determinantal point processes for repulsion? Xie and Xu already found that these merged outliers on Old Faithful, and their determinant couples all centers in a way that resists collapsed updates. Our repulsion acts on only K centers, so there is no reason to pay that cost.

Proposed Experiments

The first stage reproduces the known regimes with every method. These are the single-normal example of Miller and Harrison, the 10-dimensional three-cluster simulation and Old Faithful from Xie and Xu, and the synthetic scenarios and Iris data from Petralia et al.. On these well-specified cases our model should roughly match the flat repulsive mixture. Reported metrics are the posterior probability of $K_0$, adjusted Rand index against true labels, held-out log predictive density or log conditional predictive ordinate, and effective sample size per second for K.

The decisive experiment is a sample-size sweep from n = 500 to n = 20,000 on misspecified versions of those settings. True clusters are drawn as skew-normal, Student-t, and curved shapes, placed at the separations of the 10-dimensional simulation. The prediction that would confirm the idea is that the posterior probability of $K_0$ rises with n for our model. It should fall for the naive mixture, fall or stall for the flat repulsive mixture, and stall for the no-repulsion tree ablation. Held-out density fit should equal or exceed that of the naive mixture, since children supply the flexibility.

Three results would refute the claim. One is post-hoc merging matching us on the sweep. Another is the flat repulsive mixture already holding up under misspecification. The third is our top-level count drifting upward with n; that would mean children are escaping their parents, and it would tell us the $\Sigma_b$ bound is doing the real work.

A final real-data check clusters pretrained image features of a held-out set of tieredImageNet-H classes, the 608-class WordNet-organized subset used by Bertinetto et al.. There the true class count is known and cluster shapes are certainly not Gaussian. We found no reported clustering result on Lacuna for tieredImageNet-H features, so all numbers there will be new comparisons among the methods above.