1
00:00:00,000 --> 00:00:04,204
We previously discussed the problem of
learning the parameters of a Bayesian

2
00:00:04,204 --> 00:00:08,463
network whose structure was given to us.
But that might not always be the case.

3
00:00:08,463 --> 00:00:12,504
It's not always the case that we have a
domain expert, who understands the

4
00:00:12,504 --> 00:00:16,381
structure of the domain, of the
relationship between the variables well

5
00:00:16,381 --> 00:00:20,586
enough to write down a network that we
think is good enough. So what are some

6
00:00:20,586 --> 00:00:25,391
cases where this might happen? The first
is, when we actually want to use a network

7
00:00:25,391 --> 00:00:29,651
for answering new queries of whatever
kind, for example. New medical queries in

8
00:00:29,651 --> 00:00:34,338
a, in a medical domain, or, Before other
settings. So in this case we might, it

9
00:00:34,338 --> 00:00:38,987
might still be the case that although
there might be some domain expertise it

10
00:00:38,987 --> 00:00:43,933
might not be sufficient to come up with a
model good enough to use and we might do

11
00:00:43,933 --> 00:00:48,403
better by taking data and actually
learning the dependencies that the data

12
00:00:48,403 --> 00:00:53,475
tell us are the most significant. A second
setting where this might happen is where

13
00:00:53,475 --> 00:00:58,396
we don't necessarily even care about using
the network, we just want to discover the

14
00:00:58,396 --> 00:01:02,556
network. And, this kind of use model
occurs for example in scientific or

15
00:01:02,907 --> 00:01:06,832
biological data sets for example. Where
the goal is to discover the

16
00:01:06,832 --> 00:01:11,519
inter-relationships between the variables
just so that we understand the domain

17
00:01:11,519 --> 00:01:16,142
better. So lets focus for a moment on the
first of these two cases. Where our goal

18
00:01:16,142 --> 00:01:20,695
is to use, is to learn a network of the
purpose of using it. And let's think about

19
00:01:20,695 --> 00:01:25,591
the kind of mistakes that might happen and
how they affect the ability of the network

20
00:01:25,591 --> 00:01:30,031
to apply well to new instances. So let's
imagine that the network, that the true

21
00:01:30,031 --> 00:01:34,527
network is this one over here. And now
lets consider different kind of mistakes

22
00:01:34,527 --> 00:01:38,853
that a learning algorithm might make. So
in one case for example the ler, the

23
00:01:38,853 --> 00:01:43,439
learning algorithm might learn a network
that's missing an arc. On the other hand,

24
00:01:43,439 --> 00:01:47,825
it might learn, a network, to which we've
added an arc, and now of course one can

25
00:01:47,825 --> 00:01:52,211
also have cases where we have a bit of
each, but let's think about these two

26
00:01:52,211 --> 00:01:56,723
types of errors separately. If we're
missing an arc. Effectively the

27
00:01:56,723 --> 00:02:02,607
independencies, that the network. That the
learned network tells us is incorrect. That

28
00:02:02,607 --> 00:02:08,348
is relative to the ground truth network
which is this one. Which if you remember,

29
00:02:08,348 --> 00:02:13,299
we call it g star. The network in, the
network that we learn is making

30
00:02:13,299 --> 00:02:19,276
independence assumptions that are not
correct relative to g star. Conversely, in

31
00:02:19,276 --> 00:02:26,417
this case, we have spurious dependencies,
that is in when we have added an arc there

32
00:02:26,417 --> 00:02:32,383
is a spurious dependency, in this case
between a and b. Now, what are the

33
00:02:32,383 --> 00:02:39,357
implications of this? If we're missing an
arc, then the correct distributions p star

34
00:02:39,357 --> 00:02:45,490
cannot be learned. That is, there is no
way in general if, if p star was

35
00:02:45,742 --> 00:02:54,614
associated with this network over here,
that is g star is a perfect map. For P

36
00:02:54,614 --> 00:03:00,951
star. Then we can't learn P star using a
network that's missing an edge. Now that

37
00:03:00,951 --> 00:03:06,735
might seem like a very bad idea and we
would prefer perhaps the error model on

38
00:03:06,735 --> 00:03:12,153
the right which, even though it has these
excess edges, it does allow us to

39
00:03:12,153 --> 00:03:17,864
correctly learn P star. That is, this
additional edge over here between A and B,

40
00:03:17,864 --> 00:03:23,941
there is a setting of the parameters for
which the correct distribution P star can

41
00:03:23,941 --> 00:03:29,232
still be Estimated on this network
structure. So it might seem that this

42
00:03:29,232 --> 00:03:34,092
error model is actually, error mode is
actually better than the one where we were

43
00:03:34,092 --> 00:03:38,662
missing an arc. But, empirically that
actually turns out to be an oversimplified

44
00:03:38,662 --> 00:03:43,291
view. Specifically, the model where we
have excess arcs gives rise to an increase

45
00:03:43,291 --> 00:03:48,151
in the number of parameters, and the more
parameters we have to elicit the harder it

46
00:03:48,151 --> 00:03:52,490
is to elicit them correctly given the
limited amount of data. We've already

47
00:03:52,490 --> 00:03:56,945
talked about this when we talked about
fragmentation as the number of, of the

48
00:03:56,945 --> 00:04:02,107
data as the number of parents increases.
And so, one of the important conclusions

49
00:04:02,107 --> 00:04:06,947
from this, is that this, as we've already
seen, can give rise to worse

50
00:04:06,947 --> 00:04:12,071
generalization, which means worse
performance on unseen instances. And so

51
00:04:12,071 --> 00:04:17,694
the fact is, that sometimes, having fewer
edges could actually generalize better

52
00:04:17,694 --> 00:04:23,460
than having, more edges, even though the
correct distribution cannot be encoded.

53
00:04:23,460 --> 00:04:29,406
And so the trade offs between missing arcs
and extra arcs are subtle and it's not

54
00:04:29,406 --> 00:04:34,699
always clear which, which is the right,
which is going to give us the best

55
00:04:34,699 --> 00:04:40,295
performance. So without introduction, what
is the way in which we typically learn

56
00:04:40,295 --> 00:04:45,677
Bayesian network structure from data?
The general paradigm which we will

57
00:04:45,677 --> 00:04:51,321
refine in subsequent parts of this of this
segment of course is that we define the

58
00:04:51,321 --> 00:04:56,769
scoring function that evaluates for each
structure how well that structure matches

59
00:04:56,769 --> 00:05:02,085
the data. So here we have a dataset D,
and we have in this case, three example

60
00:05:02,085 --> 00:05:07,013
network structures and we're going to
define a scoring functions that. That

61
00:05:07,013 --> 00:05:12,057
tells us for each of these network
structures, how good. It is, relative to

62
00:05:12,057 --> 00:05:18,546
the data that we've seen. And then we have
the goal of searching for a network

63
00:05:18,546 --> 00:05:25,626
structure that maximizes the score and so
we have now turned the learning problem

64
00:05:25,626 --> 00:05:30,819
into an optimization problem. Is an
optimization over combinatorial space,

65
00:05:30,819 --> 00:05:34,997
the space of network structures, and by
defining a score that give us the

66
00:05:34,997 --> 00:05:39,346
objective that we are trying to optimize,
and now we need to come up with an

67
00:05:39,346 --> 00:05:43,925
algorithm that optimizes that score. So,
we've separated this out into the score

68
00:05:43,925 --> 00:05:48,675
component and the optimization component,
and we talk separately about each of this

69
00:05:48,675 --> 00:05:49,820
in subsequent parts.