# Bayesian mixture models (in)consistency for the number of clusters

Louise Alamichel, Daria Bystrova, Julyan Arbel, Guillaume Kon Kam King

► To cite this version:

Louise Alamichel, Daria Bystrova, Julyan Arbel, Guillaume Kon Kam King. Bayesian mixture models (in)consistency for the number of clusters. 13th Bayesian nonparametrics (BNP) conference, Oct 2022, Puerto Varas, Chile. . [hal-03866441](https://hal.science/hal-03866441)

HAL Id: hal-03866441

https://hal.science/hal-03866441

Submitted on 22 Nov 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Bayesian mixture models (in)consistency for the number of clusters

Louise Alamichel¹, Daria Bystrova¹, Julyan Arbel¹, Guillaume Kon Kam King²

<figure><img src="image_2.png" /></figure>

¹Univ. Grenoble Alpes, Inria, France

²Univ. Paris-Saclay, INRAE, France

<figure><img src="image_3.png" /></figure>

## Mixture models

$$x \sim \int p(\cdot|\boldsymbol{\theta})G(\mathrm{d}\boldsymbol{\theta}),$$

with $G$ the mixing measure.

$$x | \mathbf{w}, \boldsymbol{\theta}, K \sim f(\cdot) = \sum_{k=1}^{K} w_k p(\cdot|\theta_k),$$

where $K$ is the number of components, $\mathbf{w}$ the weights and $p$ a kernel parametrized by $\boldsymbol{\theta}$.

$K$ may be fixed, infinite or random.

## Posterior consistency

The posterior distribution is said to be consistent at $\theta_0$ if $\Pi(U^c | X_{1:n}) \xrightarrow{n \to \infty}$ 0 in $P_{\theta_0}$-probability for all neighborhoods $U$ of $\theta_0$.

$G_0$ defines a finite mixture with $K_0$ components; consistency for $G$ with $K$ components:

<table><thead><tr><th rowspan="2">Quantity of interest</th><th colspan="2">Finite</th><th> Infinite</th><th> MFM</th></tr><tr><th>$K = K_0$</th><th>$K \ge K_0$</th><th>$K = \infty$</th><th>$K$ random</th></tr></thead><tbody><tr><td>Density $f_0$</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>$G_0$</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>$K_0$</td><td>N/A</td><td>✗ / ✓</td><td>✗ / ✓</td><td>✓</td></tr></tbody></table>

## Partition-based model

* Partitions in $k$ sets:

$$\mathcal{A}_k(n) = \{(A_1, \dots, A_k) : \bigcup_{i=1}^k A_i = 1 : n\}$$

* For $A \in \mathcal{A}_k(n)$, $\mathcal{Z}_A = \{B(A, j), j \in 1 : n\}$

<figure><img src="image_4.png" /></figure>

$$A \in \mathcal{A}_k(n)$$

$$B = B(A, j) \in \mathcal{A}_{k+1}(n)$$

* $K_n$: number of clusters

$$p(A, k) = p(A)\mathbb{I}(A \in \mathcal{A}_k(n))$$

$$\theta_i | A, k \sim \pi,$$

$$i = 1, \dots, n$$

$$x_j | A, k, \theta_{1:k} \sim p(\cdot|\theta_l) \text{ if } j \in A_l,$$

$$j = 1, \dots, n$$

## Partition distributions

Gibbs-type process with $0 < \sigma < 1$, $A \in \mathcal{A}_k(n)$, $n_j := |A_j|$:

$$p(A) = \frac{V_{n,k}}{k!} \prod_{j=1}^{k} (1 - \sigma)_{n_j-1}.$$

$V_{n,k}$ satisfy the recurrence relation

$$V_{n,k} = (n - \sigma k)V_{n+1,k} + V_{n+1,k+1}, \quad V_{1,1} = 1.$$

Examples of Gibbs-type processes finite representation:

* Dirichlet multinomial process,

* Pitman-Yor multinomial process,

* NGG multinomial process,

parametrized by $K < \infty$: for $k \le \min(n, K)$, $A \in \mathcal{A}_k(n)$,

$$p(A) = \prod_K(n_1, \dots, n_k).$$

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

## Inconsistency Theorem [1]

**Condition 1:** Assume for any $k \ge 1$, $\limsup_{n \to \infty} \frac{1}{n} \max_{A \in \mathcal{A}_k(n)} \max_{B \in \mathcal{Z}_A} \frac{p(A)}{p(B)} < \infty$.

**Condition 2:** Condition on the data distribution which involves a control on the likelihood.

**Theorem 1 [1]:** Let $X_1, X_2, \dots \in \mathcal{X}$ be a sequence of r.v., and consider a partition-based model. Then, for any $k \ge 1$ if Conditions 1 and 2 hold, we have

$$\limsup_{n \to \infty} \Pi(K_n = k | X_{1:n}) < 1 \text{ with probability 1.}$$

## Inconsistency results

**Proposition 1:** Consider a Gibbs-type process with $0 < \sigma < 1$, then **Condition 1** holds for any $k \in \{1, 2, \dots\}$, so does the inconsistency of Theorem 1.

**Proposition 2:** Consider any of the following priors:

* Dirichlet multinomial process,

* Pitman-Yor multinomial process,

* Normalized Generalized Gamma multinomial process, then **Condition 1** holds for any $k < \min(n, K)$, and so does the inconsistency of Theorem 1.

Illustration on simulated data:

<figure><img src="image_7.png" /><figcaption>Figure 1: Distribution of $K_n$ for a Dirichlet multinomial process, $\alpha = 0.9$.</figcaption></figure>

## Idea of the proof for Gibbs-type processes

* For fixed $k$, $\forall A \in \mathcal{A}_k(n)$ and $B = B(A, j)$, we want $\frac{1}{n} \max_{A,B} \frac{p(A)}{p(B)} < \infty$, we can show $\frac{1}{np(B)} \le \frac{V_{n,k}}{V_{n,k+1}}(k+1)$.

* It is sufficient to prove $(\frac{V_{n,k}}{V_{n,k+1}})_{n \ge 0}$ is bounded. By an approximation of $V_{n,k}$: $(\frac{V_{n,k}}{V_{n,k+1}})_{n \ge 0}$ converges, so is bounded.

Illustration of function $n \mapsto \frac{1}{n} \max_{A \in \mathcal{A}_k(n)} \max_{B \in \mathcal{Z}_A} \frac{p(A)}{p(B)}$, for $k \in \{1, 10, 100\}$:

<figure><img src="image_8.png" /></figure>

<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /></figure>

## Consistency results

* **Dirichlet multinomial process:** satisfies assumptions in [2] for some $\alpha$, so the weights of extra clusters $\to 0$, a form of mixing measure consistency.

* **PY multinomial process:** for $\sigma = 1/2$ and some $\alpha$ satisfies assumptions in [2], the weights of extra clusters $\to 0$.

* **Dirichlet process:** Posterior consistency for $K_n$ by MTM shown in [3].

* **Pitman-Yor process:** from [4] we deduce a contraction rate, hence by using MTM algorithm we have posterior consistency for $K_n$.

* **Overfitted mixtures:** Posterior consistency for $K_n$ by MTM.

## Merge-Truncate-Merge algorithm [3]

Suppose $\omega_n : W_r(G, G_0) = o_p(\omega_n)$ for posterior sample $G$

<figure><img src="image_11.png" /><figcaption>Figure 1: Initial distribution $G$.</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Figure 2: After first stage-"merge".</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>Figure 3: After second stage-"truncation".</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Figure 4: After second stage-"merge".</figcaption></figure>

Figure 2: MTM algorithm illustration (figure from [3]).
$\tilde{k}$ number of support atoms of the output $\tilde{G}$.

$$\Pi(\tilde{k} = k_0 | X_{1:n}) \to 1 \text{ in probability.}$$

## Future work

* Do the inconsistency results generalize to NIDM processes ?

* Can consistency be recovered by adding a prior on $\alpha$, as in [5] ?

Preprint available on arXiv, search for "Alamichel".

## References

[1] Jeffrey W Miller and Matthew T Harrison. Inconsistency of Pitman-Yor process mixtures for the number of components. *The Journal of Machine Learning Research*, 15(1):3333–3370, 2014.

[2] Judith Rousseau and Kerrie Mengersen. Asymptotic behaviour of the posterior distribution in overfitted mixture models. *Journal of the Royal Statistical Society: Series B (Statistical Methodology)*, 73(5):689–710, 2011.

[3] Aritra Guha, Nhat Ho, and XuanLong Nguyen. On posterior contraction of parameters and interpretability in bayesian mixture modeling. *Bernoulli*, 27(4):2159–2188, 2021.

[4] Catia Scricciolo. Adaptive Bayesian density estimation in Lp-metrics with Pitman-Yor or normalized inverse-Gaussian process kernel mixtures. *Bayesian Analysis*, 9(2):475–520, 2014.

[5] Filippo Ascolani, Antonio Lijoi, Giovanni Rebaudo, and Giacomo Zanella. Clustering consistency with Dirichlet process mixtures. *arXiv preprint arXiv:2205.12924*, 2022.