This is the fourth part of series of notes taken to summarize notes taken while reading the Pattern Recognition and Machine Learning (Springer, 2006) book and includes simple examples with implementations for demonstration including. As in the first, second and third posts, the goal of these posts is not to be rigorous, comprehensive, or provide any new or advanced information. The target audience was first and foremost myself, but these notes are made available for anyone else who happens to find it useful, including

• Individuals curious enough to want to explore pattern recognition and machine learning, but have no previous exposure to it.
• Individuals who had a course on it and wish to refresh their memory.
• People interested in the ideas and equations, but not interested in only learning recipes and/or only learning how to use a library or toolkit.

Some contents are hidden away from default view inside modal dialogs where no page redirection takes place. These links are underlined. Either clicking outside the window, clicking the close button, or clicking the back button in the browser window will close window.

Basic background in mathematics including: basic calculus, basic linear algebra, exposure to optimization, and basic statistics is assumed; see suggested readings at the end of this page. If your statistics is rusty, fear not, as the author of the PR & ML book writes:

All snippets are done using python 3 using only numpy and matplotlib add-on packages. Also, ffmpeg package needs to be installed to create the videos.

Clustering - Gaussian Mixture Models

Reference: Section 9.2, 9.3

Initially discussion will be limited to Gaussian Mixture Models with Expectation Maximization algorithm previously introduced in Part 2.

Consider Gaussian mixture models composed of $K$ components constructed through a linear superposition of Gaussian distributions

$$p(\mathbf{x})=\sum _k^K{\pi }_k\mathcal{N}(\mathbf{x}|{\mathbf{\mu }}_k,\mathbf{\Sigma }),$$

where it is required that ${\pi }_k\in [0,1]$, ${\sum }_k{\pi }_k=1$ for the above model to be a valid distribution. The ${\pi }_k$ components above denote the contribution of the $k$-th Gaussian and are referred to as the mixing coefficients.

Similar to the previous section, consider the introduction of a $K$ dimensional vector $\mathbf{z}$ for a data point such that $z_k\in \{0,1\}$ (and consequently ${\sum }_k{z}_k=1$) for 1-of-$K$ coding scheme to indicate which class ${\mathcal{C}}_k$ a data point belongs to. The marginal distribution over $\mathbf{z}$ is then specified in terms of the mixing coefficients ${\pi }_k$ such that

$$p(\mathbf{z})=\prod _k^K{\pi }_k^{z_k}.$$

Note that ${\sum }_{\mathbf{z}}p(\mathbf{z})=1$ as required. The conditional distribution of a data point $\mathbf{x}$ for a given $\mathbf{z}$ is written as

$$p(\mathbf{x}|\mathbf{z})=\prod _k\mathcal{N}(\mathbf{x}|{\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k{)}^{z_k},$$

and marginalized distribution

$$\begin{array}{rl}p(\mathbf{x})& =\sum _{\mathbf{z}}p(\mathbf{z})p(\mathbf{x}|\mathbf{z})\\ & =\sum _{\mathbf{z}}\prod _k^K[{\pi }_k\mathcal{N}(\mathbf{x}|{\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k){]}^{z_k}\\ & =\sum _k^K{\pi }_k\mathcal{N}(\mathbf{x}|{\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k).\end{array}$$

Note that each distribution has independent unknown parameters ${\mathbf{\Sigma }}_k,{\mathbf{\mu }}_k,{\pi }_k$. As seen before, these quantities may be determined by maximum likelihood. Let $\mathbf{X}\in {\mathbb{R}}^{N\times D}$ denote the training set where each row contains a single data point. Similarly, let $\mathbf{Z}\in {\mathbb{R}}^{N\times K}$ denote the corresponding latent variables with rows ${\mathbf{z}}_n$.

Consider now the maximization of the complete data set $\{\mathbf{X},\mathbf{Z}\}$, given by

$$p(\mathbf{X},\mathbf{Z}|\underset{\mathbf{\theta }}{\underbrace{\mathbf{\mu },\mathbf{\Sigma },\mathbf{\pi }}})=\prod _n^N\prod _k^K{\pi }^{z_{nk}}\mathcal{N}({\mathbf{x}}_n|{\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k{)}^{z_{nk}}$$

subject to the constraint ${\sum }_k{\pi }_k=1$.

Next we proceed using the Expectation Maximization algorithm discussed in Part 2. As a reminder, consider the maximization of the expected value of the conditional distribution $p(\mathbf{Z}|\mathbf{X}.\mathbf{\theta })$ under the complete log distribution:

$$\begin{array}{rl}\underset{\mathbf{\pi },\mathbf{\mu },\mathbf{\Sigma }}{\mathrm{argmax}}{\mathbb{E}}_{p(\mathbf{Z}|\mathbf{X},{\mathbf{\theta }}^{old})}[\log p(\mathbf{X},\mathbf{Z}|{\mathbf{\theta }}^{old})]& =\underset{\mathbf{\pi },\mathbf{\mu },\mathbf{\Sigma }}{\mathrm{argmax}}\sum _{\mathbf{Z}}\log p(\mathbf{X},\mathbf{Z}|{\mathbf{\theta }}^{old})p(\mathbf{Z}|\mathbf{X},{\mathbf{\theta }}^{old})\end{array}$$

where,

$$\begin{array}{rl}p(\mathbf{Z}|\mathbf{X},\mathbf{\theta })& =\frac{p(\mathbf{X}|\mathbf{Z})p(\mathbf{Z})}{p(\mathbf{X})}\\ & =\frac{{\prod }_n^N{\prod }_k^K[{\pi }_k\mathcal{N}({\mathbf{x}}_n|{\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k){]}^{z_{nk}}}{{\sum }_{\mathbf{Z}}{\prod }_n^N{\prod }_k^K[{\pi }_k\mathcal{N}({\mathbf{x}}_n|{\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k){]}^{z_{nk}}}.\\ & =\frac{{\prod }_n^N{\prod }_k^K[{\pi }_k\mathcal{N}({\mathbf{x}}_n|{\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k){]}^{z_{nk}}}{{\sum }_{{\mathbf{z}}_n}{\prod }_k^K[{\pi }_k\mathcal{N}({\mathbf{x}}_n|{\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k){]}^{z_{nk}}},\\ & =\frac{{\prod }_n^N{\prod }_k^K[{\pi }_k\mathcal{N}({\mathbf{x}}_n|{\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k){]}^{z_{nk}}}{{\sum }_k{\pi }_k\mathcal{N}({\mathbf{x}}_n|{\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k)}.\end{array}$$

As a reminder, $z_{nk}\in \{0,1\}$ corresponds to the indicator term for the $k$-th class of the $n$-th point, $\{{\mathbf{z}}_n\}$ are independent, and each point can be assigned to one class. When computing the expected value of $\log p(\mathbf{X},\mathbf{Z}|{\mathbf{\theta }}^{old})$, the expected value of $z_{nk}$ under this distribution:

$$\begin{array}{rl}\mathbb{E}[z_{nk}]& =\frac{{\sum }_{{\mathbf{z}}_n}{z}_{nk}{\prod }_{k^{\prime }}^K[{\pi }_k^{\prime }\mathcal{N}({\mathbf{x}}_n|{\mathbf{\mu }}_k^{\prime },{\mathbf{\Sigma }}_k^{\prime }){]}^{z_{nk}}}{{\sum }_k{\pi }_k\mathcal{N}({\mathbf{x}}_n|{\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k)}\\ & =\frac{{\sum }_{{\mathbf{z}}_n}{z}_{nk}{\prod }_{k^{\prime }}^K[{\pi }_k^{\prime }\mathcal{N}({\mathbf{x}}_n|{\mathbf{\mu }}_k^{\prime },{\mathbf{\Sigma }}_k^{\prime }){]}^{z_{nk}}}{{\sum }_k{\pi }_k\mathcal{N}({\mathbf{x}}_n|{\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k)}\\ & =\frac{{\pi }_k\mathcal{N}({\mathbf{x}}_n|{\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k)}{{\sum }_k{\pi }_k\mathcal{N}({\mathbf{x}}_n|{\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k)}\\ & =:\gamma (z_{nk})\end{array}$$

The expected value of the complete-data log likelihood under this distribution with the constraint built in then becomes

$$\begin{array}{rl}{\mathbb{E}}_{p(\mathbf{Z}|\mathbf{X},{\mathbf{\theta }}^{old})}[\log p(\mathbf{X},\mathbf{Z}|{\mathbf{\theta }}^{old})]& =\sum _n\sum _k\gamma (z_{nk})\left(\log {\pi }_k+\log \mathcal{N}({\mathbf{x}}_n|{\mathbf{\mu }}_k,{\mathbf{\Sigma }}_k)\right)-\lambda \left(\sum _k{\pi }_k-1\right)\end{array}$$

Maximization of the above objective function with respect to $\pi ,\mathbf{\mu },\mathbf{\Sigma }$ leads to

$$\begin{array}{rl}{\pi }_k& =\frac{1}{N}\sum _n\gamma (z_{nk})\\ {\mathbf{\mu }}_k& =\frac{1}{{\sum }_n\gamma (z_{nk})}\sum _n\gamma (z_{nk}){\mathbf{x}}_n\\ {\mathbf{\Sigma }}_k& =\frac{1}{{\sum }_n\gamma (z_{nk})}\sum _n\gamma (z_{nk})({\mathbf{x}}_n-{\mathbf{\mu }}_k)({\mathbf{x}}_n-{\mathbf{\mu }}_k{)}^T.\end{array}$$

The Expectation Maximization algorithm thus reduces to:

References

Suggested general reference books:

• Bishop, Christopher M. Pattern Recognition and Machine Learning. Springer, 2006.

  Base reference for content of this page, though certainly not the best book that I have read.

• Boyd, Stephen, and Lieven Vandenberghe. Convex Optimization. Cambridge university press, 2004.

  A classic and a must-read introductory book to (convex) optimization for everyone regardless of their background. PDF copy is also available on Standford webpage as of this writing.

• Greenberg, Michael D. Foundations of Applied Mathematics. Courier Corporation, 2013.

  Good reference book or refresher on applied math.

• Bulmer, Michael George. Principles of Statistics. Courier Corporation, 1979.

  Very easy read and short refresher on basics of statistics.