Scale By The Bay 2018: Jayant Krishnamurthy, Structured Deep Learning with Probabilistic Neural Prog
I'm Janet and today I'm gonna talk to you about a library that we've developed for doing structured prediction with deep neural networks this library makes it really easy to express train and make predictions with these complex machine learning models we use this at Microsoft somatic machines for a bunch of different models and we've we've really had good success with it so I'm excited to talk to you about this today and what I'm gonna do is I'm just gonna spend a couple minutes explaining like what the problem is that we're trying to solve with this library because I know it's a little bit jargony if you're not in the machine learning space and then I'm actually going to just kind of start coding up some examples and we'll kind of build our way up to kind of a cool demo at the end okay you can see I've brought my keyboard so I'm ready to go okay so um just to look don't do that there we go okay just to motivate the kinds of problems that we're trying to solve in this talk let's consider the problem of converting from natural language into a computer program can you guys see the slide that's good so this is kind of a machine learning problem that you can imagine that any sort of digital assistant has to solve right if you're like Alexa or you're okay Google or something like that right someone gives you a command and you have to figure out what to do and how do you think about what to do well it's a program that you need to run to do the thing that the user wanted okay and this is a hard machine learning problem compared to something like classification which you may have seen for two reasons first of all the output space is very large the set of computer programs is infinite right so you can't have to pick amongst this like infinite set of outputs the second reason is that the space has complex structure so you can't just generate any sequence of symbols and have that be a valid program right there's things like type constraints which you need to satisfy when you're generating the output in order to get a well-formed program and these are the two characteristics of structured prediction problems they have a large output space with complex constraints okay and so our goal is gonna be to train machine learning models for problems like this and we're actually gonna build a demo of exactly this problem okay so I will just show you that we're not going to do sort of the full assistant domain but we're gonna do a little natural language calculator okay so let me just show you what that's gonna look like okay so I've can you see this hmm how do I make this bigger does anyone know not like that well okay this hi as I try to sort of the the normal thing okay hmm that's not good well okay if someone can figure how to make this bigger I'd really appreciate it but for now we'll just run with this so here's the calculator that I have and you can type in something like what is the average of eight and four and it actually computes the answer to the question and also produces a computation and sort of a prefix notation which we'll explain later and it produces the probability for that so in this talk we're actually gonna work our way up to building this model okay okay so just coming back to structured prediction the other thing I want to say just about this briefly is that there's many kinds of structured prediction problems it's not just this language the code one okay and each of these structured prediction problems has a different output space that you want to think about so for example in this problem of syntactic parsing the output space is the set of all trees that span the sentence and our goal with this library is to develop a library that makes it really easy to build machine learning problems for machine learning models for any kind of structure prediction problem with any kind of output space okay and we've developed the library oh my god we've developed the library for this problem that we call probabilistic neural programs and a probable signor program basically combines two different representations into one library the first thing is it has a representation of a structured output space which is basically a probability monad if you know what that is if you don't don't worry about it I'll explain it the second thing is that it has a library for expressing neural networks and what's important about this library is that it allows these two components to interact so the neural network is actually going to be able to assign the probabilities of the structured output space and then the path you take this out to space is actually going to define the neural network itself and this interaction is what lets us express these structured prediction problems in a very you're away so if you've seen other machine learning libraries like tensorflow they kind of just dude this half of the picture and if you've seen things like probabilistic programming languages they do this half of the picture and ours is the only library that really combines these things together and we'll see that that makes a very natural representation for the kinds of problems that we want to solve ok so that's basically the end of the intro part I'm now going to start doing some live coding and I'm gonna do this in sort of four chunks the first thing I'm gonna do is I'm just going to show you how we can represent some simple probability distributions in P and P then I'll show you how we can actually train these probability distributions so the probabilities are estimated from a data set and then finally both two things I'll show you how you put neural networks into that process and then I'll show you how we can assemble the demo okay so let's get started okay so you just get the setup so okay to express probability just reaches in P and P there's basically two ways to do it and to think about the first way let's define a probability distribution that represents flipping a coin okay so I'm gonna make a function which takes a probability and this is gonna return a sorry this is def coding in front of crowd makes me nervous okay so this is a gonna be a function that represents a Wow let's put that in the middle of the thing okay that represents flipping a coin and whenever you see a P and P of X think about this as a probability distribution over things of type X okay and we can define this in terms of this function called P and P twos which basically just represents a probability distribution over a list of things so I can give it true and false and I can give it the probabilities that I want so true will be probability and this will be one minus probability and I'm done this is now probability tribution so let's see what happens if we print out this distribution okay so if you print out this diffusion it's this line you can see we just get some crazy thing the reason we get a crazy thing is because PN P is a lazy representation of the distribution remember we're trying to represent these like infinitely large distributions so we can't actually you know enumerate all the outcomes and assign them probabilities so if you have one of these lazy representations of the distribution the way you go from that to probabilities is you run inference so you can think about inference is basically just you know exploring parts of the distribution using some strategy and right it's sort of like a there's a tree of executions do you explore it in some way so there's many different inference algorithms you can run you can do like sampling sometimes there's dynamic programs depending on your model in our case we're gonna do a sort of simple search okay just for this talk so if we run inference on this probability distribution you can see we get what we'd expect we get false and true with sort of 50/50 probability okay so this is obviously a simple distribution the second way that you can build probability distributions is you can compose other distributions together and P and P is a monad so you can do it using flat map or for yield so let's define a distribution over to plan flips we can just do flip and say they're different and I'll just return a tuple of the two flips and we'll just comment this out okay so you can see here we get sort of the distribution you'd expect for flipping two coins right and the two different outcomes of the two different coins okay now these two primitives can be combined in powerful ways to make much more complicated distributions so to show you that let's define a binomial distribution so a binomial distribution is I'm gonna flip num coins each of which comes up heads with probability and it's the distribution over the number of heads that I got right so it's a distribution of our integers as you can see right here and the way we can do this is we can define this as a recursive function so we could say if I'm flipping zero coins obviously the answer is zero and pmq top value just puts the thing into the moon map otherwise what I'm gonna do is I'll flip num minus 1 coins and I'll figure out how many heads I got there then I'll flip my current coin and then if the current coin is heads then I'll return the count plus 1 otherwise I'll just return the count right so I'm just adding up the number of heads that I got and we can run the inference on this guy let's say we flipped five coins probability 1/2 and this out okay so you can see here again we get sort of the distribution that you'd expect okay now I said that we'd be using these probability distributions to kind of represent the output spaces of our structured prediction model and I'm gonna show you how we can do that right now and the way I'll do that is I'll actually build the output space of our natural language calculator so conceptually what do we want to do we want to produce like an arithmetic expression all right so we can think about that as like a tree you know something like this right but instead of like having a data structure for trees and stuff just for this talk to make it simpler I'm just gonna generate a sequence of operations like this so it's just a prefix traversal of that tree okay and one thing you have to watch out for though is not every sequence of operations is legitimate right so this sequence of operations isn't well-formed because there aren't enough arguments to the operations ok so we just need to define a distribution over these sequences of well-formed operations and to do that let me just copy paste in a representation of an operation it's not super interesting okay so I've just defined this thing called an op it's just a you know type unsafe a wrapper around the Scala function and it has a name it has the number of arguments that it expects the arity and then it just has a function that will call to evaluate it these are just helpers for making some operations and this just makes the pretty printer work so ignore the implicit and then I've defined some operations so I've defined the numbers 1 2 & 3 and then I've defined addition and multiplication okay so given these operations let's define our distribution over these arithmetic expressions now to a first approximation what I want is just a distribution over sequences of ops right so something like this and one way I can get that is I can just pick an OP this just means choose with uniform probability and then I can generate the rest of the sequence and then I can do something like this okay so this has two problems the first problem is it obviously doesn't satisfy our well form in this property because I'm just picking the operations in random right the second problem is all the sequences in this distribution are infinitely long so this will never finish no matter what you do right so I'm gonna solve both of these problems by just tracking sort of where we are in the tree and the only thing I need to track for this is basically how many expressions like complete expressions I need to generate before I'm finished so I'll just make an argument called remaining and basically if I don't need to generate anything else I can just stop otherwise what I can do is I do the same thing I'm doing here and I just need to figure out how many new arguments I need so for this the way to think about it is I've generated an operation right so I'm gonna subtract one from the remaining thing because this operations being fed into something from before right but my the operation I generated might itself have arguments so I need to you know generate all of those in the future and then I just need to pass this down another way you can think about this remaining thing is I'm just tracking like the size of the stack of like the sort of things I need to fill in for the tree and I'm just tracking the count instead of tracking sort of explicitly what needs to get filled in okay I'm sorry say it again error oh no no because this is just a this isn't in the Monad it's just uh it's just a number yeah yeah okay so let's see what happens if we run inference on this expression I need to pass one gear cuz I want one guy hmm okay so we ran inference and you can see here we get some huge lists of these expressions right and I'll point out two things first of all inference didn't run forever right so there are arbitrarily long sequences of operations in this distribution okay but because the inference is approximating like it's doing an approximate search of this distribution it doesn't take infinitely long the second thing is just you know if you look at these lists you can see that they are in fact well-formed lists right like every operator has all the arguments that it has or needs so this is how we're going to define basically the output space of our structure prediction model and I'm actually just gonna copy paste this code later to do the actual modeling okay okay so that's sort of the end of this probability distribution unit I've basically shown you how you can define probability distributions in P and P basically in terms of non-deterministic choices and composing those together now throughout this part of the talk everything has been using sort of probabilities that I've specified statically as like arguments these functions right but when we're doing machine learning we really want to like learn those probabilities from a data set so in the next part of the talk I'm going to show you how we can basically learn those probabilities using data okay that's the training portion and for this I have a new app okay so to define a trainable probability distribution in P NP has three steps the first thing you need to do is you basically need to allocate some model parameters and these are just numbers just think about them as a collection of vectors and matrices what have you that are going to get optimized by training to fit your data set the next thing you need to do is you need to define your distribution in terms of these parameters okay and then once you've done that you'll be able to call some generic training operations that will fit the parameters using Stata so we just ought to do those three steps and to UM to do those let's do a very simple example of training a coin flip okay so I'm gonna I'm gonna add some parameters each parameter has a name which we can use to refer to it later and it has a dimensionality so this is like the dimensionality of its matrix or a tensor I'm just gonna make a two dimensional vector because we're just gonna have a probability of true and a probability of false okay so this is step one step two is to make our define our distribution in terms of these parameters and previously I told you that this like PNP boolean is a probability distribution over boolean s-- well actually it's a function for model parameters to probability distributions over boolean s-- so implicit in this definition is the dependence on some model parameters okay so whenever you're within the PNP monad you can get these parameters and you can basically do arbitrary neural net operations on them if you want and the way that you do that is you just do this kind of funny computation graph thing so I could put this in a for yield but our neural net thing wants the computation graph to be an implicit parameter and this is the best way to get that to work in Scala but basically the computation graph is a container for the parameters and then some other neural network stuff which we'll see in a moment okay once I have this computation graph I can just call my thing that I did before this choose thing I'll give it the same list of outcomes and then here instead of hard-coding the probabilities I'm just gonna get those model parameters and put them in so this thing has a method which lets me look up the parameters by name and I just put them into the call I need to do one more thing which is these parameters are between minus infinity and infinity so to make it a probability distribution I just need to normalize them which I can do with this this guy so this just makes it a problem description okay so now I've defined my probability distribution in terms of my model parameters so now the last step is we want to train this distribution so let's make some data let's say I flipped three twins and they came up true true and false from this data set we need to make some examples that the training system you know expects and the way that we think about a training example in P and P is it's basically a combination of two things so there's this PNP example it's a combination of the distribution over all the things that could have happened which is just a distribution so you just give it a P P and then it's what actually happened so here we got true or false based on which data point this is I mean once I have these examples I can just train the system I'll show you what this training method does in a second it's basically just setting up various optimization parameters and just to show you that this works let's let's print out what happens here before training okay so before training you can see we got some sort of arbitrary probabilities here this is because when we put the parameters in the model they're initialized to some random numbers okay so we just get random numbers out here after training you can see that we get sort of the two-thirds true one-third false distribution which was actually exhibited in our dataset okay so this just shows you that training is working now there's two things I want to do at this point the first is you might look at this and say okay this is trivial I could just count the number of trues and falses and I could have got those probabilities and that is true in this example but that won't be true once we start building sort of more complicated models so we actually need some sort of explicit optimization process the second thing I wanted to do is I wanted to show you this training method just to show you that I'm not you know hiding a bunch of code from you basically this is just configuring how we want to do the optimization so like we set up sort of an objective function which just measures the distance between the distribution and the label and then we to set up like how we want to do it so we want to use stochastic gradient descent as the optimizer and you know there's things like numbers of cores and stuff like that so it's just sort of configuration parameters that go in here it's not a complicated method okay so that's the end of the training part of the talk basically here I've shown you how we can train these probability distributions by defining them in terms of model parameters and then using some optimization algorithms in the next part of the talk I'm going to show you how we can sort of define more complex distributions that actually use neural networks instead of storage is having two parameters for you know true and false right and here here I'm actually gonna use some real data okay so if I just run this app so here I'm gonna use a sentiment analysis data set just to like you know show this on a real problem so this is a movie data set we're basically each training example is a sentence from a movie review and it's been annotated with a one to five sentiment score from very negative to very positive so these are just ten examples from the data set and there's about eleven thousand examples total okay and what we're gonna do in this part is we're basically on a train of system to take this sentence and predict the sentiment score okay so basically what we want to do is we want to fill in this predict sentiment function which I've conveniently written for us okay and basically this is even think about this as a classifier right I take a sentence and given that sentence I'm going to you know return a sentence specific distribution over sentiment labels right and note that the distribution that we return needs to depend on the sentence because sometimes it's is a positive sentiment some add negative sentiment and the way that we're gonna build this model is we're gonna use a sort of encoder classifier architecture so this is sort of a very traditional neural network for solving this kind of problem basically we're gonna have an encoder which takes the sentence and produces a vector okay and then that vector we can just treat like a feature vector for this sentence so we can just build a linear classifier on top of it and then we'll be able to train the whole system okay so how let's let's build this model so we need to get our computation graph again okay so the first thing I'm gonna do is I'm gonna run the encoder I've already written the encoder I'll show you what it does it's like 20 lines of codes just a little bit annoying to write in front of everyone and then once I've gotten my sentence vector I want to predict the label so what I'm gonna do is I'm just gonna call shoes and here my the distributions over the sentiment labels so the sentiment labels are plus a very negative negative neutral positive very positive right so the distribution of our sentiment labels and here I'm just going to build a little linear classifier so I have this sentence vector and I'm gonna multiply it by some parameter matrix so this will be basically labels by the dimensionality of the sentence vector okay so this is just a linear classifier on top of our sentence vector and I need to do the thing to make it a probable institution again and I'm gonna refer my label okay and that's our sentiment classifier so I need to do one thing which is I have a model sitting around here and I just need to put these parameters into it so there's five sentiment labels and the census vector is 100 dimensional okay so once I put my parameters in my model I can now train the system in exactly the same way that I trained my coin flip so I have some data sitting around and you make some examples so this is basically sentences paired with the label and I'm just gonna do the exact same thing I did before and I can frame this and I also wrote a little thing so we can interact with it instead of me hard coding everything so let's train this and this takes like maybe 15 seconds to train so while it trains let me just show you what the encoder does so this is the this is the code for the encoder for those of you who are familiar with neural networks this is a continuous bag-of-words encoder basically what it does is there's a vector for every word that could that it knows about and it just splits the sentence in the words it finds all the vectors for each word in the sentence and then just adds them up okay it's a fairly simple network there's just a little bit of bookkeeping you have to do to figure out you know what words I know about and if I see a word that I haven't seen before what should I do so there's just a little bit of bookkeeping up here that you have to do okay so the system has trained and we can now try typing in some stuff so like great movie with wonderful actors and you can see we get classification so it's very positive with high probability we can also try I don't know first movie of the century and you see we got a very negative score probably forty nine point six okay so this is sort of an example of how we can train these neural networks with this PNP system okay let's just get rid of these guys okay so that's the end of the sort of neural network portion of the talk and the last thing we have to do is we just have to assemble these three pieces to build the demo system now hopefully at this points you can kind of guess what I'm gonna do to build the system what I'm gonna do is I'm just gonna copy paste that expression code we saw before and I'm gonna feed in some neural networks to score each choice okay and that's it we're gonna end up with a fully trainable system okay so let's let's do that okay so again here I have a thing but I forgot what it was called okay okay so basically we want to fill in this method here right we want to be able to take a sentence and produce that distribution over operations and I will copy-paste this expression code so I've already I've already pasted all the oppor opt definitions and stuff into here so we don't have to do that again and oh yeah so the way that we're gonna fill in this method is we're good again gonna use an encoder kind of architecture but it's it's slightly more complicated because in the expression thing we'd have to make a sequence of decisions and so we're going to use a special neural network for that that's called an LS TM and the way to think about that is it's basically just a thing where you give it a vector and it'll give you a vector and a new state and then you can give that new state a new vector and it'll give you a new vector in a new state right so it's kind of like a stateful thing that you advance by providing vectors so what we're gonna do is we're basically going to take this LS TM we're gonna use its first vector to score our decision over operations then we're gonna give it a vector and then use the next vector to score the next operation etc so to do that all we have to do is basically thread the LCM through this function so I'm gonna call it a scanner because our data structure is called a scanner and you have a computation graph okay and here basically I just need to replace this choice over ops with I can get the vector from the scanner so think about this like the sentence vector except that gets advanced right and I'm just gonna build a linear classifier on top of it again okay so now I've scored my current decision and the next thing I need to do is I just need to advance this Alice TM by giving it an input vector for the next time right and the vector that I give it is just going to depend on the operation so we can do that by just doing scanner dot add inputs we'll make some parameters for this so let's say inputs so basically what's happening here is every operations gonna have its own vector and I'm just gonna look up that vector and put it into the osteon based on the choice that of me and then I just passed this guy down and I am I am done this is my full definition of that model oh well I have to glue it together with the encoder so we just need to fill in parts down here I made the encoder return an LCM scanner this time just make this faster and this is actually the model that I showed you in the beginning of the talk I only have two minutes so I won't train it but you can train in exactly the same way that you saw everything before okay so that's that's it for how we build this demo okay let me just that's basically the end of the talk let me just summarize what I have talked abouts so I've presented a Scala library for doing deep learning or structured prediction with deep learning deep neural networks and our library is called proble sic neural programs and it basically combines two interacting elements it combines this representation of a structured output space which is like a probability monad with the representation for neural networks and these two components can interact so the neural networks defined the probabilities of the output space and the output space defines the architecture of the neural network and I've shown you how we can use this for a variety of applications like defining simple probability distributions to the sort of natural language calculator example that we just saw um that's it I want to say if you have questions after the talk or something you want to reach me on Twitter I'm at J and Krish feel free to tweet at me also we are recruiting at Microsoft somatic machines if you thought this talk was interesting and you're interested in sort of natural language applications or whatever please do come talk to me we have a really excellent team of people and we are hiring aggressively so that's it thank you for your attention I will take any questions [Applause] yeah the the encoder an encoder in national my apartment that's not product is great deterministic vector so how is it in the PMP it's still a determinist of distribution yeah it is so rapper like does not have any side effects um yeah so the question is why does the encoder return a thing in a PNP because it's not a distribution and the reason it returns a thing in a paean peeve is because the PNP actually represents two things it represents the probability distribution and it also represents the dependence on the model parameters so the encoder depends on the model parameters even though it always returns the same thing so it's a mix of the expression tree and the problem yeah yeah [Applause]