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. Hi everyone. A few of you may know me from my tutorial, but if you don't, I am Mark Seifter. I'm the senior TA here at 6034. And these Friday mega recitations are going to be a little bit different than any of the other things in the class. All right. So, what is mega recitation? Mega 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 mega recitation as we attempt to work with some of the material that Patrick has sort of given us the big picture for in the lectures.

And if you've gone to recitations so far, you may have received a little bit of enrichment into how the algorithms work. Well, here in mega 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, um in some of these examples I put up here or like Patrick sometimes does in lectures to teach you the algorithms, is 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 um tripped up a lot of people in addition to emphasizing tricks that I've picked up over the gosh, has it been 3 years of um TAing 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 it in mega recitation um last year and people still got tricked by them. I guess maybe some people didn't come to mega recitation or they were just very tricky tricks. So, be sure to come to mega recitation, pay attention to the um 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 of the first quiz. So, without further ado, uh if there are no um questions on that, which I don't think there probably will be, uh 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 big Harry Potter fan. So, what we have here are 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 and you may have already seen this problem.

And if you're 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 um if you have a lot of attention to detail, but you're not really in on Scheme or Lisp, you may think that my 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 um if X is ambitious and X is a Squib, then X has a bad turn. That's rule zero up at the top.

Um that's written in sort of what we call infix notation. It's easy, it's simple. All the operators are in the order you would expect. 2 + 3 = 5. There's another kind of notation that is sometimes used on previous quizzes. And by sometimes, a good number of times, actually. I'm not sure why we still use it that way because of the fact that the class has moved on to Python, but we do sometimes. And that's called prefix notation. In prefix notation, the operator comes first. So, for instance, + 2 3 = 5. The plus comes first. The function name 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 I it said if and X is ambitious, X is a Squib, then X has a bad turn.

The and went first and there was a parenthesis 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 if you if things start being written in a really weird way with lots and lots and lots of parentheses, whatever's outside of the parentheses, whether it be plus or and 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 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 rules zero through five. For some reason, they are labeled with P's. They are often labeled with either P's or R's. The sort of secret on why they're labeled 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. Um and sometimes with R's. So, these P's are the six rules. The first rule is if X is ambitious and X is a Squib, then X has a bad turn. So, what's the deal with these question mark X's?

The question marks 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 has is ambitious, can they can that person possibly have a bad turn. What we're saying is any character in the Harry Potter universe or not in the Harry Potter universe, maybe a rhinoceros, um can fit into that X. So, for instance, if a rhinoceros is ambitious and a rhinoceros is a Squib, then a rhinoceros has a bad turn. That rule's saying for any X, um this is true.

And it's very important how we treat the question mark X, well, how we bind the question mark X when we do both back chaining and forward chaining. I'll get back to that because um some people made some very, very um 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 was very clever. Um and um it makes it a really great case study for you guys. All right. So, rule one. 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 later on and I'll use SD for Slytherin Dungeon.

Speaking of which, rule two. If X lives in Slytherin Dungeon, then X is a villain. X is ambitious. Why are there two things here? Well, after the if, we have what we call the antecedent. That's something that needs to be true in order for this rule to match. After the then, we have um what is called the consequent. And in this case, there are two consequences. Anyone who lives in Slytherin Dungeon is automatically a villain and also ambitious. So, you can sort of think of there being sort of an and there for um for the purposes of both of those assertions would be added to the knowledge base. Rule three.

If X is a protagonist or X is a villain and X is ambitious, then X studies a lot. By the way, the scope for the oops, the scope for this, just to be sure that we're clear, is this. So, we need them to be protagonist or villain and no matter what, they have to be ambitious. Rule four. If X studies a lot and X is a protagonist, X becomes Hermione's friend. And rule five. If X snogs Y and X lives in Gryffindor Tower and Y lives in Slytherin Dungeon, then X has a bad turn. 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. No, not that. This perfect. Um 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. Um our four assertions that we start with. Assertion zero. Millicent lives in Slytherin Dungeon. Assertion one. Millicent is ambitious. Assertion one is what tripped people up, so remember that Millicent is ambitious. Assertion two. Seamus lives in Gryffindor Tower. And assertion three.

Seamus snogs Millicent. So, those are our 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 um backward chaining and forward chaining, raise your hand if you thought forward chaining was harder than backward chaining. Ha! I knew it. I can prove whatever point I want because no one wants to raise their hand. Cuz I also think backward chaining is harder than um forward chaining. Raise your hand if you think backward chaining is harder 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, um I agree that backward chaining is harder than forward chaining. And I disagree with Patrick that we're going to get out of here early. So, let's start with backward chaining first so that we make sure that we spend the bulk of our time with it. Cuz forward chaining, well, you know, you just go through you 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, uh when we're doing backward chaining, we have to remember a few things. They're 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 consequent, a rule that has something in the then that can prove the assertion it's trying to figure out. So, for instance, if I was doing backward chaining on Seamus snogs Millicent, what happens? I'm immediately done because there's an assertion in assertion three that says Seamus snogs Millicent. I've proved it. I'm done. I'm happy. We can leave. We can go home. Unfortunately, that's not what the quiz asked us to do. Now, let's say that instead, um 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 recurse and try to prove whatever is in the antecedent of rule one, which is okay, well, does he live in Gryffindor 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. Um let's keep in mind the backward chainer never adds new assertions to the list of assertions.

And if you have a tiebreak, you always order based on um rule order first, P0 through P5. And if you can fire if you the rule same rule matches with more than one thing in your list of assertions, then you tiebreak based on the order of the assertions. Okay? Uh very important. Disambiguation and tiebreaking are big place to get messed up. So, we're going to try to prove that Millicent becomes Hermione's friend. All right? And so, I'm going to abbreviate um some of the things, but not 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 um messed themselves up and spent more time than they needed to by treating the goal tree in a different way. Um now, Millicent becomes Hermione's friend. Let's pretend that we're 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 have to call people in the back.

What do you think is the first thing we should do? Very first thing. Matching assertion. 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? Uh we start to look at the rules. That's right. And do you see any rule that um could prove that Millicent becomes Hermione's friend? P4. That's right. You can see in P4, X, which can be anybody, is capable 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? We have to see if Millicent studies a lot and is a protagonist. That's right. Does everyone see that? In order for her to become Hermione's friend by rule four, have to see if she studies a lot and is a protagonist. Question. Yeah, question. Um so, when you look at the rules, do you look first at like the antecedent or the Okay, 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, 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? You could see um Some people are shaking their head, but um think about 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 in back chaining, 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 um people I've asked so far, sorry, I don't know your names, like Patrick, have um correctly given me every time, which is excellent. So, notice also that she um 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. May be obvious, but after like putting the rule four in there, should we first check the assertions if uh check on the assertions if our conditions are within rule four because then we wouldn't have to search other rules.

Uh question is, do 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 um other rules? The answer, you're not only correct, sir, you're exactly one step ahead. So, we're 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 you're you're you're exactly on the way. Um further question or No, sir. Perfect. So, all right, great. Um 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 and 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. Great. 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 what order? This is where that thing I told you about depth search is crucial. We're 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.

All right? 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 studies 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 and it's a it's a it's a loss. All right? So, um we're going to move down the studies a lot branch. And we already heard from the audience, we need to look to see if it's in the assertions. Everyone, is studies a lot Millicent studies a lot in the assertions? No, it's not. All right.

Well, then, now we're going to get to that question that I had before about the antecedent or the um consequent cuz studies a lot is here in the um 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, question is, does um let's see, the question is um do we have a rule that matches um in the in the um consequent that matches Millicent studies a lot? Yeah, it would be P3. Yep, that's right, P3. And P3 would be traversed if you can prove That's right. So, P3 is um would would give us Millicent studies a lot. And so, therefore, what do we add to the um goal tree?

We add both that is Millicent either a protagonist or a villain and that he's ambitious. Yep, she turns out to be a girl. All right. So, um that's exactly right. We heard that we need to add um we need to add an and node, but 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. 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. Well, actually that is 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. Great. Okay. 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, uh where do you think we're going to go next on this tree? Uh not What? 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. Where do you think we're going to go? Which one of the two Millicent is a protagonist do we want to look at? Yeah, farthest down left. That's right. So, you guys will learn depth-first search on Monday, at which point it'll become much clearer what I'm saying.

But, yeah, you always follow the left branch far down as you can. Then you take the right branch of that same branch that you followed, all right? Great. So, we're going to try to find if Millicent is a protagonist. Where What do we do first? Everyone. Check the assertions. Yes. Is it in there? No, it's not. Okay. So, therefore we're going to try to find a a rule as a as we heard about um whether Millicent is a protagonist. So, all the way in the back. All the way in the back. What? Is there a rule that matches? That matches in its consequent that Millicent is a protagonist. Okay. Well, let's give it a try.

Which one? Rule one. That's right. So, therefore we have to add what to our goal tree? Right. And what's on that leaf? 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. All right. And since it's depth-first, that's where we're going next. Great. We're on a roll. So, what do we do first? Do we have that in the assertions? Some people say yes, but the answer's no. We have in fact Seamus living in Gryffindor tower. Most of you said no. You're right, the majority rules.

Uh we don't have it in the 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 look up, we're on an or node. So, we're not done yet because either of those can be true. Great. So, now we go back up, backtrack. Millicent is a villain. Great. What do we do first? Check the assertions. Is it in there? No, it's not. Don't worry, we're getting to where we're we'll be. We're about 40% of the or 30 to 40% of the class lost points.

Um very, very soon. So, um we see that 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? We're looking for Millicent is a villain. All right, you can see it. Uh all right, I will move it down slightly. It got a little bit off kilter when I put in the um parentheses around the and. Hold on. Uh there you go. Okay. Then they study law. All right, we're trying to prove that she's a villain though. So, do we have any with that in the consequent? That Anything that will prove that she's a villain if we fire off that rule?

All right. Uh want to give her a little bit of help? Uh see that now? You 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 um we're going to be happy. This is actually an important point not in this particular problem, but in some other problems.

So, by using P2, um we're obviously going to have the add the antecedent X lives in Slytherin dungeon. When 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 Millicent is ambitious. What do we do now? Okay. To let us use rule two. Actually, no. It's It's um the question is um do we need the uh 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 it's a it's a very interesting question. It's sort of what actually I was trying to um what I was trying to or mention earlier when I said it's single-minded, it's focused, it doesn't care about the other one. Cuz you might say, "Well, wait a minute. P2 could never have actually fired if it didn't have both of its consequence." But, in fact, the backward chainer doesn't care. All that the backward chainer is looking to do is to prove whether it's to prove whether or not there's a possibility that Millicent might be a villain.

It's not trying to say, "Oh, all of the results of of um 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 it often will probably speed you up in the long run. It like if there's for instance 100 things in the then and you only care about one of them, it would be a waste almost to add those 99. There was a follow-up over here somewhere. You can try. Um 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 um 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 all of those with the backward chainer you might not necessarily want to think that all of those things in the um the consequent are necessarily true. Um however, it can you might not care about them. And then you have to make an order end computation every time you check that list of assertions in the upper left.

That's true. However, we 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 one, but it I'm not saying to find a specific assertion is order is order end. I'm saying every time you make a new node in the goal tree, you have to check all of the assertions you've added. Yeah, you have to check through the four. But, let's say that there were 10,000 consequence of P2. Um you would have to check 10,000 instead of four if you added them if you added them all after proving P2 was true on the goal tree.

Also, another important note is that um 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. You could It's a certainly an interesting question. It's a great question for for debate and recitation. Also, I'm happy to talk about it later. I think that someone who very intelligently made hash tables and thought thought the problem through.

As Patrick said, more knowledge can mean a better actually maybe he hasn't said more knowledge can mean a better search because we haven't done that lecture yet, but You're talking about an 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 what bindings are firing that depend on the order of the assertions in the table. So, if we use the hash table, we'll lose the order and we won't be able to preserve the order. That's true. That's true, but I'm thinking like if someone wanted to make that implementation is like do some research in rules based systems, it's possible you can increase the running speed.

In this class, we are not as not completely as focused on the on the fastest algorithms, but I still think that that's a cool thing to try. Questions from people in the crowd. I'll start here. So, so ignoring the hash table thing Ignore the hash table thing. That's 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. So, ignoring the hash table thing, so if if it became like an and then and you're using this then statement because you want the villain. Okay. Along with using this, you you get X is ambitious. What happens if you use after that another then statement that you also need that says X is not ambitious.

So, how would you resolve like that? 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 somewhere in one of the other rules that you then later need. How is that The question is how do you resolve that? What does it do? Well, first of all um Okay. So, um first of all, interestingly if it says X is not ambitious um literally like that and I'm not being pedantic here. This is one of the tricks someone played in a previous quiz. um 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 in the list. So, if you have a positive assertion in a consequence X is not ambitious in a consequence X is not ambitious, it'll be happy to add Millicent is not ambitious and while Millicent ambitious 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 that would be an interesting problem. It could cause mistakes. Your back chainer would probably make the mistake of allowing this. However, this is exactly why 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 had a delete statement here. We I don't think we've ever made people work things through with the delete. Delete would um would possibly cause some issues. Question in the back. So, just to check this, we're doing backward chaining. You don't actually add assertions to your assertions table. You never add assertions in backward chaining to the assertion table. It's dumb. It just keep 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 So, the question is do you add assertions or you don't add assertions? You do not. You simply go through checking all the things in your goal tree until the goal tree is either proven or disproven, then you are out of here. All right? 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 um the cat is out of the bag because there's a question mentioning that there's 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?

Question is 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 um this is already correct by 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 is um This rule is rule four. Wait a minute. Yeah, that's rule four with studies a lot and protagonist. Down here to prove that she studies a lot is rule three. And then um at the bottom here, we have We have what rules here? We have protag the protagonist rule which is one and the villain rule which is two.

Um this is correct virtue of A0. Okay. Great. So, we've proved this whole end 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 cuz there's some interesting stuff still to come. So, Millicent is a protagonist. Well, good news everyone. uh There's a one other reason that I can do this and that's that you've already told me what I need to do. Millicent is a protagonist, you use rule one. Yeah, 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, a hash table notwithstanding, caching something you've already tried maybe 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 cache things that we've already tried. We try them again, damn it. And when And when we try it again, maybe it'll work this time. No, it never it never works this time. This fails. This end 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. Um but you're not allowed to add an assertion that matches a consequent of a rule. You can only add an assertion that You can 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 just that's basically the the the rule here cuz 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 um 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? That's true. She lives in Gryffindor and Slytherin.

So, how would you fix that? Yeah. You can pick out 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 based system. They said, well, we can add a rule that says that if you live in X and you um 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. Great. So, There was an There was another backward chaining problem.

This is 2009 quiz one. And I will 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 want to prove in the other backward chaining. Very quickly and without doing the problem can anyone can anyone who's who thinks they're very clever at backward chaining tell me exactly what things would be added to the um to the goal tree to prove that Millicent has a bad term?

Raise your hand. I won't I won't pick out a victim cuz I'm asking this to happen pretty quickly. No one? All right. I mean, you would add You would add the three antecedents to rule To rule five. What So, what would you add specifically? For anyone for variable Y. And so, you just have to show that there's at least one person who matches. So, what what can you just sort of read out? What would the first thing say with the snogs? Um X snogs. Or it sorry, Millicent snogs? Anyone? Yeah. Millicent 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's 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 to the wrong it's the wrong snoggle direction. Up there. Um Be 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 of the attention it deserves. About 8 minutes. Which will be more than enough. Okay. 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 trigger 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 who lives in Gryffindor? We absolutely do. Rule one is matches. Do we have someone who lives in Slytherin? We do. Rule two matches. Do we have a protagonist or a villain? We don't have any protagonists or villains. Rule three is not going to match cuz it's it's in an end. 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, I'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 um 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 will add is Seamus is 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 in the database? Yes. It does. But what's going to stop us from constantly doing rule one every time cuz it comes numerically before the other rules?

What stops us there is part of our implementation, and it's a very important part that people sometimes forget. So, what I like to call the no impotent rules um implementation detail. That is, if a rule's completely 100% impotent, it would do absolutely nothing. There's 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 to you have to fire off the rule if it will do anything. But right now, rule one won't do anything cuz we've already added Seamus as a protagonist. So, what rules match now? 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. And 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 figu- you remember that Millicent is already ambitious from rule 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 at what um what rules match now?

Well, as it turns out, now that Millicent is a villain and ambitious, we've matched 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, I 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. Great. So, Millicent studies a lot. However, she's not a protagonist. We still don't match rule four. Oh, well. 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. And 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 it has a lower number. A lower number. Okay. So, the question is if a rule, let's say that rule three made um Millicent be a squib. Then yes, you'd immediately not only match zero with um zero would immediately fire cuz it's numerically it comes first. You'll see that on some of the other 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.