Sum-Product Networks: Powerful Models with Tractable Inference

Each year, Microsoft Research hosts hundreds of influential speakers from around the world, including leading scientists, renowned experts in technology, book authors, and leading academics, and makes videos of these lectures freely available.

Okay. It's a pleasure to have Pedro with us. Pedro is at the University of Washington and has done a lot of excellent work on relational learning and knowledge-based representations for learning. He's going to talk to us today about some new work on inference in tractable networks.

All right. Thanks everybody for coming. Please feel free to ask questions at any point if you have them, OK? So I'm going to talk about sum-product networks, a new class of models that are quite powerful and yet still allow for tractable inference. This is work that I've done at UW with my students Rob Gens and Hoifung Poon. Hoifung is actually at MSR Redmond right now. So some of you might even have met him. I will start with some motivation. And then I will define some product networks and look at how we can learn them, both learning weights and structure and learning weights discriminatively and generatively. And then as time allows, I will have some discussion. And again, several of these things can be abbreviated. We can have more questions or fewer. So this is all flexible. So here's the motivation. We live in the age of big data. And the point of big data is that we can learn very rich models of whatever we're interested in. However, rich models means you have complex interactions between the variables in the model. And complex interactions lead to intractable inference. Meaning it becomes very computationally expensive to answer questions like, what is the probability of this given that and that? And this is bad enough, but it gets even worse for the following reason is that in most learning algorithms that learn rich models, inference is a subroutine. So as you're learning, you have to repeatedly do inference. So if inference is intractable and it's done many times inside learning, then learning becomes very tough. In particular, you have to use approximate inference. And the approximate inference and the learning interact badly. And life becomes very, very difficult. And so what really happens today is that despite all the big data excitement, for the most part or almost entirely, people do not actually learn what you genuinely call rich models. What they learn is very large simple models. Like for example, you can do a linear regression over 100,000 variables with 100,000 predictors instead of 100. Big data, but it's still only linear regression. And what we would actually like to do is learn truly rich models from big data. Because after all, the data is there and probably allows us to do that if we can only figure out how. Here's just one motivating example, a very popular example these days, social networks. So this is a graph of a social network of people. Each link is friendship or family ties. And this is how many packs of cigarettes they smoked a day. And what happened between 1970 and 2000 is that many fewer people are smoking. And traditionally, you'd model things like, what is your probability of smoking given your properties, right? Your propensity to smoke. But the thing that really drives people's smoking habits is whether their friends and acquaintances smoke. If you're a teenager and most of your friends smoke, you're going to start smoking as well. And that is actually what's hard to model because now, instead of each of these guys being an independent point, a person with their properties, It's all one big network. And now whether this person smokes is going to ultimately influence whether that person smokes as well. And so life now has become very, very tough. So on the one hand, we really want to model these things. And that's what potential we have the data to do these days. On the other hand, modeling them is going to be very, very difficult. So what can we do? Well, the most powerful or sort of like the standard powerful type of model that we can build these days is what is called a graphical model. How many people here are familiar with graphical models like Bayesian networks and MRFs? That's most of you, which is good. So I will go over this background briefly. But again, if at some point you're missing something, we can go back to it. So there's things like Bayesian networks, which there's a node for each variable. And then there's arrows pointing from some nodes to others, which roughly speaking represent some sort of direct dependence between them. Markov random fields are similar except the— except the edges don't have arrows. And lately, there's a very new, powerful, very popular type of model which can be viewed as still a type of graphical model, which is deep architectures. And deep architectures, what they have is they have a lot of layers of hidden variables, which is potentially very nice for modeling the real complexity of the world, all these hidden variables. But then you have to get at them. And the advantage that these representations have is that they're compact. You can model phenomena with a Bayesian network that is not very large and yet is actually quite rich because it can have arrows going anywhere. And you get even more compactness if you go to deep architecture. However, compactness of the representation is just one aspect of the problem. Then you also want to be able to do the inference efficiently. And by doing inference, I mean things like answering questions of the form, for example, here's a famous example. The alarm in your house will go off if there's a burglar. That's what it's for. But it may also go off if there's an earthquake. This example comes from Huda Pearl, who lives in LA, and this makes a lot of sense. So you might want to compute, for example, the probability of burglar given alarm. The problem is that in order to do that, you have to sum out earthquake. And if instead of earthquake, you had 1,000 Boolean variables, you would need to sum out over 2 to the 1,000 states. And that's what the problem is. So And in general, there's no efficient way to do that. So the conventional wisdom is that inference cost is exponential in the tree width of the graph. What is the tree width of the graph? Without going into details, if you think, for example, of an image where each pixel is a variable and each variable depends on the variables above, below, and to the left and right, the tree width of that graph, if the image is 1,000 by 1,000, is actually 1,000. Because you have to define one entire column of variables to make the 2 remaining halves of the image independent. And this is extremely bad news because if the inference cost is exponential in 2 to the 1,000, it's not going to happen in this universe. So what can we do about that? What we do is approximate inference. But now what happened? We can't do it exactly. So we use approximate methods like Markov chain Monte Carlo, belief propagation, variations, approximations, and so forth. And that in itself is already a problem because that inference tends to not be reliable. It takes a PhD to know how to make it work. It may give bad results. It may still take a long time, et cetera, et cetera. But it gets worse when you actually try to learn these models. So how do we learn these models? The high-level idea is really this, is that we want to learn the parameters of the model such that the empirical statistics, for example, how many people smoke, smoke and have cancer or how many alarms go off and there's a burglary and so on and so forth. You want the empirical statistics to match the predicted statistics. The model predicts that 80% of people who smoke will get cancer. But if in practice 90% of them do, then something is wrong with the model and it needs to be adjusted. So if I can match the empirical and the predicted statistics, then I'm good. Then I've learned a good model. The problem is that to compute the predicted statistics requires doing exactly the kind of inference that's intractable. I need to know what the model tells me in order to compare it with what the data tells me and adjust accordingly. And this is where all hell breaks loose. When you combine this with the fact that you have to do approximate inference— so first of all, the inference is approximate. So this is actually going to be unreliable. You're not actually going to get accurate values here. A lot of the time. Moreover, typically there is no closed-form solution for this problem. So you have to do some sort of optimization, gradient descent or quasi-Newton or something like that. And moreover, as long as there are hidden variables in the problem and in rich real models, there are almost always important hidden variables. You can't get rid of them. Then there is no global optimum. It's not a convex optimization problem and there isn't a single global optimum. When you combine this with the fact the inference is approximate, learning becomes very hard indeed. Even for those of us with PhDs in the subject, it's often too hard, let alone for people who are not experts.

What do you mean by there's no global optimum?

So let's say— pardon me?

Does it mean you can just go off arbitrarily?

No. What I mean is think, for example, of the likelihood as a function of the parameters. Right? No global optimum means like, here's my— let me call my parameter w. It means something like this.

So there's one. So local optimum.

I mean, it's hard to find a global optimum.

No. Sorry, yes. Yes, exactly. There isn't a single optimum. Right? Yes.

But there are local optimums.

Yes. Yes. That would be—

He doesn't mean no global, but he means there are local.

Yeah. You're not saying that there The only global optimum is that—

Yeah, sorry. Yeah, that language was loose here. What I mean is that there are local optima. So there isn't a single optimum. And so you can get trapped in here when, in fact, you wanted to go over there. And then that's the problem. So what can we do about this? Well, people have looked on many different ways to try to combat this. But the one that I'm going to try to propose here, in a way, I think, is taking the bull by the horns. Which is let us actually define a new representation where we can solve this problem. But yet, let's make that representation as efficient as possible for inference. So think of the space of compactly representable probability distributions. Some probability distributions can be represented compactly as, say, a Bayesian network, and some can't. So let's say this is the space of probability distributions that can be compactly represented as Bayesian networks or Markov random fields or deep models or whatever. Most of them are intractable. So they're trouble. There is a small subset here of models that are tractable. And these, in a sense, are good because now the inference is no longer a problem. These are things like mixture models, hidden Markov models, things that are very, very limited in what they can express. What I'm going to describe here today is a new class of models called sum-product networks. That first of all, compared to graphical models, it has an intersection in the sense that some things are compactly representable as both graphical models and sum-product networks. There are unfortunately some things that you can represent compactly as graphical models but not as sum-product networks because there's no free lunch. On the other hand, there are also many things that we can represent compactly as sum-product networks that you cannot represent compactly as graphical models. In particular, Graphical models depend on conditional independence. If there's no conditional independence, then your data is all— your graph is all one big clique, and all hell breaks loose. In some prior network, a typical some prior network actually is all one big clique. So if you looked at it as— if you look at the corresponding graphic model, you would think it was completely intractable. And yet, it's still compact. But of course, the more interesting thing is that this here is intractable inference. In the case of some prior networks, this entire space is all tractable inference. You no longer have to worry about the tractability of inference. It's linear in the size of the network. In the case of graphical models, the inference could be exponential in the size— in the number of variables in the network or in the number of nodes in the network. Here, the inference is always linear in the number of nodes in the network. So doing inference is basically just evaluating the network. It's never harder than that. You can do it on a very, very large scale. So how do we do that?

Question. Can you define compactly representable? Like a number of edges polynomial in the number of nodes or

something? Can I define what?

Sorry. Compactly representable.

Yes, think— exactly. Think of it as the number of edges. That's actually the better thing. It's not the number of nodes. It's the number of edges.

Polynomial in the number of nodes or something.

So a graphical model has nodes and edges. And inference is not tractable because it can be exponential in the number of edges in the network. In the case of some prior networks, inference is linear in the number of edges in the network. Our inference is order of the number of edges in the network. And that's what doesn't happen over in the case of graphical models. What do

you mean by inference? Does inference mean calculating the partition function? Does it mean calculating the probability of a given event? Does it mean—

It's conditional capability.

Giving me a sample. So what if I asked you to give a sample from the—

I mean all of the above. Every one of those can be done efficiently in a semiparametric network. The example that I had here was computing marginal conditional probabilities. But the same— and so here are things that are efficient for— we will see this in a little bit. But computing the partition function is tractable. Computing arbitrary marginals and conditionals is tractable. Generating samples is tractable. And computing MAP states is also tractable. So all the things that we usually want to do with probabilistic models are tractable in the case of some prior networks. And then you have time. All in linear time in the size of the network, exactly. Yeah. So that's good, right? But you're probably wondering, well, you must be sacrificing a lot to obtain that. And the whole idea in semiprogram networks is to answer the question, how little can I sacrifice while still guaranteeing this? I want to guarantee that inference is tractable, but do I really have to be this restricted? And the answer is no. There's a whole universe of things out there that we can do while keeping inference tractable. Yeah?

So are there new graphical models that you're now able to show tractable? I mean, just to see if this diagram is just— there's space outside the existing tractable models which is inside some product.

This space, yeah.

No, no, no, inside the graphical, in the intersection.

No, oh, this. What is an example of this?

No, in the intersection.

Oh, this. Oh, yes, I see. Yes. Models that are not existing tractable models, but I don't know. That's why I left that open. Right? I would guess that probably, right, this is probably non-empty. But I don't have a ready example for you. And again, you're like, why worry about— I mean, it's an interesting theoretical question, right? But the goodies are over here. All right. So what is a sum product network? A sum product network is defined recursively. A univariate distribution is a sum product network. So for example, if my variable is Boolean, my variable x is Boolean, like a Bernoulli distribution would be an example, or multinomial for discrete variables, or a Gaussian if it's continuous, or Poisson, or whatever univariate distribution you have is fine. In fact, what we really require is not that the distribution be univariate, but that the mode and the partition function of that distribution be efficiently computable. You could actually have many variables. What has to happen is that the individual distributions that you're combining themselves should be tractable. And in fact, as long as they're tractable, they could be anything that you want. What we're going to do here is combine tractable distributions into much richer, much more complex distributions that are still tractable. So how do I do that? By combining 2 things. A product of sum product networks over disjoint variables is still a sum product network. OK. So what this means is that if I have a distribution over my variable x here, and I have a distribution over my variable y, I can just take the product of the 2 and call that an SPN. And what that means is that basically I said that this variable has its own distribution that's independent of this distribution over here. So this is just an independent model. It's not very exciting so far. But remember that where we're going with this is that this could actually be a wholesome product network. And there could be more stuff on top of it. So if we actually want to represent dependencies, then what do we do? Actually, we just do a mixture model. So the other thing that a sum product network can be is a weighted sum of sum product networks over the same variables. So for the product, they have to be over disjoint sets of variables. For the sum, they have to be over the same variables. And we will see shortly why this has to be the case. But the meaning of it should be fairly straightforward. It's like, here I have an independent model of x and y. And here I have another independent model of X and Y. But now I can combine them with a weighted sum. And now they are no longer independent. And remember, this X doesn't have to be any varied distribution. It could be a big sum product network that's already over a very large number of things. So this is just a mixture model with the mixture components being sub-SPNs. In fact, for a lot of things, a good way to look at a sum product network is everywhere you see a sum node, Think of it as the result of summing out a hidden variable. So for every sum node in the sum-product network, there's a corresponding hidden variable that you've effectively summed out. Any questions so far? All right. So this definition is very simple, right? It's powerful because now you can recurse arbitrarily. I can do sums of products of sums of products up the wazoo. I can build up networks with millions or billions of nodes very easily. Okay, just by combining these things. And what we really have— For

the sum, you need the 2 parts to have the same variables. In the recursion, it's not trivial how you do that. I mean, you can't just take any 2 things and put a sum.

No, but I can check whether they share no variables.

For the sum, don't they have to share all variables?

No, sorry, for sum, no. Yes, they have to be over the same variables. So what I need to know is for an SPN is what variables it's over, which, you know, Presumably I know. And then when I'm trying to decide whether I can combine 2 SPNs with a sum node, right? I have to check whether they're over the same— whether the variables are the same. If they're not the same, for example, I can pad it out with independent models for the variables that weren't covered. In fact, in some extensions of SPNs we do that. If they're disjoint, I can do a product. If they're the same, I can do a sum. If they're neither, I need to somehow turn it into this. And in fact, this is what the junction tree algorithm is doing. So

So in this picture over here, why do you have 4 copies of x and 4 copies of y?

Oh, this is just for display purposes. Yeah. This could just be one x, but then the graph would be black. It would be what Mark Newman calls a ridiculogram. Yeah. So this, if you want to just think of this as one, yeah. So in particular, some product network doesn't have to be a tree. It can be a DAG. This is one of the things that gives it power is that nothing says that I can't reuse the same SPN 500 times if that's what I want to do. So, so far the definition is simple, right? It's potentially powerful in the sense that, yeah, you can build very complex models in this way. But now there's 2 questions, right? The first question is like, OK, but my promise here was that the inference is going to remain tractable, right? Why does the inference remain tractable? Actually, the reason— the theorem where we show that inference remains tractable is like— It's less than a one-column proof, right? And here's why it remains stratagem. And hopefully I can give you the basic idea right here. So claim 1, all marginals can be computed in linear time, right? For example, let's suppose that I have a distribution over x and y. And each of them has 3 values, 0, 1, and 2. And I want to compute the probability that x is equal to 0, right? I need to sum out y. I need to marginalize over y, right? How do I do that? And in particular, if I wanted to compute the partition function, it would just be summing out all the variables, right? So computing the partition function is a special case of computing marginals. It's a special case where you marginalize over all the variables, OK? So how do we do this, and why is it going to be tractable? Well, let's play this through the recursion. Let's suppose that x just had a univariate distribution, right? Then by hypothesis, x was just a little multinomial over these 3 values, right? Then in that case, I know how to compute the probability that x is some zeros. I just read it from the distribution, OK? And now let's suppose that x— what I actually have is a distribution over x and y, but they're independent, OK? Well, again, life is easy because I can just— these 2 things factorize, right? They factorize into 2 different distributions of different variables. I can just take my value over here and multiply it by the sum of values over there, which if the distribution is normalized is just 1. So this is what the product node buys me. And this is why I want it to be over disjoint variables because that's how I can factorize it into 2 independent components. So I can do things up to here and things remain tractable. Now what about the sum nodes? Well, what happens in the sum node is that remember, I'm doing a sum over values of y of this sum over mixture components, right? That's all that's going on at a sum node, right? What I want to do is be able to interchange the sum over values of y with the sum over mixture components. And I can do that precisely because the mixture components are over all the same variables. So it's just a matter of— here, what I did was apply the distributive law. And here, what I do is I apply the commutative law. There's nothing fancier than that going on. Notice that if they were not over the same variables, then I couldn't do this. I couldn't just interchange the sum over the mixture components and the sum over the variables because there would be different things in different subsums. And now, well, if this is valid at the leaves and it's valid at product nodes and it's valid at sum nodes, then it must be valid all the way up to the root. So bottom line, I can compute any marginal— Here I was like x was evidence and I was summing out y, but I can have anything be evidence and be summing out anything, right? And it always— and it still works out, right? Notice that what happened over here was that I had one distribution for x here, but I have another distribution for x over there. And in a large sum product network, I could have a whole bazillion of these distributions of x and they're all going to get combined with summing out over whatever the relevant variables are. But a very simple algorithm actually gives you very fast inference on something that could actually be a very, very powerful model. So this is for computing marginals. But a lot of the time in real applications, for example, in language and vision and speech and whatnot, what you actually want is to compute the MAP state. Is say, given this evidence, what is the most probable— for example, given my noisy image, what is the most probable set of segments? That the image is composed of. So how do we do that? Turns out we can also do this efficiently in linear time by the same principle. And in fact, this is going to be quite important for learning, as we will see later. And the way this works is actually very, very simple. It's the following. To do MEP inference, what we have to do is 2 passes through the network. The first path— pass is just going to compute the value of the mode. What is the maximum probability? And the way I do that is simply by replacing the sums by maxes. Everywhere I was taking a sum of the children, I now take the max of the children. And here at the leaves, instead of doing the marginal, I just take the mode. And then the upward pass is exactly the same as before. I take the mode here. I take the evidence value here. The product is the product. The max is the max. And finally, what I get here is the value of the mode. But what I want is not the— so this was exactly parallel to the computation of marginals except with maxes instead of sums. So it's tractable because it's exactly the same algorithm with only sum replaced by max. But this gave me the value of the mode. What actually— I'm sorry.

I'm just making a comment.

You're not done, right?

No, I'm not done yet. No.

So far it's

magic. OK. Let me finish this and then I'll ask your question, right? But what I actually want to know is I want to know what is the MAP state, right? What is the most likely value of y given my x? Now you see this arrow going up. This was the upward pass that computes the maximum, that computes the mode. Now there's a downward pass which is usually called the traceback phase, right? In things like this, if you know the Viterbi algorithm, the Viterbi algorithm is actually a special case of doing this. So What I do in the downward pass is I start from the root. And at each sum node, I pick the highest valued child. And remember, I know the value of each child because I computed them all on my way up. On my way up, I didn't just compute the value of this guy. I computed the value of everybody. So what happens is that at each node, I pick the most likely child. At each max node, I pick the most likely child. And the highest valued child— notice it's not the child with the highest weight. It's the child with the highest value that comes from evaluating the entire network under it. Wow. Okay? So this guy has a weight of 0.4 and this guy has a weight of 0.6, but I'm going this way because if you evaluate this whole network, this value of 0.3 and this is about 0.04. So this is, again, if you think of this as a hidden variable, right? What I'm doing is I'm picking out the most probable value of the hidden variable. Okay? And at each product node, I go to all the children. So what the MAP inference does is it selects out a subtree. It selects out a tree that has 2 properties. The tree is a subgraph of the whole SPN graph. And it accounts for all the variables. And it's a tree. And then when I get to the leaves of that tree, in each of those leaves I pick the mode of the distribution that's there. As a result of which, for example, here I pick this value of y because it was the most likely one. It wasn't necessarily the most likely one over some of the other leaves that I could have reached. And notice that this phase, of course, is also tractable because this phase is actually even faster because all it involves is order of the depth of the tree times the number of children at each node. Yeah?

About the marginal, do you get all of them? Like in belief propagation, you go once and you get all the marginal? Do you get one per iteration for each one?

There is a way to do that which I did not describe here, yes. But there's actually a variation on this algorithm that will compute all the marginals of all the variables at once. All the single variable marginals. Yes, in linear time. Yeah. I mean, it's a slightly fancier thing, but not that much. Yeah. I mean, for purpose of this talk, just imagine that you do one of these computations for each variable. You incur a penalty order of the number of variables, but that's actually— it would be stupid to do it that way. Yeah.

Sorry, I'm a little confused. In the upward pass, you were looking for somehow at each stage which of the children Leads to the largest—

No, no. Remember, what I do in the upward pass— again, if you know Viterbi, this is just like Viterbi. Or if you know junction tree, MAP on a junction tree. In the upward pass, what I'm trying to compute is the mode of the probability. What is the highest value that my probability function reaches? Think of the graph of probability. This is x. And this is p of x, right? And let's say this is distribution. In the upward pass, what I'm going to compute is this value. In the downward pass, what I'm going to compute is the value of x that gave rise to that value.

Yeah, so can you explain how— so what is the upward pass?

Right, so the upward pass is just like computing a marginal except that instead of sums, you do maxes. And instead of marginalizing here, you pick the mode. It's

like Viterbi if you're—

But we don't know Viterbi. Okay, no, yeah. Explain it to us if we don't know Viterbi.

Think of like a unichain, like where you just go forward and backward.

Actually, I mean like exactly. Ignore Viterbi.

Doesn't it like—

Yeah.

This looks like you could explain it without very much—

Ignore Viterbi, right? Think about it this way. If y was alone, if y was alone, right? Then its mode would be this value. Exactly. Good, right? If y was just being multiplied by x, it would still be this value because it's just being multiplied by the constant, right? But now what happens when I have a sum node, right? Is that the winner is going to be the largest value of this multiplied by this or this multiplied by this? And that's what I do, right? This is going to be like 0.6 multiplied by 0.5. And over here, it's going to be 0.4 multiplied by 0.1. It's not just the winner among these 2 because each one of them is now weighted by the probability of x.

So the point is that I really— so if I write sort of in your thing, right, let me call this— Down there, P1, P2, P3, P4, right? So then the probability of an event upstairs would be, let's say the weight is 1/2 between the 2, it would be 1/2 P1 times P2 plus 1/2 P2 times P3.

Exactly.

And the point is that I can think of it as introducing another variable which is sort of one which decides whether I choose the 1/2 Or the other half.

Yeah, that's the hidden variable over here. But remember, we are now maximizing over it, not summing.

Right, and that's why you can think of taking the max, because then if I want to maximize this distribution, I could think of having a distribution where I have another variable which decides I go right or left.

Yeah, and remember, I could be talking about— these are different states, right? Here's y equals 1, and here's y equals 0, right? So this is why I'm trying to pick out the max. I want to decide if the winner is going to be 0, 1, or 2. If I was marginalizing, I would want to sum the probabilities for 0, 1, and 2. Here, I just want to find which one is the max.

So if I understand correctly, what you're computing is probability.

So the max over y of probability that x is 0, that y is little y, and that the hidden variable is something. So you also need to figure out the hidden variable and then you're maximizing over that space.

Good point. So if I really want to think of the hidden variables of these nodes as representing hidden variables, then I'm actually not summing over them.

Right, because—

You're right. You're right.

The expression doesn't seem to be sort of accurate.

Yeah, because that's not what I'm— but if I wanted to do that, I could. So notice, by the way, that I can have any mix of maxes and sums here that I want. OK, now I understand that. OK. What I'm computing here is not the maximum for y summing over all the values of the hidden variables. Good point. But I could do that if that's what I wanted. But again, that's not what we want to do in typical— for example, in Viterbi, to say that type of word for just a second. OK? So in summary, all marginals can be computed in linear time in the size of the network. And all MAP states can be computed in linear time in the size of the network. So the problems that we want to solve actually now are trivially easy. This thing that we spent our time banging our heads against now is not a worry at all. Yeah?

Sorry, going back to the downward case, you might end up, if you have sums of sums, so you end up with a tree at the end.

Then what do you do with all the individuals?

No, remember the tree is one value for each variable. So here there's only one variable and it's y, so I pick 1. But in general, right, I want to find the MAP value of 100 variables. That tree is going to have the property that it has one leaf for each variable. It tells you the value of y. One leaf tells you the value of y1. One leaf tells you the value of y2. There are never 2 leaves telling you the value of y1. That cannot happen. It's easy to show.

But if you did sum over the hidden variables, that would happen, right?

Yeah, of course.

Sorry, can you convince me why this is what you'd like to compute rather than— I mean, in the example where, suppose that

like— Yes, let me—

Here you have a big discrepancy, and suppose that if in the left plot the probability of getting y equals 2 versus y equals 3 were both basically 0.5.

The reason I might want to do this So think of this in terms of junction. Do you know junction trees? Yes. Okay. All that this is is a compact representation of the junction tree, right? You don't think of a junction tree as having hidden variables representing each state of each potential, right? You maximize over them. I'm doing exactly the same thing over here. Okay? So the reason I want to do this is that I want to generalize the junction tree algorithm and Viterbi and all that good stuff. If you really care about those hidden variables and you want to sum over them, then please please do, that is still going to be tractable. But for our present purposes, that's actually, I think, not that important because the standard things that you want to do, and in particular, the way we're going to use this in learning is this way.

So that wouldn't lead to an exponential blowup in the number of hidden variables?

Well, so remember, the inference is linear in the size of the network, right? But the network— when do things get intractable? What happens if I try to represent an Ising model with this is that I have an exponential number of nodes. Exactly. Or if you will, an exponential number of hidden variables. Remember, if you have a distribution over n Boolean variables, you can always represent it as a mixture model with 2 to the n components. And that's what's going on here, except with a very important thing that what I have is like I have 10 components being multiplied by 10 being multiplied by 10. And so I get 1 million components at a cost of 3,000. That's the thing that I'm getting is at the end of the day, you can think of this as being equivalent to a very big mixture model. Except that the mixture model is being very compactly represented by using these factorizations. More questions? OK, so let's— OK, so now a couple of important questions. What does an SPN actually represent? So one of the nice things about graphical models is that if I want to set up a graphical model, I have an intuition about what the arcs represent. I put down nodes representing the variables. And I draw arrows between things that are directly dependent. I kind of have a handle on how to design a model. What is an SPN? Is this just a kind of strange computational device? Well, that's OK because the inference is efficient. But then I don't know how to deal with SPNs in real life. Well, actually, it turns out that SPNs actually have a very natural intuitive meaning, which gives you a very natural way to set them up. And this is what the intuitive meaning is. It's more than intuitive, but let's give the intuition. Is that a sum node— this will not surprise you— is really representing a clustering. Each child of a sum node represents a cluster, except that I'm doing it in a subspace. I have classes over, for example, only x, y, but not z. Or only over x1 to x10, but not over x11 to x100. Wherever there's a sum node, what's happening is a clustering of a subspace. Whenever there's a product, what I'm saying is that I'm combining independent features of the objects in the subspace. The commitment that a product node introduces is that in that context, in the context of all the sum choices that you've made so far, things are now going to be independent. So for example, this is the type of application that we've actually looked at, as you'll see in a little bit, provided there's time. Let's suppose that I want to have a probability distribution over images. And here's a fragment of that represented as an SPN. Representing the probability over images, distribution over images with a Bayesian network or Markov random field is hell. In fact, people don't get very far in trying to do it. They maybe represent some intermediate level of the objects or super segments or things like that. But now think of doing this with a support network. You might start, for example, with a sum at the top that says this is going to be an indoor scene or an outdoor scene. And if in your training data 80% of the scenes were outdoor, then that's going to be 0.8. Then for outdoor scenes, I could have something— well, this is a city scene versus a country scene. Again, a sum node. And now here we are in a city scene. And this is a very simplified example just to give intuition. But now I can say, well, here's what happens— that this scene is composed of 3 3 or 4 or 5 roughly independent pieces. There's the road itself. There's the people. There's the cars. There's the buildings. And there's the sky. I didn't put the sky here. So what happens is I'm now conditioned on that class. If it was an indoor scene, I would say, well, I'm going to decompose into ceiling, furniture, walls, and floor. Here, because it's a city, I'm going to decompose it into people, cars, roadway, buildings, and sky, and maybe trees. And now for each of these guys, I'm going to recursively model it as a mixture of the things that it could be. Like for example, this could be a person riding a bike taxi or a person walking on the street or a person doing whatever. So now I'm going to have again a mixture distribution over what the contents of this subpart of the image could be. And now if it's a person riding a bike taxi as it is in this image, now obviously I can decompose that into the person and the bike taxi. And now when I look at the person in isolation, well, maybe this is a person, but maybe it's a lamp, right? If you actually look at this thing, this is the kind of crap that real vision algorithms do, right? Is that they look at a person and think it's a lamp because the person— this could be a lamp with some noise and some piece of tree that came over from somewhere, right? So now I'm going to have a probability distribution of whether it's a person or a lamp. But then if it's a person, that in turn can be decomposed into the head and the torso and the legs and so on and so forth. So I can build a very rich model of images this way. And again, the inference in these models is always tractable. To compute any probability of any of these things, all you have to do is basically an evaluation or a couple of evaluations of the network. So this, I think, is very important because it tells you how to set up an SPN for some problem that you're interested in dealing with and also how to interpret what you get. When you learn an SPN, you can then go and inspect the summands and go like, oh, This here is a distribution over the kinds of people that I see on the street. Or this over here is decomposing a person into head, torso, and legs.

So it's kind of like— so your sum nodes are kind of like, oh, I'm not sure what this is. It's a convex combination of a person and a lamp. But now my person— now if I know it's a person, then the person has arms and legs. legs and whatever. Exactly. And the lamp has whatever the lamp is.

Exactly, the lamp could be composed, precisely. So the rule is, whenever I'm uncertain, I stick a mixture distribution on it.

Which is, so your uncertainty gives you sums which are clusters over the possibilities, and your products are, now I know what I'm doing, and now here's how.

Yeah, and the products are like in this component now, because it's a person, these, yeah.

I don't have like a leg arm.

Yeah. And now notice the following very important thing that I think you alluded—

I'm not sure if it's a leg or an arm, then—

Then I have further— yeah. And notice another important thing that happens here is that the split on this side could be different from the split on that side. And this is where you wind up with a model that, as a graphical model, could be one big clique. These guys are all dependent on each other unless you know that they are decomposed in this way. Right? There's things that are dependent on this side that aren't dependent on this side and vice versa. So if you ignore this decomposition and just try to build a straightforward graphical model, it all looks like one big clique. In fact, the graphical model for this, for the whole image, is going to be one big clique over all the pixels with 2 to a million states. Yeah?

So how would it deal with an edge case like a person's face?

Person in a wheelchair. What kind of— can you get to that kind of granularity that it could choose, that it could parse out the context enough that you're going to be able to get any sort of either/or out of that?

Yes. So, I mean, I could have— right here where I have person riding a bike taxi, I could have another option that is person on a wheelchair. And then that would in turn decompose into a person in the wheelchair, and the wheelchair would have the wheels, et cetera, et cetera.

Or it could be a person or a robot person in a wheelchair. Or a robot and it's like—

It could be a robot on a wheelchair, in which case, right?

Whatever.

Sorry, one at a time.

Is anything not tractable?

You can do MAP and marginals?

So all of these things are tractable, right? But the thing is like some things cannot be represented as a compact SPN. These things are— there's no miracle here, right? So—

I mean, within the SPN, are there things like full Bayesian inference? problem, it's more complicated than just math.

By full Bayesian, you mean in the inference sense or the learning sense of Bayesian?

I guess both.

Right. So inference is what I'm explaining here. Learning means that you now have one more distribution which is over the models themselves. And if you can factor— we actually haven't looked at that, right? But an attractive thing that this has from the Bayesian point of view is that the Bayesian model average itself can become tractable. Although I'm not ready to claim that because we haven't done that, but I would suspect that that's the case. Maybe with some additional conditions. But yeah, that's a very interesting question.

Yeah. You had a constraint saying that the plus nodes should be on the same sets of variables.

All children should be over the same variables.

The same variables. So what does that mean over here? What are the variables in this whole—

Very good question. What that means is that I lied and you caught me, right? The thing that I glossed over here but now no longer can is that, well, but if you think of this as carving out a little region of the image, right? The region of the image that gets carved for a person on a bike versus, say, a person in a car are different, which means that if that's the case, then I can't really just have a sum node over them because it would violate this constraint that they have to be over the same, right? So what are we going to do? What do we actually do in some of the examples that we have later is that, like, What we do is we have a bounding box. And we say this bounding box inside it is a person. And I can only have sums over the same bounding box. I cannot have a sum over this bounding box here and that bounding box over there.

So the variables represent the pixels.

Yeah, exactly. Finally down here, the leaves are basically univariate Gaussians over the individual pixels.

But you've only got certain paths down to them instead of all the 2 to the number of— or number of colors to the number of pixels.

Precisely. Yeah. I mean, we should never lose sight of the fact that the vast majority of models are still not compactly representable here. But the thing is that— Sure.

An abstract painting, what am I going to do with it? Right?

Yeah. Well, even an abstract painting is still not that random. But the thing is that—

It depends. I mean, if you're the same who throws his paint, it can look a little— I mean, right. If I—

It is random at some level. Yeah.

Whatever.

But the point is that those distributions, they're not what occurs in the real world anyway.

No, they're not.

They occur in Jackson Pollock's mind.

Yeah. No, no. Certainly not.

More questions? So you had a question that I never got to. OK.

Yes. Just in this example, Could you give an example? But I think it's sort of half answered now. This happens to be a tree. Can you make it a DAG?

Yes.

If you have a DAG, then how do you— I mean, the car might have a wheel also, right?

No. So how would this be a DAG? I could have a person in a car or on a bike. But the model of the person doesn't have to be different. Actually, it is different because they might be sitting versus whatever. In general, right? I could have parts of the model that are shared, right? I could say, well, person in a— I have a model of a person in a car and I have a model of a person in a bike. And then that decomposes into a model of the car and a model of the person.

If you had the same model, the variables for the person, I mean, maybe you had a model for a person and an angle of the leg. And the angle of the leg would just— so it would be still the same model, but in one case case, the angle is 90 degrees and the other is sort of standing up.

No, but exactly. And that's the real case is that people in a car might look different from people in a bike, in which case they have to be different models.

Why?

Because they have different parameters, like you said. Let's say one case it's people standing up, right? And in the other case, it's people sitting down, right? Those just look different. But for example—

different parameters if you think of them just like an image, but if you— No, no, no. If you think how my body thinks about them, they just say, oh, this person has 90-degree angle between legs and body and the other one has sort of 180 degrees and I just have set the variables inside the person different, but it's still the same.

No, but— so, but I can— there's— so what you— what I hear you saying is that like these models have the same structure but different parameters. But that means that, you know, the SBN fragment is still going to be different. And finally, remember, these things all cash out to pixels and those are just— at the end of the day, I'm accounting for the same pixels.

You see, I wanted the hidden variable which is the angle between my torso and my legs.

No, and you will.

I wanted it to be a parameter of some order.

He's trying to make something tractable, that's all. No. You're trying to do it— you're trying to do it different. No, no, no, I won't.

No, this is a good example. So I can have a node over here whose children are angles. The hidden— I could actually set it up that way or I can find out that this is what it discovered, right? I had a sum node, right, whose children were like this position, this position, this position, this position with some resolution. If there's 10 different positions that your arm could be in, I could have a sum node where those are the 10 children. And then I would have a mixture model of how things look when I'm sitting like this, when they're like this, and when they're like— et cetera, et cetera.

Right. But otherwise, it would be the same random variables downstairs.

OK. So let me just say this without going into it into too much detail. It's probably not too hard to believe at this point. The standard tractable models that people use are all special cases of SPNs, things like hierarchical mixture models, thing junction trees, including hidden Markov models. Non-recursive probabilistic context programmers, and so on. All these things can be straightforwardly expressed as sum product networks. It is also the case for each of these that there's something sum product networks do that they don't. For example, in the case of hierarchical mixture model, every model in my hierarchy is over the entire space. There isn't this notion of models over subspaces and composing them. So for example, a product of 2 hierarchical mixture models is an SPN but is not a hierarchical mixture model anymore. Even less so than when I put now a node over these guys and so on. For example, probabilistic context-free grammars, right? They're models on a string. So they only split things into contiguous pieces. And in an SPN, they of course don't have to be continuous and so on and so forth. Thin junction trees, right? Again, they very easily translate to sum-product networks. But what sum-product networks buy you is that if there's context-specific independence, if there's determinism, et cetera, et cetera, this all leads to simplifications. Oh, the subproduct network, but not the junction tree, which is how you could wind up with a junction tree that is not thin and yet the inference is still tractable. And SBNs build on a whole bunch of previous related work, which I'm cavalierly omitting here. But I'd like to mention that it does exist. They have relations to interesting things like AND/OR trees, arithmetic circuits, multilinear functions, which is something that people in theory have studied substantially. SPN naturally have interesting relationships to a bunch of these other things.

So in linguistics, people actually use these dependency grammars and so on. And you can do inference in some of these. And it's sort of a big issue what kind of structures they capture and manipulate them. And what kind of— have you looked at this in the linguistic context and how they compare to dependency things?

Yeah, so in parsing, dependency Grammars are a subset of PCFGs.

Yes.

And SPNs are a superset of PCFGs. So there's things that you can represent with an SPN that you cannot represent with a PCFG. You can represent all PCFGs and therefore all dependency grammars. You said that

PCFG is not really tractable. No, it's tractable. It's polynomial.

Right? So this is a good example, right? So how do I convert the PCFG to an SPN? The S-P-Z-N is actually going to look like the chart. So I do suffer a polynomial blowup. So the S-P-N is polynomially larger than— it's going to be cubic in the sentence length and— or sort of like in the number of— right? Right. But that's OK because you're going to incur that cost when actually the parsing anyway when you build the chart. OK, so how do we learn these? So this is all very nice, but how do we learn these networks? OK? So we're a little bit short of time. So I will probably skip over the generative learning and just try to give you the main ideas of discriminative learning and just an inkling of how we do structure learning. So for now, let's assume that the structure is known and I'm just trying to learn the weights. So how do I do that? Well, the idea in discriminative learning, which is what people use most of the time in practice, is I have some set of variables that are my query variables. And some set of variables that are my evidence variables. And what happens is that I'm always going to know these ones. And what I'm trying to do is infer those, which means that I don't need to waste any effort modeling dependencies among the x's because they're all going to be known at query time. I just want to know, for example, given the image, what is its most probable parse? Or given the sentence, what is its most probable parse? Or given like this, is it a penguin or is it some other kind of bird? So if you know conditional random fields, SPNs, the math and the learning for SPNs is very similar to the math for conditional random fields with hidden variables. With the big difference, of course, that everything is going to be tractable or the inference is going to be tractable. And in conditional random fields, it's not. So what happens? I have my image. The beauty of discriminative learning is that now I can compute any features of my image that I want. I have total freedom. To do that. It's convenient to keep them non-negative, but not the end of the world if you don't. And then I have my evidence, which is, for example, the particular pixels that I saw. And then I have whatever I want to infer, like say the class of that image. In addition, as I mentioned, you can think of the sum nodes as representing hidden variables. And now learning consists of finding the parameters of the SPN. And the parameters are just the weights on the sum nodes. That's where everything is captured, right? Because now I've already fixed the structure, right? So I want to find the parameters that maximize P of Y given X for all the training examples. So maximum likelihood learning. And you could do regularized, and you can do Bayesian posteriorism. Let's just look at— none of that changes between SPNs and other things. So how do we learn this? Well—

So there's nothing to set on the product nodes. You're just saying those are independent variables. So the only thing you're trying to figure out is your own uncertainty about the various possibilities. Yeah.

You have to remember though that— so there's nothing to learn on the product nodes, but if you're uncertain about the decomposition, right, which you could be, that uncertainty is captured at the sum node above.

Right.

I say it could be decomposed this way or that way. Now tell me what the probability of each one is. So it would be redundant.

So it could be decomposed in, for example, 2 ways but both with independent—

Yeah, I could say there's x, y which are independent of z or there's y, z which are independent of x and now I learn a mixture model over that. So the uncertainty over the part structure, if you will, is represented in the sum nodes. Yeah.

I mean, the purple box and the red box, they could have arbitrary distribution and they could be sort of different for different product nodes, right? Mm-hm. So—

Yeah, so these boxes, right, what I'm saying is I'm computing it.

So like y1, right?

Yeah, it's above.

Yeah, so there's y1 and this y1 appears in different product. And the distribution for each of the product nodes could be something and be different in different ones. And there could be a very large number of different distributions.

Absolutely, yeah. Well, so in this case, I'm assuming the structure is given.

So the only thing that's not given are those coefficients, and you're trying to learn them. Yeah. OK.

But this is what people do in practice most of the time. Again, provided there's time, I will give an example for actually learning the structure, which is the more interesting problem at the end of the day. But actually, doing weight learning is already not trivial. Yeah, sure. And if the model is rich enough, just learning the weights can actually be very powerful. So let's look briefly at how you learn the weights and then look briefly at how you learn the structure. So I want to maximize the log likelihood, which is the log of this over all the examples. And I do that by following the gradient. I'm going to do gradient descent, standard thing. So what is the gradient of the log likelihood? Well, it's the gradient of the log of p of y and x over p of x. That's just p of y given x. And so this winds up being a very natural thing, which is Here, I have to sum over all states of the hidden variables given that I know the correct label. So I'm only summing over the hidden variables. And here on this side, I'm also summing over the possible labels. And the difference between the two is my training signal. Again, once they match up, I know that I've reached my maximum likelihood. The problem is that in a CRF, computing this is intractable in general. And here, no, it's always tractable as we already saw. So we can do it all tractably. And this is my gradient that I need to compute. And then what do I do? I do backpropagation. SPNs are just made for backpropagation and the reverse. Backpropagation is where you compute the gradient of this root first and then of the next level given the root and then of the next level and so on and so forth. So the recursive structure of SPNs sort of goes hand in hand with backpropagation. Let's say this is the gradient of my whole network with respect to this. Let's say this sum node is the root. So the gradient of the log likelihood with respect to that is obviously 1 because it's the same thing. And now what happens is that at every sum node, here's the rule. It's just backpropagation except with a particularly simple set of functions at the nodes. Instead of sigmoids or Gaussians, you just have sums and products. So what's the derivative of a sum? Well, it's just the sum of the derivatives. So that's what I do. At each node for each some child, right? I add to the derivative of the child the weight, right? Because it's being multiplied by the weight times the derivative with respect to the parent, right? And likewise for a product node, right? What happens is that I have to multiply by the values of the children. So first I did an upward pass to compute the values. And now for example, the gradient, right? The partial derivative of the function of the log likelihood with respect to this guy, right? is going to be this, which was the gradient at the parent times the product of the gradients at— so times the products of the values of the siblings. That's just the product rule of differentiation. And I do this from the root all the way to the leaves. And then finally, I learn the parameters for the univariate distributions the univariate way. And this is how you migrate this in. So very easy and very efficient. Just uses the SBN structure. There is, however,

How do you know that— I mean, if you do gradient descent, how do you know you don't have a picture like that?

I can't. So this is machine learning with hidden variables. And so we don't guarantee that we find the global optimum. It's just like EM. There's all the usual things that you can do with multiple restarts and smart initialization and whatnot. But that's life. However, there's a little bit of good news that I'll give you in just a second. But first, Here's a big problem. It's what's known in the neural network literature as the gradient diffusion problem. Is that I have a strong gradient signal at the output layer or the root in our case. But then that signal gets more and more— gets smaller and smaller as I progress. Which means that by the time I'm 2 or 3 layers down, there's almost no training signal. And this is why even though in principle with backprop you can learn very deep layers, in practice people only learn networks with one hidden layer. And all of this deep learning literature that is coming out these days and, you know, getting a lot of press, what they do is they learn models with 2 or 3 hidden layers. And very rarely they might learn something with 6 layers because it was probably hand-engineered to be for character recognition or something. And the basic thing that's killing you is this gradient diffusion problem. And we face the same problem here because again we're doing backpropagation through potentially a lot of layers. So how do we solve this problem? In a very simple way. It's that we're going to do hard inference instead of soft inference. We're going to, instead of using sums here, we're going to use maxes. The advantage of using maxes instead of— so it's an approximation. You can think of it as we're approximating the sum with a max, which is often a pretty good approximation. But then given the result of your MAP inference, now the problem is convex and there's a single global optimum. Because I filled in the hidden variables. So now there's no more room for a local optimum. So what happens with hard difference is that I don't get this gradient diffusion because I always have a signal of constant strength going down no matter how many levels I have. As a result of which, we can learn some product networks with— we don't know how many. We've learned them with tens of levels. But that's because what was needed for the application. It's interesting, for example, to consider the question of Envision. How many layers do you need? And as far as we know, there is no limit to how many layers you could learn this way. We in practice have learned things within the order of 50, 60, 70 layers. But we could probably go farther. Could you

do the same thing for your neural network where you just sort of would do the same?

Well, in a standard backprop, it's not a probabilistic model. So there isn't this notion of doing MAP inference. There's MAP inference because we're doing a probabilistic model. But there are similar tricks. So the analog in that is like, I want to make sure that I have— that my signal stays strong. And there's certain tricks that you can use to do that which people have studied. But in that context, that didn't get very far. Even in deep learning today, people don't really have a solution for that. But in this context, there's a very natural solution. Yeah?

In some of these deep learning things, actually, they're replacing the standard sigmoid activation functions by just maxes, in which case you do get the gradient propagating down all the way. And some of these deep networks that have lots of layers, you don't get any gradient

work

down at the bottom if you do these.

The more scalable of these networks use things like max pooling. pooling and sum pooling. And max pooling and sum pooling are actually the analog of our max and product nodes. And people have tried to put probabilistic semantics on them, but then the inference blows up. Here, you have probabilistic semantics and no inference blowup. OK.

So is it actually noted here the big blue line is supposed to be as thick?

Yes.

The big blue line doesn't become 4?

No, because exactly, precisely because what actually— Sure. Your question will hopefully be answered by the next slide. So here's what happens. I do my MAP inference with the real data. This is my green tree. It's what the inference with the real data did. Here's my— so with my known y, summing only over the hidden variables. Here's with my unknown y. This gives me a red tree. And now my training signal is actually just going to be the difference between these trees. So if this— here there's no signal because the right answer is— the right choice is being made, right? But then here in one case, let's see, like this guy went this way. This guy went that way. So what's going to happen is that I need an increment. And it's a fixed-size increment of this guy, plus 1 because of this, plus 1 on this weight and minus 1 on that weight. And notice that it's always going to be plus or minus 1 no matter how far down you go. So you're saying that the gradient is going to be 0? You're always choosing one child. You're not choosing fractions of a child that get ever smaller. So the learning rule actually winds up being very intuitive. Is that it's— again, it's similar to conditional random fields. Is my gradient is just going to be the number of examples for each sum child. It's going to be the number of examples that had the correct label minus the number of examples with the model guess. And if they're the same, I'm good. If with model guess I have higher value, the weight needs to go down. If this was lower, then the weight needs to go up. And that's what I get because it's going to be a positive quantity.

Now, this is— I mean, this is not really what you're supposed to be calculating with the sum, not with the max. Precisely. You're doing soft gradient, not the hard gradient. And a priori, if all the sums were dominated by their maximum terms, then this would work. Is this better than that? Is it that because you're taking a difference, you could be doing better in certain cases? Yeah. Or is it really only working when the sum is dominated by the max?

Not always, in fact. So this is a lot like— and in fact, in the generative case, it's going to be exactly hard versus soft EM. So in soft EM, I do fractional assignment of things to clusters that are well-defined variables. And here, I'm doing hard assignment. And this is going to have exactly the same advantages and disadvantages. What people typically do— and the problem with soft EM is that it's very slow to learn. So people often start out doing hard EM to get the fast convergence and then soft EM to really make sure you get to an optimum. And we actually thought, oh yeah, that's what we're going to do. We're going to do max followed by— And then go back. Yeah. But actually, as it turns out, you don't actually get any mileage out of that. You don't get a better optimum that way. Now this could depend on the problem. I can certainly make up pathological cases where this will give you bad results.

Right. I mean, if you had easing near the phase transition, this is not going to— Yeah.

So in this whole thing, this is the place where we made the compromise. If this is good, then the learning is convex. The inference is tractable. Life is wonderful. But there was this one thing here that we did to overcome the local optimum or the gradient diffusion, however you want to look at it. Yeah. OK. All right. So we apply this to state-of-the-art image classification problems on standard benchmarks. And we beat everybody. So RBMs, SVMs, et cetera, et cetera, on the various conditions. This is stuff that people have put hundreds of person-hours of work into on various of these problems. Generative weight learning, it's basically the same thing except that now instead of gradient descent, we can just use EM. Generative learning is we're learning a joint model of the variables. We can do that using EM. But other than that, the algorithm is very simple. And we apply this to the problem of completing images. Like I give you half the image and you need to give me the other half. And in this case, they're faces so you can compare. But we did this with arbitrary images. This was something that most people didn't even attempt before because it was too hard. And we do intelligent things like filling out the beard here. Nevertheless, you can see that this has these artifacts. The artifacts are because we're using a decomposition into rectangular sections. When we learn structure, that decomposition itself is going to be learned. Then you won't have these artifacts anymore. Again, here's the architecture that we used. I won't go into details of what it was. Let me just— and here's a summary of how you do learning. So there's soft inference or hard inference. There's generative EM, generative gradient descent. Discriminative gradient descent, on this side you're using derivatives and on that side you're just using counts. And that's why this is more robust and also faster to learn. But again, it doesn't give you the optimum guarantee that you have on the other side. So one quick word about structure learning. Or actually, I mean, if there's no time, I can just skip over the structure learning. Yeah. OK. Yeah. So let me just say that we have a paper about structure learning coming out in ICML, and you're welcome to take a look at it. It again beats everybody by a mile. Actually, no. Let me be a little bit fair. In terms of likelihood, we are comparable to things like Bayesian network learners. But then at inference time, the ESPN takes a fraction of a second, whereas with the Bayesian network, you're doing Gibbs sampling or BP and having a lot of trouble. And then the accuracy of the query answer is much, much higher in our case. So even in cases where the Bayesian network had higher likelihood, when it comes time to answer questions, The Bayesian network loses a lot of that because of the inference, and we don't. So to summarize, in machine learning, as in computer science in general, there's always this trade-off between tractability and expressiveness. And what we do in research is explore different places on this trade-off. And this is the case with graphical models. There's junction trees over here where it's like thin junction trees or mixture models, which are not very expressive but very tractable. Or you can learn models that are more expressive but less tractable. So this is what life usually is like. But every now and then, we can do something better than explore a certain tractability-expressiveness trade-off curve, which is jump to a better one. And this is what some product networks do. In some product networks, there's still a trade-off between expressiveness and tractability. But now we have points on that trade-off that are better. Than the points that you had over here. Now with some pronouns, for the same expressiveness, I can have more tractability. Or for the same tractability, I can have more expressiveness. And so this is what the bias is that we're still doing a trade-off, but now we're in a better trade-off curve. And there'll be code data and so on. We have implementations of this that we'll be putting online within the next couple of weeks. So you can go to this URL and download it. Thank you. Questions?

There's also going to be snacks and stuff outside.

Yeah, so you can talk to me at the reception.

Yeah, perfect. Thank you, Pedro, again.

All right, thanks.