e and negative bindings of the rule before I add the antecedent. Those are called P0 and N0, okay? And now the surprise of applying the rule before that is log, you know, minus log of P0 over P0 plus N0, right? That hasn't changed. Once we have defined what that rule actually applies to, we can apply our, you know, existing notion of surprise. Okay? And same thing after we add the antecedent, right? Now we've added the new rule to the rule, right? So now there's a new set of bindings and, you know, P1 is the number of those bindings that are positive and 1 is the number of those bindings that are negative. Remember, let's say I'm building a rule for an ancestor, right? In the beginning that rule is only about two people, X and Y. But once I bring in that third person that you're an ancestor of and then they're an ancestor of blah, blah, right? Now this rule binds triples of people. The rule used to apply only to pairs of people that now it applies to triples of people. Big difference. Notice we're in a whole different world from, you know, our good old propositional rule induction. Now there's much more going on. It's much more powerful. It's also more complicated. Okay? So now, but now again some of those bindings will be positive in that, in some of those cases the ancestor relation does hold between X and Y, you know, with that Z or some of those Zs and in others it doesn't. So now I'm going to have, you know, P1 and N1 and I have my new surprise. Okay? But now first of all, I have the same problem that I had before that, you know, I don't want to have a very specialized rule that has very low surprise just because it doesn't cover anything, right? So I'm going to need something over here as I had before. But there's an even bigger problem here, right? Which is we're really, if you think about it, comparing apples and oranges when we compare these two things. Because we may be binding different sets of examples. In the propositional case this could not happen. Right? But in one case we're talking about pairs of people and in another case we're talking about triples of people. Right? And the nasty little effect that this can have is that, remember the basic heuristic that we're using here to be confident of our rule is that it covers a lot of examples. Right? Once it covers a few examples we get suspicious. Because remember what happened in propositional rule induction is that as I added more littles the number of examples always went down. At best it stayed the same but adding more antecedents meant the example, you know, I was going to cover fewer examples. What happens in this case when I add more antecedents? Does the number of examples always go down? No, in fact it could go up by leaps and bounds. You know, let's suppose you know that I had 10 people in my data set, right? The first rule matched, you know, 100 and the new one is 1000. Wow! I just got an order of magnitude increase in the number of examples that matched my rule for free. Right? Clearly if we talk to something about this we're going to get all sorts of garbage, you know, out of our induction system. So what is the simple thing that we can do here that, you know at least heuristically fixes this? It's a very simple idea, you know, like, you know, one of the things that Quinlan is very good at is coming up with like simple heuristics that do the job and this is a very nice example of that. He's just going to make a very minimal change to what this part here of the heuristic means. And that changes the following is that this T here is going to be the number of positive bindings of the original rule that are also covered by the new rule. This is going to disallow cheating by multiplying the number of examples by having new bindings. If you think about it, I really only care about the bindings of the old rule. The new variables that I brought in are auxiliaries to help me predict what I really care about, which is whether this is a course page or whether these two people, you know, have a family relation with my ancestor. So by doing this, we focus on what we really want. I might have multiplied things by a lot. I don't care. I care about which of the old rule bindings are still bound by the new rule. This is actually not obvious, but after you see the idea, it's actually, yeah, this at least should work. And again, heuristically it works very well, and you know, FOIL is very widely used. Any questions? Okay, so that's FOIL for you. Or at least the basics of FOIL. Of course, the full FOIL system has many bells and whistles, and there are many issues in this type of relational learning that we're not going to deal with. He's just an example for you to think about during the break or at home tonight. He's a very simple example, you know, just to make things concrete, because we've talked about a lot of very abstract things so far. Let's make it concrete. Here's a graph. The simplest interesting example of a problem where relational learning gives you power, that propositional learning didn't give you is a graph. So here's a very simple graph. These are nodes in my graph that represent whatever entities you want. And arrows just represent the relational link too. So let's just say this is a very small segment of the web. And if I were to represent this as a database, it would be a database like links202, links201, and so on. So this is my data. And now let's say that what I want to learn is the concept of can reach. Can reach x, y means that I can reach y from x by following the arrows. So for example, can I reach 3 from 0? Yes. Yes, right, because by way of 1 and 2, can I reach 0 from 3? No, because I have to go against the arrows. So I have a database of links and I want to use the concept of can reach. Simple example. So my data is, first of all, it's my pairs of nodes. And then for each one of them, whether they link to or whether they don't link to. Sometimes we leave the not implicit. Sometimes we make it explicit. This is what's called the closed-world assumption in databases. Closed-world assumption means that everything that is not in my database is assumed false. So with the closed-world assumption, I wouldn't need to say this, but let's just suppose for clarity that I do say this. The downside of saying it, of course, is that a lot of times you imagine a database of flights that have all the pairs of cities that don't have a flight between them. That would be really inefficient. But in the simple example, let's suppose that you actually have it. And by the way, there's a lot of data. And the corresponding adjustments of the evaluation criteria. So now what are the hypotheses that I'm going to make? They're going to be rules that have can reach as the consequent. This is what I'm trying to predict. And what can they have in the antecedents? What literals can they have? Or what predicates can appear? So I'm trying to predict can reach using what? X, Y, and can reach. So X, Y, and link to. So I'm trying to predict can reach from link to. I can reach A from B if A is linked to something and something is linked to B. So I'm going to try to build rules that predict can reach in terms of link to. Anything else? Think back to the ancestor example. Let me put it back up. I was predicting ancestor in terms of what? Ancestor and what else? Ancestor itself. That's the fun part of this. It's the recursive rule. As always, there's a lot of power in recursion. Again, in the propositional case, this made no sense whatsoever. I can't predict the class in terms of itself. But now because it's the predicate with different arguments, I can predict ancestor X, Y in terms of ancestor Z, Y. Right? So in our can reach example, I want to predict can reach in terms of what? Link to and can reach. In fact, you probably already noticed that there's something of a nice homomorphism between this problem and the family problem. What is the analog of link to here? Parents. And the analog of can reach his ancestor. Right? And in fact, you can squint at a lot of different, you know, network data sets, social networks, right? There's, you know, the friends relation. Right? The famous social graph. Friends X, Y. And you know, friends are friends and all of that good stuff. Right? You can represent it all this way and then the corresponding rules. I don't know if Facebook is using this technology yet, but maybe they will if they're not. So hypothesis space is that we want to learn rules, also learn as form causes using the predicates link to and can reach. And so the exercise for you, which at this point is probably not very difficult at a high level, is figure out what would be learned by foil and also how. Right? You can probably figure out very quickly at this point how, you know, what needs to be learned here, but the question for you is like, how would foil arrive at this? And also, you know, what might be some of the difficulties and where do false heuristics come in here? But in the meantime, we should have a break. It's 8.06, so let's reconvene at 8.16 where we will look at the second major type of first-order rule induction. Let's get going again. Right, so so far we've seen how to do propositional rule induction and we've seen one way of doing first-order rule induction, which is very powerful and yet we got there by easy steps, because first we figured out how to learn decision trees, then from that we figured out how to learn propositional rules, and then we figured out how to lift that as it's called to first-order. But now what we're going to see is a completely different way of learning first-order rules. And this is actually a very interesting way and in some ways a very natural way to do this, and it's the following. You know, for example, how in calculus we define integration as the inverse of differentiation and then we figure out how to do integration. Right, and this actually happens in mathematics. We define an operation as being the inverse of another operation because we want to be able to invert it like even square root. Why did people invent complex numbers? So they could always take the square root of a number. And this turns out to be very powerful. Well, how about we take inspiration from that and do something similar here? So we're interested in the problem of induction. This is what machine learning is all about. Going from the specific to the general. What is induction the inverse of? Deduction. Deduction, precisely. Induction is the inverse of deduction. Right, so how about this? How about we formulate induction as the inverse of deduction? In the same way that you can formulate integration as the inverse of differentiation. I would say this is a brilliant idea. It occurred to, I think it was Steve Mogelton, a well-known researcher back in the 90s or something. Right now this is just this very big idea. Let's formulate induction as the inverse of deduction and take it that way. Let's make it just slightly more concrete. The classical example of deduction is socrates is a man. All men are mortal. Therefore, socrates is mortal. Yay, right? Sorry for boring you again with this. This is our starting point. This is deduction. I went from the general. All men are mortal. One particular thing that I knew about socrates which is that he's a man. From that I deduced that he's mortal too. Deduction is nice. Most of computer science is really doing deduction in various ways. Deduction is something that you can really trust. As opposed to this weird thing called induction that I'm trying to sell you and you're not sure yet if you're buying. So what would be the induction version of this problem? The induction version of this problem would be something like this. Socrates is a man and Socrates is mortal. Plato is a man and Plato is mortal. Aristotle is a man and Aristotle is mortal. Maybe what? Men are mortal. Maybe all men are mortal. Once you see enough of those specific cases your brain is just really good at this.  All men are mortal. And then once you've acquired that rule and the one comes some completely different philosopher let's say take your favorite philosopher like this. You go like, ah or in fact your favorite person but let's just stay with philosophers for the sake of fun. Aha, Leibniz is a man therefore Leibniz is mortal. So from the specific examples you generalized by induction and from that general rule then you did the deduction. Notice how they're inverses because induction went from specific things about specific people to a general rule and deduction does the opposite because those specific people are some other specific people. So this is the way we're going to try to do induction here. Brilliant idea if you ask me. But now let's see if we can make this work. And you know, a fair warning this is going to be probably the most abstract part of the whole class but bear with me and I think it will be highly worthwhile. So let us try to make this solve a little bit more formal. Here's a formula defining what we want to do. And we're going to sort of be playing with this formula a lot so let's take it one step at a time. Induction is finding a hypothesis. Right? From a hypothesis space. And let's call it a hypothesis H. Right? What do we want that hypothesis to do? Right? Think back to the analog of integration like what do we want the integral to do? What we want the integral to do is differentiate a function and then I integrate, I get the same function back again. Right? This is what that's doing. What is induction trying to do? You can think of induction as providing the missing link. I know that Leibniz is a man and I want to conclude that he's mortal. What is missing to go from one to the other? This is what I'm trying to induce. So this gobbledygook here is really just a more formal statement of the same thing. So let's say that, you know, XI is my Ith training instance, so my Ith philosopher or my Ith person in the family. F of XI is what I'm trying to predict, like whether they're mortal or, you know, whether they're somebody's ancestor or what not. And B is a new thing. B is all the knowledge that I already have. I already have an algebus with other formulas that say first-order logical things that I know about people and about mortality and what not, right? Remember, we said early on and we saw this very clearly that knowledge is essential to induction. The more knowledge you have, the better induction you can do. If you have no knowledge, you probably have as a data than your host. Here for the first time, we're going to make that knowledge explicit. We are going to call it B. It's my background knowledge. Let's say, for example, I already know that, you know, mothers are parents and fathers are parents. I already have. And now these XI's and these FI's, they are basically my examples. I give you XI and I want you to tell me whether F of XI is true or not, okay? So now here's what I want my hypothesis H to do. I want that for every example and its class in my data, D represents my dataset, right? In general, you know, a database, right? The background knowledge, together with my hypothesis and the example, they allow me to derive, this little T means derives, they allow me to logically derive, they allow me to logically prove that F of XI. You see what I'm saying here? You know, the reason I need the hypothesis is that the background knowledge and the information about the example are not enough to get to my conclusion. Yes, you know, I know that Leibniz is a man and I know all sorts of other things, but I'm not able to show that this guy is mortal. I want a rule that says that. This is what my H is going to be. If by a fortunate accident, just using my background knowledge and my information in the database, I could already correctly predict that this person was mortal, well, then I don't need a hypothesis. The hypothesis can be the empty set. So this is the general agenda of what we're going to do here. Right? Notice that what I have here is just, you know, this is a kind of deduction. It says if I know this and this and this, then I can infer that. Right? In deduction, I go from B and H and XI to F of XI. The sense in which we're going to be inverting deduction here is that what I'm going to do is go from F of XI and XI and B to H. This really is, in a mathematical sense, a kind of, you know, inverse of pressure. And it encapsulates very neatly this whole idea that we've been having that, well, in machine learning, the program instead of being an input is not the output. Right? That's what our H is here. The program that we're trying to induce. Okay? Any questions? Okay, very good. So we've defined formally what we want to do. Here's a concrete example. Right? Nothing like a concrete example to keep things clear. Let's suppose that, you know, what we want to do is induce the concept of child.  Okay? And what we have, you know, so what is our concept, right? It's over pairs of people.  And one such example could be a child of Bobbi's share. Okay? So this is my F of XI. I want to learn to predict that somebody is the child of somebody else. Obviously this is a very simple example, but it's enough to illustrate, you know, the general idea. Right? What is my XI? Well, my example is a pair of people here, right? Bob and Sharon. So my XI is everything that I know about them or that might be relevant to predicting this. So let's say I know that Bob is male, I know that Sharon is female, I know that, you know, the father of Sharon is Bob. Right? And let's say that in addition we have some background knowledge lack, like parent of U is V, if father of U is V. Right? This is true. If somebody else is father, they are also their parent. Okay? So first of all, you yourself just looking at this, can you, so let's do this in our heads first, right? So I have XI and B, right? Are you able to infer child Bob Sharon from these things? Or no? Actually, first of all, just you as a person, right? Do you know just by looking at these things? Actually, if I gave you this information, right, even without the background knowledge, just use the background knowledge that you have about family relationships, right? So I tell you that, you know, Bob is male, Sharon is female and, you know, the father of Sharon is Bob. Is it the case that a child of Bob is Sharon? Of course. Oh yeah, right? Of course, right? Common sense. We know that. Right? But the question is whether the program knows that, right? Does the computer know that? Right? And now you can think of, like, what did you use to arrive at that conclusion? Right? You use the fact that if X is Y's father, then what? Then Y is X's child, right? Yeah, you knew that. But the computer doesn't know that. We know the computer, we know what the computer knows, right? The computer actually knows something meaningful and potential useful, which is that, you know, parent UV, if father UV. But that's not enough. From male Bob, female Sharon, father Sharon Bob, parent UV, you cannot infer, you cannot deduce that, you know, child Bob Sharon. And that's the problem. Oops. This is good. And that is the problem. Is that I'm missing some information to make that deduction possible. So our goal in deduction is going to be to figure out what we need to add to the knowledge base to make the deduction go through. And then the deduction goes through. Any questions so far? So, what did you know that the computer didn't know, right? What could you add to this knowledge base that would actually infer that, you know, a child of Bob is Sharon? We've already seen one of these cases, right? It's the case that, you know, if father UV, then child UV. Right? There's also another one, right? What's another one? Well, it's sitting right here. It's the same thing, but with parent, right? Notice that both of these things are true, right? And do both of them allow you to infer that child Bob Sharon? Yes or no? Yeah. Yeah, right? In fact, if I know that, you know, father implies child, right? Since I have father here, I can get the child here. This is what we did, right? This is the easiest route, okay? But, and this again is going to be a general theme, is that is not the only way. There's going to be more than one way. If I know that parent implies child, right? Then because I also know that father implies parent, I can say, oh, father, therefore parent, therefore child. Okay? So there's more than one way. Which means that my deduction has more than one inverse induction. We shouldn't surprise anybody because, for example, the same thing is true of integration, right? Remember, when you integrate something, it's only out to a constant. That constant could be anything. So there's more than one answer. Similarly, right, there can be more than one square root of one, right? There's plus i and there's minus i. So again here, there's more than one thing that you could add to your knowledge base and make the induction go through. And we're either going to choose between them like, say, we think the simplest, the one that makes the knowledge base smallest, or we add all of them, let's say. Typically, we use the former, obviously. Notice also the following important thing. Did I use in this deduction the fact that Bob is male? Not really, right? I never used that. Did I use the fact that China is female? No, not either. And as always, what this means is that my database is going to have a lot of information that is irrelevant to the problem at hand. And a big part of the job of the machine learning system is to get rid of that. Figure out what's relevant and figure out what's not relevant. It would be a good day on which all the information that we have is relevant to the problem at hand. Questions? All right, so this is what we're going to try to do. Now let's, you know, so here's the statement of the problem, right? So what we have now, right, you know, computer science and logic and whatnot is deductive operators. And we can express this in the following format. If I have A and B, I have a function F that produces C, right?  F is the operation that transforms A and B into C, right? And in logic, we write that as AB derives C, okay? But these two things are really just different ways of saying the same thing. Okay? And our goal here in the rest of this class is going to be to figure out inductive operators that actually do the opposite.  Okay? So again, we're looking for a function except that now it's an inductive step that's being done as opposed to a D-ductive step. Okay? All right, so before we go into this let us see what the pros and cons of doing this are because there are some very important pros and some very important cons and you need to be aware of both of them. One of the, you know, the first obvious prove this is that the previous case that we've been talking about up until now, you know, including decision to induction and propositional induction and the foil and whatnot, is really what you get in this case when your initial background knowledge is nothing. Or at least it's a very weak background knowledge that is not made explicit in declarative form, right? So if we think what we're doing here with a case of no data or sort of no knowledge, right, then this just becomes the case that we had before. So this is nice because it generalizes what we've already been trying to do, right? But now, of course, it brings in something very important, a new, which is now I can make my knowledge explicit. It's my background knowledge B. That's where I really know. I actually have a list of formulas stating that I know that, you know, mother implies that I'm well-known and so on and so forth. So I can make that knowledge explicit and therefore, I can do things with it that I couldn't when it was implicit as in the case of learning a decision tree. And, of course, I have a lot more flexibility. I can put in knowledge that I know which I couldn't do in a decision tree and use that to help my induction and have the induction complete the knowledge and build on it. And moreover, this actually suggests a new type of learning algorithm. Right? going to do is I'm going to look for H, not blindly, not just by some greedy search that's trying to hit the right things in the dark. I have all that background knowledge to guide my process. When you learn, you do not learn from scratch. God forbid that you always be learning from scratch. Imagine being in this class while being a six-month-old baby. That wouldn't work. You cry a lot and that would be fine. You're always learning by building on top of the knowledge that you already have. The methods that we saw before, you know, they're basically the analog of the newborn baby, you know, like they really, they have something in their brain, very important, right, but they really don't know anything much yet. Now we can actually be guided by our knowledge. So those are the advantages. There are also some important disadvantages, which is important to be aware of. The first and very important one is that this doesn't allow us to deal with noise. Noise is very important in the real world. Some of my examples are misclassified. Somebody mistyped something. My sensor reading was noisy, right? This email was classified as spam, but it shouldn't have been. You know, you just pressed the wrong key or something, okay? Deduction does not like noise, right? Deduction is all about complete precision and, you know, it's either true or false and you say exactly what you mean. So these methods, at least as they stand, cannot deal with noise. There are, of course, generalizations and variations that can deal with noise.  So this is one minus. The other minus, which has probably already occurred to you, is the following, right? Remember when we said that large hypothesis spaces are good, right? Because they mean you can learn lots of different things, right? So you want the truth to be in your hypothesis space. On the other hand, large hypothesis spaces are bad because, you know, they're expensive to search and they really increase your chances of overfitting, right? And the hypothesis space that we're looking at now is huge. First of all, not only is it first order, right, instead of propositional, that's already a huge jump, but now it is going to involve playing around with all this knowledge, right? So I have a much bigger combinatorial explosion that I had before. So the bottom line is that these methods are much less scalable than plain propositional decision tree and rule induction. And that's probably the biggest reason why they are not as widely used, okay? They, at this point in the current set of the, are these things do not scale to, to say Facebook, right? I don't think Facebook is using this because they want to mine a network of, you know, a billion friends and this stuff doesn't scale to a billion friends. But it might scale to millions. So for some problems, you know, you can use this. And moreover, in the straight up between knowledge and data. If all you have is a lot of data, but not a lot of knowledge, then this is probably not the right choice for you, right? Use one of those fast propositional methods. On the other hand, if all you have is a lot of knowledge, but not a lot of data, those methods can take, make use of the knowledge and that there is not enough, but this stuff might be exactly what you need. And you know, to take an example of an area where this has been applied to great success, drug design, right? My molecules, you can think of them as graphs. I want to know which molecules, for example, cause cancer or which molecules actually stop cancer, right? I can represent them in this form. I often don't have a lot of data because the data point, this molecule is carcinogenic or this molecule binds to this virus. That knowledge is very hard to come by. It requires a lab and experiments in the lab. On the other hand, there's like reams of biology papers and textbooks out there with biology knowledge. And I can write down that knowledge. This is what makes, you know, molecule carcinogenic or you know, this is what I know about organic chemistry, right? The knowledge doesn't have to be directly about the task. So in those cases where I don't have a lot of data, but I have a lot of knowledge, this might be what you want to use. All right, so let us then look at how to do this. And we're going to use exactly the same strategy that we used before. We're going to start with the propositional case, right? Cause that's the simpler case. If we don't know how to do this, you know, induction by inverting deduction for propositional rules, we don't know how to do it for the first order case. It's too hard, right? What we're going to do is we're first going to solve the propositional case. And then we're going to generalize it to the case where I have predicates and arguments and all that stuff, just like we did before. Okay? So let's start with the propositional case. And the place to start, of course, is with what is deduction exactly? Now deduction can be done in many different ways, but usually it's done using what's called the resolution rule. How many people here have heard of this stuff? Resolution? Just so I can have, you know, I can calibrate. If you've heard of this, raise your hand. Okay, very good. Nobody has heard of it. That is the second best case. The best case is everybody has heard of it and we just, you know, breeze through. The second best case is when nobody has, cause that way nobody's bored. Right? So hopefully nobody will be bored here. Well, at least if you're bored that it's because I'm a bad teacher, which, you know, so what is resolution? Resolution is how most theorem provers work. When you hear about, you know, computers proving new theorems automatically with our help from people, or proof being checked automatically, or, you know, there's lots of things that used to improve. Like for example, software and harder verification are often done using theorem proving. You prove that that circuit does what you want. What are those guys using when they do that? They're probably using resolution. I mean, there's many things that you can use, but resolution is probably the single most widely used. And here's resolution for you in one very simple little table. Right? This, and this table, you know, you can read it like you read an edition, 3 plus 4 equals 7. Right? So what I have here is that from this and this, I can deduce this. So what are these things? Here, what I have is just the simplest case, right? So, first of all, each of these things is what is called the clause. A clause is just a disjunction of literals. And the literal is just a statement or its negation. Like P, for example, could be the statement, it's sunny today. And L could be the statement, we're in Seattle. Okay? You could also have the negation of that. We're not in Seattle, so you could have something like not P or not L. Okay? And the clause is just a disjunction of those things. Clause are useful to us because whatever you have in first thought, logic can always be converted to C and F. Clause are normal form or conjective normal form. Okay? So let's assume that everything that we have is in the form of clauses, right? Makes life much simpler, more uniform. And here's what the resolution rule says. It says that if I have, this is not the general resolution rule, but it's a simple case for us to get a handle on it. It says that if I have, in my knowledge base, the clause P or L, remember P and L are just Boolean variables. And I also have the clause not L or R. I can infer the clause P or R. Right? So these are what I had before, and this is what I have after I apply resolution. So another way of saying this is that P or R is a deductive consequence of P or L and not L or R. If I know those two things, it follows with complete certainty that P or R. Now, why is that the case? Can anybody tell me? What is the basic insight behind resolution? Let me give you a hint. In logic, the basic thing that logic commits to is that every statement is either true or false. Right?  Right? So every one of these literals here is either true or false. Okay? So in particular, here's the hint. Let us focus on this literal L. Right? This is an interesting literal because it's actually the one that appears in both of the clauses. Right? And we know that, you know, that L is either true or false. Right? So what can we tell about P if L is false? It's true. It must be true. Right? One of them is true. L is false, so P must be true. What can I tell about R if L is true? It must be true. Then it must be true, right? Because not L is false. Therefore, R must be true. Okay? So to recap, I know that if L is false, P must be true. On the other hand, if L is true, then R must be true. Right? And what do we know about L by logic? Is that it's either true or false? Right? Therefore, what do I know about P and R? One of them is true. One of them must be true. Right? Because either L is true or L is false. In the first case, P is true and in the second case, R is true. Right? This is what the resolution rule is all about. Very simple but very powerful. Any inference that you can do in logic, you can be using just resolution and nothing else. Question? Yes, you can write this as like not L implies P. Right? Yeah, yeah, absolutely. This is a very good point. So often when you're looking at these clauses and trying to figure out exactly what they mean, it's good to remember that, you know, the clause not A or B is another way of writing A implies B. So in my knowledge, it's usually what I have is things of the form A implies B. Right? If you have this symptom, then you have something. Right? But when I convert that to causal form, it becomes not A or B. Because remember, an implication is true if the consequence is true or if the antecedent is false. Right? If the precondition is false, then the implication is true no matter whether you have, if you don't have the symptoms, then whether or not you have the disease, the rule is valid, the rule is true. Okay? So you can look at this, for example, and say, oh, what I'm saying here when I say not L or R is L implies R and so on. Okay? In fact, we're going to see an example of this in a little bit where very much, you know, the implication form is very intuitive. But to do resolution, we need to convert things into clause form. Okay? So did everybody get what the resolution rule is? This is absolutely key to what's going to apply. Okay? So what is the general rule? The general rule goes like this. So how do I apply resolution? Right? I have a big knowledge base of stuff that I know. And now I have a question, I have a query. Right? Is it the case that solvers is mortal? Is it the case that Anna is the mother of Baal? I want to know. Can you figure that out for me? And I just claim that you can figure that out using resolution if you can figure that out at all. Right? So how would you do that? Well, you have to find a sequence of applications of the resolution rule that will take you from what you know to the question that you're asking, either yes or no. Okay? So how do we do that? Well, here's the idea. Notice that the key thing that the resolution rule depends on is that I have a literal in one clause that appears negated in the other. Right? This is the thing that's going to bind them together into a result. Right? The result, by the way, is called a resolvent. This last clause here is the resolvent. So here's the recipe. Given two clauses, C1 and C2, I find the literal in one clause that appears negated in the other. Right? Look through your clauses and try to find, you know, something that appears negated in one but not the other. And these two are a candidate for resolution. Okay? And then how do I form the resolvent? Right? If I have found that, what is the new clause that I can now form? Right? Well, look at what happened this example. Right? The two L's disappeared. Right? They kind of cancelled each other up, colloquially putting it. Okay? And then what's left is the rest. Right? Sorry, the P became this P and the R became this R. Okay? So what is the recipe here? Is that the negated one disappears and all the other ones get grown together into one new clause. Okay? That's what we do. Here's the same thing, you know, just written as a formula. The resolvent C is going to be C1 minus the singleton set formed by L, union C2 minus the single set formed by not L. Okay? So we're thinking of the knowledge of this as a set of clauses. Okay? Everybody see this? Why did we take the trouble to write this down formally? Because hey, we're trying to invert this. Now that we've written it down like this, we can figure out how to do the inverse. Right? What is the inverse of this? Right? So, deduction was going from C1 and C2 to C. Right? What is induction going to be? Right? In deduction, we went from the two clauses to the resolvent. What is the inverse of this? Going from C and C1 to C2. Exactly. Now I have the resolvent and I have one of the clauses and I want to figure out what the other one is. Right? Remember, I know that Socrates is mortal. And I know that Socrates is human. What I want to figure out is the other mystics thing that combined with Socrates is human would produce Socrates is mortal. Right? So to do this diagrammatically, actually, let me jump to the next page. But actually, here it is diagrammatically. Right? Well, let's just do this actual example. Right? And we're going to use this as a running example. The font is a little small, unfortunately. Hopefully, you can read this if you can't let me read it to you. Right? So let's look first at a very simple example of deduction by resolution and then see how we invert it. Right? So here are the two clauses that I start with. C1 is pass exam or not no material. These examples are carefully designed to appeal to the student in you. We are very proud of this, you know, deep savvy. This one means, this one says no material or not study. So let me ask you first, what do these clauses mean in English? Remember, going back to this notion that a clause is really just another way of saying an implication. What am I saying here? If you know the material, you'll pass the exam. If you study, you'll know the material. Yeah. Right? Does anyone disagree with this? Very good. Right? Very natural things to say. Right? And what is it that you could, so don't think about resolution for just a second. Just use your common sense. What can you infer from this? Right? Is there another rule that you can infer from these two rules? A very important rule in your life as students? Right? You know that if you know that, if you study, you will know the material, right? Or sorry, it goes this way. Oops. Right? If you study, you will know the material. And if you know the material, you will pass the exam. Therefore, what can you say? If you study, you will pass the exam. Right? Aren't you learning amazing new things in this class? Yeah. So here it is. Well, if you study, you will pass the exam. Written in clausal form is pass the exam or not study. Okay? So hey, resolution and common sense agree. Okay? So this is our little example of deduction. Everybody got this? Okay, very good. But now what we want to do is induction. We want to do the inverse of this. What is the inverse of this? Well, deduction, right, was going from this and this to this. Right? Induction is the inverse. Right? In induction, I have the result. Right? And I have one of my two clauses. I want to figure out what's missing. I want to figure out the second clause. Right? That's the goal here. So over to you. How do we do that? Right? Let's suppose for just a moment that I hadn't seen this yet. Right? How do I figure out what needs to be there? This is really, once you've got this, everything else kind of follows. Right? So let's look at these two. Right? This clause was pass the exam or not know materials. Right? And this clause was pass exam or not study. So what does this clause have to be? What has to be in it? The not pass exams. The not pass exam. Why is that? Very good. Why is that? From the rule before, you know that the other two to combine to make the resultant need to not have, they take away pass exam. Right? On the first slide. Right? Absolutely. So notice the following, right? Pass exam. Right? No, sorry. What did you say? You said this rule has to contain what? It has to be the, oh, I say to the reverse. But not, they need to contain not pass exam. The one that we're looking for. On the right. Yeah. It definitely needs to contain no material because you know that the the clause that's in both of them, the one negated, is the one that you remove and you know that it's not in the final one so it must be in the other one. Exactly. I actually jumped the gun and I thought that he was saying what you're saying. Right? So very good. Notice the following important thing. No material has disappeared. Right? No material is in C1 but it's not in C. Right? So how do we make a little disappear? There's only one way. Right? It's got to be negated in the other clause because that's the only way a little disappears. Right? Because then it appears in one clause and in the other clause negated. Right? So rule number one is the stuff that was in this clause but not this one has to appear negated in the other one otherwise this doesn't work. Right? The resolution wouldn't do the trick. Right? Everybody agree with that? Okay. Point one. Point two. Point two is actually the the easier one in some ways. Right? What is the other thing that has to happen? What else needs to be in this clause? Not study. Not study. Why? Hey, it just came out of nowhere. Right? Not study was not in C1 so it has to come from C2. Right? So there we have it. I now reveal the truth. You know this is like you know scratching those things with a coin. You see if you want to allow it. Right? This is high-tech at its best. Right? So here's our clause. No material. Right? The negation of of the negation of not no material. Right? Is here. So these this is the literal that is actually going to allow the resolution to go through. Right? It appears not negated in C2 and negated in C1. Or not study. This not study goes from this clause to this clause. Okay? So the general rule is let us generalize from this. Right? I have one of the clauses and I have the resolvent. The other clause needs to contain all the literals that appear in the resolvent but not in the first clause. Right? They have to come from that. It also needs to contain the negation of what disappeared from the clause to the second. Right? Or to the resolvent. What happens if more than one literal that was in the first clause is not in the resolvent? The answer is very simple. Nothing happens. That one could not have been obtained by resolution from the first one. At least not in one step. With multiple steps maybe. Okay? All right. So any questions about this example? This example really encapsulates the whole idea here. So here's our general and more formal statement. So here's my recipe for doing inverted resolution in the in the in the propositional case. Given my initial clause is C1 and C where C is the resolvent. Right? Remember C is the thing that I'm trying to come up with the rules to be able to infer. Find the literal that occurs in the first clause C1 but not in the resolvent. Right? Look for a literal that has disappeared. Not no material in our case. Okay? And now supposing I find it. Right? I can form the second clause in the following way. The second clause is going to be C the resolvent minus right? C1 minus that literal. Right? Union not the literal. Right? So let us parse this. Right? This was a big multiple. So let's see what happens here. C2 is going to contain everything that C contains that couldn't have come from C1. Right? This is the not study literal. Okay in our example. Right? So everything that is in C that wasn't in C1 right has to have come from C2. So we need to put those things in there. Of course you know excluding the L because that one's going to you know actually disappear and for a different reason. Right? And in addition of course C2 has to contain the negation of L to make sure that it cancels with L and the resolution goes through and L no longer appears in the in the in the resolvent. Okay? Everybody agree? So here in one nice little formula is a very interesting idea for doing machine learning. For doing induction by inverting deduction. In particular by inverting resolution which is the most widely used approach to deduction. Any questions? Very good. But of course this was the easy part. Now as to first if this is all that we're going to do we probably wouldn't have gained that much compared to what we already had. In fact I don't think I've ever seen this type of induction used for propositional rulesets. For first order rulesets it's probably at least as widely used as the false style are probably more widely used but you know it's definitely widely used there. So how do we take this propositional idea and go to first order? Okay that's the last thing we're going to look at today. So first of all let's see how we do first order resolution. Right? We saw how to do resolution in the propositional case. The difference is that now in first order we have predicates and arguments not just you know boolean symbols. Okay? So how do we do resolution in this case? This is actually where things get more interesting. This for example what gives you know prologue the power of the full programming language is that it can do these you know argument combinations and replacements and you know come up with answers to not trivial questions. So the big difference as we saw between propositional and first order is that now we have arguments. Right? And the difficulty that or the interesting twist that arguments introduced right is that now finding a literal and its negation you know in order to do resolution is no longer just a matter of having something like you know r and not r. Now we have something more like you know mortal of sorry human of Socrates. And on the other hand we have something like you know a human of x implies mortal of x. Right? By the way I made it the universal quantifier here because that's what people do in prologue but this this just means that you know all humans are mortal. Okay? Now notice what is it that you want to happen here in order for your inference to go through right? What I would like to do is to infer from this that m of s right? But the problem is that this rule here doesn't even talk about x or s right? It talks about x. So how do I make the connection? Well the connection comes from the fact that this rule applies for every human right? Every x. So in particular it applies to Socrates it applies to s. So what I need to do in order for this to go through is I need to unify h of s with h of x. This is the technical term unify. What we're doing here is called unification. I want to make these guys be the same. Why do I want to make them be the same? Because remember h of x implies m of x is the same thing as not h of x or m of x. Once I've turned these two guys into the same thing now they resolve. One is the negation of the other. So what do I need to do in order to unify them? Well g, in one of them I have s and in the other one I have x. So what I need to unify them is to replace x by s. This is called substitution. What I literally do is I substitute s sorry I substitute x by s. In general I might need to substitute a whole bunch of things so I'm going to have a set of these things. This is called a substitution right? In the simplest cases what it does is it replaces variables by constants like the variable x by the constant socrates so that universal rules can apply to concrete people or to specific instances of people. This is really where deduction does its thing. So I do the substitution in order to have two little s that unify. And then once they unify I can apply a resolution just as in the propositional case. The power of this rule of course is that it's saying something in one short expression for all seven million people. In propositional logic if I wanted to say that people are mortal I would have had to say this for every single person separately. Anna is human therefore she's mortal. Bob is human therefore he's mortal.  In first order logic instead of seven billion statements I just make one. But then I need my substitution in order for the variable to actually apply to the constant. Everybody follow this? Very good. So what does first order resolution mean? I no longer have to just look for two little s that unify. There are the one is the negation of the other. I have to look for two little s that I can somehow unify by finding the right substitution. Like for example in this case replacing you know x by s did the trick. And I'm going to represent that set of substitutions by theta. And L1 theta is L1 with that substitution applied to it. So L1 theta for example is L1 with every occurrence of x replaced by s. So for example this h of x implies m of x after applying that substitution will become h of s implies m of s. And then at that point if I have found that, if I have found two little s such that with some substitution one becomes the negation of the other at this point I can apply the resolution rule to those little s subject to those substitutions. So that is going to go through only when x is suffered. It obviously will not go through when x is Aristotle. Unless I also happen to have Aristotle in my database but let's ignore that case. And then once I have that everything works as before. So you know a slightly good thing to say would be well resolution in first order is just the same as in propositional logic except with substitutions. So what is my what is my rule now is that I form the resolvent by including all the little s from c1 with the substitution theta and all the little s from c2 with the substitution theta except for L1 with the substitution theta and not L2 with the substitution theta. Notice that apart from the phrase with the substitution theta that I just repeated four times this is exactly the same sentence as before. So here's my recipe. What is my resolvent going to be? It's c1 minus l1 with the substitution theta union c2 minus l2 with the substitution theta. And again this form is the same as before except with these new interesting little theta added. Questions? All right so finally right we're scaling the mountain and we're almost at the summit. Here comes the summit right. The base of the mountain is wide but the summit is thin and indeed you know this summit is very thin it's just this one little point. So what am I saying here? Right now you have the pieces all you have to do is put them together. You know how to do propositional inverse resolution right? You know how to do first order resolution and now we just have to figure out how to do first order inverse resolution. So what's going to happen? Remember I'm looking for c2 right given c and c1 right? So what's going to appear in c2? What little s must c2 contain? Think back to the propositional case again it's going to be very similar right? It has to contain right what is this whole part here doing? Right let's start by just revisiting the propositional case and let's pretend that the that the theta's aren't even here okay? I have c minus c1 minus l1 right? This is what we had before it's all the little in c that didn't come from c1 have to come from c2 you agree? Very good but now comes this interesting part so by the way I forgot to say theta1 is the substitution that I applied to c1 and theta2 is the substitution that I applied to c2 right? This is a new complication right? I'm looking for c2 but there's also some you know finally when I have c2 and I apply it to get my resolution right? It's c2 with some resolution with some substitution right? So let's call that theta2 right? So can anybody tell me what this theta1 theta2 to the minus 1 is doing here? Theta2 to the minus 1 of course means the inverse substitution right? So first of all what is theta1 doing here? The normal substitution you applied to. Exactly right? This is what I applied to c1 to get c2 right? So that that that goes through in both cases right? Whether I'm doing you know deduction or induction right? So I took all these things in c1 right? And I put them through theta1 to get to c right? And now it's comparing to that that I'm going to see what's what needs to come from c2 right? Very good. Everybody got this or everybody has questions? But now comes the most interesting part what is theta2 to the minus 1 doing there? This is where you really see that this is an inverse operation that we're doing here right? I have some stuff that appears in the final clause that came from c2 right? But by deduction I applied theta2 to c2 to get to c right? So if I want to get from c to c2 obviously I have to apply the inverse substitutions. If I substituted you know x by socrates to get here right? Now to go the opposite way I have to replace socrates by x right? And notice this is not some little detail. This is where the induction happens. Induction happens when I go from something that was about socrates to something that's about any hex any human okay? So this theta2 to the minus 1 here is absolutely crucial. We're going to see an example of this shortly you know our same you know study no material exam okay? Alright so can anybody tell me what the second part is here? What is this model 1 here? It's the book that's going to book to c1. Right this is the negation of the little that disappears from class c1 right? Just as before. Just as in the propositional case right? Everybody agree? And now what is theta1, theta2 to the minus 1? Well it's the same thing that happened on the other side right? l1 got you know got theta1 applied to it to get to c but not to get to c2. I need to apply the opposite of theta2 and then I get my c2 okay? Everybody agree with this at this very abstract level? Of course I recommend that you go over this a little bit more carefully you know in your copious free time. Also Mitchell has a very good you know explanation of this so you know I encourage you to look at that. But in the meantime you know just to make things clear and concrete let's let's look at an actual example and this is by you know like one one system that does this is called Saigol. So let's look at an example of what Saigol would do here right? So here's our family example so actually I like this is not the no material example it's a much more interesting one. This is our original you know father child example and what we're going to try to do here is actually something more ambitious. We're going to try to learn the concept of grandchild. This example is going to last to actually show the full process or something more like the full process opposed to just one step right? What we've been seeing so far is really only one step of resolution and for only one step of inverse resolution but a lot of the power of this comes from when you can go through a whole proof tree and have all these inverse steps right? Basically what's going to happen in a real system like Saigol is that I have this proof that I would like to make right? I want to prove this result and now I'm trying to form the the proof tree but there's holes in it there's things that I need to have to make the proof go through and those are the things that I'm going to induce okay? So what we have here is a very simple proof tree and we're going to see how we fill in the holes. So let's start you know on the left side here right? So here are some of the facts in my knowledge base okay? So this is my data some of the facts in my database. I know that father Tom Bob okay? This is the fact and I know that father Shannon Tom okay? And I also know that grandchild Bob Shannon okay? And presumably I have a whole bunch of examples like this but let's just focus on one here right? What I want to do is infer from this the concept of grandchild okay? And you know let's just focus on the father case there's also the mother case but you know let's just focus on father two to keep things simple right? What is the rule there right? Let us preview what needs to happen here. What is the rule for somebody being somebody's grandchild as a function of father? A is B's grandchild if what? If A is C's child and C is B's child right? Right? So if it is the case so you know Shannon is a grandchild of Bob right? Why is that the case? Because Bob is the father of Tom and then Tom is the father of Shannon right? Everybody agree? We know this. The question now is like how does the machine learning system figure it out? Well let's see. Let's apply you know our first order inverse resolution ideas right? So this is my C1 and this is my C right? So if this is my C1 and this is my C what do we need to have in C2? Well first of all what has shown up in C that was not in C1? Grandchild right? Right? Grandchild appears in C and did not appear in C1 so it must have come from C2. Everybody agree? Right? So here's grandchild and let us not worry about the arguments just yet right? So what is the other thing that has happened from C1 to C right? Grandchild appeared but something disappeared. What was it that disappeared? Father right? So what do we know about C2? What does it have to contain? Right? It needs to contain not father you agree? Okay very good so here's the clause right? Grandchild or not father right? But now let's look at so but this is only half the story right and maybe not even the most interesting half of the story. Let us look at the arguments. Well so first of you know let us look at people right? Who appeared and disappeared between C1 and C right? Well let's see. Bob appears in grandchild right? Bob appears in C but Bob did not appear in C1 so where must Bob have come from? It must have come from C2 right? And Bob appears as the first argument of grandchild right? So it must have been the first argument of grandchild in C2. There are no two ways about that okay? Everybody agree? Very good. Well likewise Tom has disappeared from C1 right? So we need something in C2 that negated that. We need something that negated father with Tom as the second argument. Well here it is father with Tom as the second argument okay? Now what remains? What remains is the most important part. What remains is Shannon and X. Why couldn't I just let this class here be grandchild Bob Shannon? Would that work? Right? So this literal right grandchild Bob Shannon appeared in C right? So it must have come from C2 right? Well if in C2 I just put grandchild Bob Shannon does that do the job? Well let us be let us not worry about induction for just a second right? The problem we are trying to solve here is like I need the literal grandchild Bob Shannon to be in class C2 so that it appears in class C right? And let's say that I just put that literal in class C2 right? That works right? So there's nothing wrong with class C2 being grandchild Bob Shannon or not father you know Shannon Tom right? Because remember X is the same on both sides right? So why did I do this? Why did I replace why is my theta 2 replacing or my theta 2 to the minus 1 actually be Shannon replaced by X? Why did I do that? I didn't have to. Why did I do that? At the same time I'm free to do that right? Because if this is the substitution if I have grandchild Bob X and then I replace X by Shannon I get grandchild Bob Shannon and everything goes through right? So this also works but why did I go to the trouble of replacing Shannon by X? Grandchild Bob Shannon. Grandchild Bob Shannon is not really interesting. Precisely. I remember I'm trying to induce general knowledge here. I'm really not interested in just understanding who in this family is whose parent. I want to know the general rule for what makes somebody somebody's grandchild. Therefore I want to go from specific people to statements about all people and that's why I deliberately replace Shannon by X. This is what's giving the generalization. Remember inversion often has a lot of options. We're seeing a place where we have many options and so what we do is we pick the option that we like best. Not all inductions are equally good. I want to do more here than just make this go through. I want to learn the most general and accurate knowledge that I can. Any questions? You can certify yourselves that this all works by you know just not taking this as an ordinary problem of deduction and saying if I have this C1 and this C2 do I get C and you know clearly you do. But you know you can go through this as an exercise at home. So far so good? Okay so but now there's one more step. But now basically you've got the hang of it. It's just with a more complicated clause. So now let's see. Now we're going to go to this part of the proof tree and now what happens? Well grandchild appears here right and it does not appear here therefore it must have come from here right. Very good. And again look at this thing right. I had the grandchild bob x but now I have grandchild yx because I replaced you know bob by y because again I'm trying to generalize. And now notice that actually the little father does appear here and here but now I have to look at the at the arguments in the substitutions very clearly and see look what I have here is father tom bob and what I have here is not father x tom there is no way to unify these two right. You know if it can you know why do I have two fathers here right. Why couldn't I just use the father from this side. Well notice that the father here has bob as the second argument and this father has tom. There's no way to unify these two. This one is talking about bob being the father of tom and this one is talking about tom being the father of summer. There's no way to equate them. Okay so again what has to happen is that this one has disappeared right so I need to have its negation over there to make it disappear and this one here right has to have appeared so I need I need it here. At this point things are getting pretty complicated and again I suggest that you go through this you know at home but hopefully the general idea should be clear. I have put into this clause all the stuff that that is in this one but couldn't have come from here and the stuff in this clause that disappeared I negated it and put it in here plus I took all my constants and generalized them to variables because I want the general and lo and behold I have induced the definition of of grandchild right. Again if you turn this into implication form it says that if if father xz and father zy then grandchild yx bingo victory okay and of course the beauty of computers is that they will do this thing for you millions of times in seconds without complaining.  Good deal. Now you know truth in advertising it's not that simple more things have to happen but at a high level this is what's going on. Okay questions okay very good it's late we're almost done let me just mention one little thing progo. When you apply these systems like like seagull in practice you get a huge combinatorial explosion because there's all these ways of taking little and combining them and of finding resolutions and whatnot so you need something else to control the search and one very popular thing and this is what progo does is that it first tries to find a actually kind of the opposite of what i just showed you here it tries to find a specific rule not the most general possible rule but a specific one that accounts for the data and then it does the search based on that rule only within what that rule permits okay and this is the usual trade-off of overfitting right in some ways we're less powerful we might you know have fewer things that we induce now on the other hand i really really have helped to control my search and now it's much more efficient and i'm much less likely to overfit okay again i'm not going to go into the details of that here but it's important to realize that doing this in practice is not just applying something like seagull out of the box there's things like progall and systems like elephant whatnot you know there's a lot of stuff in this area okay all right any questions about any of this thank you for your persistence and alertness the good news is this was the hardest lecture in the whole class we will see other things that are hard in other ways but in some ways this was the hardest and also we've seen how to take rules to the first order level you can take anything that we're going to see in the following weeks to first order level we're not going to talk about how we do that here because there's no time for everything but at least now you have a sense of how machine learning can be powerful enough to induce you know programs from data not just you know a simple you know spam classifier based on words and whatnot okay so remember that we have no class next wednesday because i'm traveling and what we're going to have is you know you must be glutton's for punishment and you know we are certainly glutton's for meeting our punishment we're going to record in next week's class here tomorrow so you know probably most of you can't come and that's fine what that means is that you can just you know watch the class anytime that you want on your own time including you know next thursday at you know 6 30 p one or you can come to the class here or or remotely if you want okay and after that you know the class is going to be on the web right no no sorry yes sorry i forgot to say tomorrow it's set four so i i sent an email to the list about this did everybody get it yeah so unfortunately you know we couldn't do it at 6 30 because the the the room was was not available did it go to your math business no this went to the course list so if you have not subscribed to the course list please do because we send these announcements there and anyway so assuming you missed that message you know just to recap we're going to record next week's class tomorrow here at 4 p.m and you can come here or you can watch it remotely or you can then just you know at microsoft and you can then just you know watch it anytime next week okay all right and in the meantime you know have fun with your projects all right um welcome back long time no see today we're going to talk about instance-based learning instance-based learning is just about the simplest kind of machine learning there is it comes in a number of different flavors the first one we're going to look at is probably you could consider the oldest machine learning algorithm and certainly the simplest it's the famous canyers neighbor algorithm and then we're going to look at other forms of instance-based learning and we're going to conclude with look at collaborative filtering collaborative filtering is these days probably the most well known application of instance-based learning and it's what your second assignment's going to be about you're going to develop a collaborative filtering system and apply to the famous Netflix data it's too late to enable in dollars but you know you might win the next month as i mentioned there was someone in this class who didn't know any any machine learning before and you know very interested in it then went on to be you know a member of one of the two top scoring teams so first of all what is instance-based learning and why is it so simple and and potentially so fast the idea in instance-based learning is to do as little work as you can at learning time it's also known as lazy learning lazy learning in this space line got not exactly the same thing but at this point we can think of them as the same thing the idea in instance-based learning is that what i'm going to do when i see the data is nothing right if you think about it that's the fastest algorithm you can possibly imagine right it's always zero you do nothing you've never seen an old zero algorithm before you're never going to see one again this is the only old zero algorithm that you'll ever see so what i do with my database of you know training examples you know x size and their corresponding classes is nothing i just leave them there on the disk and hope for the best right this is like not studying for your class and waiting till the you know final comes and then when the final comes of course at that point you scramble right you didn't study you don't know anything so what do you do how do you quickly figure out what the answer should be right well the idea in this neighbor as the name implies is that when a new query instance comes along say i have a new patient and i want to decide what this patient has you know tuberculosis or whatever what do i do at that point i just quickly scan through my database and try to find the closest patient in terms of their symptoms and test to the one that i'm seeing now okay and then whatever the prediction for that uh item was i make for the new item right if you think about this is not a bad heuristic right if you if you find two patients whose records are pretty similar there's a good chance that the diagnosis will be the same this can actually work surprisingly well okay so if my nearest neighbor is xn all i do is i estimate f of xq notice the hat here that says it's an estimate as f of xn okay very very simple thing this algorithm as it is doesn't always work that well there's one very simple change that makes it work a lot better in fact makes it compared to with a lot of much more sophisticated algorithms and that is simply to just use the k nearest neighbors instead of the single nearest one okay so what you do you know again at learning time you don't do anything it's still a zero what happens now when you see a query is that you find the k nearest neighbors like say the three or the five nearest neighbors okay each one of those has a class and then you just vote if one class is the class of three of the five nearest neighbors and one is a class of two well the first one wins okay if what we have is a regression problem right we're trying to predict a continuous variable instead of a discrete one then what might we do right i find my five nearest neighbors i just treat five numbers and i want to predict a new number for this example what do i do you already have some formula based on the regression yeah well you're getting you know way too fancy for a simpleton is here right what's what's an even simple thing that you can do right i want to predict how much you buy from my catalog right and i know that they each bought you know a certain amount of dollars and they're the four closest neighbors to you so what can i predict for you check the distance even that is still too fancy right you've almost covered the whole lecture right yes we could wait them by distance right the closest ones probably mean more right but if i if i just tell you your five nearest neighbors have these values and what would i predict for you mean yeah just the mean right just average right that's a perfectly sensible thing to do now the average could be weighted and we'll talk a little bit about that later right but the basic idea is that for discrete problems k nearest neighbor just votes and for continuous problems you know it just averages right fairly simple okay so um as with all methods it's good to bear in mind what the advantages and disadvantage of this are right so what are the advantages of of um you know nearest neighbor methods in this and space learning in general well obviously one key advantage is that the training is very fast truth in advertising once we get to the some of the fancier versions of this that speed at training time naturally can disappear but at least in the basic version you know the things that training time can take no time another important advantage which is a little more subtle is the following is that if you want to learn a very complex target function well this can be very hard but with these methods you could actually learn that a very a very complex target function very easily because what happens is that when you memorize those examples and then you find the nearest ones at test time implicitly you could be learning a very complex function we will illustrate you know how this happens and look at it in a little bit more detail you know in a while but for the moment you keep that in mind okay another thing that is sometimes an advantage compared to something like say a decision tree or a set of rules is that with these methods or at least with the most basic version of them you don't lose any information but with the decision tree once I form the decision tree I don't have the training there anymore maybe I'll regret that maybe at some point I would wish to know what that point was in years later I still have my whole database right so I haven't lost that information so these are the advantages now what are the disadvantages right well one prominent and obvious disadvantage is that this can be very slow at query time and in fact the more that you have the slower it gets usually having more there is better because I can learn a better model but here having a lot of there could really kill it let's say trying to control a robot in real time right then you have frames of their you know past behavior you don't have time to run through all of them compared to say decision tree that's blindingly fast this is a problem or you know you're trying to play the stock market then you know you need a response in a fraction of a second or your competitors will be you instance-based learning could be a problem for that okay another obvious disadvantage which is actually not such a big one these days is that of course this takes a lot of storage a set of rules you can probably store quite efficiently with this you have to store all you know the data that you've seen in fact in the early when nearest neighbor first invented circa 1956 storage was a huge problem in fact this you know for a long time nearest neighbor was not considered practical because who could probably you know who could possibly have the storage to store even a thousand examples right this was back when memory were like ferrite cores right these little you know magnets basically and then over time sometimes memory is the bottleneck sometimes memory is not the bottleneck actually this memory is not the bottleneck right disk is cheap you can store all that stuff no problem but finally here's the least obvious and actually the most important of these problems is that nearest neighbor methods are easily fooled by irrelevant attributes let's say I have a thousand attributes of each you know person most of which are totally irrelevant there's a few there that are really relevant and if I measure you know my similarity using only those I've been to shape but the signal from those is swamped by the noise from all the irrelevant ones and now I have a serious problem okay notice that decision trees and rulesets for example are very good at dealing with this problem right they they just that this is what they do they find the relevant features and throughout the others here we're not doing that okay now of course all these problems are well known and have been you know well appreciated for a long time so there are solutions to all of them okay nevertheless if and after we incorporate those solutions these methods are still not the best ones in these dimensions compared to say some of the ads that we've seen okay so it's good to bear these things in mind any questions so far all right so well there's there's one very big thing here that I didn't talk about you right so sure we store examples and then at critical time we find the closest one mode what exactly this closest needs right how do I measure that to examples are similar clearly the behavior of this algorithm is going to depend a lot on your definition of similarity right well now your definition of similarity could be anything from extremely simple to very very complicated in fact there's this whole area called case-based reasoning where your similarity measure is a huge program with subroutine calls and who knows what fortunately for a lot of applications just about the simplest measures you can imagine actually work quite well in particular let's say that you know all your features are numeric right they're all you know numbers right what might you use as a distance measure what is the first thing that comes to your mind some of the distances to each other yeah so you know that is what's called Manhattan distance right just some of the the sum of the distances along each of the features okay or you can just use equidine distance right the straight line distance between the two points in hyperspace right both simple both widely used more generally you can use what's called an ln norm ln norm means that you take for each dimension you take the absolute to compute the difference between two examples you go to each dimension you compute the difference between the examples along that dimension take its absolute value raise to the nth power and then you sum along all the dimensions and you take the nth root okay so equally the distance is the special case of this one n is what two right and Manhattan distance is the special case when n is one exactly right because you're not raising to anything you're just taking the sum of the absolute values okay but you know i could use other n's the most popular ones are indeed one and two you know what the third most popular one is anybody care to guess no yes this is a trick question the most popular one is infinity what is the l infinity norm sounds like a weird thing at first right what's l infinity what happens when you raise the the the the distance along each dimension to infinity sum them all and then the things this the the you know the infinite root you just get the maximum right because as you raise things to higher powers the larger ones dominate more and more right so if you raise it to infinity the larger one basically sums up all the others so l infinity norm is just offensive of saying ignore all dimensions except the one with the biggest difference and that's the one that's going to be your distance for some applications that's actually what makes sense but the main point here is simple measures often work quite well now what so this is for numeric features what about for symbolic features what might you use as a as a as a distance measure between examples if you have symbolic features what is the simplest thing that comes to mind right how do you measure you know the difference in between two bits vectors like let's say my variables are just boolean right so what's what's the way to measure the difference between two boolean vectors the hamming distance out there but something like that did number of bits that are different yeah exactly which is which is the hamming distance right so the hamming distance is just the number of bits along which they differ right also known as overlap so hamming distance or overlap just means for each feature if they're the same right and this applies to you know features with multiple values right if both of these things are red and the distance is zero if one is red another one is another color well then the distance is one okay now for a long time this is all that people used with nearest neighbor and it does not work it's okay but it does not work as well for symbolic domains as the kinds of things that we saw before and so for a while there was this perception that well nearest neighbor algorithms are good if what you have is continuous variable for the squeeze variables they're not really competitive and then much later you know like in the late 80s or something like that early 90s people actually figured out a very clever distance measure that you can use and in fact with that distance measure nearest neighbor becomes competitive with many of these other methods for things like say for example predicting whether something is a promoter region in in dna or where splice tensions are and and you know a lot of things like that so what is this measure it's a finnishly clever thing it's called a value difference measure we call it measure not metric because it's not a metric it doesn't obey you know the triangle inequality and things like that or vdm for short and the idea of this measures the follow right you know let's suppose that my objects can come in multiple colors red green and blue right the problem that we have is that what meant what you know what could possibly make red you know more similar to green than to blue right with numbers we don't have that problem right two is more similar to three than to four and that's why things like equally in distance make sense right but when when what you have are just symbolic values yes they could be the same or they could be different but there is no there's no degrees of difference right if your object is red any color that's not red looks equally different right and this is where people were stuck it for a long time the idea in the value difference measure is the following is let's remember one important thing here is that i'm not measuring this distance for its own sake i'm measuring the distance for the sake of predicting the class right the whole point of deciding that two things are similar is that at the end of the day because they're similar they will have the same class right so what we want to do is we want to consider how similar say these colors are with respect to your class with respect to whether you want to buy the car or not okay so this is what we're going to do right it's so the value difference measures is still going to have this general form except that instead of this absolute difference i'm going to have this delta here so let's think of two values of the same variable val i and val j and delta is going to be the following thing it's going to be the sum over all my classes so i do this for each class of the difference between the probability of the class given the first value and the probability of the class given the second value why is this a good thing to use is that now you see why red and green might be more similar than red and blue right if people tend to buy a car when it's either red or green right then for purposes of predicting what you'll buy the car red and green are similar if i switch red by green the result will probably not be different on the hand if people really buy red cars and don't buy blue cars then those are very different if not instead of red you know in the example that i'm comparing with i have blue this is a this is a big red flag right this might make a difference in the class okay so all i do is i just compute these matrices of probability of the class given each value of each attribute and then i just plug this into the usual distance measure and i can do you know fancier things with this and the full-blown vdm has more stuff in it but this is the basic idea if you just implement this you will usually get much better results than having this and on a good day you'll beat some of these other methods that were actually designed for symbolic problems to start with and of course if in your problem you have a mixture of numeric and symbolic features well you just can use the corresponding component you know in each dimension for the symbolic features you use one of you know something like the vdm for the numeric features something like Manhattan distance and so forth okay of course this is just the starting point in general when you're using instance based learning this is probably one of the things that you focus on is designing your distance measure okay and again this is where you want to put your knowledge of the domain what you know the kind of knowledge that you use here is what makes things similar versus what makes them this similar and that's that's what you want to put in your distance measure okay any questions all right so let us try to let us try to answer the following very important question what does a set of you you know when I do instance based learning right I have a database of examples right and then when I you know find the nearest example you know with a distance measure and apply that implicitly I'm representing some concept right whenever we look at a new learning method the first thing we try to understand is like what is the representation what can it do what can it not do and we haven't really done that here right and in fact it's less service in this case than in say in the case of a decision tree right what does a big database of examples represent right what what concept I'm really learning right think of this in terms of instance space right there's positive examples there's negative examples and we're trying to find the frontier between the two and we saw that in the case for example decision tree you know the frontier between them was basically a bunch of you know axis parallel planes right a bunch of hyper planes pointing in one direction or another what is that frontier going to be in our case right and this is also going to help us understand why these methods despite being so simple can be so powerful so here's a simple example let's suppose that my instance space is the plane right here it is and think of it as the surface of a pond right it's flat there's nothing happening and then my query xq is a little pebble that I drop into the pond okay so proof the pebble falls into the pond and you get this ripple right it's a widening circle right and already in the pond let's say this is a zen garden or something like that right there's other pebbles sticking out right some of the pebbles are labeled positive and some of them are labeled negative right so in this you know pond scenario what what is the class prediction for the query going to be it's the class of the first other pebble that my ripple hits right like for example in this case here right well you know the ripple starts from xq and then the first thing that it reaches is this plus here and at that point we go like oh you're the nearest example i'm assuming by the way we're using euclidean distance here okay the same ideas would apply without the distances but you know euclidean is the most visual intuitive one so we're going to focus on that okay so the first one that the ripple hit is the one that predicts the class okay well but now let's turn this around right which queries is this positive example going to be the winner for right i can ask the question for each of these training instances what region of instance space is it closest to and therefore where the the region where it's going to win and be the one that makes the prediction right we call that the Voronoi cell of that point so the Voronoi cell of a point in space is the set of all points that are closest to that point into any other okay so these points are my training examples i sprinkled them around space right there they are hanging another Voronoi cell of a particular point is the set of is the region of space that's closer to that point into any other okay and you know here's a quick question you know suppose that i have a positive example here and i have a negative example there right what is the shape of the boundary between them going to be is it going to be a curve is it going to be a straight line what is it going to be assuming we're using it equally in distance straight line and it's just two points exactly it's a it's a straight line that's equidistant from the two points right because what is the frontier the frontier is the set of points that are at the same distance from the two instances right and that forms a straight line okay so the first thing that this tells us as a preview is that my frontier is actually again going to be a bunch of straight lines or hyperplanes in the general case okay but these hyperplanes unlike indecision trees are not going to be accessed parallel right so let's pursue this thought like so let's let's say that this is my training set and here i'm not saying what the classes are because it doesn't matter right and what i've drawn here is the Voronoi cell of each one of these so for example the Voronoi cell of this one in the middle is this shape here because for example it's a boundary with respect to this guy's right here right it's bound with respect to this guy's right here and so forth okay so any queer point that falls in here is going to be classified by this guy and so forth okay so now i have to find this notion of Voronoi cell and the Voronoi diagram is all the Voronoi cells of all the data points okay and now here's my question to you so what is if i have the Voronoi diagram can you tell me what the region of positive class is going to be in terms of the Voronoi diagram let's say that this guy was positive right then the points in that Voronoi and the Voronoi cell of that example are going to be classified positive right and if that is this guy's negative those points are going to be classified negative right so what is the definition of the positive region union of all the regions precisely it's the union of all the Voronoi cells of the positive examples right very simple okay so this is really what is implicitly being represented when i just store a bunch of examples and then use the equilibrium distance right what i stored is just these dots but implicitly i have learned this you know let's say for example that this was minus and you know this was minus and this was plus right then the positive region is a very complicated shape actually right it's this thing here this is actually something much fancier than the decision tree can induce and yet it was no trouble whatsoever to induce right because we we never actually bothered to go and figure out the equations of these hyper planes god forbid that would be really expensive and as it turns out completely pointless as well because i can get the same effect just by storing the points and then applying equilibrium distance okay so this is what's really going on when we do nearest neighbor and it's also why nearest neighbor can be so powerful and yet so simple okay any questions shape of the region is so complicated it seems like you could even have many isolated ones kind of surroundings it seems like overfitting yeah yeah very good point right so exactly you're thinking like a machine learning person like you should be suspicious of this well you know like i'm going to get these very jaggedy regions all sorts of noise right this could be a disaster so absolutely right so one of the questions that we're going to ask ourselves is like how do we combat overfitting as in every machine learning method combining overfitting is going to be our one of our key preoccupations and we'll talk about that in a little bit but in the meantime maybe you can think of what some ways would be of of waiting overfitting if we don't do anything indeed we run a big risk of overfitting okay so historical footnote nearest neighbor was invented in 1955 or 1956 and for the next 10 or 12 years it was an obscure technical report from an Air Force Research Lab nobody cared about it the reason the main reason nobody cared about it is that well first of all computers back then were small and slow and you couldn't really run in on a lot of real things so it seemed to be a purely theoretical interest but the other reason was that even in theory nobody could prove that nearest neighbor did anything useful right these were the days when there was no machine learning there was statistics and what people didn't statistics was you know you know that your distribution is Gaussian you estimate the mean and the variance this way you can prove that if you give it enough data eventually you get the right mean and the right variance and you've learned the right Gaussian right this is the kind of results that people wanted to have before they would believe in some you know modeling approach okay and people didn't have that for nearest neighbor and so you know they just thought well you know this is a crazy idea and then a couple of people came along and actually figured out how to prove that nearest neighbor actually converged to something meaningful when you give it more data and then your neighbor really took off and in fact the people who proved that unfairly or maybe fairly aren't so the ones who are often credited with inventing nearest neighbor they didn't they actually just proved that it works right and the proof that it works actually if you if you you know part it down to its bare bones is very simple and it's in its well worth seeing because you know it gives us some understanding about you know why what's good about these methods and in fact historically people used to do what is called parametric estimation like estimating a Gaussian is parametric estimation because you have two parameters the mean and the variance and all you have to do is estimate those parameters nearest neighbor was the first non-parametric method notice that compared to those things with the fixed form nearest neighbor is very powerful it doesn't tell you in advance what your model is going to be the model will arise from the day and it's full freedom so in some ways you really can think of nearest neighbor as the first machine learning algorithm but now we would also like to know that these algorithms you know do something meaningful and give you the right answer so here's here's you know in one slide right in one slide right this was like a six-page you know dense paper in you know the actually poly proceedings of something but we can actually summarize it very briefly so let's let's see what it is okay so first of all let us introduce a very important quantity that what I'm going to call epsilons epsilon start of x so x and this x is bold by the way is my vector of attribute values right let's just think of it as a point in Euclidean space okay of some dimension and and epsilon is usually the letter that's used to represent error and we're going to do that here epsilon start is the error of the optimal prediction is you know if you could seem to god's mind and figure out what the best answer was how often would be would it be wrong right and you might say well that's always going to be zero I can always find the right answer but I say no sometimes it could be wrong why is that it actually has to do with the very important issue that somebody brought up in the last lecture why might not always be able to make the right prediction any ideas overlapping data points yeah exactly suppose that I've seen you know a whole bunch suppose that I've seen 10 patients right all with exactly the same symptoms seven of them have you know lung cancer and three of them don't right then what should I predict lung cancer or not lung cancer seven of them have it seven of them don't so I predict yes you have lung cancer and then what is my epsilon there's no actually my epsilon is not seven because seven is the number that I get right right my epsilon is the number that I get wrong which is three right so my epsilon in that case is going to be 30 percent okay so the more the story is this is that suppose that I've seen infinite data I'm in the ideal situation this is what is sometimes you know jokingly called asymptopia right because it's the you know utopian case where you've asymptoted that infinite day and is actually what a lot of academic statisticians deal with you know they live in asymptopia of course in the real world as we saw even with a lot of data you sell them in asymptopia but nevertheless it's good to understand what happens as you get as you get more and more data so even if you have infinite data right so if you think about it once you've seen infinite data what happens is that for every set of values right for every possible combination of symptoms you've seen infinite points and now of course you can just predict the majority right that's the best thing that you can do but the minority will still get wrong okay and this is actually what your epsilon is going to be right and what I would like to have is an algorithm that will get at least that sure if you don't give a lot of data you can't do miracles it will make more errors but at least you know it would be reassuring if I knew that if I give a lot of data to this algorithm it will converse to the right answer as opposed to do something crazy and this is what people didn't know about nearest neighbor in the beginning is is it going to do something meaningful or is it going to do something crazy so let's see so let us call epsilon and n of x the error that the nearest neighbor algorithm makes on that point x okay if that point x was the query right and I saw that query again and again what fraction of the time would nearest neighbor be wrong okay so I'm really interested in the relationship between these two things right obviously I would like epsilon and n to be close to epsilon star okay and here's what these guys were able to to prove they prove that as the number of points goes to infinity so as the size of my training data goes to infinity right as I converge to asymptote here the error of nearest neighbor converges to something that's going to be at most twice the optimal right so with nearest neighbor you're never going to be worse than twice the optimal if the optimal is 20 percent this means you're not going to be worse than 40 percent which is not so exciting but if the optimal is one percent this means that you will get to two percent well that's pretty good for such a simple algorithm okay so how were they able to show right and this really was a game changer right this is like the beginning of non-parametric estimation well here's here's the here's the basic idea of the proof and we're just going to do it for two classes you know the generalization to multiple classes is straightforward let's think of when nearest neighbor makes an error right this is what i'm interested in it's the probability that nearest neighbor will make an error this is what epsilon and n is right it's a probability that nearest neighbor will make an error well let's see there are two ways in which nearest neighbor can make an error right the first one is is when the true the true class of the example is positive but the nearest neighbor is negative right and the second one is of course the inverse where the true class is negative but the closest neighbor happens to be positive okay so my my total probability of error is the sum of the probability that these two things happen it's the sum because they disjoint right so i kind of just add them so what's the probability that the first one will happen well it's the probability that the example will be positive right let's call that p plus times the probability that the nearest neighbor will be negative right but by assumption my data points are independent and identically distributed so the the probability of the two things happening is just the product of the two okay so the probability of the first type of error is just the probability of plus times the probability that the nearest neighbor is minus okay everybody agree right and you know for the other case it's the inverse right it's the probability that the the example is negative times the probability that the nearest neighbor is positive okay so far so good right well very good and now if you think about it the probability that the nearest neighbor is negative is the same thing as one minus the probability that the nearest neighbor is positive right so I can replace one by the other, and same thing over here, right? So now I have this, you know, not too complicated expression, right? So far this was really just algebra, right, and definitions of probability and what not. But now let us take that limit as n goes to infinity, right? This is the key step. What happens to the nearest neighbor as n goes to infinity? Right, here's my point, right, and here's my nearest neighbor, right? What happens to the nearest neighbor as I get more and more points? It gets closer, right? It never gets farther, right? Because if my new points are farther away, this one remains. But every now and then a new closer point will show up, right? And so what happens is I get, you know, more and more points is that those are going to get closer and closer and closer until they're the same, right? And so what this means is that when n tends to infinity, the probability of the nearest neighbor being positive converges to the probability of the point itself being positive, right? They become the same. This is the key, right? If I have infinite data, those two things basically become the same. And same thing for the probability of the point being negative and the nearest neighbor being negative, okay? So now let us replace one by the other in our expression, right? So what do we get? Well, now I get p plus times 1 minus p plus, right? I used to have probability of the nearest neighbor being p plus, but now, in the infinite data limit, this has become p plus again, okay? And over here what I had was again, you know, p plus, right? And probability of the nearest neighbor being plus and I have being negative, sorry, sorry, I replaced it by 1 minus the probability of being positive. So here's what I have now. Notice that this is just, this is actually the same expression on both sides, right?  So it's just 2p plus times 1 minus p plus, okay? So we're almost there now. There's just one more little thing that we need to do. What is the relationship between p plus and the error of the optimal classifier? What is the relationship between p plus and epsilon star? Are they the same? Are they different? Let's suppose that the majority class is negative, right? So I should predict negative, right? Then what is the relationship between p plus and epsilon star? 1 minus the majority? Well, so actually, exactly. They're 1 minus the other, right? p plus and p minus are 1 minus the other, right? So if I'm predicting, if I'm predicting plus and the true answer was minus, right, how often do I make an error? p plus, right? It's a fraction of times that I get it wrong, right? So in that case, p plus and epsilon star are the same. In the reverse case, right? Let's suppose that, you know, the answer really was plus. Now p plus is the probability of me getting things right. So the probability that I get things wrong is 1 minus p plus, okay? And now I can replace, you know, let's look at both of these cases, right? In one case, I replace p plus by epsilon star and in the other case, I replace 1 minus p plus by epsilon star, right? But since each of these has both of those terms at the end of the day, in both cases, what I get is epsilon star times 1 minus epsilon star. So in the end, this expression is just equal to 2 epsilon star times 1 minus epsilon star and since this is always less than 1, this is always less than 2 epsilon star and that's our proof, okay? This is actually pretty straightforward. Again, I glossed over the technical details of this, but the basic idea is right here, okay? And in fact, you know, nearest neighbor as n tends to infinity is actually what is called the Gibbs classifier for this problem. We will see, when we talk about statistical learning, we will see what that means, Gibbs classifier. So there's this notion of optimal classifier, but often the classifier, the optimal classifier, you know, is unreachable, but sometimes you can reach something called the Gibbs classifier, which is kind of like the second best thing and nearest neighbor is that second best thing, okay? Questions? Okay, now, of course, this is very nice, but it's not ideal, right? Why can't we get to epsilon, right? What we want to do is get to epsilon. We don't want to be satisfied with 2 epsilon, right? Can we get to epsilon or epsilon star to be precise? Well, it turns out that yes, we can. If we, instead of using, you know, just the nearest neighbor, we use the k nearest neighbor. So the analog of this theorem for k nearest neighbor is that if I do things right, I will get an error of epsilon star from k nearest neighbor. So k nearest neighbor can be my optimal classifier in the infinite data limit. But what does it mean to do things right? We can't just do this any other way. So here's what doing things right means. I have to let my data go to infinity, right? That's natural. I need an infinite number of data points to make sure that the nearest neighbor is all converged to my point, right? My query point. Also, k also has to go to infinity, right? So I have to do an infinite nearest neighbor algorithm, okay? Because I need infinite data points to estimate my probability of the example being plus with no error. Right? As long as I estimate it with some error, if p plus minus are very close, I could still be getting it wrong, right? So k itself has to go to infinity, okay? But k can just go to infinity in any old way, because if, for example, if I let all my points be nearest neighbors, then I'm going to get, you know, basically the default prediction, okay? So what has to happen is that even as n goes to infinity and k also goes to infinity, k over n has to go to zero. So what this means is that I'm getting more and more data points and I'm considering more and more neighbors. But the neighbors that I'm considering are a dwindling fraction of the total example, which means that I do get, you know, small and smaller ball around my point, but that ball is very, very densely estimated. And then, of course, what happens at that point to just give a very hand-waving version of the proof is that, well, I have all those points right there, right? So from them, I can estimate the true probability of plus and minus, and then I make that prediction and I get the optimal error. So for something so simple, k nearest neighbor is shockingly powerful. Any questions? Okay, very good. So let's talk about this issue or, you know, at least something that this is related to. The second biggest problem in machine learning after overfitting is what is called the curse of dimensionality. And again, the curse of dimensionality is present with every method and, you know, affects the more powerful ones more as usual. But it's a particularly severe problem in instance-based methods, which is why we're going to talk about it here. But again, just as we introduced overfitting with decision trees, but not it's going to apply everywhere, the curse of dimensionality is also going to apply everywhere. So this is a general issue, not just within instance-based method. You remember when I said that if somebody asked you, what is the problem with this machine learning algorithm and you didn't have an answer, you know, a good thing to just say is, you know, overfitting? If overfitting fails, your second best choice is curse of dimensionality. And between overfitting and curse of dimensionality, you probably get a lot of things right. So good thing to remember. So what is the curse of dimensionality? And by the way, the curse of dimensionality affects other things besides machine learning. It was initially, you know, the trend was coined by a famous controlled theorist called Richard Bellman because he had these methods for optimal control that worked fine as long as you were in all dimensions. And when the dimensions got high everything fell apart and he called it the curse of dimensionality. So what is the curse of dimensionality? Let's, you know, here's the first instance of the curse of dimensionality. It's something that we've already alluded to. Let's suppose that your instances are described by 20 attributes, okay? But only two of those are relevant to predicting the class. You know, like remember our parity example, right? Your class is the parity of two of the bits but then there's 18 irrelevant ones. For nearest neighbor this is a really serious problem. Nearest neighbor isn't going to pick out the single from those two attributes out of the noise from all those other 18. Sure, those two are pointing in the right direction but superimposed on that is a noise signal that's in order of magnitude larger than a warehouse. This, as I mentioned, is the single biggest problem with instance based methods and is the single biggest reason or at least one of the biggest reasons that people use other things like decision trees and whatnot. Okay? At least from the point of view of accuracy. Okay? And this is an example of the curse of dimensionality because if the dimensionality was low you wouldn't have this problem. Right? If you just add two relevant, two relevant ones, well given enough data you're probably able to pick out the right ones. But if you have a lot of irrelevant ones then you are a host. Okay? However, it gets worse, much, much worse. Here's the shocking thing. Let us suppose that instead of two relevant attributes and 18 irrelevant ones, I had 20 relevant attributes. Does this mean that I am in better shape than with two relevant attributes? What does your intuition say? Would I rather have more information about my customer or less? More, right? Don't be afraid to state the obvious, right? Of course this is a great question. There's a catch for it. We can do this on these two levels. So on the one hand surely knowing more about your customer is better. But here's the thing. As I go into higher and higher dimensions my space gets bigger and bigger and my examples get farther and farther apart. And if you think about it, what I need for instance space learning to make good prediction as we just saw in the theory part is I want my nearest neighbor to be close to my point. As long as the class probability is not very too suddenly, if my nearest neighbor is close to the query point there's a good chance it's going to be right. And the problem with being in very high dimensions is that in high dimensions everything is very far from everything else. And so as you add more dimensions, yes, on the one hand you have more information which is good. But on the other hand it becomes the whole notion of who's closest to you becomes very fuzzy. And so the thing that's perverse is that the curse of dimensionality hits you even if all the attributes are relevant. Now if the attributes are highly relevant, if each one of these attributes is a very strong predictor of the class then this won't happen. But then you don't need a lot of them anyway. Then many of them are redundant or irrelevant. But then what you want to use is probably something like a decision tree that you'll build a tree over those attributes and ignore the others. But if all you have is a situation where you have a lot of signals but they're all weakly predictive of the class then they're all relevant but now you're really in a situation where you might do well except for the fact that the curse of dimensionality might kill you. The signal is there, right, but it's very diffuse. This is when things become difficult. So in high dimensions nearest neighbor is very easily led astray. Its ability to discriminate basically dies down as we have to high dimensions. We're going to see some examples that hopefully we'll make clear why this happens. More generally, not just with nearest neighbor with lots of different techniques that we use in machine learning with optimization techniques, in machine learning the final step is always to optimize. Optimizes often work well in low dimensions, in high dimensions, things are much, much harder. And finally, here's the biggest issue of all. The biggest issue is in our brain. Is that we build all these machine learning algorithms and all these techniques based on our intuitive understanding of a three-dimensional world. The real world is 3D. Your brain works in 3D your visual system with all of its power works in 3D. As long as we're in 3D we're happy. We have a really powerful machine inside our heads for dealing with three-dimensional space. But the problem is that in most machine learning situations you're dealing with a hundred, a thousand, a ten thousand dimensional space. And the thing is that in thousand dimensional spaces things are very, very different from what they are in 3D. And the intuitions that you have from 3D and 2D do not carry over. In fact, very weird things happen in high dimensional spaces. And so all the intuitive things that we might do with nearest neighbor we always have to be on our guard. Because your intuition could be leading you astray. This is the biggest problem. This is what makes it hard to design these algorithms. And as I mentioned before there's a famous data mining researcher who says that if people could see in high dimensions we wouldn't need machine learning. But we can't see in high dimensions and that's why we need it. So let me just give you a few examples that hopefully you'll find entertaining as well as instructive of why low dimensional intuitions do not apply in high dimensions. So the first example is the example of our good old friend the normal distribution. The normal distribution is more basic than the normal distribution. So let's look first of all at a normal distribution in one dimension. A normal distribution in one dimension looks something like this. Here's my x and here's my p of x. And it's our famous bell curve. And here's my mean. And if I draw a band of one standard deviation around the mean something like this most of the probability mass is there. Minus sigma plus sigma. One or two standard deviations. The whole idea of a normal distribution is that most of the probability mass is concentrated around the mean. And then there's some fuzz around that mean. But roughly speaking I know that I'm going to be landing near that point. This is the very meaning of a normal distribution. Very good. Now let's see what happens in 2D. Let's look at this from the top. So what I'm going to do is I'm going to put x here and y here. And now I'm going to represent the distribution using curves of iso probabilities. So all the points around here have the same probability. The maximum of course is still here. Let's say I'm centering this at the max. Let's say zero for example. These are bands of equal probability. In 2D this is going to look like a belt. Like a real 3D belt. And now let's look again at my band of one standard deviation around the mean. There is still where most of the probability mass is. But notice the following thing that has happened. A smaller fraction of the total probability mass is now within a radius sigma of the mean. Here it really was a big chunk of the whole distribution. Here it's a smaller chunk of the whole distribution. Just looking at that hopefully you can see. This now accounts for less than my probability mass than what I had before. Even accounting for the fact that it's rising higher there. Because there's all this space around here that the lower probability can happen in. When you add up the low probability over the entire big section of the plane well that adds up to a lot. And now of course you can see where this is going. Let's do this in 3D. Now what I have is these spheres. There's a sphere that's here within one standard deviation of the mean. And now this sphere is starting to be a pretty small fraction of the whole. So even though the probability is higher there, more and more the probability is outside of that region. And guess what happens if you go to sufficiently high dimensions. And that doesn't even have to be very high. For reasonable, you know, variances. You know what's going to happen? Is that most of the mass of the probability distribution is far away from the mean. This is a really disturbing thing. You have a normal distribution and most of the probability mass is far from the mean. This is exactly the opposite of how we think of a normal distribution. And yet it's what really happens. This is the cursor dimensionality. Your picturing the normal distribution is meaning one thing because of your intuition in, you know, both dimensions. But in high dimensions something very, very different is going on. Okay? Any questions or thoughts on this? Okay. But it doesn't end here. After all, this could just be, well, you know, it's a not thing that happens with a normal distribution. Unfortunately, it's a not thing that happens with just about everything in high dimensions, right? In high dimensions it's like this Alice in Wonderland quality to everything that goes on. It's like the Twilight Zone. You know, weird paranormal things start to happen. So here's another example. Oops. The normal, the uniform distribution on a hypercube, right? Very natural thing, right? I have a hypercube. You know, let's just think of a cube, right? I have a cube here and my points are normally distributed inside it, right? So most points are going to be in the middle of the hypercube. There's going to be very, very few points that are on the walls of the hypercube, right? Let's say that we define a band of, you know, with epsilon where epsilon is very small.