Probabilistic graphical models (PGMs) are a rich framework for encoding probability distributions over complex domains: joint (multivariate) distributions over large numbers of random variables that interact with each other. These representations sit at the intersection of statistics and computer science, relying on concepts from probability theory, graph algorithms, machine learning, and more. They are the basis for the state-of-the-art methods in a wide variety of applications, such as medical diagnosis, image understanding, speech recognition, natural language processing, and many, many more. They are also a foundational tool in formulating many machine learning problems. This course is the third in a sequence of three. Following the first course, which focused on representation, and the second, which focused on inference, this course addresses the question of learning: how a PGM can be learned from a data set of examples. The course discusses the key problems of parameter estimation in both directed and undirected models, as well as the structure learning task for directed models. The (highly recommended) honors track contains two hands-on programming assignments, in which key routines of two commonly used learning algorithms are implemented and applied to a real-world problem.
Latent Variables
Loading...
來自 Stanford University 的課程
Probabilistic Graphical Models 3: Learning
211 個評分
從本節課中
Learning BNs with Incomplete Data
In this module, we discuss the problem of learning models in cases where some of the variables in some of the data cases are not fully observed. We discuss why this situation is considerably more complex than the fully observable case. We then present the Expectation Maximization (EM) algorithm, which is used in a wide variety of problems.
與講師見面
Daphne KollerProfessor
School of Engineering
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
context of base in clustering. Where we have some kind of, latent class
variable 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
form of a [INAUDIBLE], [INAUDIBLE], and that is, that the features are
independent, once we're given the class. So one example application of this is to
segmenting a set of users into 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 the MSNBC site the users chose
to click and this is due to Jack Breeze and colleagues at Microsoft research So
here we see. We're going to 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 their binary variables did you click
or did you not click, on that particular article.
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 in 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 stories.
This says twenty, 29% of the users. And
one can. Date this by, at least this article, oh
this one seems pretty perennial. and so we can so that's a 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 structures and give these users a page where they can find
these articles. 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 or states within a
phone. The latent variables are the segmentation
of the initial acoustic signal into which state it belongs to.
That is which full name and which part of which full name,
those are the hidden variables. And that's an awful lot of hidden
variables. Because if we are just given an
undifferentiated, unsegmented signal, it's very difficult to assign.
As, as a piece, a small slice of that segment of, of that speech into one fully
versus the other. So in order to train well a speech recognition HMM, the
standard strategy is a bottom up bootstrap training where one first trains
the phone HMM separately for each phone using, a phone database.
Now this to is done using the m because the breakdown within a phone into these
little constituent pieces is not labeled. And so it's still requires that we d 'em
to address the issue of latent variables, but at least it's now self contained,
because you're only training a model for a single phone.
like puh. With that model trained, we can now one
can now take entire words, and use the model, initialized with the phone with
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 trains on entire words,
but the fact that one seeded the model with this much more correct
initialization on the parameters allows the segmentation in the E step to be
performed moderately correctly and give rise to a much better local optimum in
the speech recognition problem. A yet different application is that of 3D
robot mapping. So, this is an application that's due to
thrun 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
plains and you will see the difference as to why we want the plainer map when we
look at the demo. Here the parameters of the model are the
location and the angles of walls or the plains in the environment, so we have no
idea of priori where there walls and how there situated.
The latent variables are as an association.
Variables, which assign points to walls. And so the EML Rhythm 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 a Traversty environment.
And even just looking at this image we can already see that there is a lot of
noise in the laser range data, and that and that is going to give rise as we can
see to a very noisy map of the environment.
If we now look at the marvel constructed by Yen.
So now we are going to see the planer 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, that's when enough points are assigned to a wall
then, that wall gets constructed and it's pose in the environment gets determined
by the EN algorithm. And, so we can see that everybody's
construct a much more plausible and realistic map of the environment than
just looking at the raw point cloud data. .
A, different application is also in the context of 3D laser range scans.
And, you know, we pick those, not because these are in the most common applications
of the M. But because they give rise to some pretty
cool movies. So, here is, the problem of getting, in
this case 3D, brain scans of a person in different
poses. And the goal is to see whether by
collection a bunch of these poses one can reconstruct a 3D skeleton of.
Person. So from front and front back.
So, in this particular case. the first problem is actually to
correspond points in the difference cans to each other and in this case that was
done by a different algorithm that I'm not going to talk about now although it
also used graphical models in fact it used a belief propigational algorithm.
But now lets talk about the clustering problem that is the problem 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, extenty, fo,
because, for each of those parts there is multiple estantions and then multiple,
scans that we have 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
had the part assignment, which is a latent, 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 deterministic 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 part assignments from that, but
if we now add an additional component into this model.
Specifically continuity 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 MRF constraint, which is associate or regular.
As we discussed before. And so these this model now that actually
does the clustering not of each point in isolation but rather assigns points
jointly to parts taking into consideration the geometry of the
person's body is a considerably better gives rise to 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. that points into different parts and from
this one can easily reconstruct the skeleton.
A final application that uses 'em in a different model is one that was used in
this helicopter demo alignment. Here the input and this is work that was
done at Stanford by And the 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, the exact sequence wasn't, as
we'll 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
problemistic 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 an nose are labeled as zees and we have parameters,
that tell us how, one would move from Z0 to Z1 and so on.
So those are the model parameters of this mark off model.
although it's a hidden Markov 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 at, at this point and, in towel one, tells us which
point in the intended trajectory the expert was in time one, and similarly for
time two, and so on. We're, Kebba 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
taus and the Zs, 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, expert demonstrations.
Or we could 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 that the different experts are at very different
places in the trajectory. And so the question is, how can we ad-,
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 trajec-, 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've 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 that cardinality
for the latent variable? If we use likelihood to evaluate a model
with fewer values for the latent variable versus one with more.
It's in the same way that likely it always over fits.
We will find more values is always better, because it is 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
overfitting phenomenon in the context of other structured 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 coherence 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 if these two clusters are very similar
to each other, maybe we should merge them.
And there is 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 Dasian techniques.
these are methods, often, the most commonly used class is called [UNKNOWN]
prostheses. Which instead of picking a single
carnality for the laten variable, basically maintain a distribution, over
the carnality. 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 the, the problem
of picking out latent variable cardinality is often one of trickier
issues that one has to do deal with when learning with latent variables.
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. Of the learned model as well as well as
multiple optima that are often even symmetric reflections of each other which
is a faceted unidentified ability but also ones that are not reflections or
just symmetric permeantations of each other and those really necessitate a good
initialization strategy. And we mention 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 to especially in the last
few years.
