Unsupervised Learning Using Variational Inference on Finite Inverted Dirichlet Mixture Models with Component Splitting

Abstract

Unsupervised learning has been one of the essentials of pattern recognition and data mining. The role of Dirichlet family of mixture models in this field is inevitable. In this article, we propose a finite Inverted Dirichlet mixture model for unsupervised learning using variational inference. In particular, we develop an incremental algorithm with a component splitting approach for local model selection, which makes the clustering algorithm more efficient. We illustrate our model and learning algorithm with synthetic data and some real applications for occupancy estimation in smart homes and topic learning in images and videos. Extensive comparisons with comparable recent approaches have shown the merits of our proposed model.

Appendices

Appendix

Proof of Equations (18), (19), (20)

The solution for variational inference $Q_s\big (\varTheta _s\big )$ is given by (17) as,

$$\begin{aligned} \ln Q_s\big (\varTheta _s\big ) = \big <\ln p\big ({\mathcal {X}},\varTheta \big )\big >_{t\ne s} + {\text {const}} \end{aligned}$$

(37)

where the constant term is the culmination of all the terms that are independent of $Q_s\big (\varTheta _s\big )$. The solutions can be easily derived from the logarithm of the joint distribution $p\big ({\mathcal {X}},\varTheta \big )$ given by,

$$\begin{aligned} \ln p\big ({\mathcal (X)},\varTheta \big )&= \sum _{i=1}^N\sum _{j=1}^MZ_{ij} \Bigg [\ln \pi _j + \ln \frac{\varGamma \big (\sum _{l=1}^{D+1}\alpha _{jl}\big )}{\prod _{l=1}^{D+1}\varGamma \big (\alpha _{jl}\big )} + \sum _{l=1}^D\big (\alpha _{jl} - 1\big )X_{il}\nonumber \\&\quad - \bigg (\sum _{l=1}^{D+1}\alpha _{jl}\bigg ) \ ln\bigg (1 + \sum _{l=1}^D X_{il}\bigg )\Bigg ] \nonumber \\&\quad + \sum _{i=1}^N\Bigg [\sum _{j=1}^sZ_{ij}\ln \pi _j + \sum _{j=s+1}^MZ_{ij}\ln \pi _j^*\Bigg ]\nonumber \\&\quad -\big (M-s\big )\ln \Bigg [1-\sum _{k=1}^s\pi _k\Bigg ]+\frac{\varGamma \big (\sum _{j=s+1}^{M}c_{j}\big )}{\prod _{j=s+1}^{M}\varGamma \big (c_{j}\big )}\nonumber \\&\quad + \sum _{j=s+1}^M\big (c_j-1\big )\bigg [\pi _j^*-\Big (1-\sum _{k=1}^s\pi _k\Big )\bigg ]\nonumber \\&\quad + \sum _{j=1}^M\sum _{l=1}^D u_{jl}\ln \nu _{jl} - \ln \varGamma \big (u_{jl}\big ) + \big (u_{jl} - 1\big )\ln \alpha _{jl} - \nu _{jl}\alpha _{jl} \end{aligned}$$

(38)

1.1 Proof of Equation (18): Variational Solution for $Q\big ({\mathcal {Z}}\big )$

The logarithm of $p\big ({\mathcal {X}},\varTheta \big )$ with respect to Z is given by,

$$\begin{aligned} \ln Q\big (Z_i\big )&= \big<\ln p\big ({\mathcal {X}},\varTheta \big )\big>_{\theta \ne Z_i}\nonumber \\&=\sum _{j=1}^MZ_{ij} \Bigg [\ln \pi _j + R_j + \sum _{l=1}^D\big ({\overline{\alpha }}_{jl} - 1\big )X_{il} - \bigg (\sum _{l=1}^{D+1}\alpha _{jl}\bigg ) \ln \bigg (1 + \sum _{l=1}^D X_{il}\bigg )\Bigg ]\nonumber \\&\quad + \sum _{j=1}^sZ_{ij}\ln \pi _j + \sum _{j=s+1}^MZ_{ij}\big<\ln \pi _j^*\big> + {\text {const}}\nonumber \\&=\sum _{j=1}^sZ_{ij} \Bigg [\ln \pi _j + R_j + \sum _{l=1}^D\big ({\overline{\alpha }}_{jl} - 1\big )X_{il} - \bigg (\sum _{l=1}^{D+1}\alpha _{jl}\bigg ) \ln \bigg (1 + \sum _{l=1}^D X_{il}\bigg )\Bigg ]\nonumber \\&\quad \sum _{j=s+1}^MZ_{ij} \Bigg [\big <\ln \pi _j^*\big > + R_j + \sum _{l=1}^D\big ({\overline{\alpha }}_{jl} - 1\big )X_{il}\nonumber \\&\quad - \bigg (\sum _{l=1}^{D+1}\alpha _{jl}\bigg ) \ln \bigg (1 + \sum _{l=1}^D X_{il}\bigg )\Bigg ] + {\text {const}} \end{aligned}$$

(39)

where,

$$\begin{aligned} R_j = \Bigg<\ln \frac{\varGamma \big (\sum _{l=1}^{D+1}\alpha _{jl}\big )}{\prod _{l=1}^{D+1}\varGamma \big (\alpha _{jl}\big )}\Bigg>_{\alpha _{j1}...\alpha _{jD+1}},{\overline{\alpha }}_{jl} = \big <\alpha _{jl}\big > = \frac{u_{jl}}{\nu _{jl}} \end{aligned}$$

(40)

Here, $R_j$ is intractable as it has no closed form. In order to make the equation tractable we employ the second-order Taylor expansion of the equation similar to the method followed in [65, 66]. This leads us to the Eq. (24) which is actually approximation of $R_j$ and $\big (\varvec{\alpha }_{j1},...,\varvec{\alpha }_{jD+1}\big )$ representing the expected values of $\varvec{\alpha }_j$. Thus, we can calculate ${\tilde{R}}_j$ using Eq. (24). This equation is also found to be the strict lower bound of $R_j$ as proved in [32]. Equation (39) can be now rewritten as,

$$\begin{aligned} \ln Q\big ({\mathcal {Z}}\big ) =\sum _{i=1}^N\Bigg [ \sum _{j=1}^sZ_{ij}\ln {\tilde{r}}_{ij} + \sum _{j=s+1}^MZ_{ij}\ln {\tilde{r}}_{ij}^*\Bigg ] + {\text {const}} \end{aligned}$$

(41)

where

$$\begin{aligned} \ln {\tilde{r}}_{ij} = \ln \pi _j + {\tilde{R}}_j + \sum _{l=1}^D\big ({\overline{\alpha }}_{jl}-1\big )\ln X_{il} - \bigg (\sum _{l=1}^{D+1}\alpha _{jl}\bigg ) \ln \bigg (1 + \sum _{l=1}^D X_{il}\bigg ) \end{aligned}$$

(42)

and

$$\begin{aligned} \ln {\tilde{r}}_{ij}^* = \big <\ln \pi _j^*\big > + {\tilde{R}}_j + \sum _{l=1}^D\big ({\overline{\alpha }}_{jl}-1\big )\ln X_{il} - \bigg (\sum _{l=1}^{D+1}\alpha _{jl}\bigg ) \ln \bigg (1 + \sum _{l=1}^D X_{il}\bigg ) \end{aligned}$$

(43)

It can be seen that Eq. (41) is the logarithmic form of Eq. (7) ignoring the constant. Exponentiating both the sides of Eq. (7), we get,

$$\begin{aligned} Q\big ({\mathcal {Z}}\big ) \propto \prod _{i=1}^{N}\Bigg [\prod _{j=1}^{s}{\tilde{r}}_{ij}^{Z_{ij}}\prod _{j=s+1}^{M}{\tilde{r}}_{ij}^{*Z_{ij}}\Bigg ] \end{aligned}$$

(44)

Normalizing this equation we can write the variational solution of $Q\big ({\mathcal {Z}}\big )$ as,

$$\begin{aligned} Q\big ({\mathcal {Z}}\big ) \propto \prod _{i=1}^{N}\Bigg [\prod _{j=1}^{s}r_{ij}^{Z_{ij}}\prod _{j=s+1}^{M}r_{ij}^{*Z_{ij}}\Bigg ] \end{aligned}$$

(45)

where $r_{ij}$ and $r_{ij}^*$ can be obtained from Eqs. (22) and (23). Also, we can say that $\big <Z_{ij}\big > = r_{ij}$ for $j = 1,...,s$ and $\big <Z_{ij}^*\big > = r_{ij}$ for $j = s+1,...,M$

1.2 Proof of Equation (19): Variational Solution of $Q(\varvec{\pi }^*)$

Similarly, the logarithm of the variational solution $Q\big (\varvec{\pi }^*\big )$ is given as,

$$\begin{aligned} \ln Q\big (\pi _j^*\big )&= \big<\ln p\big ({\mathcal {X}},\varTheta \big )\big>_{\varTheta \ne \pi _j^*}\nonumber \\&=\sum _{i=1}^N\big<Z_{ij}\big>\ln \pi _j^* + \big (c_j - 1\big ) \ln \pi _j^* + {\text {const}}\nonumber \\&=\ln \pi _j^*\Bigg [\sum _{i=1}^N\big <Z_{ij}\big > + c_j - 1 \Bigg ] + {\text {const}} \end{aligned}$$

(46)

This equation shows that it has the same logarithmic form as that of Eq. (9). So we can write the variational solution of $Q\big (\varvec{\pi }^*\big )$ as,

$$\begin{aligned} Q\big (\varvec{\pi }^*\big ) = \Bigg (1 - \sum \limits _{k=1}^s\pi _k\Bigg )^{-M+s} \frac{\varGamma \big (\sum _{j=s+1}^Mc_j^*\big )}{\prod _{j=s+1}^M\varGamma \big (c_j^*\big )}\prod \limits _{j=s+1}^M\Bigg (\frac{\pi _j^*}{1-\sum _{k=1}^s\pi _k}\Bigg )^{c_j^*-1} \end{aligned}$$

(47)

where

$$\begin{aligned} c_j^* = \sum _{i=1}^N \big <Z_{ij}\big > + c_j \end{aligned}$$

(48)

$\big <Z_{ij}\big > = r_{ij}^*$ in the above equation.

1.3 Proof of Equation (20): Variational Solution of $Q\big (\varvec{\alpha }\big )$

As in the other two cases the logarithm of the variational solution $Q\big (\alpha _{jl}\big )$ is given by,

$$\begin{aligned} \ln Q\big (\alpha _{jl}\big )&= \big<\ln p\big ({\mathcal {X}},\varTheta \big )\big>_{\varTheta \ne \alpha _{jl}}\nonumber \\&=\sum _{i=1}^N\big<Z_{ij}\big>{\mathcal {J}}\big (\alpha _{jl}\big )+\alpha _{jl}\sum _{i=1}^N\big <Z_{ij}\big > \ln X_{il} - \alpha _{jl} \ln \Bigg (1+\sum _{l=1}^{D+1}X_{il}\Bigg )\nonumber \\&\quad +\big (u_{jl}-1 \big ) \ln \alpha _{jl} - \nu _{jl}\alpha _{jl} + {\text {const}} \end{aligned}$$

(49)

where,

$$\begin{aligned} {\mathcal {J}}\big (\alpha _{jl}\big ) = \Bigg <\ln \frac{\varGamma \big (\alpha _{jl}+\sum _{s \ne l}^{D+1}\alpha _{js}\big )}{\varGamma \big (\alpha _{jl}\big )\prod _{s \ne l}^{D+1}\varGamma \big (\alpha _{js}\big )}\Bigg >_{\varTheta \ne \alpha _{jl}} \end{aligned}$$

(50)

Similar to what we encountered in the case of $R_j$ the equation for ${\mathcal {J}}\big (\alpha _{jl}\big )$ is also intractable. We solve this problem finding the lower bound for the equation by calculating the first-order Taylor expansion with respect to ${\overline{\alpha }}_{jl}$. The calculated lower bound is given by,

$$\begin{aligned} {\mathcal {L}}\big (\alpha _{jl}\big ) \ge \,\,&{\overline{\alpha }}_{jl} \ln \alpha _{jl}\Bigg [\psi \Bigg (\sum _{l=1}^{D+1}{\overline{\alpha }}_{jl}\Bigg )-\psi \big ({\overline{\alpha }}_{jl}\big )+ \sum _{s \ne l}^{D+1}{\overline{\alpha }}_{js}\nonumber \\&\quad \times \psi '\Bigg (\sum _{l=1}^{D+1}{\overline{\alpha }}_{jl}\Bigg )\big (\big <\ln \alpha _{js}\big >-\ln {\overline{\alpha }}_{js}\big )\Bigg ] + {\text {const}} \end{aligned}$$

(51)

This approximation is also found to be a strict lower bound of ${\mathcal {L}}\big (\alpha _{jl}\big )$ and is also proved in [32]. Substituting this equation for lower bound in Eq. (49)

$$\begin{aligned} \ln Q\big (\alpha _{jl}\big )&= \sum _{i=1}^N\big<Z_{ij}\big>{\overline{\alpha }}_{jl} \ln \alpha _{jl}\Bigg [\psi \Bigg (\sum _{l=1}^{D+1}{\overline{\alpha }}_{jl}\Bigg )-\psi \big ({\overline{\alpha }}_{jl}\big )\nonumber \\&\quad + \sum _{s \ne l}^{D+1}{\overline{\alpha }}_{js} \psi '\Bigg (\sum _{l=1}^{D+1}{\overline{\alpha }}_{jl}\Bigg )\big (\big<\ln \alpha _{js}\big>-\ln {\overline{\alpha }}_{js}\big )\Bigg ]\nonumber \\&\quad +\alpha _{jl}\sum _{i=1}^N\big <Z_{ij}\big > \ln X_{il} - \alpha _{jl} \ln \Bigg (1+\sum _{l=1}^{D+1}X_{il}\Bigg )\nonumber \\&\quad +\big (u_{jl}-1 \big ) \ln \alpha _{jl} - \nu _{jl}\alpha _{jl} + {\text {const}} \end{aligned}$$

(52)

This equation can be rewritten as,

$$\begin{aligned} \ln Q\big (\alpha _{jl}\big ) = \ln \alpha _{jl}\big (u_{jl}+\varphi _{jl} - 1\big ) - \alpha _{jl}\big (\nu _{jl}-\vartheta _{jl}\big ) + {\text {const}} \end{aligned}$$

(53)

where,

$$\begin{aligned} \varphi _{jl}&=\sum _{i=1}^N\big<Z_{ij}\big>{\overline{\alpha }}_{jl} \Bigg [\psi \Bigg (\sum _{l=1}^{D+1}{\overline{\alpha }}_{jl}\Bigg )-\psi \big ({\overline{\alpha }}_{jl}\big )\nonumber \\&\quad + \sum _{s \ne l}^{D+1}{\overline{\alpha }}_{js} \psi '\Bigg (\sum _{l=1}^{D+1}{\overline{\alpha }}_{jl}\Bigg )\big (\big <\ln \alpha _{js}\big >-\ln {\overline{\alpha }}_{js}\big )\Bigg ] \end{aligned}$$

(54)

$$\begin{aligned} \vartheta _{jl}&= \sum _{i=1}^N\big <Z_{ij}\big >\Bigg [\ln X_{il}- \ln \Bigg (1+\sum _{l=1}^D X_{il}\Bigg )\Bigg ] \end{aligned}$$

(55)

Equation (53) is the logarithmic form of a Gamma distribution. If we exponentiate both the sides, we get,

$$\begin{aligned} Q\big (\alpha _{jl}\big ) \propto \alpha _{jl}^{u_{jl}+\varphi _{jl} - 1}e^{-\big (\nu _{jl}-\vartheta _{jl}\big )\alpha _{jl}} \end{aligned}$$

(56)

This leaves us with the optimal solution for the hyper-parameters $u_{jl}$ and $\nu _{jl}$ given by,

$$\begin{aligned} u_{jl}^* = u_{jl} + \varphi _{jl},\,\,\,\, \nu _{jl}^* = \nu _{jl}-\vartheta _{jl} \end{aligned}$$

(57)