1 00:00:00,050 --> 00:00:02,500 The following content is provided under a Creative 2 00:00:02,500 --> 00:00:04,019 Commons license. 3 00:00:04,019 --> 00:00:06,360 Your support will help MIT OpenCourseWare 4 00:00:06,360 --> 00:00:10,730 continue to offer high quality educational resources for free. 5 00:00:10,730 --> 00:00:13,340 To make a donation or view additional materials 6 00:00:13,340 --> 00:00:17,225 from hundreds of MIT courses, visit MIT OpenCourseWare 7 00:00:17,225 --> 00:00:17,850 at ocw.mit.edu. 8 00:00:21,790 --> 00:00:23,350 MARK SEIFTER: Hi, everyone. 9 00:00:23,350 --> 00:00:26,510 A few of you may know me from my tutorial, 10 00:00:26,510 --> 00:00:30,250 but if you don't I'm Mark Seifter I'm the senior TA here 11 00:00:30,250 --> 00:00:34,370 at 6034 and these Friday omega recitations are going 12 00:00:34,370 --> 00:00:36,606 to be a little bit different than any 13 00:00:36,606 --> 00:00:37,980 of the other things in the class. 14 00:00:37,980 --> 00:00:41,990 All right, so, what is omega recitation. 15 00:00:41,990 --> 00:00:45,630 Omega recitation is in this lecture style room, 16 00:00:45,630 --> 00:00:48,230 but I hope to make it more like a recitation or a tutorial 17 00:00:48,230 --> 00:00:50,310 by, unfortunately for some of you, 18 00:00:50,310 --> 00:00:54,740 perhaps, calling on you guys to participate during the omega 19 00:00:54,740 --> 00:00:58,110 recitation, as we attempt to work with some of the material 20 00:00:58,110 --> 00:01:00,930 that Patrick has given us the big picture 21 00:01:00,930 --> 00:01:01,970 for in the lectures. 22 00:01:01,970 --> 00:01:03,700 And if you've gone to recitation so far 23 00:01:03,700 --> 00:01:06,400 you may received a little bit of enrichment 24 00:01:06,400 --> 00:01:08,230 into how the algorithms work. 25 00:01:08,230 --> 00:01:10,130 Well, here in omega recitation we're 26 00:01:10,130 --> 00:01:13,810 going to figure out how you can work the algorithms. 27 00:01:13,810 --> 00:01:18,070 And that's very important, because in this class being 28 00:01:18,070 --> 00:01:23,120 able to work the algorithms by hand in some of these examples 29 00:01:23,120 --> 00:01:25,430 I put up here, or like Patrick sometimes 30 00:01:25,430 --> 00:01:27,950 does in lectures to teach you the algorithms, 31 00:01:27,950 --> 00:01:29,500 is a crucial way of demonstrating 32 00:01:29,500 --> 00:01:33,590 that you understand how the algorithms work, and we use it 33 00:01:33,590 --> 00:01:34,880 on a quiz. 34 00:01:34,880 --> 00:01:37,690 The way we use it on the quiz is we-- well 35 00:01:37,690 --> 00:01:39,110 this is an old quiz problem. 36 00:01:39,110 --> 00:01:40,040 It's from last year. 37 00:01:40,040 --> 00:01:41,480 It tripped up a lot of people. 38 00:01:41,480 --> 00:01:43,490 So we're going to go over it today. 39 00:01:43,490 --> 00:01:47,120 I'm going to tell you all the tricks that tripped up 40 00:01:47,120 --> 00:01:49,820 a lot of people, in addition to emphasizing tricks 41 00:01:49,820 --> 00:01:53,720 that I've picked up over of the three years of TA-ing 42 00:01:53,720 --> 00:01:56,650 this course before, so that you will not fall prey 43 00:01:56,650 --> 00:01:58,600 to any of these tricks. 44 00:01:58,600 --> 00:01:59,520 Hopefully. 45 00:01:59,520 --> 00:02:01,900 I say hopefully, because some of these tricks 46 00:02:01,900 --> 00:02:05,029 I talked about omega recitation last year 47 00:02:05,029 --> 00:02:06,570 and people still got tricked by them. 48 00:02:06,570 --> 00:02:09,100 I guess maybe some people didn't come to omega recitation 49 00:02:09,100 --> 00:02:11,820 or they were just very tricky tricks. 50 00:02:11,820 --> 00:02:14,040 So be sure to come to omega recitation. 51 00:02:16,944 --> 00:02:18,110 Pay attention to the tricks. 52 00:02:18,110 --> 00:02:20,130 Pay attention to how these things are solved. 53 00:02:20,130 --> 00:02:23,220 Ask questions if you're not sure. 54 00:02:23,220 --> 00:02:25,010 And when we get done with the hour 55 00:02:25,010 --> 00:02:27,350 together I'm hoping that everyone's 56 00:02:27,350 --> 00:02:31,820 going to do really well on the rules part of the first quiz. 57 00:02:31,820 --> 00:02:35,510 So without further ado, if there are 58 00:02:35,510 --> 00:02:38,730 no questions on that, which I don't think there probably 59 00:02:38,730 --> 00:02:42,260 will be, let's move on to the problem at hand. 60 00:02:42,260 --> 00:02:43,980 As some of you may have noticed, it 61 00:02:43,980 --> 00:02:45,520 is a Harry Potter based problem. 62 00:02:45,520 --> 00:02:49,430 One of our TAs last year was a big Harry Potter fan. 63 00:02:49,430 --> 00:02:53,290 So what we have here a series of rules 64 00:02:53,290 --> 00:02:55,740 and a series of assertions. 65 00:02:55,740 --> 00:02:59,850 Now if you happen to be real go getter and have already looked 66 00:02:59,850 --> 00:03:01,610 at all the past quizzes online, you 67 00:03:01,610 --> 00:03:03,640 may have already seen this problem. 68 00:03:03,640 --> 00:03:06,310 And if you really, really have attention to detail 69 00:03:06,310 --> 00:03:08,740 you may notice something a little bit different in the way 70 00:03:08,740 --> 00:03:11,700 I wrote it as compared to the way it was written online. 71 00:03:11,700 --> 00:03:15,140 In fact, you may, if you have a lot of times a detail, 72 00:03:15,140 --> 00:03:17,710 but you're not really in on Scheme or LISP, 73 00:03:17,710 --> 00:03:21,680 you may think the way I wrote it is much easier to understand. 74 00:03:21,680 --> 00:03:24,260 And in case you can't understand the other way, 75 00:03:24,260 --> 00:03:26,440 and in case one of the TAs decides 76 00:03:26,440 --> 00:03:29,900 to write it in a LISP-like way again, let me explain. 77 00:03:29,900 --> 00:03:34,270 If you look at one of my rules, say if x is ambitious, 78 00:03:34,270 --> 00:03:36,880 and x is a squib, then x has a bad term. 79 00:03:36,880 --> 00:03:40,530 That's rule 0 up at the top. 80 00:03:40,530 --> 00:03:44,270 That's written in sort of what we call in fixed notation. 81 00:03:44,270 --> 00:03:45,610 It's easy, it's simple. 82 00:03:45,610 --> 00:03:48,160 All operators are in the order you would expect. 83 00:03:48,160 --> 00:03:50,950 2 plus 3 equals 5. 84 00:03:50,950 --> 00:03:53,220 There's another kind of notation that is sometimes 85 00:03:53,220 --> 00:03:54,630 used on previous quizzes. 86 00:03:54,630 --> 00:03:57,720 And by sometimes, good number of times, actually. 87 00:03:57,720 --> 00:04:00,420 I'm not sure why we still use it that way, because of the fact 88 00:04:00,420 --> 00:04:03,810 that the class has move on to Python, but we do, sometimes. 89 00:04:03,810 --> 00:04:05,480 And that's called prefix notation. 90 00:04:05,480 --> 00:04:08,510 In prefix notation, the operator comes first. 91 00:04:08,510 --> 00:04:13,580 So for instance, plus 2 3 equals 5. 92 00:04:13,580 --> 00:04:14,547 The plus comes first. 93 00:04:14,547 --> 00:04:15,880 The function, then, comes first. 94 00:04:15,880 --> 00:04:18,050 In this case, the function is plus. 95 00:04:18,050 --> 00:04:20,680 So if we were writing this in prefix notation, in fact, 96 00:04:20,680 --> 00:04:26,150 the way I received it, when it said, "if and x is ambitious, 97 00:04:26,150 --> 00:04:28,760 x is a squib, then x has a bad term. 98 00:04:28,760 --> 00:04:31,620 The and went first and there's a parentheses 99 00:04:31,620 --> 00:04:35,144 which included everything that was scoped under the and. 100 00:04:35,144 --> 00:04:37,310 Does anyone have any questions about prefix notation 101 00:04:37,310 --> 00:04:39,640 in case it comes up? 102 00:04:39,640 --> 00:04:43,160 Just remember, if things start being written 103 00:04:43,160 --> 00:04:45,270 in a really weird way with lots and lots 104 00:04:45,270 --> 00:04:47,740 and lots of parentheses, whatever's 105 00:04:47,740 --> 00:04:50,705 outside the parentheses, whether it be "plus" or "and" 106 00:04:50,705 --> 00:04:55,192 or "or" is an operator that acts on the things that are inside. 107 00:04:55,192 --> 00:04:57,150 However, we're not going to deal with that now, 108 00:04:57,150 --> 00:05:00,050 because I think the most important thing is 109 00:05:00,050 --> 00:05:02,930 to understand is the rules, and the less important thing 110 00:05:02,930 --> 00:05:05,030 is to understand prefix notation. 111 00:05:05,030 --> 00:05:07,100 And you can do a problem at home that's 112 00:05:07,100 --> 00:05:10,570 written in prefix notation to test yourself on that. 113 00:05:10,570 --> 00:05:13,270 So what rules do we have here. 114 00:05:13,270 --> 00:05:15,510 We've got equals 0 through 5. 115 00:05:15,510 --> 00:05:18,720 For some reason they are labeled with P's. 116 00:05:18,720 --> 00:05:21,420 They are often labeled with either P's or R's. 117 00:05:21,420 --> 00:05:24,930 The secret on why they are labelled with P's is that one 118 00:05:24,930 --> 00:05:28,062 year somebody labeled them with P's for like "proposition" 119 00:05:28,062 --> 00:05:29,020 or something like that. 120 00:05:29,020 --> 00:05:32,410 And then other TAs looked at that test and sometimes also 121 00:05:32,410 --> 00:05:36,320 labeled it with P's and it sort of down the line continued 122 00:05:36,320 --> 00:05:40,050 to be labeled with P's, and sometimes with R's. 123 00:05:40,050 --> 00:05:42,500 So these P's are these six rules. 124 00:05:42,500 --> 00:05:46,820 The first rule is if x is ambitious, and x is a squib, 125 00:05:46,820 --> 00:05:49,090 then x has a bad term. 126 00:05:49,090 --> 00:05:51,860 So what's the deal with these question mark x's? 127 00:05:51,860 --> 00:05:55,800 The question mark before an x, or perhaps a y down here, 128 00:05:55,800 --> 00:05:59,340 indicate that there's a variable waiting to be bound. 129 00:05:59,340 --> 00:06:01,920 We're not assuming there's a Harry Potter character named 130 00:06:01,920 --> 00:06:05,130 x, and only if that question mark x, the mystery character, 131 00:06:05,130 --> 00:06:09,220 only if mystery x character is ambitious can that person 132 00:06:09,220 --> 00:06:10,710 possibly have a bad term. 133 00:06:10,710 --> 00:06:13,470 What we're seeing is any character in the Harry Potter 134 00:06:13,470 --> 00:06:15,240 universe, or not the Harry Potter 135 00:06:15,240 --> 00:06:20,520 universe, maybe a rhinoceros, can fit into that x. 136 00:06:20,520 --> 00:06:22,850 So for instance, if a rhinoceros is ambitious, 137 00:06:22,850 --> 00:06:26,920 and a rhinoceros is a squib, then a rhinoceros has bad term. 138 00:06:26,920 --> 00:06:31,250 That rule saying, for any x this is true. 139 00:06:31,250 --> 00:06:33,950 And it's very important how we treat the question mark 140 00:06:33,950 --> 00:06:37,620 x, and how we bind question mark x, 141 00:06:37,620 --> 00:06:40,540 when we do both back chaining and forward chaining. 142 00:06:40,540 --> 00:06:44,820 I'll get back to that, because some people made some very, 143 00:06:44,820 --> 00:06:48,720 very small mistakes that really messed up 144 00:06:48,720 --> 00:06:51,130 a lot of their forward and backward chaining last year. 145 00:06:51,130 --> 00:06:52,296 It was actually very tricky. 146 00:06:52,296 --> 00:06:56,240 Jeremy, the TA who wrote this was very clever, 147 00:06:56,240 --> 00:06:59,500 and it makes it really great case study for you guys. 148 00:06:59,500 --> 00:07:03,125 All right, so Rule 1, if x lives in Gryffindor tower 149 00:07:03,125 --> 00:07:05,140 then x is a protagonist. 150 00:07:05,140 --> 00:07:06,750 By the way, for conciseness I'm going 151 00:07:06,750 --> 00:07:09,390 to be using GT for Gryffindor tower 152 00:07:09,390 --> 00:07:11,530 when I write these in later on, and I'll 153 00:07:11,530 --> 00:07:13,920 use SD for Slytherin dungeon. 154 00:07:13,920 --> 00:07:17,460 Speaking of which, Rule 2, if x lives in Slytherin dungeon, 155 00:07:17,460 --> 00:07:21,960 then x is a villain, x is ambitious. 156 00:07:21,960 --> 00:07:24,040 Why there are two things here? 157 00:07:24,040 --> 00:07:27,570 Well, after the "if" we have what we call antecedent, 158 00:07:27,570 --> 00:07:30,580 that's something that needs to be true in order for this rule 159 00:07:30,580 --> 00:07:32,030 to match. 160 00:07:32,030 --> 00:07:35,600 After the "then" we have what is called the consequent, 161 00:07:35,600 --> 00:07:37,509 and in this case there are two consequents. 162 00:07:37,509 --> 00:07:39,050 Anyone who lives in Slytherin dungeon 163 00:07:39,050 --> 00:07:42,440 is automatically a villain and also ambitious. 164 00:07:42,440 --> 00:07:45,330 So you can think of there being sort of an "and 165 00:07:45,330 --> 00:07:49,730 therefore" for the purposes of both of those assertions 166 00:07:49,730 --> 00:07:52,520 would be added to the knowledge base. 167 00:07:52,520 --> 00:07:56,320 Rule 3, if x is the protagonist or x is a villain, 168 00:07:56,320 --> 00:08:02,730 and x is ambitious, then x studies a lot. 169 00:08:02,730 --> 00:08:09,440 By the way, the scope for this, just to be sure 170 00:08:09,440 --> 00:08:14,610 that we're clear, is this. 171 00:08:14,610 --> 00:08:18,470 So we need them to be a protagonist 172 00:08:18,470 --> 00:08:22,930 or villain and no matter what they have to be ambitious. 173 00:08:22,930 --> 00:08:26,460 Rule 4, if x studies a lot, and x is a protagonist, 174 00:08:26,460 --> 00:08:28,540 x becomes Hermione's friend. 175 00:08:28,540 --> 00:08:33,950 And Rule 5, if x snogs y, and x lives in Gryffindor tower and y 176 00:08:33,950 --> 00:08:38,130 lives in Slytherin dungeon, then x has a bad term. 177 00:08:38,130 --> 00:08:39,760 So those are our six rules that we 178 00:08:39,760 --> 00:08:42,330 can use to understand Jeremy's world of the Harry Potter 179 00:08:42,330 --> 00:08:43,730 universe. 180 00:08:43,730 --> 00:08:47,060 And we also start off with four assertions. 181 00:08:47,060 --> 00:08:50,210 Let me not underestimate the value of always looking 182 00:08:50,210 --> 00:08:50,960 to the assertions. 183 00:08:50,960 --> 00:08:55,180 It's one of my white star ideas that are up here on the board. 184 00:08:55,180 --> 00:08:56,740 Let me see. 185 00:08:56,740 --> 00:08:57,240 This. 186 00:08:57,240 --> 00:08:59,270 Perfect. 187 00:08:59,270 --> 00:09:02,640 Always check the assertions before using a rule. 188 00:09:02,640 --> 00:09:05,260 This really tripped people up last year, and you'll see why, 189 00:09:05,260 --> 00:09:08,734 because we're doing last year's problem. 190 00:09:08,734 --> 00:09:10,150 Our four assertions that we start. 191 00:09:10,150 --> 00:09:14,200 With assertion 0, Millicent lives in Slytherin dungeon. 192 00:09:14,200 --> 00:09:16,980 Assertion 1, Millicent is ambitious. 193 00:09:16,980 --> 00:09:18,580 Assertion 1 is what tripped people up, 194 00:09:18,580 --> 00:09:20,820 so remember that Millicent is ambitious. 195 00:09:20,820 --> 00:09:23,690 Assertion 2 Seamus lives in Gryffindor tower. 196 00:09:23,690 --> 00:09:27,380 And assertion 3, Seamus snogs Millicent. 197 00:09:27,380 --> 00:09:30,010 So those those are our four assertions 198 00:09:30,010 --> 00:09:32,820 that we've already started with. 199 00:09:32,820 --> 00:09:35,020 Now the two things we're going to have to do 200 00:09:35,020 --> 00:09:38,400 are backward chaining and forward chaining. 201 00:09:38,400 --> 00:09:41,657 Now when you guys learned these two backward chaining 202 00:09:41,657 --> 00:09:43,840 and forward chaining, raise your hand 203 00:09:43,840 --> 00:09:46,500 if thought forward chaining was harder than backward chaining. 204 00:09:50,470 --> 00:09:51,032 I knew it! 205 00:09:51,032 --> 00:09:52,990 I can prove whatever point I want because noone 206 00:09:52,990 --> 00:09:54,320 wants the raise their hand. 207 00:09:54,320 --> 00:09:56,710 I also think backward chaining is higher than forward 208 00:09:56,710 --> 00:09:57,210 chaining. 209 00:09:57,210 --> 00:09:59,251 Raise your hand if you think backward chaining is 210 00:09:59,251 --> 00:10:00,680 higher than forward chaining? 211 00:10:00,680 --> 00:10:02,190 First of all, we have a good number of people. 212 00:10:02,190 --> 00:10:04,580 Second of all, since no one wants to raise their hand, 213 00:10:04,580 --> 00:10:06,050 I could just ask it the other way. 214 00:10:06,050 --> 00:10:09,510 That's a pro tip if you're ever with a large group of people. 215 00:10:09,510 --> 00:10:12,680 You can prove any point you want by asking the other direction. 216 00:10:12,680 --> 00:10:14,100 No one will raise their hand. 217 00:10:14,100 --> 00:10:18,370 So I agree that backward chaining is higher than forward 218 00:10:18,370 --> 00:10:18,970 chaining. 219 00:10:18,970 --> 00:10:22,680 And I disagree with Patrick that we're going to get out early, 220 00:10:22,680 --> 00:10:25,169 so let's start with backward chaining first. 221 00:10:25,169 --> 00:10:27,460 So that we make sure that we spend the bulk of our time 222 00:10:27,460 --> 00:10:27,959 with it. 223 00:10:27,959 --> 00:10:31,580 The forward chaining, well, you just 224 00:10:31,580 --> 00:10:33,710 go through pretty methodically and add new rules. 225 00:10:33,710 --> 00:10:36,660 Backward chaining, you have to draw this crazy tree. 226 00:10:36,660 --> 00:10:39,880 There's a lot of places to get lost in the middle of the road. 227 00:10:39,880 --> 00:10:42,220 So let's do some backward chaining. 228 00:10:42,220 --> 00:10:45,540 And to do that, I'll do it over here on the left side. 229 00:10:45,540 --> 00:10:47,880 So when we're doing backward chaining, 230 00:10:47,880 --> 00:10:50,470 we have to remember a few things that are written directly 231 00:10:50,470 --> 00:10:51,140 on the quiz. 232 00:10:51,140 --> 00:10:53,140 So you're not going to have to worry about that. 233 00:10:53,140 --> 00:10:55,290 But they're still pretty important. 234 00:10:55,290 --> 00:10:59,460 So-- actually, I'll write it on here first. 235 00:10:59,460 --> 00:11:01,470 I'm going to read them off. 236 00:11:01,470 --> 00:11:03,850 So when working on a hypothesis, the backward chainer 237 00:11:03,850 --> 00:11:05,510 tries to find a matching assertion 238 00:11:05,510 --> 00:11:08,050 in the list of assertions first. 239 00:11:08,050 --> 00:11:10,850 If no matching assertion is found, 240 00:11:10,850 --> 00:11:13,880 the backward chainer will try to find a rule 241 00:11:13,880 --> 00:11:15,250 with a matching consequence. 242 00:11:15,250 --> 00:11:17,460 A rule that has something in the then that 243 00:11:17,460 --> 00:11:20,220 can prove the assertion is trying to figure out. 244 00:11:20,220 --> 00:11:21,920 So for instance, if I was doing backward 245 00:11:21,920 --> 00:11:27,140 chaining on Seamus [? Snaus ?] Millicent, what happens? 246 00:11:27,140 --> 00:11:28,960 I'm immediately done because there's 247 00:11:28,960 --> 00:11:31,680 an assertion that's assertion three that says 248 00:11:31,680 --> 00:11:33,280 Seamus [? Snaus ?] Millicent. 249 00:11:33,280 --> 00:11:34,180 I proved it. 250 00:11:34,180 --> 00:11:34,920 I'm done. 251 00:11:34,920 --> 00:11:35,530 I'm happy. 252 00:11:35,530 --> 00:11:37,240 We can leave, we can go home. 253 00:11:37,240 --> 00:11:40,380 Unfortunately, that's not what the quiz asks us to do. 254 00:11:40,380 --> 00:11:44,080 Now, let's say that instead, we were supposed to say, 255 00:11:44,080 --> 00:11:46,850 I don't know, Seamus is a protagonist. 256 00:11:46,850 --> 00:11:49,890 Well then, we'd wind up looking through here 257 00:11:49,890 --> 00:11:54,170 and we would look at the fact that rule one can prove 258 00:11:54,170 --> 00:11:56,150 that someone is a protagonist. 259 00:11:56,150 --> 00:11:58,490 And we'd curse and try to prove whatever 260 00:11:58,490 --> 00:12:01,650 is in the antecedent of rule one, which is, OK, well, 261 00:12:01,650 --> 00:12:04,360 does he live in Gryffinder Tower? 262 00:12:04,360 --> 00:12:06,420 Assertion two, he does. 263 00:12:06,420 --> 00:12:07,621 So that's some really quick. 264 00:12:07,967 --> 00:12:09,550 And if that was too, fast don't worry. 265 00:12:09,550 --> 00:12:12,360 We're going to go step by step with the actual problem. 266 00:12:12,360 --> 00:12:15,826 But I just wanted to give two really easy problems, really 267 00:12:15,826 --> 00:12:17,200 quickly, how it's going to do it. 268 00:12:17,200 --> 00:12:19,730 Let's go step by step with the real problem. 269 00:12:19,730 --> 00:12:21,230 Let's keep in mind, backward chainer 270 00:12:21,230 --> 00:12:24,360 never adds new assertions to the list of assertions. 271 00:12:24,360 --> 00:12:29,470 And if you have a tiebreak, you always 272 00:12:29,470 --> 00:12:34,080 order based on rule order first, P0 through P5. 273 00:12:34,080 --> 00:12:39,130 And if the same rule matches with more than one thing 274 00:12:39,130 --> 00:12:41,030 in your list assertions, then you 275 00:12:41,030 --> 00:12:44,860 tiebreak based on the order of the assertions. 276 00:12:44,860 --> 00:12:46,200 Very important. 277 00:12:46,200 --> 00:12:49,560 Disambiguation and tie-breaking are a big place 278 00:12:49,560 --> 00:12:51,970 to get messed up. 279 00:12:51,970 --> 00:12:56,330 So we're going to try to prove that Millicent 280 00:12:56,330 --> 00:12:59,490 becomes Hermione's friend. 281 00:12:59,490 --> 00:13:04,110 And so I'm going to abbreviate some of the things, 282 00:13:04,110 --> 00:13:06,750 but not for the very first line. 283 00:13:06,750 --> 00:13:13,360 So Millicent becomes Hermione's friend. 284 00:13:13,360 --> 00:13:15,990 We start drawing a goal tree. 285 00:13:15,990 --> 00:13:21,580 Now you guys are going to learn exactly what these mean very 286 00:13:21,580 --> 00:13:25,370 soon, in fact, next lecture. 287 00:13:25,370 --> 00:13:29,620 But for now, trust me when I say these goal trees are depth 288 00:13:29,620 --> 00:13:31,120 first. 289 00:13:31,120 --> 00:13:34,150 And I'll explain what that means because some people have 290 00:13:34,150 --> 00:13:37,070 messed themselves up and spent more time than they needed to 291 00:13:37,070 --> 00:13:41,190 by treating the goal tree in a different way. 292 00:13:41,190 --> 00:13:43,950 Now, Millicent becomes Hermione's friend. 293 00:13:43,950 --> 00:13:46,110 Let's pretend that we are the backward chainer. 294 00:13:46,110 --> 00:13:48,640 We're trying to prove that this is true or disprove 295 00:13:48,640 --> 00:13:51,470 and say, well, it's definitely not true with what we have. 296 00:13:51,470 --> 00:13:54,290 So let's see. 297 00:13:54,290 --> 00:13:56,260 I'm now going to make you guys help. 298 00:13:56,260 --> 00:13:58,560 And people in the back think they won't be called on. 299 00:13:58,560 --> 00:14:00,160 So I often like to call on people in the back. 300 00:14:00,160 --> 00:14:02,380 What do you think is the first thing we should do? 301 00:14:02,380 --> 00:14:04,070 Very first thing? 302 00:14:04,070 --> 00:14:05,820 Yes, look for a matching assertion. 303 00:14:05,820 --> 00:14:07,020 Excellent. 304 00:14:07,020 --> 00:14:10,030 Do we have a matching assertion, everyone? 305 00:14:10,030 --> 00:14:10,860 No, we don't. 306 00:14:10,860 --> 00:14:13,220 That would be the world's easiest quiz problem. 307 00:14:13,220 --> 00:14:14,790 We do not have a matching assertion. 308 00:14:14,790 --> 00:14:15,600 Great. 309 00:14:15,600 --> 00:14:20,470 So, since we don't have a matching assertion, what now? 310 00:14:20,470 --> 00:14:23,565 AUDIENCE: We start to look at the rules. 311 00:14:23,565 --> 00:14:24,690 MARK SEIFTER: That's right. 312 00:14:24,690 --> 00:14:29,060 And do you see any rule that could prove that Millicent 313 00:14:29,060 --> 00:14:30,220 becomes Hermione's friend? 314 00:14:30,220 --> 00:14:31,245 AUDIENCE: P4. 315 00:14:31,245 --> 00:14:32,370 MARK SEIFTER: That's right. 316 00:14:32,370 --> 00:14:35,520 You can see in P4, x, which can be anybody. 317 00:14:35,520 --> 00:14:38,620 Anyone is capable of being Hermione's friend. 318 00:14:38,620 --> 00:14:39,310 Great. 319 00:14:39,310 --> 00:14:44,210 So P4 is our rule of the hour. 320 00:14:44,210 --> 00:14:47,300 So we're going to use P4. 321 00:14:47,300 --> 00:14:52,760 And when we use P4 to prove that Millicent becomes Hermione's 322 00:14:52,760 --> 00:14:55,330 friend, we're going to have to add something 323 00:14:55,330 --> 00:14:56,720 or another to the goal tree. 324 00:14:56,720 --> 00:14:57,824 So let's see. 325 00:14:57,824 --> 00:14:59,490 What do we have to add to the goal tree? 326 00:15:01,760 --> 00:15:03,301 AUDIENCE: We have to see if Millicent 327 00:15:03,301 --> 00:15:04,385 studies a lot [INAUDIBLE]. 328 00:15:04,385 --> 00:15:05,509 MARK SEIFTER: That's right. 329 00:15:05,509 --> 00:15:06,470 Does everyone see that? 330 00:15:06,470 --> 00:15:08,350 In order for her to become Hermione's friend, 331 00:15:08,350 --> 00:15:10,676 by rule four, we have to see if she studies a lot 332 00:15:10,676 --> 00:15:11,550 and is a protagonist. 333 00:15:11,550 --> 00:15:12,373 Question? 334 00:15:12,373 --> 00:15:13,248 AUDIENCE: [INAUDIBLE] 335 00:15:18,400 --> 00:15:20,830 MARK SEIFTER: OK, that's a very good question. 336 00:15:20,830 --> 00:15:23,330 You're going to get screwed up if you look at the antecedent 337 00:15:23,330 --> 00:15:25,190 in backward chaining first. 338 00:15:25,190 --> 00:15:27,170 It's backwards partially for a reason. 339 00:15:27,170 --> 00:15:28,950 You need to look at the consequent. 340 00:15:28,950 --> 00:15:30,040 Now why is that? 341 00:15:30,040 --> 00:15:32,550 Well, let's say there is a rule six that 342 00:15:32,550 --> 00:15:37,310 said if x becomes Hermione's friend, 343 00:15:37,310 --> 00:15:43,090 then Hermione feeds x Polyjuice Potion, or something like that. 344 00:15:43,090 --> 00:15:45,150 Will that rule help us in back chaining 345 00:15:45,150 --> 00:15:49,072 to figure out if Millicent becomes Hermione's friend? 346 00:15:49,072 --> 00:15:51,229 AUDIENCE: [INAUDIBLE] 347 00:15:51,229 --> 00:15:53,270 MARK SEIFTER: Some people are shaking their head. 348 00:15:53,270 --> 00:15:55,760 But think about it, will that rule be able to prove it? 349 00:15:55,760 --> 00:15:56,280 No. 350 00:15:56,280 --> 00:15:58,120 Now, if they do become Hermione's friend 351 00:15:58,120 --> 00:15:59,300 and we want to do some forward chaining, 352 00:15:59,300 --> 00:16:00,758 we'll figure out that they're going 353 00:16:00,758 --> 00:16:03,240 to transmute into some kind of other thing because 354 00:16:03,240 --> 00:16:04,240 of the Polyjuice Potion. 355 00:16:04,240 --> 00:16:06,040 But it's not going to help us do the one 356 00:16:06,040 --> 00:16:07,581 thing we want to back chain, which is 357 00:16:07,581 --> 00:16:08,912 to prove that thing on the top. 358 00:16:08,912 --> 00:16:10,620 So we actually need to look for something 359 00:16:10,620 --> 00:16:13,110 that has our current goal in its consequent. 360 00:16:13,110 --> 00:16:14,640 Then we add on the antecedents. 361 00:16:14,640 --> 00:16:17,430 As people I've asked so far-- sorry, I 362 00:16:17,430 --> 00:16:19,110 don't know your names-- like Patrick, 363 00:16:19,110 --> 00:16:22,700 have correctly given me every time, which is excellent. 364 00:16:22,700 --> 00:16:26,400 So notice also that she didn't say 365 00:16:26,400 --> 00:16:28,955 x studies a lot needs to be added to the goal tree. 366 00:16:28,955 --> 00:16:31,195 She said Millicent studies a lot. 367 00:16:31,195 --> 00:16:32,290 Oh, another question. 368 00:16:32,290 --> 00:16:34,410 Great. 369 00:16:34,410 --> 00:16:38,200 AUDIENCE: So obviously after putting rule 4 there, 370 00:16:38,200 --> 00:16:41,837 shouldn't we first check the assertions-- check 371 00:16:41,837 --> 00:16:44,405 on the assertions instead of our conditions [INAUDIBLE] 372 00:16:47,000 --> 00:16:48,540 MARK SEIFTER: So the question is, 373 00:16:48,540 --> 00:16:50,700 once we put rule four in there, should 374 00:16:50,700 --> 00:16:52,885 we check to see if those antecedents of rule four 375 00:16:52,885 --> 00:16:57,110 are already in the assertions before checking other rules? 376 00:16:57,110 --> 00:16:58,100 The answer? 377 00:16:58,100 --> 00:17:01,110 You're not only correct, sir, you're exactly one step ahead. 378 00:17:01,110 --> 00:17:04,010 So I'm going to assume I called on you for the very next thing. 379 00:17:04,010 --> 00:17:07,770 That's exactly what we do once we draw it onto the tree. 380 00:17:07,770 --> 00:17:10,000 You're exactly on the way. 381 00:17:10,000 --> 00:17:12,099 Further question? 382 00:17:12,099 --> 00:17:14,130 Perfect. 383 00:17:14,130 --> 00:17:16,760 All right, great. 384 00:17:16,760 --> 00:17:19,994 So again, we're putting up Millicent studies a lot. 385 00:17:19,994 --> 00:17:21,119 Millicent is a protagonist. 386 00:17:21,119 --> 00:17:23,530 We're not putting up x. 387 00:17:23,530 --> 00:17:25,190 Some people did that. 388 00:17:25,190 --> 00:17:28,200 And of course it's an n node as we heard. 389 00:17:28,200 --> 00:17:30,970 We need them both to be true or we're not going 390 00:17:30,970 --> 00:17:32,300 to be able to continue onward. 391 00:17:32,300 --> 00:17:35,860 So we have-- I'm going to use m for Millicent. 392 00:17:35,860 --> 00:17:39,580 Millicent studies a lot. 393 00:17:39,580 --> 00:17:44,680 Also over here, Millicent is a protagonist. 394 00:17:49,361 --> 00:17:51,860 And we've already heard that we need 395 00:17:51,860 --> 00:17:54,430 to search in the assertions before we 396 00:17:54,430 --> 00:17:58,315 go into any rules for what we're looking for next. 397 00:17:58,315 --> 00:18:00,690 The question is, what are we looking for next and in what 398 00:18:00,690 --> 00:18:01,290 order? 399 00:18:01,290 --> 00:18:03,540 This is where that thing I told you about depth search 400 00:18:03,540 --> 00:18:04,860 is crucial. 401 00:18:04,860 --> 00:18:06,944 We are going to look here on the left node. 402 00:18:06,944 --> 00:18:09,360 And if it has any children, if we have to keep going down, 403 00:18:09,360 --> 00:18:13,470 we are not going to look here yet. 404 00:18:13,470 --> 00:18:14,810 There's a few reasons for that. 405 00:18:14,810 --> 00:18:16,200 One of which is that we're lazy. 406 00:18:16,200 --> 00:18:18,290 The evaluation, if you learned about it, 407 00:18:18,290 --> 00:18:21,350 is also-- if you learn about lazy evaluation, is also lazy. 408 00:18:21,350 --> 00:18:23,845 And if we can disprove this study's a lot branch, 409 00:18:23,845 --> 00:18:26,220 we don't have to do any work with the protagonist branch. 410 00:18:26,220 --> 00:18:26,720 We're done. 411 00:18:26,720 --> 00:18:28,110 We're out of here. 412 00:18:28,110 --> 00:18:31,270 And it's a loss. 413 00:18:31,270 --> 00:18:34,460 So we're going to move down the study's a lot branch. 414 00:18:34,460 --> 00:18:36,360 And we already heard from the audience, 415 00:18:36,360 --> 00:18:39,250 we need to look to see if it's in the assertions. 416 00:18:39,250 --> 00:18:43,020 Everyone, is Millicent studies a lot in the assertions? 417 00:18:43,020 --> 00:18:45,430 No, it's not. 418 00:18:45,430 --> 00:18:48,560 Well then, now we're going to get to that question 419 00:18:48,560 --> 00:18:52,000 that I had before about the antecedent or the consequent. 420 00:18:52,000 --> 00:18:55,192 Because study lies here in the antecedent of rule four, 421 00:18:55,192 --> 00:18:57,400 but we're not going to be able to use rule four here. 422 00:18:57,400 --> 00:18:59,920 In fact, that's how we got here in the first place. 423 00:18:59,920 --> 00:19:05,950 So the question is-- let's see, the question 424 00:19:05,950 --> 00:19:12,360 is, do we have a rule in the consequent that matches 425 00:19:12,360 --> 00:19:14,952 Millicent studies a lot. 426 00:19:14,952 --> 00:19:15,910 Yeah, that's right, P3. 427 00:19:19,030 --> 00:19:19,730 That's right. 428 00:19:19,730 --> 00:19:23,280 So P3 would give us Millicent studies a lot. 429 00:19:23,280 --> 00:19:28,180 And so therefore what will we add to the goal tree? 430 00:19:28,180 --> 00:19:31,655 AUDIENCE: We add both that is Millicent either a protagonist 431 00:19:31,655 --> 00:19:33,150 or a villain and [INAUDIBLE]. 432 00:19:33,150 --> 00:19:34,920 MARK SEIFTER: Yeah, she. 433 00:19:34,920 --> 00:19:37,950 Turns out to be a girl. 434 00:19:37,950 --> 00:19:39,900 So that's exactly right. 435 00:19:39,900 --> 00:19:42,920 We heard that we need to add-- we 436 00:19:42,920 --> 00:19:46,845 need to add an AND node, which also has an OR 437 00:19:46,845 --> 00:19:48,480 node at the bottom of it, because this 438 00:19:48,480 --> 00:19:50,650 is a little bit of a complicated rule. 439 00:19:50,650 --> 00:19:54,380 So we have an AND node. 440 00:19:54,380 --> 00:19:55,980 So we have an AND node. 441 00:19:55,980 --> 00:19:57,630 And the first thing on the AND node 442 00:19:57,630 --> 00:20:08,230 is Millicent is a protagonist or Millicent is a villain. 443 00:20:12,240 --> 00:20:16,105 And the second thing on the AND node is Millicent is ambitious. 444 00:20:19,525 --> 00:20:21,650 Actually, that is the second thing on the AND node. 445 00:20:21,650 --> 00:20:23,390 I hope that's what I said. 446 00:20:23,390 --> 00:20:24,525 All right, the second thing on the AND node 447 00:20:24,525 --> 00:20:25,608 is Millicent is ambitious. 448 00:20:29,160 --> 00:20:37,657 So here's our handy little tree. 449 00:20:37,657 --> 00:20:39,490 Now this is where it's important, as I said, 450 00:20:39,490 --> 00:20:41,850 we're doing a depth first search. 451 00:20:41,850 --> 00:20:44,490 We're going down along the left branch. 452 00:20:44,490 --> 00:20:50,885 So where do you think we're going to go next on this tree? 453 00:20:50,885 --> 00:20:53,350 AUDIENCE: [INAUDIBLE] 454 00:20:53,350 --> 00:20:55,467 MARK SEIFTER: Not quite. 455 00:20:55,467 --> 00:20:56,300 That's a good guess. 456 00:20:56,300 --> 00:20:57,760 You didn't say we're trying to prove 457 00:20:57,760 --> 00:20:59,220 m is a protagonist on the right branch, which 458 00:20:59,220 --> 00:21:00,261 is a very common mistake. 459 00:21:00,261 --> 00:21:01,376 What do you do? 460 00:21:01,376 --> 00:21:02,834 AUDIENCE: You should go down to see 461 00:21:02,834 --> 00:21:05,410 if there's a consequence for m is-- 462 00:21:05,410 --> 00:21:06,870 Millicent is a protagonist. 463 00:21:06,870 --> 00:21:08,210 MARK SEIFTER: Which one of the two Millicent 464 00:21:08,210 --> 00:21:09,835 is a protagonist do we want to look at? 465 00:21:12,232 --> 00:21:13,440 Yeah, the farthest down left. 466 00:21:13,440 --> 00:21:14,800 That's right. 467 00:21:14,800 --> 00:21:16,624 So you guys will learn depth for search 468 00:21:16,624 --> 00:21:18,290 on Monday, at which point it will become 469 00:21:18,290 --> 00:21:19,498 much clearer what I'm saying. 470 00:21:19,498 --> 00:21:22,530 But yeah, you always follow the left branch as far down 471 00:21:22,530 --> 00:21:23,947 as you can. 472 00:21:23,947 --> 00:21:26,030 Then you take the right branch of that same branch 473 00:21:26,030 --> 00:21:27,585 that you followed. 474 00:21:27,585 --> 00:21:29,710 Great, so we're going to try to find that Millicent 475 00:21:29,710 --> 00:21:30,980 is a protagonist. 476 00:21:30,980 --> 00:21:32,800 What do we do first? 477 00:21:32,800 --> 00:21:34,332 Everyone? 478 00:21:34,332 --> 00:21:36,016 Check assertion, yes. 479 00:21:36,016 --> 00:21:36,640 Is it in there? 480 00:21:36,640 --> 00:21:37,970 No, it's not. 481 00:21:37,970 --> 00:21:38,990 OK. 482 00:21:38,990 --> 00:21:42,150 So, therefore we're going to try to find 483 00:21:42,150 --> 00:21:47,270 a rule as we heard about whether Millicent is a protagonist. 484 00:21:47,270 --> 00:21:51,740 So, all the way in the back? 485 00:21:51,740 --> 00:21:54,938 All the way in the back, is there a rule that matches? 486 00:21:54,938 --> 00:21:56,157 AUDIENCE: [INAUDIBLE] 487 00:21:56,157 --> 00:21:57,990 MARK SEIFTER: That matches in its consequent 488 00:21:57,990 --> 00:22:00,810 that Millicent is a protagonist. 489 00:22:00,810 --> 00:22:05,712 AUDIENCE: Um, there is a rule. 490 00:22:05,712 --> 00:22:06,420 MARK SEIFTER: OK. 491 00:22:06,420 --> 00:22:07,590 Well, let's give it a try. 492 00:22:07,590 --> 00:22:08,637 Which one? 493 00:22:08,637 --> 00:22:09,220 AUDIENCE: One. 494 00:22:09,220 --> 00:22:10,761 MARK SEIFTER: Rule one, that's right. 495 00:22:10,761 --> 00:22:15,380 So therefore, we would have to add what to our goal tree? 496 00:22:15,380 --> 00:22:18,419 AUDIENCE: Another [INAUDIBLE]. 497 00:22:18,419 --> 00:22:19,252 MARK SEIFTER: Right. 498 00:22:19,252 --> 00:22:21,188 And what's on that please? 499 00:22:24,092 --> 00:22:25,060 AUDIENCE: [INAUDIBLE] 500 00:22:25,060 --> 00:22:27,238 MARK SEIFTER: Yeah, Millicent lives in Gryffindor Tower, 501 00:22:27,238 --> 00:22:27,738 perfect. 502 00:22:27,738 --> 00:22:31,550 So, our new thing that we're searching for 503 00:22:31,550 --> 00:22:35,350 is-- pretend this connects. 504 00:22:35,350 --> 00:22:37,170 Actually, I guess it does connect. 505 00:22:37,170 --> 00:22:41,860 We're looking for m lives in Gryffindor Tower. 506 00:22:41,860 --> 00:22:43,484 Great. 507 00:22:43,484 --> 00:22:45,650 And since it's depth first, that's where we go next. 508 00:22:45,650 --> 00:22:47,270 Great, we're on a roll. 509 00:22:47,270 --> 00:22:50,792 So what do we do first? 510 00:22:50,792 --> 00:22:53,440 Do we have that in assertions? 511 00:22:53,440 --> 00:22:55,750 Some people say yes, but the answer is no. 512 00:22:55,750 --> 00:22:58,910 We have, in fact, Seamus living in Gryffindor Tower. 513 00:22:58,910 --> 00:23:00,390 Most of you said "no." 514 00:23:00,390 --> 00:23:01,000 You're right. 515 00:23:01,000 --> 00:23:02,650 The majority rules. 516 00:23:02,650 --> 00:23:04,310 We don't have any assertions. 517 00:23:04,310 --> 00:23:08,180 However, do we have a rule with that in the consequent? 518 00:23:08,180 --> 00:23:08,920 No. 519 00:23:08,920 --> 00:23:09,690 So what do we do? 520 00:23:13,647 --> 00:23:15,980 People are saying different things that are all correct. 521 00:23:15,980 --> 00:23:16,790 Backtrack, you say. 522 00:23:16,790 --> 00:23:17,420 Go to the next. 523 00:23:17,420 --> 00:23:18,170 We can't prove it. 524 00:23:18,170 --> 00:23:20,520 All correct. 525 00:23:20,520 --> 00:23:22,960 Put a big x. 526 00:23:22,960 --> 00:23:24,282 This isn't true. 527 00:23:24,282 --> 00:23:24,990 Now we'd look up. 528 00:23:24,990 --> 00:23:26,100 We're on an OR node. 529 00:23:26,100 --> 00:23:32,490 So we're not done yet because either of those can be true. 530 00:23:32,490 --> 00:23:36,120 So now we go back up, backtrack, Millicent is a villain. 531 00:23:38,850 --> 00:23:40,778 What do we do first? 532 00:23:40,778 --> 00:23:42,152 Check assertions. 533 00:23:42,152 --> 00:23:43,070 Is it in there? 534 00:23:43,070 --> 00:23:44,330 No, it's not. 535 00:23:44,330 --> 00:23:46,880 Don't worry, we're getting to one where it will be, 536 00:23:46,880 --> 00:23:50,460 where about 40%-- or 30% to 40% of the class lost 537 00:23:50,460 --> 00:23:54,160 points, very, very soon. 538 00:23:54,160 --> 00:23:58,770 So, we see that Millicent is a villain. 539 00:23:58,770 --> 00:24:00,430 And it's not in the assertions. 540 00:24:00,430 --> 00:24:03,930 So therefore, is there any rule that 541 00:24:03,930 --> 00:24:06,230 has that in its consequent? 542 00:24:09,684 --> 00:24:10,559 AUDIENCE: [INAUDIBLE] 543 00:24:12,749 --> 00:24:15,040 MARK SEIFTER: We're looking for Millicent is a villain. 544 00:24:17,658 --> 00:24:18,533 AUDIENCE: [INAUDIBLE] 545 00:24:22,902 --> 00:24:24,360 MARK SEIFTER: Oh, you can't see it. 546 00:24:24,360 --> 00:24:26,200 All right, I will move it down slightly. 547 00:24:26,200 --> 00:24:29,422 It got a little bit off kilter when I put in the parentheses 548 00:24:29,422 --> 00:24:30,130 around the "and." 549 00:24:30,130 --> 00:24:32,350 Hold on. 550 00:24:32,350 --> 00:24:32,900 There you go. 551 00:24:36,830 --> 00:24:41,150 AUDIENCE: If [INAUDIBLE] is a protagonist or is a villain. 552 00:24:41,150 --> 00:24:43,422 [INAUDIBLE] 553 00:24:43,422 --> 00:24:44,880 MARK SEIFTER: We're trying to prove 554 00:24:44,880 --> 00:24:46,088 that she's a villain, though. 555 00:24:46,088 --> 00:24:49,255 So do we have any with that in the consequent? 556 00:24:49,255 --> 00:24:50,755 [INAUDIBLE] anything that will prove 557 00:24:50,755 --> 00:24:53,070 that she's a villain if we fire off that rule. 558 00:24:56,150 --> 00:24:58,162 Want to give here a little bit of help? 559 00:24:58,162 --> 00:24:58,703 AUDIENCE: P2. 560 00:24:58,703 --> 00:25:01,569 If she lives in Slytherin, then she's a villain [INAUDIBLE]. 561 00:25:01,569 --> 00:25:02,860 MARK SEIFTER: Ah, see that now? 562 00:25:02,860 --> 00:25:05,200 It had two, so it was a little bit harder. 563 00:25:05,200 --> 00:25:07,510 Now some people ask, what about that ambitious thing? 564 00:25:07,510 --> 00:25:09,426 Can we like add that to the tree or something? 565 00:25:09,426 --> 00:25:10,190 No. 566 00:25:10,190 --> 00:25:12,800 The backward chainer is single-minded, focused, 567 00:25:12,800 --> 00:25:14,097 and stupid. 568 00:25:14,097 --> 00:25:16,430 Even though it's later going to need to prove that she's 569 00:25:16,430 --> 00:25:18,239 ambitious, it doesn't care. 570 00:25:18,239 --> 00:25:19,530 It just sees the villain there. 571 00:25:19,530 --> 00:25:21,200 Villain, oh, that's great. 572 00:25:21,200 --> 00:25:23,370 As long as we've got the antecedent 573 00:25:23,370 --> 00:25:27,690 we are going to be happy. 574 00:25:27,690 --> 00:25:29,290 This is actually an important point, 575 00:25:29,290 --> 00:25:32,200 not in this particular problem, but in some other problems. 576 00:25:32,200 --> 00:25:36,280 So by using P2, we're obviously going 577 00:25:36,280 --> 00:25:40,151 to have the antecedent x lives in Slytherin dungeon. 578 00:25:40,151 --> 00:25:41,150 And x here is Millicent. 579 00:25:41,150 --> 00:25:42,816 So Millicent lives in Slytherin dungeon. 580 00:25:47,720 --> 00:25:49,600 All right, so what's the first thing 581 00:25:49,600 --> 00:25:51,380 we do when we see this new assertion? 582 00:25:54,430 --> 00:25:55,430 We check the assertions. 583 00:25:55,430 --> 00:25:56,910 Is it in there? 584 00:25:56,910 --> 00:25:57,600 Yes. 585 00:25:57,600 --> 00:25:59,183 That's not where everyone lost points, 586 00:25:59,183 --> 00:26:01,314 but yes, it is in there. 587 00:26:01,314 --> 00:26:02,290 Check. 588 00:26:02,290 --> 00:26:05,260 This OR node is happy. 589 00:26:05,260 --> 00:26:08,680 Now we move up to the AND node with Millicent is ambitious. 590 00:26:08,680 --> 00:26:11,080 So Millicent is ambitious. 591 00:26:11,080 --> 00:26:11,830 What do we do now? 592 00:26:14,830 --> 00:26:18,770 AUDIENCE: So isn't the consequent of P2 593 00:26:18,770 --> 00:26:21,210 that x is a villain and x is ambitious. 594 00:26:21,210 --> 00:26:25,114 I don't know if it's [INAUDIBLE] or whatever, 595 00:26:25,114 --> 00:26:28,042 but in our assertions we have that Millicent is ambitious. 596 00:26:28,042 --> 00:26:29,994 Is that necessary to let us-- 597 00:26:29,994 --> 00:26:31,954 MARK SEIFTER: To let us use rule two. 598 00:26:31,954 --> 00:26:33,940 Actually, no. 599 00:26:33,940 --> 00:26:40,660 The question is, do we need the x is 600 00:26:40,660 --> 00:26:45,520 ambitious to be in our list of assertions in order to use P2. 601 00:26:45,520 --> 00:26:48,280 For instance, if we didn't have the assertion that Millicent 602 00:26:48,280 --> 00:26:51,167 is ambitious, would P2 have a problem firing? 603 00:26:54,030 --> 00:26:56,315 So, it's a very interesting question. 604 00:26:56,315 --> 00:26:57,940 It's sort of what actually I was trying 605 00:26:57,940 --> 00:27:02,140 to mention earlier when I said it's single-minded, 606 00:27:02,140 --> 00:27:04,550 it's focused, it doesn't care about the other one. 607 00:27:04,550 --> 00:27:06,341 Because you might say, well, wait a minute, 608 00:27:06,341 --> 00:27:08,300 P2 could never have actually fired 609 00:27:08,300 --> 00:27:10,520 if it didn't have both of its consequents. 610 00:27:10,520 --> 00:27:14,130 But in fact, the backward chainer doesn't care. 611 00:27:14,130 --> 00:27:16,560 All that the backward chainer is looking to do 612 00:27:16,560 --> 00:27:19,760 is to prove whether or not there's 613 00:27:19,760 --> 00:27:23,880 a possibility that Millicent might be a villain. 614 00:27:23,880 --> 00:27:26,530 It's not trying to say, oh, all the results 615 00:27:26,530 --> 00:27:30,455 of some certain rules are making Millicent a villain 616 00:27:30,455 --> 00:27:33,390 and all the other things that are there, like ambitious, are 617 00:27:33,390 --> 00:27:34,522 in the database. 618 00:27:34,522 --> 00:27:35,730 It's not the forward chainer. 619 00:27:35,730 --> 00:27:37,130 It actually doesn't care. 620 00:27:37,130 --> 00:27:39,560 This sometimes leads to unnecessary computation. 621 00:27:39,560 --> 00:27:42,110 But it's very simple, and it's very simple to code. 622 00:27:42,110 --> 00:27:45,160 So it often will probably speed you up in the long run. 623 00:27:45,160 --> 00:27:48,150 Like if there's, for instance, 100 thing in the then 624 00:27:48,150 --> 00:27:50,226 and you only care about one of them, 625 00:27:50,226 --> 00:27:52,100 it would be a waste, almost, to add those 99. 626 00:27:52,100 --> 00:27:57,030 There's a follow up over here somewhere? 627 00:27:57,030 --> 00:27:57,530 [INAUDIBLE] 628 00:28:00,946 --> 00:28:03,386 AUDIENCE: Order m of 99. 629 00:28:03,386 --> 00:28:04,362 And so [INAUDIBLE] 630 00:28:10,230 --> 00:28:11,740 MARK SEIFTER: You can try. 631 00:28:11,740 --> 00:28:13,600 However, then at that point, every time 632 00:28:13,600 --> 00:28:15,520 you check the assertions, you'd be 633 00:28:15,520 --> 00:28:17,250 attempting to check those 99. 634 00:28:17,250 --> 00:28:19,270 Also, you might not have used those rules. 635 00:28:19,270 --> 00:28:22,660 The question is, could you make a hash table 636 00:28:22,660 --> 00:28:26,190 with all of the 100 things that were in the consequent? 637 00:28:26,190 --> 00:28:28,840 And then, after having made that hash table 638 00:28:28,840 --> 00:28:31,320 since you were already walking through those anyway 639 00:28:31,320 --> 00:28:33,300 when you were checking it, you could add those 640 00:28:33,300 --> 00:28:34,049 to the assertions. 641 00:28:34,049 --> 00:28:36,830 The problem is that you might not necessarily 642 00:28:36,830 --> 00:28:40,200 want-- with the backward chainer-- you might not 643 00:28:40,200 --> 00:28:42,340 necessarily want to think that all 644 00:28:42,340 --> 00:28:46,860 those things in the consequent are necessarily true. 645 00:28:46,860 --> 00:28:49,620 However, you might not care about them. 646 00:28:49,620 --> 00:28:51,590 And then you have to make an order 647 00:28:51,590 --> 00:28:54,090 and computation every time you check that list of assertions 648 00:28:54,090 --> 00:28:55,271 in the upper left. 649 00:28:55,271 --> 00:28:56,146 AUDIENCE: [INAUDIBLE] 650 00:28:59,819 --> 00:29:02,110 MARK SEIFTER: You don't know what assertions there are. 651 00:29:02,110 --> 00:29:04,200 You have to check the entire list of assertions 652 00:29:04,200 --> 00:29:06,240 in the upper left every time you get 653 00:29:06,240 --> 00:29:07,760 to a new node in the goal tree. 654 00:29:07,760 --> 00:29:09,550 So each one is order 1. 655 00:29:09,550 --> 00:29:13,060 But I'm not saying to find a specific assertion is order n. 656 00:29:13,060 --> 00:29:15,530 I'm saying every time you get a new node in the goal tree, 657 00:29:15,530 --> 00:29:17,999 you have to check all the assertions you've added. 658 00:29:17,999 --> 00:29:20,540 AUDIENCE: You have to do that anyway. [INAUDIBLE] assertions. 659 00:29:20,540 --> 00:29:22,748 MARK SEIFTER: Yeah, you'd have to check for the four. 660 00:29:22,748 --> 00:29:26,710 But let's say that there were 10,000 consequents of P2. 661 00:29:26,710 --> 00:29:28,930 You would have to check 10,000 instead of four 662 00:29:28,930 --> 00:29:31,750 if you added them all after proving 663 00:29:31,750 --> 00:29:33,990 P2 was true on the goal tree. 664 00:29:33,990 --> 00:29:37,820 Also, another important note is that you might not 665 00:29:37,820 --> 00:29:39,420 use every branch of the goal tree, 666 00:29:39,420 --> 00:29:41,160 if there's like an OR that's up higher 667 00:29:41,160 --> 00:29:43,110 and you wind up using a different branch, in which case 668 00:29:43,110 --> 00:29:44,901 you'd probably have to make a separate hash 669 00:29:44,901 --> 00:29:47,910 table for every sub-branch that you have 670 00:29:47,910 --> 00:29:50,060 and then remember which hash tables were updated 671 00:29:50,060 --> 00:29:51,850 based on which sub-branch. 672 00:29:51,850 --> 00:29:53,430 And then sub-branches die. 673 00:29:53,430 --> 00:29:56,906 It's probably more effort than it's worth. 674 00:29:56,906 --> 00:29:58,530 It's certainly an interesting question. 675 00:29:58,530 --> 00:30:01,890 It's a great question for a debate in recitation. 676 00:30:01,890 --> 00:30:03,980 Also, I'm happy to talk about it later. 677 00:30:03,980 --> 00:30:07,750 I think that someone who very intelligently made hash tables 678 00:30:07,750 --> 00:30:10,180 and thought the problem through, as Patrick said, 679 00:30:10,180 --> 00:30:12,342 more knowledge can mean a better-- well, 680 00:30:12,342 --> 00:30:14,550 actually maybe he hasn't said more knowledge can mean 681 00:30:14,550 --> 00:30:16,924 a better search because we haven't done that lecture yet, 682 00:30:16,924 --> 00:30:18,020 but-- 683 00:30:18,020 --> 00:30:20,270 AUDIENCE: You're talking about implementation decision 684 00:30:20,270 --> 00:30:23,975 and using hash table might well be a good way to do this. 685 00:30:23,975 --> 00:30:27,056 The problem is that we're presuming some things about how 686 00:30:27,056 --> 00:30:30,444 the rules are firing and what [INAUDIBLE] they're 687 00:30:30,444 --> 00:30:33,832 firing that depend on the order of assertions in the table. 688 00:30:33,832 --> 00:30:36,736 So if we used the hash table, we'd lose the order. 689 00:30:36,736 --> 00:30:38,597 [INAUDIBLE] 690 00:30:38,597 --> 00:30:39,680 MARK SEIFTER: That's true. 691 00:30:39,680 --> 00:30:40,195 That's true. 692 00:30:40,195 --> 00:30:41,820 But I'm thinking like if someone wanted 693 00:30:41,820 --> 00:30:44,790 to make that implementation as like do some research in rules 694 00:30:44,790 --> 00:30:48,890 based systems, it's possible you can increase the running speed. 695 00:30:48,890 --> 00:30:53,260 In this class, we are not completely as focused 696 00:30:53,260 --> 00:30:54,940 on the fastest algorithms. 697 00:30:54,940 --> 00:30:57,440 But I still think that a cool thing to try. 698 00:30:57,440 --> 00:30:59,860 Questions from people in the crowd? 699 00:30:59,860 --> 00:31:00,800 We'll start with you. 700 00:31:00,800 --> 00:31:02,420 AUDIENCE: So ignoring the hash table? 701 00:31:02,420 --> 00:31:03,920 MARK SEIFTER: Ignore the hash table. 702 00:31:03,920 --> 00:31:06,296 That's a good idea because it's a little extra enrichment 703 00:31:06,296 --> 00:31:06,795 thing. 704 00:31:06,795 --> 00:31:08,500 It's not anything you would possibly 705 00:31:08,500 --> 00:31:10,646 need to know for the quiz. 706 00:31:10,646 --> 00:31:14,630 AUDIENCE: [INAUDIBLE] So if it became 707 00:31:14,630 --> 00:31:17,618 an [INAUDIBLE] are you using this "then" statement 708 00:31:17,618 --> 00:31:19,610 because you want the villain. 709 00:31:19,610 --> 00:31:23,096 So along with using this you get x is ambitious. 710 00:31:23,096 --> 00:31:26,582 [INAUDIBLE] used after that, another "then" statement 711 00:31:26,582 --> 00:31:29,072 that we also use that says x is not ambitious. 712 00:31:29,072 --> 00:31:31,845 So how would you resolve that? 713 00:31:31,845 --> 00:31:33,220 MARK SEIFTER: So the question is, 714 00:31:33,220 --> 00:31:36,370 let's say you used rule two somewhere in the tree 715 00:31:36,370 --> 00:31:38,480 to get that x is a villain, which 716 00:31:38,480 --> 00:31:40,480 then says that x is ambitious. 717 00:31:40,480 --> 00:31:44,900 Then later, you have x is not ambitious 718 00:31:44,900 --> 00:31:50,192 somewhere in one of the other rules that you then later need. 719 00:31:50,192 --> 00:31:51,900 The question is, how do you resolve that? 720 00:31:51,900 --> 00:31:52,750 What does it do? 721 00:31:52,750 --> 00:31:53,705 Well, first of all-- 722 00:31:53,705 --> 00:31:54,580 AUDIENCE: [INAUDIBLE] 723 00:31:59,130 --> 00:32:00,880 MARK SEIFTER: First of all, interestingly, 724 00:32:00,880 --> 00:32:05,537 if it says x is not ambitious-- literally like that. 725 00:32:05,537 --> 00:32:06,870 And I'm not being pedantic here. 726 00:32:06,870 --> 00:32:08,245 This is one of the tricks someone 727 00:32:08,245 --> 00:32:11,060 played in a previous quiz. 728 00:32:11,060 --> 00:32:13,050 You can have that and x is ambitious 729 00:32:13,050 --> 00:32:16,340 both in the list because it's a dumb rules-based system it 730 00:32:16,340 --> 00:32:19,190 doesn't know that you can't have both of those on the list. 731 00:32:19,190 --> 00:32:22,760 So if you have a positive assertion in a consequent, 732 00:32:22,760 --> 00:32:25,990 x is not ambitious in a consequent, x is not ambitious, 733 00:32:25,990 --> 00:32:29,000 it'll be happy to add Millicent is not ambitious 734 00:32:29,000 --> 00:32:31,730 while Millicent ambitious this is already there, 735 00:32:31,730 --> 00:32:33,020 because it's stupid. 736 00:32:33,020 --> 00:32:35,490 Now if it had delete Millicent is 737 00:32:35,490 --> 00:32:37,740 ambitious in the consequent and deleted something that 738 00:32:37,740 --> 00:32:44,110 was previously there, that would be an interesting problem. 739 00:32:44,110 --> 00:32:46,406 It could cause mistakes. 740 00:32:46,406 --> 00:32:47,780 Your back chaining would probably 741 00:32:47,780 --> 00:32:49,196 make the mistake of allowing this. 742 00:32:49,196 --> 00:32:53,580 However, this is exactly what we do not, I believe as a policy, 743 00:32:53,580 --> 00:32:55,795 do not have DELETE statements on the quizzes. 744 00:32:58,496 --> 00:32:59,870 At least previous quizzes did not 745 00:32:59,870 --> 00:33:02,170 have them, except for in a hypothetical 746 00:33:02,170 --> 00:33:04,480 of what happens if we add a DELETE statement here. 747 00:33:04,480 --> 00:33:06,480 I don't think we've ever made people work things 748 00:33:06,480 --> 00:33:07,610 through with the delete. 749 00:33:07,610 --> 00:33:10,910 Delete would possibly cause some issues. 750 00:33:10,910 --> 00:33:12,460 Question in the back? 751 00:33:12,460 --> 00:33:13,930 AUDIENCE: So, just to check this, 752 00:33:13,930 --> 00:33:16,053 we're doing backwards chaining, we 753 00:33:16,053 --> 00:33:18,350 don't actually add assertions to your [INAUDIBLE]. 754 00:33:18,350 --> 00:33:20,230 MARK SEIFTER: Never add assertions in backward chain 755 00:33:20,230 --> 00:33:21,188 to the assertion table. 756 00:33:21,188 --> 00:33:22,840 It's dumb. 757 00:33:22,840 --> 00:33:23,890 The system is dumb. 758 00:33:23,890 --> 00:33:25,850 I'm not saying it's a dumb idea to do this. 759 00:33:25,850 --> 00:33:28,040 It's actually pretty fast to do it this way. 760 00:33:28,040 --> 00:33:29,840 But the system is dumb. 761 00:33:29,840 --> 00:33:32,204 The question is, do you add assertions 762 00:33:32,204 --> 00:33:33,370 or you don't add assertions? 763 00:33:33,370 --> 00:33:34,610 You do not. 764 00:33:34,610 --> 00:33:37,350 You simply go through, checking all the things on your goal 765 00:33:37,350 --> 00:33:40,050 tree until the goal tree is either proven or disproven, 766 00:33:40,050 --> 00:33:42,530 then you're out of here. 767 00:33:42,530 --> 00:33:44,660 So, cool so far, everyone? 768 00:33:44,660 --> 00:33:46,080 Good questions from everyone. 769 00:33:46,080 --> 00:33:47,790 These are all questions that are things 770 00:33:47,790 --> 00:33:49,300 that often trip people up. 771 00:33:49,300 --> 00:33:51,190 So, our next thing, Millicent is ambitious. 772 00:33:51,190 --> 00:33:53,259 We sort of-- the cat is out of the bag 773 00:33:53,259 --> 00:33:55,300 because there is a question mentioning that there 774 00:33:55,300 --> 00:33:57,130 is an assertion that says that. 775 00:33:57,130 --> 00:34:01,290 But I direct you guys to our favorite rule, rule two. 776 00:34:01,290 --> 00:34:03,000 Shouldn't we use rule two to prove 777 00:34:03,000 --> 00:34:05,480 that Millicent is ambitious? 778 00:34:05,480 --> 00:34:08,010 The answer is if you want to lose four points or however 779 00:34:08,010 --> 00:34:09,420 many points, then yes. 780 00:34:09,420 --> 00:34:11,130 But if you don't want to lose points, 781 00:34:11,130 --> 00:34:22,280 then this is already correct by virtue of assertion one. 782 00:34:22,280 --> 00:34:26,250 So I guess I should write, also, that this over here, 783 00:34:26,250 --> 00:34:33,840 Millicent studies a lot rule, this rule is rule four. 784 00:34:33,840 --> 00:34:36,210 Yeah, that's rule four [INAUDIBLE] and protagonist. 785 00:34:36,210 --> 00:34:40,980 Down here to prove that she studies a lot is rule three. 786 00:34:40,980 --> 00:34:48,989 And then at the bottom here we have what rules here? 787 00:34:48,989 --> 00:34:52,870 We have the protagonist rule, which is one, 788 00:34:52,870 --> 00:34:55,610 and the villain rule which is two. 789 00:34:58,330 --> 00:35:01,250 This is correct virtue of A0. 790 00:35:04,500 --> 00:35:06,390 OK, great. 791 00:35:06,390 --> 00:35:08,670 So we've proved this whole AND node. 792 00:35:08,670 --> 00:35:10,700 We know that Millicent studies a lot. 793 00:35:10,700 --> 00:35:12,824 But now we're going to have to go a little bit more 794 00:35:12,824 --> 00:35:16,080 quickly based on time, and so I will do the remaining things. 795 00:35:16,080 --> 00:35:18,270 Anyone who has not been called on is off the hook. 796 00:35:18,270 --> 00:35:19,760 But that doesn't mean not to pay attention 797 00:35:19,760 --> 00:35:22,100 because there's some interesting stuff still to come. 798 00:35:22,100 --> 00:35:24,350 So, Millicent is a protagonist. 799 00:35:24,350 --> 00:35:27,460 Well, good news, everyone. 800 00:35:27,460 --> 00:35:29,770 There's one other reason that I can do this 801 00:35:29,770 --> 00:35:32,500 and that's that you've already told me what I need to do. 802 00:35:32,500 --> 00:35:37,810 Most is a protagonist, you use rule one, rule one. 803 00:35:37,810 --> 00:35:40,580 And check if she lives in Gryffindor tower. 804 00:35:40,580 --> 00:35:43,031 Now, will it do it again? 805 00:35:43,031 --> 00:35:44,340 Yes it will. 806 00:35:44,340 --> 00:35:47,715 It hasn't cached that it's already tried that. 807 00:35:47,715 --> 00:35:49,840 Now, hash table not withstanding, caching something 808 00:35:49,840 --> 00:35:52,810 you've already tried may be a good idea with backward 809 00:35:52,810 --> 00:35:55,070 chaining, but we do not do that in this class. 810 00:35:55,070 --> 00:35:56,610 That's an implementation detail. 811 00:35:56,610 --> 00:35:58,672 It's another idea of something you can do. 812 00:35:58,672 --> 00:36:00,630 We don't catch things that we've already tried. 813 00:36:00,630 --> 00:36:03,250 We try them again, dammit. 814 00:36:03,250 --> 00:36:06,170 And when we try it again, maybe it'll work this time. 815 00:36:06,170 --> 00:36:07,390 No, it never works. 816 00:36:07,390 --> 00:36:09,725 It never works this time. 817 00:36:09,725 --> 00:36:10,490 This fails. 818 00:36:10,490 --> 00:36:12,000 This AND node fails. 819 00:36:12,000 --> 00:36:13,880 The whole thing fails. 820 00:36:13,880 --> 00:36:15,820 They're not friends at all. 821 00:36:15,820 --> 00:36:19,310 They're bitter enemies. 822 00:36:19,310 --> 00:36:22,120 Millicent does not become Hermione's friend. 823 00:36:22,120 --> 00:36:24,510 So now they ask us a few questions 824 00:36:24,510 --> 00:36:28,020 which are pretty easy to answer based on the ordeal we've just 825 00:36:28,020 --> 00:36:28,950 been through. 826 00:36:28,950 --> 00:36:32,580 So, determine the minimum number of additional assertions 827 00:36:32,580 --> 00:36:34,450 that we would need to add for Millicent 828 00:36:34,450 --> 00:36:38,180 to become Hermione's friend. 829 00:36:38,180 --> 00:36:40,740 But you're not allowed to add an assertion that 830 00:36:40,740 --> 00:36:43,820 matches a consequent of a rule. 831 00:36:43,820 --> 00:36:47,060 You can only add an assertion-- in other words, 832 00:36:47,060 --> 00:36:51,030 you can't add an assertion that will prove some other rules. 833 00:36:51,030 --> 00:36:55,090 You have to add an assertion that directly-- yeah, 834 00:36:55,090 --> 00:36:56,880 that's basically the rule here. 835 00:36:56,880 --> 00:36:58,820 Because there's a lot of choices. 836 00:36:58,820 --> 00:37:01,440 But he wanted one particular answer. 837 00:37:01,440 --> 00:37:03,105 And so can anyone think of an assertion 838 00:37:03,105 --> 00:37:06,650 that doesn't match any consequent of any rule that 839 00:37:06,650 --> 00:37:11,560 will make her be Hermione's friend. 840 00:37:11,560 --> 00:37:13,680 A lot of people say Millicent lives in Gryffindor. 841 00:37:13,680 --> 00:37:14,304 That's correct. 842 00:37:14,304 --> 00:37:16,640 So, part three, your solution to part two 843 00:37:16,640 --> 00:37:18,650 causes an uncommon situation. 844 00:37:18,650 --> 00:37:21,140 What is the uncommon situation? 845 00:37:21,140 --> 00:37:23,780 And what should you do to the list of assertions 846 00:37:23,780 --> 00:37:24,770 to solve this problem? 847 00:37:27,207 --> 00:37:29,040 Does anyone know what the uncommon situation 848 00:37:29,040 --> 00:37:31,300 would be if we added that she lives in Gryffindor? 849 00:37:31,300 --> 00:37:32,330 Hand is raised up here. 850 00:37:32,330 --> 00:37:33,935 What is your answer? 851 00:37:33,935 --> 00:37:36,687 [INAUDIBLE] That's true. 852 00:37:36,687 --> 00:37:38,270 She lives in Gryffindor and Slytherin. 853 00:37:38,270 --> 00:37:41,742 So how would you fix that? 854 00:37:41,742 --> 00:37:46,090 [INAUDIBLE] Yes, you could take out 855 00:37:46,090 --> 00:37:49,270 Slytherin from the assertions and say that she only 856 00:37:49,270 --> 00:37:50,540 lived in Gryffindor. 857 00:37:50,540 --> 00:37:54,159 A lot of people gave the answer to this question, 858 00:37:54,159 --> 00:37:55,700 which is a perfectly reasonable thing 859 00:37:55,700 --> 00:37:57,270 to do in a rules-basis system. 860 00:37:57,270 --> 00:37:59,440 They said, well, we can add a rule that 861 00:37:59,440 --> 00:38:06,060 says that if you live in x and y is different than x, then 862 00:38:06,060 --> 00:38:08,040 you can't live in y. 863 00:38:08,040 --> 00:38:10,520 The problem with that, among other things, 864 00:38:10,520 --> 00:38:13,290 is that we asked for a way to change the assertions and not 865 00:38:13,290 --> 00:38:13,850 the rules. 866 00:38:13,850 --> 00:38:15,340 And you gave us a way to change the assertions. 867 00:38:15,340 --> 00:38:16,340 That's the right answer. 868 00:38:22,310 --> 00:38:25,210 There was another backward chaining problem, 869 00:38:25,210 --> 00:38:32,030 this is 2009 quiz one, and I will leave it off 870 00:38:32,030 --> 00:38:32,800 for the moment. 871 00:38:32,800 --> 00:38:35,110 You guys should take a look at it, 872 00:38:35,110 --> 00:38:37,550 in particular with variable binding. 873 00:38:37,550 --> 00:38:40,150 Because remember, you always have to bind 874 00:38:40,150 --> 00:38:42,171 the variable that's relevant to you. 875 00:38:42,171 --> 00:38:43,920 But that doesn't mean that you always have 876 00:38:43,920 --> 00:38:45,460 to bind all of the variables. 877 00:38:45,460 --> 00:38:47,270 For instance, let's say that we wanted 878 00:38:47,270 --> 00:38:49,290 to prove that Millicent has a bad term, which 879 00:38:49,290 --> 00:38:51,081 as it turns out, is what we wanted to prove 880 00:38:51,081 --> 00:38:52,490 in the other backward chaining. 881 00:38:52,490 --> 00:38:57,549 Very quickly and without doing the problem, can anyone who 882 00:38:57,549 --> 00:38:59,840 thinks they're very clever at backward chaining tell me 883 00:38:59,840 --> 00:39:03,860 exactly what things would be added to the goal tree 884 00:39:03,860 --> 00:39:05,590 to prove that Millicent has a bad term? 885 00:39:05,590 --> 00:39:06,256 Raise your hand. 886 00:39:06,256 --> 00:39:08,350 I won't pick out a victim because I'm asking 887 00:39:08,350 --> 00:39:09,955 this to happen pretty quickly. 888 00:39:12,750 --> 00:39:13,330 No one? 889 00:39:18,190 --> 00:39:20,732 All right. 890 00:39:20,732 --> 00:39:25,405 AUDIENCE: You would add the three antecedents to rule-- 891 00:39:25,405 --> 00:39:26,530 MARK SEIFTER: To rule five. 892 00:39:26,530 --> 00:39:28,580 So what would you add specifically? 893 00:39:28,580 --> 00:39:30,282 AUDIENCE: For anyone, variable-wise, 894 00:39:30,282 --> 00:39:32,365 you would just have to show that there is at least 895 00:39:32,365 --> 00:39:34,160 one person who matches. 896 00:39:34,160 --> 00:39:36,860 MARK SEIFTER: So can you just sort of read out, 897 00:39:36,860 --> 00:39:39,580 what would the first thing say with the snogs? 898 00:39:39,580 --> 00:39:44,200 AUDIENCE: X snogs-- or Millicent snogs anyone. 899 00:39:44,200 --> 00:39:47,200 MARK SEIFTER: Yeah, Millicent snogs y. 900 00:39:47,200 --> 00:39:48,120 That's crucial. 901 00:39:48,120 --> 00:39:49,910 Some people did a lot of different things. 902 00:39:49,910 --> 00:39:51,660 Some people put Seamus in already. 903 00:39:51,660 --> 00:39:53,140 You can't do that. 904 00:39:53,140 --> 00:39:55,970 The system is stupid, it doesn't know that the person is Seamus. 905 00:39:55,970 --> 00:39:57,860 Also, some people said it worked, 906 00:39:57,860 --> 00:39:59,610 because look, they're snogging each other, 907 00:39:59,610 --> 00:40:03,130 but it's the wrong snoggle direction up there. 908 00:40:05,650 --> 00:40:07,460 Because we have Seamus snogging Millicent, 909 00:40:07,460 --> 00:40:08,710 not Millicent snogging Seamus. 910 00:40:08,710 --> 00:40:09,418 But yes, exactly. 911 00:40:09,418 --> 00:40:11,440 It would be Millicent snogs y. 912 00:40:11,440 --> 00:40:12,980 Millicent lives in Gryffindor tower. 913 00:40:12,980 --> 00:40:15,160 y lives in Slytherin dungeon. 914 00:40:15,160 --> 00:40:19,930 So, let's give forward chaining all the attention it deserves, 915 00:40:19,930 --> 00:40:22,895 about eight minutes, which will be more than enough. 916 00:40:26,410 --> 00:40:28,570 OK, we still got all these rules. 917 00:40:28,570 --> 00:40:30,410 We've still got all these assertions. 918 00:40:30,410 --> 00:40:33,345 Instead of doing that horrible backward chaining-- well, 919 00:40:33,345 --> 00:40:35,640 it's not that horrible-- but we'll do forward chaining. 920 00:40:35,640 --> 00:40:36,880 It'll be really easy. 921 00:40:36,880 --> 00:40:38,900 We'll just add new assertions as they go. 922 00:40:38,900 --> 00:40:41,260 Remember the tiebreak order. 923 00:40:41,260 --> 00:40:43,400 Rules in order from 0 to 5. 924 00:40:43,400 --> 00:40:46,490 And if the same rule could fire off 925 00:40:46,490 --> 00:40:48,530 with multiple different assertions, 926 00:40:48,530 --> 00:40:51,160 we'll use the assertions in order from 0 to 3. 927 00:40:51,160 --> 00:40:55,160 So let's see. 928 00:40:55,160 --> 00:40:59,530 We don't have much time, but with our four assertions, 929 00:40:59,530 --> 00:41:01,310 let's see, what rules possibly could 930 00:41:01,310 --> 00:41:04,110 match with our four assertions? 931 00:41:04,110 --> 00:41:06,390 Well, I'll figure out for you. 932 00:41:06,390 --> 00:41:09,100 Do we have an assertion about an ambitious person? 933 00:41:09,100 --> 00:41:09,600 Yes. 934 00:41:09,600 --> 00:41:10,720 But they're not a squib. 935 00:41:10,720 --> 00:41:11,917 So not rule zero. 936 00:41:11,917 --> 00:41:13,750 Do we have someone that lives in Gryffindor? 937 00:41:13,750 --> 00:41:14,580 We absolutely do. 938 00:41:14,580 --> 00:41:16,019 Rule one is matches. 939 00:41:16,019 --> 00:41:17,810 Do we have someone that lives in Slytherin? 940 00:41:17,810 --> 00:41:18,560 We do. 941 00:41:18,560 --> 00:41:19,550 Rule two matches. 942 00:41:19,550 --> 00:41:21,850 Do we have a protagonist or a villain? 943 00:41:21,850 --> 00:41:23,680 We don't have any protagonist or villain. 944 00:41:23,680 --> 00:41:26,500 Rule three is not going to match because it's in an "and." 945 00:41:26,500 --> 00:41:28,440 do we have someone who studies a lot? 946 00:41:28,440 --> 00:41:30,149 We do not have someone who studies a lot. 947 00:41:30,149 --> 00:41:31,481 Rule four is not going to match. 948 00:41:31,481 --> 00:41:32,730 Do we have some snogging? 949 00:41:32,730 --> 00:41:34,220 We do have some snogging. 950 00:41:34,220 --> 00:41:36,500 So rule one, two, and five match. 951 00:41:36,500 --> 00:41:40,810 So m for matching, we have one, two and five. 952 00:41:40,810 --> 00:41:43,180 Everyone, which one wins the tiebreak between one, two, 953 00:41:43,180 --> 00:41:44,350 and five? 954 00:41:44,350 --> 00:41:47,070 One, because it comes first numerically. 955 00:41:47,070 --> 00:41:50,740 Which one is rule one if x lives in Gryffindor tower? 956 00:41:50,740 --> 00:41:52,980 The only binding for x is Seamus. 957 00:41:52,980 --> 00:41:54,810 Seamus lives in Gryffindor tower. 958 00:41:54,810 --> 00:41:57,520 We're firing off rule one. 959 00:41:57,520 --> 00:42:01,260 So new assertions, the first assertion that we'll add 960 00:42:01,260 --> 00:42:06,075 is Seamus is it a protagonist. 961 00:42:06,075 --> 00:42:06,575 Great. 962 00:42:09,380 --> 00:42:12,060 Now, there's one other thing, and it's 963 00:42:12,060 --> 00:42:16,590 the main thing I wanted to tell you about in forward chaining. 964 00:42:16,590 --> 00:42:19,420 About our old friend, rule one, now that we've done this, 965 00:42:19,420 --> 00:42:22,940 does rule one still match an assertion in the database? 966 00:42:26,430 --> 00:42:27,450 Yes. 967 00:42:27,450 --> 00:42:28,590 It does. 968 00:42:28,590 --> 00:42:32,186 But what's going to stop us from constantly doing rule one 969 00:42:32,186 --> 00:42:33,810 every time because it comes numerically 970 00:42:33,810 --> 00:42:35,650 before the other rules? 971 00:42:35,650 --> 00:42:38,260 What stops us there is a part of our implementation. 972 00:42:38,260 --> 00:42:40,840 And it's a very important part that people sometimes forget. 973 00:42:40,840 --> 00:42:44,240 It's what I like to call the no-impotent rules 974 00:42:44,240 --> 00:42:45,240 implementation detail. 975 00:42:45,240 --> 00:42:47,220 That is, if a rule is completely, 976 00:42:47,220 --> 00:42:51,190 100% impotent, it would do absolutely nothing. 977 00:42:51,190 --> 00:42:52,505 Then you do not fire it. 978 00:42:52,505 --> 00:42:53,990 You go to the next one. 979 00:42:53,990 --> 00:42:55,200 That's pretty important. 980 00:42:55,200 --> 00:42:57,350 Let's say that you possibly had a delete, which 981 00:42:57,350 --> 00:42:59,660 you won't have on the quiz. 982 00:42:59,660 --> 00:43:02,630 That means that if the thing to delete is missing, 983 00:43:02,630 --> 00:43:03,520 it's impotent. 984 00:43:03,520 --> 00:43:05,720 If the thing to delete is there, it's not impotent 985 00:43:05,720 --> 00:43:07,200 because you can delete. 986 00:43:07,200 --> 00:43:09,990 Let's say you have 500,000 things that you're going 987 00:43:09,990 --> 00:43:11,700 to add to your assertions. 988 00:43:11,700 --> 00:43:15,670 499,999 are already in your database. 989 00:43:15,670 --> 00:43:16,740 One of them is missing. 990 00:43:16,740 --> 00:43:18,390 Is it an impotent rule? 991 00:43:18,390 --> 00:43:19,090 No, it's not. 992 00:43:19,090 --> 00:43:20,360 You have to fire it anyway. 993 00:43:20,360 --> 00:43:23,060 You can't be like, oh, it's mostly impotent rule. 994 00:43:23,060 --> 00:43:23,560 No. 995 00:43:23,560 --> 00:43:27,147 You have fire off the rule if it will do anything. 996 00:43:27,147 --> 00:43:29,730 But right now rule one won't do anything because we've already 997 00:43:29,730 --> 00:43:31,590 added Seamus is a protagonist. 998 00:43:31,590 --> 00:43:34,260 So what rules match down? 999 00:43:34,260 --> 00:43:37,510 Well, Seamus becoming a protagonist is nice and all, 1000 00:43:37,510 --> 00:43:40,620 but he's not ambitious, so we still don't match rule three. 1001 00:43:40,620 --> 00:43:43,230 We still match rules one, two, and five. 1002 00:43:43,230 --> 00:43:45,460 As I basically just got finished telling you, 1003 00:43:45,460 --> 00:43:48,930 the one that we're going to fire off now is two. 1004 00:43:48,930 --> 00:43:50,000 That's right. 1005 00:43:50,000 --> 00:43:54,240 So, rule two is if x lives in Slytherin dungeon 1006 00:43:54,240 --> 00:43:57,130 our only [? binding ?] for that is Millicent. 1007 00:43:57,130 --> 00:43:59,950 And that will show that she's a villain and she's ambitious. 1008 00:43:59,950 --> 00:44:04,372 So what assertions will we add? 1009 00:44:04,372 --> 00:44:05,330 Millicent is a villain. 1010 00:44:05,330 --> 00:44:06,570 And people stopped. 1011 00:44:06,570 --> 00:44:07,380 That's right. 1012 00:44:07,380 --> 00:44:08,410 Good job, everyone. 1013 00:44:08,410 --> 00:44:10,350 You remembered that Millicent is already 1014 00:44:10,350 --> 00:44:15,080 ambitious from assertion one, so we don't have to add them both. 1015 00:44:15,080 --> 00:44:16,340 A lot of people did. 1016 00:44:16,340 --> 00:44:17,580 They were wrong. 1017 00:44:17,580 --> 00:44:21,550 So Millicent is a villain. 1018 00:44:21,550 --> 00:44:24,020 The other part of that rule doesn't do anything. 1019 00:44:24,020 --> 00:44:26,420 But it's not an impotent rule because one of the things 1020 00:44:26,420 --> 00:44:27,410 is not on there. 1021 00:44:27,410 --> 00:44:29,740 Great. 1022 00:44:29,740 --> 00:44:31,890 So, what rules match now? 1023 00:44:31,890 --> 00:44:34,150 Well, as it turns out, now that Millicent 1024 00:44:34,150 --> 00:44:37,700 is a villain and ambitious, we match rule three as well. 1025 00:44:37,700 --> 00:44:41,370 So we match one, two, three, and five. 1026 00:44:41,370 --> 00:44:43,710 What rule are we going to fire, everyone? 1027 00:44:43,710 --> 00:44:44,210 Three. 1028 00:44:44,210 --> 00:44:47,470 Because one and two are impotent rules. 1029 00:44:47,470 --> 00:44:48,890 We'll fire rule three. 1030 00:44:48,890 --> 00:44:50,800 Well, Millicent is a villain. 1031 00:44:50,800 --> 00:44:51,770 She's also ambitious. 1032 00:44:51,770 --> 00:44:53,890 She's our only match for three. 1033 00:44:53,890 --> 00:44:57,250 Therefore, what assertion do we add? 1034 00:44:57,250 --> 00:44:58,250 Millicent studies a lot. 1035 00:44:58,250 --> 00:44:58,791 That's right. 1036 00:45:05,030 --> 00:45:07,220 So, Millicent studies a lot. 1037 00:45:07,220 --> 00:45:08,820 However, she's not a protagonist. 1038 00:45:08,820 --> 00:45:12,180 We still don't match rule four. 1039 00:45:12,180 --> 00:45:14,520 Oh well, we figured that out already ourselves 1040 00:45:14,520 --> 00:45:17,400 from backward chaining that we were never going to match that. 1041 00:45:17,400 --> 00:45:19,210 So what matches? 1042 00:45:19,210 --> 00:45:21,200 It's still one, two, three, and five. 1043 00:45:21,200 --> 00:45:22,950 Seeing as one, two and three are impotent, 1044 00:45:22,950 --> 00:45:26,695 the only match is five. 1045 00:45:26,695 --> 00:45:28,570 So the only match we care about, the only one 1046 00:45:28,570 --> 00:45:30,970 we're going to fire is five. 1047 00:45:30,970 --> 00:45:32,220 And the result? 1048 00:45:32,220 --> 00:45:33,280 Let's see. 1049 00:45:33,280 --> 00:45:34,180 x snogs y. 1050 00:45:34,180 --> 00:45:36,020 That's Seamus snogs Millicent. 1051 00:45:36,020 --> 00:45:39,010 x lives in Gryffindor, that's Seamus. 1052 00:45:39,010 --> 00:45:41,130 y lives in Slytherin, that's Millicent. 1053 00:45:41,130 --> 00:45:43,870 So what do we add? 1054 00:45:43,870 --> 00:45:45,360 Seamus has a bad term. 1055 00:45:56,660 --> 00:46:00,000 Simple, painless, it works out. 1056 00:46:00,000 --> 00:46:00,860 We're done. 1057 00:46:00,860 --> 00:46:03,430 And we got 100 on this quiz. 1058 00:46:03,430 --> 00:46:05,180 Hopefully you guys will, too. 1059 00:46:05,180 --> 00:46:06,000 Question? 1060 00:46:06,000 --> 00:46:09,640 The question is, if you have a new assertion which matches 1061 00:46:09,640 --> 00:46:11,520 a rule but it's really high number, 1062 00:46:11,520 --> 00:46:14,150 it's all the way down at the bottom of the rules, 1063 00:46:14,150 --> 00:46:16,350 but it's new and it has new stuff, 1064 00:46:16,350 --> 00:46:20,220 should we do that first, maybe, because it's new? 1065 00:46:20,220 --> 00:46:23,075 Oh, you mean that it has a lower number, a lower number? 1066 00:46:23,075 --> 00:46:23,950 AUDIENCE: [INAUDIBLE] 1067 00:46:23,950 --> 00:46:25,630 MARK SEIFTER: OK, so the question 1068 00:46:25,630 --> 00:46:29,270 is, if a rule-- let's say that rule three made Millicent 1069 00:46:29,270 --> 00:46:30,920 be a squib. 1070 00:46:30,920 --> 00:46:33,090 Then yes, you'd immediately not only match 1071 00:46:33,090 --> 00:46:36,715 zero-- zero would immediately fire because numerically 1072 00:46:36,715 --> 00:46:37,900 it comes first. 1073 00:46:37,900 --> 00:46:39,790 You'll see that on some of the old quizzes. 1074 00:46:39,790 --> 00:46:41,604 And you may see that in tutorial. 1075 00:46:41,604 --> 00:46:44,270 If you guys want to do some more practice problems in tutorials, 1076 00:46:44,270 --> 00:46:46,356 your TAs will have that available as one 1077 00:46:46,356 --> 00:46:47,355 opportunity in tutorial. 1078 00:46:47,355 --> 00:46:48,930 But yeah, that's exactly right. 1079 00:46:48,930 --> 00:46:50,930 It happened that it went in order this time, 1080 00:46:50,930 --> 00:46:53,130 but it will definitely hop anywhere 1081 00:46:53,130 --> 00:46:57,217 it can in order to get to the lowest numbered assertion.