Perhaps the most common use of the
expectation maximization algorithm is to
the problem of learning with latent
variables. These are situations where
there is a certain set of variables that
we just never get to observe. But they
turn out to be important for capturing
some important latent structure in the
distribution of the data instances that we
have. So let's look at a number of these
examples and talk about how '''em was
applied in those settings. So perhaps the
simplest example is in the context of
[inaudible] clustering. Where, we have
some kind of latent class variables and
some set of observed features, and we're
trying to basically segment the instances
that we have into categories where we
assume that for each category, there is a
similar distribution over the observed
features. And specifically in many of
these applications that distribution takes
the fall of the [inaudible]. That is that
the features are independent once given
the class. So, one example application of
this, is the segmenting, a set of users
into a similarity groups. And so, one cute
example of that is, the following
segmentation of users on the msnbc website
based on which of the stories on msnbc
site the users chose to click. And this is
due to jack freeze and callings in
Microsoft research. So Here we see, we're
gonna see four clusters. The first of
these is a cluster that a human given name
to, because the machine doesn't give a
name to the cluster, it just calls it
cluster one. Turns out to be readers of
commerce and technology stories. So these
are people for whom the highest
probability clicks on stories were, for
example, email delivery isn't exactly
guaranteed, or should you buy a DVD
player? So, remember, the stories are the
features, and they're binary valuables.
Did you click or did you not click on that
particular article? [inaudible] And the
cluster is the segmentation of the users
into these different categories. So this
is category one. The second cluster are
people who primarily clicked on sports
stories. So the highest probability
features in this, for this user group,
were, for example, stories such as Cowboys
are reborn, and win over Eagles, or
something like that. The third cluster are
the people who went to the top page, and
basically clicked on the top promoted
stories. This says [inaudible], 29 percent
of the users. And one can. Dates this by
at least this article. Oh, this one seems
pretty perennial. And so we can, so that's
the third category. The last one was the
surprising one. These are people who
traversed all over the site. So for the
previous three categories, there were
actual pages that existed, for sports, for
top promoted stories, and for commerce and
technology. This last category are people
who went all over the site to look for
stories that you might call softer news.
And, so, this was an interesting discovery
for the MSNBC website about its user
population. And suggested that the website
might. Be better redesigned to capture
this kind of structure and give these
users a page where they can find these
articles. [sound]. A very different
application is to speech recognition,
which is one that we've talked about
before. In the context of speech
recognition, we've already discussed that
the standard representation of choice is a
hidden Markov model. And in a hidden
Markov model, we have hidden variables,
and we have parameters. The parameters are
the parameters of the HMM. The. Transition
probabilities for example between one
phone and the other. Or, the acoustics, or
the probability over the acoustics signal
that we observe for different pieces are
states within a phone. The latent
variables are the segmentation of the
initial acoustic signal into which state
it belongs to; that is, which phoneme and
which part of which phoneme. Those are the
hidden variables. And that's an awful lot
of hidden variables. Because, if we're
just given an undifferentiated,
unsegmented signal, it's very difficult to
assign. As, as a piece, a small slice of
that speech into one [inaudible] versus
the other. So. In order to train well a
speech recognition HMM, the standard
strategy is a bottom up, boot strap
training, where one first trains the phone
HMM separately for each phone using a
phone database. Now this, too, is done
using yam because the breakdown within a
phone into these little constituent pieces
is not. Labeled and so it still requires
that we do [inaudible] to address the
issue of latent variables, but at least
it's now self contained because you're
only training the model for a single phone
like [inaudible]. With that model trained,
we can now, one can now take entire words
and use the model initialized with the
phone, the, the model trained on
individual phones to now train the higher
level model. And one still retrains the
phone HMM parameters. In the context of
this larger training regime, where one now
trains on entire words. But the fact that
when seated the model, with this much more
correct initialization on the parameters,
allows the segmentation in the E step to
be performed moderately correctly, and
gives rise to a much better local optimum
in the speech recognition problem. [sound]
And yet a different application is that of
3D robot mapping. So, this is an
application that's do to [inaudible] at
all and Here, the input to the, to the
problem, is a sequence of point clouds
obtained by a laser range finder that were
collected by a moving robot. And the
target output is a 3D map of the
environment as a set of planes. And you'll
see the difference as to why we want the
plainar map when we look at the demo. Here
the parameters of the model are the
location and the angles of the walls, or
the planes in the environment. So we have
no idea a priori where there are walls and
how they're situated. The [inaudible]
variables are an association. Variables
which assign points to walls. And so the
'''em algorithm effectively in the E step,
figures out which points go with which
wall. And in the M step it figures out how
to move the wall around to better fit the
points that were assigned to it. So what
we see here is the raw data collected by
the robot. The red box is the robot moving
around in its environment. The, red beams
that emanate from the robot are the
directions that the laser took in order to
collect the point cloud. And what we see
here, is, the point cloud that was
collected by the robot as it traversed the
environment. And even just looking at this
image, we can already see that there's a
lot of noise in the laser range data. And
that, and that this is going to give rise,
as we can see, to a very noisy map of the
environment. If we now look at the model
constructed by [inaudible], and so now
we're going to see the planar map
constructed by the robot. And this is done
on the fly, actually as the robot is
moving. We can see that... Walls are
constructed when there is enough data to
support them. And, and that's, when enough
points are assigned to a wall, then that
wall gets constructed, and its pose in the
environment gets determined by the EN
algorithm. And so we can see that this
constructs a much more plausible and
realistic map of the environment than just
looking at the raw point cloud data.
[sound] A, different application is also
in the context of 3D laser [inaudible].
And you know, we picked those not because
these are the most common applications of
[inaudible] but because they give rise to
some pretty cool movies. So here is, the
problem of getting, in this case, 3D rain
scans of a person in different poses. And
the goal is to see whether by collecting a
bunch of these poses, one can reconstruct.
A 3D skeleton of. Person. So, from front
and from back. So in this particular case.
The first problem is, actually, to
correspond points in the difference
[inaudible] to each other. And this case
that was done by a different algorithm
that I'm not going to talk about now,
although, it also uses graphical models.
In fact it used a belief propagation
algorithm. But now let's talk about the
clustering problem that is the problem of,
of assigning points in each of those scans
to body parts. So, here we have the notion
of a cluster which, in this case,
corresponds to a part, and. Each part. In
a given, in a given scan of the person has
a transformation. So, that's why we have a
plate around each of the parts, because we
have an insta, because for each of those
parts there is multiple instantiations in
the multiple scans that we have of the
same person in different poses. Now a
landmark is a particular point on that. On
that person, in that in that part. And if
we knew the part, that is if we have the
part assignments which is [inaudible]
unobserved variable then we could predict
how the point that we see. On this scan,
would translate to the point on this scan
because that would be effectively a
deterministic or close to the terministic
function of the unobserved transformation
of the part, that is the fact that the
arms they moved from this pose over here
to this raised arm pose over here. So
given the transformation and given that we
know which part the point, or landmark, is
assigned to, we can predict how the point
transformed from its original position to
its new position. So this is a way of
clustering points into parts. And one can
run '''em on that, and if one does that,
effectively, one gets pretty much garbage.
Because it turns out that there is enough
muscle deformation to make the actual
positions here fairly noisy, and it's very
difficult to get correct parts assignments
from that. But, if we now add an
additional component into this model.
Specifically, contiguity of space. We can
now consider say two points that are
adjacent to each other and impose the soft
constraint, not the hard constraint but a
soft constraint, that a part assignment of
two points that are adjacent should be
softly the same. Doesn't have to be
exactly the same because otherwise of
course everything would be assigned to the
same part but it's a soft constraint which
is actually an MRF constraint. In fact
it's even an amaranth constraint, which is
associative or regular. As we discuss
before. And so, this, this model now, that
actually does the questioning not of each
point in isolation, but rather assigns
point jointly to parts taking in
considerations the geometry of the
person?s body is considerably better of
its right considerably better outputs. And
what we see here, is the algorithm in
action. And we can see that the algorithm
converges very nicely to a partition of
the points into different parts and from
this one can easily reconstruct the
skeleton. A final application that uses
'''em in a yet a different model, is one
that was used in this helicopter demo
alignment. Here the input, this was work
that was done at Stanford by And rings
group, and here the input to the algorithm
is basically different trajectories of the
same aerobatic maneuver flown by different
pilots so they were all trying to do the
same thing, but each person has their own
idiosyncratic way of doing this and so,
the pb, the exact sequence was as we see
exactly the same. The goal of this, was to
produce an output, which aligns the
trajectories to each other, and at the
same time, learns a probabilistic model of
what the target or template trajectory
ought to have been. So how does this get
represented as a graphical model? Here we
have, a latent trajectory, which is the
intended trajectory that, that the users
were aiming for. And the states in those
are labeled as Zs. And we have parameters
that tell us how one would move from Z
zero to Z1 and so on. So those are the
model parameters of this Markov model.
Although it?s a hidden markup model as
we'll see. The expert demonstrations, that
is what we saw in terms of what the expert
did at each point in time is a noisy
observation of the intended trajectory.
But, we don't actually know which point in
the trajectory the expert observation
comes from and so we have this additional
set of latent variables which are the time
indices and they basically tell us that at
time tau zero. The demonstration, which of
the. Which of the true states in the
intended trajectory, the expert was added
this point. And it, and Tau one tells us
which point in the intended trajectory the
expert was in time one, and similarly, for
time two, and so on. Where [inaudible] is
the is the expert demonstration. So in
the, so K is the index on the expert. So,
this problem can be solved using an
expectation maximization algorithm where
we have two sets of latent variables, the
[inaudible] and the z's and one set of
model parameters which are. The transition
probabilities. Although, it's possible
that we can also, it's also possible to
learn the model for the M expert
demonstrations. Or we can simply fix the
noise model. Both are legitimate
strategies. So let's see how this works.
Let's first look at the original
trajectories, and we can see that,
initially, they start out aligned. But
after a while, they start to diverge. So,
for example, by the time we're right about
here, you can see the different experts
are very different places in the
trajectory. And so the question is, how
can we address that limitation. And so if
we look at the aligned model, which is
what we see over here on the right. We can
see that the algorithm manages to maintain
alignment. Fairly well, and that, here you
can see. That the. Different trajectories
are pretty much at exactly the same point
in the sequence. And from that it's much
easier now to learn the model and have the
helicopter fly the new, fly the correct
trajectory. So one important issue
regarding latent variables is the number
of values of the latent variables. And
this is something that has been implicit
in many of the applications that I have
mentioned in this module. So how many user
clusters do we have or how many different
pieces of a phone are there. And so how do
we pick the cardinality for the latent
variable? If we use likelihood to evaluate
a model with fewer values for the latent
variables versus one with more it's in the
same wave as likelihood always over fits.
We'll find that more values is always
better because it's a strictly more
expressive model and can therefore achieve
a higher likelihood. Now one can
circumvent that, in the same way that we
circumvented the likelihood over-fitting
phenomenon in the context of other
structure learning algorithms. So we can
use, for example, a score, that penalizes
complexity. Such as the BIC score. As we
mentioned back then, the BIC score tends
to under fit, and so there has been a
range of extensions to the Bayesian score
for the context of incomplete data. These
are always approximations because we can't
actually do the integration required for
the Bayesian score for incomplete data,
and so we have approximations to the
Bayesian score that turn out to work much
better in practice than BIC in many
practical applications. There's also other
strategies that people have adopted. For
example, we can use metrics of cluster
coherents to look at a cluster, and say,
ooh, it seems like this cluster is really
incoherent, so maybe there's really two
clusters in there, so maybe we should
split it up. Or these two clusters are
very similar to each. Maybe we should
merge them. And there's various heuristic
exploration algorithms that basically
split clusters and add clusters in a way
that hopefully converges to the right
number of clusters. And finally, of great
popularity in the last few years, is a
range of methods that are based on
Bayesian techniques. These are methods
often the most commonly used class is
called Dirichlet processes, which instead
of picking a single cardinality for the
latent variable, basically maintain a
distribution over the cardinality. And
then, instead of picking a single value
for that cardinality, average over the
different cardinalities. Using often
techniques such as Markov Chain, Monte
Carlo, although there's also other
approaches. But this turns out often that
the problem of late invariable cardinality
is often one of the trickier issues that
one has to deal with when learning with
latent variable. To summarize, latent
variables are a really common scenario in
the context of learning graphical models.
And one of, perhaps, the most common
setting for incomplete data. And it turns
out that when we want to construct models
for richly structured domains, the
introduction of these latent variables can
be, can be critical in the success of the
model. We, it's, we've already mentioned
that latent variables satisfy the missing
at random assumptions, and so the
expectation maximization algorithm is
applicable in this case. And, and is very
commonly used for, for optimizing latent
variable models. However, it's, we've,
we've already discussed this, previously
as well, that when we're learning with
latent variables, we have serious
problems, both with identifiability. The
learned model as well a multiple
[inaudible] that are often even symmetric
reflections of each other. Which is a
facet of unidentifiability but also ones
that are not reflections are just
symmetric permutations of each other. And
those really necessitate a good
initialization strategy. And, we mentioned
that picking variable cardinality for the
latent variables is a key question in, in
these latent variable models, and one to
which a lot of work has been devoted,
especially in the last few years.