>> Okay Michael, so what I'm going to do, I'm going to step through how
you find dependency trees and just stop me if it doesn't make any sense, okay?
>> Sure.
>> But hopefully it's fairly straightforward, at
least if you understand information theory. And
again I want to stress that although
we're going to, we're going to spend some time doing
this, this is just one example of
ways that you could represent a probability distribution.
It's just going to turn out that
this one is particularly easy and powerful, okay?
>> Exciting.
>> Okay, so the first thing we have to remember, Michael,
is that we have some true probability distribution which I'm just going
to write as P, that we're trying to do. That's our P
soup theta in this case. But the general question of how you
represent a dependency tree doesn't depend on theta or anything else, there's
just some underlying distribution we care about, let's call that P. Okay.
And we're going to estimate it with another distribution which I'm going
to represent as p-hat because, you know, for approximation. That's going to
depend upon that parent function that we defined before. Okay?
>> Alright.
>> So somehow. You sound skeptical, Michael.
>> Well, because I saw that you wrote those train tracks.
>> And you figure they must mean something?
>> Well I know they mean something. It's a,
it's an information theory thing but I'm not going to
remember what it is. You're going to, it's going to,
you're going to say something like kl divergence or something.
>> That's exactly right. So, somehow we want
to not just find a p-hat sub theta,
that is a dependency tree that represents the underlying
distribution, but we want to find the best one. And
so best one here sort of means closest one,
or most similar, or the one that would generate the
points in the best possible way. And it turns
out, for those who remember information theory, that there's actually
a particular measure for that and it's called the KL
Divergence. You remember what the KL Divergence stands for, Michael?
>> Kullback Leibler
>> That's right. And it has a particular
form and in this case noncontinuous variables. It
has basically this form. And that's basically a
measure of the divergence, that's what the D stands
for, the divergence between the underlying distribution P
that we care about and some other candidate distribution
P-hat that we're trying to get as close
as possible. So if these are the same distributions,
if P-hat and P are the same
distribution, the Kullback–Leibler divergence is equal to zero.
>> Mm. Mm-hm.
>> And as they differ or as they diverge this number gets larger and larger.
Now it turns out that these numbers are unitless. They don't obey the triangle
inequality. This is not a distance. This is truly a divergence. But if we
can get this number to be minimized, then we know we have found a distribution
P-hat, that is as close as we can get to P, okay? And
we have a whole unit that Pushcar will do to remind everybody about information
theory where this comes from. But basically this is the right way to define
similarity between probability distributions. You just have
to kind of take that on faith.
>> Okay. Well, I'll, I'll pause this and go back and
listen to Pushcar's lecture and then I'll be ready for you.
>> Okay, beautiful. Okay. So what we really want to do is we want
to minimize the Kullback–Leibler divergence the that is minimize the
difference between the distribution that we're going to estimate with
a dependency tree and the true underlying distribution. And just
by doing some algebra, you end up getting down to
what looks like a fairly simple function. So Michael, if
you were, if you were paying close attention to the
algebra, you will realize that well p log p, now
that you've come back from Pushcar's lecture is just entropy.
>> Yep.
>> So or it's minus the entropy. And so
I can rewrite this as simply minus the entropy
of the underlying distribution, plus the sum of the
conditional entropies, for each of the Xis, given its parent.
Which has some, you know, sort of intuitive niceness
do it, but, whatever. This is what you end
up with just by doing the substitution. P log
P gives you minus entropy of P minus P log
P hat, which gives you the conditional entropy according
to the function, the parent function pi. Okay. Well,
in the end all we care about is finding
the best pi. So, this term doesn't matter at all
and so we end up with a kind of
cost function that we would like to minimize. Which I'm
going to call here J. Which depends upon pi
which is just the sum of all the conditional entropies.
Basically the best tree that we can find
will be the one that minimizes all of the
entropy for each of the features, given its
parents. Does that make any intuitive sense to you?
>> Yeah. I think so. Cause we want, we want to choose parents that are
going to give us a lot of
information about the values of the corresponding features.