now, going to 100 million versus going to, let's say, even 100, right? It's just prohibitive. So pruning like this often works better, but it has these two problems. If you're in the small data regime, it actually could hurt you more than it helps. If you're in the large data regime, it might be a wonderful thing, but you just don't have the cycles to do it. Or you're not willing to wait that long. So what other methods can we use? You could prune as you went. So each time you added a note, you could say, does my held out data say this is a bad idea? Precisely. So pruning as you... So the obvious solution to not growing the tree and then shrinking it is, well, don't grow in the first place, right? I need to decide as I go that I want to stop growing here. Right? But notice, now I really cannot do this on the validation set because if I do this on the validation set, it's not the validation set anymore. What makes the validation set powerful is that I'm only making a small... I'm only choosing among a small number of choices there. It's the different subtrees of the tree that I could have. At learning time, I'm actually choosing among an exponential number of choices. So I really consumed the data quickly. Right? So we have that problem. We have to do something different there. Right? So what might we do? What's something that we might do if you can recall something from your stats 101? This is actually something from stats 101 that we can actually plug in here. Any ideas? You know what I mean? Yeah. Of course, it's always that way. Okay, so tell me what's up there. I mean, I guess you could have some kind of test of whether there is a significant improvement in the next layer or next layer of the tree or not. Statisticians are very fond of this, right? Significance tests. You may not remember this or have ever learned it, right? But there are these things called contingency tables and I compare to distributions and I try to decide whether they are the same or not, right? If they're exactly the same then, you know, things are good, but there's always noise, right? So the thing is like, if this is a distribution is this other one a noisy version of this distribution or is it really a different distribution? And this is exactly the situation that we're in here, right? We can use accuracy or information gain to pick the best attribute. But then we can apply one of these statistical tests like, you know, chi-square, for example, right? But there's others, but let's say chi-square. This is the one that you're going to have in your project, right? I use a chi-square to decide is the class distribution that I'm getting now significantly different from the class distribution that I had before. If it is significantly different, then I'm not over-fearing, right? Because I'm really modeling the class distribution better when I have this attribute than when I don't. On the other hand, if, you know, they look close enough, right, and the less that you have the harder it is to tell, of course, maybe I should stop because I'm not confident that I really have a different distribution and at that point, I really might be over-fearing. Okay? Everybody follow this? So this is option number two. In fact, historically, this was the option that people started out using first. So Quinlan, you know, his first system was called ID3 and he used, you know, pre-pruning with a chi-square test. You actually have a pointer to his original very famous paper where he does this. It's actually, you know, fairly simple and straightforward. It makes a difference. But then, you know, he started finding that, you know, this kind of pre-pruning as it's called, right? It's kind of, if you think about it from the gardening point of view, pre-pruning is a very good notion, right? How can you prune a plant before you grow it, right? But in decision tree terms, you can talk about it as pre-pruning. He actually found that pre-pruning was very bad a lot of the time. And in fact, if you do post-pruning, which then became the norm, you could do much better. And then he had this system called C4.5, you know, where both of these are available on the web, by the way, where he did post-pruning. And then, you know, the data mining explosion happened and he created the startup and got rich and retired. That's a good outcome, I believe.  What is an example of a problem where this kind of pre-pruning fails miserably? We've already seen it. And not long ago. Do you want more hints? I can give you a visual hint. This is not a typical question, right? So don't be ashamed by requiring hints. If you thought of the test, you assumed some distribution of the data, right? No, I agree. I agree. But, you know, let's try to think of a very simple, let's say, boolean example, right? Where pre-pruning fails and post-pruning succeeds. The previous levels, you know, don't really show much improvement, but later on that second or third level will improve the creativity. Yep, yep, yep, yep. Yep. Remember this example? Why does pre-pruning fail and post-pruning succeed here? Well, first of all, does pre-pruning fail here? Parity, right? What is the problem of parity for pre-pruning? Is the distribution of the class significantly different when you have split on X1 and when you haven't? Heck, no, it's exactly the same. Right? There's nothing to be happy. Clearly not significant. So clearly pre-pruning fails here. What about post-pruning? Post-pruning is more interesting. What happens with post-pruning here? So post-pruning, you know, to recap is like, I just barrel on. I keep growing the tree with any attribute that I have. If there's a tie, I pick something. If they all have zero, I just pick one and hope to get lucky in the future. Right? So what would post-pruning do here? Right, I'm at the root. I need to pick one attribute to split on. What's going to happen? Can you just have a red dot? Yeah, what I'm going to have is that one of three things is going to happen. I'm going to have X1 as the thing that I split on. Is this good or bad? This is good, right? That's what I want. Or X2, which is still good, right? On the other hand, I could also have X3, right? They all look the same, right? But in this case, I actually have two-thirds chances of picking the right thing. Right? And if I pick... On the other hand, you know, I do run the risk of picking the wrong thing and imagine if they were like, you know, 100 irrelevant ones, then I almost surely would pick one of the wrong ones, right? Which is why even prostruding does not entirely solve this problem, but yet it does something useful and, you know, depending on the problem, it actually may be enough. Why? So first of all, let's suppose that I had split on X1, okay? Now what happens? Who do I split on X? Let's say, I mean, the branch X1 is true, right? And among the examples where X1 is true, so that's these ones here, right? I am trying to choose between splitting on X2 and splitting on X3. What do you think I should do? X2. X2, right? X2 is perfect and X3 is noise. So I had to get lucky the first time, but the second time there is no luck involved. Same thing if I had picked X2 first and then X1, right? Okay, but of course the tough case for us is, what if I had split on X3? Now what happens? Who do I split on X? This is not the hardest question you'll have in this class. After I split, unless you're like, what do they call it? Britain's ass, right? It was between two bays of hail and stars because he didn't know which one to pick. So we split on X3, right? So what are we going to do next? Exactly. It's going to be one of two things, right? Either pick X1 or pick X2, right? Are those things good or bad? They're both good, right? And then after I split on one of those, what happens next? I split on the other, right? And then we're done, right? So moral of the story, in all cases here, I wound up learning the right concept, right? So things were not so bad. What was the, but however, right? If you look at the decision trees produced in each of these cases, which one would you prefer? The one that started with the split on X1 or the one that started with the split on X3? The one where you split on X1, right? Because the other one has garbage in it, right? The other one, you know, isn't going to give you any insight in how it's going to mislead you into thinking at some point there isn't. And it's, you know, of course, this is a toy example, but, you know, it's going to cost you more to store, more to use, more to apply, et cetera, et cetera, right? So it still has been better to, you know, find one of the others, but hey, with post pruning, we actually found this one, okay? However, this is a somewhat optimistic situation, right? Because what's going to happen in the real world?  What's going to happen there? I split, probably the first thing I do is split on a bad attribute, right? And then, what do I split on next? Another bad attribute, right? And I keep splitting on bad attributes. And what is the problem of splitting on bad attributes? After each split, I have less and less data, right? I get exponentially less data. This is called the splintering problem. As I grow my decision tree, I'm exponentially peeling away parts of the space and I'm zeroing in on small parts that eventually have no data in them. Right? So I'm actually wound up with pure noise. I never got around to my good attributes. Now, what will happen on a good day is that I will get some mix of the good and bad attributes in there. And, you know, this actually often happens in practice is that I learn a very big decision tree, most of which is garbage. It's got some good stuff in there. So for prediction purposes, it still does better than chance. That might be good enough for what I need. Okay? It depends on the ratio of good to bad attributes and how difficult it is to figure out, you know, how the function depends on the good attributes. Okay? So the more the story is, you know, post-pruning is much better than pre-pruning in this respect. Right? Pre-pruning always fails. Post-pruning has a chance. Right? But nevertheless, it's still not perfect. Okay? Okay, so any questions? So far? Okay, there is one more method that is also quite popular that we want to touch on. So we've seen two methods so far. We've seen stop growing the data when the split is not statistically significant, and we've seen growing the full tree and then post-pruning. Right? There is a third method, which you also use when you don't have a lot of data. When you don't have a lot of data, and say you don't like this whole notion of, you know, statistical test and what not, what else might you do? Any ideas? This is probably not obvious, but it's a good example of the type of strategy that people use in machine learning all the time. And the strategy goes like this. Actually, I don't know if I have that here, but... Yeah. So, we've already looked at these two cases, and now we're going to look at this third case. What we're going to do is we have an evaluation function, right? Let's say the information gain or the accuracy that doesn't quite do what we want. Right? So let's change it. Let's change it to an evaluation measure that is more likely to give us what we want. This evaluation measure, of course, is not going to do as well on, you know, training errors, just optimizing the training error, right? Hopefully, it moves us away from training error, but towards what we would really like to have. And people are very creative in coming up with measures of this type. Right? Use your creativity at something, you know, to that, you know, error information gain that will help you induce a good tree. Can you think of what such a thing might be? Again, there's many options, but, you know, let's try to think of a simple one. The size of the tree? Right? Usually the trees that are overfitted are very big. So do you know, even without looking at any validation data that as your tree is getting larger, you should start to worry? You don't know exactly how much, exactly when, but you have these general feelings that the bigger the tree is, the thinner the ice that you're on. And so, you should just have a heuristic based on that. Take your error measure and after that a penalty on the complexity of the tree. So you have to know the number of nodes. Again, you could do very fancy things there, but a lot of the time you don't need to. Let's just say the number of nodes. Okay? And so now what has to happen is that when I grow the tree, it has to be improving my accuracy by more than the complexity of penalties costing me. So I will allow extra nodes in my tree, but they have to pay for themselves by more than a certain increase in accuracy. Okay, but how do I weigh these two things? Well, maybe for that you can use sold out data. Or you can use sold out data to pick, you know, the coefficient on your complexity penalty that trades it up against diversity. If you don't have a lot of data, this could be a good thing to do.  If you have a lot of data and you have a lot of cycles, it's unlikely to be beaten. If you have a lot of data, but you don't have a lot of cycles, you might find yourself doing one of these two things, because you can't really afford to do, you know, the full growth and then the full pruning. Questions? So this measure, by the way, this method of growing the full tree and then pruning is usually, is often called reduced error pruning. So reduced error pruning is where you prune by the reduction in error that you're getting as you prune. You split your data into training and a validation set, and then, you know, you learn your tree on the training set, and then what you do is you look at pruning each possible node, see how much that improves your error and the validation set, pick the best one, and as long as you keep getting an improvement, you keep pruning. When every possible pruning left that you could do only hurts the accuracy on the test set, that's when you stop. And in fact, unlike the growing stage where things are basically over the day, you know, if you do this, you can actually prove that you get the best decision tree on the, you know, in terms of validation here. Questions? Okay, now, there's actually another, actually, so before we go on to that. Here's what happens on the diabetes dataset when you do reduce error pruning. And again, this is fairly typical. So I grew my whole decision tree, remember all the way to here, and now I'm here. Very bad tree. And guess what? I start getting better and better and better and better until I finish here. Brilliant. You know, actually, in this case, the post pruning pretty much aced it. Okay, we could have gotten a slightly smaller tree, but we got just about the best accuracy that we could. Okay? So it worked in this case. Quick question. Notice that the curve that I get on the way back is above the curve that I get on the way there, right? Is that an accident or is there a reason for that? If I'm asking, it's probably because there's a reason, right? So that was more of a rhetorical question, right? What might the reason be? Because you only prune if you get better. Yeah, because notice, right? When I'm pruning, right, now I'm actually, here's the key thing is that the nodes do not get pruned in the same, in exactly the reverse order to what they got added, right? If the first node that I pruned was always the last one that got added, the two curves would be exactly the same, right? But they don't. When I start pruning, I actually have the choice of pruning any node anywhere that I want, and I pick the best one. So, in general, that one's actually going to be better than, you know, it's going to be better to prune that one than the one that, you know, I happened to add last, right? I added one over here, but there's actually an over that I'm better off pruning. So, you know, reduced better pruning can be very good provided you have the cycles in the day. Questions? Very good. It's actually very interesting, and it actually gets us talking about the stuff that we're going to be talking about next week, which is rule post pruning. This is actually something that Quinlan added to C4.5 and wound up being what is used most of the time. It's a kind of a reduced better pruning, so it's a kind of post pruning, but the interesting thing is that you prune the tree not into a tree, but into a set of rules. That's why it's called rule post pruning. So what's going to happen is that I'm actually going to induce the tree not as the end goal, but I'm inducing the tree as a way to finally get a good set of rules out. And in the next week, we're going to talk about just, you know, using rules from scratch without worrying about decision trees, and then we'll compare the two. But you can also induce rules by first inducing a decision tree and then pruning it to rules. So let's look at the three things in time. First of all, what is the correspondence between decision trees and sets of rules? And second of all, how you prune a decision tree into a set of rules and finally why that might be a better idea. So first of all here's our good old friend, the decision tree for playing tennis. And the first question is if I were to just convert this into a set of rules, so don't even worry about pruning for just a second. What do the set of rules look like? Remember, a decision tree is really a set of nested if-then statements, right? You know, if outlooks sunny then, if humidity, high then no, and so on and so forth, right? So it's a tree of if-then statements. A rule is just the statement of the form, if this and this and this and this, then play tennis. And then there's another rule that says if that and that and that, then don't play tennis. And so forth, okay? So for, and for every decision tree, there's an exactly equivalent set of rules. Okay? So what is that equivalent set of rules? So for example, this is probably a very easy question, but nevertheless, let's go through it, right? So here's my decision tree, right? Give me one decision, leave me one rule, sometimes called a decision rule that you would get from it. If outlook equals overcast-then-yes. If outlook equals overcast-then-yes. Yeah, brilliant. This is a really short rule, right? What's another one? outlook equals-then-yes. Yup, here's another one, right? Yup, here's another one, right? So if the tree has n leaves, how many rules are we going to have? n. Right, there's going to be one rule per leaf or per path in the decision tree, right? And the rule corresponding to a particular leaf, what are going to be the antecedents of that rule? What is it going to be testing? It's the attributes on the corresponding path of the decision tree, right? No brain. And then the consequence is just the class prediction at that note, okay? So for every decision tree there's an equivalent set of rules, okay? And I can turn one into the other completely mechanically, okay? And indeed when I do so did everybody follow this? Yeah, straight forward, okay? So the first thing that I do when I do rule postponing is I just take my final full, big, noisy, overblown, overfit decision tree and convert it to the equivalent set of rules. Okay? So now, what do you do?  So how would you do that? It's probably going to be somewhat similar to the, you know, postponing that I had for decision trees, right? But what, you know, and again, there's more than only to do this, but, you know, what's one way? Let's think about one rule in particular. Let's take, you know, a decision tree is one being complicated, you know, interrelated structure, but the rules at some level are all independent, right? So let's look at one rule, right? I have this rule here that has a whole bunch of things, right? And probably some of them are noise, right? So how do I go about figuring out which wants to drop and which wants to keep? So remember, in the decision tree, right, what I did was I looked at each node and I tried pruning it, right? And then I pruned the one that gave me the biggest improvement, right? So in the case of a rule, what should I do? Exactly, I look at dropping each one of the antecedents, right? And whichever one I get the most increase in the whole dot accuracy from, I drop that one, and now I have a rule that's shorter, right? And then what do I do next? And I'll look at the remaining ones and drop the best one or the worst one, right? And when do I stop? Same rule as tree and accuracy does not go up. Exactly, when I try dropping every one of the attributes in my rule and every single one of them now dropping it decreases my accuracy on the validation there. At that point, well, all those attributes seem to be doing something useful, so I'm done, okay? So that's step two. Are we done? This is actually where I think suddenly get a little more interesting. So far this was, you know, a fairly straightforward analogy to decision tree pruning, you know, given this concept that we're going to produce a set of rules. But in the case of the decision tree, at this point we were done. In the case of the set of rules, are we done at this point? Is this a rhetorical question? Yeah, this is a rhetorical question. So why are we not done at this point? The order of rules. Why does the order of rules matter? Which one should be evaluated first?  And I have a bunch of rules that say no spam, right? And now how do I decide? One more time? Performance? Performance, sure. But more specifically. I mean, some of the rules might take longer to be evaluated? Sure. I mean, sometimes that's a consideration. But usually the main consideration is accuracy, right? And some rules are more accurate than others. So what's the natural way to order the rules? The most accurate one first, right? So I order my rules, you know, by accuracy, right? And then I just, you know, it fires winds. It's just a, you know, an if then statement with a lot of else's. If blah, blah, then spam. Else, blah, blah. And some of these might be spam, some of them might be not spam. But as a heuristic, it's hard to disagree with the notion that I should put the most accurate rules first. There's, in fact, another thing that we can do there, in fact, works even better, but again, we're going to talk about some of that later, which is what? There's a way to make a different suggestion and tell that, like, majority of the executives fall under one rule, but that won't work. Exactly, majority. We vote. Remember? Learning algorithms like democracy. They like the wisdom of crowds. I have a bunch of rules. Some of them say yes, some of them say no. Let them all vote, and the one with the most votes wins. Should all rules have the same weight, or should some rules have more weight than others? One should have heavier weight. Yes, certainly if you believe in simplicity as a heuristic bet, that's something that you should use, right? But what's another thing that you should use for the weight? That's even more obvious. In fact, you could combine the two. Remember, when we were ordering the rules, we put the more accurate ones first, right? In a way that's like saying the first rule has more weight than all the others put together, right? So what's something that I could weight my rules by when I'm voting? The accuracy. In fact, what people typically use is a combination of the accuracy and not the simplicity, but the coverage of the rule. The coverage of the rule is how many examples in the training set does it account for? What might the reason for that be? Given two rules with the same accuracy, why would I prefer a rule with more coverage? Let's say these two rules are both 100% accuracy. This rule here is 100% accurate on two examples, and this one here is 100% accurate on 2,000 examples. Which one would you prefer? Generalizable. The one on 2,000 examples because? In generalize. If you got two examples right, you know, you got lucky. For all I know. If you got 2,000 examples right, it probably wasn't luck, right? Again, there's many combinations of these things that you could use, but those are two different things to use. I still don't get the prove each rule in different teams. We have each path as the rule. How are we pulling it? We are removing an attribute and changing it. I did not get that part. No, so very good. Another point that I was about to bring up. Let me actually backtrack for just a second and then we'll get back to this. Why did we have to do this for the rules but not for the decision tree? In the decision tree, we didn't have to pick an ordering or vote among the leaves or any of that. Why was that? Because the rules that you get by directly translating the decision tree have a very, very unusual property. That set of rules. The set of rules that I got from this tree has a property that most rule sets don't have, which is, this is not immediate to see, so let me just say. Only one rule ever fires. The property that the decision tree has is that the path to the leaves are all mutually exclusive. In the assumption of full data, because no missing data, you can only go down one path, which means that if this rule matches then this one for sure cannot and when I prune the decision tree all I'm doing is shrinking it towards the root. What is the big difference between that and what happens when I'm pruning two rules? This is a subtle point but it's actually crucial. If I was pruning the decision tree from the leaves to the root, I would consider pruning humidity, right? And then I would consider and I would consider pruning wind, right? And if I had actually pruned these, then I might consider pruning out again having no tree, right? That would be bad but it could happen, right? But here's something that would never happen, right? I would never prune outlook without pruning humidity and wind. You agree? There's just no way to do that. Because the outlook is what actually splits me into these joint sets. And then I get more splits and so on and so forth, right? So decision trees have this advantage that applying them to the test example is actually faster, right? It takes essentially logarithmic time, right? To just fall down to a leaf.  So decision trees are faster to apply. However, pruning two rules tends to give a more accurate model than pruning to decision trees. Why? My discovery is that the humidity is normal, the outlook doesn't matter. You get rid of noise. Yeah, yeah. Keep going. Anything else? You also prune an action value instead of action values. Very good. So let's try to synthesize this, right?  When I'm pruning a decision tree, what I have to do is I either prune humidity really, or then I prune, or, you know, by the end of the process, I have pruned humidity and outlook, right? So I can, all I can do is shrink the path from the end to the beginning, right? So what do you mean by pruning humidity? It's like removing that room? Yeah, I'm removing this and I just, you know, I predict, you know, once I'm sunny, I just predict, let's say yes. Okay. So I get rid of that, right? So when I'm pruning through decision tree, I'm very constrained in the things that I can prune. When I'm pruning to a rule set, given one rule, I can prune any attitude that I want, right? In particular, you know, once I have this rule, if outlook's sunny and humidity high, then play tennis now, right? If you look at pruning the decision tree, I can prune humidity, but I can prune outlook, or I could prune both. But when I'm pruning to a rule, sure, I can prune outlook, right? So I can prune more things in the, in the case of the rule and in the case of the decision tree. And now, why might this be a good idea, right? Notice the following. Outlook is, sorry, outlook is the thing that we stuck with here, right? And outlook, the thing that happens here is that like outlook is tested in every single rule. Boy, that outlook attribute has to do a lot of work. Suppose that that outlook is good for some rules, but not others, right? In the case of the decision tree, while I'm stuck with it, I have to take the good with the bad. In the case of the rule set, no, I can prune it from some rules, but not others. So you tend to get a better model when you prune to a rule set. A more accurate model. In addition, and sometimes this is actually the biggest reason, you also tend to get a much simpler model.  Run C4.5, do the, do the decision tree, and do the postpone to the rules, and then decide whether you'd rather be looking at the decision tree or the rules. The set of rules, if you give a cost of once if you reach at the season in each rule, and the cost of one for each rule in the decision tree, the set of rules is going to tend to be much, much smaller than the decision tree. Why is that? Remember, in the decision tree, this lower part of the tree, I'm always going to have it there, right? The rules, I can actually get these short rules, each of which that uses the two or three attributes that are really good. In the decision tree, I'm stopped with using Outlook for everybody. And then, you know, when Outlook is, you know, say, sunny, I'm then stuck using the entire next subject for everybody. Okay? So by pruning two rules, I can get a more accuracy and then B, a much smaller and easier to understand model. So it's no wonder that people often prefer to have a rule set. It does have some disadvantages. It'll typically be more expensive to learn, and when you're on a large data set, that is an important consideration. It'll be more expensive to apply. And in some domains, applying things very quickly. In some domains, it doesn't matter. In some domains, you know, that's a big constraint. And it's also, you know, the decision tree pruning is fairly straightforward.  Okay? So there's pros and cons, but it's definitely worth knowing about pruning right? So once you get to rules and prune, you can't go back very simply, right? Yeah, yeah. That is a good question. In fact, we're going to talk about this question next week. So I propose that you think about it, and then, you know, then you can tell us what you found next week. There's definitely a very interesting question, right? Think about this. If I have a set of rules, right, can I convert it back to a decision tree, right? Yeah. I think as the post pruning process is more complicated, you have more attributes as technology. Is there a risk of fitting the test date validation data? Exactly. Very good. Yeah, this is machine learning thinking, right? Is that, oh, sure, it's more powerful. I can learn more things, but you should also be thinking, well, now I have to make many more choices. So if I have a large, you know, rule set and I do a lot of stuff, I should be more careful.  By the way, here's a quick, you know, question. When you're splitting your training data into training and validation sets, whether you're going to use decision trees or rules, what relative size should they be? 50-50 should use more than if we're training, should use more for validation. What is your feeling? 90-10 training. Sorry, you said more for training? 90-10. 90-10. Oh, 90-10. Okay. So, but 90-4 training and 10-4 testing is what you're saying? Yes. Okay. Anybody disagree? I agree. Less for training and more for testing. Less for training and more for testing. Why? Because that will reduce the complexity of our as much as we get a chance to prune. No, so you're arguing for less pruning there or more pruning there? I'm arguing for more test validation and less training data. Okay, because? Because that way our complexity is less and we get a chance to prune and we have more data to validate. Do you agree? Yeah. Okay, so what's the argument for more training there? You get a better model to start with. All of these arguments have some merit. Two to one right now. Who else wants to weigh in? Who feels lucky today? That is a total, very excellent. Now we have all the options on the table. 50-50, what's the argument for 50-50? That's a totally reasonable thing to suggest, right? What's the argument for 50-50? Both sides have, I mean, both the arguments have merit, you know. But do they have equal merit? And more importantly, are there bigger arguments that have not been made yet? You know, what you just stated is the famous principle of indifference. It's formulated by Monsieur Laplace back in the 19th century, which is when you don't know, just 50-50. Right, you're indifferent. But better, you know, so if you have to do things in a short time, that's a reasonable thing. But now let us think about what might be better. Anybody else want to weigh in? Well, I mean, it seems like there's also a question of how much data you have. I mean, if you only have a small set of training data, then, well, sorry, a small set of data you can work with, then maybe you want to go 90% with your training. But if you've got a huge set of data you can work with, maybe you only need numbers. Another very good point, so let me synthesize that as follows. The trade-off is not necessarily independent of the data set size. In fact, it might change as the data set changes. In fact, if I have a ton, a ton of data, what should this split be? I don't care. I have a ton of data either way. As long as it's not epsilon versus one minus epsilon, with a lot of data, it doesn't really matter. So this is really a crucial question when I have very little data. This may be way out on a limb, but could you start with a small amount of training data and a lot of validation data and see if the model works well, and if it doesn't, then gradually increase the amount of training data until you find a model that fits well? You could, but that's a little dangerous, and you're starting to use the validation that is more training there. The thing about validation there is that you have to use it infrequently. And that might not be too frequent, but it's a slippery slope. Any other thoughts? It seems to me like selecting the training data set. If you're selecting a small piece, depending on which piece you select, that could really change your whole decision tree. So how could you compare... So you vote for more training? I vote for more validation, actually. Oh, okay. So, three to one. Anybody else want to say something? But your argument of decided leader... I'm enjoying this. The other argument is decide leader.  You should go into politics. I see you rising high above the rights of the manager. But we're just engineers here, so let's try to not go that round.  And maybe that's what you're saying about leader. And that's pretty good enough. Actually, let me just put a thought into the air. Let me ask you this question. Which one is harder? Learning the initial tree from data or pruning a tree to the best subtree? Which one do you think is harder? Pruning is harder. Is it? Because we have so many paths. Let me actually jump ahead. If pruning is harder, then we should use more data for pruning. Because we want to use more data for the harder thing. Does everybody agree? Whichever is hardest is what we should reserve most of the data for, because that's where it's needed. But which one is harder? Is it pruning or training? How do we decide this? Let's think about it this way. This is a search problem. It's an optimization problem. I have a search space of decision trees. What is the search space for learning and the search space for pruning? What is the search space for learning? It's every decision tree in the universe. Which one is larger? Which space is larger? The space of decision trees when you're learning or the space of decision trees when you're pruning? When you're training. And by a lot, it's way larger. Anyone care to revise their votes? Is that your final answer? This is the kind of thinking that you have to do when you apply machine learning. Once these things become a pattern, then one day they just become part of a class that you get to take. You can acquire this experience in particular. People started out doing splits of various kinds and indeed, so let me jump right to the punchline and what do people usually do? They always have a big percentage of the data for testing. The percentage varies. And one of the ways in which the percentage varies is with how much data you have. If you don't have a lot of data then you really stuck. You're in that early part of the learning because you lose a lot by reducing your training set. On the other hand, your validation data is going to be very noisy too. As you get more and more data, things become very easy in both directions. For example, when I'm using something like two-thirds, one-third, this is empirical. There's also a lot of theory about this but empirical is what people tend to use. Two-thirds, one-third, or three-quarters, one-quarter, or 90-10. 90 for what? 90 for training and 10 for pruning. Now, when you're really, really short of data, there's something you can do called cross-validation. Has anybody heard of cross-validation? It's where you have, you pick one set of data for training, one set of data for validation and then you pick a different set of data for training, a different set of validation. It's a very clever idea. Yes, roughly speaking. Let me say it a little bit more precisely. It's a very clever idea where you actually get to use all the data for both training and testing. Isn't that amazing? Here's what you do. Let's say you do 10-fold cross-validation. This is probably the most popular. You divide your data randomly into 10 pieces. And then what you do is you train on 9 and you test on the 10. And you see where this is going next? Then you pick another piece that you hold out. You train on the other 9. So all of them rotate through being you form 10 different training sets, each of which contains nine 10s, and then you test on the remainder. So at the end of the day, you basically every data point got to be used as training and testing. So you get out of those runs where you had a 90-10 split. This is good. Everybody got to be training nine times and everybody got to be testing one time. The disadvantage of this is what? There's two. You're doing the work 10 times over. Yes, it's expensive. You just increase your running time by an order of magnitude. Ouch. The other problem is that, at the end of the day, what is the decision tree that you produce? You just learn nine. What people typically use cross-validation for is things like picking the value of that complexity penalty. How much should I weigh the complexity versus the accuracy? Let's use cross-validation for that. Let's see what's the coefficient that gives me the optimal trade-off. I can do that using my cross-validation and then once I found that coefficient, now I run on all the data and this is a very common machine learning strategy. Questions about any of this? There's one more important thing to touch on before we're done today. We're covering, as you've probably noticed, we're covering a lot of very important stuff today. This is a very high utility class. The final thing that I would touch on is the problem of scaling up. We're in the days of big data. How about running the algorithm that we've seen so far, any one of them on big data? Here's what's going to happen.  Then one day towards the end of the universe, hopefully before the entropy death of the universe, the answer comes back. We need to worry about scaling up our algorithms. People sometimes say that data mining is machine learning scaled up. I think that's a little bit understanding it, but certainly in practice a lot of what people like me did in the early days of data mining was take machine learning algorithms that were like cubic or quartic or whatever and try to make them linear or log linear. Or maybe even better. But try to make them scale to large data sets. This was not easy. There's been a progression with different algorithms and whatnot. It's just a very, very large data set. What I would like to do is just in five minutes briefly touch on what some of these things are just so that you're aware of them. First of all, what is the biggest reason why these algorithms will not scale to large data? The biggest reason of algorithms like ID3 which does pre-pruning, C4.5 which does post-pruning is that they all assume that your data fits in main memory. They do random access to the data. I put my examples in main memory and then I go collect statistics of different attributes in random order depending on how the tree is growing. Right? But big data doesn't fit in main memory. Now main memory keeps growing but big data grows faster. Right? And you know Moore's law is great but the Moore's law of disk actually far outpaces the Moore's law of computing. There's actually a lot of what drives processing in big data is this thing, is that our ability to store data greatly outpaces our ability to process it. If the exponential for processing part of Moore's law moved faster than the corresponding law for disk well, you know, big data we'll just shove it into the CPU and then run it. Right? The problem we have, the algorithm complains like, oh, I'm a company I have terabytes of data but what do I do with it? We mined big data. We're going to be mining it from disk. And number one, reading data from disk is, roughly speaking a thousand times slower than reading it from main memory. So already there we have a problem. We just suffer the thousand factors but the other big thing of course is that what? What is the big difference between disk and main memory? In disk access is sequential. Right? So if you take an algorithm and try to run it on disk it's never going to finish unless the data set is very small. I have a data set of a billion points which is not unusual these days even a hundred million and it's randomly accessing the disk is spinning, the head is finding its place and this never finishes. So the number one thing that people worry about doing when scaling up became a big issue this was like circa, I don't know, 1995 let's say algorithms that only do sequential scans of the data. I want an algorithm that reads the disk and maybe picks the roots and then maybe reads the disk again and finds the entire next level all at once and then keeps on doing this. This is a natural idea but making it work and actually gaining efficiency is surprisingly tricky. There were seeds of algorithms that did this which you should at least know about how to tweak and whatnot. IBM actually had a data mining package at one point that one of the first companies really out the gate with this and this was basically one of the main algorithms that they used there. Now this works up to millions of examples. The reason it doesn't work beyond that is that even just reading a million examples from this takes a while particularly if they have a lot of data. If you were doing multiple scans of the data this thing may be taking days or weeks even to just learn one model. But of course the learning process is that you don't learn one model. You are playing with the data and learning a model in 20 different ways and doing cross validation here and taking parameter there and not changing the data like that and if your cycle of this is the week or even days is we are going to require what's called working in data stream mode. Data stream mode and this gets us back to that distinction between batch and online learning. Data stream mode is I only look at the data once. I see it and it's gone. I see the next one and it's gone. It's gone. I can choose not to use it but if I want to use it I have to use it right then and I never see it again. This could be because I can't afford the disk storage or because I don't want to scan the disk more than one time because it will take too long. You said you don't store it anywhere either you just see it once. This is one option is the data is never stored. For a lot of very high volume applications like say network monitoring you and ISP. Your servers are like your routers are generating are spewing out data like crazy. You don't even want to store them. In some cases however you can afford the storage but running through that because storage is getting cheaper and cheaper but just running through that takes too long. The third generation of algorithms are algorithms that work in stream mode. They do at most one scan of the data. Ideally they don't even scan all the data. For that there's a number of different algorithms but the best one that I know of now is something called BFDT very fast decision tree learning which was actually invented here at UW. You should be suspicious because it's me telling you about my work. You should probably get a second opinion on this one. You can go to Google Scholar and what not. Nevertheless it's good to know that there are algorithms without getting into all the details of how this works. We have algorithms now that can actually grow decision tree in one scan of a data that is basically as good as the decision tree that you would learn with random access. In fact the best part of this is that you might need much less than a scan of the data. You can actually be scanning the data and decide at some point that like hey, I've already grown as much as I'm going to grow I don't need to see any more data. I am done at this point which is a very nice thing to have. Again we're not going to go into the details of these algorithms here but you want to be aware that they exist because if you find yourself pruning a very large data set or even a large data stream these are probably the kinds of things that you want to look at. The basic algorithms first and that's what we spent our time on here but you don't want to have the experience like I know people who have had that they started with ID3 and they spent six months basically rediscovering how to line from this. Questions? All right, very good. So now your fun begins. Now you're going to do your project where you implement the decision tree learner and apply it to quick stream data. This moment because it might not finish running before the due date. This is not like some of your other projects here. I've been warned do it this weekend and let it run until the due date is run out. Well, if that needs to happen then you're doing something wrong. We carefully selected the subsets of the data that are reasonable in apple of the morning. Nevertheless, we hope you have a lot of fun. All right, see you next week. All right, let's go then. Welcome to week three. Are you having fun learning decision trees and mining quick streams? Yes, I see from your smiles that you are. So maybe the next project needs to be harder. So you know what data mining really is like. In the meantime, today we're going to talk about rule induction. Another major area of machine learning. In fact, we already talked a little bit about rule induction last week. Because the last thing that we saw was how to turn decision trees into sets of rules. And how nice sets of rules are because they can be very compact and easy to understand. But here's a question that may have occurred to some of you. Before we're going to learn at the end of the day is a set of rules, right? Why are we doing it by way of learning a decision tree? Couldn't we just learn the rules directly? Wouldn't that be a better way? Well, the reason we learned both is that they had their pros and cons. But let's look today at how we can actually learn rules directly. And in fact, we're not going to stop at that. We also need to see how we can learn much more powerful rules than the decision trees that we saw last time. When we started talking about machine learning, I said that machine learning is learning programs from data. But the programs that we've seen so far are very limited, right? The decision tree is just a set of basically nested if there are no statements. Today we're actually going to see how you can learn full-blown programs. So last week we got down to basics. But this week we're really going to climb into the stratosphere. So pass in your seat belts, okay? All right. So as usual, let us first think about what rules are and what kind of learning algorithms do we use for learning rules. So first of all, rules are very popular and for a reason that's easy to understand, right? Rules are probably the most easily comprehensible thing that you could mind. They're even simpler than a decision tree. It's just a bunch of statements that you can actually read in English and they make sense, right? In fact, I don't know if you've had the experience of having like, you know, great application rejected and then there's a piece of text that says your application was rejected because you haven't linked long enough at your address and your employer, blah, blah, right?  It should know more. But nevertheless, it's actually something you can put down in writing and people, you know, can just read without any expertise, okay? So this is one of the main advantages of rule sets is that they're very understandable and often very compact. Okay? Excuse me. Like decision trees, rule sets are a variable size representation. If I have more data, I can learn more rules and they can be longer. They can be more detailed. They can have more preconditions. They're also deterministic and they also can have both discrete and continuous parameters. So the discrete parameters are the choices of tests that you put in the rule and the continuous parameters can be things like the thresholds for tests that you have on continuous attributes or things like, you know, the probability of the class given the attributes, right? If this email has these words in it, then it is, you know, spam with some probability, for example, okay? Learning algorithms for rule sets like decision trees are also constructive search, right? How do we learn a set of rules? Well, the natural way to do it is to learn one rule at a time, right? And the natural way to learn one rule is to learn one antecedent at a time and that's what we're going to do. We're going to construct the rule set step by step. Most rule induction algorithms are eager and they batch, meaning that we have all the data at training time and then we do as much, you know, with that data at training time, we learn a model that then hopefully is quick to apply, okay? Again, there's exceptions to this. There's online learning algorithms, there's lazy algorithms, but for the most part, rule induction is an eager and batch process, okay? Any questions so far? All right, so first of all, what is a set of rules, right? What is the hypothesis space that we're going to be working in in this class? Well, the rule, right, is just what you probably already think it is. It's just a set of tests. Each one is of the form this variable is equal to this value. If the variables are discrete, like for example, the color of the car is red or this variable is less than or equal to some value or greater than or equal to some value if you're talking about a numeric value, like, you know, the temperature today is about 60 degrees, for example, okay? These V's and these X's are values and our attributes and values that appear in the training bed, okay? And it's out of those that we're going to build up the rules, okay? And then what a rule says is things like, for example, if the variable X1 has the value sunny and the variable X2 has a value less than 75% then the class is yes, meaning we are going to play tennis, okay? So this is one rule. A set of rules is just the disjunction of rules, okay? So let us assume for the moment that we're just going to learn a concept, right? So we're just trying to learn something binary, right? Is this a car that I want to buy or is it not, right? Does this patient have pneumonia or does she not, okay? So a little bit later we'll talk about learning with multiple classes. But when we're learning rules for one class, the simplest thing to do is to just have the model for the whole class to just be a disjunction of the individual preconditions, right? So the email is spam if it meets these preconditions or it meets those, okay? So at the end what you have is a DNF a disjunctive normal form defining the concept. So for example, we could have these three rules. If X1 is sunny and X2 is less than 75% then yes. If X1 is overcast then yes. If X1 is rain and X3 is less than 20 then yes, okay? Notice there are no rules here saying no. The reason there are no rules here saying no is that the answer is no if none of the rules match, okay? So I have only rules for the positive class and then if none of the rules fire then by default I just assume that the class is no. Okay? There are other ways to do things but this is the simplest one and it's the one that we're going to focus on for the moment, okay? So question number one. So how do rules relate to decision trees? We touched on this last time. What is the relationship between a decision tree and a set of rules? Does anybody remember? Different representation of the same answer. Exactly. You can build rules from a decision tree. So I can take a decision tree and convert it to a set of rules. How do I do that? Every leaf is a rule. Every leaf is a rule and the conditions on that rule are the conditions on the path to that leaf. So in particular the rules that we just saw here are what you get from this decision tree which is the one that we've been playing with all along. Or you know, something close to it. So going from decision trees to rules is easy. But now the next question is what about going from rules to decision trees? Actually let me hide this slide for just a moment because temptation can be hard to resist. Right? And first of all, can we always translate the decision tree into an equivalent set of rules? Is the inverse also true? Can I always translate a set of rules? Let's say in a Boolean domain the variables are Boolean, the class is Boolean. Can I always translate a set of rules into an equivalent decision tree? Yes or no? Yes? Anybody want to say no? No. Okay, so we have yeses and noes. So let's hear the case for the yes. If it's going to represent a Boolean function then there must be a way to represent any Boolean function of the decision tree. Right, remember we saw a long time ago that a long time ago, all those weeks ago that you can represent any Boolean function with a decision tree. So what do the noes have to say? Somebody remotely was saying no. So what if you can't really find something to be the root of the tree? Like you have multiple rules. I don't know how to describe it too well but I think the idea is like for instance how we have half look as the root in the decision tree if you created a set of rules then you could actually minimize it to the point where something like half look is no longer a root. Very good actually. So this is a real problem. So what you're saying is that you can't see how you would do it, right? You want to say something? Yeah, and also I remember we talked about pruning and when you prune it you could actually prune a rule but it did not remove the node. No, I agree but notice for the moment we're not talking about learning algorithms, right? We're just talking about the representation. So my point is you could represent rules like that which you cannot represent directly at the decision tree. Yeah, so at heart these problems are the same, right? So let's think about this, right? So at some level we know that it must be possible. What it's not obvious is half. We can figure out how but this is going to have consequences, right? So the natural question is who's going to be the root of the tree, right? So does one of the, you know, yes votes have a suggestion, right? You said it's possible, right? In theory there's this notion of a constructive and a non-constructive proof, right? So you could have a non-constructive proof but we can have a constructive one, yeah. I mean, assuming these are all like disjoint variables that you have A, B, and C and you pivot on those roots you can pick a random one, say A. And at the two other levels you pivot on both trees at B. And one of those is going to be redundant for like the no, I think. Depending on the rule.  They're all redundant but you're covering every rule that you are worried about making a root. Yeah, very good. In fact, this general idea works even if the rules do have overlapping in attributes. In fact, the overlapping attributes, you know, kind of looks like it complicates things but all that happens is that I already tested that value before so I don't need to test it again. So, but let's pursue this idea and, you know, here's a concrete example, right? Here I have three rules, very simple ones. X1 and X2, then Y. If X3 and X4 then Y. And if X5 and X6 then Y, right? Another question is how do I build a decision tree out of this? Well, let's just pick one of them. Actually picking anyone. Clearly the decision tree is going to depend on X1, X2, X3, X4 and X5 and X6, right? It's going to depend on all of those. Which one of these shall we put at the root? It's not always irrelevant which one you put at the root, right? Because you could get a smaller or larger decision tree. But for the moment, let's just worry about doing this any way that we can, okay? So let's just say that we pick the first antecedent in the first rule. Why not, right? So the first thing that we test is X1, right? And then notice that if X1 is true, right? We're going this way, right? And then obviously we need to test whether X2 is true because that's the other antecedent in that rule, right? And if X2 is also true then what do we know? Then it's a yes, right? Because that rule says it's a yes and that's that leaf over here, right? On the other hand, let's go back to the roots. This is the interesting part. What happens if X1 is false? If X1 is false then this rule doesn't fire, right? So then where are we? What do we need to do now? Does that mean that the example is false too? No, right? Because it could still be true because of one of the other rules, right? Everybody agree? The first rule failed to say yes, but well, there's still the others and those might say yes, okay? So now what we need to do is what? As always in decision trees, this is a recursive process, right? So the first rule has failed, but now we need to do what? We need to represent the other rules on both sides of the tree. Exactly. So we need to test the second rule and then the third rule and two people have already alluded to what the problem is going to be, right? So let's see what the problem is. When X1 is false, right? Now I need to test the second rule, which means I test X3 and then X4, right? And if X3 and X4 are both true, then I get the answer true, right? And, you know, to keep going, if this rule is also false, right, then I have to test the last one, which means first I have to test X5 and then I test X6 and if they're both true, then the result is 1, okay? Everybody with me so far? Now, we've captured all the yes cases, right? But we're not out of the woods yet. In fact, you know, woods is actually an appropriate metaphor here, right? We're in a big jungle. Why are we in a big jungle? Because notice, I don't just have to test for the second rule over here, right? I also have to test for it over here, right? Because over here, right, this first rule has also failed, right? So in that case again, I'm going to have to test the second rule. So what do we get here? We get a repetition of the same subtree that we had over there. Notice that the subtree rooted at this node and the subtree rooted at this node are the same, right? You see what's happening here? I have to go test that subtree in every case that the first rule fails, right? If there were 10 interstitutes in the first rule, I have to do this 10 times. And then what happens when the second rule fails? In every one of those cases, I'm going to have to test the third rule. And if I had 100 rules, this would be really bad news, right?  That's right. Worse than quadratic, exponential, right? I'm going to need to look at all, in the worst case, right? I need to look at all combinations of truth values of the rules. And I'm going to have a subset of the tree for true, false, false, et cetera, et cetera, yeah. You can share pointers though, right? Across the tree. No, very good point. You cannot. Although you could learn a different model called a decision graph. In a decision graph, you can have pointers to the same thing. Okay? So in the decision graph, we would not have this problem, right? Or at least, you know, most of this problem would be solved. It's not necessarily the case that the decision graph would be as compact as the set of rules, but yes, the decision graph would all be at this problem. So is that just because of the definition of a tree? Yeah. The problem with the decision graph is that it's more complicated to learn a decision graph than a decision tree. So even though they're a very natural idea, for the most part, people never use decision graphs. This was tried at one point to use decision trees. But decision trees do have this huge problem. It's called the replication problem. Because you get more and more replications of the same things as you go down. Notice that, for example, by the time you get to the end of this, you've tested x6 here. And you've tested it here. And you've tested it here. And you've tested it here. There were four tests of x6. And if this rule came at the end of a whole bunch of other more, instead of four tests, there would be eight or 16 or two to the who knows what. And notice, there's nothing particularly pathological about this set of rules. It's a perfectly simple and natural set of rules. So decision trees have this very sticky problem, at least compared to decision rules, that the same concept could be exponentially larger, express the decision of the tree than expressed as a set of rules. Not always, but it can happen. So this is one significant advantage of rules over trees. This is not just a representational problem, by the way, right? Because the other thing that we saw last time was that as I grew the decision tree, I get less and less data, right? And so as I noticed that once I split on x1, I only have half the data points, roughly speaking, on each side. So now when I finally get to inducing these subtrees, they're being induced on a fraction of the data that I had before. So the data dwindles for learning decision trees in the way that it doesn't dwindle for learning rules, which means that we might not be able to learn something as a decision tree when we would be able to learn it as a set of rules. Okay, any questions? Okay, but if rules are so great and trees are so bad, then why do we bother with learning decision trees? Why are decision trees the most popular, you know, data mining method than not rules? What are the potential disadvantages of learning decision trees or complications? Sorry? At runtime, yes. At runtime, decision trees are blindingly fast. Decision trees are just about the fastest thing you could have at runtime. Right?  It's all there for you. Rules, you have to match all the rules. If you have a lot of rules, that could take a long time. That could be too slow. What's another potential complication? We also saw this last time when we looked at rule post-prime. With decision trees, you always know who's the winner because there's only one. Right? You only go down one branch. With rules, well, sure. I have all these rules, then, you know, they all fire. So what do I do? In this case that I have here, it doesn't happen because I only had rules for the positive class. But, you know, jumping ahead, if I had rules for multiple classes, then, you know, I have a, you know, a non-obvious decision to make. Okay? Okay, these are two problems, but there's another one which is more subtle, but perhaps more important. Can anyone guess at what it might be? Just use your gut feeling. By the way, here's a good rule of thought. If somebody ever asks you, what is the problem with this machine learning algorithm and you have no clue, just say overfitting. You will be right more than half the time. Okay. If that's what you've noticed, let's go back to our question. What might be the other problem with rule induction with decision tree induction? Yeah, exactly. What would rule induction be more prone to overfitting than decision tree induction? This now is not an obvious question, but, you know, think about it for a moment. Why would we have more chances to overfit when learning rules than when learning decision trees? And therefore have to be correspondingly more careful. Yeah. I think you're always looking at all the attributes. That's one thing. Yeah, so there is one aspect is that, remember, when we're learning a decision tree, we're computing information again over all values of an attribute. On one hand, this is unfortunate because it ties it together, but on the other hand, it's fortunate because it actually avoids making highly overfit decisions, at least better than with rules, right? In a bit, that with rules, you run a very high risk of overfitting very highly, right? And, you know, the other way to think about this, which is more those are like, it's a more flexible representation, right? And therefore, since it's more flexible, on the one hand, that's good because you can learn more things, but on the other hand, it's bad because you run a bigger danger of overfitting. We're finding some set of rules that look good just by chance. And this is a trade-off that has always been to be present in machine learning. And so you might as well get used to it, you know, right at the outset, okay? Questions? Very good. So, let's look... Now we know the representation, right? In many ways, it's similar to decision trees, so this is not a big leap from decision trees. Now let's look at how we learn rules, right? And we don't have to do it from scratch. We already know how to learn decision trees. Naturally, learning rules should not be able to use a lot of the same ideas, right? So can anybody suggest how we might learn a set of rules by analogy with decision trees or just, you know, using whatever comes to your mind? How might we do that? And remember, we said it's a constructive algorithm, right, where we build one rule at a time and so on and so forth. So how might we go about it? Just as learning decision trees convert to rules. No, I couldn't agree with you more, right? So what's method number two? That is a perfectly good method, right? That's what's in C4.5, right? You can do that. You know, when Coulomb did his data mining company and became a multimillionaire, actually, I don't know if he became a multimillionaire, but that's what he had, right? He was learning rules via decision trees, right? But let's suppose that we want to, you know, learn rules directly, right? How might we do that? Just start picking examples and make a very narrow rule, and then as you find more examples, like broaden the rules, if it makes sense. This is actually one option. We're not going to talk about it today, but this is often called the bottom-up or specific to journal learning rules. I actually leave my PhD thesis in that, so it must be good. But anyway, right? Short of that method, which is a good one, but, you know, it's not the most widely used one. What might we do? I guess you could start with a rule that uses the least number of attributes and covers most examples. Yeah, exactly. So this is the analog of initially, you know, we have a tree that is empty and we pick the rule. Like, what we're going to do is like, we're going to start with a rule that just has the consequence and has no antecedents, meaning it matches everything. Everybody's a good credit risk. You give credit to everybody. And then you figure out, well, let me try each attribute in turn and add that as a condition on the rule. Right? Very natural thing to do. Let me test that and see if it gives me a more accurate rule. There's a good chance that it will. So I try adding each possible antecedent and I pick the best one. And then what do I do? Rinse and repeat. Right? Then I now have a rule with this antecedent and the consequence. So I add every of the other possible antecedents that I have in addition to that one and I find the best rule of size with two antecedents. And I keep going until when? Until when? What's sorry? I tell you, you don't see an improvement anymore? Yeah, until you get no improvement. Very good. And what is the most natural case in which I get no improvement? In which, in fact, in the case of learning a rule, I know I can always get to that. Right? Remember, in the basic decision tree algorithm, we stop, you know, growing the decision tree. Correct? Yeah, when everything on my training set was of the same class, therefore I don't need any more conditions. Right? Same thing here, right? Initially I have a big mixture of positive and negative examples, right? I start adding antecedents and notice what happens is that I'm adding an antecedent that throws out hopefully a lot of negative examples and very few positive ones, right? So as I grow the rule, I have fewer, fewer negative examples until hopefully I come to a point where I have no negative examples, right? And my rule only covers positive examples at which point it makes no sense to try to refine it more, and that's where I stop, okay? So that is our algorithm for growing one rule. Very simple idea. Okay? Yeah. So what happens if you have two examples with exact same values but different classes? Very good. That can happen. That is actually the only failure case. Right? Notice that as long as that doesn't happen, right? If the examples have different values, I can guarantee that I'll always be able to use a pure rule, right? Because in the worst case, that rule's just going to add every antecedent corresponding to every value in that example and then we're going to have it. If I have, you know, say three examples like that and two are the positive class and one is negative, well, the positive wins, you know, and the probability is two-thirds. If I have one of each, which can happen, right? I have two patients with exactly the same symptoms and tests. One has tuberculosis, one doesn't well. You can flip a coin or maybe try something else. We can't tell. But in rules, you can't represent that probability, right? You just have to choose one or the other. No, I mean, like I said, you could, right? A basic rule doesn't have that, but I can, this is often done, right? I attach to each rule the probability with which the consequent holds given the antecedents. For example, if I'm going to vote among rules, that's probably a very useful thing to have. Okay, so as before, we have the problem of, you know, we need the criterion to decide how good a test is, right? And before, if we're going to the decision tree, we'll look at accuracy and information gain, right? And again, here in the case of rule induction, I have lots of possible quality measures for a rule and people come up with new ones all the time. But again, just the accuracy of the rule is actually a very decent thing to use. Okay? It's actually used more for rules than for decision trees. Right? Because when learning a rule, we don't have this problem that we're trying to balance what happens between different branches. We just want that rule to be accurate. Okay? So I could just use the accuracy as a rule, right? Of the fractions of examples that the rule says are positive, how many really are positive, and that's my accuracy, right? I could just use that.  There's other things that you can do. In particular, you can use the analog of the information gain. But notice that before, right? I was looking at all the values of the variable. At this point, actually, what we have is we can actually go back on the notion of gain and entropy and just think back to the surprise, right? I'm actually now growing a rule to predict a particular class. Right? So what I don't want to have is nasty surprises. Right? I don't want that when my rule says it's spam, it's actually not spam. Okay? So what I can do here is actually not maximize, you know, gaining the action, but just like minimize my surprise. So here's my old surprise and here's my new surprise. Okay? So remember, surprise was p log p, right? Or the expected surprise, right? For this particular case, right? This is actually what I'm trying to improve on. Right? So the difference between the old one and the new one is my reduction in expected surprise. Okay? When I'm in this situation, when I'm saying that the rule is one. Okay? Now, notice that there is only one part of what I have here. I've also put this M1 prime here. M1 prime is the new number of positive examples covered. And M0 prime is the new number of negative examples covered. And I've multiplied my, you know, reduction in expected surprise by M1 prime. Why would I do that? If your rule covers 100,000th of your data set really well, do you really care? Precisely. It's really easy to induce a rule that looks really good. Namely, say a rule that covers only one example, right? It's 100% accurate. You know, you've got the maximum possible reduction in surprise.  Why is there a problem happening here and it didn't happen in decision trees? Remember, in decision trees, when we branch on a naturally, we were looking at both sides. Right? And we're balancing what happens on both sides. When we're learning a rule, no. We're only looking at this one side. So we just throw out all the negative examples that we can and then we get all that is totally overfitting. What is a sign that we might be overfitting? M1 prime gets quite small. Precisely, right? The fewer examples the rule covers, the more suspicious we should get. If the rule covers 100,000 examples and they're all positives, we're pretty confident that, you know, that region that the rule covers is just positive.  So a very simple thing to use, you know, as a fix for this is to actually multiply the gain by the positive examples that the rule still covers. We want that to be large. And if the surprise reduction is big at the expense of making this small, then this rule is dubious. This is just a heuristic, but it's very important to use something like that. We will see many different ways of combating overfitting, but this here in a simple way is one way of combating overfitting. Questions? Okay, so at this point we know how to use a single rule. Okay? So with this algorithm as a subroutine, what should our algorithm be for learning the whole rule set? We're almost there, but we need one more step. So I have a black box that returns the best rule that we can find. What should I wrap around that black box to induce a set of rules, not just a single rule? Here's one way to think about this. Okay, I just learned my best rule. Okay, I have a rule now. So what do I do next? Get rid of all instances that satisfy that rule and then pick the next best one. Yeah, exactly. I now need to learn my second rule, right? And I don't want to go and use the same rule again, right? But my goal with the second rule and the remaining ones is to account for the instances that the first rule didn't account for, right? The positive instances that were collectively classified by rule one, well, they're taken care of, they're covered. Okay? So what I do is I take those away and now I have a new smaller training set and now I go find the other best rule on that training set. Okay? And I keep on doing this until when? Again, don't worry about overfitting for just a second. When should I stop? You know, I want to make that possible under some rule. Precisely. Once I've accounted for all my positive examples, there's nothing left to do. We're done. Okay? And this is our algorithm. Also known as separating conquer, right? By analogy with decision trees. Decision trees are dividing conquer, right? I divide my set into small and smaller pieces and I conquer them. In rule induction, what I do is I conquer one piece, I separate that out and then I go conquer the rest. Okay?  Any questions? Yeah? So what if you... So you have just positive and negative classes right now. Can this be extended to, like, multiple classes? Absolutely. And we're going to talk about that in a little bit. But, you know, as a background process, you can figure it out in the antelos. But you're not allowed to look ahead in the slides. Look ahead is sometimes machine learning, but it's very expensive. Any other questions? Okay. Now, in the case of decision tree learning, greedy search works fine, and it's what people almost always use. In the case of rule induction, that is not quite the case. Here, greedy search actually can give very bad results in rule induction because it can get very quickly stuck in a very bad local optimum. Okay? So for rule induction, there's a couple of other things that people often do that are worth knowing about. Okay? So let me just briefly mention those. The first one is what's called round robin replacement. And this has to do with the fact that if you think about it, the first rule has an unfair advantage. It's not competing with anybody. It can account for everything that it wants and it leaves very little data for the succeeding rules. Right? If there's some data that's covered by two rules, right, once the first rule took care of it, now the second one doesn't have access to it. So I've unnecessarily restricted the data that the second rule has access to it. Okay? So what can I do about that? Well, what I can do is I can use a bunch of rules and then say, throw away the first rule and say, well, let me now induce something in the presence of the other one and see what that would be. If it's the same rule again, then fine.  Because now the other rules have accounted for part of what they will account it for and so on and so on. Now this one can be different. Okay? So this is called round robin replacement. I can also do this process sort of like as I go, as I add each rule, I try removing rules. There's many variations of this, but some of the best rule induction methods do something of this value. Okay? But the most important thing to know about is this last one, beam search. Does anybody here know what beam search is? Beam search is a less greedy, greedy search. In greedy search, what happens is that at each point I pick the best antecedent and then I run with that and I never look back and you can get into a lot of trouble that way. In beam search, what you do is the following. At each point I pick the K best antecedents and I form K candidate rules. K is called the width of the beam, right? It's called a beam. It's a beam because it's like, you know, having a flashlight with a wider beam as opposed to just a pencil of light pointing in that one direction, okay? And then what I do is I try adding each new antecedent to each one of those, right? So now instead of 10, I have, like, say, you know, 100 candidates. And now, again, I find the best 10 of those, okay? And I keep going in the usual way. And then finally, of the 10 best that I have at the very end when there's nothing, you know, no improvement to be had, I pick the best one. Okay? So what is the relationship between beam search and greedy search? Greedy search is a beam of what? Exactly. Greedy search is just what you get when the beam is one, right? They only keep the best one. What is the advantage of beam search over greedy search? Right? When will greedy search and beam succeed? Think of the second best, right? The one that greedy search threw away. It could be that that second best conjoined with the next attribute now becomes the best. Okay? In fact, that can happen a lot. And that's why beam search can be a very worthwhile thing to do. It's more expensive, right, by roughly, you know, the order of the size of the beam, but you can get much better results that way. So the typical method that people use in rule induction is actually beam search, not greedy search. If you just agree to search, you could wind up with a very bad rule set. And usually what happens is that you get stuck right away. You don't actually find any good rules because, you know, the concept is pretty complicated and then you don't know what else to do. Okay? Questions? All right, so. Next problem. We're going to meet here one of the biggest problems in all of machine learning, and even in probability and statistics. This is a problem that occurs all over the map. In fact, they already created decision trees, but it wasn't as bad there, so we didn't focus on it.  In fact, there's whole soft fields of machine learning dedicated to dealing with this problem. And in areas like, for example, like speech recognition, the problem that we're going to talk about is a good chunk of the whole speech recognition is about dealing with that problem. More natural language processing, for example. So what is that problem and what can we do about it? It's the problem of estimating probabilities from a small sample. If my rule has a probability of, you know, 80% based on a thousand examples, I'm confident. If it has a probability, you know, of 80% based on ten examples, I am not so confident. And so as I induce the rule, as it grows longer and longer and covers fewer and fewer examples, my decisions become more and more random until at some point the antecedents that I'm adding are just garbage. So last time we saw, you know, some ways of finding this, right? What's one way that we use for decisions that we could also use here? Something from stats 101. Yeah, I can do a significance test, right? This is one option. And it works fairly well. But there's actually a much simpler option that typically works just as well or even better. Shockingly simple. So let's see what that option is. So let's see, you know, this is my estimate of the accuracy, right? P is the probability of, you know, the example being true. M1 is the number of true examples covered by the rule. M0 is the number of false examples. And P is just M1 over M0 plus M1. Right? Clearly this becomes very unreliable when M1 and M0 are small. So how might we fix this? Any ideas? You're allowed to read this slide. Yeah. Just say it in your own words. Here's a really, really simple idea. Remember when I talked, you know, when we mentioned before, you know, Monsieur de la Place and his principle of indifference? His principle of indifference was inspired by the following deep philosophical question. See, philosophy is relevant. We're going to prove that right here, right? It's relevant to computer science. How do I know that the sun will rise tomorrow? You didn't know coming in here today, at 6.30 p.m. on a Thursday, that we'd be talking about such esoteric things, right? But bear with me for a second. How do I know? I don't know, right? It's always risen so far, right? But maybe tomorrow, you know, the sun will go over and, you know, or it will die. Right? How do I know? So Laplace's answer to this question, which you could say is a shallow answer, it's actually a deep answer, is the following. In the beginning, right, I haven't seen the sun rise on any day yet. I don't know, right? So I just say that the sun has a 50-50 chance of rising. Right? That's its principle of indifference. Okay? So before I've seen any example, it's 50-50. But then, you know, the dawn of the first day, right, that glorious moment, the sun rises for the first time. Should that change your probability of the sun rising? Well, yeah, sure.  You suddenly believe that because the sun rose one day, it's going to rise every day. That seems a little too much. Right? So the question is like, what can you do that's between 50-50 and, you know, 100-0? What might you do? You know, by the way, let's play this forward, right? Once the sun has risen for two days, right, I should get even more confident that the sun is going to rise, right? And once the sun has risen for, you know, five billion years, right, at that point I should be pretty darn confident that the sun will not be 100% confident because one day the sun will not rise. So what might we do? Let's say day two. So day zero, or, you know, like before the sun rises for the first time, your estimate is 50-50. Or, you know, one in two, right? After the sun has risen one day, what might your new estimate be? 1.5 by 2. Yeah, something like that, right? So how about the following? I add one, like before I had one and one, right? And now what I do is like I'm just going to pretend that I started out seeing one of each. So now what happens is that I've seen two of the sun rising and one of the sun not rising. This is really the Laplace idea, right? So my new estimate is going to be two-thirds, right? It's actually going up substantially, but definitely not 100%. Did everybody follow this idea? So we get the following thing that's often called the Laplace estimate, which can take a lot of forms, but here's one, the simplest one. I'm just going to add half to the numerator and one to the denominator. I could also add one and two or, you know, two and four. We'll look at that in a little bit. So this is my Laplace estimate. So first of all, what is my Laplace estimate if I haven't seen any data? 1.5, right? Very good. What is my Laplace estimate if I've seen infinite data? Let's suppose that I have seen infinite examples where the sun rises and no examples where the sun does not rise. Now what is my probability that the sun rises? 1.5. It's 1, as it should be, right? So what happens with this very simple thing is that as I see more data, it asymptotes to perfect confidence or to what the probability really should be, right? Let's say that the sun, you know, on some planet rises, you know, two-thirds of the time, right? Then after a while what I have is two-thirds, you know, plus or minus absolute. This is exactly what we want, okay? So with this very, very simple change, right? From this to this. All I did was add 0.5 to the numerator and 1 to the denominator. And I actually have something that can handle small knots of data. This one little change that will take you about 10 seconds to make in your code is the difference between a rule induction system that fails miserably and is a great success. This is the greatest bang for the buck that you've probably ever seen in any area of computer science, right?  Not that, okay? But now you could ask yourselves, well, why should that be 0.5 and 1? Right? Maybe I have some prior reason to believe that, you know, the sun rises some percentage of the time. Now let's say I'm building a rule for spam and, you know, 90% of my email is spam, right? Why should I start my rule with the assumption that it's going to be 50-50? That seems silly, right? We know it's not going to be 50-50, right? So what might I do instead? Right? This is, we're looking at a generalization of the Laplace estimate, right? What could I have here instead of 0.5 and 1? There's, mm-hmm. I'm not putting the percentage of the time you expected. Exactly, right? In fact, the short answer to this, to the question, what could I have here are the three numbers that we want here? As long as the number of top is not larger than the number on the bottom, okay? But typically what you will do is, like, you will have the ratio of these two numbers be your prior estimate of the probability, right? If I priority, I think it's going to be true at probability 0.9, then that's what I do, I put 0.9 and 1, okay? Step one. Step two. But why put 0.9 and 1 and not, you know, 9 and 10? What is the difference between those two? In fact, what is the difference between, you know, putting down 0.51 or putting 0.5100? Or for that matter, you know, 5,000, 10,000? What is the difference between these cases, right? Your prior estimate in all of them is 0.5. So what difference does it make? One skews it more towards whatever, if you have 5,000 or 10,000, you're going to skew it far more towards, you know, your earlier estimate, because of the data you have. Precisely. The stronger I make, the larger I make those numbers, the stronger my prior belief. If I make those numbers small, my prior belief is wiki will be overridden by the data very quickly. If I believe in those numbers very strongly because I have very concrete, you know, positive information that they're true, then I need a lot of data to override them and then I make it, you know, and then I make them large numbers. Again, a very simple thing to play with, that has a very large effect on the results. In fact, you know, every good learning algorithm has one good overfitting control parameter and this is such a parameter. Just writing this parameter goes all the way from overfitting widely, right? If I make it, you know, 0, to basically ignoring the data, right? If I make those numbers much larger than the size of the data, the data has no effect. And in fact, some of them are often used in practice in areas like, for example, speech and languages to make these numbers very, very small. They're actually, they can be smaller than 1, too. Those numbers are just there as a placeholder until I see any data. As soon as I see some data, I start to believe the data. But what I don't want to have is 0 over 0, right? Because that would be a lot of trouble. Okay? So these numbers are very easy to play with. You know, this is sort of like what you would call the general prior estimate or the end estimate because you call that number M. But this is a couple of numbers that are really worth putting in there and, you know, really playing with when you're applying rule induction to some problem. Okay? So you're dealing with chi-square and all of that stuff that we're forcing you to do in decision tree induction. We just picked the most painful method because we want you to suffer. And as I mentioned, this is not just a problem in rule induction. What you just learned in the last five minutes is something that you can apply anywhere that you're doing probability estimates. In natural language and speech, for example, people estimate, you know, all these probabilities. Like, you know, the famous Google machine translation model?  N-grams is, you know, like sequences of n-words and how often they occur. The biggest problem when learning large n-gram models is exactly this problem. I make the n-grams longer and then the probability estimates start to get very unreliable, so the smoothing becomes really, really important. By the way, this is often called smoothing because obviously what it does is it makes my probability estimates smoother. They don't jump all over the place anymore. They're very smoothly from your prior to the tree. Questions? All right. Moving on. Somebody asked the question, again, let me hide that. Somebody asked the question, what if we had multiple classes? See, the strategy in these classes to be on the lookout for that 10th of a second when the slide shows up and use your iconic memory and then you have all the answers in you. How might we handle everything that we saw so far as learning with one class? What if I have half a dozen? What should I do then? Any suggestions?  What is a simple, easy thing to do here? Each class one at a time? Precisely. Always try to use what you already have as a black box. This is a golden rule in all of computer science. Let's say I already have a black box for learning one class. How do I bootstrap that black box into another one for learning multiple classes? Just learn rules for each class in turn against all the others. No change. So I have classes A, B, C, and D. I have a bunch of rules that says if this rule fires your A, if this rule fires your B, and so on, are we done or do we need something else? I think those rules could overlap, right? Yep. You have to solve that problem. Exactly. So if the rules overlap, what do we do, right? A rule for class A fires, and a rule for class B fires. So what do I do now? Can you build rules that apply to that? I can contrive the rules such that they're mutually exclusive. Isn't that a devious idea? And what do you get in that case? You get a decision tree. Historically, actually, rules precede decision trees. But then there was this problem. I'm abusing history a little bit here, but this is not entirely incorrect. When you learn decision tree rules, which at least for people coming from an ad background were very natural because it says the rules, but there was always this very thorny problem of how you combine the rules. If you contrive the rules to have mutually exclusive antecedents, you never have that problem, and that next decision tree is kind of attractive in some ways. But you know, like today, our agenda is, you know, we're going to do this with rules. So what might you do? Sort them by confidence. Precisely, right? We already looked at this last time. We can sort them by confidence or by some measure of quality, and the first rule wins, right? We call the decision list, which is really a kind of case statement, right? Natural idea. But we also saw that, and you know, this is an often used method. We also saw last time that this is typically not the best method in terms of accuracy. What is the best method? Voting, right? Democracy. We like democracy. Right? The rules all get to vote. Right? Because suppose that the most accurate rules say of class A. But then there's tens, would you be really stubborn in that case and still favor class A? No. At that point, maybe the balance of evidence favors class B. Right? I have one rule firing saying this is a chair and I have ten rules saying it's a table. Well, you know, I might go with a table. Okay? So what you do is you vote. You have a set of rules. Each one has some sort of coefficient, like, you know, coverage, accuracy and whatnot, and then they vote according to these coefficients and whichever class gets the most weighted votes wins. There's other ways to combine them. Some of them quite, you know, interesting. Probabilistically, we will look at some of these ideas later, but, you know, this actually works pretty well and is easy to implement. Okay? It has the disadvantage that it's the slowest, right? Because I need to run through all the rules to see if they all match and then vote them, as opposed to as soon as one of them fires. And remember, typically the rules at the top cover a lot of examples, so there's a good chance that one of the other rules will fight. So this is the slowest method, and it tends to be the best one. Okay? Questions? So this problem doesn't really exist in decision trees, right? Yeah. Decision trees are immune to this problem because I always go into exactly one leaf and that leaf predicts exactly one class. So that's one advantage of decision trees. One of the things that you should be able to do when you're done with this class is, when faced with a new problem, when twisted and aggregated for machine learning, think about these various algorithms and representations and see what is good for this problem versus what is not. Which is why it's important for you to see a good sample of these things. And of course, it's not a random sample. It's the most widely used ones, and it's a very set. But you want to have that understanding of what the options are and the circumstances and weaknesses and so forth. All right. Somebody had a question? What do you do if none of them are supplied? Oh, absolutely. Great question. Darn it. I forgot that. What do you do when none of the rules file? You do what? It's a negative example. But what is a negative example? You have multiple classes and I've learned the rule for each of the classes. There are no negative examples anymore. What couldn't you just define sort of a default class? Yeah, precisely. You can have a default prediction. What is the single most frequent class overall? What is the single most frequent class among examples that none of the rules cover? Right. Remember, in reality, we're going to prune. So the rules aren't going to cover all the examples. So I could see what is the most frequent remaining class and then I predict that. Or you could just tell the user, hey, I don't know. Some machine learning systems have what's called a reject option, which is, I'm not confident. This is actually what the post office uses or used to use for things like, you know, figuring out the zip code on letters. If the character recognition system was confident that it knew the zip code, it would get sorted automatically. Otherwise, there's a reject option that says, like, a human had better look at this. So you also have that option. By the way, even for the case where I only have two classes, the best performing method is to learn rules for one class and for the other class, and then vote them or order them. It's typically more robust. So in the case of two classes, I don't have to do that. I could just learn rules for one class, but I'm usually better off actually having rules for both of them and then having some ordering procedure . Any questions? Very good. So this was the straightforward part of today's class. Straightforward because if you think about what we did in this hour, it was really just transposing to rule induction what we knew about decision tree induction. It wasn't that different at the end of the day. You might even wonder if this was all worth all the trouble because if you already know about decision trees, then figuring out how rule learning works is not that big of a deal necessary. But now we're going to about take a big leap into something much more powerful than anything that we saw last time. And if at the large part of the reason why we've looked at rule induction that we did so far is that there's going to be the basis for learning rules of a much more powerful form. And that's what we're going to spend the rest of today's lecture on is learning first order rules. I don't know if you guys know this from my lecture but everything that we've seen so far was propositional representations because they're at the level of propositional logic. In propositional logic all that you have is propositions like in like a Boolean symbol is a proposition. The Boolean symbol a represents its sunny today. Anyway you can do a lot of propositional logic but it's also a very impoverished language. To really do programming in general you need something at the level of first order logic. First order logic is when you can have functions and arguments to the functions and predicates with arguments and so on and so forth. We want to learn things like that. This of course is much much harder but actually at this point step by step we're already halfway to that. So let's see what else we have to do and what this new more powerful representation is. So there's a lot of formal background that you could give here about first order logic and whatnot. I'm going to mostly avoid that and keep things at a more or less intuitive level. However, if at any point you're not clear what we're saying or have any questions just let me know and we can look into things a bit more carefully. So I'm going to be relying on examples a lot to show what happens here. So here's a classic example of the type of thing very simple, that you can learn with first order rules, with rules in first order logic that you couldn't learn with propositional rules or with decision trees the way we saw before. This is the example of the concept of ancestor. Ancestor is not a property of a person it's a property of a pair of people. This is what makes it interesting. Whether a patient has tuberculosis or not is a property of that patient. Whether Anna is an ancestor of Bob well that's a property of the pair. So things now get a lot more interesting. What we would like to do is learn the definition of ancestor from data. You give me a database of family relationships and I want to infer from that what ancestor means. This is a very real example. I have a big information extraction system in fact we're going to see an example from information extraction shortly and I want to extract these relationships figure out how one relates to others and so on and so forth. So here's an example of a couple of logical rules that define ancestor. One is X is an ancestor of Y if what? What's the simplest case in which X is an ancestor of Y? Think of this as a recursive definition and think of the base case. What is the base case of the recursion? Paran. Paran, right? X is an ancestor of Y if X is a parent of Y so that's our first rule. Easy street. What is the more interesting case the recursive case? X is an ancestor of Y if what is the general case? If X is an parent of another ancestor of Y Exactly.  Everybody agree? And that's what the second rule here is doing. X is an ancestor of Y if there's a Z somewhere such that X is a parent of Z and then Z is an ancestor of Y. Okay? Look at this carefully for just a second because this is the kind of argument play that we're going to be using all along here. Right? Some of you might know this is actually a couple of statements in Datalog. And you ask at some level of abstraction is equivalent to Datalog and most of the database or at least the simple database quiz that you issue can be formulated in this form. Datalog is also a special case of the prolog programming language. In prolog you can write whole programs just by writing down rules like this in logic. The difference between Datalog and prolog is that in prolog you can have functions inside here. I could have ancestor F of XY. We're not going to deal with that case here. We're just going to look at the Datalog case. Because you know it's complicated enough and powerful enough for our purposes here. Okay? So what we would like to do is learn a couple of rules like this from data. And by the way it does look a little weird because the arrow is pointing in the opposite of the usual direction. We have the antecedents first and then the consequence but this is what people do in prolog and Datalog so we're just going to stick with that. Okay? You can read this rule anyway that you want but the rule and rule is the consequence are always on the back of the area sorry the consequence are on in front of the area and the consequence are behind the area. Okay? So this is the type of representation that we would like to be able to learn it. Much more powerful than what we had before. Okay? Now of course this is a trivial little example just family relationships. What's a more realistic example of this? Why do we care? Here's actually a real example of the type of first order rule that you can learn. Let's suppose that you want to do the every popular thing of classifying web pages. You might want to classify web pages by what topic they're on by what kind of object they represent. You can see how this would be interesting because like Amazon and Google and Microsoft and what not. You want to organize the web. Right? So here's an example of such a rule from a real system and we're going to see how that system works shortly. They apply this system to the web pages of a bunch of computer science departments and they wanted to classify the web pages into this is a course page this is a faculty page this is a student page this is a project page and so on. Let's figure out if a web page is the web page of a course or of something else. And now what we're going to do is we're going to do rule induction. We already know how to do rule induction we're going to try to form a rule that predicts that something is a course page using properties of the page. This is the single most accurate rule for predicting courses that come out of the system and let's see what it has. So it says that A is a variable A is a course and you can read the rule like this. What does this first antecedent say if you translate into English? Web page A has the word instructed. So if the web page contains the word instructed that makes it more like it to be a course page. Pretty obvious, right? And what does the second one say? By the way this thing here in case you're not familiar with it is the negation sign, right? It means not. So what does this one say? Let's do it. Let's keep moving and not focus too much on what that part of the rule means. I don't know. A course page is a course page if it doesn't contain the word good in it. Well, this is just an empirical fact. Let's not overinterpret it. But anyway these two antecedents actually we could have done with what we had before. In fact, people often do this. I represent a web page as the bag of words that appear in it. Instructor, it does not contain the word good. It contains the word isn't that in the other, right? And then I could just have the rule that says well, if instructor not good, then course, right? So far, propositional would be good enough. Where does the extra power come in? Well, let's see the next pair of antecedents. These two. What are these two saying? This is the really interesting part of this rule. There's a wink from page A to page B and page B equals the word assigned. Or contains the word assigned. Yes. Right, so by the way, some of the people often doing text processing is stemming.  So this is a sign really comes from the word assignment. Right? So what these two guys are saying together is that something is a web page if it points to another page that contains the word assignment. Well, of course. Isn't that brilliant? The web pages for courses contain links to pages that contain the word assignment because they are assignments. In fact, the web page of this very class is a positive example of this rule. We really contrived it to make that happen, but hey, we have that positive example. Right? It does contain the word instructor. It does not contain the word good and it contains a link to a page that says assignment. Right? See? This is the power of machine learning. Isn't it amazing? Especially when you contrived the examples. No, just kidding. Okay, so see why this is different from what we could do before because now we're talking about a property of something else. We're no longer talking about a properties of the object that we're classifying this web page. We're talking about properties of a related object. And now we have all this power at our hands, right? And you can see why in the web you'd be able to go hog wild with this because links are all over the map, right? This page is about something because there's another page that points to it that's about something else. Etc. Etc. Right? So now I can use another powerful example of this. I can predict that you will go see this movie if your friends that you trust went to see that movie. Right? Now I can use properties of related objects to predict properties of the objects of interest. I couldn't have done this before. Or maybe I could have done this by putting together in the record for an object all the properties of all the related objects, but this is insane, right? It would mean, like, that for every page that I'm trying to classify, I would need all the properties of all the pages on the web that are connected to it, which is probably all the pages on the web are almost all of them. So that would be a non-start. Okay? So we get a lot of power from being able to do this. Now, by the way, what is this last one here? What does this mean? It has a link. This is actually the least obvious one, but it also makes sense, right? So this here says not link from BC. What is this saying in English? Nothing links to page B. Actually, the other way around, B links to nothing. Remember, links from a B is A links to B. So what this says is that B links to nothing, right? So what does this mean in terms of course pages and assignment pages? Okay. So the assignment pages you can dash on the assignment page itself? Right, exactly. Right, again, this makes sense. The course page has a link to the assignment page, but then the assignment page doesn't have links to anything else. Our assignment page violates this one. Darn it. We failed there. I'm going to fire the TA. He'll be grateful. Right, so this actually looks a little odd at first, but it makes a lot of sense. Assignment pages typically do not have pointers to other things. At least in the data set that they were learning this from, that was the case. And by the way, this rule was completely accurate on the training set and on the test set. These were both pretty small. This was back a long time ago, in the early days of the web, when doing this was a new thing. But this is actually a surprisingly accurate rule. Is that a good thing that the training set had 100% accuracy? A good thing that what? That it had 100% accuracy on the training set. It's a good thing, but it's a suspicious thing. Another question that you want to ask yourself as a newly minted machine learning pro is how much do I believe that 31 out of 31? And the answer is, well, I would believe that plus or minus 3 or 4, which, guess what, is exactly what happened. You would have to be pretty lucky to get this 31 out of 31 times if it wasn't accurate. That's very unlikely. I would trust this rule before looking at the test that hindsight is always 2020. I would trust it to be accurate. I would not trust it to be 100% accurate. And that turns out to be the case. This rule is not 100% accurate, but it's still pretty accurate. It's a valid rule. Looks like the training set, the test set is just the training set and three more sites. Again, what they did in this problem, as you're doing in your project that everyone always needs to do, they actually were of comparable size. I don't remember exactly what the split was, but it's not like they were totally different from these things. Questions so far? Excuse me. Okay. Now we know, at least at an intuitive level, what first are the rules are. Hopefully, I persuaded you that this is a powerful thing that we would like to be able to use if we can, but it's probably not going to be that easy. It sounds a lot more complicated than what we had before. But of course, what we're going to do here, as always, is step by step. We already know how to build rules in the propositional setting. Now what we have to try to do is extend that to the first order setting. Hopefully some things will stay the same and we don't need to mess with those. Some things will change and then we need to deal with those and then we'll have a full algorithm. Okay. And this is exactly what we're going to do here. In particular, we're going to look at something like the first order rule induction system, but it's still very popular and it encapsulates very neatly many of the basic ideas. Or at least one of the main approaches of learning first order rules. We're actually going to see two main approaches. This is the first one. It's the one that builds directly on what we already know about rule induction. And four, by the way, again, was also from Ross Quinlan. You know, this great U-double alumni that is one of the grand old people in machine learning. And he also invented FOI. Pretty amazing guy. And by the way, FOI is first, first order inductive learning. It's one of those acronyms that really mean something. Unfortunately, I've never heard people proposing, you know, calling their algorithm shrink wrap and silly things like that. That did not come to pass, but I did hear it proposed. So what is FOI going to be? It's going to be the same as our propositional separate and conquer method built with two key differences. What are those two key differences? Well, think about the FOI. What we did when we were doing propositional induction was we look at all the possible antecedents, right? We try adding each one and then you see which one works best, right? But we can still do that here. What has changed, though, is the language of antecedents that I can add. The antecedents that I had before would just test like it's sunny today or it's not sunny. The humidity is above 70% or it's not. Now I have a much richer language of things that I could add. In particular, I have, you know, predicates like has word and links from and what not. So that basic idea of constructing rules one antecedent at a time can stay the same. What has changed is that now I have a much more powerful language of antecedents to add. Everybody got this? Okay, so that's rule number one. I'm going to have to look at different candidate specializations of my rules. In particular, my specializations are going to be what are called literals in logic. A literal is either a predicate with arguments like this or a negated predicate with arguments like this. So these are the kinds of things that we're going to be looking at adding. Difference number one. Difference number two is that, obviously, I'm going to need a different evaluation function now. In any learning algorithm, the choice of evaluation functions is always one of the key things. The type of evaluation function that I had before doesn't really work here anymore. Let's suppose that evaluation function was just the accuracy. The accuracy was the fraction of correct examples that I covered. What is the accuracy in this case? Actually, what is an example in this case? It's not even clear what's an example anymore. Before, an example was like a patient and their 10 symptoms. But now what I have is like this big network. It's the web. There's links. There's substructure in the page. There's tags. What is an example? It's not actually clear what an example is and whether it's the same before and after I add an antecedent to the rule. Clearly, as much as we still want to maximize accuracy or information gain or any of those things, coverage, etc., etc., we're going to have to adapt that. These are the two changes that we're going to have to make. Let's see how we're going to do that. First of all, it's going to be easier than it seems. That's the good news. On the other hand, fair warning, I'm going to gloss over a lot of subtle details here. You're welcome to look at the more in the book and then, for example, look at the pilot and play with it and whatnot. At a high level, actually, it's not going to be that complicated, at least compared to the part that we're going to get. First of all, how do we specialize rules in the court? Well, let's say we have this current rule. Now, notice that for a start, the head of my rule is no longer just a class. It's a natural predicate, like ancestor X, Y. So it's going to be a predicate symbol, P, with some set of arguments, X1, X2, X3, X4, as in antecedent, X1, X2, and so forth.  L1 is really standing for a predicate symbol with a bunch of arguments in parentheses, like parent X, Y, or has link, AP, and whatnot. So I have this rule like this so far. Now, what am I going to add to it? Over to you. What should I consider adding? Oh, and by the way, what is the training set now? The training set used to be a very important point. The training set used to just be a table of my examples. For each patient, their symptoms, or for each email that would appear on it. What is our training set now? It's actually, again, a much more general thing than we had before. What is the training set for a first-order rule learner? That's one way to look at it. It can be a graph, and we're going to see an example like that a little bit, but it's actually even more general than a graph. The training set is going to have instances of this predicate, right? Because we're trying to learn it. It's going to have instances of, oh yes, Anna is a parent of Bob and Bob is a parent of Charles and so on and so forth, right? So it's going to have a bunch of stuff like that, but it's also going to have to have a bunch of stuff like this, right? Are there relations like, you know, has worth and links to? So what is this looking like? Declarations. Yes, they are. This is declarative knowledge, right?  Our training set now is a relational database, right? Relation, you know, L1 is another relation, right? There's the links to relation, there's the has-words relation. Those only had two arguments, but I could have a relation here with, you know, any number that I want. Okay? So when we're doing relational learning, this is often called relational learning, what we have is not just a table anymore, it's a whole bunch of tables, meaning a database, okay? Which is nice considering that, you know, like most of the world's information systems run on databases and we would like to be able to see how we're about to see how, okay? So my data is a database, right? And so I have different relations in that database, like the has relation, sorry, the has-word relation, the, you know, the links to relation, et cetera, et cetera, right? And I'm trying to build a rule out of those relations, okay? And let's say I have a rule in which I really have a bunch of those. What is the next thing that I can add? Let's suppose, for example, that in my database, you know, I'm trying to predict p of x, y, and I also have something like, you know, r, x, y, s, x, y, and t of x, y, right? So my database consists of four binary relations. Again, they could have many arguments, but for simplicity, they just have two, right? And I'm trying to learn to predict p as a function of r, s, and t, okay? So let's say that in my rule, I already have something like, you know, very trivial, r of x, y, if r of x, y, right? What can I add now? What are the first obvious choices? Just give me one suggestion of something I might add to the rule. Negated. No, yeah, sure. So that's one thing. I could have something like not x, y. Actually, I probably want to have both r, x, y and not x, y. So certainly we want to allow negations of these things. That was, in fact, my last point. But for the moment, let's ignore negation, r of x, y, if r of x, y. And I'm going to try to further refine this rule. How might I refine it? Yeah, exactly. I could add one of the remaining ones, right? I could now make it, you know, r of x, y and s of x, y, or r of x, y and t of x, y, right? And let's suppose that I just did that and now I can try the remaining one, right? So now I have p of x, y, if r of x, y, sorry, x, y, if r of x, y, and s of x, y and t of x, y. And now comes the really interesting part. Am I done with the things that I can add here? Certainly if this was propositional rule induction, I would be done, right? I have not used up all the attributes that I have. But in this case, am I done? Let's think back to the web example, right? Am I done once I have added my, you know, has word and my link from? Clearly not, right? I can keep adding more of those, right? What is the thing that can happen here that couldn't happen in propositions? What can happen here that couldn't happen in propositional rule induction? I can have the same predicate repeated, right? But what changed from one case to the other? The arguments. The arguments, right? That's the key that thing that makes this powerful is that my predicates now have arguments. And they could share arguments in very interesting and complicated ways. I could add the same predicate multiple times. I say, you know, this page links to this page that says this and to that page that is linked to by another page and I could even follow another link from one of these pages and go to the words that are two steps away.  So the moral of the story is I don't just have a choice of which predicates to add. I have a choice of which predicates to add with which arguments. So another question is should I just allow any addition of arguments any way that I want? That's the natural thing to say, right? That's my language. Add any predicate within your arguments. So for example, I could have p of x, y if r of x, y, right? And, you know, s of y, z, right? This is a perfectly legitimate rule, right? So this is a good thing. But let me give you another example that hopefully will make you think. What about the following? p of x, y, y, s of u, v? You like this one? It is surprising. It is surprising. Yes, this rule is surprising, right? But more to the point, indeed. More to the point. Is it a good idea to add suv to this rule? That's right. It fails the common sense test, right? I'm trying to classify x, right? Why am I talking about the relationship between u and v that have one relationship to x? It doesn't make any sense, right? So we probably want to allow this, but not this. Okay? On the other hand, notice the following interesting fact here, right? Is that this... I did have here in this rule that we agreed was reasonable a variable that never appeared before. I'm allowing this rule to involve objects that I never talked about before. So it's not that I only want to apply in them, right? That would be too restricted. And again, notice that in this example, my rule here, when I'm talking about b and c that did not show up here, right? And also, like, remember in our ancestor example, there's a key role being played here by z, right? z is this person in the middle that x is apparent of and who is then an ancestor of y, right? So I wouldn't allow that. So can you induce from these examples what the general rule for what we want to allow is? I wouldn't allow adding any antecedent with any arguments provided that exactly, at least one argument already appears in the rule. Doesn't have to be in the head, but it's in the rule. If that argument already appears in the rule, that means that there's a connection between what I'm now saying and what I was saying before, right? I can bring in a new page because it has a link to a page that was related to what I want to classify. And then once I have that page, now I could go look for links to that page, right? What I probably don't want to do is just bring in random pages that I'm linking to any of the pages that I'm talking about already, okay? So it's just from a relational database standpoint, it's just, like, doing a join? Precisely. In fact, this is exactly what happens. If you want to do this stuff, on this kind of large scale, you're going to do it by database drives. And that's all that's going on here is that this is really what a data log rule is, right? This is the reason database is, you know, if you think of this as a database query, right? What happens is that here, right, there's a non-trivial join between these two things, right? And here, these things don't join, right? They have no arguments in common. They're talking about different things. Okay? So this is the important point, number one, is that I will allow in my language any antecedent, any literal, with any arguments with a condition that I have to have at least one argument that appeared before, otherwise it doesn't make sense. Okay? This is number one. Number two is something that might seem a little odd at first sight, but actually is quite important that's why it's there. I'm going to allow the special predicate equal. Equal x, j, x, k means that these two variables are the same. So I could actually just replace them both by y. Okay? Now, why would I want to allow that versus not just in, like, if x, j and x, k are both going to be y, well, why don't I just call them y to start with? Why would I want to have this here? And let me give you a hint. This is not because of the representation. It has to do with the fact that we're going to learn these things using search that is necessarily greedy. So what might be the advantage of having this in there? Let me put it this way. Suppose that we already have this rule, right? And, you know, these rules all have the different arguments. What could be the advantage of adding an antecedent like equal x, i, x, j? What is it doing, right? It's basically saying that these two arguments that I had over here are actually the same. Right? Why might I want to do that? For j and x, x, y, k? It might... When I added these literals, right, it might not have been apparent at the point that at the end of the day the arguments should be the same. Right? And this, as I said, is going to happen very often, right? I'm adding a bunch of things, right? And then I realize, well, actually this part here really should be talking about the same thing as this part here. And if I don't allow this equality at that point, I'm host. You could also say that instead of allowing equality, you know, you should allow at some point replacing different arguments by the same. But the point is that often you want to do this in the search, in the beginning, when you were adding things greedily, remember they were just tied to the existing by one argument. But now if they have other connections among their arguments, right, that may only have become apparent once I add the other things that come around to this. So it can be very important to allow equality. It can also be very important to allow the negation of equality. Just as we want to allow the other particles to be negated, often the most interesting rule like a trivial special case. So I also want to allow not-equals. Questions so far. We just covered a lot of ground here. So now we know how to build a very powerful class of rules. But we still don't know how to evaluate our candidates. Okay, let's go back to what we had before. We had this heuristic that minimized, or sorry, that maximized my getting surprised, i.e. minimized my surprise inside the rule, right? And then we also multiplied by the coverage of the rule because we didn't want it to over-specialize, right? Let's do that here and see what breaks and then how to fix it, right? So remember, let's say that my rule is R, right? My rule so far is R, and L is the literal that I'm considering adding to the rule, okay? And now let's P0 be the number of positive bindings of the rule. What is this thing called binding? What is the binding of a rule? We didn't have this before. This has to do with the fact that now what is an example is no longer very well defined. Think of this as a graph. I have a very big graph of things and now what exactly is the subgraph that I'm going to use for this particular prediction? Well, that could vary. What determines the relevant subgraph is the rule, right? It's the things that the rule binds to. Binding is actually a technical term. I have a rule with these variables, right? And anything that those variables could be replaced to creates a binding of the rule.  So I can have a particular family and the rule applies to that family with its relationships. That's what a binding is, okay? So I no longer have a notion of an example. I have a notion of the bindings of the rules. You could say that in some sense all I have is one big interconnected mega-example but that's too much of a heading. Let's just look at the part of that big graph that matches the rule. That's the binding. Well, in general, you know, if the rule is good, it'll match many different subgraphs, right? It'll match this family and that family and that family, right? And that's the number of bindings that I want to count. This is what now plays the role of my number of examples. Now, of course, some of those bindings will be positive and some of those bindings will be negative. Think of the binding of the rule as a set of people, right? And their relations. In some of those sets, A really will be the ancestor of B or an ancestor of B and some of them it won't. The first will be positive examples and the second will be negative examples, right? This is a very important notion. Everybody on the same page? Okay, very good. So I'm going to count the number of positiv