SHAP: Shapley Values in Machine Learning

Hey Katie. Hey Ben. Okay. It's been some time since we were talking about Shapley values. I don't have a pun for this one either because I'm really excited to talk about Shapley values of the interactions. So let's just, I'll just say first, you are listening to linear digressions. And now we can do a quick recap of the last episode. If you haven't listened to the last episode, I highly recommend going back and listening to it because it'll kind of lay the groundwork for this episode. But a quick recap. Last episode you were talking about how to take models that may be difficult to understand and take a prediction and try to figure out what components, what features were important in making the prediction that the model made. And this can be used to kind of understand what the model is doing or why the model is working or what the model is waiting. Yep, you got it. And Shapley values are kind of the way that we do that, where we take all of the different features that go into the model and we assign a weight to each one of these features to figure out and we're trying to figure out how impactful each of these features was in creating the prediction that we're, that we're trying to understand. And the way that we do that is we combine in order to get the weight of a particular feature, we combine that feature with all of the other features in all of the different combinations we possibly could do and we measure with and without that feature. And we take all of those differences. We average them all together and we are left with a Shapley value for that feature. So in other words, we're basically averaging the impact that that feature has in all of the different possible combinations of features. So not that feature when it performs the most in a particular combination, not that feature when it performs the worst but kind of the average of the range of values that that feature contributes to the particular prediction that we're looking at. Yeah, that's about right. And then a little bit of additional context is that Shapley values themselves are this established idea from Game Theory. The thing that's kind of interesting here is the idea of using them to help with interpreting a machine learning model. So that's an innovation that as far as I can tell has only happened in the last year or so. And it's kind of cool for some reasons that we talked about in the last episode but it has some of these nice theoretical properties where it can be, give you an answer that's intuitive in a number of different ways all at the same time. So that's really great. Now in this one we'll talk a little bit more about the specifics of like the pros and cons of Shapley values for machine learning and why this is starting to work a little bit better now than maybe it has in the past. I'm not sure if people have thought of this before or well, one of the things that we kind of mentioned last time just to get into it is that Shapley values can be kind of expensive to calculate. Right, because you need to do, you need to calculate them for every single combination of all of the other features. Yeah. So to take a specific example, if you want to do a little bit of, you know, big O notation on how expensive it might be to calculate the Shapley value for a complex model. Let's suppose that you have a gradient boosted tree model. So in that case, GBT's are kind of one of your standard best out of the box type algorithms. And what they are is basically a bunch of different decision trees that are built sequentially. So hopefully each one is, you know, better than the last in some way. But that means that each decision tree itself might be fairly complicated and then there's a whole bunch of them that you're using all at the same time and so that's extra complicated. And so if you want to do a Shapley value calculation in a GBT model, like you said, you kind of have to try out all these different combinations of the features with each other, adding them in in different orders. So you have to do that for potentially dozens or hundreds or even thousands of features in certain models. Yeah. And so the time complexity, if you want to do that calculation, if you do it the naive way where you're kind of chewing through all the different combinations methodically, is this going to be like the number of trees times the number of leaves per tree times two raised to the power of M where M is the number of features. And so the point here is that it's exponential in the number of features, how expensive this is. So if it's 2 to the M and M is 100, that's 2 to the 100 to do a Shapley value calculation. So that's, that's not great. Yeah. And 2 to the 101, if you have one more feature is twice that, you know. So. Yeah. It's not good. Yeah. So this is, this is computationally prohibitive. The, one of the innovations here though is an approximation algorithm for Shapley values. So basically what this approximation does is it looks at all of the different paths down the trees that a prediction could take because you're trying to explain an individual prediction. And then figures out, I'm not going to do a very good job of explaining this, but basically figures out all of the different subsets of features that follow those paths weighted by how many features fall into a given, or how many subsets of the features fall into a given leaves of the tree. So recursively keep track of what proportion of all the subsets of features flow down into each of the leaves of the tree. The point is that this introduces a little bit of extra memory complexity. You're keeping track of all the different subsets of features and where they're going. But it makes it a lot faster. So instead of being the number of trees times the leaves per tree times 2 to the m, it's now number of trees times number of leaves per tree times the depth of a tree squared. And that's typically the depth of a tree might be whatever 10 splits or 15 splits or something like that. Not thousands. Yes, this is not going to be nearly as expensive. And so that's one of the innovations here. Or one is just figuring out that Shapley values this idea from Game Theory can be cross-applied to machine learning where the idea is that you have to do this kind of credit sharing problem across all these different features to figure out which ones have a big impact on your prediction. And then number two, how do you make that computationally tractable? So both of those have now been kind of figured out. Interesting. So someone might have had this idea quite a while back, but you kind of need to solve both problems. To not only understand that this could apply to this problem, but also find a way to actually make it feasible. Yeah, I mean, I don't specifically know how long machine learning researchers have been doing on this, but yeah, I think you would need both of those at the same time. And the thing that's kind of nice about this is there's a number of other different ways to do feature importance that are on the market. So we talked a little bit last time about ways you can build simplified models that approximate a more complex model. And then there's also, if you're taking the example of something like a decision tree, for example, there's ways that you can use the structure of the decision tree itself to come up with different feature importance metrics. So a simple one might be something like split count. So how many times does a feature appear in a decision tree? Well, if it appears a lot, maybe that's a more important feature. If it doesn't appear that often, maybe it's a less important feature. Oh, interesting. So in this way, you're kind of looking into the model to see in some way what it's doing. Maybe not actually what it's ultimately doing, but you're kind of looking at the, I don't know, architecture. I don't know if that's the right word for this of the model to say, hey, we're using this value or this thing a lot. So maybe it's a little more important. Yeah, yeah. And there's a number of different ways you can do this. So another similar thing, but not exactly the same thing, is that maybe instead of counting up the number of times a feature is used, it's going to look at each one of those splits that you do on that feature and say, how much do we improve the purity of our predictions as a result of this split? So if we went from a 50, 50 mixture, then we split on some feature and then all of our reds are in one bucket and all of our blues are in the other, then maybe that was a very important feature that we just split on. And so it gets some credit in that scenario or maybe it's something like there's, you can do what's called a permutation test, which is where you take the feature and you scramble all of the values before you send it in through the decision tree and you see how much the predictions move around. So if the predictions don't change after you've scrambled the values, then that probably wasn't a very important feature, but if you kind of destroy that structure between the feature and the outcome and then your predictions fall apart, then maybe that was a really important feature. Anyway, the whole point is that there's a bunch of different ways that you can do this and the thing that's a little bit funny is that for a lot of them, you can come up with kind of pathological counter examples where they'll give you results that are pretty counter intuitive. And so that's why although there are some good feature importance methods out there on the market, Shapley values are, they're quite nice if you're a machine learning researcher. I'll just say one more thing about why they're nice and then we'll move on. Another thing that they're nice for is that in a lot of these feature, feature importance metrics that you get back say from your standard packages like scikit learn or whatever, they'll give you a number where maybe the higher the number, the more important the features, but very often those numbers don't have a sign. And so they won't say this is a feature that's pushing, pushing you more towards the zero case or pushing you more towards the one case. And it'll say this is important, but it won't tell you which way it's nudging it. And so sometimes when you're trying to do some of these model interpretations and understand from a trust level, how are these features playing into the model? Understanding which way they're nudging the model is actually pretty important and not that easy to get. But Shapley values give you that as well. So this seems like this method has a lot of promise. Is it a pretty easy thing to implement? I don't know how easy it is to implement. OK, one thing I should add, I'm embarrassed I got this long without saying this. So this is also based on a really nice paper by the same group of researchers who wrote the paper we covered last time. So the name of this one is called consistent individualized feature attribution for tree ensembles and we'll attach a link to this in linear digressions.com. But back to practical tips and tricks. One of the things I really like about this algorithm from the point of view of a practitioner is that there's actually a pretty nice package that's as far as I can tell has implementations in XG boost and maybe inside kit learn as well. So those are a couple of the big sort of decision tree machine learning packages that you might be using if you're working in Python. So what that means is that if you're a data scientist working in Python, you can use this package. It's called SHAP. Well, I'll attach a packet or a link to their to the GitHub page as well so you can actually see the implementation. But the point is that they've made it really easy to use. So if you're running XG boost or if you're running decision trees and psychic learn, you can get the Shapley values without a whole lot of extra drama and it has this fast implementation and all this nice stuff. But the second thing that I really like about this again from kind of a usability standpoint is that it comes with a lot of nice visualization tools as well. So the idea that you're using, you're using this method to try to understand the predictions and to understand like the impact that features have on predictions coming out of these models. But communicating that visually can be a little bit complex. So they put some thought into, let's imagine a case where you have a case that you're trying to explain and maybe some of the features are nudging your prediction in one direction. Other features are nudging it in the other direction. Each feature has a certain amount of importance that you could denote by say the size of an arrow. And so they have these nice plots that have kind of red arrows pointing to the right and blue arrows pointing to the left and they say, you know, here's kind of where you started. Here's where your features moved your prediction around to, here's where it ended up. And so then understanding kind of how that prediction came to be if that makes sense. Which I think is really cool, the idea that trying to make that as easy to surface as possible. And then the last thing, and then I will get off my, get off my soap box, is Shapley Value Predictions operate on an individual case basis. So each prediction, you'd say, like, what are the Shapley values for this prediction? Why did the model make this final decision? And so if you're trying to think about this on the level of, I have a whole data set that I need to understand. So maybe there's hundreds or thousands of predictions. Well, that's a little bit more complicated because then there's potentially lots and lots of these little diagrams that you want to look through. Right. Yeah, you're kind of taking that individual thing and you're giving it an additional dimension. Yeah. But here's what I think is really cool, is they have some of these diagrams and again there's, as I understand it, some code that makes these really easy to generate. Let's imagine that you have a thousand predictions that you're explaining with Shapley values. So there's a feature in the code where it can order all of those predictions by how similar their explanations are. So if you have two cases where it gave almost the same prediction, it'll like line them up. And then you line up, yeah, it's really, it's about to get cooler. So you order them by prediction similarity. And then you have your little diagram that's got your red arrows and your blue arrows. And so you, because you have thousands of these red arrows and blue arrows next to each other, what it basically does is it starts to make a distribution of the feature importance as well. And the thing that's really cool then is that when you have lots of cases that are giving the same answer for the same reasons, that's a way of doing basically supervised clustering, which is super cool because clustering is a thing you usually have to do with unsupervised methods, which is really a hassle. But with this one, you can start to find like substructure within your data set of here's different sets of predictions that are all hanging together because there's like a cluster of explanations here, which I think is just so cool. Man, we're a lot of levels deep now. I remember, I was at a conference last fall and one of the authors of this paper was there giving an explanation. This was the first I heard of it when I went to this conference and since then I've heard about it a lot more. And I remember struggling a little bit at the beginning because I didn't really understand what Shapley values were and kind of assumed that you knew them. And I was like, okay, there's this thing called the Shapley value. I should breed up on what that is, but I guess it's a number that tells you how important something is for some reason. Okay, got that. Now let me just hang on for the rest of this talk. And I kind of walked out of there and I was like, whoa, this is cool. So I've been looking forward to this episode for a while, I've been meaning to have a reason to do a deeper dive into this, finally got a chance to take a few hours and read up on it this weekend. Anyway, I think it's really cool. I was so happy you did because I am not in ML and wouldn't ever watch recordings of talks like that. And now I know what Shapley values are, why they're important and how you can almost use them on a meta level for a dataset rather than an individual prediction to like understand substructures in your data. That's crazy. That's really cool. It's really neat. So again, we'll attach a bunch of links to the GitHub repo, to the papers, to lineardiaggressions.com. I might even try to see if I can find a recording of this talk because I thought it was really helpful, if I can find one, I'll attach that on lineardiaggressions.com. But in the meantime, yeah, if you're a data scientist and interpretable models are important to you, I think this is a really cool thing to check out, hopefully you kind of understand it now. And go give it a whirl because it's about as easy as it could be to use from what I can tell. And it's just a really interesting and neat way of thinking about how to do feature importance and credit attribution in machine learning models. LinearDeggressions is a creative commons endeavor, which means you can share or use it any way you like. Just tell them we said hi. To find out more about this or any other episode of linearDeggressions, go to lineardeggressions.com. And if you like this podcast, go ahead and leave us a review on iTunes, so other people get to listen to this content too. You can always get in touch with either of us. Our emails are [email protected] and [email protected]. In case you have comments or suggestions for future shows, you can tweet us @LinDeggressions. Thank you for joining us and we'll see you next time.