The Master Algorithm | Pedro Domingos | Talks at Google

Welcome everybody to one more Authors@Google talk. Today our guest speaker is Pedro Domingos, whose new book is called The Master Algorithm. We have it here and you can buy copies outside. So one definition of machine learning is the automation of discovery. Our guest Pedro Domingos is at the very forefront of the search for the master algorithm, a universal learner capable of deriving all knowledge, past, present, and future from data. Pedro Domingos is a professor of computer science and engineering at the University of Washington. He is the co-founder of the International Machine Learning Society. Pedro received his MS in electrical engineering and computer science from IST in Lisbon. his Master of Science and PhD in Information and Computer Science from the University of California at Irvine. He spent 2 years as an assistant professor at IST before joining the faculty of the University of Washington in 1999. Pedro is the author and co-author of over 200 technical publications in machine learning, data mining, and other areas. He's the winner of the SIGKDD Innovation Award, the highest honor in data science. Thank you. He is an AAI fellow and has received a Sloan Fellowship, an NSF Career Award, a Fulbright Scholarship, an IBM Faculty Award, several best paper awards, and other distinctions. He's a member of the editorial board of the Machine Learning Journal. Please join me in welcoming Pedro today to Google.

Thank you. Let me start with a very simple question. Where does knowledge come from? Until very recently, it came from just 3 sources. Number 1, evolution, that's the knowledge that's encoded in your DNA. Number 2, experience, that's the knowledge that's encoded in your neurons. And number 3, culture, which is the knowledge you acquire by talking with other people, reading books, and so on. And everything that we do, right, everything that we are basically comes from these 3 sources of knowledge. Now what's quite extraordinary is just only recently there is a 4th source of knowledge on the planet and that's computers. There is more and more knowledge now that comes from computers, is discovered by computers. And this is as big of a change as the emergence of each of these 4 was. Like evolution, right, well that's life on Earth, it's It's a product of evolution. Experience is what distinguishes, you know, us mammals from, you know, from insects. And culture is what makes humans what we are and as successful as we are. Notice also that each of these forms of knowledge discovery is orders of magnitude faster than the previous one and discovers orders of magnitude more knowledge. And indeed the same thing is true of computers. Computers can discover knowledge orders of magnitude faster than any of these things that went before and that coexist with them, and orders of magnitude more knowledge in the same amount of time. In fact, Yann LeCun says that most of the knowledge in the world in the future is going to be extracted by machines and will reside in machines. So this is a major change that I think is not just for us computer scientists to, you know, to know about and deal with. It's actually something that everybody needs to, needs to you know, needs to understand. So, um, so it does, you know, so how do computers discover new knowledge, right? This is of course the province of machine learning, and, uh, in a way what I'm gonna try to do in this talk is, is try to give you a sense of what machine learning is and what it does. If you're already familiar with machine learning, this will hopefully give you kind of like a different, uh, you know, perspective on it. If you're not familiar with machine learning already, this should be, you know, uh, quite fascinating and, and, and, and, and interesting. So, uh, there are 5 main paradigms in machine learning, and I will talk about, you know, each one of them in turn and then try to stick back and see what, you know, what, what is the big picture and what is this idea of, you know, of, of the master algorithm. The first way computers discover knowledge is by filling gaps in existing knowledge, pretty much the same way that scientists work. Right? You make observations, you hypothesize theories to explain them, and then you see where they fall short and then you adapt them or throw them away and try new ones and so on. So this is one. Another one is to emulate the brain, right? The greatest learning machine on earth is the one inside your skull, so let's reverse engineer it. Third one is to simulate evolution. Right. Evolution by some standards is actually an even greater learning algorithm than your brain is because first of all it made your brain, it also made your body, and it also made, you know, every other life form on Earth. So maybe that's something worth figuring out how it works and doing it with computers. Here's another one, and this is to realize that all the knowledge that you learn is necessarily uncertain, right? When something is induced from data, you're never quite sure about it. So— The way to learn is to quantify that uncertainty using probability, and then as you see more evidence, the probability of different hypotheses evolves, right? And, you know, and there's an optimal way to do this using Bayes' theorem, and that's what this approach is. Finally, the last approach in some ways is actually the simplest and maybe even the most intuitive. It's actually to just reason by analogy. There's a lot of evidence in psychology that humans do this all the time. You're faced with a new situation, you try to find a matching situation in your experience, and then you transfer the solution from the situation that you already know to the new solu— to the new situation that you're faced with. Okay? And connected with each of these approaches to learning, there is a school of thought in machine learning. So the 5 main ones are, are the Symbolists, Connectionists, Evolutionaries, Bayesians, and Analogizers. The symbolists are the people who believe in, you know, discovering new knowledge by filling in the gaps in, in the knowledge that you already have. One of the things that's, you know, fascinating about machine learning is that the ideas in the algorithms come from all of these different fields. All right. So for example, the symbolists, they have their origins in logic, philosophy, and they're in some sense the most computer science-y of, of, of the 5 tribes. The connectionists, their origins are of course in neuroscience because they're trying to take inspiration from how the brain works. The evolutionaries, well, their origins are of course in evolutionary biology, right, in the algorithm of evolution. The Bayesians come from statistics. The analogizers actually have influences from a lot of different fields, but probably the single most important one is psychology. So, you know, in addition to being, you know, very important, you know, for our lives, And machine learning is also a fascinating thing, I think, to, to study because, you know, in the process of studying machine learning, you can actually study all of these, all of these different things. Now each of these tribes of machine learning, if you will, has its own master algorithm, meaning its own general-purpose learner that in principle can be used to learn anything. In fact, each of these master algorithms has a mathematical proof that says if you give it enough data, it can learn anything. Okay? For the Symbolists, the master algorithm is inverse deduction, and we'll see in a second what that is. For the Connectionists, it's backpropagation. For the Evolutionaries, it's genetic programming. For, for the Bayesians, it's probabilistic inference using Bayes' theorem. And for the Analogizers, it's kernel machines, uh, also known as support vector machines. Okay? So let's see what just the key ideas in each one of these, uh, um, are. So the Symbolists, you know, here are some of the most prominent Symbolists in the world. There's Tom Mitchell at Carnegie Mellon, Steve Muggleton in the UK, and, and Ross Quinlan, uh, in Australia. And their idea is actually a very, um, interesting one. It's to think of deduction— sorry, it's to think of learning as being the inverse of deduction, right? Learning is induction of knowledge, right? Deduction is going from general rules to specific facts. Induction is the opposite. It's going from specific facts to general rules. So in some sense, one is the inverse of the other. And so maybe we can figure out how to do induction in the same way that people in mathematics figure out how to do other inverse operations. Like, for example, subtraction is the inverse of addition, or integration is the inverse of differentiation, and so forth. So, you know, as a very, very simple example, right, addition gives you the answer to the question, if I add 2 and 2, What do I get? Right? Subtraction— and the answer of course is 4. And this is the deepest thing I'll say in this whole talk. And subtraction of course gives you the answer to the inverse question, which is, what do I need to add to 2 in order to get 4? The answer of course being 2. Now inverse deduction, right, works in a very similar way. Right? So here's a simple example of deduction, right? You know that Socrates is human and you know that humans are mortal and the question is what can you infer from that? Well, of course the answer is that from that you can infer that Socrates too is mortal. Okay? Now the inverse of this, and that's when it becomes induction, is if I know that Socrates is human, what else do I need to know in order to be able to infer that he's mortal? And of course what I need to know is that humans are mortal. And so in this way I have just induced a new general rule that humans are mortal. Of course in general I wouldn't just do it from Socrates, I would do it from Socrates and, you know, and a bunch of other people, but that's the general way that this works, okay? And then once I've induced rules like this, I can now combine them in all sorts of different ways to answer questions that I may never even have thought of. And this kind of flexibility and compositionality is actually something that of all the 5 tribes only the symbolists have. Now, of course, these examples are in English and, you know, computers don't understand natural language yet. So, so what they use is something like first-order logic, right? So these things, both the facts and the rules that are discovered, are, are represented in first-order logic and then questions are answered by, by chaining those rules, by reasoning with them, okay? So, but whether it's in logic or natural language, the, the principle is the same. Okay. And as I said, of all the 5 paradigms, this is the one that is most like scientists at work, right? They figure out like, where is the— you know, what are— where are the gaps in my knowledge? Let me, you know, enunciate a general principle that will fill that gap, and then let me see what follows. Let me see if it's correct given the data. Let me see what gaps I then find, and so on. And in fact, one of the most amazing applications of inverse deduction to date is actually a robot scientist. So if you look at this picture, the biologist is not the guy in the lab coat. The guy in the lab coat is actually a computer scientist and machine learning researcher by the name of Russ King. The biologist in this picture is this machine here. This machine is a complete automated biologist. It starts out with basic knowledge of molecular biology, DNA, proteins, RNA, and all of that stuff. And then what it actually does is it formulates hypotheses using inverse deduction. It designs experiments to test those hypotheses using things like DNA sequencers and whatnot. That's what's on there. It physically carries them out, right? So it does the whole process with no human help. And then given the results, it refines the hypothesis or comes up with new ones and so on. Okay. Now there is only one of these robots in the world today, its name is Eve. There was actually a previous one called Adam. And Eve last year discovered a new malaria drug. And the thing that's amazing about this is that, well, once you've made one robot scientist like this, there is nothing stopping you from making a million. And now you have a million scientists working on a problem where before maybe all you could afford was a few, okay? So this can really speed up the progress of science. And I would say that in areas like molecular biology, there is no hope of really understanding, for example, you know, very well how cells work without, without this kind of thing, right? There's just too much information for, you know, for human beings to, to discover on their own. Okay? Now, this is one very, uh, I think attractive way to do machine learning, but of course it's not the only one. In particular, the connectionists are very skeptical of it. They say, well, this is too abstract, it's too clean, you know, it's too rigid, logic is not how the real world works. Right? You have to do things more like human beings do. And of course, you know, the way human beings do things is with their brains, so let's figure out, you know, how brains work, at least enough that we can take inspiration from them and build algorithms based on that. So this is what the connectionists do. The most prominent connectionist is Geoff Hinton. He actually started out as a psychologist 40 years ago, and now he's really more of a computer scientist. And, and, you know, he's been incredibly determined in his goal of understanding how the brain learns. In fact, he tells this story that one day he came home from work very excited, you know, saying, yay, I've done it, I figured out how the brain works. And his daughter replied, oh, Dad, not again. And, you know, and he's the first one to say that he's had some successes and failures, but I think the bottom line is that these days, you know, for example, he's one of the co-inventors, of course, of backpropagation. Uh, the successes far outweigh the failures, right? So definitely this sort of like long-term research agenda has already given a lot of fruits and, and it's going to give more, right? And 2 other prominent connectionists are Yann LeCun and Yoshua Bengio. Of course, connectionism, you know, is also known as neural networks and these days as deep learning, uh, but it's really all the same paradigm, okay? So, so how does it all work? Well, what we're gonna do is we're going to build a model, A mathematical model of how a single neuron works. We're going to make it as simple as we can, provided it's enough to learn and to do, you know, the inferences that we need it, you know, to do. Okay? And then we're going to put these neurons, these models of neurons together into big networks, and then, and then we're going to train those networks. Okay? And at the end of the day, what we have is in some sense a miniature brain, if you will. Okay? Of course, much simpler than the real one, but hopefully with some of the same properties. Okay? So now a neuron, right, is a very interesting kind of cell, right? It's a cell that actually kind of looks like a tree, right? There's the cell body and then there's the trunk of the tree is what is called the axon. And then the branches, you know, are called dendrites, right? And the— but where neurons get very different from trees is that the branch— the branches of one neuron actually connect back with the roots of another. Or in fact with the roots of many others, and that's how you get a big network of neurons, okay? And where the dendrites of one neuron join the dendrites of another, that's called a synapse. And to the best of our knowledge, the way humans learn, everything you know is encoded in the strengths of the synapses between your neurons, okay? So if the synapse is strong, then, you know— So let me backtrack for just a second. The way this works is that, you know, the neurons communicate via electric discharges down their axons. They're literally an electric discharge called an action potential. And what happens is that if you look at all the charge coming into a neuron through its various synapses, if it exceeds a certain threshold, then that neuron itself fires. And of course then it sends, you know, currents to the neurons downstream. Okay? And the synaptic process itself involves chemistry and whatnot, but those details don't, you know, are not important for us. Okay? So, so what's going to happen is that, you know, the, the, the learning basically happens when a neuron helps to make another neuron fire. And then the strength of the connection goes up. This is, you know, this is, this is called Hebb's rule. Okay? And as far as we know, this is how all our knowledge is encoded, is in how strong the synapses are. If the neurons fire together a lot, then the synapses become stronger and it becomes easier for the first neuron to fire the second one. Okay. So this is the basic idea. And now what we have to do is, you know, first of all, turn it into a model. That's not that hard. So the model is just this. What my neuron is going to do is it's going to do a weighted combination of the inputs. Okay. Let's suppose, for example, that this was actually the retina, right? So this is the input, you know, each one of these inputs is a pixel. And then each one of them gets multiplied by a weight that corresponds to the strength of the synapse. And if that weighted sum exceeds the threshold, then I get 1 as the output, otherwise I get 0. So for example, if this neuron is trying to recognize a cat, if this is a cat, then hopefully what happens is that this, this weighted sum will be high enough that this will fire and, and the, and the, and the, you know, and the neuron will say, yes, this is a cat. Okay? Now, this is all easy. You know, this, this goes back to the 1950s and Frank Rosenblatt and whatnot. The really hard and interesting and important question is, how do you train a whole network of these neurons, right? That's when things actually become very difficult. Because if you have a big network of neurons, like so here, you know, here are my inputs, they go to one set of neurons, right? These are the, the, you know, the, the, the functions that they compute, right? They're, they're in purple here. And then those go to another layer and many, many layers until finally you get the output. Another question is, well, if the output is correct, right? So let's say this, this was a cat, and the network said that yes, it is a cat, then life is good, right? Nothing needs to change, right? Why go fixing what ain't broke? But what happens if there was an error, right? This should have been firing but wasn't. And now the key question is like, what do I change in that whole big messy network to try to make it, you know, give the right answer tomorrow? There is no obvious answer to this question because, you know, think of one neuron, you know, somewhere in the middle of the network. How is it responsible for the error at the output? Right? The error, the error at the output could have come from an infinity of different places. This is called the credit assignment problem, or maybe it should be called the blame assignment problem because it's deciding who's to blame for an error and therefore needs to change. And this is the problem that backpropagation solves. Right. And when people first came up with, with, you know, with, with sort of like neural networks in the '60s, they didn't have this. It was when, when finally it was, you know, invented, uh, in, in the, in the '80s, you know, by, by David Rumelhart and others that, that things really took off. And the basic idea in backprop is actually, you know, um, quite intuitive, I think. It's the following. Well, let's think of the difference between my actual output and my desired output. Let me call that delta, right? This is the error. The output should have been 1, but it was 0.2. Okay? So it needs to go up. Another question is like, what can I tweak, right, in these weights to make it go up? Right? Well, a weight that is, you know, thinking at this last layer, right? Uh, well, at that last layer, like the neurons with the highest weights are the ones most responsible for the result, right? And if, you know, if this neuron is saying no but the answer is yes, well, then its weight needs to go down because it's preventing it from firing. And, you know, if this one actually, you know, if this one was saying yes and, and, but, but this is not firing, then its weight needs to go up. Okay? So what I do is like I compute the derivative of this error with respect to, to the weights, in the last layer. And then with those, I now have an error signal coming from these neurons. It's like, oh, you should have been higher, right? You should have been higher in order to make this guy fire because you have a positive weight. You should have been lower because you have a negative weight and you're preventing it from firing. So now I know an error signal at, at, at the neurons at this layer. And I can keep doing the same thing all the way back to the input. And this is why it's called backpropagation because what I'm doing is I'm propagating back the errors, And then updating the weights, changing the weights in order to, to make that, you know, that error as small as possible. Okay? Well, this is the backpropagation algorithm. Uh, it's what's at the heart of deep learning. And, you know, these days, you know, this is used for just about everything on Earth, right? Uh, you know, very early on people used it to do things like predict the stock market. These days you use it, you know, for search, use it for ad placement, use it for video recognition, use it for speech recognition. You know, you use it for things like, you know, simultaneous translation and whatnot. But, you know, I think at least for the public, the best-known instance of this is still Google's own, you know, famous Cat Network, right? Unfortunately, people think it's, you know, it got called the Cat Network by the journalists, right, because it happened to recognize cats very well. Actually, it wasn't an accident, right? This was all learned from YouTube videos, right, as you probably know. And, you know, people really like to upload, you know, videos of their cats, right? So there was more data on cats than on anything else. Right? But, you know, this— maybe it should be called the couch potato network, right? Because it's based on, you know, on watching a lot of video. And at the time, this was the biggest, you know, neural network ever built. It had, I think, on the order of a billion parameters, but of course these days there's much bigger ones and, you know, and they're continuing to grow. So we'll see. We'll see how far, you know, we can take this paradigm. Now the evolutionaries, they say, well, sure, but all you're doing is, you know, adjusting the weights, you know, on this model. You know, you're just tweaking the strengths of the synapses. Where did that brain come from, right? That in some sense is the bigger question. That brain was produced by evolution. So maybe what we really should do if we want to learn really powerful things is, you know, figure out how evolution works and we actually already have a good sense of how evolution works. There's a lot of details of course that are still to be understood, but at a high level we understand how evolution works. So let us do the same thing on the computer. And, you know, the first guy who really ran with this idea was John Holland, you know, he started in the '50s, '60s. And, you know, for a long time this whole area of evolutionary computing, you know, the joke was that it was John, his students, and their students. But then in the '80s things took off and a lot of people started doing it. You know, John Holland called what he did genetic algorithms, and then John Koza, you know, developed a more powerful version called genetic programming, which we'll see in a second. And Hod Lipson is, you know, one of the people who are doing very interesting things with, you know, with evolutionary learning these days, as we'll see in a bit. So what's the basic idea here? Well, how does evolution work? You have a population of individuals, each of which is described by its genome, okay? But in our case, in the computer, you know, the genome instead of being base pairs, right, instead of being DNA, it's just going to be bits, right? 0 and 1 in some sense are the DNA of computers. And then each of these individuals gets to go out in the world and be evaluated. It gets evaluated at the task that it's supposed to be doing. And the individuals that do better will have a higher fitness and will therefore have a higher chance of being the parents of the next generation, right? You get 2 very fit parents and you cross over their genomes just like you know, just like people do. And so now you have a child genome that is partly the genome of one parent and partly the genome of the other parent, the mother and father, you know, genomes, if you will, okay? And then you also have random mutation, right? Some bits just get randomly mutated because of copying errors or whatever, and then you have a new population. And what's remarkable is that you could actually start out with a population that is essentially random, and after you do some number of generations of this, you actually have things that are doing, you know, a lot of non-trivial functions like, for example, you can evolve circuits that, you know, you can develop radio receivers and amplifiers and things like that in just this way. And they often work better than the ones that are designed by humans. In fact, people like John Koza, they have a whole bunch of patents that were actually, you know, the patent designs were actually invented by the genetic algorithms, not by the humans, okay? Now, you know, Koza's idea was actually to take this one step beyond, and that's the following. Well, you know, these strings are a very low-level representation, and, you know, just cutting the string in the middle to cross over is probably going to muck things up, right? We are trying to evolve programs, right? At the end of the day, that's what we're trying to do is evolve programs. So why don't we actually work directly with the programs themselves? And a program is really a tree of, you know, subroutine calls all the way down to simple operations like additions, multiplications, and ANDs and ORs. So let's look— let's represent the programs as trees, and then in order to cross over 2 programs, what we're going to do is we're going to randomly pick a node in each of the trees, and then we're going to swap the subtrees at those nodes. And now we have 2 child programs, okay? So for example, here, if I do the crossover at this point, then one of the subtrees that I will get is the one that's all in white. And this tree actually represents one of Kepler's laws. This is the law that gives the duration of a planet's year as a function of its average distance from the sun. It's actually a constant times the square root of the cube of the distance, and that's what this is representing. So genetic algorithms can actually discover things like this and much more complex ones as well. Okay. In fact, these days what the genetic folks are having a lot of fun with is something that's exciting and scary at the same time, is they're not just doing this with software anymore, they're not doing it as a simulation inside the computer, they're actually doing it out in the physical real world with robots. You literally start with robots that are random piles of parts, And then once those robots are good enough, they actually get, you know, printed by a 3D printer, and then they start crawling and walking and doing things in the real world, right, seeing how fast they can crawl, you know, trying to recover from injury and so on and so forth. This is actually a real robot from Hod Lipson's lab, okay? And then what happens is that in each generation, the fittest robots get to program the 3D printer to produce the next generation of robots. Okay. So, you know, so if Terminator comes to pass, this, this might be how we get there. Okay? Of course, these robots are not yet ready to take over the world, but they've already come remarkably far, right, from the soup of parts that, that they began with, right? And, you know, in these days if you see, you know, a little spider running around, you know, take, take a good look because it could be one of these instead of one of the biological ones. Okay. All right. So the Bayesians. So here are some famous Bayesians. Huda Pearl, you know, within computer science is probably the most famous one. He actually won the Turing Award, the Nobel Prize of computer science a few years ago, for inventing something called Bayesian networks, which is one very powerful type of Bayesian model where, you know, it's a big graph where each node is a variable and then the edges between the nodes represent dependencies between the variables. 2 other famous Bayesians are David Heckerman and Mike Jordan. Bayesians are known in machine learning as the most fanatical of all the, of the 5 tribes, right? They really have a near-religious devotion to their paradigm. And, you know, they're the first ones to say so. And I think the reason for this is that, you know, you know, Bayesians have their origins in statistics, and for 200 years Bayesians were a persecuted minority in statistics, right? So they had to become very hardcore in order to survive. And it's a good thing that they did survive because they have a lot to contribute. And these days, you know, with computers and, you know, algorithms like Markov chain Monte Carlo and, you know, and large data and whatnot, they're actually on the ascendant in statistics. So what is, you know, what is the basic idea behind Bayesian learning? Well, the basic idea is that, as I said, all— everything that you learn is uncertain. So what you have to do is compute the probability of each one of your hypotheses and then update it as new evidence comes in. And the way you do that is with Bayes' theorem, okay? And Bayesians love Bayes' theorem so much that there was this Bayesian machine learning startup that actually had Bayes'— a neon sign of Bayes' theorem made, and then they stuck it, you know, outside their office, okay? So it was like, you know, Bayes' theorem in, in, in big neon letters, okay? So how does, you know, how, how does Bayes' theorem work? Bayes' theorem is actually, you know, incredibly simple. It's so simple it's barely worth being— it would be barely worth calling a theorem if it wasn't so important. So the idea is this. So, you know, let's suppose that you have all your hypotheses, right? You define your space of hypotheses in some way. It could be, for example, the set of all Bayesian networks or the set of all, you know, neural networks or all decision trees or whatever. And now the first thing that you're going to have is a prior probability for each hypothesis. This is how much you believe in that hypothesis before you've even seen any data, okay? And this is actually what makes Bayesian learning very controversial is that many statisticians say, well, you have no grounds on which to just make up a prior. And the Bayesians' answer to that is like, you have— you have to make that up whether explicitly or implicitly, so, you know, let's just be explicit about it, okay? So the prior is how much you believe in each hypothesis before you see the evidence. But then what happens is that as the evidence comes in, you update the probability of each hypothesis. A hypothesis that is consistent with the data will see its probability go up. A hypothesis that is inconsistent with the data will see its probability go down, okay? And the consistency of the hypothesis with the data is measured by what's called the likelihood function, which is the probability of seeing the data if the hypothesis is true, okay? And this here is actually no different from, you know, frequentist statistics and the maximum likelihood principle, which is basically saying that if your hypothesis makes what you're seeing likely, then conversely, you know, what you're seeing makes your hypothesis likely, okay? And the Bayesians incorporate that in the likelihood. And the product of the likelihood and the prior is just the posterior, which is how much you believe the hypothesis after you've seen the evidence. So as you see more evidence, the probabilities evolve, and hopefully at the end of the day one, you know, hypothesis will come out as clearly better than the others, but being— but that won't necessarily be the case. You might still be entertaining a lot of hypotheses even after you've seen a lot of data, okay? There's also the marginal, which is just something that you have to divide by to make sure that the probabilities add up to 1. So, you know, let's not, let's not worry about it for now, okay? And a lot of great things have been done with, with Bayesian learning. Like for example, you know, self-driving cars have, have Bayesian learning in their brains. Okay? So, uh, you know, it's in some sense this Bayes' theorem, you know, like is, is helping to drive that car or, you know, help the car to learn how to drive and, and, you know, and, and without it, you know, it would be much harder. But, but one application of Bayesian learning that, that everybody's probably familiar with is, is spam filtering. The, the, the first spam filter was actually, you know, uh, uh, designed by David Heckerman and, and, and, and his coworkers. And they just use this very simple Bayesian learner called the Naive Bayes classifier. And the way it works there is the following. The hypothesis before I've seen evidence is that the email is spam or that the email is not spam, okay? And the prior probability is like, you know, your prior probability of an email being spam, 90%, 99%, 99.999%, take your pick, okay? And then the evidence is the actual content of the email. So for example, if the email contains the word Viagra, that probably makes it more likely to be spam. If it contains the word FREE in capitals, that makes it even more likely to be spam. And if that FREE is followed by 4 exclamation marks, that makes it even more likely to be spam, okay? On the other hand, if it contains the name of your best friend on the signature line, that actually makes it less likely to be spam, okay? And And so what the Naive Bayes classifier does is it incorporates that evidence and at the end of the day computes a probability that the email is spam or not spam, taking all of that into account, okay? And then based on the probability, you can decide whether to filter it out or, or actually show it to the user, okay? And, you know, we're all grateful that spam filters exist, otherwise our, our mailboxes would be unmanageable. These days all sorts of different learning algorithms get used for spam filtering, but, you know, but, but, Bayesian learning was the first one and, and it's still, you know, uh, used in, in many, uh, spam filters. Okay. Finally, the analogizers. So as I mentioned, the basic idea of the analogizers is that everything that we do, everything that we learn is reasoning by analogy. It's looking at similarities between the new situation that we need to make a decision in and the situations that we're already familiar with. Okay? And one of the early pioneers in this area was Peter Hart. Uh, you know, he proved some things, uh, related to the nearest neighbor algorithm, which we'll see shortly, which is kinda like the first, uh, you know, similarity-based algorithm. Uh, Vladimir Vapnik, uh, is the inventor of support vector machines, aka kernel machines, which is the most widely used and most successful type of, of, uh, uh, you know, similarity-based, uh, learner, but these are both actually still fairly primitive forms of analogical reasoning. There are some much more sophisticated ones that people like, for example, Douglas Hofstadter work on. And Douglas Hofstadter, of course, is also famous— he's not just a cognitive scientist and computer scientist, he's also famous as the author of Gödel, Escher, Bach, which ironically is actually itself an extended analogy between, you know, Gödel's theorem and the music of Bach and the art of Escher. And in fact, his most recent book is 500 pages arguing that all of intelligence is just analogy. So he really does think that analogy is the master algorithm. And in fact, the term analogizer was coined by him, okay? So let's see how this works. And I'm going to do it by proposing to you a very small puzzle. And the puzzle is this. Let's suppose you— I give you a map of 2 countries which I fancifully called Posistan and Negaland because of positive and negative examples. And I don't tell you where the frontier between the 2 countries is. I just tell you where the major cities are. So the major cities in Posistan are the plus signs. Positiveville is the capital. And, you know, and similarly for the negative cities. Okay? And now my question to you is the following. If I only tell you where the major cities are, can you tell me where the frontier, where the border between the 2 countries is? Okay? Of course, you can't know for sure, right? Because the cities don't determine the border, but that's what the machine learning problem is, right? You have to generalize. Now, the nearest neighbor algorithm has a very simple answer to this question. It just says, I'm going to assume that a point on the map is in Posistan if it's closer to some positive city than to any negative city. Okay? And the effect that this has is to divide the map into the neighborhood of each city, and then Posistan is just the union of the neighborhoods of the positive cities. The neighborhood of, of a city is the points that are closer to it than to any other city. Okay? And then as a result, you get this, you know, jagged straight line frontier. And what's remarkable about this is that even though the nearest neighbor algorithm is extremely simple, In fact, at learning time it doesn't do anything, right? It's an O algorithm. It just sits there, doesn't have to do anything, right? It can actually, uh, form very, very complicated frontiers. In fact, if you give it enough data, it'll converge very closely, uh, uh, you know, in fact, it'll converge to the best possible hypothesis that you could ever have if you use more than one neighbor, but let's not go into those, those details, okay? Now there's a couple of, uh, you know, things here that are not ideal. One is that this line is probably not quite the right one, right? Because the real frontier is probably smoother, it's not jagged like that. And another one is that if you look at this map closely, you could actually throw away some of the cities like this one, for example, and it wouldn't change anything. If you throw away this city, right, its area gets absorbed by the areas of these 2 other cities and the frontier doesn't change at all. The only cities that you need to keep are the ones that actually, you know, take part in defining the frontier, the so-called support vectors, right? In general, these are vectors in, in, you know, in hyperspace and they're called support vectors because they're the ones that keep the frontier where it is. So often you can throw away the great majority of, of your examples and, you know, that doesn't change anything. Right? And of course, in this example, this doesn't matter, but when you have, you know, a dataset with millions or billions of examples, that does matter. Okay? And support vector machines or kernel machines for short, uh, solve both of these problems. So they actually, you know, they have a learning procedure that lets them throw away all the examples that are not necessarily to define the frontier, so they leave only these. And they also make the frontier smoother. And the way they draw the frontier is by saying, Well, let me try to walk from south to north while keeping the positive cities on my left and the negative cities on my right, but I want to always stay as far as possible from them as I can. Okay? Think of the cities as mines and think of this as a minefield, right? If I told you to walk, you know, all along a minefield, you would try to give each mine, you know, the widest possible berth, right? You would try to maximize your— your margin of safety, and that's exactly what, what support vector machines do is that they maximize the margin between the frontier and, and the, and the nearest examples. Okay. And, you know, in the days before deep learning took off, support vector machines were the most, you know, uh, um, probably the most powerful, you know, type of learning that was commonly used. Okay. All right. Um, let's look at one application of this. Right? Again, this type of analogy-based learning, you know, people have been doing it since the '50s. But, you know, so it's used for, you know, just about everything on earth. There is, however, one application that, you know, that I think everybody has experienced even if they don't know it's an application of analogy-based learning. And that is recommender systems, okay? So for example, let's say that I want to figure out, you know, what movies to recommend to you. Right? The idea that folks had like almost 20 years ago now was a very simple one, is let me not try to do that based on the properties of the movie because that's hard, right? People's tastes are very complicated things. What I should do is what is called collaborative filtering, is find people who have similar tastes to you, meaning they gave 5 stars to a movie that you gave 5 stars to, they gave 1 star to movies that you gave 1 star to, and now if they gave 5 stars to a movie that you haven't seen, then I'm going to hypothesize that by analogy, right, you will also like that movie and so I will recommend it to you, okay? And this turns out to work spectacularly well. It works so well in fact that 3/4 of Netflix's business comes from its recommender system. And Amazon also has a recommender system, you know, about a third of its business comes from its recommender system. And, you know, and every e-commerce site worth its salt has something like this. Of course, these days people use all sorts of different, you know, learning algorithms for it, but the first one was, was this kind of like, you know, nearest neighbor type, type method. And it's, it's still, you know, one of the best, okay? So stepping back, we've met the 5 tribes of machine learning. We've seen that each one of them has a problem that it can solve better than all the others. And it has a, a particular master algorithm that solves that problem. So for example, for the, the sim— the problem that the symbolists solve that none of the others know how to solve is the problem of learning knowledge that you can compose in many different ways. Okay? And they learn that knowledge with inverse deduction as we saw. Connectionists solve the credit assignment problem using backprop. Evolutionaries solve the problem of learning structure, right? The connectionists just start with a fixed structure and just adjust the weights. The evolutionaries know how, know how to come up with that structure in the first place using genetic programming. The Bayesians are all about uncertainty. They know how to deal with the fact that all the knowledge that you learn is uncertain. They know how to update the probabilities of hypotheses, see more data. They use that using probabilistic inference, you know, which is essentially, you know, computationally efficient ways to apply Bayes' theorem to very large sets of hypotheses. And finally, analogizers, right, they can reason by similarity. They can actually generalize from just one or two examples, right? Think of Niels Bohr, right? He came up with the first, you know, theory of quantum mechanics by doing an analogy between the atom and the solar system, generalizing from one example. None of the others can do this. And, you know, one of the be— the— probably the best-known analogizer algorithm these days is kernel machines. But the thing that I want to point out is that precisely because each of these problems is real and important, none of the individual algorithms are enough. What we really need is a single algorithm that solves all 5 problems at the same time. We need, you know, a grand unified theory of machine learning in the same sense that the standard model is a grand unified theory of physics or, or the central dogma is a grand unified theory of biology. And in fact, a bunch of us have, have been working on this problem for a while and we've actually made a lot of progress. Uh, we know we're still far from the end of this, but let me just give you a sense of, of where we are at this point. So if you, if you think for a moment about this problem of like, so we have these 5, algorithms or like these 5 types of learning, right? How can we unify them all into one? At first, this seems like a very hard problem. And in fact, some people have claimed that it's an impossible problem to solve. It seems very hard because the algorithms all look very different. But if you look at them closely, actually they're not that different. They all have the same 3 parts: representation, evaluation, and optimization. So let's look at what those parts are and then how we can do the unification. So representation is how the learner represents what it's learning, the model or the program that it's learning, right? It's in some sense the programming language in which the learner is going to write the algorithm that it discovered. Typically, it's not gonna be Java or C++ or anything like that. It's gonna be something like first-order logic, right? But, you know, it could be differential equations, it could be linear regression, it could be all sorts of things, right? So the first thing that we need to do is to unify the representations. And a natural thing to do here is to start with the, you know, with the representations of that, uh, that, um, symbolists use, which are variations on, on first-order logic, and the representation that the Bayesians use, which are, you know, generally known as graphical models. Bayesian networks are one type of graphical model, another type is Markov networks, and so on. Each of these is already extremely general. If you can combine the two, you can pretty much represent anything you might want to represent, right? Any computer program can, for example, already be represented in first-order logic. You know, any way to deal with uncertainty and weighing evidence can be represented in graphical models. You know, there's all these sort of like bazillions of different models that people have in statistics that are all fit into that framework. So if we can combine the two, we have a very good, you know, representation to start with. And indeed we have done that. In essence, what we've developed is various forms of probabilistic logic. So this is a logic that also incorporates probability and uncertainty. And the most widely used is called Markov Logic Networks. It's essentially a combination of logic and Markov networks. And it's— and it's very simple. It just starts with formulas in first-order logic. Think of a rule in logic, like, you know, if this then that, for example. And then what it does is it gives each rule a weight. Okay? So if you really believe the rule, you give it a high weight. If you're not sure, you give it a lower weight. And then the weights of the— and then the probability of a state of the world goes up with the number and the weight of the rules that are true in that world. Okay? So with this, we can represent pretty much anything that we'd like. Now the next part of every learning algorithm is the evaluation. The evaluation is the scoring function that tells me how good a candidate model is, right? How well does it fit the data? You know, how well does it fit my purposes? Okay? In, in essence, what, what, what the learning problem is, is to find within the space defined by a representation, find the program that maximizes my evaluation function. Okay? So what should that evaluation function be? Well, one obvious, you know, candidate is just the posterior probability that Bayesians use, and that again has a lot of other things already as special cases. But more generally, um, the evaluation shouldn't really be part of the algorithm. It should be provided by the user. It's for the user to decide what the learner should be optimizing. So now, so if you're a company and, and your purpose is to maximize profits, then that's what the evaluation function should be. If you're a consumer and your purpose is to maximize your happiness, then that's what should be being maximized, is some measure of your happiness. Okay? So what the, what the, what the master algorithm should be able to do is take anybody's, you know, objective function and, and then learn to optimize that. Okay? Finally, right, I just said the word optimize. The third part of this is optimization, is how do we actually find the model that maximizes that function. Okay? And here there's a natural combination of ideas from genetic programming and backpropagation. Namely, to discover formulas we can use genetic programming, right? Each formula in first-order logic is a tree, right? And now I can cross these trees over and, and, and apply the genetic process to come up with better formulas that better describe my domain. And then once I have those formulas, of course, you know, if I'm doing— if I'm using Markov logic, I need to come up with weights for those formulas. But of course this is where backpropagation comes in. comes in, right? I have my big chain of reasoning, right, involving many different formulas and facts and different steps, and all of those have weights. And in order to, you know, learn those weights, I can naturally use backpropagation. Okay? So, you know, we're pretty far along in this. Uh, we haven't succeeded yet, uh, but, uh, you know, some people think it's only a matter of time before we do. I'm actually a little— Less gung-ho. I think that even after we've successfully unified these 5 paradigms, there are still major ideas missing. Ideas that we haven't had and without which we will not have a truly universal learner. And in fact, part of my goal in writing the book was to, you know, open it up to people who are not already machine learning researchers so they can think about the problem and maybe have ideas that people who are already thinking along the tracks of one of the tribes wouldn't have. So if you figure out how to solve this problem, let me know so I can publish your solution. Okay, let me conclude by talking a little bit about what I think that the master algorithm will enable that we cannot do today, okay? I have 4 items here, there are of course more, but I think these 4 give a good sense of just how momentous a development this would be. The first one is home robots, right? We would all love to have robots that, you know, cook dinner for us and do the dishes and make the beds and whatnot. But why don't we have them today? Well, first of all, it can't be done without machine learning, right? There's just no way to program a robot to do all the things that it might have to do. But second of all, the learning algorithms that we have today are not good enough because a robot, You know, a home robot in the course of a normal day will run into all 5 of those problems multiple times. So it needs to be able to solve all of them. So with the master algorithm, we are on our way. Without it, I think it will be much, much harder and much slower if we ever get there. Here is another one. Everybody, including of course Google, has a project to try to turn the web into a knowledge base, right? Instead of, you know, issuing keyword queries and getting back pages, what I would like to do is ask questions and get answers. But for that, all the knowledge that's on the web has to be represented in a way that the computer can reason with, something like, for example, first-order logic. On the other hand, you know, the web is full of contradiction and noise and gaps and whatnot, so it's going to be very noisy, so I need probability, okay? So again, I need to be able to combine those 5 types of learning in order to really be able to extract these knowledge bases from the web, okay? Here is perhaps the most important one, cancer. Why haven't we cured cancer yet? The problem is that cancer is not one disease, right? Everybody's cancer is different and in fact the same cancer mutates as it goes along. So it's very unlikely that there will ever be one drug that cures all cancers. The real cure for cancer or at least that's what an increasing number of cancer researchers believe, is something like a learning program that takes in the genome of the patient, the medical history, the mutations in the tumor cells, and predicts for that tumor what is the drug that's going to kill it without harming the patient's normal cells, okay? Or maybe the sequence of drugs or a combination of drugs or perhaps even a drug that will be designed from scratch for that particular patient. Okay? In some ways this is not a very different problem from, you know, recommender systems that recommend a book or a movie to you, right? What— however, what they do here is they recommend a drug. The problem, however, is that this problem is that this is an— you know, this problem is orders of magnitude harder than the problem of recommending a drug or the problem of recommending a movie or a book, right? You have to understand, you know, how the cell works, you have to understand you know, the interactions between the genes and the proteins that they make and then they go back and regulate the genes and it's when this machinery gets out of whack that you get cancer, okay. The good news is we actually have a lot of data to do these things like microarrays and sequences and whatnot. But again, with the learning algorithms that we have today, we're not going to be able to do it. With something like the master algorithm, we will be able to do it. Okay, finally, apropos of recommender systems, let me mention this one. What I would really like to have as a consumer is not 500 different recommended systems recommending 500 different things to me. Netflix recommending movies and Amazon recommending books and Facebook selecting updates and Twitter selecting tweets and what I want is a complete 360-degree model of me learned from all the data that I generate, okay? And then that model knows me much better than all these tiny little models. And as a result, can make much better recommendations, okay? And not just recommendations of small things but recommendations of jobs, recommendations of houses, recommendations of what to major in or— oops, I guess I skipped this slide here. As the former CTO of the federal government said, if we use these things, we can actually have a recommender system that is in essence your best friend throughout your life, recommending the things that you need at every step, okay? And again, in order to do that, we need not just the data, which increasingly we have, we need the algorithms that are powerful enough to learn that rich model of you, okay? More about all of these things in the book, The Master Algorithm, and thank you for listening and I'll take questions. Thank you.

The representation that you proposed, the Markov logic network, covers all— covers the natural language? Like, is there a one-to-one mapping between the representation and the— Yeah.

In fact, one of the biggest areas where Markov logic has been applied is natural language. It's a very good match to natural language because natural language is both very compositional, right? So you need the logic for that. And also, you know, very ambiguous, very uncertain, so you need the— you know, very noisy, so you need the probability for that. So people at this point have applied Markov logic networks to pretty much every major problem in natural language and, you know, and won competitions using it and so forth. So in some ways natural language is one of the killer apps for Markov logic networks.

Are we able to learn it using the genetic programming?

Yeah, so the question is, are we able to learn, you know, Markov logic networks using genetic programming? People haven't done that yet. So we've learned, you know, there's a wide range of algorithms for learning the structure of Markov logic networks. They are similar to genetic programming but without the crossover, right? They're, you know, like the evolutionaries really believe in crossover. Everybody else in machine learning thinks, you know, something like hill climbing, greedy search, or beam search is probably enough. And there are many different search methods that have been used and, and that work pretty well. It's actually a good question, right? That part has not been done yet, whether, you know, actually doing the crossover between the formulas would help.

Related question to genetic programming. How is the solution space limited? Because it seems that combining various subtrees would lead to a rapidly fast exponentially growing solution space. And have there been any success with NP-hard problems?

Yeah. So, um, you know, in, in, uh, something that people have observed in genetic programming is that the trees tend to get bigger and bigger over time. People jokingly call it the survival of the fattest. Uh, what you can do to combat that is to actually have a bias, a penalty on the size of the trees. So if the trees are big, you know, they're less fit just because of that, right? You, you put that into your objective function, okay?

Um. NP-hard problems, any success in that area with, uh, genetic algorithms or programming?

Well, I mean, the short answer to that is yes, and the longer answer is yes, but, right? A lot of the problems that people are approaching with genetic algorithms are NP-hard problems. The question that, you know, the people who aren't evolutionaries ask is, did you really solve— so first of all, they're NP-hard problems, right? So you're not— you can't solve the worst, the hardest instances efficiently, but there are many instances that aren't the hardest, and, you know, so can you solve them, you know, well enough? And there are examples of generic algorithms solving these problems, but there are also counterexamples of people saying, look, I could have done that with hill climbing and it would have been just as fast or just as good. So the jury is still out on this.

So with your 360-degree recommender systems, what's to keep that from being kind of self-fulfilling or guiding a person into some particular path that's— Not perhaps—

Yeah, well, what's going to keep that from being self-fulfilling is the way machine learning works, which is the system recommends something to you or for example it recommends 10 alternatives to you, right? Or let's say it recommends one but then you say like, no, this was the wrong one, then it learns from that. So the recommender system is not something that you learn one day offline and then you use it, it's something that is continuously learning from what you do. So if it starts doing the wrong thing, right, you start being unhappy, And you start displaying that unhappiness in one form or another and then it learns from that to try something else. And also remember these recommender systems, they can talk with each other to the extent that you decide that they can, right? So it won't just be learning from you, it will be learning from a lot of people, right? So if it had to— it's always the question of like how far do you have to generalize, right? The more data that you have, the easier the problem becomes. And the more you have a continuous loop of feedback, the more robust the learning is.

The 360 recommender, how do you square it with the need for privacy for people?

Yeah, so that's a very important question which I didn't allude to. I want to have a 360-degree model of me, but I want it to be under my control, right? Because if somebody else has a model of me that knows me better than my best friend, they have too much power, right? So I think what needs to happen is that Right now what happens is that like the data that you generate is spread all over the place. It would be cool to bring it all to one place, but that place has to be under your control. And I think one way that this could work is that you could have a company that is to your data like a bank is to your money, right? You put your money in the bank and then the bank invests it for you and so on and so forth, but ultimately the money is under your control. So I think the same thing should happen with your data. That's a great idea. with your data, right? So this company aggregates the data, it learns the model, it uses the model on your behalf, but at the end of the day it's for you to decide whether maybe, for example, you want to take the data somewhere else or you want to do something else with it. I think if you don't do that, people won't trust this enough for it to happen.

What are your thoughts on TensorFlow?

I haven't played with TensorFlow myself, right? I think first of all it's great that TensorFlow has been released, right? I think releasing open source software like this is a large part of how we make progress. And, you know, definitely deep learning and doing it on a large scale are very important. There are a number of other, you know, alternatives out there. Uh, we'll see how, you know, TensorFlow compares with them. But, uh, and we also see, you know, like just from my own point of view, right? I have some of my students working on deep learning. The question with each one of these systems is what does it support well versus not, right? I think if the learning that you're trying to do sort of like fits within the paradigm of TensorFlow, then it's probably a good thing to use. But if it doesn't, then you may need something else. Or maybe, you know, what's gonna happen is that there will be an extension of TensorFlow to do these things in the future.

One of its goals actually is to become a universal system for expressing AI solutions.

Yeah. And I very much sympathize with that goal, right? I think that in order to be a universal system, you have to cover these 5 paradigms, right? But the way to cover it— one way to cover them is to start from one, let's say deep learning, and then try to absorb another and another and another, and there are people doing this kind of thing. Like for example, we have the Alchemy system which combines first-order— combines the symbolist and the Bayesian learning. We've also developed, for example, combinations of symbolic learning and instance-based learning and this with neural networks. So what I hope to see from a platform like TensorFlow is is see it absorbing more and more of these capabilities. And absorbing them doesn't necessarily mean going and giving us some primitives to do what that school does, I mean that's okay, but it also increases the complexity. The ideal thing would be you still have something that is simple, but yet with that simple thing you can do all these combinations of things. And I do think that's possible and I'm curious to see how this is all going to evolve in— in the next several years.

And with that, please join me in thanking Pedro for this talk.

Thank you.