[MUSIC]

In the previous video we decided to solve the clustering

problem by making a probabilistic model of our data.

But how? How can we model our

data probabilistically?

Well we don't know that many distributions so far.

But we know Gaussians, right?

So in week one we learned how to feed the parameters of the Gaussian

distribution into the data set.

And we can do it here, it's a reasonable thing to do.

But it turns out that Gaussian is not the very best model for this kind of data.

Recall that we decided that our data consist of several clusters or

groups which may be far away from each other.

And even with this simple example, we can see that Gaussian has

to model all the data points as one big circle or maybe ellipse.

And in this case, It just has to assign hyper mobility to the center of

the circle, it's the way Gaussian works.

And you can see here that the center of the Gaussian kind of fall into

the region in between the clusters where there are not that many data points.

And this is problem with modeling this kind of data with one Gaussian.

We have to model everything with one big circle, and

we have some regions in between the clusters where there are few data points.

But the Gaussian just has to assign hypergrowth to these regions.

So, what else can we do?

Are there any better probabilistic models we can use here?

Well, if one Gaussian doesn't work let's use several of them like three for

example.

So in this case we are kind of assuming that each data point came from one of

the three Gaussians, and each Gaussian explains one cluster of the data points.

Or if you put it more formally then the density of each data point

equals to the weighted sum of three Gaussian densities, and

the weights by are some negative number which sum

up to 1 to make an actual probability distribution.

So the parameters theta here are the weights by.

And three groups of parameters of three Gaussians.

Their locations, the mu vectors, and their shapes, or

their covariance matrices sigma.

Notice that if we succeed in fitting this kind of model into our data,

we will solve clustering problem.

Because for each data point,

we may now find from which Gaussian this data point came from.

And this is exactly the alternative to finding the cluster index.

So we may say that all the points that came from one

Gaussian is the points of one particular cluster.

This models is sometimes called Gaussian Mixture Model, or GMM for short.

So great, we have found model which we would like to use.

What are some positive and negative features of this model,

compared to the just plain one Gaussian?

Well obviously, Gaussian is much less flexible.

So Gaussian Mixture Model allowed us to fit our complicated dataset, and

it actually turns out that you may fit just almost any probability

distribution with Gaussian Mixture Model with arbitrarily high accuracy.

Well of course as always happens with this kind of theorems so in the worst case you

may have to use exponentially many Gaussians, so it's not a very practical

theorem, but anyway Gaussian Mixture Model is very powerful and flexible model.

The downside is obviously the number of parameters.

So, as you increase the number of Gaussians you use for

your data you increase the number of parameters by the same texture right?

Okay great.

We decided to use this kind of Gaussian mixture model.

But how can we fit it?

How can we find its parameters?

So it's bi, mu and sigma vectors and matrices.

Well the simplest way to fit a probability distribution is to use

maximum likelihood estimation right?

So we want to find the values of parameters which maximise the likelihood,

which is the density of our data set given the parameters.

And we want to maximise this thing with respect to the parameters.

It's usually much in learning, we will assume that the data set consists

of n data points, which are independent given our parameters.

Which basically means that we can factorize the likelihood.

So the likelihood equals the product of likelihood of individual objects.

Well, One more thing we can do to

simplify this expression, to understand how to maximize it,

is to substitute the definition of the marginal likelihood of xi given

the parameters by using the definition from a few slides before.

So each data point density is a mixture of Gaussian densities, right?

Okay, so now we have this kind of optimization problem.

And just one more thing we forgot here is, we have some constraints, right?

We have to say that the weights pi are non-negative, and that they sum up to 1.

Because otherwise, it will not be an actual probability distribution.

But now it seems like we're good to go.

Now we may use your favorite stochastic optimization algorithm from data flow,

like item or whatever you would like to use,

and we can optimize this thing to find the optimal parameters, right?

Well, it turns out that we kind of forgot one important set of constraints here.

The covariance [INAUDIBLE] as a sigma cannot be arbitrary.

Imagine that you have,

that your optimization logarithm proposed to use covariance matrix with all zeros.

It just doesn't work. It doesn't define a proper Gaussian

distribution.

Because in Gaussian distribution definition you have to Invert this matrix,

and you have to compute its determinant, and divide by it.

So if you have a matrix which is all 0s,

you will have lots of problems like division by 0, and stuff like that.

So it's not a good idea to assume that the covariance matrix can be anything.

And actually, the set of valid covariance matrices is something called Positive.

Don't worry if you don't know what it is, it's not the important right now.

The important part is that it's a really hard constraint to follow,

so it's hard to adapt your favorite stochastic rate in descent to

always follow of this kind of restraint.

So to maintain this property that the matrices are always positive,

semi-definite I don't know how to do it efficiently, so we have a problem here,

we don't know how to optimize this thing, at least with stochastic rate and descent.

Well, it turns out that even if you get this constraint, so

if you consider a simpler model, for

example if you say that all the covariance matrices are diagonal, which

means that the ellipsoids that corresponds to the Gaussians cannot be rotated.

They have to be aligned with the axis.

In this case it's much easier to maintain this constraint.

And you can actually use some stochastic optimization here.

So for example, in this example I used Adam and

I tuned it learned grade to optimize this thing.

And you can see that it's doing a reasonable job here.

So the blue curve is the, Performance of the item here.

On the x-axis we see epochs, and on the y-axis we see log likelihood,

which we are trying to maximize.

And so, Adam is doing a good job, right?

It's like ten e-books optimizing this thing to to something reasonable.

I think real line here is the ground for which came from minor because I know

from which probability distribution I generate this data, so,

I know the optimal value for the log likelihood.

But it turns out that even in this case where we don't have this very complicated

constraints you can make so much better by exploiting the structure of your problem.

And this is something we're going to discuss in the rest of the week,

is something called the expectation maximization.

And if you apply it here, it just works so much better.

In like a few iterations it found the value,

which is better than the Ground Truth, which probably is overfitting,

but anyway it works good on the test set also.

So to summarize, we may have two reasons to not

to use this stochastic gradient descent here.

First of all, it may be hard to follow some constraints which you may care about,

like positive semidefinite covariance matrices.

And second of all, expectation maximization algorithm,

which can exploit the structure of your program,

sometimes is much more faster and efficient.

So as a general summary we discussed that the Gaussian mixture model is a flexible

probability distribution, which can solve the clustering problem for

you if you fit your data into this Gaussian mixture model.

And sometimes it's hard to optimize for the stochastic gradient descent, but

there is this alternative which we'll talk about in the next video.

[MUSIC]

Gaussian Mixture Model

Bayesian Methods for Machine Learning

Meet the Instructors