Unifying Logical and Statistical AI with Markov Logic
Pedro Domingos presents Markov Logic Networks (MLNs) as a unified representation that combines first‑order logic’s expressive power with probabilistic reasoning’s ability to handle uncertainty. He introduces the core idea of turning logical formulas into soft constraints weighted by real numbers, yielding a log‑linear probability distribution over possible worlds. The talk explains how an MLN, together with a set of domain constants, grounds into a Markov network where each grounding of a predicate becomes a Boolean variable and each grounding of a formula becomes a feature (edge) with its weight. Domingos shows how MLNs subsume pure logic (infinite weights) and many standard statistical models (by using zero‑arity predicates), and how contradictions are gracefully handled. He then addresses the major computational challenges: grounding explosion and inference, introducing lifted inference and probabilistic theorem proving that exploit symmetries to reduce complexity. Learning is covered in two parts: (1) weight learning – generative maximum‑likelihood via gradient descent (with pseudo‑likelihood as a tractable surrogate) and discriminative learning using structured perceptron / MAP inference; (2) structure learning – operators for adding/removing literals, flipping signs, evaluation via pseudo‑likelihood plus priors, and various search strategies (beam, shortest‑first, genetic). To achieve industrial‑scale performance, Domingos describes a tractable sublanguage (Tractable Markov Logic) with three rule types (subclass, subpart, relation) that yields linear‑time exact inference even on millions of objects and billions of parameters, demonstrated on a DBpedia/YAGO‑derived knowledge base. He concludes with a survey of applications (NLP, robotics, social networks, biology, personal assistants) and points to resources (paper, book, Alchemy system).
Chapters
Hi, I'm Pedro Domingos, and I'm going to talk about unifying logical and statistical AI with Markov logic. Intelligent systems must be able to deal with the complexity and the uncertainty of the real world. The language of choice in AI for dealing with complexity is first-order logic, and the language of choice for dealing with uncertainty is probability. So in order to make progress towards really good AI, we need to be able to combine the two, and that's what this talk is about. How do we combine first-order logic and probability into a single coherent representation language? And then, and equally important, once we have that language, how do we learn and reason efficiently in, in it? And the basic idea that I'm proposing is very, very simple. It's the following. You can think of a logical knowledge base as a set of hard constraints on the set of possible states the world could take. As soon as one constraint is violated, the world becomes impossible, and that's what makes logic so brittle. So instead of that, what we can do is we can make those formulas in the logical knowledge base be soft constraints, so that when a world violates a formula, instead of immediately becoming impossible, it just becomes less probable. And we're going to give each formula a weight, such that a higher weight corresponds to a stronger constraint. And then the probability of a world is just the exponentiated and normalized sum of the weights of the formulas that the world satisfies. Very simple idea. Let's make it a little bit more concrete. So a Markov logic network, or MLN for short, is a set of pairs f, w, where f is a formula in first-order logic in the, you know, with the standard syntax and semantics, And w is a real number. Together with a set of constants representing objects in the world, an MLN defines a Markov network, an undirected graphical model representing a probability distribution, with one node for each grounding of each predicate in the MLN. A grounding of the predicate means we replace the variables with constants so that it becomes, you know, it refers to concrete objects. And we define a set of one feature for each grounding of each formula in the MLN with the corresponding weight. So this is a bit of a mouthful. Let's look at a, at a simple example to try to make, you know, it more, more intuitive. So think about smoking. Smoking causes cancer and we want to combat it, but it's hard to get people to stop smoking because they're influenced by the people around them. If your friends don't stop smoking, then you are unlikely to stop smoking as well. What this graph illustrates is the reduction in smoking from the '70s to, to, you know, to the 2000s. And you can see that there's less smoking, but, but, you know, the smokers that are still there are in clumps. They're clustered. So we want to be able to model that influence in order to know how to intervene. So there's a social network aspect involved. So let's start by making 2 simple statements about this problem in natural language. Smoking causes cancer. And friends have similar smoking habits. And we can translate this into logic as follows: for every x, smokes implies cancer, and for every , friends implies that smokes is equivalent to smokes, i.e., if they're friends, either both of them smoke or neither of them does. Now, this translation is very straightforward, but there's a little problem here, which is the statements in English were true. And the statements in logic are actually false because not everyone who smokes gets cancer, and certainly not all pairs of friends have the same smoking habits. Now we can turn this back into true and useful statements by turning this small knowledge base in first-order logic into a Markov logic network by assigning weights to the formulas, where a higher weight corresponds to a, to a stronger regularity. So, so smoking is more likely to cause cancer than friends are to have similar smoking habits, so that formula is going to have a higher weight. So this here is now a very simple MLN, or Markov Logic Network. But what does it mean? What is the probability distribution that it represents? Now remember, in order to represent a concrete probability distribution, we have to combine this with a set of constants representing objects in the domain. So let's suppose we just have 2 2 people in the domain, Alice and Bob. And now what we're going to have is one grounding of each predicate for each constant. So for example, we're going to have smokes of Anna. Smokes of Anna is just a Boolean variable that is true if Anna smokes and false if she doesn't. And similarly for Bob, and similarly for cancer. Now, what about friends? Right. If I have 2 constants, friends has 4 groundings. One of them is friends Anna Bob. Another one is friends Bob Anna, because friendship is not necessarily symmetric. You know, Bob could be a much better friend of Anna than she is of Bob. That actually, you know, is quite common in real life. And we also shouldn't forget friends Anna Anna and friends Bob Bob, which are also valid groundings and maybe correspond to their, you know, self-esteem or something. Now what we have now is just a bunch of Boolean variables. And now we can set up a probability distribution over these Boolean variables. And how does that happen? We're going to have a feature for every grounding of the formula with each set of, you know, variables that the grounding of the variables in the formula with the constants in the domain. And each feature is going to set up an edge. In the graph. So for example, smokes x implies cancer x has 2 groundings, one for Anna and one for Bob, and you get the corresponding edges between smokes Anna and cancer Anna on the one hand, and smoked Bob and cancer Bob on the other hand. The edge between smokes Anna and cancer Anna just means that these variables are directly dependent on each other. What about friends? Well, friends, there are 3 predicates that appear in the formula friends xy implies And so what that means is that I'm going to have edges between all 3 of those predicates, so it's going to set up a triangular clique. So there's going to be a clique between smokes Anna, friends Anna Bob, and smokes Bob. Similarly with, you know, friends Bob Anna. And there's also going to be a degenerate edge, which is, you know, just for the case of, you know, friends Bob Bob and friends Anna Anna. So now here what we have is a graphical model. It's a Markov network. And what is the probability distribution that it represents? Well, notice the MLN itself, and in fact this is a big part of its power, is just a template for building a ground Markov network that will build different ground Markov networks corresponding to different sets of constants. Once we have those constants, the probability of a world is just a standard log-linear model, right? It's just a standard Markov network. The probability of a state x is just 1 over z, where z is the partition function, the normalizing— normalization constant, times the exponentiated sum over all the formulas of the weight of the formula times the number of true groundings of the formula in that— in a particular state of the world. So if a formula has more true groundings, then the world becomes more likely. So as more smokers get cancer, the world is more likely and vice versa. So if there's a smoker that doesn't have cancer, that doesn't make the world impossible, it just becomes— it just makes it less probable. So we have this graceful degradation where things become less probable as you have, you know, more and more violations of the constraints, which is exactly what we want. Now this is nice that distribution is well-defined and this is very powerful potentially. Of course, you might be thinking this is not going to be very efficient because the size of the domain is going to be exponential, and so this is— and, you know, the number of substitutions that you have of the variables by constants, and so this is going to blow up very quickly. Now, we're going to look at, you know, what are all the things that you can do, or at some of the things that you can do to make this efficient, but the first and very simple one is to just have typed variables. So if you have a predicate like works for x y, you only need to replace x by people and y by companies or other organizations. And this already really cuts down on the number of groundings that we're going to have to, you know, put the probability distribution over. Now what I'm going to cover in this talk is just the very basics of Markov logic. Bear in mind that in Markov logic we can also have functions as in first-order logic. Existential quantifiers, the full set of constructs. And even though I'm only going to be talking about finite domains, we can also have, with, with an interesting semantics, infinite and continuous domains again, as in, as in first-order logic. Now that's the representation, and you might ask, so how does this relate to the 2 things that we're trying to unify? First-order logic on the one hand and probabilistic models on the other. Well, first-order logic is actually the limit of Markov logic when the weights go to infinity. When the weights go to infinity, the constraints become hard. You get back to the situation where if you violate even one instance of a formula, the world becomes impossible, which is exactly what we would like to have. But more interestingly, even in the case of finite weights, which is really what, what we're after, The following holds. If you have a satisfiable knowledge base, meaning it's possible to make all formulas true at the same time, and all your weights are positive, then the satisfying assignments, the assignments of truth values to all the Boolean variables that, that make all the formulas true, are the modes of the distribution. So even in the finite weight case, the worlds that first-order logic prefers are still there. They're just the modes of the distribution. They're the points where the states where the probability is highest, and as we move away from them, the probability goes down gradually as we'd like to, as we'd like it to. Now, equally important, the knowledge base doesn't actually have to be satisfiable. In first-order logic, if you have a contradiction in the knowledge base, then anything follows, and you know things just break down, which makes it very hard to build very large knowledge bases. Or to combine knowledge from different sources using the web and things like that. But in Markov logic, there's no problem at all with contradictions. If you have a contradiction between formulas, you just add up the weights and, you know, whatever the highest weight is will have the highest probability. And that's all there is to it. So now it's very easy to integrate, you know, knowledge from different sources with lots of contradictions, maybe even with lots of problems, but, you know, the inference, as we'll see, will tend to produce something Meaningful out of that. What about the relation to statistical models? A very nice feature of Markov logic is that essentially all the standard types of models that we deal with in AI, statistical models, are special cases of Markov logic networks. Markov networks, Markov random fields, Bayesian networks, log-linear and exponential models, maximum entropy models, Gibbs distributions, logistic regression, Hidden Markov models and conditional random fields. These are all simple special cases of Markov logic. In fact, you can set them up with just a few formulas. And, and very importantly these days, many deep architectures, including some of the most popular ones, are also special cases of Markov logic. And they are all obtained by making all the predicates zero-arity. So all your statements that you're making are all about one object. This is really what characterizes traditional statistical models, is that the data is IID. Each object is in its own separate world, and we can do that easily in Markov logic. But of course, as we saw in the social network and smoking example, that's not what we want. In most cases, there are actually dependencies between objects, and in traditional probabilistic modeling, it's very hard to handle that. In Markov logic, it's very straightforward. You can just have predicates with more than one argument, like for example, friends , that set up dependencies between them. So Markov logic generalizes traditional statistical models in that it allows them to be interdependent. And this naturally allows us to model a lot of things in the world like social networks and the web and, you know, the cell and molecules and how, you know, molecular, you know, metabolic networks and so on in a way that we couldn't before. So this is all very nice. It seems to be a powerful and yet simple representation, but it's not of much use unless we can efficiently do inference with it. So let's look at that now. How do you do inference in Markov logic? Well, what is inference? As in, you know, probabilistic models, what we have is some evidence and we want to compute the probability of a query given the evidence. What is the probability that Anna has cancer given that Bob smokes and they're friends and so on? So we want to compute the probability given some evidence, facts that we know, and an MLN and constants, remembering that the MLN and the constants together constitute or define a Markov network. And also bearing in mind that when, when you have evidence, the effect of that is just to compile the, the, the model into a new simplified model where where the evidence has been taken out because it's been, you know, the evidence variables have been taken out because they've just been replaced by constants like true and false. So now we have the probability of the query given, you know, an ordinary Markov network, and we can use any probabilistic inference algorithm to compute this, like Markov chain Monte Carlo, belief propagation, and so on. There is, however, a very big problem with this, is that the ground Markov network is typically going to be far too large for this to be feasible except in toy domains. Because the, the size of the ground Markov network is exponential in the clause arity. So, you know, if you have 1,000, you know, objects and, you know, you know, a clause of arity 3, that's already a billion groundings. So clearly we need something else. So, so what can we do? Well, the key idea here is the idea of lifted inference. In first-order logic, we can make inferences about very large numbers, even infinite numbers of objects using a finite number of steps. using inference at the level of, of sets of objects, not individual objects. So what we want to do is extend that, generalize that to this case where we're combining logic with probability. So let's see how we might do that. So the probability of the query given evidence and an MLN and constants is just the sum over all the worlds where the query holds of the probability of the world. That's all there is to it. Of course, the problem is that there's an exponential number, so you need— A smarter way to do this. But now suppose that the world can be divided into independent subworlds. Like, you know, for example, there's this family here that has a probability distribution. There's another family over there and has another probability distribution. And now the probability of a world, if the subworlds are independent, is just the product over the subworlds of the probability of the subworld. So this, this is a simplification. But now further, and this is where the lifted inference idea comes in, If the subworlds can be grouped into kinds such that all subworlds of one kind have the same distribution, now the probability of a world is just a product over the kinds instead of being a product over subworlds. And it's the product over the probability of a subworld in the kind raised to the number of subworlds in that kind because it's just the same thing multiplied by itself that number of times. Okay? So this now is potentially an exponentially a large decrease in the amount of work that we have to do. Now of course, you know, usually you don't have a lot of independent subworlds in the distribution because what would be the point? But conditioning, this is, this is what's crucial, conditioning tends to create independent subworlds. Once I have evidence, that tends to break up connections and now I look at the remaining pieces and I can see if I can summarize them into, you know, a small number of kinds. So for example, here's a very, very simple example of this going back to the friends and smokers world. Let's suppose that, you know, I condition— so I condition on smokes x, right? So I condition on smokes Anna and smokes Bob. So those 2 variables disappear because they are now constants. And importantly, the edges connecting those variables to other variables also disappear. Which means that where before I had one very complicated network, now I just have a bunch of independent Boolean variables. And now inference is much easier. And now further, if let's say, you know, Allison bought both smoke, or if neither does, if they're the same, then I have only 2 kinds of worlds, or 2 kinds of variables. I have friends and above, the green ones shown here, and the red ones. Friends Anna Bob and friends Bob Anna, friends Bob Bob and friends Anna Anna all have the same distribution. And, and cancer Anna and cancer Bob all have the same distribution as well. So if I want to compute the probability of a state of these variables, all I actually have to do is, if you look here at the lower right corner, is raise the probability of cancer to the power 2, so square it because there's 2 instances of that, and raise the probability of friends x y to the power 4. So now what, what, what before was a very, very large computation now is actually a very, very short one. Of course, this is what happens on a good day. On a bad day, things don't simplify as much. So for example, if Anna smokes and Bob doesn't, or vice versa, then actually you have 4 kinds of worlds. Friends Anna Bob and friends Bob Anna are one, but now cancer Anna and cancer Bob are different, and so on. In practice, what's usually going to happen is that you're going to be somewhere between these 2 limits, meaning I don't— again, as in first-order logic, where for some things you need to use constants, And for other, you know, with substitutions and so on. And for others, you know, you can stay at the class level. The same thing will happen here. So in the worst case, this is still going to be exponential. But in the best case, the cost of the inference is going to be order of the size of the Markov logic network, which is a very small thing typically, or at least much smaller than the full network. It's not going to be of the order of the size of the ground Markov network. So we have, you know, there's been a lot of research in all of these things. A lot of it has been very nicely synthesized in this procedure that we call probabilistic theorem proving, which as the name implies is a generalization of theorem proving to cover the probabilistic case. And the beautiful thing about this theorem proving, the basics of which I just described to you, there's of course many more details, is that, is that it has essentially all the major types of inference in AI as special cases. If you look at this diagram here, in the lower left-hand corner you have propositional theorem proving, which is equivalent to satisfiability testing. This of course is obviously covered. And now we have 3 axes: counting, weighting, and lifting. If you want to count the number of, for example, solutions of a logical formula instead of whether just saying whether it's satisfiable or not, you get the model counting problem. This is of course included in the probabilistic theorem proving. If you want to— if you want— if the formulas are weighted, you actually get weighted satisfiability, which is equivalent to doing MPE, inference in graphical models, or finding the most probable explanation. If you combine those 2, you now have weighted model counting, which is equivalent to probabilistic inference. You know, typical inference in Bayesian networks and so on, and Markov networks, is weighted model counting. And that's of course just the propositional case of probabilistic theorem proving. But now each of these things we can lift to the first-order level in using lifted inference and reasoning at the level of sets of objects. So if you lift basic theorem proving, you get just, you know, ordinary first-order theorem proving. If you lift the weighted case, you get lifted weighted SAT. And if you combine that with counting, now you actually have the full-blown probabilistic theorem proving, which is really just lifted weighted model counting. So with this one procedure, by making the appropriate choices, you can do all the different kinds of inference that you usually want to do in logic, from pure logic, you know, theorem proving, propositional inference, or to full-blown probabilistic inference, to the combination of the two. What about learning? So it's— we have a good representation. We actually at this point able to handle, you know, fairly large domains efficiently in terms of inference. But we need to be able to learn these networks from somewhere because, you know, just setting them all up by hand will, you know, first of all, be very time-consuming. And second of all, people are not very good at coming up with weights. Even if they're good at coming up with formulas. So for learning, what's going to happen is that the data, instead of just being one table as in traditional machine learning, is going to be a relational database. It's going to be multiple tables with objects that appear across them and can be joined and so on. So now, again, in a more general setting, we will still have the old one as the special case where we have a single relation. And in this talk, I'm going to make the closed-world assumption, which is that every relation that is not in the database is assumed to be false. This is appropriate in some domains, in others it's not. So in others, you know, if something is not in the database, you just don't know if it's true or false. And we can also handle that case using EM versions of the algorithms that I'm going to describe. But I'm not going to go into that for the sake of time. And now there's 2 major tasks, as always in machine learning. There's learning the parameters, which in this case are the weights on the formulas. That can be done generatively or discriminatively, and we're going to look at each of those in turn. And then more ambitiously, there's learning the actual structure of the formulas. You know, like what are the formulas that hold in this domain? And then there's other things like predicate invention, you know, hidden variable discovery and so on, transfer learning, etc., etc., that have also been done in Markov logic, but I won't go into those. So let's start with generative weight learning. So here the goal, as usual, is simply to maximize the likelihood of your training database. And we can just do that using gradient descent. And the nice thing is this is a convex optimization problem, so there are no local maxima. And in fact, the gradient has a very intuitive form if you work it out. The derivative of the log likelihood— of the log likelihood with respect to a weight is just the difference between the number of true groundings of the corresponding formula in the data and the expected number of true groundings according to the model. So if the model predicts that a formula is going to— is true more often than it really is in the data, then its weight needs to go down. If it predicts that the formula is true less often than it really is in the data, then its weight needs to go up to increase its probability. And once the predictive and empirical probabilities line up, For all the formulas, then we're done. We've achieved the maximum likelihood solution. So this is all very nice, but there's one big snag, which is computing the expected number of true groundings of a formula according to the model requires inference. And inference, as we saw, is, you know, worst-case exponential, and we have to do it at every step of gradient descent. So usually just doing this in the way I described here is not going to be feasible. We need something else. What might that be? Well, one idea that's a very old one, it comes from, from, you know, Markov networks, it was introduced by Julian Besag in 1975, is to use something that is similar to the likelihood and plays a similar role but is actually efficient to compute. And what he proposed and we use is what is called pseudo-likelihood. So the pseudo-likelihood of a state is just the product over all the variables Of the probability of the variable given its neighbors in the, in the Markov network, given its so-called Markov blanket. And this is nice because it doesn't require inference, right? Computing, you know, this number is just a matter of multiplying a few potentials in the, in the, you know, in the network, the ones involving X, and then summing over the states of X. Very, very easy and very quick. This is also a consistent estimator, meaning that as we get more and more data, the estimates of these probabilities tend to go to their true values. It's widely used in areas like vision and spatial statistics, but of course it has some shortcomings. In particular, pseudo-likelihood tends to work when the chains of inference that you want to do are very short. When the chains of inference are long, this may not work well, and that's not surprising because the learning wasn't optimized for that. The pseudo-likelihood is really just optimizing for chains of inference of length 1, So if we have long chains of inference, it's not surprising that sometimes it's going to give very poor results. So what can we do in that case? Well, in that case, we can resort to discriminative weight learning, which in fact is often what works best just because in general machine learning discriminative weight learning tends to work better than generative learning. So what is discriminative learning is when you know which variables you're going to be querying and which variables are going to be evidence. And so you actually have that as your goal, not just, you know, optimizing the whole joint distribution. So things work pretty much the same as before, except that now we're looking at the probability of Y given X, where Y is the query and X is, is the evidence. And, you know, the formula is the same. The big difference is that now we can approximate the expected counts by the counts In the most probable state of Y given X. As we condition on evidence, the modes of the distribution, which is what makes inference hard, that there are a lot of modes and widely dispersed, they tend to disappear. And often you wind up with most of the probability being concentrated in just one mode. And so what we can do is we can just find that mode using, you know, the corresponding version of probabilistic theorem proving and use the statistics in that mode to, you know, to compute, you know, to compute our expectations. Very simple idea. How do we do this in practice? Well, there's a number of ways. The simplest one is to use what is called a structured perceptron. The structured perceptron was originally proposed for training hidden Markov models by Mike Collins in 2002, and it works as follows. It assumes that the network is a linear chain because that's what a Markov model is. And it starts out with the weights all being 0, and then it does the following for some number of iterations. It finds the MAP state of Y, where Y could, for example, be, you know, what words did you speak, and the observations are the sounds that were heard, right? Typical application of HMMs. So you find the most likely words using the Viterbi algorithm, and then you update the weights as follows. You take a gradient step where to the previous weights you add the gradient of the to add the learning rate times the count of y in the data, right, of each value of y in the data, minus the count in the MEP state that we just computed. And then it would return the average of this— of these values of the weights over all the iterations that we did. Why the average and not just the final value? It tends to generalize much better, both empirically and, you know, there's theorems to that effect. Now, of course, this is just for HMMs. We want to do this for any MLM. So how do we do that? Well, very simple. All that we have to do is replace the Viterbi algorithm by probabilistic theorem proving, by the MAP version of probabilistic theorem proving. And now, you know, I can apply this to any Markov logic network, and now the learning is based on the difference between the counts in the data and the counts in the MAP state that was computed by probabilistic theorem proving. Improving, and the rest of the algorithm can stay pretty much the same. So simple idea, very effective. This is probably the most widely used method for learning Markov logic network weights. Of course, that's just learning weights. You can, you know, it's very common for people to set up an MLN, you know, by writing down the formulas and then learning the weights. That's often a very good thing to do. But we would like to also be able to learn the structure. either from scratch or, or we would like to refine the initial formulas that somebody wrote down. So, so how might we do that? If you think about it, structural learning is a generalization of both the problem of feature induction of Markov networks and of inductive logic programming, and there's a lot of research on both of those that we can draw on. There are some differences here though. One is that we want to be able to induce any formulas in first-order logic, not just Horn clauses, right? In inductive logic programming, typically we're just inducing Prolog programs meaning Horn clauses. So we need to generalize that. Another thing is that in inductive logic programming, typically we use some form of accuracy or entropy as the goal. But here we're learning a probabilistic model and we want the evaluation function to be likelihood. And we can do that. However, the problem is that remember computing the likelihood requires you know, doing inference. And it requires every time that we consider a candidate change to a formula, we need to relearn the weights for the MLM, right? And that itself is not necessarily very fast, so this could actually be very, very slow. Surprisingly, that actually turns out not to be the bottleneck if you just do a couple of simple things. The first one is to initialize the new weights at the old ones because when you change one formula, typically most of the weights don't change at all. And the other one is to use an efficient optimization procedure, not just gradient descent. If you use something like a quasi-Newton method like LGFCS, often this conver— the learning will converge in just a couple of iterations. So surprisingly, the bottleneck turns out to be something else. It's counting clause groundings. When we were doing weight learning, we just had to do that once in the beginning and then we were done. Now here, every time that we propose a new candidate formula, we have to compute its number of groundings. And surprisingly, this is a problem that in the worst case is Sharpie-complete. So, so this, you know, can be a serious bottleneck. But here again, there's a simple solution which is to subsample. We don't actually need to exhaustively count all groundings of a formula. We can just sample some number like say 1,000 enough to give us a good sense of what the true value would be. And this now is much, much, much faster. And, you know, there's efficient procedures like the Karplubi algorithm for doing that, which we use. And as a result, at this point we can actually do structure learning in Markov logic at a comparable speed to what we would do structure learning in standard inductive logic programming, which is still not super efficient, you know, We'll see later how to scale to truly large domains. But it basically means that as far as unifying logic and probability, the inference at this point is actually as good as the inference of either one alone. And often we can also surprisingly get gains from combining the two. Now, so how exactly will the structured learning work? Well, there's a number of things that you have to choose. There's the initial state. If you want to do learning purely from scratch, You can just start with unit clauses and then extend them, or you can start with a hand-coded knowledge base that you now refine. And this is often a very attractive option because it combines the best of knowledge engineering and machine learning. And now there's operators like adding and removing literals, you know, the obvious ones. Also flipping the sign of a literal is very useful because often people write down good formulas but they get the implication in the wrong direction, so you just want to reverse it. We need an evaluation function. The obvious one is pseudo-likelihood because it's the most efficient one to evaluate, combined with a structured prior, right? If you just use pseudo-likelihood, you will probably overfit, as in, you know, learning graphical models. But again, we can have a structured prior as in learning graphical models where you penalize divergence from the initial network. Every time you add or remove an edge, you pay a penalty, and then, you know, you have this trade-off between increasing the likelihood and complexity, very similar to graphical models, tends to work pretty well. And then finally you need a search method. Many different ones have been used. Beam search, which comes more from the world of ILP. Shortest first, more, more from the world of Markov logic networks. Bottom-up, genetic search. People have, you know, published dozens of papers, maybe even hundreds, on different ways to do this. So, We have a good representation. We have efficient algorithms for doing learning and inference in it. Are we done? Well, no, we're, we're not done by any means because this still does not scale to truly large domains. To scale to truly large domains, we need to do what people did in classic AI, which is to come up with tractable sublanguages of Markov logic. I think traditional knowledge representation people came up with sublanguages of first-order logic like, you know, like logic programming and, you know, frame systems, object-oriented systems and whatnot. And we need to do something similar here, you know, in order for this to be scalable and industrial strength, right? We don't want to have to rely on approximate inference in production systems because that's too unpredictable and it requires too much handholding. So we have done that. We, in particular, we've developed a language called Tractable Markov Logic that is a tractable subset of Markov logic, where what we have are 3 types of weighted rules and facts: subclass rules and facts, subpart rules and facts, and relation rules and facts. So this is very similar to classic AI, right? There's going to be a class hierarchy, there's going to be parts and subparts, and we're going to take advantage of that to make the inference efficient. So subclass rules are things of the type, you know, a family is a social unit. A subclass fact is something of the form, the Smiths are a family. A subpart rule is something of the form, a family has 2 adults. A subpart fact is something of the form, you know, the Smiths have as their first adult Alice. And then relation rules just state certain relations that hold, like for example, in every family, every adult is a parent of every child. Notice that this is not always true, right? Some, some adults might not be parents of some But that's okay in Markov logic because we allow exceptions. You know, this is just going to have some weight and hold with some probability. And then finally, of course, we can just have basic relational facts like Alice and Bob are married. And the amazing thing about this language is that even though it's still a pretty powerful language, right, at the level of the traditional knowledge representation languages that people use, the inference time is linear in the number of rules and the number of objects. And this might seem surprising. Why, why is that the case? It's for the following reason. It's that the structure of the knowledge base is actually isomorphic to the structure of the computation that you have to do to compute probabilities and partition functions. In particular, the probability by design, the probability of an object given its class is just a product over the subparts. Of the probability of the subpart given the class. So the problem breaks up into a product of independent subproblems. And the probability of anything given a class is just— it's a mixture model. It's a sum over the subclasses of the probability of what we're interested in given the subclass times the probability of the subclass. So if you draw this as a graph, also known as a subproduct network, you'll see that that graph has exactly the same structure as the structure of the knowledge base. With, you know, subclasses under classes and subparts under parts and so on. So thanks to that, you know, doing the computation is extremely efficient. It's essentially just a sweep through the knowledge base, whatever the probability is that you want to compute. And moreover, most of the time you actually do not need to, you know, recompute everything from scratch. You can select only the subparts of the knowledge base that need to be changed given new evidence or or given a new query. So we've taken advantage of this by building, to our knowledge, the— by far the largest probabilistic knowledge base ever built. We extracted it from DBpedia and YagoNL, all well-known, you know, web knowledge bases, and we built a tractable Markov logic network that has millions of objects and billions of parameters, and yet you can ask any probabilistic query in this language And you get back an exact answer, not an approximate one, in sub-second time. So you can actually query the, the tractable MLN at interactive speeds. And of course there's lots more to say, but let me stop there. There have been many other applications of MLNs in areas like natural language processing, robotics, social network analysis, computational biology. You know, parts of Cyc, you know, the famous, you know, large knowledge base have been turned probabilistic using MLNs. Personal assistants like, like, you know, DARPA's famous Kello project made extensive use of— that Siri came out of— made extensive use of MLNs. And, you know, and more applications continue to appear. MLNs have been used and researched widely. In fact, this body of work is one of the most cited bodies of work in AI of recent times. And they've also been used in industry by all sorts of companies, both tech companies like Facebook and Google and Netflix and other companies. And, you know, and people continue to develop and, you know, both on the research side and on the application side. Application side, they continue to develop Markov logic. So to summarize, to make progress towards AI, we need to unify logic and probability. I would say we have largely succeeded in doing that at this point using— of course, there's a number of approaches, but the most widely used and the most powerful one is Markov logic, where what you have is just ordinary first-order formulas with weights. That represent a probability distribution over the groundings of the formulas. We and many others have developed a series of powerful inference and learning algorithms for Markov logic, and I think we now have something that is potentially a good foundation for modern AI. Instead of just starting from either logic and then hacking things, or from just probability and then hacking things, we actually can now do this all in a consistent, clean, and powerful way. Of course, there's much more still to do. And, you know, we'll see what the future brings. If you would like to find out more about Markov logic, I recommend you look at this recent article in Communications of the ACM. There's also a book. It's a little bit out of date now. There's several things we covered here that are not in the book, but it's still a very good introduction. There's also a number of open-source implementations of Markov logic. One of them is Alchemy. Alchemy is also a website. The URL is, is right here where you can go to find MLNs, datasets, pointers to the literature, publications, both Alchemy and other systems. So I recommend you take a look. Thank you for listening, and, and I'll take questions now. Hi, Pedro.
