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 connects.
Actually, I guess it does connect.
We're looking for m lives in Gryffindor Tower.
Great.
And since it's depth first, that's where we go next.
Great, we're on a roll.
So what do we do first?
Do we have that in assertions?
Some people say yes, but the answer is no.
We have, in fact, Seamus living in Gryffindor Tower.
Most of you said "no."
You're right.
The majority rules.
We don't have any assertions.
However, do we have a rule with that in the consequent?
No.
So what do we do?
People are saying different things that are all correct.
Backtrack, you say.
Go to the next.
We can't prove it.
All correct.
Put a big x.
This isn't true.
Now we'd look up.
We're on an OR node.
So we're not done yet because either of those can be true.
So now we go back up, backtrack, Millicent is a villain.
What do we do first?
Check assertions.
Is it in there?
No, it's not.
Don't worry, we're getting to one where it will be,
where about 40%-- or 30% to 40% of the class lost
points, very, very soon.
So, we see that Millicent is a villain.
And it's not in the assertions.
So therefore, is there any rule that
has that in its consequent?
AUDIENCE: [INAUDIBLE]
MARK SEIFTER: We're looking for Millicent is a villain.
AUDIENCE: [INAUDIBLE]
MARK SEIFTER: Oh, you can't see it.
All right, I will move it down slightly.
It got a little bit off kilter when I put in the parentheses
around the "and."
Hold on.
There you go.
AUDIENCE: If [INAUDIBLE] is a protagonist or is a villain.
[INAUDIBLE]
MARK SEIFTER: We're trying to prove
that she's a villain, though.
So do we have any with that in the consequent?
[INAUDIBLE] anything that will prove
that she's a villain if we fire off that rule.
Want to give here a little bit of help?
AUDIENCE: P2.
If she lives in Slytherin, then she's a villain [INAUDIBLE].
MARK SEIFTER: Ah, see that now?
It had two, so it was a little bit harder.
Now some people ask, what about that ambitious thing?
Can we like add that to the tree or something?
No.
The backward chainer is single-minded, focused,
and stupid.
Even though it's later going to need to prove that she's
ambitious, it doesn't care.
It just sees the villain there.
Villain, oh, that's great.
As long as we've got the antecedent
we are going to be happy.
This is actually an important point,
not in this particular problem, but in some other problems.
So by using P2, we're obviously going
to have the antecedent x lives in Slytherin dungeon.
And x here is Millicent.
So Millicent lives in Slytherin dungeon.
All right, so what's the first thing
we do when we see this new assertion?
We check the assertions.
Is it in there?
Yes.
That's not where everyone lost points,
but yes, it is in there.
Check.
This OR node is happy.
Now we move up to the AND node with Millicent is ambitious.
So Millicent is ambitious.
What do we do now?
AUDIENCE: So isn't the consequent of P2
that x is a villain and x is ambitious.
I don't know if it's [INAUDIBLE] or whatever,
but in our assertions we have that Millicent is ambitious.
Is that necessary to let us--
MARK SEIFTER: To let us use rule two.
Actually, no.
The question is, do we need the x is
ambitious to be in our list of assertions in order to use P2.
For instance, if we didn't have the assertion that Millicent
is ambitious, would P2 have a problem firing?
So, it's a very interesting question.
It's sort of what actually I was trying
to mention earlier when I said it's single-minded,
it's focused, it doesn't care about the other one.
Because you might say, well, wait a minute,
P2 could never have actually fired
if it didn't have both of its consequents.
But in fact, the backward chainer doesn't care.
All that the backward chainer is looking to do
is to prove whether or not there's
a possibility that Millicent might be a villain.
It's not trying to say, oh, all the results
of some certain rules are making Millicent a villain
and all the other things that are there, like ambitious, are
in the database.
It's not the forward chainer.
It actually doesn't care.
This sometimes leads to unnecessary computation.
But it's very simple, and it's very simple to code.
So it often will probably speed you up in the long run.
Like if there's, for instance, 100 thing in the then
and you only care about one of them,
it would be a waste, almost, to add those 99.
There's a follow up over here somewhere?
[INAUDIBLE]
AUDIENCE: Order m of 99.
And so [INAUDIBLE]
MARK SEIFTER: You can try.
However, then at that point, every time
you check the assertions, you'd be
attempting to check those 99.
Also, you might not have used those rules.
The question is, could you make a hash table
with all of the 100 things that were in the consequent?
And then, after having made that hash table
since you were already walking through those anyway
when you were checking it, you could add those
to the assertions.
The problem is that you might not necessarily
want-- with the backward chainer-- you might not
necessarily want to think that all
those things in the consequent are necessarily true.
However, you might not care about them.
And then you have to make an order
and computation every time you check that list of assertions
in the upper left.
AUDIENCE: [INAUDIBLE]
MARK SEIFTER: You don't know what assertions there are.
You have to check the entire list of assertions
in the upper left every time you get
to a new node in the goal tree.
So each one is order 1.
But I'm not saying to find a specific assertion is order n.
I'm saying every time you get a new node in the goal tree,
you have to check all the assertions you've added.
AUDIENCE: You have to do that anyway. [INAUDIBLE] assertions.
MARK SEIFTER: Yeah, you'd have to check for the four.
But let's say that there were 10,000 consequents of P2.
You would have to check 10,000 instead of four
if you added them all after proving
P2 was true on the goal tree.
Also, another important note is that you might not
use every branch of the goal tree,
if there's like an OR that's up higher
and you wind up using a different branch, in which case
you'd probably have to make a separate hash
table for every sub-branch that you have
and then remember which hash tables were updated
based on which sub-branch.
And then sub-branches die.
It's probably more effort than it's worth.
It's certainly an interesting question.
It's a great question for a debate in recitation.
Also, I'm happy to talk about it later.
I think that someone who very intelligently made hash tables
and thought the problem through, as Patrick said,
more knowledge can mean a better-- well,
actually maybe he hasn't said more knowledge can mean
a better search because we haven't done that lecture yet,
but--
AUDIENCE: You're talking about implementation decision
and using hash table might well be a good way to do this.
The problem is that we're presuming some things about how
the rules are firing and what [INAUDIBLE] they're
firing that depend on the order of assertions in the table.
So if we used the hash table, we'd lose the order.
[INAUDIBLE]
MARK SEIFTER: That's true.
That's true.
But I'm thinking like if someone wanted
to make that implementation as like do some research in rules
based systems, it's possible you can increase the running speed.
In this class, we are not completely as focused
on the fastest algorithms.
But I still think that a cool thing to try.
Questions from people in the crowd?
We'll start with you.
AUDIENCE: So ignoring the hash table?
MARK SEIFTER: Ignore the hash table.
That's a good idea because it's a little extra enrichment
thing.
It's not anything you would possibly
need to know for the quiz.
AUDIENCE: [INAUDIBLE] So if it became
an [INAUDIBLE] are you using this "then" statement
because you want the villain.
So along with using this you get x is ambitious.
[INAUDIBLE] used after that, another "then" statement
that we also use that says x is not ambitious.
So how would you resolve that?
MARK SEIFTER: So the question is,
let's say you used rule two somewhere in the tree
to get that x is a villain, which
then says that x is ambitious.
Then later, you have x is not ambitious
somewhere in one of the other rules that you then later need.
The question is, how do you resolve that?
What does it do?
Well, first of all--
AUDIENCE: [INAUDIBLE]
MARK SEIFTER: First of all, interestingly,
if it says x is not ambitious-- literally like that.
And I'm not being pedantic here.
This is one of the tricks someone
played in a previous quiz.
You can have that and x is ambitious
both in the list because it's a dumb rules-based system it
doesn't know that you can't have both of those on the list.
So if you have a positive assertion in a consequent,
x is not ambitious in a consequent, x is not ambitious,
it'll be happy to add Millicent is not ambitious
while Millicent ambitious this is already there,
because it's stupid.
Now if it had delete Millicent is
ambitious in the consequent and deleted something that
was previously there, that would be an interesting problem.
It could cause mistakes.
Your back chaining would probably
make the mistake of allowing this.
However, this is exactly what we do not, I believe as a policy,
do not have DELETE statements on the quizzes.
At least previous quizzes did not
have them, except for in a hypothetical
of what happens if we add a DELETE statement here.
I don't think we've ever made people work things
through with the delete.
Delete would possibly cause some issues.
Question in the back?
AUDIENCE: So, just to check this,
we're doing backwards chaining, we
don't actually add assertions to your [INAUDIBLE].
MARK SEIFTER: Never add assertions in backward chain
to the assertion table.
It's dumb.
The system is dumb.
I'm not saying it's a dumb idea to do this.
It's actually pretty fast to do it this way.
But the system is dumb.
The question is, do you add assertions
or you don't add assertions?
You do not.
You simply go through, checking all the things on your goal
tree until the goal tree is either proven or disproven,
then you're out of here.
So, cool so far, everyone?
Good questions from everyone.
These are all questions that are things
that often trip people up.
So, our next thing, Millicent is ambitious.
We sort of-- the cat is out of the bag
because there is a question mentioning that there
is an assertion that says that.
But I direct you guys to our favorite rule, rule two.
Shouldn't we use rule two to prove
that Millicent is ambitious?
The answer is if you want to lose four points or however
many points, then yes.
But if you don't want to lose points,
then this is already correct by virtue of assertion one.
So I guess I should write, also, that this over here,
Millicent studies a lot rule, this rule is rule four.
Yeah, that's rule four [INAUDIBLE] and protagonist.
Down here to prove that she studies a lot is rule three.
And then at the bottom here we have what rules here?
We have the protagonist rule, which is one,
and the villain rule which is two.
This is correct virtue of A0.
OK, great.
So we've proved this whole AND node.
We know that Millicent studies a lot.
But now we're going to have to go a little bit more
quickly based on time, and so I will do the remaining things.
Anyone who has not been called on is off the hook.
But that doesn't mean not to pay attention
because there's some interesting stuff still to come.
So, Millicent is a protagonist.
Well, good news, everyone.
There's one other reason that I can do this
and that's that you've already told me what I need to do.
Most is a protagonist, you use rule one, rule one.
And check if she lives in Gryffindor tower.
Now, will it do it again?
Yes it will.
It hasn't cached that it's already tried that.
Now, hash table not withstanding, caching something
you've already tried may be a good idea with backward
chaining, but we do not do that in this class.
That's an implementation detail.
It's another idea of something you can do.
We don't catch things that we've already tried.
We try them again, dammit.
And when we try it again, maybe it'll work this time.
No, it never works.
It never works this time.
This fails.
This AND node fails.
The whole thing fails.
They're not friends at all.
They're bitter enemies.
Millicent does not become Hermione's friend.
So now they ask us a few questions
which are pretty easy to answer based on the ordeal we've just
been through.
So, determine the minimum number of additional assertions
that we would need to add for Millicent
to become Hermione's friend.
But you're not allowed to add an assertion that
matches a consequent of a rule.
You can only add an assertion-- in other words,
you can't add an assertion that will prove some other rules.
You have to add an assertion that directly-- yeah,
that's basically the rule here.
Because there's a lot of choices.
But he wanted one particular answer.
And so can anyone think of an assertion
that doesn't match any consequent of any rule that
will make her be Hermione's friend.
A lot of people say Millicent lives in Gryffindor.
That's correct.
So, part three, your solution to part two
causes an uncommon situation.
What is the uncommon situation?
And what should you do to the list of assertions
to solve this problem?
Does anyone know what the uncommon situation
would be if we added that she lives in Gryffindor?
Hand is raised up here.
What is your answer?
[INAUDIBLE] That's true.
She lives in Gryffindor and Slytherin.
So how would you fix that?
[INAUDIBLE] Yes, you could take out
Slytherin from the assertions and say that she only
lived in Gryffindor.
A lot of people gave the answer to this question,
which is a perfectly reasonable thing
to do in a rules-basis system.
They said, well, we can add a rule that
says that if you live in x and y is different than x, then
you can't live in y.
The problem with that, among other things,
is that we asked for a way to change the assertions and not
the rules.
And you gave us a way to change the assertions.
That's the right answer.
There was another backward chaining problem,
this is 2009 quiz one, and I will leave it off
for the moment.
You guys should take a look at it,
in particular with variable binding.
Because remember, you always have to bind
the variable that's relevant to you.
But that doesn't mean that you always have
to bind all of the variables.
For instance, let's say that we wanted
to prove that Millicent has a bad term, which
as it turns out, is what we wanted to prove
in the other backward chaining.
Very quickly and without doing the problem, can anyone who
thinks they're very clever at backward chaining tell me
exactly what things would be added to the goal tree
to prove that Millicent has a bad term?
Raise your hand.
I won't pick out a victim because I'm asking
this to happen pretty quickly.
No one?
All right.
AUDIENCE: You would add the three antecedents to rule--
MARK SEIFTER: To rule five.
So what would you add specifically?
AUDIENCE: For anyone, variable-wise,
you would just have to show that there is at least
one person who matches.
MARK SEIFTER: So can you just sort of read out,
what would the first thing say with the snogs?
AUDIENCE: X snogs-- or Millicent snogs anyone.
MARK SEIFTER: Yeah, Millicent snogs y.
That's crucial.
Some people did a lot of different things.
Some people put Seamus in already.
You can't do that.
The system is stupid, it doesn't know that the person is Seamus.
Also, some people said it worked,
because look, they're snogging each other,
but it's the wrong snoggle direction up there.
Because we have Seamus snogging Millicent,
not Millicent snogging Seamus.
But yes, exactly.
It would be Millicent snogs y.
Millicent lives in Gryffindor tower.
y lives in Slytherin dungeon.
So, let's give forward chaining all the attention it deserves,
about eight minutes, which will be more than enough.
OK, we still got all these rules.
We've still got all these assertions.
Instead of doing that horrible backward chaining-- well,
it's not that horrible-- but we'll do forward chaining.
It'll be really easy.
We'll just add new assertions as they go.
Remember the tiebreak order.
Rules in order from 0 to 5.
And if the same rule could fire off
with multiple different assertions,
we'll use the assertions in order from 0 to 3.
So let's see.
We don't have much time, but with our four assertions,
let's see, what rules possibly could
match with our four assertions?
Well, I'll figure out for you.
Do we have an assertion about an ambitious person?
Yes.
But they're not a squib.
So not rule zero.
Do we have someone that lives in Gryffindor?
We absolutely do.
Rule one is matches.
Do we have someone that lives in Slytherin?
We do.
Rule two matches.
Do we have a protagonist or a villain?
We don't have any protagonist or villain.
Rule three is not going to match because it's in an "and."
do we have someone who studies a lot?
We do not have someone who studies a lot.
Rule four is not going to match.
Do we have some snogging?
We do have some snogging.
So rule one, two, and five match.
So m for matching, we have one, two and five.
Everyone, which one wins the tiebreak between one, two,
and five?
One, because it comes first numerically.
Which one is rule one if x lives in Gryffindor tower?
The only binding for x is Seamus.
Seamus lives in Gryffindor tower.
We're firing off rule one.
So new assertions, the first assertion that we'll add
is Seamus is it a protagonist.
Great.
Now, there's one other thing, and it's
the main thing I wanted to tell you about in forward chaining.
About our old friend, rule one, now that we've done this,
does rule one still match an assertion in the database?
Yes.
It does.
But what's going to stop us from constantly doing rule one
every time because it comes numerically
before the other rules?
What stops us there is a part of our implementation.
And it's a very important part that people sometimes forget.
It's what I like to call the no-impotent rules
implementation detail.
That is, if a rule is completely,
100% impotent, it would do absolutely nothing.
Then you do not fire it.
You go to the next one.
That's pretty important.
Let's say that you possibly had a delete, which
you won't have on the quiz.
That means that if the thing to delete is missing,
it's impotent.
If the thing to delete is there, it's not impotent
because you can delete.
Let's say you have 500,000 things that you're going
to add to your assertions.
499,999 are already in your database.
One of them is missing.
Is it an impotent rule?
No, it's not.
You have to fire it anyway.
You can't be like, oh, it's mostly impotent rule.
No.
You have fire off the rule if it will do anything.
But right now rule one won't do anything because we've already
added Seamus is a protagonist.
So what rules match down?
Well, Seamus becoming a protagonist is nice and all,
but he's not ambitious, so we still don't match rule three.
We still match rules one, two, and five.
As I basically just got finished telling you,
the one that we're going to fire off now is two.
That's right.
So, rule two is if x lives in Slytherin dungeon
our only [? binding ?] for that is Millicent.
And that will show that she's a villain and she's ambitious.
So what assertions will we add?
Millicent is a villain.
And people stopped.
That's right.
Good job, everyone.
You remembered that Millicent is already
ambitious from assertion one, so we don't have to add them both.
A lot of people did.
They were wrong.
So Millicent is a villain.
The other part of that rule doesn't do anything.
But it's not an impotent rule because one of the things
is not on there.
Great.
So, what rules match now?
Well, as it turns out, now that Millicent
is a villain and ambitious, we match rule three as well.
So we match one, two, three, and five.
What rule are we going to fire, everyone?
Three.
Because one and two are impotent rules.
We'll fire rule three.
Well, Millicent is a villain.
She's also ambitious.
She's our only match for three.
Therefore, what assertion do we add?
Millicent studies a lot.
That's right.
So, Millicent studies a lot.
However, she's not a protagonist.
We still don't match rule four.
Oh well, we figured that out already ourselves
from backward chaining that we were never going to match that.
So what matches?
It's still one, two, three, and five.
Seeing as one, two and three are impotent,
the only match is five.
So the only match we care about, the only one
we're going to fire is five.
And the result?
Let's see.
x snogs y.
That's Seamus snogs Millicent.
x lives in Gryffindor, that's Seamus.
y lives in Slytherin, that's Millicent.
So what do we add?
Seamus has a bad term.
Simple, painless, it works out.
We're done.
And we got 100 on this quiz.
Hopefully you guys will, too.
Question?
The question is, if you have a new assertion which matches
a rule but it's really high number,
it's all the way down at the bottom of the rules,
but it's new and it has new stuff,
should we do that first, maybe, because it's new?
Oh, you mean that it has a lower number, a lower number?
AUDIENCE: [INAUDIBLE]
MARK SEIFTER: OK, so the question
is, if a rule-- let's say that rule three made Millicent
be a squib.
Then yes, you'd immediately not only match
zero-- zero would immediately fire because numerically
it comes first.
You'll see that on some of the old quizzes.
And you may see that in tutorial.
If you guys want to do some more practice problems in tutorials,
your TAs will have that available as one
opportunity in tutorial.
But yeah, that's exactly right.
It happened that it went in order this time,
but it will definitely hop anywhere
it can in order to get to the lowest numbered assertion.