Emeritus Lecture: Pedro Domingos (Oct 2022)
In this emeritus faculty lecture, Pedro Domingos reflects on two decades of research at the University of Washington, outlining seven foundational areas he helped launch and their evolution. He begins with the challenge of scaling machine‑learning algorithms to massive data streams, introducing the VFML library and the concept of data‑stream mining with IID assumptions. He then discusses statistical relational learning and information integration, showing how machine learning can automate schema matching across heterogeneous databases. The talk moves to adversarial learning, framing it as a game between a classifier and an adaptive adversary, and traces its resurgence with deep‑learning vulnerabilities. Domingos explains influence maximization, linking early viral‑marketing ideas to modern network‑value models built from recommender‑system data. He introduces Markov Logic Networks as a unification of first‑order logic and probability, describing learning, inference, and the probabilistic theorem‑proving framework that makes inference tractable. He connects this to sum‑product networks, a class of deep models with tractable partition functions, and argues for their under‑utilization due to sociological inertia. The lecture then presents symmetry‑based (geometric) learning, emphasizing how discovered symmetries can dramatically improve generalization and lead to interpretable models, with examples ranging from faces to cats. Domingos also recounts his role in building AI curricula, popularizing machine learning through his book The Master Algorithm, and serving as an ambassador to industry and policy makers. He concludes with a forward‑looking view that current scaling will eventually hit limits, and that new paradigms—game‑theoretic learning, probabilistic logic, and symmetry‑based learning—will shape the next generation of AI research.
Chapters
Welcome to today's Emeritus Faculty Lecture by— for Pedro Domingos, who began as a professor in the Department of Computer Science at the University of Washington a little over 20 years ago, right at the start of the millennium. retiring as Professor Emeritus in the Paul G. Allen School of Computer Science and Engineering. So this is a 20-year span. Back when Pedro started, we were in Sieg Hall. We now have 2 new buildings. And we get to enjoy a place like this for colloquia. Pedro has had many accomplishments. Award papers, has done research in many diverse areas. I'm not going to list them all. One that's particularly close to me is his work on statistical relational modeling and so on. So that's where it's impacted some of the things that I work on. But he's had impact in a lot of areas. And he's also been a well-known popularizer. of this, of the whole area of machine learning with his work, his book, The Master Algorithm. And Pedro is going to tell us something about the last 20 years and the next. I'm very much looking forward to it. Thank you, Pedro. Welcome.
All right. Thanks, Paul. And thanks everyone for being here. And also thanks to all the great people that I've had the luck to work with over the years. And, you know, that's— you know, a lot of this work is really theirs as much as mine. I would like to dedicate this lecture to the memory of my mother, Ana Maria, who was the leading sociologist of education in Portugal and left us this year. And what I would like to do in the next 50 minutes or so is go over 7 areas that we helped to start. You know, look at what I've done with these people in the last 20 years in the Allen School, but also the part that we played in the machine learning revolution more generally. I will also So I'm going to look at what motivated us, what we came up with, and what the state of these areas is today. I will also touch, as Paul mentioned, on some of the work that I've done in machine learning, in AI education and popularization, and speculate on what the future might hold. So when I started at UW back in 1999, the main focus of my research was on scaling up machine learning algorithms. The major types of machine learning were already developed by then, and there had been a lot of progress in the '90s on making them more practical. For example, by making them more robust to noise. But they were not keeping up with the volumes of data that were becoming available. The algorithms' running times were typically quadratic or worse. And we typically ran them on hundreds or thousands of examples, which I can hardly say without smiling now. But datasets with millions of examples were becoming available, and we wanted to be able to mine them. So the question was, what to do? And at the time, there were a lot of very hacky approaches to solving this problem. You would typically take something like decision tree induction or clustering. And come up with a version of it that ran in linear time and that was good. But on the other hand, there was no particular known relationship between what this algorithm produced and what the original one did. So our idea was to come up with a way to minimize the running time of learning algorithms while guaranteeing that the model they produced would be approximately the same as you would get if you could run them on infinite data. At least with high probability. And so that's what we did. Then you can ask yourself, so how far can we push this? It turns out we could push it a lot farther than we thought. In fact, this approach actually lets you run in time independent of the size of the data. We were aiming for linear, and usually log is the big success, but this was constant, right? And you might think, well, gee, how is that possible? possible, right? Actually, the reason that it's possible is very simple. Think of polling, right? If you want to know how many people will vote for a particular candidate, the number of people you need to poll does not depend on the size of the population. It only depends on the error that you're willing to tolerate in the estimates, okay? And, you know, the number of people who vote for a candidate is one parameter. And the machine-learned model is really just a very large number of parameters. But the same thing that we can do for one parameter, we can do for a very large number of them while preserving the guarantees if we're careful about how we do it. And that's exactly what we did. Crucially, for this to be practical instead of just a nice piece of theory, the treatment— the bounds have to depend on the specifics of how the algorithm works, not just the hypothesis classes as is often done in learning theory. So we started by doing this for decision tree induction, which at the time was the most popular machine learning method and today still the best one for many problems in the form of an ensemble learned using something like SGBoost, which was developed here, or random forest and whatnot. And then we ran it on a data set of 100 million examples. Which was unheard of at the time. In fact, just to store the data, I needed to buy more disk space than the entire department had at the time. And then we did it for other things like clustering, mixture models, Bayesian networks, relational models, and so on. And then finally, we came up with a general method by which you could give us a learning algorithm and we would turn it into a learning algorithm that behaved approximately the same with guarantees but in time independent of the size of the data. And we made all of these available in the open source VFML library. And the whole paradigm of mining data streams came out of the work of our group and a few others. And the idea here is that instead of you having a static data set that you then mine and deploy the model, the data is always coming in. And you're continuously adapting. And you only ever get to look at each example once. Either because you never see it again or because there's just no time. There's too much data and, you know, you only have, you know, fixed time, for example. And, you know, these days, of course, you know, this is becoming something that is almost standard, at least in the more advanced industries. It is also something that is very similar to how your brain works if you think about it, right? This is what you see. You see a continuous stream of data and you're continuously learning from it. And indeed, there's a large literature on this in the cognitive psychology literature And part of what's interesting about this is that it made contact with that and kind of like helped to bring it over to machine learning. Now, of course, you may be thinking this sounds a little too good to be true. And it is a little too good to be true. So as in all apparent miracles, there's a catch. And the catch here is that the data has to be IID, or independent and identically distributed. This is just statistical jargon for saying that, Once you know the model, one example says nothing about another. And this is a standard example throughout statistics and machine learning. And it makes the math a lot easier. But it's completely unrealistic for almost every domain that you can think of. And indeed, pretty soon, dealing with IID data became a central focus of my research, as I will talk about in just a moment. But before that, let me touch on a couple of other things that we did in my early years at— in what was then the CSC department. So information integration is actually one of the most important— is like the most important problem in computer science few people have heard of. By one estimate, almost half of the entire IT budget of a typical Fortune 500 company is spent spent on integration. The data that the company runs on is in all these different databases, applications, ontologies, spreadsheets, et cetera, et cetera. And they don't talk with each other. Every organization today is a Tower of Babel. And this creates a lot of problems because then you want to— it makes you unable to answer queries that otherwise you should be able to. Even within the same database, if in one relation somebody's phone number is stored as a field called phone and in the other one it's called contact, then the system doesn't know that the 2 are the same, okay? And this becomes an even bigger problem if you want to mine the data. And if now instead of just looking at a single company, you're actually looking at the whole— you know, at all the structured information on the web, this become— you know, this problem becomes nearly impossible. Okay? Who's going to come up with all the mappings, you know, among these fields and concepts and entities and whatnot, right? Traditionally, this was done by hand, right? Somebody would really— would, you know, would write down the rules to convert, you know, one concept to another, often a combination into another. So for example, if you want to merge prices with and without tax, right, you need to know the tax. And the tax varies by state. So now you have to bring that in, right? So this was very costly. And it was always incomplete and continuously getting more so. So our idea was to solve this problem using machine learning. If you think about it, the contents of the relations, of the tables, are a very powerful guide to what those fields are, or records, or et cetera, et cetera. Right? So for example, if you have a field that's full— if you have 2 fields in 2 databases that are both full of what seem like telephone numbers, they're much more likely to match than if one looks like telephone numbers and the other one looks like addresses. OK? And even better, as the data that you have grows, the problem instead of getting harder gets easier because you have more hints. So this was our idea. Now part of what makes this interesting from a machine learning point of view is that this is not a standard machine learning problem. You can't just apply an off-the-shelf machine learning algorithm here because in standard machine learning, the data is all in one relation and here it's going to be in many relations. And in standard machine learning, there is IID and here again, it's not going to be IID. And then on top of that, there are a lot of constraints that the data has to satisfy without which this doesn't work or make any sense. And there's no easy way to incorporate those constraints into a standard learning algorithm. So what we came up with was a new type of machine learning algorithm with a couple of different components. The first component is, you know, we learn a model of the joint distribution of the data sources. We actually learn many different models using many different Bayes learners because, you know, there's such a wide variety of things, no single algorithm will be better. And then we combine them using a meta-learner, something which is new— you know, newly popular these days. And then in the second phase, we combine— when we apply this to a new pair of, for example, databases that we want to merge, we estimate the similarity of every pair of fields. And then we combine that with a constraint satisfaction solver to actually produce our predictions for what matches what. And then we generalize this to complex mappings by searching over combinations in one database that would produce something in the other database. Okay. And then we apply this to things like, you know, hunting for real estate on the web, right? You want to buy a house, there's all these different sites that have listings or houses for sale and wouldn't it be nice if you could just go to one place that had all the data and then you query that and get your answers? Well, that's precisely what we did so it's much more convenient and, you know, you might otherwise miss the house that you actually wind up buying. You can actually tell from the contents of this balloon that house prices have gone up a little bit since then. So this was— using machine learning for information integration is now a standard thing to do. And a lot of things work better because of that. From the machine learning point of view, it's also interesting because it led to this new class of problems where there's multiple relations, it's non-IID, there's constraints, and so on, which I will continue with in just a second. So here's another interesting— direction, which is actually even more interesting these days. And this is adversarial learning. So the 2000s in America were dominated by 9/11 and the specter of terrorism. And like the defense intelligence, police, et cetera, they quickly realized that machine learning could be a great tool in catching the bad guys. But, you know, at one point, a DARPA program manager bemoaned to me that everybody was trying to sell a classifier to the Pentagon but the classifiers didn't work. And the reason they didn't work is that the bad guys, you know, quickly figured out how to change the features of what they were doing to defeat the classifier. And I thought, huh, this is an interesting problem. Because number one, it goes beyond the standard machine learning paradigm. And number two, it seems to have a lot of other interesting and important instances besides counterterrorism or law enforcement or whatever. Things like fraud detection, intrusion detection, spam filtering, aerial observation, et cetera, et cetera, were all instances of this. And then one day while standing in the TSA line at SeaTac with nothing to do and kind of wishing we'd be done, This idea came to me that what you needed to solve this problem was a combination of machine learning and game theory. Because what really happens here is that there's a game being played where your move is a classifier. And your opponent's move is a data perturbation to defeat the classifier. And this is a game, except it's a very unusual kind of game because the moves are not just defect or cooperate, but they're like it's a whole classifier. Oral data manipulation. So I had just started a graduate machine learning class. And I suggested this as one of many possible projects for people to do. It was towards the end of the list because it was one of the harder ones. And I didn't think anybody would be rash enough to try it. But there was a group of 4 students that did. And they made shockingly rapid progress. And within a month of the end of the quarter, we had submitted the paper on this to KDD, which is the top data science conference. And the paper had a theoretical framework. It had some strong theoretical results. It had an algorithm. And we applied it to spam filtering using existing databases. And it was spectacularly successful. So without— so the original spam filter was maybe 90% accurate. And then once the adversary optimized his side of it, It went down to like 50% almost. But then once we did our thing, it went up even higher than it was before for interesting reasons that I won't go into. And people were very excited about this at the time. Some were saying, wow, this is a whole new direction in machine learning. And then for the next 10 years, nothing happened. I got a grant from Google to do this, which was nice. I found out about a whole other set of problems, of adversarial learning problems that they had very important to them, things like link farming and— And click spam and whatnot. But their conditions for using the data were so strict that we really couldn't do much with it. So for 10 years, nothing happened. And then in 2014, a group of deep learning researchers discovered that deep learning is extremely vulnerable to this type of manipulation. And so the whole area of adversarial learning took off like a rocket. It continues to this day. There's an ever-growing variety of algorithms. But the basic theoretical framework is still the one that we defined here. And looking forward, I actually think that game theoretic learning is going to be central not just to AI but to how society functions. And the reason is that, of course, machine learning is now used everywhere. But the paradigm that we use in machine learning is not in touch with the real world. This paradigm that you get data, you mine the data, you deploy a model, and then it works. You know, indefinitely. That's not how things work. When you deploy a model, the people that it's modeling change their behavior in response to the model, adversarially or not, but they change their behavior, right, which renders the model obsolete, okay? So what really happens in the world is that there's this arms race going on between the modeler and the modeled. And we are all modelers and modeled. In fact, some people even say that that's why we have such large brains. The interesting thing from a machine learning point of view is that these days some of those modelers and modeled are machine learning algorithms. The machine learning algorithms model us, but now we're also modeling them. And they model each other. And in areas like the stock market and ad networks, this is already pretty far along. But I think as we go forward, this will become the norm everywhere. And you want sound principle ways to deal with this as opposed to just, you know, hacks and trying to keep up with things which is what Google was doing back then. So here's another very interesting one, influence maximization. So back in 2000, in the glory days of the dot-com boom, the house magazine of the startup world was something called Red Herring. And one day while browsing at Bulldog News on the Ave, I ran into an op-ed in Red Herring by Steve Jurvetson, a famous venture capitalist, where he described— so they backed Hotmail, the first big successful free email service. And he described something he called viral marketing, which had been responsible for the success of Hotmail. And this was just a simple genius idea that they had was that in every email you sent using Hotmail, there was a tagline at the end saying, this email was sent using the free email service Hotmail and you can get your own free account here. And then, you know, every user became a marketer and they exploded in one country after another on the back of no marketing expense, okay? And he had a very simple— in that, you know, 2-page piece, he had a very simple 4-parameter model of how viral spread works. And I immediately thought, wow, with machine learning we could actually do this for real. We could have a model of the social network, the people, the nodes between them and how they behave. And then we could use that to get the maximum possible number of conversions for the lowest possible budget. And this is what became known as the influence maximization problem. And again, these days there's a whole industry of people doing it. Okay? There was only one problem though, which was there was no data, right? This was before Facebook. This was before MySpace. There were no social networks. There's a group here, a very well-known one at UW, that studied social networks. And, you know, the datasets that they had were typically networks with tens or hundreds of examples. I kid you not, right? So I thought, well, yeah, nice idea, but I shelved it, okay? But then a few months later, something else occurred to me, which was that A recommender system, which is also something that was just beginning at the time, effectively creates a social network among its users where your neighbors are the people with similar tastes to yours whose preferences are used to predict yours, okay? And there was a well-known recommender system data available at the time called EachMovie, which was 3 million movie ratings by 70,000 users. 70,000, well, you know, imagine that. I mean, compared to what we had before. So we use that and we developed a way to measure what we called the network value of a customer. So Joe's network value is high if the expected increase in the number of people who buy the product is high, right? So the more people you influence, not necessarily 100% or directly, but whose probability you increase even by a little bit, right? All of that contributes to your network value. On the other hand, if you influence very few people directly or indirectly, your value is low and we could actually compute this from the model and then we could use it to solve the optimization problem of like how can I get the greatest number of conversions for the smallest possible investment budget. And when this— so now you can ask like, well, how high can the network value of a customer be? may be high, but we need— we didn't expect it would be as high as it was. In a network of 70,000 people, the user with the highest network value had a network value of 20,000. So marketing to— if you convince that one guy, it's potentially as good as convincing 20,000 people. Now naturally this received a lot of interest from industry because everybody wanted the magic of marketing for free. Right? I got calls from like tech companies, old-style companies like AT&T and Ford and from ad agencies which are actually some of the savviest, from startups. I had one of the founders of MySpace in my office talking about how to use this. And then of course Facebook came along and social networks with billions of people and these days influencer marketing is a standard thing to do. But what's interesting is that it's still mostly very ad hoc, even compared to the model that we had 20 years ago. And the reason for that is not wholly surprising. It gets back to this issue that modeling a social network properly, as opposed to just some hacky heuristics like centrality and whatnot, is actually very hard. Precisely because there is non-IID, If you have a network with 1 million people, you now have a model that is 1 million times bigger than the model for the individual users that you had before. And now the influence maximization problem is solving an NP-complete problem over this data, right? So this seems completely hopeless. And we had a lot of things that we did to make it more viable, and we did. But more importantly, this was another strand that led us to kind of like finally decide to squarely face this issue of how do we learn with data that is non-IID, that is in multiple relations, and where there are constraints that are not just, you know, the data and vary from domain to domain. And the good news is at this point we actually have, you know, a very good understanding of how to do this. And that understanding really stems from one very simple observation, which is that we've had the language to do this all along. It's called first-order logic. Right? It's the language of objects and relations between objects and dependencies between those relations. It's just that we have to combine it with the language of probability and statistical models that we use in machine learning. And it's that combination that's going to give us the power that we want. And this is indeed what we, many of us, and then many other groups in academia and industry following on from this worked on. In particular, the language that we developed is called Markov Logic Networks, and it is a unification of first-order logic and probability. And, and, you know, the basic idea is actually very simple. Think about it this way. Suppose you want to say that smoking causes cancer and friends have similar smoking habits, right? Because you want to convince teenagers to not smoke because indeed their friends are the biggest influence on whether they start smoking or not. Okay? You can express this very straightforwardly in logic as for every x, smokes of x implies cancer of x, and for every x, y, friends of x, y implies that smokes of x and smokes of y are equivalent. Okay, very nice. There's a big problem with this though, which is that this— these 2 statements in English are true and these 2 statements in logic are false because not everyone who smokes gets cancer and certainly not all pairs of friends have the same smoking habits. So what we need to do is we need to turn these back into the statistical statements which implicitly they always were, right? Smoking is likely to cause cancer. Friends are likely to have the same mixed genetics, you know, more or less, right? So that's exactly what we do. So starting from logic, you know, in standard logic, a knowledge base is a set of hard constraints on the set of possible worlds, okay? And their hardness is exactly the problem. Like, it makes life easy on the one hand, but on the other hand, it makes them unrealistic. So let's make them soft constraints. So when the world violates a formula, it becomes less probable but not impossible. So we get this grateful degradation as more smokers don't get cancer and so on. And then we give each formula a weight that reflects how strong of a constraint it is. A formula that is almost never violated has a very high weight and so forth, okay? And then the probability of a state of the world is just the exponentiated normalized sum of the weights of the formula instances that it satisfies, like in all the smokers that do have cancer and the pairs of friends that have similar smoking habits and whatnot. So this is an intuition. Let me just give you a more precise statement and then I will unpack it. So— A Markov logic network, or MLN for short, is a set of pairs f, w where f is a formula in standard first-order logic and w is a real number. The MLN together with a set of constants representing objects defines a Markov network, a standard undirected graphical model with one node for each grounding of each predicate, each relation that appears in the MLN. and one feature for each grounding of each formula in the MLN with the corresponding weight W, okay? This is a bit of a mouthful. Let me illustrate with that friends and smokers example, okay? So here are my 2 formulas and now suppose that I have a very large social network consisting of Alice and Bob who maybe live alone on a, you know, desert island or something, okay? So what does this— and, you know, and Smoke says, you know, the first formula has a weight of 1.5, the second 1.1 because it's a weaker regularity, right? So what probabilistic model is this representing? OK? Well, think of the rule, right? There's going to be a ground predicate, which is just a Boolean variable for whether Bob gets cancer and whether Anna gets cancer and whether each one of them smokes, right? Same for Bob is friends with Anna. A different one for Anna is friends with Bob, because friendship is not symmetric, as any student of these things will tell you. And then also friends Anna, Anna and friends Bob, Bob, which, you know, maybe have to do with their self-esteem or something, right? So these are the variables that the probabilistic model is going to be over. They're just simple Boolean variables. And now, you know, in a graphical model, there's an edge between any 2 variables that directly depend on each other, which in our case is any 2 variables that appear together in the same formula, okay? So for example, there's going to be an edge between smokes Anna and cancer Anna, and same for Bob, right? And then there's going to be a clique between friends Anna, Bob smokes, Anna smokes Bob, and so on, okay? And so at the end of the day, what is the probability distribution that this is representing? Notice that— so it's given by a formula. So the probability of a state of the world, which is who smokes, who doesn't, who's friends, who isn't, who gets cancer, et cetera, is just the normalized exponentiated sum over all the formulas of the weight of the formula times the number of its instances in the data that are true. OK? So if a formula with high weight has a lot of true instances, that makes the world a lot more probable, and so on. Notice importantly that the MLN does not represent a single probabilistic model. It's a template. It actually represents a whole family of them. And this is a lot of what makes it powerful. One way to think about this is that an MLN is to an ordinary probabilistic model like programming in Java or Python is to programming in assembly code. And like, who wouldn't want that? You could even say that machine learning isn't mature until we start doing things at this level. Now, of course, what I described here is just the very basics. We can handle functions as essential quantifiers, infinite continuous domains, the whole works. I won't go into the details here. The nice thing is that first-order logic is a simple special case of this. It's just the case that you get when all the weights go to infinity. And every entailment question in first-order logic can be answered by answering a conditional query in this language. And the statistical models that we all know and love are also special cases of this. In particular, the special cases you get when all your predicates are unary. All you have are properties of individuals. You don't have relations between pairs of individuals or more. So this was very nice. The problem of unifying first-order logic and probability goes all the way back to Boole and others. And many people, scientists and mathematicians and philosophers, Some of them thought it was impossible to solve. And we have solved it. And this opens up a whole range of applications and a lot of things we can do faster and better than we could before, if we could do them before at all. But of course, none of this means much if you're not able to do learning and inference efficiently in this representation. And that actually is the big challenge. So how do we learn MLNs? Well, the training data is now a relational database with as many relations as you want or anything that you can convert into— represent as a database like text or images. We can learn formulas by discrete search using ideas from inductive logic programming and graphical model structure learning. And now how do you learn the weights? And going in, we thought, well, this is going to be so hard because the data is not IID anymore. All hell breaks loose. Well, actually, it turns out to be no harder. You maximize the likelihood using gradient descent. The gradient actually has a very natural, you know, form. You know, the gradient with respect to a weight— or sorry, the log likelihood with respect— the derivative of the log likelihood with respect to the weight is the number of true groundings of that formula minus the number according to the model. So you have to increase or decrease the weight until these 2 things line up, and then you have your maximum likelihood. And then you can optimize this by gradient descent. It's a convex problem. Right, so you can find your global optimum, right? Now, of course, there must be a catch here, and the catch is that each gradient step now requires inference that is much more expensive than before. Okay, because it's now over one of these mega examples like a whole social network as opposed to just saying, you know, one user or one customer or whatever. Okay, so this is all only— so why do we need that inference? Because This is just from the data, but to compute the expected number of 2-groundings according to the model, we have to do inference in the model, okay? So this is actually where the bottleneck is. So really the crucial problem in all of this comes down to doing inference efficiently, both in its own right and for the sake of the learning. And, you know, there was a lot of research on this. There's still ongoing research on this. But we, you know, after many steps, we came up with something that was a fairly complete solution. And this is what is called probabilistic theorem proving, which is a generalization of theorem proving, as the name implies, to having formulas that have probabilities. Okay, and I won't go into the details of how we do that. Let me just show you this, this diagram, which is maybe my favorite diagram from all the papers I've written. So there's, there's, you know, each corner of this cube represents a class of problems. And the edges represent variations. So here on the bottom left, you have theorem proving in propositional logic, which is equivalent to satisfiability testing. And then there's 3 dimensions— counting, weighting, and lifting. So counting is when, in addition, you don't just want to solve the SAT problem. You want to count the number of solutions. Weighting is when each formula has a weight, and you want to maximize the sum of the weights of the satisfied formulas. And this is actually equivalent, formally equivalent, to doing inference of the most probable explanation in a probabilistic model. And now if you combine the two, you get weighted model counting, which is equivalent to computing marginals in probabilistic models. So all of propositional logic and graphical models probability is encompassed here. Now finally, there's this notion which is lifting, which is going to first order. Having predicates with variables that range over objects and so on and so forth. So, okay, when you lift propositional theorem proving, you get first-order theorem proving. But then you also have the lifted version of weighting, and you also have the lifted version of model counting. And when you combine all of those, probabilistic theorem proving is a procedure that does lifted weighted model counting. And once we have a procedure to do that, we have a procedure that does every single one of these things, you know, as a trivial special case. So you're saying that the Now, of course, probabilistic inference alone is Sharpey complete. And first-order logic is semi-decidable. So this, in the worst case, is still not going to cut it. So what do you do? Well, now you can do approximate inference. And indeed, we and others have developed approximate versions of this based on things like Markov chain Monte Carlo, belief propagation, variational inference, and so on. Another thing that you can do, which from an industrial point of view is probably the most important one, is we can focus on tractable sublanguages of Markov logic. In particular, we've developed an object-oriented language called Tractable Markov Logic that ensures— it's still a surprisingly expressive language, of course not as expressive as first-order logic, but allows it to express a lot of most of the things that you want most of the time. And apparently, it's also very psychologically plausible. And the inference time is linear in the size of the MLN and in the size of the data, worst case. In practice, it's actually more like logarithmic. And using it, we've been able to extract from the web a probabilistic knowledge base with millions of objects and billions of parameters. And then we can answer queries over that knowledge base in a fraction of a second and give exact answers, not just approximate ones. What makes this possible? The key property is that all the dependencies in this model have to be mediated by the class and part hierarchies. Computing probabilities is basically doing sums and products. And the problem is that there's an exponential number of them. And what's going on here is that every time you do a sum, it has to be over the subclasses of a class. And every time you do a product, it has to be over the subparts of an object that are assumed independent given the class, right? So it can enrich by having more classes. And, you know, of course, in the worst case, you could have a very large number of classes, okay? And this also turns out to have a very interesting connection to deep learning, another area that I've worked a lot in and that we will get to in just a Second. So Markov logic has been applied to many different areas. Probably the biggest one is natural language processing. I think essentially every major subtask of machine— of NLP has Markov logic solutions for it. But it's also been applied to things like social network analysis, robotics, vision, computational biology. The famous Cyc knowledge base, the largest hand-built knowledge base ever, they turned part of it into an MLN to show how they could make it probabilistic. And the CALO project, the famous DARPA project out of which Siri came, the inference engine for that project was based on Markov logic. So the personal assistant, the CALO personal assistant, was basically doing Markov logic-based inference and representation. And MLNs have been widely researched in academia and widely researched in industry and the user base. Continues to grow. So deep learning. If you pick up the standard deep learning textbook by Ian Goodfellow, Yoshua Bengio, and Aaron Courville, you will notice that it's composed of 2 main parts. One part is the deep learning we do, and the other one is the deep learning we'd like to do. The deep learning we do is, fairly efficient provided you have enough GPUs. But it's a pile of hacks. The deep learning we'd like to do involves sophisticated probabilistic models like deep belief networks and deep Boltzmann machines and whatnot. But it's not practical. And the reason it's not practical is precisely that the probabilistic inference is intractable. And probabilistic inference all boils down to computing this thing called the partition function Z. Which is the sum of the unnormalized probabilities of the exponentially large number of possible states. Because you need that to actually normalize the distribution, compute conditionals, and so on. In fact, this problem is so bad that Geoff Hinton famously says that he has spent his life under the shadow of the partition function. And it's not just important in machine learning. It's very important, for example, in physics. Again, Richard Feynman and many others, you know, say that, and it's true, that every quantity of interest in statistical physics can be computed by computing the partition function. Okay, so the question that we asked ourselves was, what are the most general conditions under which the partition function can be tractably computed? Okay, and these turned out to be much more general than was previously assumed. And it leads to a new class of deep networks called sum-product networks. And they're called sum-product networks because the networks consist of alternating layers of sums and products. And in fact, a tractable Markov logic network, as I described before, can be compiled into an SPN of the same size. And that's why inference in it is tractable. And then as a bonus, this representation is much more intelligible than the traditional deep learning ones. Because a sum node corresponds to a mixture model, literally a statistical, you know, mixture model. And the product node corresponds to a feature and you can go and say like, oh, you know, I have a distribution over images, you know, there's a mixture model between, you know, urban and rural and seascapes, for example. And then a city breaks up into like, you know, buildings and roads and cars and those have distributions and you have the product of the distribution over the car— cars and the people conditioned on the city and so on and so forth. So it's tractable and it's much more interpretable. Now when we started doing this back in 2011, there were about 2 dozen deep learning groups in the whole world. So here's a web page that Yoshua Bengio put together in January 2013, right after AlexNet came out, with a list of deep learning groups in the world. Here's ours, but the entire list fits on this page. So deep learning has grown a little bit since. Now, why isn't everyone using SPNs, which ironically won the best student paper award at the conference that AlexNet came out in? And Geoff Hinton said this was the only thing he saw at the conference that scared him. But they haven't taken over the world yet. And why is that? I would say that it's largely down to sociology. When AlexNet— was so successful, people just converged to that type of architecture when, in fact, there were many others that worked just as well or better. But the end of this story is still far from being written, which brings us to the next and final research area that we helped to start, which is what's called symmetry-based learning or also geometric deep learning or it goes by a number of different names. And the basic idea is this. The Achilles heel of deep learning, and indeed of all machine learning today, is that it doesn't generalize very far from the data. OK. As you get farther from the data, the predictions get inaccurate very quickly. And you can paper this over— and this is indeed what's happening today— by having more and more data. But in a high-dimensional world, at some point, this just— this runs out of breath. So I believe that we need a fundamentally new paradigm, different from the existing ones, to solve this problem. And symmetry-based learning is precisely that. And I first proposed it at an invited talk at ICLR in 2014. ICLR is the number one conference on deep learning rather than just general machine learning. And back then it was a workshop of 200 people. Now it's a conference of 6,000 people. This was the, you know, this was the second one ever. And in all honesty, talking about this back then was probably premature, but these days it's a very rapidly growing area and several best paper awards at, you know, top conferences have been won by various, you know, groups doing this and so on. So what's the idea in symmetry-based learning? The idea is the following. So first of all, what is a symmetry? A symmetry of an object is something that we're all familiar with. It's a transformation of the object that leaves its fundamental properties unchanged. So for example, rotating a square by 90 degrees leaves it unchanged, so it's a symmetry of a square. Rotating a circle by any degree leaves it unchanged, so all of those are symmetries of a circle. More generally, and more relevant for our purposes, A symmetry of a function is any change in the input that does not cause the output to change. And now you can start to see that this— suppose the function is a classifier. So now this is potentially very relevant for machine learning. Now symmetries can be discovered from data even without supervision, particularly if there are small changes. And this is the crucial point. Symmetries can be arbitrarily composed. So if I discover 100 different symmetries from data, 100 small changes, by composing them, I can wind up with something that looks very different from the original, but I can still solidly make a prediction for. So for example, if I've seen many pictures of cats and learned many different symmetries of cats, I can now compose them to correctly classify an image of the cat that is potentially radically different from any image of a cat that I've seen before. Or for example, I can answer questions by finding paraphrases in the question of things that were in my text and compositions of them. So the text that answers the question could look very different from the question itself. Now of course, the most famous and simplest example of symmetry-based learning is just ConvNets, convolutional neural networks, which set off the deep learning explosion. Are just an application of the simplest symmetry there is, which is translation invariance, to perceptrons. And so the first thing that we did was use these ideas to generalize ConvNets to what we call deep affine networks, where your image may not— may have been not just— or the object is not only invariant to translations, but to rotations, to scalings, to anything in the affine group. Okay? And as a result, we can learn a better classifier with far fewer examples than a standard ConvNet. Okay? And then we apply this to text and question answering. And what we're working on currently is discovering these symmetries from video, right? Because video seems like a killer, you know, source. You know, like each pair of successive frames has some small transformations between them that are, you know, potentially symmetries that you can then reuse later. So stay tuned. The early results are pretty exciting. Ultimately, I think that symmetry is going to be a new foundation for machine learning, along with and as important as logic, probability, and optimization. So switching gears, talk a little bit about education and popularization. When I joined UW, we had only 2 graduate AI classes, AI1 and AI2, and 1 undergraduate majors and 1 undergraduate non-majors. And in 2001, I started the first graduate data mining— machine learning class, which at that point we called data mining because that was the popular term. But it was really machine learning under the name of data mining, as illustrated by this web page complete with the steam-powered Turing machine. And then in 2001, I also proposed to the curriculum committee an undergraduate class on machine learning. But they rejected it, saying it was too specialized and no one would want to take it. But then student demand eventually prevailed. And in 2009, 446 started. I also proposed a new class on probabilistic methods. But the curriculum committee said, like, oh no, you can't have a class with that name because probabilistic methodology means something else in theory of computing. And so I changed the name to Statistical Models. And 515 started in 2009 as well. And of course, these days we have a whole variety of machine learning and related courses, and hopefully more to come as well. One interesting side effect of this was that I spent 10, 15 years teaching machine learning to people at various levels— graduate, undergraduate. PMP was actually— the Professional Master's Program was actually a very, very interesting one. And so I got used to explaining machine learning concepts in kind of like simple, easy-to-follow terms. And this came in very handy when I decided to write a popular science book about machine learning, which was in 2012. Because at that point, this was when big data was taking off. And I felt really strongly that we were at the point where it wasn't just for experts to know about machine learning. Every CEO, every policymaker, everybody who uses a recommender system needed to have at least a good conceptual model of how machine learning works. And so I wrote this book called The Master Algorithm. And the book is really just the class minus the pseudocode and the equations and plus a bunch of quotes, analogies, and anecdotes, and so on. And the timing was very fortuitous because by the time the book came out in 2015, AI had taken off. It was on the covers of magazines. Everybody wanted to learn about it. So the book wound up being translated into a dozen languages. You can see some of the editions here. And it has sold over a third of a million copies to date, which if somebody had told me that at the time, I would have thought they were crazy. And it continues to sell. It's like one of those evergreen backlist items. And as a result of writing this book, I've spent the last several years being somewhat of an ambassador of AI to people in other areas, talking about AI to CEOs, VCs, policymakers, scientists, investors, journalists, artists, et cetera. And this has been an incredibly— it's been an amazing experience because I've gotten a window into how the tech industry works and other sectors of society work that via their interactions with AI that I think few people ever get. And it all started with a few classes and the small group here in the Allen School. So where are we going? In its 70-year history, machine learning has alternately been limited by the amount of data and the amount of computing available. And today, we are in the mode of going all out trying to scale up further. But I'm pretty sure that at some point, this is going to run out of steam. And like I concluded back in my early days in the Allen School, Our algorithms, no matter how much data we give them, are not smart enough. We just need fundamentally better algorithms. And this is where I think the real action is going to be. And in some sense, the real action is just beginning. Back in 2007, we had a seminar here at UW in the fall on human-level AI. And we had a bunch of great speakers from UW and from outside. And in my talk in that seminar, I said the following. I said, no one— AI was by then like 60 years old. And I said, no one so far has really worked on human-level AI for a very simple reason, is that we don't have the computing power to do it. So we work on these restricted subproblems that are what we can make progress on with the hardware we have. But in 10 years' time, if you extrapolate, we will have the power to do that. Well, those 10 years have passed, and that's now. So the real AI research is really just beginning today. So I think this is a very exciting time to live in. And indeed, the best is yet to come. And on that note, I'd like to end this talk where I think it should end, which is with the new generation of machine learning researchers in the Allen School. Thank you. So when I was the first machine learning hire in CSC back in '99, and then for the next decade when I was the only machine learning faculty in the department, I could scarcely have imagined that one day we would have a group of this size and caliber. And this is not even counting all the people who do machine learning applied to various things. So I'm looking forward to seeing what they get up to and to meeting again in 20 years' time to celebrate what's been accomplished and look forward to the next 20 years. Thank you.
Thank you, Pedro. We do have time for a few questions. Any questions from the audience?
Yes. Hey, Pedro. Good to see you. Hey,
how's it going?
Could you run through another symmetry-based example?
Sure, pick one.
I don't know, my face.
Okay, faces are a great example. So notice that human faces have a lot of symmetries. Like, for example, they have approximate reflection symmetry about an axis that bisects your face along the nose, right? Which means that the space, your instance space, is actually half as large as you thought it would be because, you know, half— knowing half of your face to a large extent is good enough to predict the other half. Right? And many other things like this, right? At a fine level of detail, many of the patterns that, you know, of shape that appear in your face, whether it's on your chin or on your forehead, right? Your chin is not dissimilar to a small version of your forehead, right? And your, you know, the hair— the hairs on your head are all similar to some degree, maybe similar to the ones in your beard, et cetera, et cetera, right? So there's this vast, you know, rich set of symmetries that we can discover and then compose. to then identify a new face with much less work than we had— than we needed before.
Okay. Thank you.
Cats are a great example, number one, because they're very popular, right? You know, there's— cats are the number one subject of videos on YouTube, which is why there's the Google Cat Network. But also because cats are so damn hard because their body can change in such complicated and unpredictable ways. Even today, you know, no one really has a good cat classifier, but I think we're going to deal with symmetry-based learning.
Maybe I can ask about interpretability. So there's, you know, in the engineering sciences there's more and more pressure on sort of explainable AI interpretability of the models that you get out. I'm just kind of curious of your thoughts on, you know, the symmetry for instance is a very important one for engineering because a lot of physical systems have symmetries, but I'm just kind of curious of a broader view of what you think about that.
So interpretability is crucial for several reasons. One is that— some of them widely appreciated— is that people want interpretable answers for obvious reasons. And in some cases, it's the law, whether you like it or not. But a less appreciated aspect is that interpretable is also very important for the machine learning developers and researchers. Because if I don't understand what the model is doing, I don't know how to improve it. And I think this is a lot of what has held neural networks back for 30 years. In a way, it's embarrassing that we didn't discover 30 years ago some of the things that we only discovered in the last few years. So interpretability is really important even for just making progress in AI. And that has always been one of the guiding goals of my research. So for example, one of the big goals of Markov logic networks is to allow people to build models without having PhDs in machine learning. What you should do— and this is actually what we have done— is we just ask people to write down what they know about the problem. This is converted into first-order logic. Initially, we did it by hand, but now we can do it automatically, right? And then you can go— this is the best part— you can have a loop of interaction with the system that is not, oh, let me hack another hyperparameter or hack another variation of the architecture, but like, oh, this assumption was false, let me remove it. Here's another assumption that I see you're missing. This happened, right? So the progress even in a specific application happens by this interaction, and that's what we want to support. SPNs, as I gave another example, are— this was actually not originally intentioned, but then it turned out to be— the interpretability turned out to be a very powerful thing. And of course, a lot of the motivation for symmetry-based learning, some of it is mathematical, but a lot of it is that humans use this. Exactly how they use this is an interesting question. Maybe we don't use it in the same way. But if you want to communicate with humans, It's good if your models, you know, are based on similar ideas to how people think in terms of. And, you know, one thing that I found out, you know, like talking about, you know, the master algorithm to all sorts of people is that of all the different machine learning paradigms, the one that really resonates with people and that they find most intuitive is not deep networks or graphical models or any of these things or first-order logic. It's reasoning by analogy. And reasoning by analogy, what is it? It's mapping one problem to another using precisely a composition of these transformations. which is things that were done in a more ad hoc way, you know, years ago, but now we can actually do it much better.
Okay, other questions? Yes.
Yeah, so in game theoretic learning, how do we actually like decide what kind of underlying game theory models are we dealing with? Like usually in standard game theory mechanism design, they kind of assume a model is And then there's kind of some parameters in order to get the true values of the model. But if we don't have an idea about the model, then how do we start this game theory game?
Right. That is the question. So here's how I formalize this problem. We have 2 players. One of them is the learner and the other one is the adversary. And each of these players has a payoff function. And they have costs. I have costs for measuring features and you have costs for modifying features. And then we are each trying to maximize our payoff, maximize our utility. And now let's take spam, for example. You generate data. I classify it together with data that wasn't generated by you. And now we find there's a linear program that solves this problem for you, the adversary. And then based on that, I can find my solution. And then we can iterate this. So this is how we formalize the problem. And now there are, of course, many different instances that will depend on what the data is and what the— model classes, right? If you know what it is, you can exploit it, and what the payoffs are, right? Depending on the cost, for example, if features are all cheap to measure and hard to modify, I win. But in the other case, you win, right? So then the data will dictate what these are.
OK, let's take one last question. So, Seth?
So sorry, by the way, before I forget, if there's any questions that you didn't get a chance to ask today, Or you'd like to talk about research ideas or anything, I'm having office hours tomorrow all day in my office in the Allen Center across the street from here. So stop by.
Yeah, I was going to mention this. Yeah, so anybody who has— you can sign up on the web if you're part of CSE or—
Just walk in.
Yeah. So Zach, for the last.
With the Markov logic, what happens if we grow the cube and extend a second and Higher-order logics.
No, very good. So we have done that. In fact, almost all applications of Markov logics that we've done eventually wind up involving second-order logic. Not full second-order, but logic with predicate variables.
So I can quantify—
Yeah. And I can learn, right, over the predicates just— because, for example, in language, the predicates are the verbs, right? And I want to learn over the verbs just like I want to learn over the nouns, right? So this winds up being very common. And the good news is at the formal level this actually doesn't change much. You now just ground over the possible predicates like you ground over the possible objects. At the inference level, of course, now this becomes harder, okay? Full first-order logic is very hard, which is why most people don't do it. But the level of second-order logic that we found useful, which is predicate variables, actually there's a straightforward generalization of probabilistic theorem proving that can handle that.
Please join, join me in thanking Pedro.
Thank you.
