1
00:00:00,000 --> 00:00:04,527
Our final big module in this course is
that of learning a probabilistic graphical
2
00:00:04,527 --> 00:00:09,109
model from data. Before we delve into the
details of a learning, a specific learning
3
00:00:09,109 --> 00:00:13,360
algorithm, let's think about some of the
reasons why we might want to learn a
4
00:00:13,360 --> 00:00:17,832
probabilistic graphical model from data,
some of the different scenarios in which
5
00:00:17,832 --> 00:00:22,414
this learning problem might arise and how
we might go about evaluating the results
6
00:00:22,414 --> 00:00:27,780
of our learning algorithm. So the setup
here is that we assume that we have some
7
00:00:27,780 --> 00:00:32,874
kind of true distribution, which is
typically denoted by P. And in many
8
00:00:32,874 --> 00:00:38,406
cases, although not always, we might
assume that P is actually generated from
9
00:00:38,406 --> 00:00:44,010
a probabilistic graphical model, M. And
that assumption allows us to talk about
10
00:00:44,010 --> 00:00:49,396
the differences between a learned model
and the ground truth model, M that
11
00:00:49,396 --> 00:00:58,077
generated, the distribution. Now. We're
assuming that from this distribution P,
12
00:00:58,077 --> 00:01:05,509
we get a data set, D, of instances
d1 up to dM. And we're assuming that those
13
00:01:05,509 --> 00:01:11,545
are sampled from distribution P. Now,
in addition to the data, we may or may not
14
00:01:11,545 --> 00:01:16,354
have some amount of domain expertise that
allows us to put in some prior knowledge
15
00:01:16,354 --> 00:01:20,932
into the model. And in fact, the ability
to put in prior knowledge is one of the
16
00:01:20,932 --> 00:01:25,915
strengths of probabilistic graphical model
learning as compared to a variety of other
17
00:01:25,915 --> 00:01:30,639
learning algorithms where this is not
always quite as easily done. So combining
18
00:01:30,639 --> 00:01:36,245
elicitation from an expert and learning,
what we end up with is a network that we
19
00:01:36,245 --> 00:01:41,782
can then, look at and use for different
purposes. So to make this a little bit
20
00:01:41,782 --> 00:01:46,972
more concrete, let's look at the,
different scenarios in the context of a
21
00:01:46,972 --> 00:01:52,647
Bayesian network. The issues in a Markov
network look, fairly identical. So in the
22
00:01:52,647 --> 00:01:58,171
case of known structure and complete data,
we have a network which we assume to be
23
00:01:58,171 --> 00:02:04,471
true. We have input data which is nice and
clean. We see that all the variables have
24
00:02:04,471 --> 00:02:11,528
values in every single instance. And our
goal is to produce. This set of CPDs, for
25
00:02:11,528 --> 00:02:18,344
the network. In the case of unknown
structure in the complete data, we have
26
00:02:18,344 --> 00:02:26,449
the same type of datasets, but notice that
now the initial network has no edges in it
27
00:02:26,449 --> 00:02:33,515
and we now need to infer the edge connectivity as well as the CPDs. Incomplete
28
00:02:33,515 --> 00:02:40,356
data arises when, notice that here we have
some of the variables are not observed in
29
00:02:40,356 --> 00:02:46,952
the training data. And as we'll this can
actually complicate the learning problem
30
00:02:46,952 --> 00:02:53,958
quite considerably. And finally, the
unknown structure, incomplete data. Now in
31
00:02:53,958 --> 00:03:00,109
the latent variable case notice that we
have a situation where we know about three
32
00:03:00,109 --> 00:03:05,889
of the variables X1, X2 and Y but our
final model has in addition to X1, X2 and
33
00:03:05,889 --> 00:03:12,114
Y an additional latent variable H that we
didn't even know about, it might have been
34
00:03:12,114 --> 00:03:18,191
here but we didn't observe any of the
values for it. We didn't even know of its
35
00:03:18,191 --> 00:03:24,268
existent and we want to learn a model that
involves not only X1, X2 and Y but also
36
00:03:24,268 --> 00:03:31,142
the variable H. So, now let's think about
the reasons why we might want to learn a
37
00:03:31,142 --> 00:03:35,761
probabilistic graphical model. And, the
most obvious one is that we want a model
38
00:03:35,761 --> 00:03:40,436
that we can use in the same way that we
would use one that we elicited by hand to
39
00:03:40,436 --> 00:03:44,997
just answer probabilistic queries whether
conditional probability queries or map
40
00:03:44,997 --> 00:03:49,434
queries, about new instances that we
haven't seen before. Now, introducing
41
00:03:49,434 --> 00:03:55,498
concepts that we'll study in a more detail
a little bit later on, the simplest
42
00:03:55,498 --> 00:04:01,330
possible metric that we might envision,
for training a PGM is basically, how
43
00:04:01,330 --> 00:04:07,861
probable are the instances that we've seen
relative to a given model? So, this metric
44
00:04:07,861 --> 00:04:14,159
is called training set likelihood and
it's formalized as the following, it's the
45
00:04:14,159 --> 00:04:20,757
probability of the data that we've seen,
our data set D. Relative to a given model M.
46
00:04:20,757 --> 00:04:25,941
And the intuition behind this is, that if
a model makes the data more likely, it,
47
00:04:25,941 --> 00:04:31,190
that it was more likely to have generated
this data set then it's a pretty good
48
00:04:31,190 --> 00:04:37,027
model or pretty good assumption about the
process that generated our data. And, in
49
00:04:37,027 --> 00:04:43,822
this in just opening up this definition
this just turns into the product over,
50
00:04:44,074 --> 00:04:51,540
over instances M of the probability of the
individual instances given the model given
51
00:04:51,540 --> 00:04:58,420
candidate model M. And this is assuming
that the instances are, independent and
52
00:04:58,420 --> 00:05:04,808
identically distributed from the model M.
So, one important notion that will
53
00:05:04,808 --> 00:05:10,313
accompany us throughout this discussion is
that while training set likelihood seems
54
00:05:10,313 --> 00:05:15,819
intuitively like a pretty good, surrogate
for a pretty good scoring function for
55
00:05:15,819 --> 00:05:21,062
picking a model, it isn't what we actually
care about. Because what we really care
56
00:05:21,062 --> 00:05:25,716
about is new data. Not the data that we
got before. We care about making
57
00:05:25,716 --> 00:05:31,240
conclusions about data that we haven't
seen. And so what we really want to do is
58
00:05:31,240 --> 00:05:37,401
evaluate our model on a separate test set
and you've all already seen the notion of
59
00:05:37,401 --> 00:05:43,269
test set in concept of other learning
problems and the same the same idea is
60
00:05:43,269 --> 00:05:49,137
fundamental here in PGM as well is that
our evaluation really should care about
61
00:05:49,137 --> 00:05:55,152
not the original data set D but
rather a new data set D prime
62
00:05:55,152 --> 00:06:00,360
which gives us a surrogate for what's
called generalization performance.
63
00:06:00,360 --> 00:06:12,039
[sound]. [sound]. A related, but somewhat
different variant on the notion of,
64
00:06:12,039 --> 00:06:17,634
[inaudible], on the learning task that you
might want the PGM to perform, is when we
65
00:06:17,634 --> 00:06:23,499
have a specific prediction problem that we
care about. So, for example, we might so
66
00:06:23,499 --> 00:06:28,285
where we specifically care about
predicting a particular set of target
67
00:06:28,285 --> 00:06:33,071
variables Y from a set of observed
variables X. And we've seen multiple
68
00:06:33,071 --> 00:06:37,992
examples of this such as image
segmentation, where we have, for example,
69
00:06:37,992 --> 00:06:43,506
X being the pixels in the image, and Y
being the predictive. Class labels. Speech
70
00:06:43,506 --> 00:06:49,654
recognition is another such example, where
we have an acoustic signal as X, and a
71
00:06:49,654 --> 00:06:57,197
sequence of phonemes as Y. So all of these
are, are cases where we have a particular
72
00:06:57,197 --> 00:07:03,049
prediction task. Now. Although, in this
case, we often care about a specialized
73
00:07:03,049 --> 00:07:08,150
objective. So, for example, pixel-level segmentation accuracy, in the
74
00:07:08,150 --> 00:07:13,592
context of the image segmentation. Or in
the context of speech recognition, might
75
00:07:13,592 --> 00:07:19,102
care about the word accuracy rate. Even
though that's often the case, it turns out
76
00:07:19,102 --> 00:07:24,816
that, in many cases, it's convenient for,
for algorithmic and mathematical purposes,
77
00:07:24,816 --> 00:07:29,754
to select our model to optimize the same
notion of either likelihood. Or
78
00:07:29,754 --> 00:07:35,786
conditional likelihood, where we try and
predict, where we're computing the
79
00:07:35,786 --> 00:07:41,714
probability of the Y's given the X's. And
although that. Likelihood is not always a
80
00:07:41,714 --> 00:07:45,725
perfect surrogate for the objective that,
the specialized objective, that we
81
00:07:45,725 --> 00:07:50,004
actually care about, it turns out to be
mathematically convenient, and that's why
82
00:07:50,004 --> 00:07:55,736
it's often done. However, it's important
to evaluate the model performance, on the
83
00:07:55,736 --> 00:08:01,695
true objective over test data as opposed
to just use likelihood as in the
84
00:08:01,695 --> 00:08:07,512
evaluation of how successful our learning
algorithm was. A third setting where we
85
00:08:07,512 --> 00:08:12,315
might want to use PGM learning is actually
qualitatively quite different. In this
86
00:08:12,315 --> 00:08:17,000
case, we might not care about using the
model for any particular inference task
87
00:08:17,000 --> 00:08:21,566
but rather we hear about inferring the
structure itself. That is, what we care
88
00:08:21,566 --> 00:08:26,369
about is knowledge discovery, or structure
discovery, where our goal is to try and
89
00:08:26,369 --> 00:08:31,370
get as close as possible to the generating
model, M star. Using PGM learning for this
90
00:08:31,370 --> 00:08:36,232
task might help us distinguish between
direct and indirect dependencies. So if we
91
00:08:36,232 --> 00:08:40,793
see a correlation between X and Y in the
data, we want to infer whether that
92
00:08:40,793 --> 00:08:45,295
corresponds to a direct probabilistic
interaction between them, or something
93
00:08:45,295 --> 00:08:49,857
that, proceeds via third variable Z, for
example. In some cases, when we are
94
00:08:49,857 --> 00:08:54,658
learning a Bayesian network, we might be
able to infer the directionality of the
95
00:08:54,658 --> 00:08:59,315
edges, and thereby, get some intuition
regarding causality. And in other cases
96
00:08:59,315 --> 00:09:04,061
when we learn models with latent
variables, the existence of those latent
97
00:09:04,061 --> 00:09:09,068
variables, their location and often the
way in which the values of the latent
98
00:09:09,068 --> 00:09:14,009
variables get assigned to different
instances, gives us a lot of information
99
00:09:14,009 --> 00:09:20,235
about the structure of the domain. In many
cases although not always when we, when we
100
00:09:20,235 --> 00:09:26,901
solve this learning problem by training
using the same ideas that use a likelihood
101
00:09:26,901 --> 00:09:32,496
based objective for training. Now we know
that, that is not a particularly good
102
00:09:32,496 --> 00:09:37,428
surrogate for structural accuracy but from
a mathematical and algorithmic
103
00:09:37,428 --> 00:09:42,560
perspective, it's a very convenient
optimization objective. And therefore it's
104
00:09:42,560 --> 00:09:48,121
often used in practice although there are
also other ideas out there. However, it's
105
00:09:48,121 --> 00:09:53,744
important not to use likelihood even
likelihood of the test set as the sole
106
00:09:53,744 --> 00:09:58,923
objective for evaluating model
performance. And in many cases, as we'll
107
00:09:58,923 --> 00:10:04,545
see in the context of some examples, the
evaluation here needs to be done by
108
00:10:04,545 --> 00:10:10,242
comparing to whatever limited prior
knowledge we have about the model M star.
109
00:10:10,242 --> 00:10:16,604
So we can compare prior knowledge that was
not given to the algorithm and see whether
110
00:10:16,604 --> 00:10:22,506
the algorithm was able to adequately
reconstruct this. Now, we talked earlier
111
00:10:22,506 --> 00:10:29,873
in this module about the fact that, that
the training likelihood tends to over fit
112
00:10:29,873 --> 00:10:36,546
the model and that in fact is a general
observation, that when you select the
113
00:10:36,546 --> 00:10:43,133
model M to optimize the training set
likelihood, then that tends to over fit
114
00:10:43,133 --> 00:10:49,980
badly to statistical noise random
fluctuations that happen when we generate
115
00:10:49,980 --> 00:10:56,522
our training sets. That happens in several
different ways. It happens, by over
116
00:10:56,522 --> 00:11:02,476
fitting at the level of parameters. So
where the parameters fit random noise in
117
00:11:02,476 --> 00:11:09,083
the training data. And that can be avoided
by the use of regularization, or parameter
118
00:11:09,083 --> 00:11:15,452
priors over the parameters. And we'll see
how that gets done. It also happens when
119
00:11:15,452 --> 00:11:19,701
we over fit the structure. And
specifically, one can show that if we
120
00:11:19,701 --> 00:11:25,044
optimize the training set likelihood, then
complex structures always win. That is, we
121
00:11:25,044 --> 00:11:30,388
would always prefer the most complicated
structure that our model allows. And so if
122
00:11:30,388 --> 00:11:35,667
we're training, if we're trying to fit
structure, it's important to either bound
123
00:11:35,667 --> 00:11:40,625
the model complexity, or penalize the
model complexity, so that we don't learn
124
00:11:40,625 --> 00:11:45,642
models that are just ridiculously
complicated for no good reason. Now all of
125
00:11:45,642 --> 00:11:51,622
these different choices that we've talked
about are called hyper-parameters. So
126
00:11:51,622 --> 00:11:57,980
hyper-parameters include things like the
parameters priors or the regularization.
127
00:11:57,980 --> 00:12:03,015
Over parameters, the strength of the
regularization. If we're doing complexity,
128
00:12:03,212 --> 00:12:08,313
bounds, or complexity penalties, that's
another hyperparameter. All of these are
129
00:12:08,313 --> 00:12:13,022
things that we need to pick before we
could actually apply our learning
130
00:12:13,022 --> 00:12:17,862
algorithm. And so how does that happen?
Well, we need to figure out a way to
131
00:12:17,862 --> 00:12:23,094
select that. And it turns out that, that
decision makes a huge difference, in many
132
00:12:23,094 --> 00:12:27,865
cases, to the performance of our learning
algorithm. And so how do we fit these
133
00:12:27,865 --> 00:12:32,226
hyper-parameters? Well one obvious choice
is to put them on the training set. A few
134
00:12:32,226 --> 00:12:36,374
seconds of thought often convinced us
that, that is a terrible idea because we
135
00:12:36,374 --> 00:12:40,735
just talked about the fact that on the
training set the optimal thing to do is to
136
00:12:40,735 --> 00:12:45,202
have maximum complexity. And so if we put
these hyper parameters on the training set
137
00:12:45,202 --> 00:12:49,275
they're going to effectively become
totally vacuous. Another obvious
138
00:12:49,275 --> 00:12:54,889
choice is to pick them on the test set.
That turns out to be another terrible idea
139
00:12:54,889 --> 00:13:00,503
because that basically makes us look over,
makes our performance overly optimistic
140
00:13:00,503 --> 00:13:05,980
because we picked these very important
parameters so as to optimize performance
141
00:13:05,980 --> 00:13:11,644
on the test set. So training set is bad.
Test is bad. And so the correct strategy
142
00:13:11,644 --> 00:13:17,857
is to use what's called a validation set.
Which is a set that is separate from both
143
00:13:17,857 --> 00:13:23,996
our training set on the one hand and our
test set on the other. A variance on this
144
00:13:23,996 --> 00:13:29,786
is to use what's called cross validation
on. The training set, where we split the
145
00:13:29,786 --> 00:13:35,612
training set, iteratively into a training
and a validation component and use that to
146
00:13:35,612 --> 00:13:41,369
pick hyper parameters. And these are all
concepts that you've seen before in the
147
00:13:41,369 --> 00:13:47,570
context of other learning algorithms, and
they're equally important here. [sound]
148
00:13:47,570 --> 00:13:52,707
Finally, let's talk about why you might,
why and when you might want to use PGM
149
00:13:52,707 --> 00:13:58,740
learning as opposed to a generic machine
learning algorithm. Pgm learning is
150
00:13:58,740 --> 00:14:03,690
particularly useful when what we're trying
to do is make predictions, not over a
151
00:14:03,690 --> 00:14:08,825
single output variable, such as a binary
outcome like a positive class or a
152
00:14:08,825 --> 00:14:13,466
negative class. But rather, we're trying
to make predictions over structured
153
00:14:13,466 --> 00:14:18,354
objects. For example, labeling entire
sequences as in when we're trying to do
154
00:14:18,540 --> 00:14:22,659
For example, sequence labeling and, and,
and speech recognition or in natural
155
00:14:22,659 --> 00:14:26,990
language processing or when we're trying
to label entire graphs. For example, in
156
00:14:26,990 --> 00:14:31,215
the case of image segmentation where we
have, there's a grid of pixels and we're
157
00:14:31,215 --> 00:14:35,981
trying to label all the pixels simultan,
simultaneously. This allows us to exploit
158
00:14:35,981 --> 00:14:41,495
correlations between multiple predicted
variables often giving us significant
159
00:14:41,495 --> 00:14:47,264
improvements to performance. A second
reason to use PGM learning, is it allows
160
00:14:47,264 --> 00:14:53,793
us to incorporate prior knowledge into our
model in a way that many other algorithms
161
00:14:53,793 --> 00:14:58,505
have a bit of a difficulty in, in
allowing. And finally, this is
162
00:14:58,505 --> 00:15:04,182
particularly useful when we're trying to
learn a single model. Single state PGM
163
00:15:04,182 --> 00:15:08,912
model for multiple different tasks.
Whereas traditional learning algorithms
164
00:15:08,912 --> 00:15:14,146
you learn a particular x y mapping, here
you can learn a single graphical model and
165
00:15:14,146 --> 00:15:19,129
use it in multiple different ways for
answering different kinds of queries. And
166
00:15:19,129 --> 00:15:24,616
finally the idea of using learning for
knowledge discovery is useful in other is
167
00:15:24,616 --> 00:15:29,535
also possible in the context of other
learning algorithms but is particularly
168
00:15:29,535 --> 00:15:34,139
useful in the context of PGMs because the
form of the knowledge is often
169
00:15:34,139 --> 00:15:35,653
particularity intuitive.