Inference in mixture models | Guest lecture by Tom Heskes

Very popular for data where we have latent variables.

  • Machine learning recap
  • Clustering and k-means
  • Maximum Likelihood Estimation
  • Classification
  • Clustering with Gaussian Mixture Models (and EM model)

Machine Learning review

David Mackay, Information, Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003.

(This lecture discusses chapter 20-22 (?) I thought)

Freely available: www.inference.phy.cam.ac.uk/itprnn/book.html

Mackay first person to introduce Bayesian methods in machine learning field.

Machine learning applications to "knowledge-poor" but "data-rich" problems.

Today the main topic is unsupervised learning. Given data, we try to discover structure in the data.

  • Clustering
  • Compression

Clustering

The goal of clustering are:

  • discovering hidden 'classes' and we hope they have meaning.
    • E.g. observe the color of living things; two unobserved classes may be "animals" and "living plants".
  • Vector Quantization (e.g. compression)
    • E.g. image segmentation: reduce image to K colors, by seeing pixels as 3D samples.
  • Outlier detection

K-means clustering

Define the binary responsibility $r_{nk}$, which is 1 iff $n$ is assigned to $k$.

Find a partition such that data points ${x_n}$ are partitioned into K disjoint subsets such that error function J is minimized.

What are the parameters of J?

  • $r_{nk}$
  • $m_k$
  • K
    • A higher K will always lead to a lower error (but this is increasingly likely overfitting! )
    • In a way a "hyperparameter"; not directly optimized.

Compute partial derivates of J w.r.t. parameters $r_nk$ and Algorithm:

  1. Set K means to random values
  2. Optimize $r_nk$ by assigning datapoints to closest means
  3. Update sample means: weighted average (weighted by responsibilities) over datapoints corresponding to a cluster k.
  4. Repeat 2 and 3 until convergence

Issues

Where does K-means go wrong?

  • "little" and "large" cluster
  • elongated shapes of two clusters

Other issues:

  • We don't really have good methods for finding K.
    • One approach is to plot J against the number of K clusters, taking into account it always gets better. Then we pick the point where the "l" curve starts to flatten (so here we have diminishing returns + chance of overfitting)
  • Sensitivity to random initial cluster assignment
  • What distance measure to use?
  • Only distance counts, there is no "size" measure for the clusters
  • No measure for the 'shape' of the clusters
    • Cf. point with elongated clusters
  • Binary assignment is binary; no soft cluster assignments.

Maximum Likelihood Estimation

We will talk about mixtures of Gaussians. So we need to talk about a binomial distribution over cluster assignments. Intermediate step: review MLE.

We have a probabilistic model $p(D|\theta)$, is both a function of the data and the model parameters.

Sampling distribution: if we set model parameters e.g. $p(D|\theta=\theta_0)$ we can sample data points.

In machine learning, we go the other way: we want to find the model parameters such that the data is fitted.

When viewed the same function as a function of model parameters we speak of the likelihood function (so here the data is fixed):

$p(D=D_0|\theta)$

This is not a probability distribution for $\theta$.

Example:

We have data D and want to predict a 'new' datum x.

  1. specific probabilistic model
  2. inference (learning)
  3. model-based prediction

We will work this out for MLE.

  1. Choose model

Specify a data generating distribution $p(x|\theta)$

  1. Learning

Maximimize the log-likelihood for given data D, using i.i.d. assumption.

We assume that:

  • Data points are independent given model parameters.
  • Data points come from the same distribution

Q: When does this assumption fail?

A: For time series data!

  1. Prediction

Find $\hat{\theta}$ and substitute this in the model to get our best fitting data generating distribution.

$p(\mathbf{x}|D) = p(\mathbf{x}|\hat{\theta})$

Difference with Bayesian approach is that we really analytically optimize at step 2.

Now we look at the two "base cases" for MLE: Multivariate Gaussians for continuous variables and the Multinomial distribution for discrete variables.

MLE with Log-likelihood for a multivariate Gaussian

Model: MVG.

Write out log-likelihood of MVG. We have on term corresponding to determinant of covariance function; the other to the Manahoibis distance. (I also saw this in the book). If the Sigma would be the identify matrix this would reduce to Euclidean distance.

Our parameters are mean and covariance matrix. We are trying to optimize these.

Take gradient of loss w.r.t. mean and covariance.

For MVG we know that there is a single maximum, so we can just set the gradient to 0 and easily find a solution.

The MLE solution for the mean is not surprisingly the sample mean.

REVIEW (slide on MLE for variance of MVG):

  • vector derivative and matrix derivative.
  • Check relation of determinant of matrix w.r.t. determinant of its inverse.
  • Something with "trace" of the matrix. Sum of elements on the diagonal.
  • Gradient of determinant of inverse matrix is just.. the matrix (I think). Review.

Note! We are taking the frequentist MLE approach we are doing a bit of overfitting. That's why we use 1/N (biased estimator) instead of 1/(N-1) (Bayesian unbiased approach).

MLE for multinomial distribution

We have a die with K-sides, then $x_k = 1$ iff die lands on kth face.

Estimate what's the probability that die ends up with face k.

I didn't do bold face on vectors properly! Be aware of this!

Model: multinomial model $p(x_k|\theta_k)$ with constraint that $\sum_k \theta_k = 1$ which effectively leads to k-1 parameters.

Handy notation:

$p(x|\theta) = \prod_k \theta_k ^(x_k)$

We use one-hot-encoding, so we either have $\theta^0$ (drops out in product i.e. x1 ) or $\theta^1$.

Now for the whole data we also deal with n-throws.

$p(D|\theta) = log \prod_n \prod_k \theta_k ^(x_{nk})$

TODO: derive formula (as sum I think); too slow here.

Sufficient statistic: we only have to take into account the counts some die is counted. Insight here is that this simple result can be derived with the MLE method.

Then apply Lagrange multiplier with the constraint to find the MLE for $\theta$.

When taking derivative w.r.t. lambda, we have the constraint back. When taking w.r.t. $\theta_k$, we take the constraint into account. Then we'll get the MLE with lambda as a parameters, but lambda is set to N because then the constraint is satisfied.

MLE for Generative Probabilistic Classification

We have some dataset with known labels. Now for a new data points, what's the probability it belongs to a particular class?

Example with two classes

Priors: sample proportions.

Generative classification: model specification for the joint pdf p(x|y)p(y), then use Bayes to infer posterior class probabilities.

Model specification: Distribution within each of the classes is a MVG. They have a different mean, for now we assume they have the same shared covariance matrix.

Once we know these parameters, we can use Bayes' rule for competing the probability over classes for a new data point.

Now we maximize the joint log-likelihood of inputs-outputs.

Again use one-hot encoding; then this breaks down into a problem with two components:

  • Multinomial density estimation for class prior pi_k
  • Gaussian density estimation for parameters mean and covariance

Using this we can get the priors for the classes, and the MVG we compute after grouping the data into separate classes.

$y_nk$ is used for grouping the data of the same class (it's 1 if the class under consideration; 0 otherwise).

Gaussian Mixture Model for unobserved classes

Classification with unobserved classes: we have a "clustering" problem.

We will use the same model for the Bayesian classifier. But now we introduce a parameter of the unobserved (latent) class, z.

We end up with a Gaussian Mixture Model.

This is a universal approximators of densities (similar to a multi-layer perceptron). If we have enough latents, we can approximate any function. But the curse of dimensionality is relevant: in practice we will not have enough data to make a good approximation in high dimensions.

(E.g. "spike and slap model": heavily spiked Guassian with flat Gaussian to make the long tails).

The model now is a sum over all k of $p(x_n, z_{nk}=1)$

But now the sum over k is within the log:

$\sum_n log \sum_k \pi_k N(x_n|\mu_k,\Sigma_k)$

This is hard to work with!

Posterior responsibility is a soft class estimator

Knowing the theta's and other parameters, we can compute the expectation that a data point belongs to cluster $z_k$.

$p(z_{nk}=1)= \pi_k$

Note that $\gamma_{nk}$ is in [0 .. 1].

They are called soft responsibilities. (Before we hard the hard binary responsibilities in clustering $y_{nk}$).

REVIEW.

MLE for clustering

Plug in soft responsibilities in formulas for mean and covariance matrix and the prior $\pi_k$. But responsibilities also respond on the parameters!

Solution: we iterate between updating the responsibilities and the model parameters.

This is Expectation-Maximization (EM) for multivariate Gaussians.

We see that this handles the elongated shapes k-means didn't do.

One downside is that final convergence is very slow. It's quite greedy.

K-means is a special case of EM

K-means:

  • All clusters same covariance (which is why we can't separate small and large clusters)
    • So similar to using mixture components with fixed variance $\epsilon \mathbf{I}$.
  • Take limit of $\epsilon$ to zero to get hard assignments.

Difference with EM-GMM is that the covariance matrix is now "trainable".

MLE Overfitting Problem

We have now a lot of flexibility. We may overfit on the data by assigning a cluster to one datapoint; if we optimize we basically end up with a delta peak.

Went a bit fast. Slide "Maximum Likelihood Problem"

Conclusion

What's nice is that the same probabilistic models form the basis for unsupervised and supervised approaches; it's a very general and extensible framework for machine learning.

ML estimation is an approximation of Bayesian learning. This estimation works well when we have much data, but in general this method is very sensitive to overfitting (as we've seen before).

The EM algorithm is a general approach to MLE for models with hidden variables. It's a natural elegant approach, but for specific problems you may have faster alternatives.