YouSub
Untitled

en English

Untitled English subtitles

0 downloads · 1,081 lines · added Nov 18, 2015

Report a problem
What's wrong?
Advertisement

English transcript

The following content is provided under a Creative
Commons license.
Your support will help MIT OpenCourseWare
continue to offer high quality educational resources for free.
To make a donation or view additional materials
from hundreds of MIT courses, visit MIT OpenCourseWare
at ocw.mit.edu.
MARK SEIFTER: Hi, everyone.
A few of you may know me from my tutorial,
but if you don't I'm Mark Seifter I'm the senior TA here
at 6034 and these Friday omega recitations are going
to be a little bit different than any
of the other things in the class.
All right, so, what is omega recitation.
Omega recitation is in this lecture style room,
but I hope to make it more like a recitation or a tutorial
by, unfortunately for some of you,
perhaps, calling on you guys to participate during the omega
recitation, as we attempt to work with some of the material
that Patrick has given us the big picture
for in the lectures.
And if you've gone to recitation so far
you may received a little bit of enrichment
into how the algorithms work.
Well, here in omega recitation we're
going to figure out how you can work the algorithms.
And that's very important, because in this class being
able to work the algorithms by hand in some of these examples
I put up here, or like Patrick sometimes
does in lectures to teach you the algorithms,
is a crucial way of demonstrating
that you understand how the algorithms work, and we use it
on a quiz.
The way we use it on the quiz is we-- well
this is an old quiz problem.
It's from last year.
It tripped up a lot of people.
So we're going to go over it today.
I'm going to tell you all the tricks that tripped up
a lot of people, in addition to emphasizing tricks
that I've picked up over of the three years of TA-ing
this course before, so that you will not fall prey
to any of these tricks.
Hopefully.
I say hopefully, because some of these tricks
I talked about omega recitation last year
and people still got tricked by them.
I guess maybe some people didn't come to omega recitation
or they were just very tricky tricks.
So be sure to come to omega recitation.
Pay attention to the tricks.
Pay attention to how these things are solved.
Ask questions if you're not sure.
And when we get done with the hour
together I'm hoping that everyone's
going to do really well on the rules part of the first quiz.
So without further ado, if there are
no questions on that, which I don't think there probably
will be, let's move on to the problem at hand.
As some of you may have noticed, it
is a Harry Potter based problem.
One of our TAs last year was a big Harry Potter fan.
So what we have here a series of rules
and a series of assertions.
Now if you happen to be real go getter and have already looked
at all the past quizzes online, you
may have already seen this problem.
And if you really, really have attention to detail
you may notice something a little bit different in the way
I wrote it as compared to the way it was written online.
In fact, you may, if you have a lot of times a detail,
but you're not really in on Scheme or LISP,
you may think the way I wrote it is much easier to understand.
And in case you can't understand the other way,
and in case one of the TAs decides
to write it in a LISP-like way again, let me explain.
If you look at one of my rules, say if x is ambitious,
and x is a squib, then x has a bad term.
That's rule 0 up at the top.
That's written in sort of what we call in fixed notation.
It's easy, it's simple.
All operators are in the order you would expect.
2 plus 3 equals 5.
There's another kind of notation that is sometimes
used on previous quizzes.
And by sometimes, good number of times, actually.
I'm not sure why we still use it that way, because of the fact
that the class has move on to Python, but we do, sometimes.
And that's called prefix notation.
In prefix notation, the operator comes first.
So for instance, plus 2 3 equals 5.
The plus comes first.
The function, then, comes first.
In this case, the function is plus.
So if we were writing this in prefix notation, in fact,
the way I received it, when it said, "if and x is ambitious,
x is a squib, then x has a bad term.
The and went first and there's a parentheses
which included everything that was scoped under the and.
Does anyone have any questions about prefix notation
in case it comes up?
Just remember, if things start being written
in a really weird way with lots and lots
and lots of parentheses, whatever's
outside the parentheses, whether it be "plus" or "and"
or "or" is an operator that acts on the things that are inside.
However, we're not going to deal with that now,
because I think the most important thing is
to understand is the rules, and the less important thing
is to understand prefix notation.
And you can do a problem at home that's
written in prefix notation to test yourself on that.
So what rules do we have here.
We've got equals 0 through 5.
For some reason they are labeled with P's.
They are often labeled with either P's or R's.
The secret on why they are labelled with P's is that one
year somebody labeled them with P's for like "proposition"
or something like that.
And then other TAs looked at that test and sometimes also
labeled it with P's and it sort of down the line continued
to be labeled with P's, and sometimes with R's.
So these P's are these six rules.
The first rule is if x is ambitious, and x is a squib,
then x has a bad term.
So what's the deal with these question mark x's?
The question mark before an x, or perhaps a y down here,
indicate that there's a variable waiting to be bound.
We're not assuming there's a Harry Potter character named
x, and only if that question mark x, the mystery character,
only if mystery x character is ambitious can that person
possibly have a bad term.
What we're seeing is any character in the Harry Potter
universe, or not the Harry Potter
universe, maybe a rhinoceros, can fit into that x.
So for instance, if a rhinoceros is ambitious,
and a rhinoceros is a squib, then a rhinoceros has bad term.
That rule saying, for any x this is true.
And it's very important how we treat the question mark
x, and how we bind question mark x,
when we do both back chaining and forward chaining.
I'll get back to that, because some people made some very,
very small mistakes that really messed up
a lot of their forward and backward chaining last year.
It was actually very tricky.
Jeremy, the TA who wrote this was very clever,
and it makes it really great case study for you guys.
All right, so Rule 1, if x lives in Gryffindor tower
then x is a protagonist.
By the way, for conciseness I'm going
to be using GT for Gryffindor tower
when I write these in later on, and I'll
use SD for Slytherin dungeon.
Speaking of which, Rule 2, if x lives in Slytherin dungeon,
then x is a villain, x is ambitious.
Why there are two things here?
Well, after the "if" we have what we call antecedent,
that's something that needs to be true in order for this rule
to match.
After the "then" we have what is called the consequent,
and in this case there are two consequents.
Anyone who lives in Slytherin dungeon
is automatically a villain and also ambitious.
So you can think of there being sort of an "and
therefore" for the purposes of both of those assertions
would be added to the knowledge base.
Rule 3, if x is the protagonist or x is a villain,
and x is ambitious, then x studies a lot.
By the way, the scope for this, just to be sure
that we're clear, is this.
So we need them to be a protagonist
or villain and no matter what they have to be ambitious.
Rule 4, if x studies a lot, and x is a protagonist,
x becomes Hermione's friend.
And Rule 5, if x snogs y, and x lives in Gryffindor tower and y
lives in Slytherin dungeon, then x has a bad term.
So those are our six rules that we
can use to understand Jeremy's world of the Harry Potter
universe.
And we also start off with four assertions.
Let me not underestimate the value of always looking
to the assertions.
It's one of my white star ideas that are up here on the board.
Let me see.
This.
Perfect.
Always check the assertions before using a rule.
This really tripped people up last year, and you'll see why,
because we're doing last year's problem.
Our four assertions that we start.
With assertion 0, Millicent lives in Slytherin dungeon.
Assertion 1, Millicent is ambitious.
Assertion 1 is what tripped people up,
so remember that Millicent is ambitious.
Assertion 2 Seamus lives in Gryffindor tower.
And assertion 3, Seamus snogs Millicent.
So those those are our four assertions
that we've already started with.
Now the two things we're going to have to do
are backward chaining and forward chaining.
Now when you guys learned these two backward chaining
and forward chaining, raise your hand
if thought forward chaining was harder than backward chaining.
I knew it!
I can prove whatever point I want because noone
wants the raise their hand.
I also think backward chaining is higher than forward
chaining.
Raise your hand if you think backward chaining is
higher than forward chaining?
First of all, we have a good number of people.
Second of all, since no one wants to raise their hand,
I could just ask it the other way.
That's a pro tip if you're ever with a large group of people.
You can prove any point you want by asking the other direction.
No one will raise their hand.
So I agree that backward chaining is higher than forward
chaining.
And I disagree with Patrick that we're going to get out early,
so let's start with backward chaining first.
So that we make sure that we spend the bulk of our time
with it.
The forward chaining, well, you just
go through pretty methodically and add new rules.
Backward chaining, you have to draw this crazy tree.
There's a lot of places to get lost in the middle of the road.
So let's do some backward chaining.
And to do that, I'll do it over here on the left side.
So when we're doing backward chaining,
we have to remember a few things that are written directly
on the quiz.
So you're not going to have to worry about that.
But they're still pretty important.
So-- actually, I'll write it on here first.
I'm going to read them off.
So when working on a hypothesis, the backward chainer
tries to find a matching assertion
in the list of assertions first.
If no matching assertion is found,
the backward chainer will try to find a rule
with a matching consequence.
A rule that has something in the then that
can prove the assertion is trying to figure out.
So for instance, if I was doing backward
chaining on Seamus [? Snaus ?] Millicent, what happens?
I'm immediately done because there's
an assertion that's assertion three that says
Seamus [? Snaus ?] Millicent.
I proved it.
I'm done.
I'm happy.
We can leave, we can go home.
Unfortunately, that's not what the quiz asks us to do.
Now, let's say that instead, we were supposed to say,
I don't know, Seamus is a protagonist.
Well then, we'd wind up looking through here
and we would look at the fact that rule one can prove
that someone is a protagonist.
And we'd curse and try to prove whatever
is in the antecedent of rule one, which is, OK, well,
does he live in Gryffinder Tower?
Assertion two, he does.
So that's some really quick.
And if that was too, fast don't worry.
We're going to go step by step with the actual problem.
But I just wanted to give two really easy problems, really
quickly, how it's going to do it.
Let's go step by step with the real problem.
Let's keep in mind, backward chainer
never adds new assertions to the list of assertions.
And if you have a tiebreak, you always
order based on rule order first, P0 through P5.
And if the same rule matches with more than one thing
in your list assertions, then you
tiebreak based on the order of the assertions.
Very important.
Disambiguation and tie-breaking are a big place
to get messed up.
So we're going to try to prove that Millicent
becomes Hermione's friend.
And so I'm going to abbreviate some of the things,
but not for the very first line.
So Millicent becomes Hermione's friend.
We start drawing a goal tree.
Now you guys are going to learn exactly what these mean very
soon, in fact, next lecture.
But for now, trust me when I say these goal trees are depth
first.
And I'll explain what that means because some people have
messed themselves up and spent more time than they needed to
by treating the goal tree in a different way.
Now, Millicent becomes Hermione's friend.
Let's pretend that we are the backward chainer.
We're trying to prove that this is true or disprove
and say, well, it's definitely not true with what we have.
So let's see.
I'm now going to make you guys help.
And people in the back think they won't be called on.
So I often like to call on people in the back.
What do you think is the first thing we should do?
Very first thing?
Yes, look for a matching assertion.
Excellent.
Do we have a matching assertion, everyone?
No, we don't.
That would be the world's easiest quiz problem.
We do not have a matching assertion.
Great.
So, since we don't have a matching assertion, what now?
AUDIENCE: We start to look at the rules.
MARK SEIFTER: That's right.
And do you see any rule that could prove that Millicent
becomes Hermione's friend?
AUDIENCE: P4.
MARK SEIFTER: That's right.
You can see in P4, x, which can be anybody.
Anyone is capable of being Hermione's friend.
Great.
So P4 is our rule of the hour.
So we're going to use P4.
And when we use P4 to prove that Millicent becomes Hermione's
friend, we're going to have to add something
or another to the goal tree.
So let's see.
What do we have to add to the goal tree?
AUDIENCE: We have to see if Millicent
studies a lot [INAUDIBLE].
MARK SEIFTER: That's right.
Does everyone see that?
In order for her to become Hermione's friend,
by rule four, we have to see if she studies a lot
and is a protagonist.
Question?
AUDIENCE: [INAUDIBLE]
MARK SEIFTER: OK, that's a very good question.
You're going to get screwed up if you look at the antecedent
in backward chaining first.
It's backwards partially for a reason.
You need to look at the consequent.
Now why is that?
Well, let's say there is a rule six that
said if x becomes Hermione's friend,
then Hermione feeds x Polyjuice Potion, or something like that.
Will that rule help us in back chaining
to figure out if Millicent becomes Hermione's friend?
AUDIENCE: [INAUDIBLE]
MARK SEIFTER: Some people are shaking their head.
But think about it, will that rule be able to prove it?
No.
Now, if they do become Hermione's friend
and we want to do some forward chaining,
we'll figure out that they're going
to transmute into some kind of other thing because
of the Polyjuice Potion.
But it's not going to help us do the one
thing we want to back chain, which is
to prove that thing on the top.
So we actually need to look for something
that has our current goal in its consequent.
Then we add on the antecedents.
As people I've asked so far-- sorry, I
don't know your names-- like Patrick,
have correctly given me every time, which is excellent.
So notice also that she didn't say
x studies a lot needs to be added to the goal tree.
She said Millicent studies a lot.
Oh, another question.
Great.
AUDIENCE: So obviously after putting rule 4 there,
shouldn't we first check the assertions-- check
on the assertions instead of our conditions [INAUDIBLE]
MARK SEIFTER: So the question is,
once we put rule four in there, should
we check to see if those antecedents of rule four
are already in the assertions before checking other rules?
The answer?
You're not only correct, sir, you're exactly one step ahead.
So I'm going to assume I called on you for the very next thing.
That's exactly what we do once we draw it onto the tree.
You're exactly on the way.
Further question?
Perfect.
All right, great.
So again, we're putting up Millicent studies a lot.
Millicent is a protagonist.
We're not putting up x.
Some people did that.
And of course it's an n node as we heard.
We need them both to be true or we're not going
to be able to continue onward.
So we have-- I'm going to use m for Millicent.
Millicent studies a lot.
Also over here, Millicent is a protagonist.
And we've already heard that we need
to search in the assertions before we
go into any rules for what we're looking for next.
The question is, what are we looking for next and in what
order?
This is where that thing I told you about depth search
is crucial.
We are going to look here on the left node.
And if it has any children, if we have to keep going down,
we are not going to look here yet.
There's a few reasons for that.
One of which is that we're lazy.
The evaluation, if you learned about it,
is also-- if you learn about lazy evaluation, is also lazy.
And if we can disprove this study's a lot branch,
we don't have to do any work with the protagonist branch.
We're done.
We're out of here.
And it's a loss.
So we're going to move down the study's a lot branch.
And we already heard from the audience,
we need to look to see if it's in the assertions.
Everyone, is Millicent studies a lot in the assertions?
No, it's not.
Well then, now we're going to get to that question
that I had before about the antecedent or the consequent.
Because study lies here in the antecedent of rule four,
but we're not going to be able to use rule four here.
In fact, that's how we got here in the first place.
So the question is-- let's see, the question
is, do we have a rule in the consequent that matches
Millicent studies a lot.
Yeah, that's right, P3.
That's right.
So P3 would give us Millicent studies a lot.
And so therefore what will we add to the goal tree?
AUDIENCE: We add both that is Millicent either a protagonist
or a villain and [INAUDIBLE].
MARK SEIFTER: Yeah, she.
Turns out to be a girl.
So that's exactly right.
We heard that we need to add-- we
need to add an AND node, which also has an OR
node at the bottom of it, because this
is a little bit of a complicated rule.
So we have an AND node.
And the first thing on the AND node
is Millicent is a protagonist or Millicent is a villain.
And the second thing on the AND node is Millicent is ambitious.
Actually, that is the second thing on the AND node.
I hope that's what I said.
All right, the second thing on the AND node
is Millicent is ambitious.
So here's our handy little tree.
Now this is where it's important, as I said,
we're doing a depth first search.
We're going down along the left branch.
So where do you think we're going to go next on this tree?
AUDIENCE: [INAUDIBLE]
MARK SEIFTER: Not quite.
That's a good guess.
You didn't say we're trying to prove
m is a protagonist on the right branch, which
is a very common mistake.
What do you do?
AUDIENCE: You should go down to see
if there's a consequence for m is--
Millicent is a protagonist.
MARK SEIFTER: Which one of the two Millicent
is a protagonist do we want to look at?
Yeah, the farthest down left.
That's right.
So you guys will learn depth for search
on Monday, at which point it will become
much clearer what I'm saying.
But yeah, you always follow the left branch as far down
as you can.
Then you take the right branch of that same branch
that you followed.
Great, so we're going to try to find that Millicent
is a protagonist.
What do we do first?
Everyone?
Check assertion, yes.
Is it in there?
No, it's not.
OK.
So, therefore we're going to try to find
a rule as we heard about whether Millicent is a protagonist.
So, all the way in the back?
All the way in the back, is there a rule that matches?
AUDIENCE: [INAUDIBLE]
MARK SEIFTER: That matches in its consequent
that Millicent is a protagonist.
AUDIENCE: Um, there is a rule.
MARK SEIFTER: OK.
Well, let's give it a try.
Which one?
AUDIENCE: One.
MARK SEIFTER: Rule one, that's right.
So therefore, we would have to add what to our goal tree?
AUDIENCE: Another [INAUDIBLE].
MARK SEIFTER: Right.
And what's on that please?
AUDIENCE: [INAUDIBLE]
MARK SEIFTER: Yeah, Millicent lives in Gryffindor Tower,
perfect.
So, our new thing that we're searching for
is-- pretend this conn
…

Need subtitles from another video?