Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions (Paper Explained)
deep learning machine learning arxiv explained neural networks ai artificial intelligence paper imle implicit mle maximum likelihood backpropagation through algorithms deep learning discrete discrete deep learning discrete backpropagation gradient discrete gradient of an algorithm
#imle #backpropagation #discrete

Backpropagation is the workhorse of deep learning, but unfortunately, it only works for continuous functions that are amenable to the chain rule of differentiation. Since discrete algorithms have no continuous derivative, deep networks with such algorithms as part of them cannot be effectively trained using backpropagation. This paper presents a method to incorporate a large class of algorithms, formulated as discrete exponential family distributions, into deep networks and derives gradient estimates that can easily be used in end-to-end backpropagation. This enables things like combinatorial optimizers to be part of a network's forward propagation natively.

OUTLINE:
0:00 - Intro & Overview
4:25 - Sponsor: Weights & Biases
6:15 - Problem Setup & Contributions
8:50 - Recap: Straight-Through Estimator
13:25 - Encoding the discrete problem as an inner product
19:45 - From algorithm to distribution
23:15 - Substituting the gradient
26:50 - Defining a target distribution
38:30 - Approximating marginals via perturb-and-MAP
45:10 - Entire algorithm recap
56:45 - Github Page & Example

Paper: https://arxiv.org/abs/2106.01798
Code (TF): https://github.com/nec-research/tf-imle
Code (Torch): https://github.com/uclnlp/torch-imle

Our Discord: https://discord.gg/4H8xxDF

Sponsor: Weights & Biases
https://wandb.com

Abstract:
Combining discrete probability distributions and combinatorial optimization problems with neural network components has numerous applications but poses several challenges. We propose Implicit Maximum Likelihood Estimation (I-MLE), a framework for end-to-end learning of models combining discrete exponential family distributions and differentiable neural components. I-MLE is widely applicable as it only requires the ability to compute the most probable states and does not rely on smooth relaxations. The framework encompasses several approaches such as perturbation-based implicit differentiation and recent methods to differentiate through black-box combinatorial solvers. We introduce a novel class of noise distributions for approximating marginals via perturb-and-MAP. Moreover, we show that I-MLE simplifies to maximum likelihood estimation when used in some recently studied learning settings that involve combinatorial solvers. Experiments on several datasets suggest that I-MLE is competitive with and often outperforms existing approaches which rely on problem-specific relaxations.

Authors: Mathias Niepert, Pasquale Minervini, Luca Franceschi

Links:
TabNine Code Completion (Referral): http://bit.ly/tabnine-yannick
YouTube: https://www.youtube.com/c/yannickilcher
Twitter: https://twitter.com/ykilcher
Discord: https://discord.gg/4H8xxDF
BitChute: https://www.bitchute.com/channel/yannic-kilcher
LinkedIn: https://www.linkedin.com/in/ykilcher
BiliBili: https://space.bilibili.com/2017636191

If you want to support me, the best thing to do is to share out the content :)

If you want to support me financially (completely optional and voluntary, but a lot of people have asked for this):
SubscribeStar: https://www.subscribestar.com/yannickilcher
Patreon: https://www.patreon.com/yannickilcher
Bitcoin (BTC): bc1q49lsw3q325tr58ygf8sudx2dqfguclvngvy2cq
Ethereum (ETH): 0x7ad3513E3B8f66799f507Aa7874b1B0eBC7F85e2
Litecoin (LTC): LQW2TRyKYetVC8WjFkhpPhtpbDM4Vw7r9m
Monero (XMR): 4ACL8AGrEo5hAir8A9CeVrW8pEauWvnp1WnSDZxW7tziCDLhZAGsgzhRQABDnFy8yuM9fWJDviJPHKRjV4FWt19CJZN9D4n
 Hello there! Today we're looking at implicit MLE back propagating through discrete exponential family distributions by Matthias Niepert, Pascal Minervini and Luca Franceschi. This paper is a paper that we've discussed in our regular paper discussions on Discord and so it is informed by everything that I have heard there. If you want to take part in these discussions and influence my opinions you're very welcome to do so. The link to the Discord is in the video description. Alright let's get into this paper right now. This paper proposes essentially a discrete layer for neural networks. This is maybe how I can describe it and the basic setup is in this figure right here. So let's say you have an input X which might be some sort of a continuous input like an image. They do give an example. By the way the authors they have quite helpful code that's available but also they have made themselves a little video about the paper and I also recommend that you go watch that video because it's quite helpful. So what they give as an example in the video which I find a good example is you have a map of and they use I think they use even Warcraft maps but you have a map and you know there's like a lake somewhere and then there's like a little house right here and so on. Your task is to go from the top left here to the bottom right. So you need to plan your way somehow through that. Now you don't get this as a graph that would be directly input into Dijkstra's algorithm however you get this as an actual image right. Yet the solution here is going to be some sort of a some sort of a path some sort of a gold path that's the label and or maybe something even derived from the gold path like how long the gold path is. So maybe that's five long or something like this. So it's very complicated you first need to recognize where can I even go based on the image on the left. Then you need to find the shortest path based on you've determined where to go. Then you need to evaluate based on that shortest path you need to evaluate some property for example as I said how long is the shortest path or just you know follow the shortest path on the actual map. So it's a mix of continuous and discrete elements and specifically the part in the middle that's described by this P of Z right here that is going to be some sort of a discrete solver. In the case here it's going to be a shortest path algorithm. Now the question is how can we run back propagation if we only have the label on the right hand side. How can we back propagate? I mean we can back propagate from the label through here right. This is a neural network that maybe determines some property of the shortest path but then how are we going to back propagate through this layer right here back to this neural network that's supposed to extract the input graph to the Dijkstra algorithm from the image. And that is a challenge there have been some solutions already for example some one famous example is a score matching. Sorry that is also an example but the famous example is the straight-through estimator. However that it doesn't always work it fails sometimes and specifically here the authors propose a different framework in this implicit MLE framework. I'm going to look at how that's built up. This is a very technical paper and I'm by no means an expert in these things I just try to give you a little bit of the idea of what's happening right here so that you know what's going on and if you have something like this in your neural network like a combinatorial optimization solver or anything like this then you can just go grab their code and use that as a layer it is really super simple. Alright that was the overview now let's get into the paper. Hold on this video is sponsored by weights and biases. Weights and biases is your one-stop shop for all your machine learning needs. It will track your experiments with a single line of code. It'll upload automatically all your logs all your configurations everything to your cloud. It will automatically grab all the output all the metrics all the configurations of your experiments and store that in one neat location so you can see your experiments you can track them wherever they run you can compare among the experiments but you can go further you can then tune your hyper parameters according to the results of those experiments and all of this is done automatically in a distributed way you can literally sit on your toilet on your smartphone and tune your hyper parameters and start new experiments but it's not only experiment tracking and hyper parameter tuning weights and biases has tools for the entire pipeline of machine learning research from the initial idea up until the deployment and beyond that when you actually want to track what you've deployed weights and biases has cool methods to track all of your data set and their dependencies to each other as well as your models and all kinds of other artifacts that you might produce a very powerful visualizations for all the inputs and outputs of your pipelines as well as the models themselves all of this runs in the cloud but if you're concerned about privacy there are options to self host the system is free for personal use and for academics and they have great plans for enterprises small teams large teams doesn't matter so thank you very much weights and biases for sponsoring this video if you don't know them yet absolutely check them out it's free it'll make your life a whole lot easier now let's get into the video as I said the the the problem right here is that you have these kind of these kind of discrete tasks sometimes as a part of an entire learning setup so the paper makes different contributions but here are they here they're listed out they say we propose implicit maximum likelihood estimation as a framework for computing gradients with respect to the parameters of discrete exponential family distributions so what we want is of course gradients gradients of this discrete process in the middle and the discrete process specifically is going to be formulated as a exponential family distribution and we're going to see how that happens they say we show that this framework is used for useful for back propagating radiance through both discrete probability distributions and discrete optimization algorithm sorry sorry optimization problems and that would be the example right here would be a a Dykstra shortest path algorithm or an integer linear program solver or anything like this in fact they're one of the general formulations they have is for integer linear program solving I am Ali requires two ingredients a family of target distribution Q and a method to sample from complex discrete distributions we propose two families of target distributions and a family of noise distributions for gumble max based sampling so we're going to check look into how that works and exactly what it contributes and then yeah we show that this simplifies explicit to explicit maximum maximum likelihood learning when used in some studied settings and experimental evaluation these points were probably not going to go into too much essentially in point four they show that for some settings this reflects already established methods so it's in sort of a generalization of methods that have already been around of methods that are maybe specific to a given setting or problem and the experimental results well you just like their experimental results essentially show that their method for example out compete the straight-through estimator method so what's the deal with discrete things in neural networks the problem is of course that we can't compute gradient with respect to discrete things now take for example the straight-through estimator the problem it's trying to solve or one of the problems you can formulate it like this you have some X you put it into neural network and out in the middle somewhere you it you are required for some reason to sample from some sort of distribution for example you're required to this produces a produces a probability distribution over a few classes let's say over four classes and then what you're going to do is you're going to sample one of the classes right here and then you're going to continue with that through the nest the rest of your neural network until you're at the label now again as before you need to back propagate in order to learn through this network which is easy but through the choice through the sampling procedure of that of that inner layer and that's hard so what the straight-through estimator does is it's a bit of a trick it essentially in the forward pass you do the discrete optimization you do the sampling but in the backward pass you you act as if you simply propagated the distribution as such so for the to the forward pass it is really a discrete sample but to the backward pass it looks like you've simply you did you never sampled you simply pass the whole distribution say well I'm not sure it's like 70% this and 30% this the way you would implement that usually as you have some signal let's call that H for for maybe that's the histogram right here and what you would do is you would if you sample from H that was going to give you like S well let's say let's say we take the most likely state right so we determine H and we take the most likely state which which is let's say S is the R of max of H okay that is your sample now what you would do in your forward pass is you compute the next layer H prime as S which and then plus H minus a stop gradient of H so the stop gradient am I doing this correct no of course not of course not yes oh yes I'm doing this correctly of course okay so let's analyze this in the forward pass the stop gradient has no effect on the forward signal so these two here essentially cancel out these cancel out to zero however in the backward pass right since derivation is distributes over addition and subtraction what you would do if you were to derive the gradient of H prime that's essentially the gradient of S plus the gradient of H plus the gradient of stop gradient of H now stop sorry minus minus stop gradient of H obviously has no gradient so that goes to zero the gradient of S is also zero because it's a discrete operation and most of these frameworks simply tell you well the gradient is zero it's a discrete optimist operation if you're not sure that this is happening you may in fact also put a stop gradient operator around s and you can see what remains is the gradient of H so you see the trick in the forward pass these two cancel out however since in the backward pass this by itself is already zero because of the stop gradient operation the gradient of H remains right here this is a trick you can you can simply swap out a gradient in the backward pass for whatever you like with this trick people have used this to get gradients with respect to discrete operations like this but this paper right here is an alternative and as they show in some situations it is more appropriate to use that alternative however it is also quite a bit more tricky so what's the first thing we're going to do the first thing we're going to do is we're going to take that inner thing right here that inner procedure and again let's go back to the task of of finding the shortest path so what's the input the input is some sort of a graph right where you need to find the shortest path with cost associated with each of the edges and some some start and some end goal and what we want is the shortest path some sort something like this now the first thing we're going to do is we're going to encode this problem into a binary vector now how exactly we do this is is I don't really know for for shortest path problems but we're going to encode this into essentially another binary vector but I'm going to encode the problem into this vector theta right here so theta in this case what you would do is your theta vector let's this is the theta vector it will have I guess hmm it will have probably for each edge it will have an entry with the negative cost of that edge associated in the vector so the negative cost of edge one the negative cost of edge two the negative cost of edge three now why are we doing this you can see that we are going to multiply this theta with another vector called z and z here is the let's call it the solution or the proposed solution to this inner problem and z is now a binary vector so z can eat either be 1 or 0 in each entry and it's going to be 1 if and only if this edge here is part of the proposed solution so any path in this graph can be represented by a given z variable right by simply setting a bunch of things to 1 and 0 I can I can select some of the edges and if I have selected the correct ones they will form a path and if I have selected the absolutely correct ones they will in fact form the shortest path you can immediately see that for the shortest path the inner product between the two vectors will be the highest among all the paths right so this is how I formulate my problem I'm formulating my problem between as an inner product between a binary vector and some sort of a weight vector theta such that for the solution of the inner problem like the shortest path algorithm or the case subset selection or the integer linear program such that for the solution of this problem it is the case that this inner product is the highest possible now you immediately see that of course I can make that inner product even higher by putting all of the edges to zero right so you know z right here I can simply say zero zero zero zero zero all the costs here are negative ergo I have no negative cost ergo that is going to be zero and that is going to be the largest possible I've solved the problem what's the problem this isn't a path in the original formulation so the last ingredient we're missing right here is what they sometimes here call capital C this thing right here capital C is a constraint set so capital C would define in this case what the valid entries for the z vector are so z must be in this capital C class and I think C must be yes that defines what the valid valid valid solutions even look like so in the simplest case if this is a classification problem right this is a classification problem theta would sort of yeah faith you can you can think of this is a classification problem and then z would be selecting the class right you can model theta in this case as just a vector of ones and then z right here could select the class by simply putting that entry to one wherever of whatever class is selected and the constraint set C could be easily modeled by saying the norm what is that the sum of all the entries which is probably the one norm of z must be equal to one right that could be the constraint set am I correct here I'm not sure I can actually model I probably can't model it like this like here there probably needs to be like there probably needs to be some some sort of cost per class or something like here and then I can model the constraint as saying the inner product of z with a vector of ones must be equal to one that looks better so that is actually part of the definition of the constraint set and the the problem in these cases is that this constraint set makes it very difficult on on obtaining good gradients through this discrete through this discrete problem because right here as you can see it's it's not really easy because most of the z vectors in the Dykstra problem aren't actually valid paths so the issue here is that we need a gradient we need to respect the constraint set of the problem they go ahead and they formulate this as I said as this problem where you have a vector this vector z is whatever solution you propose the theta is the definition of the problem the inner product is sort of the the reward let's say the yeah the reward maybe the inverse loss of the problem and they can now formulate this as a exponential family distribution by simply raising this by putting this inside of an exponential function let's see they've done it somewhere somewhere right here look at that oh it's not even a it's not even a minus sign all right so for now just trust them that it is necessary to formulate it as a distribution and and don't just kind of hang in there it is going to get very complicated but it is going to lead somewhere so they can formulate this inner process as a probability distribution P of Z where that is according to the exponential family so as I said the exponential family here you put in this thing right here there is a temperature at which you sample so what is that essentially is going to do is going to normalize given this right here this is the the log partition functions the normalization constant this is essentially going to give you a distribution over the individual dimensions of the Z vector and that is going to be normalized and is going to be more peaky or less peaky depending on the temperature right here so the process that they formulate this as is you take some input X right here you put it through the first neural network to obtain the theta the theta is essentially the problem definition for the inner algorithm the inner algorithm you formulate as a probability distribution so it's going to have more or less likely states with the more likely states being the ones that solve the inner optimization problem more perfectly to more reward so Z is going to be a random variable that is according to that distribution for now you can just think of Z is a random variable and the likely states of Z are the ones that have the paths that have a very short path through the in our example or whatever states solve the inner problem very accurately and then from that Z we're going to put that through another neural network that's going to give us our output and we're going to compare the output with the gold label and then we're going to backpropagate through all of it our parameters are the parameters here and here so the parameters of the two neural networks fu right here this is easy to do right because we can simply back propagate from y into the neural network and the parameters of HV the V parameters this is hard this is the hard part so what do we need to do in order to back propagate all the way to H sorry to the V variables well what we need to do is we need to the direction here is that the parameters sorry X becomes theta becomes Z comes y this is with the help of the parameters V and this is the help of the parameters you right you is easy for V what we need to do if we want to have the what you can see right here the gradient with respect to V we first need the gradient with respect to theta and then we can once we have the gradient with respect to theta where is it where is it I guess here once we have the parameters with respect to theta we can use the the back propagation algorithm again to back propagate into this network and change the weights V so how do we get the gradients with respect to theta again this is means we have to back propagate through this piece right here which is the inner optimization algorithm so the here is it here's the chain rule expanded this is this here that's theta and so we need the parameters the gradient with respect to theta and then we can use back prop okay this by the way is the entire algorithm as it's going to be later you can see it's fairly simple you can also see there is a lot take mistake right here but I think that's my conversion so that what they do is they say this it's very hard it's very very hard to compute this gradient with respect to this inner optimization procedure right it's very hard to compute a gradient with respect to the Dykstra shortest path algorithm essentially you'd have to know how do I need to change my graph definition in order for the path to become shorter or in different in some way and that's very hard like all you can do really is kind of try and see what happens I wouldn't know anywhere anyhow else because yeah remember that what the theta is the theta is the output of the first neural network so the theta is the definition of the graph and that is produced by by this neural network right here that looks at the picture and gives you the discrete graph so essentially what it gives you is an adjacency and an adjacency matrix but still so the question is you know how does my adjacency matrix need to change for the Dykstra algorithm to find a shorter path let's say a shorter path or well or a path that is more close to the gold label that I have because you don't always want to shorter you actually want to learn from data so the first step they do in this challenge in this sub challenge right here is they say this is too hard we're going to replace the loss right here this loss the true loss of our output compared to the label with a surrogate loss this L is an implicitly defined a maximum likelihood objective and we're going to calculate its gradient instead of the gradient of our true loss now the logic of how we get there is the following in this inner problem we define a probability distribution this probability distribution remember what is this P here P describes the solution space of in our case the Dykstra algorithm so P is a distribution that would assign high value to or high likelihood to paths that are very short in the graph that's defined by theta and low value to paths that are very long in this same graph right now what we can say is can we this is essentially a distribution can we find a different distribution we call a target distribution where we can show that in expectation the loss the loss from this target distribution right here is always smaller than the loss from the true distribution so essentially can we find the distribution that where the paths that it outputs are lower in loss lower in the final loss than the ones we have so remember we have X and all of that and the end there is Y right we predict Y and we compare the Y to the true Y there's going to be some loss and the question is can we reduce that loss right here so we don't necessarily want to find theta such that we find a shorter path but we want to find a more appropriate theta in here such that the rest of the neural network can predict Y hat more accurately in order to be closer to Y for in the in our example we want to if if our neural network right here is very bad at actually extracting a proper walkable graph from the landscape right here like if it doesn't recognize that this is a lake you know it thinks you added all of this is really fine to walk on and so on the graph right here will be quite crappy the weights on the edges will be not accurate right it's not inferred correctly from the landscape that means that this network here will have a pretty hard time determining the actual value of the shortest path because even though the Dijkstra algorithm does a good job of finding the shortest path it's on the wrong graph and therefore it's useless so what we need to be able to do is we need to be able to more accurately extract the graph from the image so we need to train these parameters right here so here we ask ourselves can we come up this distribution P here that's the distribution of solutions to the problem that's defined by theta we ask ourselves can we come up with a distribution that has a lower loss than the distribution we have and the answer is going to be yes we can do so with a simple a simple let's say trick so if you look at back at this I realize we're in like three layers deep of problems like we have a problem for that we have another problem to solve for that we have another problem self our current problem is that we want to see can can we change this distribution such that the loss is lower how do we need to change this distribution essentially and the answer is going to be we're going to take the output right here and we're going to pass it through this network we're going to look at the loss and we're going to back propagate that loss until the point where this algorithm stops and then we're going to take one gradient step into the direction right here and then that is going to be our new distribution so what does that mean in our example right here we're going to take the graph that we output right here we're going to run it through Dijkstra gives us the shortest path remember this is a crappy graph because our network initially is not good we're going to put that through this neural network right here that determines the cost and we're going to calculate the loss and back propagate that so what does that give us ultimately that tells us well the gradient says what how do I need to change the output right here in order for the neural network that follows to do a better job right and let's say the output is well this edge here has a bad weight or in fact this edge there's an edge right here that's missing or or something like this not sorry no that is formulated wrongly what we are going to change is we're going to change obviously the Z which is the solution so it's going to say in this shortest path that you computed there's something wrong for example you should have maybe taken a different shortest path or you should have weighed it differently or something like this and we're going to take a step into that direction so for example if the shortest path rather than up and over should have gone directly we know that the edge right here should have had maybe a lower cost associated with it or something like this so we're going to use gradient descent to see how do we need to change the inner problem such that the rest of the pipeline does a better job and that's what you see that's what you see right here somewhere there okay so this is the target distribution is this right here so it's the same as the regular distribution of inner solutions however instead of inputting the graph as it is we're going to input the graph minus a step size times the gradient of the loss with respect to the output of the inner of with respect to the output of the inner solver so this is using gradient descent in order to come up with a better problem definition right here since these two are vectors they're multiplied together we can use in fact the gradient with respect to z and subtract that from theta because they're of the same dimension right so we're going to ask ourselves what would be what would be a more appropriate problem definition in order for the rest of the network to do a better job and that's going to be our so-called target distribution and now our job now we have a pretty simple job our job is going to be well can we make it such that the current the current graph that we output right here is more like this target graph so can we make the distribution p more like the distribution Q is the same as asking can we make the current graph that was output by the network H more like the graph that would be more optimal for the rest of the network and that is let's say a solvable problem in fact if you work it out the formulas get pretty simple so if we do it like this and by the way this inequality here is crucial obviously because and but we see why it's given because of gradient descent we're in expectation guaranteed that the Q distribution is going to have a lower loss than the p distribution because we do one step of gradient descent with respect to the loss right so essentially we do step of gradient descent in the inside and then our surrogate loss is going to be well can we make the output distribution more like the result of that gradient descent this this must be one of the most confusing videos ever but I hope you're still with us so what we want is to make these two distributions closer remember we said we can't back propagate through the discrete optimization procedure so what do we do we said instead of back instead of back propagating through the inner optimization procedure we're going to replace that by a new objective the new objective has two steps step one determine what would be what would be a better output for for the discrete sorry what would be a better input for the discrete solver and then step two is can we make the input that we've received more like the input to the discrete solver right this is where this where we do the gradient descent inside and how are we going to make distributions more like each other that's this right here this is the KL divergence between P the actual distribution and Q the target distribution and that's going to be our surrogate loss that we use instead of the loss that we cannot differentiate if you if these are both exponential distribute exponential family distributions you'll see that this pretty easily cancels all cancels out and reduces and in the end the gradient of this surrogate loss simply going to be the difference between the two marginals so between the two means of the distributions now this seems pretty easy but inside of the three layers of problems we get another problem so what does this mean this is the mean of the exponential family distribution when given a certain definition problem definition theta prime or theta if you are over over here this given that it's a let's say it's a hard problem with these constraints at and so on calculating the mean of such a distribution is hard it's in fact probably as hard as as solving the the entire problem itself so calculating the mean of these distributions is not an easy task sampling from these distributions straightforwardly is also not an easy task so what this paper does is it says for under certain conditions what we can do is we can replace the mean with this and this is a trick well a trick a method that they call perturb and map by map they mean maximum a posteriori so essentially means that for the exponential distributions what we can do is we can approximate the mean using map the most likely state and what's the most likely state for example in this di extra algorithm the most likely state is in fact the shortest path by how we describe how we define the problem right so we've defined the problem as the inner product between the problem definition and the proposed solution now what's the most likely proposed solution if likelihood is given by the inner product obviously the one that maximizes the inner product which is the one that by construction has the shortest path okay so fairly convoluted but this is something we can actually do so we cannot calculate the means of these distributions but we can calculate the most likely states and it's not so straightforward in fact it is a better estimate so they consider I think yes so you're computing the marginals is in general a what's that sharp p sharp hard problem scales poorly with dimensionality so map states are often used to directly approximate the the means however it's apparently better if you use this perturb and map this strategy where you estimate the mean not directly as the most likely state but as an expectation sampling from a noise distribution and perturbing this state what does that mean that means that you can get the mean of the distribution let's again draw our di extra graph right here like that you can get the mean of this distribution by wealth by slightly perturbing the problem so maybe slightly reweighing the edges saying this edge is higher this edge is now lower slightly perturbing a lot of times and then every time you calculate the shortest path so most of the time like this will be the shortest path most for most of this but then every now and then you'd perturb it so hard that you know this edge now goes up very high in cost so then you'd have this as the shortest path right here and so on but ultimately yeah so adding all of that up getting the expectations over all the shortest paths in oil for a lot of perturbations will give you a good approximation of the mean of that distribution the last question is a little bit okay what noise distribution is appropriate for this and the answer is going to be the answer is going to be that is going to be a gumble noise and I think this is this now gets a little bit too deep but just to mention this right here if in fact there are some properties are given and the specific property that needs to be given for this to be accurate is that you can define the problem always such that such that the constraint set is given by a number K and where you can see right here exactly K entries in Z have to be one if that's obviously not covering all of the problems we've considered but it covers a lot of the problems we've considered and even if not you can still apply it as I as they say it's just not as appropriate but still appropriate enough and they also have a way to sample gumble distributed random variables but I don't think necessarily we need to go into that you just need to know that the appropriate noise distribution in fact to get a good estimate of the mean is a gumble noise gumble distribution by the way it describes extremal values so if you want to know the distribution of of the maxima of some phenomenon that will be gumble distributed and then you have it at the end of the day you would be this surrogate gradient would be given by the difference between perturbed maximum sorry the maximum a posteriori solutions of perturbed Thetas right here and yeah so this is a few layers deep let's actually look at the entire algorithm and you'll see it's not that hard so what do we do in the forward pass we take X and as I said we get theta this is a neural network in our case it takes a picture and it extracts the adjacency matrix which is theta so it extracts the graph that we're now going to run Dykstra on okay so this data goes into this forward pass right here what do we do in fact we forward propagate the maximum a posteriori state of a perturbed version of theta and this year if you remember this year is going to give us the mean that's a wrong new is going to give us the mean of that distribution that we're looking for okay so it's going to be for were propagated in so that is going to be forward propagated to let's say to the second neural network and that's going to give us why or at least an estimate of why and then we're going to compare to the real why we're going to get the loss and now we're back propagating right so back propagating we take the loss we go back we go back through this first neural network until we're here and that is where to start so the backward pass that would come in here right this gradient here that's the gradient we get from the chain rule in the backward pass we also need this step size lambda right here okay so what are we going to do we're going to take that gradient and rather than giving it straight to like the straight through estimator or to the chain rule we're going to compute and update to the theta to our graph definition right to our adjacency matrix or our our cost cost matrix for the shortest path algorithm essentially saying how do I need to change the problem definition for the Dijkstra algorithm in order to in order for the upstream sorry for the downstream modules to do a better job predicting the correct label why that's so we're going to compute an updated theta then we're going to compute a this surrogate loss right here and the surrogate loss as you've seen right here is going to be the difference between the two max perturbed maximum a posteriori things so it's going to be by the results that we've derived where was it where was it here by these results right here remember this is the gradient this is directly the gradient of our surrogate loss and the surrogate losses can we make the output of the first neural network closer to something that's more useful so the gradient is directly given by the difference between these two things so by the difference of marginals which we approximate by the difference of maximum of posteriori so this requires us to run Dijkstra once here in the forward pass and then it requires it to run Dijkstra again here once on the on this updated graph and the difference between the two is going to be the gradient in which we have to update our inputs okay notice that I'm I've talked I think a bit confusingly so here I already said how do we need to update our problem definition right and you could think that you know we could feed that directly upstream but we can't the real gradient we want to feed upstream is right is this thing right here so essentially the top thing is how do we need to change our problem definition so the downstream neural network can do a better job and this right here is that what or sorry how does the upstream network so the one that maps X to theta how does that need to change its behavior in order to produce a better input to the solver yes that is the least confusing I can say it and then we return the gradient that gradient that we computed and this is our substitute gradient for the gradient that would be this is our substitute gradient for the gradient of the true loss with respect to theta and since it's a gradient with respect to theta we can continue back propagating through here back probating it into this neural network here and update the weights so that is it the only thing I'm not sure about is if they really return the Z hat right here like it was my impression that in the forward pass they would actually feed the true the true Z upstream but I'm not sure because for example where was it yeah here they rely on Z bar which is Z bar is essentially that's mu so not sure exactly we might have to look at the code exactly but I hope you understand a little bit of what's going on right here yeah so recap we have some discrete part in our neural network like a shortest path algorithm or some other combinatorical solver or even sampling from or taking the top k elements from some distribution something like this okay this is not the entire algorithm but this is one layer in the neural network right the layer really requires a discrete operation to continue the question is how can we back propagate through that in order to update the rest of the network specifically these upstream parts right here that are in front of it they need a gradient signal from the loss that's all the way over here at the end so what do we do we use this algorithm right here we forward propagate let's say we for propagate regularly in the backward pass we first compute a better a target distribution prop a parameter ization of the target distribution which essentially means we are going to construct a better problem definition a better problem definition that would make the downstream life easier so making the downstream life easier means that we move into the direction of the gradient of that downstream loss we move with a certain step size and then we ask ourselves well having this target distribution now can we make our in our upstream modules such that they provide the solver with something that's actually more close like that target distribution and that is exactly the gradient with respect to theta and that is going to be computed as a difference between two marginals as we've shown and we cannot compute the marginals because these distributions are very complex they have these constraint sets and so on but what we can do is we can compute most likely states that's exactly what these solvers do and if we compute the most likely states of these perturbed inputs that is going to be a good approximation good estimator for the marginals and there and then at the end we get the gradient there as substitute gradient that approximates the true gradient with respect to the input I just I want to highlight how why this is so complicated because essentially we have no idea how to back propagate through like a Dykstra shortest path algorithm the question is how do I need to change the input right here such that something based on the output changes in some way right for that I essentially need to know well if I change the graph a little bit like if I up way this edge right here how is the shortest path going to change and this is not a continuous process this is a discrete process right it's not going to change for a while until I up this too much and then all of a sudden swoop de boop the shortest path is a different route like it's really discontinuous so what we're going to do and that's going to be a problem of selecting the hyper parameters like the lambda and the temperature of the exponential distributions is going to be how exactly like how how noisy do I have to make this process to get an actual estimate of how my outputs change so essentially what I do is I perturb so this adding adding this noise right here I change my graph a little bit like this right and then sometimes the shortest path is going to change if I do this you know a million times then I have a good idea a little bit of how is my shortest path changing with respect to an input change so that's essentially what I do but the problem is I need to tune the hyper parameters if I change too little the shortest path is not going to change at all and I'm going to have no idea you know what how I need to adjust because there's no gradient if I change too much the shortest paths just going to fly around wildly changing every time and again I have no idea how to change anything in order to go into a specific direction so that's the challenge right here and the additional challenge I don't want to do it a million times for each forward and backward pass ideally you want to draw one sample and have that sample be a good low variance estimator of what I'm looking for cool so I've also like I've left out part of this like entire parts of this paper that you can still look at if you so desire but this is the basic idea again you can take this there's code you can take it like inside of a layer I think I have it open right here it's it's available there's code in torch and in tensorflow they give a little bit of an example of this is not the entire algorithm this is a little bit of an example of one part of that algorithm to essentially show this inner routine where you have to come up with good set of problem definition so here you see the essentially the let's say the true problem this is on the left you can walk on the bright paths and you cannot walk on the dark squares and you can see that if you for example sample the if you don't sample at all if the temperatures are set to zero then this is what you get it's it's you can see kind of the shortest path but it's not really good right if you up the temperature a little bit and let the algorithm do some exploration on you know using the inner algorithm you can see that over time you get a much better much clearer picture of what the supposed landscape is is looking like so this again this is not the entire thing this is just this inner part it's an illustration of why you need appropriate amount of noise for that inner part you can see that over time as the algorithm infers the essentially the the every time it solves the shortest path algorithm it gets a good idea with over time of how the landscape looks like all right I invite you to read the paper check out the code check out the video that was made by the authors themselves it's surely linked somewhere I'll link it and it'll give you a fresh perspective and with that and thank you so much for listening I'll see you next time bye bye oh there's experiments well okay well there's experiments there they're better than other stuff cool excellent bye
 Hello there! Today we're looking at implicit MLE back propagating through
 discrete exponential family distributions by Matthias Niepert, Pascal
 Minervini and Luca Franceschi. This paper is a paper that we've discussed in our
 regular paper discussions on Discord and so it is informed by everything that I
 have heard there. If you want to take part in these discussions and influence
 my opinions you're very welcome to do so. The link to the Discord is in the video
 description. Alright let's get into this paper right now. This paper proposes
 essentially a discrete layer for neural networks. This is maybe how I can
 describe it and the basic setup is in this figure right here. So let's say you
 have an input X which might be some sort of a continuous input like an image. They
 do give an example. By the way the authors they have quite helpful code
 that's available but also they have made themselves a little video about the
 paper and I also recommend that you go watch that video because it's quite
 helpful. So what they give as an example in the video which I find a good example
 is you have a map of and they use I think they use even Warcraft maps but you
 have a map and you know there's like a lake somewhere and then there's like a
 little house right here and so on. Your task is to go from the top left
 here to the bottom right. So you need to plan your way somehow through that. Now
 you don't get this as a graph that would be directly input into Dijkstra's
 algorithm however you get this as an actual image right. Yet the solution
 here is going to be some sort of a some sort of a path some sort of a gold path
 that's the label and or maybe something even derived from the gold path like how
 long the gold path is. So maybe that's five long or something like this. So it's
 very complicated you first need to recognize where can I even go based on
 the image on the left. Then you need to find the shortest path based on you've
 determined where to go. Then you need to evaluate based on that shortest path you
 need to evaluate some property for example as I said how long is the
 shortest path or just you know follow the shortest path on the actual map. So
 it's a mix of continuous and discrete elements and specifically the part in
 the middle that's described by this P of Z right here that is going to be some
 sort of a discrete solver. In the case here it's going to be a shortest path
 algorithm. Now the question is how can we run back propagation if we only have the
 label on the right hand side. How can we back propagate? I mean we can back
 propagate from the label through here right. This is a neural network that
 maybe determines some property of the shortest path but then how are we going
 to back propagate through this layer right here back to this neural network
 that's supposed to extract the input graph to the Dijkstra algorithm from the
 image. And that is a challenge there have been some solutions already for example
 some one famous example is a score matching. Sorry that is also an example
 but the famous example is the straight-through estimator. However that it
 doesn't always work it fails sometimes and specifically here the authors
 propose a different framework in this implicit MLE framework. I'm going to look
 at how that's built up. This is a very technical paper and I'm by no means an
 expert in these things I just try to give you a little bit of the idea of
 what's happening right here so that you know what's going on and if you have
 something like this in your neural network like a combinatorial optimization
 solver or anything like this then you can just go grab their code and use that
 as a layer it is really super simple. Alright that was the overview now let's
 get into the paper. Hold on this video is sponsored by weights and biases. Weights
 and biases is your one-stop shop for all your machine learning needs. It will
 track your experiments with a single line of code. It'll upload automatically
 all your logs all your configurations everything to your cloud. It will
 automatically grab all the output all the metrics all the configurations of
 your experiments and store that in one neat location so you can see your
 experiments you can track them wherever they run you can compare among the
 experiments but you can go further you can then tune your hyper parameters
 according to the results of those experiments and all of this is done
 automatically in a distributed way you can literally sit on your toilet on your
 smartphone and tune your hyper parameters and start new experiments but
 it's not only experiment tracking and hyper parameter tuning weights and biases
 has tools for the entire pipeline of machine learning research from the
 initial idea up until the deployment and beyond that when you actually want to
 track what you've deployed weights and biases has cool methods to track all of
 your data set and their dependencies to each other as well as your models and
 all kinds of other artifacts that you might produce a very powerful
 visualizations for all the inputs and outputs of your pipelines as well as the
 models themselves all of this runs in the cloud but if you're concerned about
 privacy there are options to self host the system is free for personal use and
 for academics and they have great plans for enterprises small teams large teams
 doesn't matter so thank you very much weights and biases for sponsoring this
 video if you don't know them yet absolutely check them out it's free it'll
 make your life a whole lot easier now let's get into the video
 as I said the the the problem right here is that you have these kind of these
 kind of discrete tasks sometimes as a part of an entire learning setup so the
 paper makes different contributions but here are they here they're listed out
 they say we propose implicit maximum likelihood estimation as a framework for
 computing gradients with respect to the parameters of discrete exponential
 family distributions so what we want is of course gradients gradients of this
 discrete process in the middle and the discrete process specifically is going to
 be formulated as a exponential family distribution and we're going to see how
 that happens they say we show that this framework is used for useful for back
 propagating radiance through both discrete probability distributions and
 discrete optimization algorithm sorry sorry optimization problems and that
 would be the example right here would be a a Dykstra shortest path algorithm or an
 integer linear program solver or anything like this in fact they're one
 of the general formulations they have is for integer linear program solving I am
 Ali requires two ingredients a family of target distribution Q and a method to
 sample from complex discrete distributions we propose two families of
 target distributions and a family of noise distributions for gumble max based
 sampling so we're going to check look into how that works and exactly what it
 contributes and then yeah we show that this simplifies explicit to explicit
 maximum maximum likelihood learning when used in some studied settings and
 experimental evaluation these points were probably not going to go into too
 much essentially in point four they show that for some settings this reflects
 already established methods so it's in sort of a generalization of methods that
 have already been around of methods that are maybe specific to a given setting or
 problem and the experimental results well you just like their experimental
 results essentially show that their method for example out compete the
 straight-through estimator method so what's the deal with discrete things in
 neural networks the problem is of course that we can't compute gradient with
 respect to discrete things now take for example the straight-through estimator
 the problem it's trying to solve or one of the problems you can formulate it like
 this you have some X you put it into neural network and out in the middle
 somewhere you it you are required for some reason to sample from some sort of
 distribution for example you're required to this produces a produces a probability
 distribution over a few classes let's say over four classes and then what
 you're going to do is you're going to sample one of the classes right here and
 then you're going to continue with that through the nest the rest of your neural
 network until you're at the label now again as before you need to back
 propagate in order to learn through this network which is easy but through the
 choice through the sampling procedure of that of that inner layer and that's hard
 so what the straight-through estimator does is it's a bit of a trick it
 essentially in the forward pass you do the discrete optimization you do the
 sampling but in the backward pass you you act as if you simply propagated the
 distribution as such so for the to the forward pass it is really a discrete
 sample but to the backward pass it looks like you've simply you did you never
 sampled you simply pass the whole distribution say well I'm not sure it's
 like 70% this and 30% this the way you would implement that usually as you have
 some signal let's call that H for for maybe that's the histogram right here
 and what you would do is you would if you sample from H that was going to give
 you like S well let's say let's say we take the most likely state right so we
 determine H and we take the most likely state which which is let's say S is the
 R of max of H okay that is your sample now what you would do in your forward
 pass is you compute the next layer H prime as S which and then plus H minus a
 stop gradient of H so the stop gradient
 am I doing this correct no of course not of course not yes oh yes I'm doing this
 correctly of course okay so let's analyze this in the forward pass the stop
 gradient has no effect on the forward signal so these two here essentially
 cancel out these cancel out to zero however in the backward pass right since
 derivation is distributes over addition and subtraction what you would do if you
 were to derive the gradient of H prime that's essentially the gradient of S
 plus the gradient of H plus the gradient of stop gradient of H now stop sorry
 minus minus stop gradient of H obviously has no gradient so that goes to zero
 the gradient of S is also zero because it's a discrete operation and most of
 these frameworks simply tell you well the gradient is zero it's a discrete
 optimist operation if you're not sure that this is happening you may in fact
 also put a stop gradient operator around s and you can see what remains is the
 gradient of H so you see the trick in the forward pass these two cancel out
 however since in the backward pass this by itself is already zero because of the
 stop gradient operation the gradient of H remains right here this is a trick you
 can you can simply swap out a gradient in the backward pass for whatever you
 like with this trick people have used this to get gradients with respect to
 discrete operations like this but this paper right here is an alternative and
 as they show in some situations it is more appropriate to use that alternative
 however it is also quite a bit more tricky so what's the first thing we're
 going to do the first thing we're going to do is we're going to take that inner
 thing right here that inner procedure and again let's go back to the task of
 of finding the shortest path so what's the input the input is some sort of a
 graph right where you need to find the shortest path with cost associated with
 each of the edges and some some start and some end goal and what we want is
 the shortest path some sort something like this now the first thing we're
 going to do is we're going to encode this problem into a binary vector now how
 exactly we do this is is I don't really know for for shortest path problems but
 we're going to encode this into essentially another binary vector but
 I'm going to encode the problem into this vector theta right here so theta in
 this case what you would do is your theta vector let's this is the theta
 vector it will have I guess hmm it will have probably for each edge it will have
 an entry with the negative cost of that edge associated in the vector so the
 negative cost of edge one the negative cost of edge two the negative cost of
 edge three now why are we doing this you can see that we are going to multiply
 this theta with another vector called z and z here is the let's call it the
 solution or the proposed solution to this inner problem and z is now a
 binary vector so z can eat either be 1 or 0 in each entry and it's going to be
 1 if and only if this edge here is part of the proposed solution so any path in
 this graph can be represented by a given z variable right by simply setting a
 bunch of things to 1 and 0 I can I can select some of the edges and if I have
 selected the correct ones they will form a path and if I have selected the
 absolutely correct ones they will in fact form the shortest path you can
 immediately see that for the shortest path the inner product between the two
 vectors will be the highest among all the paths right so this is how I
 formulate my problem I'm formulating my problem between as an inner product
 between a binary vector and some sort of a weight vector theta such that for the
 solution of the inner problem like the shortest path algorithm or the case
 subset selection or the integer linear program such that for the solution of
 this problem it is the case that this inner product is the highest possible
 now you immediately see that of course I can make that inner product even higher
 by putting all of the edges to zero right so you know z right here I can
 simply say zero zero zero zero zero all the costs here are negative ergo I have
 no negative cost ergo that is going to be zero and that is going to be the
 largest possible I've solved the problem what's the problem this isn't a path in
 the original formulation so the last ingredient we're missing right here is
 what they sometimes here call capital C this thing right here capital C is a
 constraint set so capital C would define in this case what the valid entries for
 the z vector are so z must be in this capital C class and I think C must be
 yes that defines what the valid valid valid solutions even look like so in the
 simplest case if this is a classification problem right this is a
 classification problem theta would sort of yeah faith you can you can think of
 this is a classification problem and then z would be selecting the class
 right you can model theta in this case as just a vector of ones and then z
 right here could select the class by simply putting that entry to one
 wherever of whatever class is selected and the constraint set C could be
 easily modeled by saying the norm what is that the sum of all the entries
 which is probably the one norm of z must be equal to one right that could be the
 constraint set am I correct here I'm not sure I can actually model I probably
 can't model it like this like here there probably needs to be like there probably
 needs to be some some sort of cost per class or something like here and then I
 can model the constraint as saying the inner product of z with a vector of ones
 must be equal to one that looks better so that is actually part of the
 definition of the constraint set and the the problem in these cases is that this
 constraint set makes it very difficult on on obtaining good gradients through
 this discrete through this discrete problem because right here as you can
 see it's it's not really easy because most of the z vectors in the Dykstra
 problem aren't actually valid paths so the issue here is that we need a gradient
 we need to respect the constraint set of the problem they go ahead and they
 formulate this as I said as this problem where you have a vector this vector z is
 whatever solution you propose the theta is the definition of the problem the
 inner product is sort of the the reward let's say the yeah the reward maybe the
 inverse loss of the problem and they can now formulate this as a exponential
 family distribution by simply raising this by putting this inside of an
 exponential function let's see they've done it somewhere somewhere right here
 look at that oh it's not even a it's not even a minus sign all right so for now
 just trust them that it is necessary to formulate it as a distribution and and
 don't just kind of hang in there it is going to get very complicated but it is
 going to lead somewhere so they can formulate this inner process as a
 probability distribution P of Z where that is according to the exponential
 family so as I said the exponential family here you put in this thing right
 here there is a temperature at which you sample so what is that essentially is
 going to do is going to normalize given this right here this is the the log
 partition functions the normalization constant this is essentially going to
 give you a distribution over the individual dimensions of the Z vector
 and that is going to be normalized and is going to be more peaky or less peaky
 depending on the temperature right here so the process that they formulate this
 as is you take some input X right here you put it through the first neural
 network to obtain the theta the theta is essentially the problem definition for
 the inner algorithm the inner algorithm you formulate as a probability
 distribution so it's going to have more or less likely states with the more
 likely states being the ones that solve the inner optimization problem more
 perfectly to more reward so Z is going to be a random variable that is
 according to that distribution for now you can just think of Z is a random
 variable and the likely states of Z are the ones that have the paths that have a
 very short path through the in our example or whatever states solve the
 inner problem very accurately and then from that Z we're going to put that
 through another neural network that's going to give us our output and we're
 going to compare the output with the gold label and then we're going to
 backpropagate through all of it our parameters are the parameters here and
 here so the parameters of the two neural networks fu right here this is easy to
 do right because we can simply back propagate from y into the neural
 network and the parameters of HV the V parameters this is hard this is the hard
 part so what do we need to do in order to back propagate all the way to H sorry
 to the V variables well what we need to do is we need to the direction here is
 that the parameters sorry X becomes theta becomes Z comes y this is with
 the help of the parameters V and this is the help of the parameters you right you
 is easy for V what we need to do if we want to have the what you can see right
 here the gradient with respect to V we first need the gradient with respect to
 theta and then we can once we have the gradient with respect to theta where is
 it where is it I guess here once we have the parameters with respect to theta we
 can use the the back propagation algorithm again to back propagate into
 this network and change the weights V so how do we get the gradients with respect
 to theta again this is means we have to back propagate through this piece right
 here which is the inner optimization algorithm so the here is it here's the
 chain rule expanded this is this here that's theta and so we need the
 parameters the gradient with respect to theta and then we can use back prop okay
 this by the way is the entire algorithm as it's going to be later you can see
 it's fairly simple you can also see there is a lot take mistake right here
 but I think that's my conversion so that what they do is they say this it's very
 hard it's very very hard to compute this gradient with respect to this inner
 optimization procedure right it's very hard to compute a gradient with respect
 to the Dykstra shortest path algorithm essentially you'd have to know how do I
 need to change my graph definition in order for the path to become shorter or
 in different in some way and that's very hard like all you can do really is kind
 of try and see what happens I wouldn't know anywhere
 anyhow else because yeah remember that what the theta is the theta is the
 output of the first neural network so the theta is the definition of the graph
 and that is produced by by this neural network right here that looks at the
 picture and gives you the discrete graph so essentially what it gives you is an
 adjacency and an adjacency matrix but still so the question is you know how
 does my adjacency matrix need to change for the Dykstra algorithm to find a
 shorter path let's say a shorter path or well or a path that is more close to the
 gold label that I have because you don't always want to shorter you actually want
 to learn from data so the first step they do in this challenge in this sub
 challenge right here is they say this is too hard we're going to replace the loss
 right here this loss the true loss of our output compared to the label with a
 surrogate loss this L is an implicitly defined a maximum likelihood objective
 and we're going to calculate its gradient instead of the gradient of our
 true loss now the logic of how we get there is the following in this inner
 problem we define a probability distribution this probability distribution
 remember what is this P here P describes the solution space of in our case the
 Dykstra algorithm so P is a distribution that would assign high value to or high
 likelihood to paths that are very short in the graph that's defined by theta and
 low value to paths that are very long in this same graph right now what we can say
 is can we this is essentially a distribution can we find a different
 distribution we call a target distribution where we can show that in
 expectation the loss the loss from this target distribution right here is always
 smaller than the loss from the true distribution so essentially can we find
 the distribution that where the paths that it outputs are lower in loss lower
 in the final loss than the ones we have so remember we have X and all of that
 and the end there is Y right we predict Y and we compare the Y to the true Y
 there's going to be some loss and the question is can we reduce that loss
 right here so we don't necessarily want to find theta such that we find a
 shorter path but we want to find a more appropriate theta in here such that the
 rest of the neural network can predict Y hat more accurately in order to be
 closer to Y for in the in our example we want to if if our neural network right
 here is very bad at actually extracting a proper walkable graph from the
 landscape right here like if it doesn't recognize that this is a lake you know
 it thinks you added all of this is really fine to walk on and so on the
 graph right here will be quite crappy the weights on the edges will be not
 accurate right it's not inferred correctly from the landscape that means
 that this network here will have a pretty hard time determining the actual
 value of the shortest path because even though the Dijkstra algorithm does a
 good job of finding the shortest path it's on the wrong graph and therefore
 it's useless so what we need to be able to do is we need to be able to more
 accurately extract the graph from the image so we need to train these
 parameters right here so here we ask ourselves can we come up this
 distribution P here that's the distribution of solutions to the problem
 that's defined by theta we ask ourselves can we come up with a
 distribution that has a lower loss than the distribution we have and the answer
 is going to be yes we can do so with a simple a simple let's say trick so if
 you look at back at this I realize we're in like three layers deep of problems
 like we have a problem for that we have another problem to solve for that we
 have another problem self our current problem is that we want to see can can
 we change this distribution such that the loss is lower how do we need to
 change this distribution essentially and the answer is going to be we're going
 to take the output right here and we're going to pass it through this network
 we're going to look at the loss and we're going to back propagate that loss until
 the point where this algorithm stops and then we're going to take one gradient
 step into the direction right here and then that is going to be our new
 distribution so what does that mean in our example right here we're going to
 take the graph that we output right here we're going to run it through Dijkstra
 gives us the shortest path remember this is a crappy graph because our network
 initially is not good we're going to put that through this neural network right
 here that determines the cost and we're going to calculate the loss and back
 propagate that so what does that give us ultimately that tells us well the
 gradient says what how do I need to change the output right here in order
 for the neural network that follows to do a better job right and let's say the
 output is well this edge here has a bad weight or in fact this edge there's an
 edge right here that's missing or or something like this not sorry no that is
 formulated wrongly what we are going to change is we're going to change obviously
 the Z which is the solution so it's going to say in this shortest path that
 you computed there's something wrong for example you should have maybe taken a
 different shortest path or you should have weighed it differently or something
 like this and we're going to take a step into that direction so for example if
 the shortest path rather than up and over should have gone directly we know
 that the edge right here should have had maybe a lower cost associated with it or
 something like this so we're going to use gradient descent to see how do we
 need to change the inner problem such that the rest of the pipeline does a
 better job and that's what you see that's what you see right here somewhere
 there okay so this is the target distribution is this right here so it's
 the same as the regular distribution of inner solutions however instead of
 inputting the graph as it is we're going to input the graph minus a step size
 times the gradient of the loss with respect to the output of the inner of
 with respect to the output of the inner solver so this is using gradient descent
 in order to come up with a better problem definition right here since these
 two are vectors they're multiplied together we can use in fact the gradient
 with respect to z and subtract that from theta because they're of the same
 dimension right so we're going to ask ourselves what would be what would be a
 more appropriate problem definition in order for the rest of the network to do
 a better job and that's going to be our so-called target distribution and now
 our job now we have a pretty simple job our job is going to be well can we make
 it such that the current the current graph that we output right here is more
 like this target graph so can we make the distribution p more like the
 distribution Q is the same as asking can we make the current graph that was
 output by the network H more like the graph that would be more optimal for the
 rest of the network and that is let's say a solvable problem in fact if you
 work it out the formulas get pretty simple so if we do it like this and by
 the way this inequality here is crucial obviously because and but we see why
 it's given because of gradient descent we're in expectation guaranteed that
 the Q distribution is going to have a lower loss than the p distribution
 because we do one step of gradient descent with respect to the loss right
 so essentially we do step of gradient descent in the inside and then our
 surrogate loss is going to be well can we make the output distribution more
 like the result of that gradient descent this this must be one of the most
 confusing videos ever but I hope you're still with us so what we want is to make
 these two distributions closer remember we said we can't back propagate through
 the discrete optimization procedure so what do we do we said instead of back
 instead of back propagating through the inner optimization procedure we're
 going to replace that by a new objective the new objective has two steps step one
 determine what would be what would be a better output for for the discrete sorry
 what would be a better input for the discrete solver and then step two is can
 we make the input that we've received more like the input to the discrete
 solver right this is where this where we do the gradient descent inside and how
 are we going to make distributions more like each other that's this right here
 this is the KL divergence between P the actual distribution and Q the target
 distribution and that's going to be our surrogate loss that we use instead of
 the loss that we cannot differentiate if you if these are both exponential
 distribute exponential family distributions you'll see that this pretty
 easily cancels all cancels out and reduces and in the end the gradient of
 this surrogate loss simply going to be the difference between the two
 marginals so between the two means of the distributions now this seems pretty
 easy but inside of the three layers of problems we get another problem so what
 does this mean this is the mean of the exponential family distribution when
 given a certain definition problem definition theta prime or theta if you
 are over over here this given that it's a let's say it's a hard problem with
 these constraints at and so on calculating the mean of such a
 distribution is hard it's in fact probably as hard as as solving the the
 entire problem itself so calculating the mean of these distributions is not an
 easy task sampling from these distributions straightforwardly is also
 not an easy task so what this paper does is it says for under certain conditions
 what we can do is we can replace the mean with this and this is a trick well
 a trick a method that they call perturb and map by map they mean maximum
 a posteriori so essentially means that for the exponential distributions what we
 can do is we can approximate the mean using map the most likely state and
 what's the most likely state for example in this di extra algorithm the most
 likely state is in fact the shortest path by how we describe how we define the
 problem right so we've defined the problem as the inner product between the
 problem definition and the proposed solution now what's the most likely
 proposed solution if likelihood is given by the inner product obviously the one
 that maximizes the inner product which is the one that by construction has the
 shortest path okay so fairly convoluted but this is something we can actually do
 so we cannot calculate the means of these distributions but we can calculate
 the most likely states and it's not so straightforward in fact it is a better
 estimate so they consider I think yes so you're computing the marginals is in
 general a what's that sharp p sharp hard problem scales poorly with
 dimensionality so map states are often used to directly approximate the the
 means however it's apparently better if you use this perturb and map this
 strategy where you estimate the mean not directly as the most likely state but as
 an expectation sampling from a noise distribution and perturbing this state
 what does that mean that means that you can get the mean of the distribution
 let's again draw our di extra graph right here like that you can get the
 mean of this distribution by wealth by slightly perturbing the problem so maybe
 slightly reweighing the edges saying this edge is higher this edge is now
 lower slightly perturbing a lot of times and then every time you calculate the
 shortest path so most of the time like this will be the shortest path most for
 most of this but then every now and then you'd perturb it so hard that you know
 this edge now goes up very high in cost so then you'd have this as the shortest
 path right here and so on but ultimately yeah so adding all of that up getting
 the expectations over all the shortest paths in oil for a lot of perturbations
 will give you a good approximation of the mean of that distribution the last
 question is a little bit okay what noise distribution is appropriate for this and
 the answer is going to be the answer is going to be that is going to be a gumble
 noise and I think this is this now gets a little bit too deep but just to
 mention this right here if in fact there are some properties are given and the
 specific property that needs to be given for this to be accurate is that you can
 define the problem always such that such that the constraint set is given by a
 number K and where you can see right here exactly K entries in Z have to be
 one if that's obviously not covering all of the problems we've considered but it
 covers a lot of the problems we've considered and even if not you can still
 apply it as I as they say it's just not as appropriate but still appropriate
 enough and they also have a way to sample gumble distributed random
 variables but I don't think necessarily we need to go into that you just need to
 know that the appropriate noise distribution in fact to get a good
 estimate of the mean is a gumble noise gumble distribution by the way it
 describes extremal values so if you want to know the distribution of of the
 maxima of some phenomenon that will be gumble distributed and then you have it
 at the end of the day you would be this surrogate gradient would be given by the
 difference between perturbed maximum sorry the maximum a posteriori solutions
 of perturbed Thetas right here and yeah so this is a few layers deep let's
 actually look at the entire algorithm and you'll see it's not that hard so
 what do we do in the forward pass we take X and as I said we get theta this
 is a neural network in our case it takes a picture and it extracts the adjacency
 matrix which is theta so it extracts the graph that we're now going to run
 Dykstra on okay so this data goes into this forward pass right here what do we
 do in fact we forward propagate the maximum a posteriori state of a
 perturbed version of theta and this year if you remember this year is going to
 give us the mean that's a wrong new is going to give us the mean of that
 distribution that we're looking for okay so it's going to be for were
 propagated in so that is going to be forward propagated to let's say to the
 second neural network and that's going to give us why or at least an estimate
 of why and then we're going to compare to the real why we're going to get the
 loss and now we're back propagating right so back propagating we take the
 loss we go back we go back through this first neural network until we're here
 and that is where to start so the backward pass that would come in here
 right this gradient here that's the gradient we get from the chain rule in
 the backward pass we also need this step size lambda right here okay so what are
 we going to do we're going to take that gradient and rather than giving it
 straight to like the straight through estimator or to the chain rule we're
 going to compute and update to the theta to our graph definition right to our
 adjacency matrix or our our cost cost matrix for the shortest path algorithm
 essentially saying how do I need to change the problem definition for the
 Dijkstra algorithm in order to in order for the upstream sorry for the downstream
 modules to do a better job predicting the correct label why that's so we're
 going to compute an updated theta then we're going to compute a this surrogate
 loss right here and the surrogate loss as you've seen right here is going to be
 the difference between the two max perturbed maximum a posteriori things so
 it's going to be by the results that we've derived where was it where was it
 here by these results right here remember this is the gradient this is
 directly the gradient of our surrogate loss and the surrogate losses can we
 make the output of the first neural network closer to something that's more
 useful so the gradient is directly given by the difference between these two
 things so by the difference of marginals which we approximate by the difference
 of maximum of posteriori so this requires us to run Dijkstra once here in the
 forward pass and then it requires it to run Dijkstra again here once on the on
 this updated graph and the difference between the two is going to be the
 gradient in which we have to update our inputs okay notice that I'm I've talked
 I think a bit confusingly so here I already said how do we need to update
 our problem definition right and you could think that you know we could feed
 that directly upstream but we can't the real gradient we want to feed upstream
 is right is this thing right here so essentially the top thing is how do we
 need to change our problem definition so the downstream neural network can do a
 better job and this right here is that what or sorry how does the upstream
 network so the one that maps X to theta how does that need to change its
 behavior in order to produce a better input to the solver yes that is the
 least confusing I can say it and then we return the gradient that gradient that
 we computed and this is our substitute gradient for the gradient that would be
 this is our substitute gradient for the gradient of the true loss with respect
 to theta and since it's a gradient with respect to theta we can continue back
 propagating through here back probating it into this neural network here and
 update the weights so that is it the only thing I'm not sure about is if they
 really return the Z hat right here like it was my impression that in the forward
 pass they would actually feed the true the true Z upstream but I'm not sure
 because for example where was it yeah here they rely on Z bar which is Z bar
 is essentially that's mu so not sure exactly we might have to look at the
 code exactly but I hope you understand a little bit of what's going on right here
 yeah so recap we have some discrete part in our neural network like a shortest
 path algorithm or some other combinatorical solver or even sampling
 from or taking the top k elements from some distribution something like this
 okay this is not the entire algorithm but this is one layer in the neural
 network right the layer really requires a discrete operation to continue the
 question is how can we back propagate through that in order to update the rest
 of the network specifically these upstream parts right here that are in
 front of it they need a gradient signal from the loss that's all the way over
 here at the end so what do we do we use this algorithm right here we forward
 propagate let's say we for propagate regularly in the backward pass we first
 compute a better a target distribution prop a parameter ization of the target
 distribution which essentially means we are going to construct a better problem
 definition a better problem definition that would make the downstream life
 easier so making the downstream life easier means that we move into the
 direction of the gradient of that downstream loss we move with a certain
 step size and then we ask ourselves well having this target distribution now can
 we make our in our upstream modules such that they provide the solver with
 something that's actually more close like that target distribution and that
 is exactly the gradient with respect to theta and that is going to be computed
 as a difference between two marginals as we've shown and we cannot compute the
 marginals because these distributions are very complex they have these
 constraint sets and so on but what we can do is we can compute most likely
 states that's exactly what these solvers do and if we compute the most likely
 states of these perturbed inputs that is going to be a good approximation good
 estimator for the marginals and there and then at the end we get the gradient
 there as substitute gradient that approximates the true gradient with
 respect to the input I just I want to highlight how why this is so complicated
 because essentially we have no idea how to back propagate through like a
 Dykstra shortest path algorithm the question is how do I need to change
 the input right here such that something based on the output changes in some way
 right for that I essentially need to know well if I change the graph a little bit
 like if I up way this edge right here how is the shortest path going to change
 and this is not a continuous process this is a discrete process right it's
 not going to change for a while until I up this too much and then all of a
 sudden swoop de boop the shortest path is a different route like it's really
 discontinuous so what we're going to do and that's going to be a problem of
 selecting the hyper parameters like the lambda and the temperature of the
 exponential distributions is going to be how exactly like how how noisy do I have
 to make this process to get an actual estimate of how my outputs change so
 essentially what I do is I perturb so this adding adding this noise right here
 I change my graph a little bit like this right and then sometimes the shortest
 path is going to change if I do this you know a million times then I have a good
 idea a little bit of how is my shortest path changing with respect to an input
 change so that's essentially what I do but the problem is I need to tune the
 hyper parameters if I change too little the shortest path is not going to change
 at all and I'm going to have no idea you know what how I need to adjust because
 there's no gradient if I change too much the shortest paths just going to fly
 around wildly changing every time and again I have no idea how to change
 anything in order to go into a specific direction so that's the challenge right
 here and the additional challenge I don't want to do it a million times for
 each forward and backward pass ideally you want to draw one sample and have
 that sample be a good low variance estimator of what I'm looking for cool
 so I've also like I've left out part of this like entire parts of this paper
 that you can still look at if you so desire but this is the basic idea again
 you can take this there's code you can take it like inside of a layer I think I
 have it open right here it's it's available there's code in torch and in
 tensorflow they give a little bit of an example of this is not the entire
 algorithm this is a little bit of an example of one part of that algorithm to
 essentially show this inner routine where you have to come up with good set
 of problem definition so here you see the essentially the let's say the true
 problem this is on the left you can walk on the bright paths and you cannot walk
 on the dark squares and you can see that if you for example sample the if you
 don't sample at all if the temperatures are set to zero then this is what you
 get it's it's you can see kind of the shortest path but it's not really good
 right if you up the temperature a little bit and let the algorithm do some
 exploration on you know using the inner algorithm you can see that over time you
 get a much better much clearer picture of what the supposed landscape is is
 looking like so this again this is not the entire thing this is just this inner
 part it's an illustration of why you need appropriate amount of noise for
 that inner part you can see that over time as the algorithm infers the
 essentially the the every time it solves the shortest path algorithm it gets a
 good idea with over time of how the landscape looks like all right I invite
 you to read the paper check out the code check out the video that was made by the
 authors themselves it's surely linked somewhere I'll link it and it'll give
 you a fresh perspective and with that and thank you so much for listening I'll
 see you next time bye bye oh there's experiments well okay well there's
 experiments there they're better than other stuff cool excellent bye