Avi Bryant, Brushfire: Distributed Decision Tree LIbrary, SF Scala @Twitter 20150106

Recording: Avi Bryant, Brushfire: Distributed Decision Tree LIbrary, SF Scala @Twitter 20150106

some of your Bryant I used to work at Twitter on this stuff I know work on stripe work at stripe and and still try to use as much of this tech as i can because I'm used to it and so there's a talk about an application of scalding and especially of algebra we use it it's stripe for machine learning and in particular for training decision trees and so the the title of this talk is adding tree and tree but but a more descriptive title is probably this so brush fire is a distributed generic framework for distributed generic decision tree learning using scalding and algebra and it's open source you can find it on github and so you know Hadoop talks are classically about counting you know and the word count example is is sort of always used but as you as you heard from Oscar and Ian we like to think about adding really and and so this is this is sort of a talk about counting but it's really a talk about adding and in particular it's a talk about adding trees let's talk about adding decision trees so what's a decision tree so a decision tree is a particular kind of machine learning model where what you're trying to do is make some prediction right so the the basic interface for this and for a lot of different kinds of models is you have this this predict method right and you feed it some set of attributes some call it just map from strings that maybe your names of attributes names of features like size or color or whatever and and the associated values and you get back something right so to make this a little bit more concrete you might have a predictive model as to whether or not a particular Muppet likes cookies okay and so the features that they go into this prediction might be there I might be their color might be what they wear and and the output of the model is is an answer to the question of do you like cookies and so a very simple tree model that might answer this sort of as simple as possible tree model that that might answer this might look like this and I'm going to talk a little bit about how these models work when you evaluate them but just to sort of be clear this talk is principally about how you build these models right so evaluating them is then kind of the next step so you know does cookie monster like cookies right and so the way you evaluate this is you start at the root and and the root node sort of represents you know the entire space of possibilities here and then you ask a question you have some some predicate you know is the color associated with this instance blue and based on the answer to that for this particular instance this particular observation that you're feeding into this you go either to one child or the other right it's okay in cookies monsters case it is blue and so you go to that node and then you have some prediction that's associated with that node and that is the the result that you return so yes cookie monster does like cookies so so that's good but you know with your you you you might have a prediction you might have a leaf node or you might keep going right so these are trees the recursive structures and so you might go down the other path colors not blue and then you would get to another interior node where you would have another predicate right so does you wear stripes and so we're going to say here you know that that Burt does like cookies and you know that Oscar doesn't know relation to the Oscar who spoke earlier I guess and and so that's what the tree looks like and so I said you know when I showed this this this interface here I showed it returning a prediction as type T right and so what you want to think about conceptually with this tree is that you've got these T values sitting in the nodes that are the predictions and and you know the the job of building this tree is really twofold one is to kind of come up with the structure of the tree where what the predicate Tsar and in what order and so on and then the other is coming up with those predictions in the notes right so what type is that so you might think about different models different kinds of models having different types in those leaves so you might have what people call machine learning a binary classifier right which is do you like cookies yes or no okay and the type in that case that you really want to get back as a boolean you might have a regression where the type you get back is is the the answer you get back in some kind of numeric value right how many cookies will you eat so then you might have an inch or a double or something like that in the leaves you might also have a multi class classifier not a binary classifier right where there's a series of discrete values like what's your favorite kind of cookie and so the values and the leaves are going to be some kind of string right these are all different different kinds of things but the structure is the same and so when I talk about brushfire being a generic framework for for distributed decision trees right that's that's 11 a specter or part of what I mean by it being generic right it tries as much as possible not to make concrete decisions about this this is going to be a boolean this is going to be a string whatever but to use generic type parameters like this is just some prediction type T right and so most machine learning frameworks they're they're a huge there's this huge space of possibilities even just if you constrain to talking about decision trees of you know what what function are you going to use to evaluate it what is this a classification or a regression how are you validating it are you doing it with some kind of out of time validation or some kind of out of bag validation or K fold cross-validation or whatever do if you have trees how do they split do they have binary splits or multi-way splits do you have multiple trees in an ensemble and so and so and so on right and so brush fire oscar said this great thing about how you know we just like to write these beautiful abstract traits and like leave other people to implement them right brush fire is sort of applying the same philosophy to machine learning right I don't care someone else can go implement all of those right I just want to set up what the traits are what are the kind of abstract shins that that make up a decision tree learner right and and so let's let's talk let's keep talking about this prediction type T so I said that for binary classification you might think of it as having bullion's in the leaves is the predictions that's actually a very naive binary classification right usually you don't want a hard yes no answer usually you want maybe some kind of probability out right you want to know you know what are the chances this is true what are the chances this is false so you might think that maybe okay the right thing for a binary classifiers have a double with with probability the problem is or or let's say an additional constraint on this framework is that we want to be able to compute this in a distributed way and if you think about where those predictions are coming from where they're coming from is some input set of training data right we have a bunch of examples and we're going to look at what leaves those examples fall in and we're going to want to look at what what the the target values you know the do you like cookies or whatever are for all of the examples we have for some leaf and so what do we want to be able to do we want to be able to add up all of those examples that are at a leaf right and we want to be able to do this efficiently which means that we want the the values that are in our leaves to be something that we can compute and in this kind of distributed you know aggregation way that that Oscar nian we're talking about so from a type class point of view whatever our value t is there we want it to be a mono it right you want we want it to be something that we can sum up and so the problem with with using just a double in that case is that it doesn't it doesn't some the way we want it to right if we have a whole bunch of instances and they've all got like ones and zeros for whether or not they like cookies for the individual probabilities whether or not they're like cookies and you add those all up you don't get the probability right you what you need is some kind of average so you need some something better and so for binary classification what turns out to be or you know one type that is useful one very simple type that's useful is just a map that counts the truths in the falses right and so really what you get to is that you think of these lasses predictions and more as distributions really what we want in the leaves actually is a distribution that represents all of the examples that we have for that leaf and that has a bunch of nice properties it has the nice properties you can add them up it has the nice properties that you can combine them right so if I prune away these two leaves and I want to know what the the prediction should be for just this interior leaf then I can do that very simply right I just add the two distributions of the leaves and now I know what the distribution is for for the interior node you can also think about this if you want to think about this in kind of evasion way as I want the the predictions to be updateable right so we want to have a prior we want to be able to turn the crank and it with new information and come out with a new prediction right and so saying it's summable or saying it's updateable really kind of amounts to the same thing right and so the the other constraint that I put on this framework is is that or you know we talked about it being generic we're not to talked about it being distributed and so why is it important for this to be distributed apart from that it's like a fun intellectual problem and and if you already have this this constraint that it has to be generic then it's probably not going to be fast right so so usually the usual approach to building this kind of machine learning algorithm is you have some very well optimized code that's using you know ultimately fast like Fortran matrix multiplication or something under the covers and and runs one particular algorithm really really well and that's great you know if you're running this on some single CPU with a lot of memory which is kind of typically how you do this right but it runs like one algorithm and if you want this to be generic which i do then you're going to be slow which means you need to be able to throw a lot more computing power at it which means that needs to be distributed right it's also the case that in general if you have more training data you're going to get better models out and in particular you know people when you say that people tend to sort of immediately jump to okay you have a lot of observations a lot of examples to look at and it's true that that's useful but also it's really useful to be able to have a huge number of features that you're considering right so not just a lot of rows but a lot of columns and so that's an important design characteristic for this and and finally sort of you know it's like why do you rob banks that's where the money is right why do you want this to run on Hadoop that's where the data is and so a lot of people just you know a lot of organizations the interesting data to Train machine learning models on is already sitting in an HDFS cluster and so the kind of convenient pragmatic thing to do is to have your training algorithms be able to run on an HDFS cluster right so it's stripe you know we certainly don't have twitter scale of data we're dealing with transactional data rather than you know clickstream data we probably could and sometimes do you know get a big enough machine to run these algorithms you know on on a single node but it's just so much more convenient to just throw it at the cluster because that's where the data already lives right so so what does this look like in practice so here's an example of what it kind of looks like to train a tree in scalding so this this you know some of this should kind of look familiar from from earlier talks but basically you need some kind of training data which brushfire expects to be in this instance case class and we'll talk more about that in a moment and you need to feed that that sort of distributed collection of instance objects into a trainer and then you can ask the trainer to do things like expand and and what I mean by that is that what the trainer is doing is recursively building up this decision from starting at the root and then recursively adding a layer and it uses actually two MapReduce steps but only one full scan through the data for each new layer of the tree that our needs to add on so when you say expand repeatedly 10 like that what you're saying is like add and layers of depth to my tree and that's going to kick off this sequence of like you know 20 MapReduce steps right and one at the beginning to initialize the root and uh yeah so so you know again recursively right you know you have this tree it's got these predictions in the in the leaves but we want to make a bigger and so each we've splits and then we want to run it again in each we've split and so on right okay but we have a base case we need a base case we need to actually be able to create the route to begin with before we start expanding and conveniently that's that's a simpler thing to start talking about so how does this actually work what does this actually do okay so you have the training data you need to start with the training data where you have both the attributes you're going to use to make these predictions and the predictions themselves that you want to get out right and and so that's basically what what this instance case class is right you you need to have both your your map of values right your map from from future names to values and you need to have your target distribution and I still tend to think of these as distributions and they're still kind of you know structured as distributions even though this is kind of a degenerate case of a distribution right because this is like a distribution with exactly one element in it but it might be useful to weight them differently and so you might end up you know making use of that but but typically you end up with something like this where if for each instance going in you have say a map saying okay this one's true so I've got a map from true to one map from false to on and so on right hopefully that makes sense and and to create two first just initialize the root node all we actually want to do is just sum up all of those distributions and get the the you know the overall distribution for the entire data set right and that's our prediction for the root and if we if we never bothered splitting them we would just give exactly the same prediction out for for everything that came in right so near distributed context what does that look like so you know for each we've got our instances sort of split over a bunch of odes and so all in each of those nodes we're going to take each instance we're going to extract its distribution and then we're going to sum all of those distributions locally on the nodes right so we get those kind of local subtotals of tea and then we're going to send all of those subtotals to a central node in the reduced step that's then going to sum those up and get us our answer for what the what the root is right are there any questions by the way the people should feel free to like heckle or shout questions out midway through or whatever okay okay fine so that's that's nice but that all that gives us this boring route the exciting part of the interesting part at least the exciting part to me is then the question of what do you do when you want to split right so you know you have all of these possible ways you could split you have all of these features you might choose to split on you have all of these values of the features or ranges of values or whatever that you might choose and and you have to pick one and decision tree learning algorithms are greedy algorithms right they're always looking for every time they're splitting a leaf they're looking for the best possible split at that point right there not looking ahead but what I want to do is I have this kind of huge space of possible splits and I need to pick one um so so you know this is showing a putative splits from from a couple of different features from color and height let's let's restrict this just a little bit and talk about just the let's imagine that we only have one feature that we care about them we want to know what's the best value to split on for that one feature right okay so so we have this this table from this kind of you know slice of our of our training data which has this value and and again we have this distribution and and we want to know what to do so what we need to do to decide on how to split this feature is we need to build up not just the distribution of outcomes of say trues and falses but the joint distribution between the possible values for this feature and the possible outcomes right and here we're going to do just this this naive thing again of having you know maps of maps right we have a map of values and and then that's pointing to these these maps that represent the outcomes right and and we'll call that type that that joint distribution type s and again you know this is this is a generic type right this this this joint we don't we don't care at a framework level we don't care what the distribution type T is as long as it's something we can sum and again we don't care what the distribution type s is as long as it's something we can sum so I'm showing it with this sort of somewhat naive exact Joint Distribution of a map of map of counts right but this is where like count me and sketch that Ian talked about for example fits in really nicely right so if you have a huge key space rather than having an exact Joint Distribution you can use count and sketch to give you an approximate distribution of a discreet feature right or you can use some other approximation to get to get a distribution of a continuous feature let's say right okay so what does this look like so so we're going to do almost the same thing on the individual nodes that we did to get the root node right with but which is we're going to sum up these joint distributions instead of summing up just the just the distribution right so for any given value for any given feature i should say we're going to produce a joint distribution from the instance and then we're going to sum those up locally on each node and then we're going to send those in the reduced step to to another node and that's going to give us the total joint distribution for that feature right and then we need to have some way of producing a whole bunch of possible ways of splitting that feature from that joint distribution and so there's a splitter trait and again this is one of these nice abstract traits that like someone else can implement right and what splitter trait needs to be able to do it has this internal type s which is the type of the Joint Distribution that it knows how to work with it needs to be able to create one of those joint distributions given a value and Anna target right this actually looks a lot like the aggregator thing on the skirt was talking about it needs to have a semigroup so it needs to be able to combine these and then it needs to be able to split them right so given a joint distribution it needs to be able to produce a whole bunch of possible splits for us to consider and those splits need to be both a predicate right so they need to be a way of splitting and the distributions for each leaf that that this each new leaf that this split is producing so there's this split trait down at the bottom which is just you know some number of edges usually too but it doesn't have to be to some number of edges where you have a predicate for which item you know which instances filter into that and then you need to be able to pull out at least an approximation of the distribution that that will yield and so you know you might have for example a binary splitter here that works you know as long as you have a mono don t we can have a map from a value to t as as the Joint Distribution type and so on and that works as long as you have a relatively small number of possible values right and then you might do other things for other cases ok so what that does then what that splitter trait does is takes the joint distribution and and then expands it out into a whole bunch of splits right now you have this problem of I need to pick the best split and so how do you do that and so you bring in another trait which is this error trait which is actually gets used in a bunch of places but this is the first place that it gets used and so that again needs to be able to sort of have this pattern of needs to be able to produce this type the error type doesn't care what the arrow type is but it needs to be able to produce it and needs to be able to combine them and and the idea here is we have these these leaves and we have these leaves that have these individual distributions in them and we now need to be able to produce the error at each of those leaves and the error trait is set up so that it takes an actual distribution and takes a predicted distribution then comes out with the air and in this case when we're using it the actual and the predicted is the same right we only have the training set we're only evaluating based on on the data that we have right now and so the question really we're asking is if you were making a prediction from this distribution that you've got locally how good with that prediction be and and so that ends up looking really like often like you're computing the variance or something right because your prediction might be the mean and then your error is going to be the squared error on everything that you use to produce that mean and so you end up with the variance right so breyer score error is kind of like a variance for for binary classifiers and multi class classifiers and it's one of the implementations in there right and so your error term there ends up being this like mean squared error which is just an average okay so so you know now you have a split right now you can now you can expand this tree except that we only looked at one feature and we need to look at all of the features and the nice thing is this this can start happening sort of more and more in parallel so actually we're not just outputting one joint distribution at all of these nodes for each of these instances we're outputting a joint distribution for each feature and so in parallel each of those can also be producing these joint distributions and producing these subtotals of the joint distributions and then those subtotals of those joint distributions can be sent off to some different node in the reduced step which can then be looking at that joint distribution in producing all these candidates splits and those candidates splits can all be evaluated and the best one on that node can be picked and then we can bring all of the sort of best candidate splits together in one place and pick the very best one overall and then that becomes our split except there's a whole bunch of different leaves of the tree there's a question yeah the question is do you can do you allow a split to be across multiple features and the answer is no each individual split has to be on a particular feature and you get multi future interactions by like different levels in the tree right so you have a split on one feature and then in the next level you'd have split on the other feature if you wanted to do something with a combination of the feature you would create another feature that was like the exactly that just combined was the cross product of those two right so yeah so this is happening in parallel for all features but then of course this is also happening in parallel for every leaf of a tree and so each leaf of a tree we are individually considering and so you can but it's all still one pass through the data right because you can feed in the training data and the first thing that you do with the training data is figure out which leaf of the current tree you've got that training data would go to that instance would go to and then all of its information about the joint distributions gets associated with that leaf and summed independently with the other instances that are on that leaf right and so that's all happening in parallel but actually you're not usually building just one tree right so usually you're doing some kind of ensemble method like a random forest where you're building a very large numbers of tree very large number of trees and so you have this another step of parallelism where all of this is happening for every feature for every leaf for every tree and so you get a huge number of these things all being summed up right and so so how does that work so you have this other trait that comes in which is a sampler and the samplers job is to tell you for each instance that comes in for each tree that you are producing whether or not that instance should be considered when training that tree or in fact how many times should be considered because we're annum forest for example you do this bootstrap sampling where you actually might use a given instance 0 to n times in a given tree right and it's also the samplers job to tell you whether an instance maybe doesn't appear in the training set at all and should be used later for validation right because you want to train this stuff on one set of data and then you later want to evaluate it on our different set of data and so so that's the sampler trait so you have you know sampler trait for for just build a single tree with everything you have a sampler trait for let's do k fold cross-validation which will mean something to some people and well for others and that's fine you have a sampler trade for random forests and so on and I showed the full instance case class there I don't know it's a little bit small type maybe people can't see but the instance case class actually has a couple of extra things that I haven't talked about yet one is a unique ID and this is important just to be able to have a seed for for the sampler right you want to be able to consistently assign these things to different trees and so on and the other is a time stamp just because this comes up so often that you want to do some kind of out of time validation for example right everything before a certain time gets used for training everything after a certain time gets used for validation and so it's useful enough is just good to have it in there and to Oscars point about composing these things composed right so a lot of these things compose but samplers compose which is maybe not obvious so for example you can have an out-of-time sampler that wraps around a random forest sampler any other sampler and changes doesn't change most of the methods but changes this question of whether something goes into the training set or the validation set right so you can take any sampler you have and wrapping out of time sampler around it and and that'll work and so on right okay so a slightly more complete picture of what this looks like in scalding is this where actually when you're constructing the trainer you need the training data and you also need to give it the sampler which is critical for sort of everything you're doing and then implicitly it will start filling in the other stuff based on the types of your instances right so it will implicitly find a splitter for you it will implicitly find an error function for you and and you can override these of course but their defaults in there's normally you don't need to to think about this stuff too much but it is in there I don't remember why that slides in there and and so I one thing I've been glossing over through all this is I've been pretending that there's this one type v which is these feature values right but in reality you don't normally have a single type for all of your future values you've got some kind of you know heterogeneous thing right sometimes it's like all doubles but it's not usual and so how does that work and so you know the framework is in some sense kind of agnostic about that but in another sense it it has a way that that is easy to do which is that it provides this trait dispatched which is kind of like an either or something in Scala but has four cases instead of just one and so the idea here is you can have four types and each and it's kind of a union type right so each instance each value in your map is going to be one of these four types and the idea is that you have an ordinal type which is to say you know some kind of like int write something that is ordered but has a has a discrete number of values you have a nominal type like string which again is is is not ordered but has a sort of small discrete number of values and so for those you're going to use splitters that that do these exact representations and then you might have a continuous type like a double which is ordered but has an infinite number of values or a sparse type which is is not ordered but has an infinite number of values that's useful for like IP address or something right when you have these features they just have an incredible number of different values and usually for continuous and sparse you're going to use splitters that use these approximate data types right they use count men sketch or something like that so the idea is that you can set this up so that you pick or have the framework pick for you for different strategies for each of these and it'll it'll recognize the value coming in the type of the value coming in and take the right one to use right and so then actually your feature maps look kind of like this where you have these the future name and then it goes not directly to 3 or blue but to these wrapper types of whether this is ordinal or nominal or whatever and that's just for fun like this is a dispatch splitter which just wraps around for other splitters and does the dispatch and the code gets kind of crazy but it's written for you so you don't need to deal with it so the last thing that I wanted to talk about before getting the questions was I mentioned that the that one error trait gets used for a bunch of other stuff and it's worth talking about what other stuff the air trade gets used for so trainer has a bunch of other methods one is validate where you just want to know the error of your model and so there it's using the sampler not to pick out the training set but to pick out the validation set and there the fact that error has a semigroup associated with it is critical because what's going to happen is it's going to take each item you know in this distributed model it's going to take each item of your validation set and compute the error rights is going to throw your model let it find the prediction get the predicted T back then ask the error for for the error object given the actual value that you have on the instance and the predicted distribution you got back and then it's just going to sum up the errors for all of your validation set right that's why it needs to be a semigroup because you again want to be able to some of these up in this tribute away feature importance is kind of cool so the question is you know which which of these features that I fit in is actually useful and so what it's doing is going I'm not going to go through the full algorithm but basically walks through your your validation data and just permute sit a little bit so it'll take some some feature value and change it and and see what the error is for each it sort of groups the error by which feature was / muted right and so then you can you can rank the features by how much commuting that feature affected the error and and so this you can see has an ordering type class on future importance right and pruning which there isn't code in there right now for but there has been and will be again you can take an individual tree and again with the same error trait you can look at what is the error individually on two leaves or if I combine the distributions of those two leaves and get a parent distribution then I can look at what is the error for that parent distribution and if that's less than the leaves are useless and I should get rid of them right and so then this is less important if you've got like a random forest more important if you're working with a single tree that you want to be able to prune that right so so this error function becomes extremely useful and as people who have probably done a bunch of machine learning know it's like very nice to be able to define your own very customized error function for whatever the particular problem you're doing is right so you know I expect like in practice almost everyone who is using this is going to implement their own error trait and so it's nice that that air that that customary trait you've got can then be sort of fed through all these different parts of the system right okay just some links and questions planet was a paper out of Google that inspired the design of this pretty heavily where they talk about how how Google does decision tree learning on top of MapReduce scalding and alder bird obviously provide the foundation for this and and brush fire is the framework itself questions just like in your experience like how long does it take to train like a non-trivial like random for us yeah so um you know it's not fast right so the the models were training at stripe which are you know tend to be a few hundred million instances but like pretty big like a large number of features on each of those on a relatively small hood of cluster and we end up seeing like a few minutes for each level of the tree right and so if you want to train something like 20 deep or something like this then it ends up being a few hours if you're doing something you know really complement in uist features that slows it down more and so because the proximate algorithms take more time so yeah I mean certainly order hours not order seconds right I it would be very interesting by the way to see if spark could could improve that considerably right it's it's it's quite possible also like I haven't done a ton of work optimizing this right so I mean thanks for the great talk is this the first time when brush fire is actually publicly available long is also it's hard to say this is open source in brush fire this is called me don't brush fire was open source about a month ago or so so this may be the first public talk that acknowledges that it's open source guess speaking of spark I noticed after the any scholar or NW scholar conference that there's some interaction feed you and Eric gosh I'm about potentially getting a version of our start working on spark you know where that stands or that's something this I I don't believe anyone has done much work on this Eric was looking at it Vitaly Gordon was also looking at it I don't think either of them have done much more than kind of poke at it they i should say like the the dependency on algebra is very heavy here the dependency on scalding is very light it would be very easy for someone i mean it would not be a ton of work for someone to port this to spark or whatever else acha or something right and and I would encourage in love and be happy to help with that scoldings just what it was convenient for me to build this on but I did consciously try to make it you know make sure the abstractions as much as possible we're not tied to scalding awesome a scalding is of course cool well i'll be around for a few minutes of people