All right. Welcome everybody to the wonderful world of machine learning and data mining. The most fascinating subject you will ever see. My name is Pedro Dominguez and I will be your instructor. Please feel free to ask questions and share your thoughts at any time. One of the funnest things that happens in this class is when people share the experiences that they have with, you know, doing data mining in their jobs and whatnot and ask questions and so on, so I hope some of that happens here. Let's get some logistics out of the way first. So, my email is PedroDXCS. Please feel free to email me at any point with any questions that you have. Also, I have office hours every week. I have set them from 5.30 to 6.20 right before class, which is the most convenient for you. And my office is CAC648, so please stop by anytime. If, you know, you happen to be on campus at some other time and you want to see me, you know, we can do that by appointment as well provided, you know, I'm in. Your TA is Rob Guns back there. He's in charge of making your life hell. So, everything that happens in this class is his fault. Everything that is mine may. His email is RCG. Again, feel free to send him an email. He has office hours again at the same time. Not ideal to have them at the same time, but it's, again, probably the most convenient for you. And the office hours are in at 2.16. Okay? You don't have to write any of this information down because it's all on the class web at www.cs.washingtonedu.p546. This is the short form URL. There's also a long form. And you can also just find it by following pointers from the department site and whatnot. There's also a mailing list that we highly encourage you to subscribe to. You can do this by following the link from the class webpage. We're at CSCP 546 at CS. And, you know, we will be posting important information about the project, certifications, and whatnot there. Okay? The decision whether to send an email to the list or to us is one of whether you think the question is only of interest to you or of interest to everybody. If you think it's of interest to everybody, please send it to the list. We reserve the right to embarrass you by replying to a question that you sent us privately publicly. Okay? So beware of that. There's also a discussion forum that you can join to, you know, again discuss the class. And that can actually with, you know, with your colleagues and us, that can be a very, very productive thing to do. So we highly recommend that. Okay. Evaluation, our favorite subject. How are we going to give you a lot of useless long hours of work where you learn nothing is the problem we're trying to solve. And here's how we solve it this time. We don't have a meter more final. There's four assignments. Each one is worth 25% of the grade. We'll hand them out on weeks two, four, six, and eight. And they each do two weeks later. Okay? And they roughly cover the corresponding two weeks of the course. You know, more or less not exactly. Okay? The assignments are a mix of three things. One is implementing machine learning algorithms. Right? This one of the main things that you're going to do here is learn various machine learning algorithms. And there's no better way to learn them than to actually implement them and work with them yourself. The second part, of course, without which, you know, a course like this would not be complete, is applying those algorithms to real data sets and seeing what you find. Of course, you have limited time to do this, right? Some people do this, you know, as a full-time job. And even then, it's not enough. But nevertheless, we hope to give you a flavor of what it's like to really do data mining machine learning in practice. Some of the data sets that we might be using we haven't decided yet are things like clickstream mining. Can you predict what people are going to do on your e-commerce website, for example? Recommender systems, right?  Spam filtering, right? You can build a spam classifier that, you know, tests whether something is spam or not. And then maybe you can use it as your own spam filter for your own email and do better than the generic spam filters from the search engines. And so on. Some of it will be exercises, you know, math-style exercises because, for some things, that's the best. Some of the questions, maybe related to the programming part, maybe not that test your understanding and also help you to, you know, dig deeper and whatnot. Some of the projects will have more open-ended questions that those of you with, you know, a ton of pre-time on your hands, I know that's everybody, that can use to go to town and, you know, and go further. And, you know, just as an example, in this class a few years ago, one of the data sets that we used was the famous Netflix collaborative filtering data set, right? The one with a million-dollar prize. And, you know, we had a great time implementing algorithms for it. One of the students who had never done machine learning before went on to be a member of one of the two top teams, right? And they only lost because they turned in their solution, like, you know, an hour later than the winning team. So the next one could be you, okay?  Okay. So any questions on the assignments evaluation and so on? You have no questions now, but I guarantee that you'll have plenty of questions later. Source materials. So what are we going to be using in this class? Some of you probably already have this. If you don't, I encourage you to get these as soon as possible. If you're only going to have, there are many good textbooks in this series, some of them more advanced, some of them more applied, et cetera, et cetera. The one that I recommend as the first book to study is the book Machine Learning by Tom Mitchell. It's a fairly short book as they go. It's fairly simple and accessible. It's a very nice, efficient way to get the basics of machine learning. It's clear. It's not too math heavy. It has a broad view of machine learning. So in many ways it's an ideal textbook. The only problem with it, and it's a big one, is that it's outdated, right? So it's about 10 years old or more. So there's many things that it doesn't cover. And also some of the things that it covers, it doesn't quite cover to the depth that we're going to need here. So to complement that, we have pattern classification, which is actually a new addition of the earliest classic text in this area. So I highly recommend that you get both of these books if you haven't already. And then I highly recommend that you do the following. Scheme the relevant chapters before you come to class. So on the website, we've actually posted a rough plan for the whole course. It may change, but roughly that's where it's going to be. And there's also draft slides up there, and whatnot. Again, those may change. But you make the most of the class if you already have an idea coming in of what we're going to be talking about. And literally, you can do that by just getting through the slides in the book in 15 minutes. If you don't do that, then you spend a lot of your cognizant foreign class just getting your bearings. If you do that, you'll actually make much better use of your time here. And then after you've gone to class, then you can go back to the textbooks and study things more deeply and try to do the assignments and whatnot. And then ask us questions if you have them and so forth. We will also be complementing as needed the textbooks with various papers and whatnot. For example, there's a very good paper on the quickstream mining project that we're going to do and so forth. So we'll do this on a week by week basis. Questions about any of this? Because, of course, I want to get to the exciting part. So number one, why should you bother with this? What is the point of studying machinery and data mining? Now, I could tell you that it's fascinating and it happens to be what I do for a living, but I'm biased, right? So why should you believe me? So what I say is like, don't believe me. Believe these people. Here are a few quotes, and there's many more like this that should at least tell you that there's something that you should learn. And you're probably already aware that machine learning is a very hot area in computer science these days, but you may not be aware of just how hot it is and why it's important. So let's spend a little bit of this first class on that. So here's something from a guy you might know. His name is Bill Gates. And he says a breakthrough in machine learning would be worth 10 Microsoft. That would be the world's first multi-trillion-dollar company. I think he's guilty of understatement. We'll see why shortly. But hey, if it's worth 10 Microsofts, there might be something in it. So DARPA is this famous agency that funded the internet development and a lot of other great things in computer science in other areas. Tony Tether, who was until a few years ago the director of DARPA says machine learning is the next internet. If it's the next internet, maybe it's worth knowing about. John Hennessey, who's actually a well-known computer scientist, but these days is the present of Stanford, says machine learning is the hot new thing in computer science. Prabhakar Raghavan, who was until recently the director of research at Yahoo. Since I made this slide, it's already outdated, because he's been hired by, I think, Microsoft or Google, one of those. Web rankings today are mostly a matter of machine learning. You might not know this, but every time you do a search and get results, you're using a machine learning algorithm. Greg Papadopoulos, another famous guy in information technology. He used to be the city of sun, now he's a venture capitalist and other things. He says machine learning is going to result in a real revolution. These are people who are not necessarily very likely to engage in hyperbole. Jerry Yang, founder of Yahoo, machine learning is today's discontinuity. Technology and civilization advance not as a linear progression, but by making sudden huge leaps. He says machine learning is the one that's happening today. Steve Baldmer, another guy you might have heard of, says machine learning today is one of the hottest aspects of computer science. Clearly, there's a lot of bollywood about machine learning. What is the bollywood about? What is this thing called machine learning? Why is it so important? It's traditional to start a class by defining the subject and I'm going to fall for the same thing. At the end of the day, you will know much better than you can say in one sentence what machine learning is. But for now, let's just try to do that. And I'm going to do this definition in two words. It's not one sentence, it's two words. Machine learning is automating automation. What we as computer scientists do is automate everybody's job and make them unemployed. Yay. Oops, no. That's not what I meant. What we do as computer scientists is we make things possible that weren't possible before, because it would take a million people to do them and we don't have those millions of people. With computers, we can actually do the work of a million people with one CPU. And so all sorts of things that were completely impossible before become possible. Like computer games and imagine if somebody was actually painting each of those pixels by hand. So the power is in automating things. The more we automate things, the cheaper they become, the more people that can have them and so on and so forth. But here's the question. Who automates the automation? As we automate more and more things, perversely, the bottleneck becomes us, the computer scientists, the software engineering, the information integration. That's what's slowing us down. So this is what we want to do. We want to make the computer science, the programming, the software engineering process itself be automated. Right? So here's the picture. Computer scientists put everybody else out of jobs. Machine learning people put the other computer scientists out of jobs. That might be a good reason to learn machine learning. Right? And then you'll still have a job where no one else is left standing. OK? And it's also very ethical to steal from the thieves. Right? Then two minuses cancel. And we're very nice people. OK. So joking aside, how are we going to do this? Right? This sounds very good. But how do we automate automation? Right? We have to get computers to program themselves. This is the idea in machine learning. We're not going to program the computers. We're going to get the computers to program themselves.  If you're smart and you're hardworking, you can do systems, you can do software, programming languages, networking security, you know, graphics, all of that stuff is for the smart people.  We want to push a button and have the all of them do the stuff for us and then we go to the beach. And we're still making a lot of money and whatnot, right? So that's the agenda. Getting computers to program themselves. So how are we going to do that? Right? Think of all the smarts that you put into writing software. Right? Can we actually get a computer to do that for you? That's the agenda. Right? We want to replace this ball neck of writing software where all the, you know, persons, you know, months are now going into the thing that's keeping us from going further and have the computers do that themselves. And then maybe things can take another leap to happening even faster and on a larger scale and so forth. So how are we going to do that? Right? This sounds like, well, sure, beautiful dream, but, you know, how's that going to happen? We have one secret weapon to make that happen. And it's because we have that weapon that all of this is possible and wasn't before. And that weapon is data. We're going to let the data do the work for us. And as you heard, this is the era of big data. Right? There was that McKinsey report, you know, like some months ago saying, we are now in the era of big data. We need 150,000 people who have expertise in analysis of big data. And, you know, what we have right now is like 1% of that. We're going to take that data, right? And it's by sucking all the juice out of that data that we're going to have the computer automatically write programs that otherwise will take a lot of work on our part or even better. We might not even know how to write those programs, but by running machine learning programs on data, we'll actually have them. We'll see some examples of that. Okay? So that's the idea. We're going to take the data and turn it into programs. Now, even with that, you're probably still thinking, well, you know, this sounds too good to be true. Right? So first of all, we can do this in some cases, but not others. And as the research progresses, we'll be able to do it in more cases. But even with a small, you know, simple that some level programs that we can, you know, create today in this way, it's amazing what you can already do with them. And we'll see some examples of that shortly. But nevertheless, you might still be justified in having some skepticism. Okay? So let's see a little bit of how this is done, right, before we dive into the details. Here first is the picture of traditional programming, right? This is what we all know and love, right? This is what we do for a living. There's a computer, and the program go in and out comes the output that you want, right? And our job is to write the programs inside, is to write these programs that then go inside here and combine with the data to produce the results. Okay? So this is what we all do. Machine learning is turning that around. What machine learning does is it just switches two little things in this diagram. The output is not the input. And what was the program, what was an input, now becomes the output. The output is not the input and the program is not the output. You see what this is doing? What this is doing is the machine learning program, right, this is what the machine learning is going to do, is that it takes in the data, the raw data that the program is going to have to operate on. And then the desired output, right, we just give the computer examples of what we want it to do. And then hopefully, on a good day, if the machine learning works, and you can get it to work, then from the examples of the input and the output that you want, you can induce the program that should be running on the computer. Okay? And then once you have that program, guess what, then you put it in there and now the same old thing happens. Okay? But the beautiful thing is that you didn't have to write the program yourself. Okay? Or the long hard exercise of writing the program became a much easier exercise of just controlling the machine learning to make sure that it does what you want. Okay? Here's a metaphor for what happens. Not everyone likes this metaphor because it's very low tech, but actually think it's a very instructive metaphor. And the metaphor is this, is that machine learning is a lot like gardening or agriculture, right? What could be, you know, lower tech than agriculture? Why is that if you think about it in all the artifacts that we have, you know, cars, you know, TVs, computers themselves, right? We have to put them together piece by piece. We have to create the nuts and bolts from the raw materials. We have to assemble the nuts and bolts into sub-systems and those things into the systems, right? This is a ton of work. It's a ton of work and it doesn't scare because the more complex the system becomes, the harder it becomes to actually put it all together without making mistakes and whatnot. Okay? Compare this with what happens in gardening, right? Gardeners have a very easy life. Nature does most of the work for them, right? The gardener just provides the seeds and the nutrients and a little bit of care. And then from that, you get, you know, flowers, plants, trees, right? Or agriculture gets, you know, you're weak in your corn and your rice and so forth, right? So this is a very smart thing to do if you can, right?  So this is what we actually do in machine learning, right? In machine learning, the seeds, right? If you think about it, you know, in your beautiful plant or flower, all the information is already in the seed, right?  So our seeds are going to be the algorithms. Of course, the seed by itself is not a plant. You need to feed it. It needs water. It needs nutrients. This is where the data comes in. Here is our nutrients. You're going to feed that seed with a lot of data, with a lot of nutrients, and then the programs will grow. Your job is to manage the whole process, make sure that the plant doesn't die, or if it dies, you plant another one and so on and so forth. But it's much easier to do that than it is to, you know, assemble a whole plant by yourself, molecule by molecule, right? That would be a very hard thing to do, but yet this is actually what's happening while the gardener is asleep, okay? So keep in mind this metaphor, you know, as we go forward, I think this kind of illustrates well why machine learning is potentially so powerful and such a great thing for lazy people like us. Okay, so that is, you know, just a short overview of what machine learning is. Let us more concretely illustrate this with, you know, the number of, you know, applications of machine learning, right? Just so you can see more specifically what are some of the things that we... All these things you might be familiar with, some of them might not be in any case, you know, they're just a sample of the many things. I mean, there's more things being done with machine learning today than anybody can keep track of. So I started with some of the ones that are more, say, let's say, current and commercially important, and then, you know, gradually moved on to the ones that are more speculative, but even the more speculative ones are not that speculative these days. So, of course, you know, a very good place to start, which I already mentioned, is Web Search. The single most, you know, these things are closely guarded secrets, right? But what seems to be the case from what people like Prabhakar say is that the single most important ingredient in designing a search engine is the following. When the engine gives you a set of pages, right, and there's summaries, you click on some, but not others, right? You click on the one that looks most interesting to you. And if that's the one you want that satisfies your needs, then you're done. Otherwise, you might go back and click on others or even refine the query, right? Now, if you think of this as an input from machine learning algorithm, this is a beautiful thing to have, right? Because what this input-output-parry setting is, if I put up these web pages for you, then you'll click on these ones. So what the machine learning algorithm can learn to do is predict which pages you will click on, and then it actually just puts those up. It puts up the ones that you are most click on instead of letting you see all the track. And the other thing is that search engines have a lot of data, right? They get billions of queries every day. You'll get a lot of data to do this. So at the end of the day, by using machine learning, you end up with a much better search engine than you have in the days when machine learning wasn't used for search. Here's another very different example. Computational biology. Very big area for machine learning. There are many different applications of machine learning in computational biology, but think of just this one. Drug design. In the old days, companies designed drugs by trying things out in the lab. It's a low painful process. And it was very trial and error, very random. And for a while this worked. But these days they have largely run out of what they can do with that. So now we know what they do is what's called rational drug design. One of the big components in rational drug design is like you try to design the drugs and be fairly sure that they're going to work and actually try them in the lab. For the cost and time of trying one drug in the lab, you can try millions of them on the computer. And this is where the machine learning comes in. I know something about molecular biology. I have examples of molecules and what they do. Like, for example, how they dock to viruses and inhibit them and whatnot. And now what I can do is I can try to predict for other molecules by generalizing from, again, the ones that I saw how these ones are going to behave. The input is the molecule and the output is what I want or how will it dock and whatnot. So this is one very important application in computational biology, but there's many others. Here's another great one, finance. Finance was actually one of the early major applications of machine learning even before the web was around. Everything on the web uses machine learning these days. Think of a bank. One of the things that no banks do is they send you credit card offers. They use machine learning to decide what to send what offers to. They have that on you and from that they try to figure out using a machine learning program how to predict whether you are a good credit risk or not.  If you just go to the bank as a company or an individual and make a loan application, chances are your application will be evaluated by a machine learning program. They do not use that much at least for loans of a certain scope. Human evaluators anymore. They use machine learning programs. So they're predestined applications on whether the outcome was default or whether they paid on time and what not. So you can use machine learning for that. And then they have all this money from you. They need to decide how to invest it. Machine learning comes in again. You can use machine learning to try to predict stock market, currency fluctuations, where the companies are going to make money, et cetera, et cetera. So machine learning gets used very extensively for this type of thing. Next thing they're worried about whether they're going to lose you or not. So they can use machine learning and they do to predict whether you are likely to leave or not to drop them for another bank or another credit card and make an offer to you at that point. They can even use it to decide whether they think you're not really worth keeping and suddenly try to discourage you. I'm not going to say whether they do this or not, but they might. Finally, they're also worried about fraud. There's a lot of fraud with credit cards in fact, but in fighting fraud. Actually, not just in finance, but in everything. Because again, what you do is you figure out what are the signs that credit card has been stolen and then they suspend the credit card. You've probably had this experience getting a call from a bank saying or an email, your transactions are suspicious. Can you confirm that these are yours? And there's more, but this is just a sample of the things that machine learning gets used for in finance. Okay, so to take a total different application, space exploration. Here's two examples of space exploration. You send a probe out there to Mars and the probe is on its own. Light takes whatever, 10 minutes to travel between Mars and Earth. If the robot has to be instructed by people, it slows it down by orders of magnitude. So the more autonomous the robot is, the more productive it will be. It needs learning algorithms to figure out what to do on its own. Another example, astronomy and planetary science are one of the big producers of masses and masses of data. Like you send a probe to Venus and it takes pictures of the entire surface. This is a real example. And now the planetary scientists want to figure out where the volcanoes are on Venus because that allows them to test the use of planet formation. Well in your days you would have to pay someone to look at these plates and say volcano, not volcano, volcano, not volcano. And of course they're only skilled so far. These days you get a machine learning program to figure out what is a volcano and what is not. It learns from a much smaller number of examples that were labeled by people but then it goes off on its own. And in the same way you can form catalogs of stars and galaxies and other objects in space and what not. Robotics is another example and at this point it should be obvious, right? Robots, the more autonomous and flexible they are, the better. There's actually lots of robots in industry today but they are very inflexible. There is one movement or a sequence in a more controlled environment. They're not flexible, they can't react to failures. You want to make them more flexible without having to program this all yourself. In many cases you don't even know how to, right? You want to program to grasp this or that into more of a different object. You can use machine learning for that. That's what people do. As a very famous example of this, right? The famous self-driving car, right? These days we're at the point of having cars that will actually be your taxi and not actually have a driver. You know, for the people who built these cars they will tell you there's machine learning in every new concurring of what they're doing, right? Information extraction. How do we make computers smarter, right? It's one thing to use a search engine and type in a few keywords and get back a bunch of documents but that's not really what you'd like to have, right? What you'd like to have is the ability to ask questions and this thing answers your questions by reasoning over databases that are collected from the web, right? This is a very big agenda for a lot of companies that have been definitely good for us as users. Again, the way to make that work is to use a lot of machine learning to be able to do the information extraction automatically. Here's one that used to be somewhat futuristic but no longer. Social networks, right?   You've probably heard that Facebook valued at something like $100 billion, right? Why are they worth $100 billion? Right? If you read the stories on this, the number one reason they're worth $100 billion is that they have this motherload of data about how people relate to each other, live their lives, do things with their friends, what they prefer, what they don't, right? Their ability to mine that data and then use it to select, you know, for example, which banner adds to show and, you know, and other things are valuable, okay? So first of all, you have a company that gathers a huge amount of social information like the social graph and lots of other things. But then, right, the question is what value can you extract out of that data? The better your machine learning, the more value you can extract out of it. And, you know, if Facebook is already worth $100 billion with the machine learning that they have today, imagine what it would be worth if machine learning that was much better, okay? So it's coming. Okay, so let me give as a last example one that's completely different from all of these. Machine learning is now becoming very popular basically for every problem in computer science and beyond, but in particular for things like systems and software problems. You can use machine learning to try and optimize the behavior of your data center, to make it faster to respond, to make it consume less power. You can use machine learning for things like debugging, right? We all know that debugging is one of the most annoying and most labor-intensive processes in software development. Wouldn't it be great if we could partly automate it? Notice it doesn't have to be the case that the problem will fine and fix the bug all by itself. But if the only thing that this program does is it tells you what are the 10 most likely places where the bug is, this will already be very useful, right? It will save you from looking for needle in the haystack potentially. And again, you can use machine learning programs for this. You can use traces of the program running. You can use traces of how people debug their programs in the past. And again, try to predict from the program from what happened then, you know, was there a crash? Was there not a crash? You know, what did the user do? What did the programmer do? Like, what did the compiler produce? From that, try to learn where the bugs are and where they are.  What problem are you interested in? And how would you apply machine learning there? Maybe this is a problem where machine learning has already been applied, but chances are you can come up with a different angle on it. Maybe this is a problem where machine learning has never been applied and there's a huge opportunity for you there, okay? And if you do decide to do that and, you know, have questions and thoughts, you know, please talk to us. We'll be very excited to find out what you're up to. Okay? All right.  The rest of the class is not going to be like this, right? It's going to be more, you know, concrete and more problem solving, but, you know, enjoy this part while it lasts. And also, I think it's useful to have sort of like this overview of what machine learning is and what it's good for before we dive into the details. Any questions? Not so far. Okay, let's keep going. So, hopefully, you know, in these few minutes I've at least persuaded that machine learning is intriguing and potentially worth studying. So, now let's start studying it. What is machine learning? How do you do this amazing thing of getting a computer to program itself? And if you're interested in machine learning, if you just decided, for example, you might want to use machine learning in your, you know, problem of interest, in a way, it's kind of hard to get your bearings because, well, you know, many of the test books are pretty impenetrable for someone who doesn't already have a lot of mathematical background and whatnot. And then if you look at the literature, right, what you see is like there's tens of thousands of different machine learning algorithms.  So, the number of machine learning algorithms seems to be growing exponentially and now how do you get your bearings, right? Do you have to learn each one of these new things or, you know, face doing the wrong thing or being out of date? Actually, you don't. Right? And this is one of the first things that, you know, I think you can take this class to the following. Machine learning algorithms are essentially just combinations of certain components. And if you understand what those components are, then this combinatorial space of machine learning algorithms becomes a much more space of the components and then you can combine them in different ways.  And then as you hear things about machine learning and you see new things coming out, now you have a way to keep things organized and to not get, you know, overwhelmed. So what are those components? They're basically three. Almost all machine learning algorithms have these components in one form or another. They are representation, evaluation, and optimization. Okay? So let's look at each one of these and see what it is and what examples of it are. So representation. If your computer, right, if your machine learning program is going to create its own program, the first decision that needs to be made is what language this program is going to be in. Like you as a programmer might decide, well, I want to use Java or I want to use Perl or I want to use whatever. It's a similar decision to be made by the machine learning algorithm or by you for the machine learning algorithm. Of course, the languages in this case are not going to be things like Java, etc., which are designed for humans. They're going to be languages that hopefully are good for the machine learning program to use. So what are some of those languages? Well, here's one. Decision trees. Decision trees are the first one we'll study and they are according to surveys that by a good margin, the most widely used representation. Okay? And by the way, roughly speaking, the way we're going to organize this class is by representation. So we look at each of these representations in turn and then see how we do the evaluation and the optimization with them. Also as a rule of thumb, new representations come up much less often than new evaluation functions come up, which in turn come up less often than new forms of optimization come up. So in a way, the representation is the most stable core of machine learning. This is not to say that there aren't new representations to be invented. I'm sure there are and I look forward to them. So here's another one that's also a very natural one. It's sets of rules. You can think of a decision tree as being a set of nested if-then statements. That's at some level what a decision tree is. So it's just a basic programming construct with launch. Sets of rules are also if-then statements except they're not nested. They're just, you know, it's a sequence, right? The first one that fires wins, or then you do some combination of the ones that fire. Sets of rules can be very powerful because in particular if the rules are in first order logic, and then they're also called logic programs, you can genuinely write any program in this way, right? So it's very powerful. It's a very powerful representation. You don't necessarily want to write a program in this way, but in principle, you know, there's languages like Prologue, for example, that, you know, can do anything other than Sun, and we will see how to learn such programs from there. Another one, and in fact one of the oldest ones is instances. This is the best of the laziness approach to machine learning. The instances approach is you just remember the cases that you saw. And then when a new test comes up, you just try to find the nearest case and you apply it. So you're doing medical diagnosis, you just remember all your past patients. And when a new patient comes in, you find your old patient that's most similar to her, and you apply the same diagnosis. Of course, there's many variations on this, and we will spend a whole, you know, a lecture on it, but the basic idea is joyfully simple and unsurprisingly powerful. So this is the use of instances themselves as the representation for what you want to learn. Then getting on towards more sophisticated things, there are a lot of approaches in machine learning that use probability, right? Problem is a very powerful tool. It lets us deal with uncertainty, it lets us weigh evidence, you know, it means we don't have to always be making black and white decisions. Efficiencies that we concern, graphical models are a very large family of probabilistic models where I use a graph of the dependencies in my distribution. So we will also look at some of those, and in particular there's two main families called Bayes Nets and Markov Nets, and we will see what some of them are. As some of you might know, the Turing award this year was won by Huda Pro, a great computer scientist. His main contribution was developing Bayesian networks. Neural networks, this is a very fun one. The idea in neural networks is let's reverse engineer the competition. If you're going into market with a new product and the competition is way ahead of you, it's a very good tactic to just look under the hood, right? See how they're building their cars and see if you can make yours the same. While they're behind, this is a good thing to do. And make no mistake about it, when it comes to learning, we are way behind ourselves. What does that mean? We as the producers of machine learning programs are way behind ourselves as humans. The human brain is the most amazing machine learning system ever invented. And now there are animals, too, for that night. The human brain is really doing something extraordinary, and we haven't figured out what it is yet. If we did, you know, there wouldn't be worth 10 Microsofts, it would be worth, I don't know, 1,000 Microsofts, or, you know, the whole world economy potentially. So the idea in neural networks, and of course the human brain is a network of neurons, hence the name Neural Network. In neural networks, let's look at what the human brain does, and then let's see if we can turn that into an algorithm. A very selective idea. And again, we will spend a week seeing how we can do this and the state-of-the-art things that come out of it. Even more recent, so all of these approaches have been around for decades. They continue to be developed. So new algorithms in any of these families continue to appear. Here's one that became popular more recently, but is also very, very powerful. And this is support vector machines. Support vector machines, in a way, are a more powerful version of instance-based learning, but they are quite powerful. They are different from some of the other methods in that they use much more sophisticated mathematics. And many people just use them as a black box because often they work very well, but it's a pity to have to use them as a black box. And, you know, we in this class don't want to use anything as a black box. We want to understand how things work so that we can change them, make them fit our needs, and then tomorrow when things come along we want to be able to then understand those as well. So what we will do when we study support vector machines is we will cover just enough of the mathematical background that you can see what support vector machines are doing and why. And then one thing that people have also found in recent years is that the best thing that you can do when it comes to learning is not to learn one program or one model, but learn a whole bunch of them and combine them. This is the wisdom of crowds applied to algorithms. It's the wisdom of algorithms, right? Often you have many people vote on something they come up with a better estimate than any individual person. The same thing is true of machine learning algorithms. If you run a hundred algorithms with a hundred different conditions each one of them and combine the results, you will usually get better results than if you just run one of them. This is very powerful, for example, the Netflix prize was won and the second place was also systems that combined a lot of different algorithms. In fact what both of these things were doing was competing to see who could aggregate the most people quickest. They all started out being small groups competing with each other and then they realized that by aggregating they could do better. So they wound up with larger numbers of things being combined than ever before. I think in the future we're going to see more of this. So being able to create model ensembles is a very important topic. It's often a very easy way to get a large extra payoff after you've put all the work into developing algorithms and trying different things. Instead of picking one, combine them. And we will also see how to do that. So these are the main things that we will cover here but not all of them. But this at least gives you a flavor of the kinds of representations that get used in machine learning. Questions so far? All right, so. But of course once you've picked a representation for your program, your work has just begun. Right? Sure. You've picked a language. Now what? Well this is where the next thing comes in and the next thing is evaluation. What the machine learning system is going to do is generate candidate programs. Right? From the data it's going according to some algorithm generate a candidate program. Is this what you want? These were the inputs and outputs that you gave me. I have just created a program that seems to pretty well transform these outputs into those outputs. Is this what you want? Right? Now if you could personally inspect every program that the machine learning system generates fine, but of course you don't want to do that. It's going to generate easily millions of candidates. So what we need is an automatic way to evaluate the program.  How am I going to gauge that version A is better than version B? And therefore select version B. And then maybe try variations of B, C and D and select one of them. So here are some of the measures that people use. The first measure is accuracy. Very simple. Out of those examples, how many of them did you get right? Right? Let's say, you know, I'm an email provider and I have lots of examples of emails that I spam and not spam. I know which ones I spam because the users conveniently mark them as spam. Right? And now I create a program that predicts whether something is spam or not, and yet this is just a fraction of the spams that it marks as correct, plus the non-spams that it correctly marks as non-spam. So this is like the fraction of diagnosis that were correct, or the fraction of your credit cards that you issued that they really did not, you know, go bankrupt and so forth. So this is the simplest measure. Two other measures that are often used like information retrieval applications are precision and recall. Precision and recall are a lot like accuracy. Precision is out of all the fraction of things that you predicted were yes, how many of them really were yes. So what fraction of your spams, of your predicted spams really were spams? What fraction of the pages that you said were interesting really are interesting? And then recall is out of all the ones that really were spams, how many did you identify as spams? So notice that these two measures are complementary and you really want to do well on both of them. The reason these measures are useful over something like accuracy is that in many domains there is a very large number of true negatives. Most of the things are false, they're not, you know, interesting and you don't want to mark them as interesting and you won't and you want to ignore those. Accuracy doesn't ignore those precision and recall do ignore that. Now before you're trying to predict instead of just being yes, no, like spam, not spam or interesting, not interesting, it's something like a rating. For example, if I send my catalog to this consumer, how much will they buy? In this case, you're predicting the numeric quantity, so you want to measure that varies with how much of an error you make. Again, there's many things that you can use here, but the most popular one is squared. So it's the sum over all your examples of the square of the difference between what you predicted and what the true value was. Okay? When you're building probabilistic models what you're trying to do is try to predict the probability of something. For example, what is the probability that this page is interesting? Then, you know, the standard measure to use is something called likelihood, which you may remember from statistics 101, but, you know, even if you don't, we'll go over it here. Likelihood is basically how likely is what you're seeing according to your model. If what you're seeing is unlikely according to your model, you're probably not a very good fit to the real world. If what you're seeing is very likely according to your model, then your model to the best of your knowledge probably does fit the real world. Okay? So that's the idea of likelihood. Likelihood is often good when your learner is not very powerful, but when your learning is powerful, it's very like, you know, you could get by very high likelihood by just, you know, memorizing your examples, and then you don't generalize, but you want to generalize. One way that you have of generalizing is or you want to generalize is instead of using likelihood, use what is called a posterior probability. Again, we will look at the details of this when the time comes, but the posterior probability is a combination of two things. One of them is the likelihood, and another one is the prior probability. The prior probability is how likely you think something is a priority. This is where you get to put your knowledge, your expert hypotheses, your assumptions into the system. You can put them into your prior. Before you've seen any data, you believe that certain things are more likely than others. That's your prior distribution. And then when you combine that with the likelihood you get your posterior, and then it's the posterior that you use to evaluate your models. So when you're using prior probability, you're actually evaluating your candidate programs using a combination of the data and your own beliefs about the product. So this can be very powerful. It can also be complicated, but we will see how to do it. So, you know, these are all things that people have used for a while. But here's something that people discovered when they started applying, you know, machine learning in practice, you know, on a big scale. They often found that these algorithms, the machine learning algorithms were not really producing what they needed. And the reason for this, a very common reason was that if you look at something like accuracy, right, what percentage of my SPAMs or non-SPAMs did that predict correctly? You could actually be very accurate in a very poor job. For the following reason is that the cost of a false positive, saying that something is a SPAM when it isn't, can be very different from the cost of a false negative. Something that is not a SPAM and you say it is. Or sorry, something that is a SPAM and you say it isn't. If something is a SPAM and you say it isn't, well, then it just gets through and annoys the user a little bit. Something is a message from your boss and I need this by tomorrow and you're fired if you don't do it. And that gets tagged as SPAM because it has too many exclamation marks and too many words in capitals. This is like a realistic thing. Then you could lose your job because of that. So the moral of the story is you want to be conservative. You want to err on the side of predicting that something is not SPAM. And as it turns out, this is a very, very common thing to happen. For example, if you have a test for AIDS and you want to err on the side of telling people yes, you may have cancer do another test as opposed to letting them walk away with a cancer in back. So the moral of the story is we want to take cost into account when making decisions and ideally we will actually do that right inside the learning algorithm itself. So this is another type of measure that you could use. More generally, you could use what in decision theory is called utility. Different decisions, different outcomes have different utilities that you want to do. This is what being rational means is you want to make the decision that maximizes your expected utility. So this is your average utility over the outcomes that you have. And again, you could use that after superiority or you could use that inside the learning algorithm. More recent things use even funerals like, for example, in support of the machines, we use the margin. The margin roughly has to do with how far you are. When you make, for example, a boundary between on this side it's spam and on the other side it's not spam, I would actually like my boundary to be as far from any given example as possible. Because if it runs very close to an example, maybe that's not quite where the boundary should be. So that's another thing, another measure that you can use. And then there's the ever-popular measures that come from the era of information theory. Information theory has lots of interesting notions like entropy, the information content, KL divergence also known as the relative entropy between variables. We can also use these to guide our learning and indeed we will see examples of that. And there's many more. Again, people come up with new measures every year. These are the more popular ones and we're not going to cover everything but it's good to have a notion of what some of the main things are. Often an exercise you can do is you can take an algorithm using one of these measures and change it to use another measure and see what has to change in order to do that. For example, you might try to turn an algorithm that is not cost sensitive is just maximizing accuracy into one that is cost sensitive. All right, so we've chosen a representation, we've chosen an evaluation measure, but in some sense the most important part is yet to come. The most important part is, okay, so now how do I actually generate candidate programs? So that part is the optimization or search part. Now you need an algorithm that will actually generate lots of candidates for you that you can evaluate. And then finally pick one of them and you return it to the user and that's the program that you're going to use. Now, of course, if you have unbounded resources you could just try every program on Earth but you probably don't want to do that because you don't have the resources. And in fact, even if you have the resources you might not want to try that because you might overfit this and then get better results that way as we will see later. So that's why we're talking about picking which programs to generate. And of course this should be guided by the evaluation measure. This is why we have the evaluation measure inside the system and outside. My algorithm search algorithm is going to be evaluating candidates, picking some of them and then generating variations of those and so forth. Now again, there's many different types of search algorithms that you can use or optimization. People in operations research optimization, in computer science we call it optimization or such but it's really all the same thing. The type of optimization that you want to do naturally depends on what type of representation you're using and what type of evaluation measure you have. In particular, if your representation is discrete, what you need to do is combinatorial optimization. What you do is this process of combining pieces into larger pieces, see how good they are, taking a piece, modifying it, see how good that is and so forth. The simplest type of combinatorial optimization is just greedy search. It's what I've been using as an example. You generate a candidate, you see how good it is, you generate 10 candidates, you pick the best one and then from that candidate you generate 10 more and you keep going. This is the research but there's many other types of combinatorial optimization that you can use. If you have numerical parameters to optimize which many machine learning algorithms if not most do, then what you use is what's called convex optimization. It's really just numeric or continuous optimization. Convex is a technical term that we will see what it means later on. The simplest form of convex optimization is gradient descent. It's the continuous analog of greedy search. Gradient descent is if you want to find the value just let the ball go down the hill. That's what it is, right? Wherever it is steepest, it's where we'll go. This is good for a lot of things but it's also pretty crude. It can fail in many ways. It can be very, very slow, it can get stuck so we'll see some better ways of doing convex optimization. And finally, particularly most recently people in machine learning have started using a lot of constrained optimization. So what is constrained optimization? Constrained optimization in a way is a combination of combinatorial and continuous optimization. It's continuous optimization where you are subject to constraints. I have this surface, right? I'm not trying to find my optimum in that surface but I'm trying to find the optimum subject to stay within a certain box. And this box is what the constraints are. The famous example of this is linear programming. I have this linear function that I'm trying to optimize. I'm trying to optimize my profits from my factory or whatever but I have these constraints on how many machines I have and how many things I can produce an hour of the components and whatnot. So I'm trying to optimize a function subject to constraints. If the function and the constraints are linear then what we have is linear programming but there might be no linear as well and some of those techniques get used in machine learning. So this is just a very brief overview of the space but I think it's very important to have a map of the territory before we dive in. What we're going to be doing most of the weeks of this class is looking at specific representations and optimization algorithms for them and issues that arise but at this point we at least have a general map of the territory. Questions so far? Now there's more than one type of machine learning and again it's good to be aware of what the main types are. The examples that I've been giving so far and that little diagram that I have with the box and the computer and the program these are really examples of what is called supervised learning that's also known as inductive learning. This is the largest subfield of machine learning it's the most mature subfield and it's the one that's most widely used so it's the one that we will spend most of our time on. So what is it? This is learning where you have supervision this is why we call it supervised where the learning problem is given examples of the desired output. The learning problem is told this is spam, this is not spam this person has aids according to this test this person doesn't. This is the direction in which you should drive in order to stay on the road. So obviously learning with supervision is much much easier than learning without supervision. It's still pretty hard and we'll see what some of the issues are that arise but it's certainly a much more solid technology at this point than easier to deploy. The problem with it of course is that it's hard to come by supervision. Big data is all over the place generating you know the rules and rules of data can be done very easily in many domains. Labeling the data still has to be done by humans. In cases where the labels for the data are generated automatically for example this stock I predicted that it would go up tomorrow and tomorrow it did go up. Those domains are great because you can really kill them with supervised learning but in many many domains you don't have supervision so then what you do is you have to learn from data where you yourself have to figure out what the output is. An example of this is cluster. For example a very popular exercise in marketing is to cluster your customers. Like Nike's two main types of customers are teenage boys and middle aged women. True fact. It's very important to realize that these two clusters exist because they have very different tastes. A marketing campaign geared to teenage boys is unlikely to appeal to middle aged women and vice versa. So cluster can be really really important. A marketing journal will not tell you in advance what those clusters are. You have to figure them out. Also another example this is clustering text. I have millions and millions of documents in my company. How do I organize them and find them? Well maybe I can form a hierarchical cluster in them. Things like Yahoo and Demos they are hierarchies of documents or web objects. In most cases in the beginning in the early days these were done by hand but pretty soon they were done using machine learning. Use machine learning to figure out what this hierarchy is. And then once you have the hierarchy when a new document comes along you can say oh this one is about sports or more specifically it's about baseball or even more specifically it's about this or that. So once you figure out what the outputs are then you can figure out how to turn the inputs into the outputs and then in the future you produce those outputs in response to the inputs. Now unsupervised learning is also a longstanding field of machine learning but obviously it's much harder. It's much harder because you have less information to work with. It's also much harder because it's much harder to tell what is a good result and not. In supervised learning it was spam and you predicted it was that's a success. You gave the credit card to this customer and she paid you know her bills on time. In fact the best credit card customers are obviously not the ones who pay the bills on time. Are the ones who are always a little bit late this season what not. The ones who don't pay are bad. You have the supervision to produce that. So what do we do? Well this is where semi-supervised learning comes in. It is often the case that you can't afford to label all the data but you can afford to label some of it or you have some by a lot some subset of the data that does come with labels. And so what you want to do is you want to start with that small subset of the data that is supervised and then you want to bootstrap from there to label the ones that aren't supervised. So use a small amount of supervision to at the end of the day do a large amount of unsupervised learning. And this can be amazingly effective because a little bit of supervision can go a long way. In fact you could say that this is how most people learn most things, right? It's semi-supervised. They get a little help from their parents or from their teachers but then they're on their own. The parents and teachers can be on top of them all the time saying wrong, right, wrong, right. So we're not going to talk about semi-supervised learning here just because there isn't time for everything but it's good to be aware that it exists because it might be just the perfect thing for your problem. Finally there's reinforcement learning. Reinforcement learning is probably the most ambitious type of machine learning. AI types tend to like reinforcement learning a lot. It's also in some ways the hardest. The idea in reinforcement learning is that reinforcement learning is not learning to make point-by-point decisions. For example, is this stage interesting or not? Does this patient have this disease or not?  You're making a sequence of decisions. You're playing a game, for example, or you're doing something over time. And it's only after you've made a bunch of these decisions that it becomes clear whether you were doing the right thing or not. At the end of the day, you win the game of chess or you lose. And then you have to somehow propagate this information back to those decisions that you're making early in the game. When it was not obvious at all whether they were going to be good or bad. So, you know, where reinforcement learning is a kind of semi-supervised learning because you only have a small amount of supervision but it's distinguished by the fact that there's this sequential kind of semi-supervised learning. You're learning to propagate the results of the payoffs when you finally have them back to the decisions that you made earlier. Again, we're not going to be covering this topic because there's no time for everything but it's a very interesting and large area of machine learning. It is by far the least used of all these types of learning. So, you know, if you're looking for algorithms to use in practice tomorrow, reinforcement learning may not be your pick. But you should at least be aware that it exists because, you know, it might. And in the future, there'll probably be better reinforcement learning algorithms that will be more easy. Yes. I have a question about the semi-supervised learning. I'm confused about if it is just learning with the smaller training data set, isn't it the same as supervised learning just with the smaller training data? No, no. Let me clarify this. So here's the idea.  This is supervised learning. Suppose none of them are labeled. Then you just want to cluster them into good and bad emails and maybe this will coincide with being spam and not spam. This is very hard. You have no labels. Semi-supervised learning is when you have three types of emails. Some are labeled as spam. Some are labeled as not spam and some are not labeled. So for some of them you don't have labels at all. And what typically happens in semi-supervised learning is that you only have labels for a small fraction. So let's suppose, for example, that you are an email and this is a real example in many cases is what happens. Let's say you're an email provider and you have a billion emails. But you only have 100,000 of them labeled as spam and 100,000 of them that for some reason you know for sure are not spam. So this is the semi-supervised learning state. And the idea there is that you want to start out doing supervised learning. Just looking at the ones that are labeled. But then from those you can bootstrap.  So maybe those are spam and maybe those are not spam. And now I have a larger training set. Until finally, hopefully, I've labeled the whole training set. When this works it's extremely powerful. Of course it's harder to make it work than fully supervised learning but it's easy to make it work than fully unsupervised learning. More questions? Okay. So these are the main types of learning. In this class for most of you we're going to focus on supervised learning also known as inductive learning. Since this is doing what the philosopher is calling induction. In some ways it's the oldest known type of learning. Towards the end of the class we will talk some about unsupervised learning. But for most of our time here we're going to be talking about inductive learning so let's start focusing on that. So what is inductive learning? What is the problem? Why is it hard and how can we solve it? Here's a very simple definition of inductive learning. What I have is examples of a function. Each example has two parts. X and F of X the output. X is your email or maybe it's just a list of the words that appear in your email. This is a common thing to do. And then F of X is this is spam or this is not spam. Or it could be something like automatically picking which folder you want to refile the email into. Or automatically deciding what tags you want to level it with. In all cases the key thing that defines inductive learning is that this is the test. When I see an X when I see an example that I have not seen before this was not in the data that I used to train my learning algorithm my training data. Along comes a new example a new email. Can I now classify? Can I now predict this one correctly? Can I for a new example X correctly predict the value of the function? This is the problem and this is the challenge. I have to guess what the functions of unseen examples are. This is very different from almost everything else in computer science. In the rest of computer science you're doing things that are more like deductive reasoning. I have these things and I know how to turn the crime to get this result. The crime might be very complicated might be millions of lines of code but you only have to work on input state you know what they're going to be. Here I basically have to make this leap from the examples that I've seen to the ones that I haven't seen. A new patient comes along her combination of symptoms is different from any one that I've seen before. Can I still correctly predict what she suffers from? People are good at this. Traditional programs are not necessarily very good at this but this is what inductive learning is all about. Now there's three main types of inductive learning. If the function that you're trying to predict is discrete for example spam versus not spam or what topic is this piece of text on then the problem is called classification. And each of the discrete outcomes is called a class simply enough. Before you're trying to predict this continuous like you're trying to predict the continuous variable for example there's this company here in Seattle that you might have heard of that predicts house prices. This is a very nice thing to be able to predict. This is a regression problem. The house prices are continuous variable. Regression is what most statisticians do for a living. People in computer science and machine learning tend to be more interested in discrete things. So we will focus mostly on classification in this class. Nevertheless for most classes of algorithms there's a classification version and there's a regression version. So if you know one usually with a little bit of tweaking changing the evaluation measure and some things you can see how you would get the other from the first. And we will touch on regression occasionally because you know we want to have some coverage but again we don't have time for everything and so mainly we will focus on classification. The other thing is when the final type of inductive learning is when what you're trying to predict is the probability of that instance. How likely is this thing to show up? Or how likely is this page to be interesting? In this case what you're trying to compute is a probability and now this is called probability estimation. You could think of probability estimation as a kind of regression since a probability is variable but it's a very special kind of regression because remember the probabilities of all things have to add up to one. So you're not free to just predict any old thing that you want. There's this normalization condition that you have to satisfy. So at the end of the day the techniques that you use for probability estimation are often very different from the ones that you use for regression. And if you're trying to predict the problems of discrete outcomes often the classification and the probability estimation go hand in hand. So you have to build a classifier by building a probability estimator and then thresholding the probability. So I build something that predicts the probability that an email is a spam and then I say if the probability is about 0.5 then I predict that it's a spam. Or if I want to be more conservative then I will predict that it's a spam if the probability is above say 0.8. So these tasks are different but there's also relations between them. Questions about any of this? Okay, so that's the definition of inductive learning. Here's a preview of what we're going to do in this class. So as I said, most of the class will be spending on supervised learning. I believe it's very good to get your hands dirty right away. Start working with real algorithms and applying them to real things right away. Many machine learning algorithms are joyfully simple at least the basic versions of them and the basic versions get you very far. People often get intimidated when they see these very mathematical machine learning algorithms and machine learning textbooks with literally hundreds of equations in every chapter. There's equation number 11.647. But the truth is actually that is all icing on the cake. You can get a lot of the problem machine learning with much simpler things. So let's start studying some of them right away. So we will look at decision tree induction, rule induction, instance-based learning basically one of these every week, Bayesian learning or more generally statistical learning, neural networks, support vector machines, how to do ensembles of these things. We will spend a week on learning theory. There's a largely determined theory and some people like to start with a theory. I actually don't think that's the best idea because you don't know the point of the theory in the beginning and you know, it's very natural to be alienated. What we're going to do is like, we're going to look at the learning theory after we've looked at a bunch of these things and see what the common questions are that arise. One of the things here is that there's a set of representations and evaluation functions and whatnot, but there's a set of recurring problems that keep coming up like over-fitting and the cursive dimensionality independent of the representation. And so once you've seen that, I think at that point hopefully we'll be ready to like, can we really come up with fundamental notions of how we deal with these? And that's when we will dive into some theory and we will focus on the theory that's useful. There's a lot of gratuitous theory out there but that's not what we're going to do. It's not going to be useful to you in deciding, you know, what are we going to use and how to optimize it and whatnot. And then actually after that, we will look at support vector machines because support vector machines are actually a machine learning approach that comes out of this theory. A lot of the approaches that we're going to see, they predate some of the theory that we're going to look at, the support vector machines actually come out of that theory, so that makes a very nice surprise. Also some model ensemble methods came out of that theory. And then finally, as a huge field, we could easily spend the whole quarter on unsupervised learning. We don't have time to do that, but we do have time to look at the two main types of unsupervised learning and a few of the key techniques in each one.  And the two main types of unsupervised learning are clustering, which I already mentioned, and dimensionality reduction. The idea of dimensionality reduction is that there's two ways in which big data can be big. Two oversimplifying things a little bit. One is that you have a lot of examples. I have, you know, I'm Facebook, I have information on a billion people. Wow, that's big data. That's one dimension of big data. But the other dimension of big data, you know, in machine learning terms, that means I have a lot of examples to learn from. But the other dimension is that I might know a lot about each one of these people. In fact, you could even argue that that's the big advantage that Facebook has, is that it actually has more information than, you know, Google or Amazon or any of these companies. So in technical terms, we say that you have many dimensions for each example. I have not a thousand variables. I might have hundreds of thousands or even millions of variables. And this really is a brave new world. If you look at traditional statistics, you know, what's considered high-dimensional and there's like 10 dimensions. In fact, in the old days, anything above three dimensions, which is what our world has, was considered high.  A thousand dimensions is starting to get interesting. A hundred thousand is big data. But now if you have all those dimensions, this is going to be very problematic. As we'll see, this is going to make life very hard for the machine learning algorithms and it's going to make life very hard for you.  It's going to take too long. So the very natural idea in dimensional reduction, as the name implies, is that we want to reduce that number of dimensions. I don't want to be looking at a hundred thousand pieces of information. I want to be looking at, you know, a dozen. Or maybe even three, so that I can plot it, you know, in 3D or even two. Or, you know, four if time is one of the dimensions. So dimensional reduction is a study of how to take examples with many, many dimensions and reduce them to the most informative dimensions. Okay? And again, this is a very active area of research these days. Many fascinating governments being invented. It's time to cover the main ones and to give you a sense of the power of this type of machine learning. Okay? All right, so, before we go into all of that, however, there's something very, very important to remember, which is what we're going to spend, you know, 99% of this class on, or let's say 90 plus percent is actually only 10% of what people who do, doing analytics, you know, machine learning in practice spend their time on. And it's very important to be aware of what the other 90% of it is. Okay? Because, you know, if you become a data analyst, this will be chances are what you spend most of your time on. So what are those things?  Right? You want to design a vaccine for AIDS. Right? This is, of course, a very real example. Right? What is the first thing that you have to do?  The first thing you have to do is understand the problem. Understand the domain. Learn the biology. Learn the marketing. Learn natural language if you're going to do document, you know, processing. Okay? This is where talking to experts is important. Usually a machine learning project involves at least two people. The machine learning expert and the domain expert. In some cases these two people are the same, but that's a very, you know, high burden for one person to bear. You might be working in collaboration with a doctor who has the expertise about AIDS or in collaboration with a marketer or in collaboration with, you know, someone who's an expert on finance. Okay? If you're willing to talk with you, you have to learn some finance or medicine or whatever to talk with them. Okay?  Right? Because there's no point in understanding the domain if most of it is irrelevant to the task at hand. And sometimes the goals are very clear. Right? This is a hedge fund.  You have $10 million, you know, invested. Learn to predict better than chance and if you do that successfully, you know, you'll be rich and if you don't do that successfully, you'll be fired. Right? In that case, the goal is clear. More often, actually, what happens is that the goal is extremely unclear. The goal is like this, you know, like I'm the CEO of a company and I know that we have a lot of data. We have tons and tons of data and our customers coming every day to our website and I have the feeling that there's enormous value in this data. My competition is ahead of me in data mining and we've got to catch up with them. Please do something. Do something is not a very clear goal. Right? In some ways, this is a harder problem and in some other ways, it's actually a great opportunity for you. Like, go to town. Right? Have fun. Figure out what there is to do. When I talk to people in industry, like, you know, people who do machine learning at these companies, the number one thing that they always say is then we can. They only have so many thousands of people in the company and, you know, some companies, a good chunk of the engineers are, you know, people with expertise in machine learning but they have too many things to try. So go and discover where in the company is the value to be created. Either way, it's very important to understand the problem, the domain, the goals, the constraints that you're going to be operating in. Certain things might be very good machine learning but might not be deployable. In which case, you know, you should think about that so this is step one. Step two. Sounds very boring and banal but this is often the single most time-consuming step. You've got to get your data. Remember, the reason we can be lazy is that the data is going to do our work for us. No data, no learning. Big data, big learning, that's where the opportunity is. Like, the reason machine learning is taking off like gangbusters is that we have more data than ever. Does this mean that our life is easy? Life is harder. Dealing with more data is harder than dealing with less data. At the end of the day, you might be able to learn a much better model but you have to and you know, the thing is that like the bigger the data is, the crappier it is. This is like Murphy's law of machine learning.  You know, in the old days somebody would do an experiment in the lab, very well controlled, would have a thousand data points with ten dimensions each but it was like sparkling, clean data. These days instead of those thousand data points and each one of them has ten thousand dimensions but you know, half of it is garbage. Half of it is people who, you know, put in their birth data as being January 1st, you know, 11-11. Half of it is like, you know, incompatible formats got munched together, right? So you've got to take all that, you have to find your data, you have to clean it, you have to integrate it. You often have multiple sources of data. In all large projects, this is always the case. You don't have a single source of data. You have multiple sources. Often from very different origins and you have to put them all together.   Right? For example, I know an example where the program learned that men get pregnant because somebody merged the fields wrong. Right? That kind of stuff happens. Okay? So cleaning the data, preprocessing it, integrating it, selecting what's what's most important is a very big, big chunk of all of this. Finally, you get to what's usually considered the fun part and again, if you talk to the people who do this, this is usually the part that they really like to do, which is to learn the model. Right? This is where the fun begins. You know, you do discovery.  Right? This is when you get to discover things and, you know, follow hints, you know, be a detective. And this is where we have a lot of great technology for you to use. This part is very mature. Part of the reason why it's very mature of why we're going to spend almost all our class on it is that we can come up with very general techniques that you can learn in this class and then you can apply to a hundred different things. And tomorrow there'll be a hundred new things that you can apply to that. Today we haven't even thought of them. Right? So here we have very general tools and they're pretty mature. So this stuff works. Part of the reason why this often doesn't take most of your time is that it's pretty good at this point. So, you know, using it actually doesn't have to take that long. It depends on how accurate you want to get.  But in many ways, this is the most efficient part of the whole process. After you've learned your models, you are not done yet. You have to understand them. There are some areas where if your model works, people are willing to close their eyes and let you use that. One of these areas is finance, in some cases at least. Nobody really, at the end of the day, understands how the markets work. If you're out with them, no matter how opaque it is, reliably predict something better than chance, well, it's making money. We'll take it. We prefer to have something we can understand, but you know, if we can't understand but it's making money, we'll live with it. For most problems, however, if people don't understand what your algorithm produces, they will refuse to use it. You don't want to tell somebody, well, you need surgery because you have breast cancer. Why? Because this complicated nonlinear function with these coefficients is outputting plus 0.5, which is above threshold. This is not a very persuasive thing to tell a patient. Or to tell the CEO of a company if you want to persuade them that there's a different market segment that they need to address and whatnot. Remember, you're probably going to be in the room with experts who are very convinced of their expertise and often your learning algorithm will tell them, like, you know, I'm sorry, no, we know better now. And they're going to say, this box of junk is telling me that I'm wrong, no. I know of many examples where people had very accurate machine learning algorithms that were not used because of this. Just to give a random example, you can use machine learning algorithms for wind design. But, you know, if the wind flies and whatnot and has the right envelope of characteristics, people might be satisfied with that, but hell no. They wouldn't be convinced that that thing is safe. It's just some black box neural network that produced this design and they're not going to take it. The second reason why interpreting results is very important, more subtle but equally important, is that this whole thing is not a one-shot process. It's a cycle. And you need to understand what your algorithm is doing in order to then go and improve it. The machine learning algorithm is doing this very large search. That's what the computer is for. But the hour loop involves you. It involves you tweaking the algorithm and trying different things. And again, this is what people spend a lot of time with. But it's very hard for you to tweak the algorithm or try another algorithm or maybe bring in a new source of data because that's what was missing if you don't understand what the algorithm is doing. So it's very important to understand the results in order to make that loop converge to the point where it's doing something really good so this whole thing is really not a linear sequence of steps but it loops within loops. From interpreting results you might want to go back to learning models or you might realize that you need better data. When learning the models you might realize that you need better data. This whole process might lead you to a better understanding and based on an understanding you're going to do a whole bunch of different things now. So this is how things actually work in practice. Finally, let's suppose you came up with a crackerjack model. This thing works amazingly well. Are you done? You're not done. The majority, I don't have a firm statistic on this but I'm willing to bet that the majority of machine learning projects that were successful in the lab, if you will actually wind up not being used in practice because as with anything else between your project and people actually using it there's all these things that have to happen. There's all these stakeholders that say yes or no that might help it or hinder it. Things might have changed on the ground while we were learning your model and these things are all getting better. So I think the hit rate is actually improving. But the key thing to remember is that your job is actually not done. You can't just go to your boss and say here's the model, not use it. You actually have to make sure that the people who have to use the model will be willing to use it or that this thing will get deployed and they'll have the format like here's an example. Donnelly the largest printing company in North America. They actually had at one point the result of this was a decision tree. What they actually created was a piece of paper that got pasted onto the machine saying if this reading is this and that reading is that do this, this was the deployment. Of course there's often the deployment is you have an algorithm on our website that is predicting oh, if you bought this book you're gonna buy that book as well. But it has to work at that level number one and then number two it has to keep on working. The world keeps changing. The phenomenon that your modeling might have changed. Also the data might have changed. Your algorithm assumes that the data is coming in this form but now the data has changed to that form and nothing starts to go haywire. So like any piece of software in a way machine learning system also has a life cycle and you have to keep outtaining to it making sure that it stays relevant if necessary going back and redoing it or even better and as increasing as the case is making sure that the learning is happening online. Every day you're adapting the model or every week or every month. So the key point to remember here is that machine learning in practice is a cycle that has many steps. We're now going to zoom in on the one step in the middle that's very well understood but bear in mind that the others are there as well. The other reason of course why we can teach learning models but not the other parts so much is that learning models there's a very general set of techniques many of these other parts are very domain specific. There's a number of things that you can say for example about how do you deploy systems but really it's going to be dependent on your particular domain. The same with things like data cleaning and data formats and whatnot. The bang for the buck of trying to teach your stuff like that is much lower. I have other things but it's very important to remember that those things are there as well and you're going to have to deal with them if you want to do successful machine learning in practice. Questions about any of this? All right, so very good. Let us take a break. It's 7.54. Let's take a 10 minute break and reconvene at 8.05. We'll generally be doing this every week. We'll take a 10 minute break roughly in the middle and then do the second part. So see you back here at 8.00. All right, let's keep going again. I'm going to round 2. Round 2, exactly. Round 1.2. Round 2 is next week. So what we're going to do the rest of today is dive into the meat of things but before we start studying specific algorithms, specific representations let us just try to understand what the inductive learning problem is, why it's hard and also how we can solve it and what the important dimensions of the problem are. Okay? So, what is inductive learning? Just as a quick recap, we are given training examples of some unknown function X. A training example is a pair of two things. The input X, which could be a vector or it could be a piece of text or it could be lots of things. And the output corresponding to that input f of X. Okay? And our goal is to find a good approximation of f. Ideally, we will be able, from those examples, discover exactly what f is most of the time that's too hard but maybe what we can find is a good approximation of f. Good enough that when we apply f, when we apply our approximation to tomorrow's examples of f, most of the time they will get the right result or at least the useful result. Okay? So, here are a few concrete examples of this to keep in mind as we go through this. I've already mentioned some of them but let's make them a little bit more concrete. Number one, credit risk assessment. Okay? Very important application. In this case, your X is the property of your customer. You know, like their job, how long they've been at the same house, their income, the size of their mortgage, about your debt, you will have to write on the form that they send you. And also, if you're asking for money to buy a specific thing, you know, properties are the thing that you're trying to buy. You know, if this is an investment, it's one thing, if it's consumer credit, it's another, et cetera, et cetera. The output that you want is either approve or deny the credit request in the simplest version. Okay? So simple binary decision. Here's another example, disease diagnosis. Again, a very important example. Their age, their sex, their, you know, things that they suffered from in the past and also the results of, you know, the tests that you've applied to them. You know, both the symptoms that they have and blood tests, x-rays, et cetera, et cetera. And the output now is potentially a prediction with many different classes, right? It's like, what do they suffer from? Okay, which disease is generating these symptoms? And potentially even, you know, actually, you know, what medicine should you be taking? Or what combination of medicines? So it could just be a diagnosis or it could actually be a therapy. Here's another example, a very popular one since the early days of machine learning and actually an even more popular one these days because, you know, there's cell phones with cameras and what that. Face recognition, right? In some ways, this is one of those quintessential machine learning problems. Here, the input is just a bitmap for the person's face, right? I give you a picture of somebody, right?  And the goal is to say who it is. Right? This is you. This is your grandmother in this picture. You know, this is Barack Obama. This is whoever. Okay? Final example, again, a very famous one these days, automatic security. Right?  Right? What is the simplest way to formulate this problem? Not necessarily a complete solution, but at least the heart of it, it's like this. The input is, again, a bitmap image, right, captured by a camera in front of the car. Right? It's a picture of what's in front of the car. And the output is the degree to which you should turn your steering wheel. Okay? Let's suppose that we're going at a constant speed or that it's the person controlling the speed, right? The computer now just has to figure out which way to turn. Right? And this is now a continuous problem, except that, you know, you could quantize and say, well, you know, there's only 10 different directions from hard left to straight to hard right. And your goal is to, given a picture, predict which way the wheel should be. Okay? So keep these examples in mind as we go forward. This is a nice variety of the kinds of things that you might want to do with supervised learning. But here's an interesting question. Right? So these are all good classic examples of supervised learning. There's others, but there's also problems through which supervised learning is not a good idea. And as with any technology, it's very important to have a sense of what problems machine learning is good for and what problems it's not good for. In particular, what is inductive learning good for? Okay? And this question actually has some very interesting answers. So here are four different situations where inductive learning may be a good idea. The first situation is where nobody knows the answer. The reason you don't have, you know, always think of this comparison, right? I could have this program be learned by machine learning algorithm from data or I could have a human write the program, right? If it's better to have a human write the program than don't bother with the machine learning, right? So another question is like, under what circumstances is it better to use supervised learning, right? Here's the first one. In a way, it's an obvious one. If people don't know the answer, then they can't program it, right? In particular, you know, let's say you're trying to find something that binds to the ACE protease molecule, right? So that inhibits the AIDS virus, right? It keeps it from multiplying and so forth, right? It would be great to have an answer to this question. Nobody has it, right? The amazing thing is that there are actually many problems where machine learning can find answers that people don't know. So the machine learning, really, there's doing like honest-to-God discovery. Why would that be the case? Well, people in machines have different strengths, right? People have a lot of varied knowledge and a lot of intelligence, a lot of tactics, you know, problem-solving ways.  Your brain has a lot of hardware for doing vision and language, but not for other things, right? If your problem is to design a molecule, well, you know, in the lab can only try so many molecules. If you have a good simulator of these molecules and you've learned to predict whether they're good or bad for your purpose, you can, you know, have your cluster be similar in millions of these all night long at very low cost, okay? So the learning can have an advantage when you can use more computing power, et cetera, et cetera, than the human hands, okay? In many ways, these are very exciting applications of machine learning because they are learning things that weren't even known before. However, even when we're not in that situation, and, you know, many or even most of the applications of machine learning are not in that situation, we are in a problem that humans can actually do better, right? So if you could get a human to do it and the human was cheap enough, maybe you could just let the human do it, right? But you want to program it. And there's a very big difference between somebody knowing how to do it and somebody knowing how to program it. We spend a lot of time programming things, so we almost forget that this difference exists, but consider the following. Suppose, for example, that, you know, what you're trying to do is character recognition, right? We humans are really, really good at character recognition, right? We can recognize, you know, semi-garbled handwriting, you know, pharmacists can recognize doctors' handwriting, writing almost superhuman-wise, et cetera, et cetera. But nobody knows how to write a good program to recognize characters. Nobody. People did that in the beginning. They said, well, what is an art? It has a stroke like this and a stroke like this, and, you know, what is a cube, right?  This was terribly inaccurate. So we're in this interesting paradoxical situation where we know how to do something, but we don't know how we know. Another great example of this is, you know, just riding a bike, right? You know how to ride a bike. Can you program a computer to ride a bike? If you figure that out, tell me, because I want to steal your idea and publish it under my own name, right? It's much easier. So here's the paradox that it's much easier to ride a bike than it is to program a computer to ride a bike, because your brain is very powerful. Deep in the, you know, lower layers of your brain, particularly in the case of things like riding a bike, it's actually, you know, your brainstem that's doing a lot of the work.  So there are many, you know, driving the cars is another example, right? So there are many applications where people know how to do it, but we don't know how to program it. In many ways, this is an ideal problem for supervised learning, right? To generate our supervision by having people do it. In fact, a lot of the only cars that drove themselves, this is exactly what happened, right? You just had a car, right, and the camera pointed at the road, and the person was driving the car, right? And this is the supervision, right? At the end of the day, we have a video of the road and we have a record of which way the person, you know, turned the wheel. And this is our supervision, right? So if people know how to do it, they can give a supervision. Same thing with character recognition, right? There's a lot of these character recognition datasets. From the post office, right? They're obviously big consumers of this technology, right? And by the way, if it wasn't for machine learning, sending a letter would be a lot more expensive, right? Because there have to be people figuring out what the address is. But the way these algorithms were trained was by actually having, you know, characters labeled by people. That wasn't very hard to do. And then the machine learning actually figures out how to do it. So this can be that. So that's the second class of applications for which supervised learning can be good. But that's not the end of it. Here's another case, right? Which also occurs very often. Suppose that, yes, people know how to do it, and yes, they know how to program it. The problem is that it's not cost effective. Because, for example, the thing that you're trying to learn is changing every day. So if you're going to hire someone to program it, like they have to be programming it every day. And in fact, it might take them more than a day to programming it, at which point, you know, it's already out of date. People have all sorts of rules about how to predict the stock market, but they don't really work. The models that work really change, you know, in some cases, depending on the type of investment, it could be on a day-by-day basis, or a week-by-week basis, or whatnot. In this case, again, it might be a good idea to use machine learning. Finally, you know, in some sense, this is another version of the same thing, but let's suppose things do not change very rapidly. Like, they're very fairly stable. Like, for example, your taste in movies, or your taste in books, right?  They have a recommendation engine that says, oh, people who bought these books, you know, also bought these. They need one of those for every customer, for every user out there. Okay? Your tastes are stable, you know?  There's, I don't know, 500 million people or whatever, I use Amazon.  That would cost more than the money they'll make from selling you the books. And by the way, like, it really contributes to Amazon's bottom, and I forget what the statistic is, but, like, a large percentage of their sales come from the recommendation engine. So this is definitely a really, you know, useful technology, but if they had to hire someone to go and model your tastes, you know, it would be a big money loser. So the lesson here is, even when people know how to do it, if you need to do it in a very large number of cases, like, for example, one for every person, then it's probably not cost-effective to do it, you know, manually, but machine learning can do it, right? Amazon has your click stream on their website, or, you know, Walmart, another big consumer of these things, has, you know, your record of the things that you bought every time you went to Walmart, and from that, they can try to figure out what you like to buy and, you know, what they should put on the aisles and then what not. Questions? Okay. Okay. So there this in mind when you're considering machine learning for an application, right? If your application doesn't fall into these things, and if it doesn't have the characteristics that you don't always have to be completely right, probably not a good idea if it's machine learning. For example, you probably don't want to use machine learning to design a network protocol, right? It's a very complicated and intricate thing, and if you get one step wrong, the system breaks. Okay. On the other hand, you know, I don't think it's being used for things that I didn't think it was good for, so, you know, I wouldn't be surprised if tomorrow there was a network protocol designed by machine learning, or maybe there is one already, so. But in any case, it's good to bear these things in mind. Okay. All right. So what is the inductive learning program? How is it hard, and how can we solve it? Before we dive into the details of different algorithms and their different strategies and whatnot, let's look at this problem in the simplest form that we can. So here it is. I'm trying to learn a Boolean function, y, and it's a function of four Boolean inputs, x1, x2, x3, and x4. Okay. So this black box here is the Boolean function. All right. This is my goal, is to figure out what that function is. If I figure out what that function is, then tomorrow when a new set of x1 to x4 inputs comes along, I apply the Boolean function, and I get, hopefully, the same result as the real function. Okay. So this is the goal. Now what do I have? What I have is examples of the function. So here's a table with examples of my function. For example, my first example says that when x1 is zero, and x2 is zero, and x3 is one, and x4 is zero, then y is zero. Okay. So I have seven examples. And now, of course, my job is to induce what the value of the function for the other examples is. Okay. All right. Over to you. How would you solve this problem? Let's see your suggestions. Maybe you'll come up with right here right now new machine learning only that no one has thought of. So how would you solve this problem? Don't worry about it being a sophisticated solution. We're not going to look at sophisticated solutions to anything today. So can you think of a simple way to solve this problem? If else? Sure. If else, say what? Effect conditions on variable values. Absolutely. So in fact, this is what we're going to be looking at very shortly. But be a little bit more specific about that. So that's your language, right? But now how would you learn statements in that language? How would I learn it automatically? Yeah, exactly. By building decisions? Okay. So here's the thing that's going to happen. Think of each example. Okay. So for example, I could say if X1 is false and X2 is false and X1 is true and X0 is false, then Y is false. This is an if-then rule. Then I could have one of these if-then rules switch to these examples. These seven rules get all these examples correct. Is this a good solution? It might be good enough. This is the whole problem. Is that this is not a good solution? Yeah. So I was going to say, wouldn't that kind of be overfitting the data if you keep all of them possible? This would actually be maximally overfitting the data or maybe you could say that this would be the passable solution, like the opposite of what we want. The problem with this is that such a solution would only tell me what I already know. I don't need those rules for that. I have the examples to tell me that. Remember, the goal in learning is to learn a function that I can apply to new examples that I haven't seen before and get those right. What would happen with this solution on a new example? It wouldn't match any of them, right? I only have rules for the examples that are already there. This would be completely useless on new examples, yeah. So what if we try to find the closest to a new item? Say, I already know seven of these and I get a new one and I try to guard some kind of a distance between what I already know and the new one. So this is the type of strategy that we can use. And now a question that we can get. We can just have a very large... Instead of saying, let me just do a bunch of random operations on these things and whichever sort of operations actually fits all this data. This is a good strawman, actually. Why not just do something random? We could. The thing is that something random might not be that good. In a way, what we're trying to do here is better than random. Chances are random will basically be as good as flipping a coin, meaning you classify half of your spans and non-spans and so forth. We give you about half the time, right? No, but if being right half the time is good enough, then great. But you probably want to be right more than half the time. By the way, notice the following. Let's say you have a problem with 10 classes, each of which occurs 10% of the time. Being right half the time is a brilliant achievement. Because by flipping a coin, you only write 10% of the time. So sometimes being right half the time is amazing. By the way, on the stock market, when you're trying to predict what the stock is doing up or down, being right half the time is not good enough, but being right 51% of the time is great. If you can reliably be right, because you can do many trades even per second. If you reliably write 51% of the time, you can make money. I'm oversimplifying a little bit, but if somebody says that they write 60% of the time, they're lying or they're doing something wrong. In the stock market, 60% is out of reach. But 52%, hey, you know, you could be on the way to great reaches with 52%. Yeah. I have a question here. I was just looking at, for example, whenever X2 is 1, the output is 0. So while coming up with the model, do I need to have some intuition about what the relationships between them are? Because that may be a good relationship. Very good. So first of all, this is where having any kind of knowledge about the problem can help, right? You bring that to bear and you start to see. The other one is that that is exactly the kind of rule that we're going to be looking for. Aha, look, this too is predicted with the class being 0. It's not the whole answer, right? But we're not going to try to come up with the whole answer all at once. We're going to try to build it out of these pieces. Yeah. I think it's just an approach to how you do this. So you have to have a weight or something assigned with each of the inputs. So the probability, if this input is 1, the probability that the output y is 1, and then you somehow do some function of all of those, and if the total is above some threshold, then you decide that y is 1. Absolutely. See, you have just invented the naive base classifier. I've done it with a machine before. There you go. So you didn't invent it. Ah, darn it. OK, so naive base is actually the foundation of spam filtering, right? At least we don't know, because they don't say it for obvious reasons, right? But at least in the beginning, most end filters were naive base and naive base. Most of them still are naive base with a lot of things on top of it. But yeah, this is the basic idea of the naive base algorithm, right? For each of these x's, you compute how good of a predictor of why it is, and then you combine them all. And then we will see more detail how to do this. Very simple strategy, but actually very effective for a lot of things. OK, so here's another way to look at this problem, OK? Or, you know, continue with the same way. That was what I had. But now let's look at it. We're never going to be able to do this again. That's why we're doing this in a small example here. I can actually look at the table of the whole function, right? Because it's only four Boolean inputs, right? So it doesn't have that many states, OK? So now what I've done here is like this table is the standard that I have on the previous slide, right? OK, those examples are still there, right? But in addition, I put in here all the other possible examples, OK? Except that the ones that are not in my training said I have a question mark for. So for example, I've never observed 0, 0, 0, 0, so I have that with a question mark, OK? And the problem that we're trying to solve here is just this. I want to fill in those question marks, OK? This is my problem. What do I put where those question marks are, OK? And here's the first important thing to realize. It's a really basic thing, but it's very important. And even machine learning excerpts can get it some other time. You can put any darn thing that you want in there, right? If you don't know anything about your problem, just the data doesn't get you there, right? Machine learning is all about the data, but the first lesson is the data's not enough. You need something else, right? With just the data, right, I know the values for the examples that I've seen, like, you know, this and this. But yeah, there's, you know, like somebody said, do it randomly, flip a coin for each one of them, right? How do you know that that's going to be worse than anything else, right? You have your super-specified classifier technology. Why should that be randomly guessing? The reason, and in practice, however, we do have super-specified classifier technologies that does be randomly guessing most of the time. But this is because it embodies something about the problem that actually turns out to be right for the problem, okay? So the first lesson is that if you're in a state of complete ignorance, you can't do better than random guessing. You have to bring in something else, right? Going back to the gardening analogy, right? Complete ignorance is like having all the nutrients but no seed. Well, you can have all the water and, you know, nitrogen and whatnot in the world that you want. No seed, no plant, okay? This is the first important thing to remember. The next thing is, actually, in this example, right, we're going to be able to do another thing that we're never going to be able to do again, which is this example is so small that, you know, this question that I asked, like, you know, how you're going to, so how would we come up with those, say, if there are rules, right? In this case, actually, we can just try all of them, right? In general, we're never going to be able to do it because there's way too many, right? But this is actually the small enough case that we could actually try all the rules, right? And there's another lesson here which is, like, in this case, right, I have, there are 16 possible examples, right, four variable 16 examples, right? I know seven of them. There's only nine that I don't know.  In this case, it's not a bad thing to have. It's almost half. But in real examples, right, you've seen a billion email messages. How many possible email messages are there? Ten to the who knows what, right? That those billion are infinitesimal. It will be, like, in this table only knowing one example. And that is still an overstatement, right? You're going to, you will have seen 1% of 1% of 1% of the things that you could see.  You'll be lucky, actually, if you ever see one of those exactly ever again in many cases, okay? So we need something better. And now notice the other interesting thing here, which is I have four variables, right? So I have two to the four states, right? So four variables, right? Two to the four states, right? IE, 16 states, right? So how many functions are there? How many possible functions are there? Of 16 Boolean inputs. Oh, yeah, I know. People didn't answer? Two to the 16th. So generally, right, if you have, let's say, n dimensions, right? You have two to the n possible states, right? One for every combination. And then each of those states you could label with two or false, right? So you have two to that, right? Everybody got that? This first two to the n is the number of states. And then the number of functions is two to the number of states, okay? So look at this shocking thing that I just put here. This is two to the two to the n. This is a doubly exponential function. Now you've all heard how easy problems in computer science are polynomial and the hard ones are exponential, right? We in machine learning will laugh at those people who say NP-hard problems are hard, right? Those are ridiculous, right? We're not just dealing with an exponential, we're dealing with a double exponential, right? And when you're writing a program, you know, if you have four inputs, you have to choose among 16 things. If you're trying to learn the function, you have to deal with two to the two to the four. It's an exponentially harder problem, right? So yes, you know, there's a reason machine learning, you know, hasn't been done from the early days of computer science, right? This is the problem that we're faced with. It's this double exponential, right? Even if your number of dimensions was small, this would be, you know, really tough. Imagine now when your number of dimensions, instead of being four, it's like, say, a thousand, right? Now you have two to the two to the thousand, right? The total number of subatomic particles in the universe is an infinitesimal thing compared to that, okay? So the bottom line is brute force is never going to work, okay? And this is why generalization is important, right? Because the part that you've seen compared to what you're going to see tomorrow to what you could see is infinitesimal, okay? Questions? These are simple things, but this is really what underlies, you know, all the algorithms that we're going to be dealing with is this, this is the nature of the problem, right? This is also, in many ways, very different from other things in computer science. Okay, so that's the following, right? The space is too large, right? Let us just pick a language, right? Let's pick a type of rule, right? And then just, in this case, try them all, right? Let's see what happens. Again, this problem is small enough that we can try that. We're not going to try all possible Boolean functions, right? Even that is a lot, although in this case we could try it, right? To sort of make this half realistic. Let's pick a restricted set of rules or a restricted class of rules and use those, okay? So, you know, let's take your suggestion and just use, you know, if-then-rules, okay? Let us just use if-then-rules of the form, you know, ifx this and x this and x this, then the class, okay? So, for example, this first rule says that if nothing, then the class, meaning that, you know, every example is-you don't test anything, every example is true, right? Well, if you go looking-and now what we're going to do is like this is what's called generating test, right? We're going to create all possible rules of this form and we're going to test everyone against the training set, right? And if there's a counter-example, we know it can't do the right rule, we throw it away, right? And we're going to do this until we find one rule that really does hold for every example in the dataset and then we can declare victory, right? Because, you know, we don't need that, right? So, we do that and then we try, for example, if x1 is true, then y is true, right? Meaning that y is true exactly when x1 is true and false exactly when x1 is false. Is there a counter-example to that? Well, unfortunately, yes, there is. So, this one fails. We try all of those, they fail. Now, we try combinations of two. Let's say, you know, if x1 and x4, then y. Well, there's also a counter-example to this one. And then we try combinations of three. All of those have counter-examples. Finally, we try all four of them. If x1 and x2 and x3 and x4, then y. There's also a counter-example to this, okay? More of the story. I picked the wrong hypothesis class, right? My hypothesis class was nice because it was small. On the other hand, it was so small that it didn't have the right answer, okay? So, this class doesn't work, all right? Well, let's try another. How about, here's a very popular and useful class. People use it a lot in medical diagnosis, for example. Real human doctors use rules of this type. These are so-called M-of-N rules. M-of-N rules are, there's these five symptoms. If you have at least three of them, then you have pneumonia, okay? Because, you know, medical diagnosis isn't cut and dried, right? But what they do is a balance of evidence. There's these things that kind of are indices of syn pneumonia. Often, you don't have all of them. But if you have at least three of them, then you probably do have it, okay? And, you know, the same thing can be used for lots of other problems. They also have the advantage that they're simple. And, they're more powerful than just simple if there are rules that just test the values of specific variables. So, let's try those M-of-N rules. So, first of all, let's try the rule one out of X1. You know, and this one, you know, you can do only one, of course, because there's only one variable. Is there a common example? Yes, there is. One of everything, there's a common example, right? So, all these fail, right? These all fail. Now, let's try one out of these two, right? One out of X1, X2, meaning that Y is true if either X1 is true or X2 is true or both, okay? Again, these all fail, right? There's common examples to all of them. Now, let's try two of them, which is actually just a conjunction, right? Those we already saw, they all fail, okay? But now, let's try, for example, one of three, right? This is new. Y is true whenever one of these three is true, okay? We try that, they all fail. Now, let's try two. This is getting more interesting, like I have three variables, and if two of those three are true, then Y is true. For example, if X1 and X2 are true, then Y is true, X1 and X3, X2 and X3, but, et cetera, okay? Nothing else. Well, lo and behold, one of these actually succeeds. There is no common example to this in the day. And now, we can try all the others, you know, three out of three, those fail, right? Again, this is basically just a case that we had before. One, two, three out of these four, those also fail. Okay, so at this point, we can declare victory, right? We postulated that, you know, this was an M of N rule, and there's only one that works, so that has to be the answer, okay? So at this point, we can declare victory and go home. But, you know, maybe you should be a little suspicious, right? What we just did here in microcosm is actually what people do when they run machine-running algorithms on stuff, with many more subtleties that we'll see later. They're hard. This is what's going on. And what can we learn from this? You know, let's take a step back and look at what happens here, right? And then look at maybe what is not quite right and should be done differently or better, right? One way to look at what just happened is the following. Is that in the beginning, I have complete ignorance, right? I don't know anything about my problem, okay? And then you give me a data set. Well, this is good to know, right? It's real information about the domain. But as we just saw, that real data set doesn't tell me anything about the examples different from the ones that I've seen, okay? So now I need one more thing. I need a piece of knowledge, right? But if I know, let's suppose that we really knew for real that the concept was an M of N rule, right? Then we could do the procedures that we just did and we would have gotten the right answer, right? So what happened with this is that each of these things removed some of our uncertainty. Having my data removed some of my uncertainty. But as we saw, it only usually removes a tiny fraction of the uncertainty because most of the examples remain unseen. And then I bring in my, I say, I assume or I believe or I know that this is an M of N rule. That removes a lot of uncertainty, right? It excludes all the possible CNFs that that concept could be, right? So that really reduces your uncertainty a lot. It cares a lot of information, but not completely because there's still a whole bunch of M of N rules that you don't know which one it is, right? But now, when you combine that rule with the data on a good day, lo and behold, the right answer comes out, okay? So one way of looking at this is saying what is learning, it's removing your uncertainty, right? The data itself is not enough. Your knowledge of the, let's say that you start with the knowledge that it's an M of N rule, right? That is not enough. But that, plus the data on a good day will remove your uncertainty and then you'll be left with the right concept, okay? This is one way to look at learning, okay? Another way to look at it is the following. Well, gee, you know, you really got lucky here, right? We just, we have like this random Boolean data set. We didn't know most of the examples and we postulated that this is an M of N rule. Great, right? What are the chances of that actually being the case? Right? Well, notice this loaded word here. Learning requires guessing a good small hypothesis class. There is always guesswork involved in learning. Some people are not comfortable with that, right? They like the certainty of, I just build this deterministic program and they know that it does what it needs. To do machine learning, you have to be comfortable with the notion that it's guesswork and you're not always going to be right. If in your application you always have to be right, it's unlikely that machine learning is a good solution. On the other hand, if your application is a search engine and people will keep using you even if half the stuff that you return is crap, this could be a good, you know, problem for machine learning, okay? This also means that your ability to make a good guess is very important, right? If I can guess a small class that actually contains the right answer, then the data will do the rest of the job, right? So one way to look at learning is, you know, it's like the cleanest woodwork, right?  He's been chasing this guy, you know, throughout this warehouse. They've been shooting at each other, you know. And finally, the guy, you know, is down on the floor and then his gun is like a yard away and he's trying to decide whether to lunch for the gun or not, right? And Clint Eastwood comes up to him and points his gun at him and says, well, do you feel lucky today or don't you? Right? Because if he feels lucky, he can lunch for the gun but maybe Clint Eastwood has run out of bullets, right? They haven't been counting how many bullets they have.  On the other hand, if he does still have bullets, right, then he could get shot. So in the movie where this is being Hollywood, of course, you know, the guy lunches for the gun and, you know, Clint Eastwood still has a bullet and kills him, right? But the key thing is that, like, there was an element, there's an element of gambling. It's informed gambling, right? It's not completely random, but you have to do that. That element is always present in machine learning. It would be nice if we have the city, you know, if you think about it, if you already knew the domain with certainty, well, then you don't need data, right? Your program, okay? So when you're doing machine learning, it's almost always the case that, you know, things about the domain, right? You suspect that maybe this is the case, maybe that is not, and then you have a lot of data. But at the end of the day, you need an element of luck. When we do the theory part of this class, you'll actually see that, you know, just because you need luck doesn't mean you have to be completely in the dark. You can play the odds. You can be smart about how likely you are to be writing and whatnot, right? For the moment, you know, we'll pursue a more empirical approach to this, and the theory also has its limitations, but nevertheless, you're not completely taking a shot in the dark. However, the main lesson is you're going to be able to, you're going to have to make some guesses, and your ability to make those guesses as well is going to be crucial to success. This is part of why machine learning is fun, because it's not, machine learning is not just turning the crank on a large dataset.  This is a very important component. Quick question, real quick question on that. The fact, I'm going to try to figure out a phrase that makes sense, the fact that you need this kind of domain knowledge to guess hypothesis class, does that mean that we should have some skepticism about whether machines can ever initiate machine learning, like the human gardener will always have to be there at the end of the day? Well, this is a great question, right? So notice the following, that in machine learning part it's similar to, well, the humans are there doing some of the work. The machines have not taken over yet, right? You know, Rick Kurzweil says that that's going to happen soon, but most people don't believe it, right? Nevertheless, so, we are bringing something to bear, right? But just think about the following for a second. Evolution that produced us is a learning process, right? Evolution started out knowing nothing, right? We were all amoebas, or we were all, you know, bacteria or whatever, right? So somehow that learning process, you know, actually produced us, right? Evolution is a big data problem, right? You know, the big data is all these creatures exploring the world, right? So there has to be something, some regularity in the world that we can explore, right? And what you want to do is hopefully encode this into your algorithm so that you don't have to put them there yourself, right? The other side of this, right, is that, well, you could be wrong, right? You could be wrong even if things seem to work out. Look at this here, right? Hey, I postulated that it was an M of N concept and I found only one that fit. Does it mean I should go home happy? Not really, right? Because if you think about it, there's other things that would work here, right? So for example, the rule, you can check this yourself, you know, at home. The rule X1 and not X2 implies Y also works. So which one is it? If this is the true one and we guessed the M of N one, we'll get all our stuff wrong, right? So we could be wrong. And you can never be sure that you weren't wrong. In some cases, you can have high confidence that you were right, but you can never be sure that you were wrong, that you were right, okay? You could always have been wrong and you have to be comfortable with that, okay? However, notice the following. There's a trade-off in the size of the hypothesis class. The smaller I make the hypothesis class, right? The more information is encoded in that the lower the burden that it has to bear, the easier the problem becomes. On the other hand, the more things I throw out, the less likely that the right hypothesis actually will be in that class. So in a way, you want to make the hypothesis very small to make the learning easy. On the other hand, you want to make it very large to make sure that the right answer is in there and there is an inevitable tension between these two things, okay? In practice, how do people deal with this tension? By trying successively larger sets of hypothesis. I start out trying something very small. If that works, you know, looking pretty good. If that doesn't work, then I try a larger set and a larger one, just like we did with if, then, rules in the name of end concepts, okay? The larger the set that I tried, the less I'm going to be sure that I found the right answer. Right? Because I need less luck to have found the right answer, okay? Nevertheless, it's very good to have that ability to try successively larger hypothesis sets. And this is exactly what many algorithms do. In particular, the decision tree learners work that way. As we will see next week, they start out trying very small hypotheses, very small trees. If that doesn't fit the data well, then they try larger trees and larger and larger until they either fit the data well or they decide to stop earlier to avoid other things. Questions about this? Okay. So, out of these two observations come two strategies for the machine learning. And, you know, we're going to see them in action in the coming weeks in a bunch of different ways. One of them is, since it's so important to express and use prior knowledge to make our learning easy, one of the things that we should have is languages in which it's easy to express the kind of prior knowledge that we have, right? And in fact, for example, something that is popular in some quarters is, I'm going to allow rules with only a particular syntax on the antecedents. I'm not going to allow any antecedents. I'm going to allow antecedents that obey these rules. For example, I might know that, you know, certain variables cannot appear negated because they're positive indicators of the class. This is a common thing, right? These are useful restrictions to have. We want to have languages in which it's easy to say those things. And in fact, one of the main criteria for choosing representation is which representation makes it easy to encode the knowledge that you have. I've never seen this in the textbooks, unfortunately, but this is actuall