Having defined a set of structure scoring criteria, we now turn to the problem of
trying to optimize that structure score over a set of possible candidate
structures. And we're first going to consider the specific case of trees. So
just as a reminder, we define a scoring function that evaluates how well a
structure matches the data. So here is a set of different structures and here is a
graphical depiction of our score and we would like to search for structure that
maximizes the score. Now this is an optimization problem, and where the input
is a tray, is a training set, a scoring function and is possible structures and
the output is a network. Then it turns out that absolutely the key property, for, of
computational efficiency is, the composability of the score, which is, the
decomposition of the score as a sum of family scores, which we've seen before.
So, the first problem that we're going to focus on is that of learning, either a
tree or a forest. So what is, what is a forest. A forest is at most one parent per
variable. So here for example, is. One-fourth, and notice that a fourth
doesn't have to be connected. That is, it can be separate disconnected components. A
tree, on the other hand, would require that the graph be connected, so we might
have this edge, for example, as well. And notice that it's, a still [inaudible]
tree. So why should we care about learning trees given trees are degenerate, so a,
you know, they're so restricted in their expressive power. Well there are reasons,
there are different types of reasons why we like trees. First of all it tunes out
that the math is very elegant. Now that might not be a convincing reason, but that
elegant math give rise to what turns out to be a very efficient optimization over
the set of trees, that allows me to solve it extremely effectively, even for very
high dimensional, problems. The, and then finally, the third reason is that trees
are limited expressive power but that also implies that their parameterization is
very sparse. And because their parameterization is sparse, it means
they're less susceptible to over fitting. And therefore, at least in cases where M
is small relative to the network complexity. [inaudible] To M. Then it
turns out that it can provide better generalization, even though it doesn't
capture the full expressive power that we would hope to have in our network. So,
let's not talk about the problem of learning forth and we're going to define a
little bit of notation. We're going to define P of I for variable I to be the
parent of xi or zero in case xi has no parent. So note that each variable has at
most one parent so this works. So, let's look at our decompo-, composable score,
and again, this can be any of the three scores that we talked about because, they
all have this property. So, the score is the sum of score of individual families XI
and their parents. And, now, the parents are very simple because we have only most
one parent per variable. So, we're going to divide this into two cases. The first
case is nodes that have a parent and the second one is nodes that don't. And so for
the nodes that have a parent, what we have is the score of XI given its one parent,
and for the nodes that don't have parent, it?s just the score of XI as a stand-alone
variable. And now we're gonna shuffle things around a little bit, and we're
going to do the following. We're going to introduce into this expression a score of
x I and then we're going to add it back in. Over here. So now we have a sum of all
variables, so noted this is I equals one to N, of a score of XI in isolation. But
for the XI's that have a parent I've subtracted that off in the first
summation, and so I've compensated for them both sides. The important property of
this expression is that this is the same for all trees. And so it doesn't affect
the comparison between one tree and the other, and so the only the only expression
that I need to consider when comparing, two trees, is this expression over here,
which is the sum over I, of the score of X-I with its parents minus the score of
X-I without its parents. So you can think of this as the score of the empty network
and this the first, and the first expression the first tonation is the
improvement that a tree gives me over the empty network. And so the square now
turned into a sum of S square where each of these is a square of an edge from PI
Why. Plus a constant that doesn't affect the selection of the net words. And that
turns out to be the critical piece for doing the optimization efficiently. So,
let's see how this all works out. So first of all we can define the weight of an edge
from I to j to be the score of xj with it's parent xi minus the score of xj. This
is exactly the term that we saw on the previous slide in the first of the two
summations. Now, for the likelihood score, if we go back and plug in the likelihood
score, we can see that this weight turns out to be M times the neutral information
between I and J. The extent to which they are correlated with each other. And
because mutual information is always non-negative, it means that all edge
weights are always non-negative. And that means that the optimal structure is always
a tree. That is there is always benefit, or at least there is no penalty, for
including additional edges. For BIC or BDE, we know that there is a penalty
score. So even if introducing an edge from XJ to XI, increases the likelihood we
might end paying for it more in the penalty score than what we gain. And so
the weight, this weight, can actually be negative. At which point, the optimal
structure might actually be a forest. That is, it might be detrimental to our overall
score, to make the graph full connected. [inaudible] mostly [inaudible] graph
connected. That is, a tree rather than a forest. Okay. Now, a second observation. A
score? Remember satisfied score equivalent is the property that define, we define
before if I could structure have the same score. And all the score that we talk
about are score equivalent. And turns out that, for score equivalent score we can
show that the weight from I to j is equal to the weight from j to i. That is, you
should compute this expression over here. For j to I or for I to j we're gonna get
the exact same value. And you can see that in the likelihood score directly, because
mutual information doesn't have any kind of directionality associated with it. The
mutual information of x I to x j is the same as mutual information from x j to x
i. So for likelihood score you could just see that. And it turns out that for the
other cases, it's also it also follows. And so that means that we can define an
undirected graph where it doesn't really matter whether I go from I to J or from J
to I, and because the weight is the same for both. And so four score equivalent
scores, we therefore get the following rhythm. We can define an undirected graph
with nodes being the variables in my graphical model. And then I define a
weight W, I, J to be the max of the score X, I between X, I and X, J and zero. And
remember that it doesn't matter whether I do I, J, J, I here wouldn't get the exact
same thing for score for that networks. The zero is going to be a way of
eliminating negative edges so that I can optimize things efficiently without having
to worry about negative edge costs. Now I can go ahead and find a forest or tree
that has the maximal weight. And in, and the nice thing is it turns out that you
could use any of the standard algorithms for maximal weight spanning trees in order
to do this. So, for example, either Prim's or Kruskal's algorithm can be used to
solve this. And we can in fact explain the solution in time that is O of n squared,
which is an inevitable cost given that I'm considering all unsquared combinations in,
in terms of pairs of edges. And then if I end up having edges of weight zero, that
indicates that the edge there potentially contribute with the right from a negative
component of the scores, I remove all of the edges whose weight is zero to produce
a force and that is an [inaudible] and square time algorithm for finding the
absolutely optimal tree relative to any of these three scores, [inaudible] scores
that we've defined. So let's look an example. This is the ICU alarm network
again. This is a picture of the original of the original network and if we apply
this tree-learning algorithm, we end up with the following structure. Where the
edges that have been marked in red are edges that existed in the original
network, and the blue ones are edges that are [inaudible], that is they weren't in
the original network. So this blue one over here, for example, isn't in the
original network. And so we see that although many most even of the edges that
we end up with are edges in original network. Some aren't, some are derived
from correlation that went through indirect path in the original network. And
the other thing that's important to see, looking at this, is that the inferred
edges in the tree are intrinsically undirected. It doesn't mean that I can't
force a direction on them. But the direction isn't determined by my
optimization algorithm. And that means that I'm not able to determine what came
before what in the original graph when I'm learning the tree. So to summarize,
structured learning is an optimization problem over the inventorial set of, space
of graphs. The decomposability property allows me to break that up as a sole term
for the families and that allows me to optimize in the specific case of tree
structured networks using standard maximal wave standing tree algorithm every
efficiently in quadratic.