YouSub
Untitled

en English

Untitled English subtitles

0 downloads · 942 lines · added Nov 18, 2015

Report a problem
What's wrong?
Advertisement

English transcript

PROFESSOR PATRICK WINSTON: I was in Washington for most of
the week prospecting for gold.
Another byproduct of that was that I forgot to arrange a
substitute Bob Berwick for the Thursday recitations.
I shall probably go to hell for this.
In any event, we have many explanations,
none of them good.
But today we'll try to get back on track and you'll learn
something fun.
In particular you will learn how a graduate student of mine
Mark [? Phillipson ?], together with a summer UROP
student, Brett van Zuiden, one of you--
managed to pull off a tour de force and recognize in these
two descriptions the pattern that we humans commonly call
"revenge." It was discovered.
The system didn't have a name for it, of course.
It just knew that there was a pattern there and sat waiting
for us to give a name to it.
That's where we're going to end up.
But it'll be a bit of a journey before we get there,
because we've got to go through all that
stuff on the outline.
And in particular, we want to start off by a
little tiny bit of review.
Because some of the stuff we did last time
went by pretty fast.
In particular, you may remember they had this
wonderful joint probability table, which tells us all we
want to know, all we want to know.
We can decide what the probability of the police
being called is given the this and the that, and all that
sort of stuff, by clicking the appropriate boxes.
The trouble is, gee, there are only three variables there.
And when there are lots of variables it gets pretty hard
to make up those numbers or to even collect them.
So we're driven to an alternative.
And we got to that alternative just at the end of
the show a week ago.
And we got to the point where we were defining these
inference nets, sometimes called "Bayes nets." And the
one we worked with looked like this.
There's a burglar, a raccoon, the possibility of a dog
barking, the police being called, and a trash can being
overturned.
So more variables than that.
That only has three.
This has got five.
But we're able to do some magic with this because we, as
humans, when we define--
when we draw this graph we're making an assertion about how
things depend or don't depend on one another.
In particular, there's something to break down and
memorize to the point where it rolls off your tongue.
And that is that any variable on this graph is said by me to
be independent of any other
non-descendant given its parents.
Independent of any
non-descendant given its parents.
So that means that the probability of the dog
barking, given its parents, doesn't depend on T, the trash
can being overturned.
Because the intuition is all of the causality is flowing
through the parents and can't get to this variable D without
going through the parents.
So that is [? inserted ?]
property of the nets that we draw.
And we tend to draw them in a way that reflects causality.
So it tends to make sense.
So somehow this thing is going to be--
we're going to use this thing instead of that thing.
But wait.
We may need that thing in order to do all the
computations we want to perform.
So we need to be able to show that we can get to that thing
by doing calculations on this thing.
So what to do?
Well, we're going to use the chain rule.
And remember that the chain rule came to us by way of the
basic Axioms of Probability plus the definition plus a
little colored chalk.
So we got to the point last time where we
sort of believed this.
It's a really magical thing.
It says that the probability of all this stuff happening
together is given as the product of a bunch of
conditional probabilities.
And the conditional probabilities in this product
are arranged such that this first guy depends
on everybody else.
The second guy doesn't depend on the first guy but depends
on everything else.
So that list of dependencies gets smaller and smaller as
you go down here until it depends only one thing.
There's no conditional at all.
So that's going to come to our rescue because it enables us
to go from calculations in here to that whole table.
But first I have to show you a little bit more slowly how
that comes to be.
One thing I'm going to do before I think about
probability is I'm going to make a linear list of all
these variables.
And the way I'm going to make it is I'm going to chew away
at those variables from the bottom.
I've taken advantage of a very important
property of these nets.
And that is there no loops.
You can follow the arrows in any way so as
you get back to yourself.
So there's always going to be a bottom.
So what I'm going to do is I'm going to say, well, there are
two bottoms here, there's C and T. So I have a choice.
I'm going to choose C. So I'm going to take that off and
pretend it's not there anymore.
Then I'm going to take this guy.
That's now a bottom because there's nothing below it.
I've already taken C out.
So we'll take that out next.
And now I've got this guy, this guy, and this guy.
This guy no longer has anything below it.
So I can list it next.
Now over here I've got raccoon and trashcan.
But trashcan is at the bottom.
So I've got to take it next because I'm working
from the bottom up.
I want to ensure that there are no descendants before me
in this list.
So finally I get to raccoon.
So the way I constructed this list like so ensures that this
list arranges the elements so that for any particular
element, none of its descendants
appear to its left.
And now that's the magical order for which I want to use
the chain rule.
So now I can write--
I can pick C to be my variable n.
And I can say that the chain rule says that the joint
probability of all these variables P of C,
D, B, T, and R--
the probability of any particular combination of
those things is equal to the probability of C given
everybody else.
Next in line is D given everybody else.
Next in line is T--
next in line is B given everybody else.
And next in line is T given everybody else.
And finally, just R. So this combination of things has a
probability that is given by this chain rule expression.
Ah.
But first of all, none of those expressions condition
any of the variables on anything other than
non-descendants, all right?
That's just because of the way I've arranged the variables.
And I can always do that because are no loops.
I can always chew away at the bottom.
That ensures that whenever I write a variable, it's going
to be conditioned on stuff other than its descendants.
So all of these variables in any of these conditional
probabilities are non-descendants.
Oh wait.
When I drew this diagram, I asserted that no variable
depends on any non-descendant given its parents.
So if I know the parents of a variable I know that the
variable is independent of all other non-descendants.
All right?
Now I can start scratching stuff out.
Well, let's see.
I know that C, from my diagram, has only one parent,
D. So given its parent, it's independent of all other
non-descendants.
So I can scratch them out.
D he has two parents, B and R. But given that, I can scratch
out any other non-descendant.
B is conditional on T and R. Ah, but B has no parent.
So it actually is independent of those two guys.
The trashcan, yeah, that's dependent on R. And R over
here, the final thing in the chain, that's just a
probability.
So now I have a way of calculating any entry in that
table because any entry in that table is going to be some
combination of values for all those variables.
Voila.
So anything I can do with a table, I can do in principle
with this little network.
OK?
But now the question is, I've got some probabilities I'm
going to have to figure out here.
So let me draw a slightly different version of it.
So up here we've got the a priori probability of B. Well,
that's just probability of B. Down here with the dog, I've
got a bigger table because I've got probabilities that
depend on the values of its parents.
The probability of dog barking depends on the condition of
the parents, nothing else.
So let's see.
I've got to have a column for B. I've got to have a column
for the burglar and the raccoon.
And there are a bunch of possibilities for those guys.
But once I get those then I'll be able to calculate the
probability of the dog barking.
So there are two of these variables.
So there are four combinations.
There's T T. There's T R, R T, and--
whoa, what am I doing?
Wake up!
T false.
False true.
And false false.
So what I really want to do is I want to calculate all of
these probabilities that give the probability of the dog
condition of the burglar and the raccoon.
Similarly, I want to calculate the probability of B happening
doesn't depend on anything else.
So I don't know what to do.
Well, what I'm going to actually do is I'm going to do
the same thing I had to do up there.
I'm going to keep track of--
I'm going to try a bunch of--
I'm going to get myself together a bunch of data.
Maybe I do a bunch of experiments.
Maybe somebody hands it to me.
But I'm going to use that data to construct a bunch of
tallies which are going to end up giving me the probabilities
for all of those things.
So I don't know, let's see.
How should we start?
Step one, find colored chalk.
Step two, I'm going to extend these tables a little bit so I
can keep track of the tallies.
So this is going to be all the ones that end up in a
particular row.
And these are going to be the ones for which dog is true.
Similarly, I'm going to extend this guy up here in order to
keep track of some tallies.
This is going to be the ones for which B is true.
And this one will be all.
So that's my set up.
And now suppose that my first experiment comes roaring in.
And it's all T's.
So I have T T T. That's my first experimental result, my
first data item.
So let's see.
The arrangement here is burglar, raccoon, dog.
So burglar as a true.
And there's one tally count in there.
Likewise, the T T, that's the burglar and the raccoon, that
brings me down to this first row.
So that gives me one tally in there and dog is true so that
gives me a tick mark in that one.
All right?
Are you with me so far?
And now let's suppose that the next thing
happens be all false.
Well, burglar is false.
But there is one experiment.
Everybody's false.
So we come down here to false false.
And that's the row we're going to work on.
We get a tally in there.
Do we put one in here?
No, because that's false.
Dog is false.
That's what our data element says.
So that's cool.
Maybe one more.
Let's suppose we have T T F. Well in that case, we have a
tick mark here and a tick mark here because the burglar
element is true.
Then we have T T. That brings us to the first row again.
So we get a tick mark there.
But dog as false, so no tick mark there.
That's how it works.
I suppose you'd like to see a demonstration, right?
Always like to see a demonstration.
So here's what it actually looks like.
So on the left you see the network as we've constructed
it, with a bunch probabilities there.
And what I'm going to do now is I'm going to start
simulating away so as to accumulate tick marks, tally
marks, and see what kinds of probabilities that they
indicate for the table.
I happen to be using a process for which the model on the
left is a correct reflection.
So there's one simulation.
So the dog barking--
let's see, the burglar is false.
The raccoon is true.
I get one tick mark.
So the probability there is one.
Of course, I'm not going to just go with one.
I want to put a whole bunch of stuff in there.
So I'll just run a bunch more simulations.
No [? dice. ?]
I don't even have an entry at all yet for T F here.
That's because I haven't run enough data.
So let me clear it instead of doing it one at a time.
Let me run 100 simulations.
See, it's still not too good.
Because it says this T T probability true.
This just because I'm feeding it data, right?
And I'm keeping track of what the data elements tell me
about how frequently a
particular combination appears.
Yes, [INAUDIBLE]
STUDENT: So when you're doing one simulation, is that
[INAUDIBLE] variables?
PROFESSOR PATRICK WINSTON: When I'm doing one simulation,
I'm just keeping track of that combination in
each of these tables.
Because it's going to tell me something about the
probabilities that I want reflected in those tables.
So it's pretty easy to see when I go up here to burglar.
If I have a lot of data elements, they're all going to
tell me something about the burglar as well
as the other variables.
So if I just look at that burglar thing, the fraction of
time that it turns out true over all the data elements is
going to be its probability.
So now when I go down to the joint tables, I can still get
these probability numbers.
But now they're conditioned on reticular
condition of its parents.
So that's how I get these probabilities.
So I didn't do too well here because that T T combination
gave me an excessively high probability.
So maybe 100 simulations isn't enough.
Let's run 10,000.
So with that much data running through, the probabilities I
get-- let's see, I've got 893 here, instead of 0.9, 807
instead of 0.8, 607 instead of 0.6.
And that one's dead-on at 0.01.
So if I run enough of these simulations, I get a pretty
good idea what the probabilities ought to be
given that I've got a correct model.
OK, so that takes care of that one.
And of course, I didn't draw the other things in here.
But by extension, you can see how those would work.
Oh.
But you know what?
I think I will put a little probability of
raccoon table in here.
Because the next thing I want to do is I want to
go the other way.
This is recoding tallies from some process so I
can develop a model.
But once I've got these probabilities, of course, then
I can start to simulate what the model would do.
All right?
How would I do that?
Well, do I want to use the same table?
I think just to keep things sanitary, what I'll do is I'll
go over here and do it again.
Here's B. It's got a probability of B. Here's R.
Here's a table probability of R. That comes down into a
joint table for dog.
And it's got four elements.
Depending on the burglar condition and the raccoon
condition, we get a probability of dog.
And now, imagine these have all been filled in.
So what do I want to do if I want to simulate this system
generating some combination of values for all the variables?
Well, I do the opposite of what I did when I was working
around with this chain rule showing that I could go from
the table to those probabilities.
Now I've got the probabilities.
I'm going to go the other direction.
Instead of chewing away from the bottom, I'm going to chew
away from the top.
Because when I go into the top and chew way, everything I
need to know to do a coin flip is there.
So in particular, when I go up in here, I've got the
probability of burglar now.
So I'm going to use that probability to flip a coin.
Say it produces a T. So that takes care of this guy.
And I can now scratch it off since it's no longer in
consideration.
It's no longer a top variable.
So now I go over into raccoon and I do the same thing.
I take this probability.
I do a flip.
And say it produces an F. Whatever its probability is, I
flip a biased coin and that's what I happen to get.
But now, having dealt with these two guys, that uncovers
this dog thing.
And I've got enough information, because I've done
everything above, to make the calculation for whether to dog
is going to be barking or not.
But wait.
I have to know that I've got a T and a T and a T and an F and
an F and a T and an F and an F. Because I have to select
the right row.
So I know that B is T. And I know that R is F. So that
takes me into the table into the second row.
So now I get this probability.
I flip that coin and I get some result, say, T. Voila.
I can do that with the other two variables.
And I've got myself an experimental trial that is
produced in accordance with the
probabilities of the table.
OK?
Of course--
yeah, in fact, how did I get those numbers?
Actually what I did is I used the model on the left to
generate the samples that were used to compute the
probabilities on the right.
So you've seen that a demonstration of this already.
Now of course--
I don't know, all of this sort of depends on having
everything right.
I've written a thing to write it one more time.
Burglar, raccoon, dog, call the police, trashcan.
But somebody else may say, oh, you've got it all wrong.
This is what it really looks like.
The dog doesn't care about the raccoon at all.
So that's a correct model.
Now when I do a simulation, I could fill in the tables in
either model, right?
I'm sure you'd like to see a demonstration.
So let me show you a demonstration of that.
So there are the two tables.
And I can run 10,000 simulations
on those guys, too.
Now, look.
The guy on the left is a pretty good reflection of the
probabilities in a model I used to produce the data.
But the guy on the right doesn't know any better. it
just fills in its own tables, too.
So what to do?
I say this one's the right model.
And you say that one's the right model.
Who's right?
Maybe we'll never know.
And the guy on the left will get rich in the stock market
and the guy on the right will go broke.
I would be nice if we could actually
figure out who's right.
So would you to see how to figure out who's right?
Yeah, so would I. What we're going to do is we're going to
look at naive Bayesian inference.
And that's our next chore.
So here's how it works.
We know, from the definition of conditional probability, we
know that the probability of A given B is equal to the
probability of A and B divided by the
probability of B, right?
Equal to by definition.
So that means that the probability of A given B times
the probability of B--
I'm just multiplying it out--
it equal to that joint probability.
Oh, but by symmetry, there's no harm in saying I can turn
that around and say that the probability of B given A times
the probability of B is also equal to that joint
probability, right?
I've just expanded it a different and symmetric way.
If I've got to write a, b on B, b, a on A. Thank you.
Who was complaining?
Good work.
That would have been a major-league disaster.
But now, having written that, I can forget about the middle.
Because all I'm really interested in is how I've
turned the probabilities around in that conditional.
Why would I care about doing that?
By the way, we're now talking about the work of
the Reverend Bayes.
Because we can rewrite this yet again as the probability
of A given B is equal to the probability of B given A times
the probability of A divided by the probability of B.
That's just elementary algebra.
But now I'm going to do something magical.
I'm going to say I've got a classification problem.
I want to know which disease you have.
That's a classification problem.
Maybe you've got the swine flu.
Maybe you've got indigestion.
Who knows.
But I get all these symptoms.
I get all these pieces of evidence.
You've got a fever.
You're throwing--
oh, well, let's not go into too much detail, there.
But what I'm going to do is I'm going to say, well, let's
suppose that A is equal to a class that I'm interested in,
the disease you've got.
And B is equal to the evidence,
the symptoms I observe.
Voila.
I may have a pretty hard time figuring out what the
probability of the class is given the evidence.
But figuring out the probability of the evidence
given the class might not be so hard.
Let me get another board in play and show you what I mean.
By plugging class and evidence into Bayes' rule, what I get
is the probability of some class given the evidence is
equal to the probability of the evidence given the class
times the probability of the class divided by the
probability of the evidence.
Now you've got to let that sing to you a little bit.
Suppose I've got several classes that I'm trying to
decide between.
I'm trying to select the best out of that batch of classes.
Well, I've got the evidence.
And if I know the probability of the evidence given each of
those classes, and if I know, a priori, the initial
probability the class, then I'm done.
Because I'
…

Need subtitles from another video?