The algorithm we're going to use to infer the cluster parameters as well as soft
assignments is something called expectation maximization or.
And the idea is we start with a set of unlabeled, observed inputs.
Such as the data shown here.
And the goal is to output a set of soft assignments per data point
meaning an allocation of that data point to each one of the clusters.
And in this example, there are three different clusters.
A fuchsia cluster, a green cluster and a blue cluster and
the shadings of the individual data points indicates the uncertainty of our
assignment of that data point to each of these different clusters.
And a key question here is how are we going to output the soft assignments
just from this set of unlabeled data points.
well to begin with lets just assume we actually know the cluster parameters and
we just want to compute the soft assignments having fixed the values
of this cluster parameters.
The soft assignments are quantified by something called
the responsibility vector, so for each observation I.
We form a responsibility vector with elements Ri1,
Ri2, all the way up to Ri
capital k where capital k is the total number of clusters
in our mixture model and each element Ri little k,
represents the responsibility that cluster k takes for observation i.
So in particular, it's the probability that observation i is
assigned to k cluster, so that's this term here.
Given, remember this bar here means given.
The set of cluster weights and shapes.
So that's here, remember the pi's or the weights and
the muse in the sigma's specify the shapes of each of the clusters and
were going to condition on observed value of the i data point so that's xi here.
So just to make sure this notation is very clear.
What we're writing here when we write probability of the first thing is
the random variable that the distribution is over.
And then on the right-hand side of this given sign this var.
These are going to be a set of fixed values.
That define the probability distribution.
But before we get to specifying this probability in equations,
let's gain some intuition by looking at a set of pictures.
And in this example, we're going to assume that there's just two clusters,
this green and blue cluster, with spherically symmetric shapes, and we're
going to assume that there's basically equal weightings between the two clusters,
which we see from the fact that they have.
Very similar numbers of data points which are represented by these little stars.
And then we're going to hone in on a single observation
which is outlined with this pink color.
And we're going to look at
the soft assignment of this observation to these two clusters.
And what we see in this case here is that this highlighted observation
is closer to the center of the green cluster than it is to the blue cluster.
So as a result, the green cluster is going to take more responsibility for
this observation than the blue cluster.
Though still both split responsibility for this observation.
But in contrast in this situation here, notice that we've
shifted our highlighted data point towards the blue cluster.
So now this key observation is closer to the center of the blue cluster.
And this blue cluster, as a result, is going to take more responsibility for
this data point.
But, finally, if the key observation were somewhere in-between the two clusters,
then there would be basically split responsibility between the green and
blue cluster, representing a lot of uncertainty.
In the cluster membership for that data point.
But what if one cluster weighed much more heavily in a mixture model than the other
cluster.
So, for example,
what if this green cluster have a lot more mass than the blue one?
And we see this now by the green cluster having lots and lots of data points and
the blue cluster having just a few.
On this case, if we look at this highlighted observation that was
on the boundary of the green and blue clusters.
We're still of course uncertain about the cluster membership, but the green cluster
starts to seem like a much more likely explanation for this observed point.
And so, what happens is because of this imbalance
in the proportion of the clusters in our mixture model,
the green cluster starts to take more responsibility for that point than
the blue point whereas previously it was exactly split between the two clusters.
In equations, we're saying that we need to weigh this initial or
prior probability that a given observation comes from anyone of our clusters
with how likely the observed value is under each of these clusters.
So, that's the second term here.
So, for example let me switch colors here, yeah I'll choose a red color.
If we look at a data point here.
Maybe we would say that this data point is
very unlikely under the green cluster.
Even though our prior probability on the green cluster is much higher.
So we really have to consider both a these two terms together.
Then in order to make this a valid probability,
we need to normalize over all possible cluster assignments.
These equations quantify the discussion that we had in the last section
where we talked about how in to weigh the prior term which represented just for
example that prior probability that out of our set of images were going to grab
out an image and that image is going to be a cloud image with the likelihood term.
Which represented for
a given image based on the values that we're observing on of that image.
How likely are those values under a giving cluster assignment.
And as we see now,
it is indeed the combination of these two terms that determine our soft assignments.
So, in summery, if we know the cluster parameters,
then computing these soft assignments is really trivial.
All we have to do is for
each one of our possible clusters, we compute the prior times the likelyhood.
To form our responsibility and then just normalize this vector, so
that it sums to one over all the possible clusters.
But the story isn't over, because we don't actually know our cluster parameters.
That's something that we also have to somehow infer just from our
unlabeled data.