[MUSIC]
We showed that if you know the cluster parameters,
then it's easy to compute the soft assignments.
And then we showed that if you know the soft assignments,
it's very straightforward to estimate the cluster parameters.
So this motivates an iterative algorithm where we're going to cycle
between these two steps.
And the algorithm that we're going to present is a special case of a more
generic algorithm called expectation maximization or.
So more formally, the Algorithm for mixtures of Gaussian is going to
cycle between two steps where in the first step, which is called the E step.
We're going to estimate our cluster responsibilities
given the current estimate of our cluster parameters and the equation for this for
the mixture of Gaussian case is shown here
which is just a specific example of the equations that we showed previously.
Then the second step of that algorithm which is called the M-step
is to compute the maximum likelihood estimate of our cluster parameters
given our current estimate of the soft assignments.
And so the update here, the maximum likelihood estimate based on a set
of soft assignments takes the form of the equations that we showed previously.
In pictures, the Algorithm works as follows.
The first step is to initialize our set of model parameters.
So our mixture weights at the zeroth iteration, our means,
and our covariances and
those are represented by the ellipses shown in this picture,
where each one has a center and then give and spread an orientation.
Then having fixed these cluster
parameters then we compute our responsibilities.
So our estimate of the responsibilities at the first
iteration are based just by computing that prior times the likelihood term for
each cluster and then normalizing so I won't repeat the equations here.
But just to show in pictures that the point here is that this data point.
So each one of these big circles is a data point.
And it's also a pie chart,
which is indicating the responsibilities associated with that data point.
So for example this data point here,
maybe this has a responsibility vector at the first iteration.
That is maybe it's something like 0.52
in the fuchsia color and 0.4 in the blue cluster and
has a responsibility of 0.08 to the green cluster.
And then having computed these responsibilities for
each of our data points, we go and we reestimate our cluster parameters.
So we're going to maximize
The likelihood given our soft assignments.
Rik at the first iteration.
And this is going to lead to updated estimates of our cluster parameters pi hat
k at iteration one, mu hat k at iteration one, sigma hat k, at iteration one.
And what you see in this picture is that these ellipses have shifted and changed.
So then, based on these new set of clusters
are the parameters associated with these clusters.
We're going to recompute our responsibilities.
So estimate of the responsibilities at the second iteration.
And then we are going to rinse and repeat.
Until convergence and
we are going to talk about convergence more in the next section.
But here's our plot at convergence, and
what you see is that our clusters are pretty clean.
They, in my point of view, capture the structure of the data fairly well.
And, really critically, if we look at, for example, this observation here.
We see that even after convergence, there's still uncertainty that's
represented in that observations cluster assignment.
And I want to emphasize that this is exactly what we want from this algorithm.
In contrast to k mean, that would have made a hard decision about whether that
observation was going to be associated with the blue cluster or fuschia cluster.
Here, Provides the sense of uncertainty
about which cluster this observation should be associated with.
And this is true for other observations as well, not as much as for
this observation that's clearly on the boundary of these two clusters.
But in summary, hopefully we see now in pictures the difference between what
Gives us and K means.
And again, just to emphasize, not only is it giving us this soft assignments but
we also have estimates of the cluster parameters so the shapes of these
different clusters and their locations in the space, not just the cluster locations.
So let's watch this one more time and
before we do just remember each one of this circles or
this little pipe charts is a data point and the color shown in the pie
chart represent the responsibilities associated with that observation.
So how much its currently associated with anyone of the three clusters and
our model.
And this ellipses represents the three different 2D Gaussians in this example and
as we're going through these plots it's going to show the updates to both
the responsibilities and our estimates of these cluster parameters.
So here is our initialization of the algorithm and
then this is after one iteration, two iterations and act convergence.
[MUSIC]