Neural Networks are Decision Trees (w/ Alexander Mattick)
deep learning machine learning arxiv explained neural networks ai artificial intelligence paper
#neuralnetworks #machinelearning #ai 

Alexander Mattick joins me to discuss the paper "Neural Networks are Decision Trees", which has generated a lot of hype on social media. We ask the question: Has this paper solved one of the large mysteries of deep learning and opened the black-box neural networks up to interpretability?

OUTLINE:
0:00 - Introduction
2:20 - Aren't Neural Networks non-linear?
5:20 - What does it all mean?
8:00 - How large do these trees get?
11:50 - Decision Trees vs Neural Networks
17:15 - Is this paper new?
22:20 - Experimental results
27:30 - Can Trees and Networks work together?

Paper: https://arxiv.org/abs/2210.05189

Abstract:
In this manuscript, we show that any feedforward neural network having piece-wise linear activation functions can be represented as a decision tree. The representation is equivalence and not an approximation, thus keeping the accuracy of the neural network exactly as is. We believe that this work paves the way to tackle the black-box nature of neural networks. We share equivalent trees of some neural networks and show that besides providing interpretability, tree representation can also achieve some computational advantages. The analysis holds both for fully connected and convolutional networks, which may or may not also include skip connections and/or normalizations.

Author: Caglar Aytekin

Links:
Homepage: https://ykilcher.com
Merch: https://ykilcher.com/merch
YouTube: https://www.youtube.com/c/yannickilcher
Twitter: https://twitter.com/ykilcher
Discord: https://ykilcher.com/discord
LinkedIn: https://www.linkedin.com/in/ykilcher

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 everyone. Today we're talking about neural networks and decision trees. I have Alexander Madduck with me, who is, maybe you want to introduce yourself. Yeah, I'm currently a student at FAU in Germany. And most people know me probably through Yannick, through his Discord. I'm one of the people who manage the paper discussions every week and present more of the theoretical papers usually. So we came across this paper all across social media. I saw it at one point and I'm like, meh. And then I saw it all over LinkedIn being like, whoa, neural networks are no longer a black box. We now know what's going on. I saw it on Twitter. I saw it, essentially like it really got some push behind it. As I said, when I first saw it, it was like, meh, this has been known for a while. So what does this paper say in a general sense? And has it been known for a while or is there actually something in there? Okay. So basically what this paper does, it shows how you can basically take a neural network, which is a sequence of weights with non-linearities in between. And then you can kind of each, if you rewrite them by effectively pulling out the right slopes and merging them up into new weights. And that would give you effectively this kind of structure. It's important to say this is only for if the non-linearity is piecewise linear, for example, a ReLU non-linearity. Otherwise we have an approximation, but this is actually in the exact mapping that we're doing right here. So we just rewrite the neural network somehow and then we get out what? So we get out such a tree and effectively you can see these W hats here and these W hats, I think they're defined somewhere. Yeah, I think somewhere up here. Yeah, effectively just unroll the piecewise slopes always from the layer above. So effectively we go and we draw the different cases that happened through the previous layer. We draw them up into the subsequent weights and that gives us kind of this tree structure because we of course get this unfolding of kind of which path can we go into the neural network and then the next layer can kind of enhance that path and so on. I think it's still a bit unclear maybe to some people who are not super familiar with this. They might be under like the general notion is a neural network is a non-linear function, right? Therefore I wouldn't just be able to represent it with a single, even if the W and the W hat are different, right? I still at the bottom here I see you know X times W something which is a linear function. So why all of a sudden I have a neural network? Why do I arrive at a bunch of linear functions? This mostly has to do with the fact that neural networks intrinsically are just compositions of these piecewise linear functions. For example, there's been more recent work, I think here in the Spline Theory of Deep Learning. So more recent work, more recent than the paper we're looking at? No, recent in a sense of it was published after 2000. This paper from I think 2018 and there they make this very very explicit where effectively they show that you can unfold almost every network into what is called splines and you can think of splines as kind of regions which then in and of itself are affine linear. So it's a linear transform with some bias against it and these deep neural networks are just different regions all of which have their own slope and bias. If we imagine a neural network with ReLU non-linearities, if we imagine a point somewhere in the input, if we move that point like just a tiny bit, then we move it small enough so that none, it crosses none of these boundaries. ReLU is essentially like this so it has like a boundary here where the slope changes. But if we move just small enough that either the signal is in the slope so it changes a bit in the slope or it doesn't change at all because it's in the zero part. So if we move just a bit, we don't change the ReLU activation pattern and that essentially means since all the functions are either linear or piecewise linear but we don't switch the piece, that means that within such a ReLU cell, it's essentially a linear function. I think that's what we see here at the end of the decision tree. The decision tree essentially says with this particular input, which of these ReLU cells am I in? And inside of that cell, it's actually a linear function. And that's what's described here. The neural network in total is non-linear because obviously we piece together super many of these tiny ReLU cell regions and that can make something that appears almost like smooth because if we zoom out, then it's like a video game where everything is made of triangles. But you zoom out and it kind of looks round, it kind of looks smooth. The paper shows you can rewrite the neural network and you get something like this. What does it mean? That's an entire different question because there are many different ways of viewing such a conversion. One is through a practical lens. Another one is from a lens of what does it help us to study decision trees? Another one is how does it help us to study neural networks? From a position of studying decision trees, it doesn't really help us that much because neural networks are inherently a lot more impenetrable than decision trees. Really studying a neural network and that helping us to figure out something about decision trees is rather hard. Additionally, we have the problem that decision trees fundamental, so the decision tree learning algorithms we built, they themselves don't map to neural networks perfectly. What I mean by that is you can take a decision tree like this thing here and transform it into a neural network. However, during the decision tree training process, what you usually do is you take one of those effectively edges and then you split it up into two lower ones. For that, you may need a new neural network because the capacity of the original one does not work out anymore. From a perspective of taking a neural network and then helping to figure stuff out for decision trees, it is pretty hard. On the other hand, we can use these decision trees to find and figure out stuff about neural networks. This is a lot more promising, but there is often the case that to do the kind of analysis you can do with the decision trees, you don't necessarily have to explicitly build this tree like the Spline Theory of Deep Learning paper, which does lots and lots of analysis. For example, there was a recent paper which specifically looks at what Batch Norm actually does through this lens. They don't need to build the explicit decision tree because they are just interested in this piecewise linearity. They are not necessarily interested in how exactly this fits to the actual neural network part or the actual tree part. Last but not least, we can also analyze it through the view of, let's take an existing neural network like a ResNet and try and make it more interpretable. That's where I also saw a lot of the hype going on. Because decision trees are more interpretable, you could obviously go and take a ResNet, transform it into a decision tree, and have this great interpretability. But in practice, this doesn't really line up that well. The reason is, again, kind of connected to this idea of decision trees being small and then progressively growing, where neural networks are large and just basically large enough to fit everything inside of them. That means that the actual size of these neural network trees can become rather gigantic. The way we can do analysis with a theoretical lens is by studying something called the VC dimension or the Wapnik-Schevonenkin dimension, which effectively just tells us how many different points can a network distinguish, which of course for a decision tree, if you have a fully balanced tree like this one, would be 2 to the power of the depth of the tree, while for a neural network, it's a lot harder to figure out because you have all of these different architectures. What you can do though is we can go in, we can bound this. There's been lots of work in trying to figure out bounds. For example, the best bound I could find is from this paper from 2017, which provides nearly tight bounds. Specifically, they provide this kind of theorem for a lower bound, meaning what they basically show is there's some universal constant which has this constraint, so effectively the square of it has to be less than the number of weights. You get a minimum amount of regions of resolution from a neural network of W, so the number of weights, times L, which is the depth of the network, times the logarithm of W over L, and then you have this C constant in here. That effectively means the number of regions we have scales a little bit more than linearly because we have this W in the log, and it stays a little bit less than linearly with the number of layers because we divide by L here. If we now take this absolute lower bound, what we can say is because we divide by C here, we can just set C square equal to the square root of W because that's the worst case scenario. It gives us the smallest bound. We can try to run this. I have here this very trivial neural network which has one hidden layer. We go from 1 to 1, so like this. Or we can also look at something like 1024 to look at something that would happen, for example in a transformer where you have these individual layers. If we run this, we get for this relatively small network, we get a depth of this full decision tree of about 16. If you would try to plot this, this is not going to run for a very very long time. 16 doesn't seem that much, but this is essentially an exponent. This is an exponent, so it is a giant number. We have 2 to the power 16. Again, I'm taking here the depth down. 2 to the power 16 different regions which is going to crush most algorithms. Even if you could build such a decision tree, so actually build one, it becomes rather hard to reason about them. Simply because the reason neural networks are hard to interpret is not necessarily because each individual component is hard to interpret. It's because the emergent properties of putting all of these things together and these billions of parameters or millions of parameters even together, that makes the problem hard. Yes, and I was just to say that this 16 depth tree, that's kind of the best case scenario. That's our bound on what would be possible in order for transferring a neural network to... What's the minimum size of tree we need to even represent that? It could be the case that it's more. But that was my impression as well is when I look at a decision tree, I have sort of one path to go down to make the decisions by. But if I look at a classification problem, it's not always one path. It's not just, is the picture bright or dark? Well, if it's dark, is it this and this? At some point, you get the same question. Is the picture bright or dark? Yes. Is there a small or a large object in it? Let's say. This question, you might want to ask whether it's light or dark. You have a matrix, right? Light picture, big object, light picture, small object, dark picture, and so on. But these are represented by two different nodes in a decision tree. No matter how you structure it, you have to ask one question first and the other question later. That means one of these questions is necessarily going to be represented by two different nodes in the decision tree. That just for me, looking at the decision tree, I no longer notice, I no longer recognize or the algorithm doesn't anymore tell me that these two things are actually related in some way. So whereas in a neural network, I have internal representation, I have features or weights that look at particular features inside of these representations. One set of the neural network might look at the lighting condition. The other part of the neural network may look at the shape of something and they can work in parallel. In a decision tree, it's one after the other and therefore I'm no longer the analysis gets way harder because stuff in the decision tree happens everywhere. And it doesn't know algorithm can tell me by the way, these things represent the same feature. It kind of boils down to this fundamental tension between having parametric and nonparametric approaches. Because the people don't know the distinction here is effectively a neural network is a fixed skeleton with lots of blank spaces and the objective of fitting the function in the neural network is figuring out what should be put into its blank spaces. This is a parametric approach because we have lots of parameters. Decision trees are nonparametric approaches. So what you do is you effectively say we have this entire family of different trees which not only have parameters like this W but also you have effectively the architecture which gets optimized along the way. And if you have nonparametric approaches, this usually gives you way different classifiers because in a parametric approach, because we have stuff like gradients which make a lot of sense in parametric approaches, you can say something like I don't necessarily want an optimal split. I just want some split that effectively amounts to you go and you take this W and just move it around a little bit to go closer to a good split. But decision trees do it a lot differently because decision trees have to work with this gigantic family of functions. We now have to do optimal splits, at least to some optimality constraint because you just randomly kind of pull out decision trees and try to figure out is this the right decision tree? You're never going to be able to finish. This is also why decision trees tend to work well in stuff like tabular datasets because you have relatively few features which are very well defined and you can compute the statistics for them which help you to figure out what would be the perfect split for a specific feature and which feature should I split next. While for something like an image, think about it, you have an image which is 224 by 224 by three RGB channels. The statistics you can get even with a massive dataset are not that great, especially since you have to consider things like shifting around the image a little bit to basically make the statistics more robust. That means it's very hard to fit a decision tree because statistics are always bad. A neural network performs way better because it doesn't care about how well it splits, it just does some split and hopes for the best. This means that a neural network is by its nature going to be less optimal but it's also going to make some progress even if there are only very bad statistics where a decision tree always has some sense of optimality if you fit it with something like CART because you only do somewhat optimal splits. Of course, at the cost of you have to have some notion of what optimal means so you need those statistics. This algorithm is a decision tree. It's what one would call a simple function, like Mathematica speaks, so decision trees are effectively just nice representations of simple functions but it's not really a decision tree as it would be produced by a decision tree algorithm and that's the problem what makes them uninterpretable because they just grow without bounds, these neural network trees. So when we look at, let's get back to the paper at hand, by the way this is still running which I like, back to the paper at hand, is the proof sound, the proof that neural networks are decision trees, right? It is absolutely sound, it's not wrong, all good. Is it new or unknown? No. So there are multiple things to that. One is there are already papers in the past which did that. So for example, this paper I think is from 1999, yeah November 1999. They also showed like algorithm for extraction of decision trees from artificial neural networks. So this is known and it's also one of those things that often happens to plop out as a corollary. So there are very few people who go and explicitly write this proof down because it's kind of a natural thing that occurs. If you have some algorithm which splits the world up into kind of classification polygons or simplices or affine regions which for example this paper does, then getting this decision tree form is effectively just a corollary, it just plops out passively. So this paper here for example, the Spline Theory of Deep Learning paper could easily just say well yeah the decision of which spline we are in is made hierarchically in the form of a decision tree. So it would be a one sentence and that just plops out. The same would be true for many of these theoretical proofs where first of all very rarely do you actually need this decision tree kind of realized but oftentimes the proof behind it that for example abuses the fact that we have this ReLU max function which effectively tells us to go either to the left where you have the zero region or to the right where we have new values. That is often just there, you don't need to do any more to get the actual decision tree out. I also know this from because I used to work quite a bit in the field of adversarial examples and there I think it was made oftentimes quite explicit to some degree because obviously people as long as stuff is linear you could have some kind of bounds on how worse it can get but then as soon as it's non-linear it gets a bit more tricky and you've also shown me before like a paper on verification of neural networks which is exactly right sort of in this area where people are trying to say well how bad can it get and they use the fact that also there we have these essentially these cells of linearity. So one of the problems is also what this ReLUplex algorithm, the idea is that you can view this max operation effectively as splitting everything up into a simplex then you can make arguments about with something like an SMT solver you can try to make arguments okay what happens inside the simplex or basically what can happen inside the neural network and you can do that to guarantee some safety guarantees but even this algorithm gets crushed at scale and the scale as we've seen here I think it's still running yeah it explodes rather quickly so and they of course don't explicitly build this but yeah this idea of neural networks mapping well to decision trees kind of boils down to the fact that a feed-forward network is effectively just a gigantic graph you can just take every you can effectively compute the spanning tree of that graph and that gives you a decision tree at least in the case of a ReLU and that's basically also what this paper does we compute the spanning tree by computing these w hats these double your hats take the slope from a kick appropriate slope from the previous layer and come and build up the appropriate double your hats so maybe for people so the if you we can just go to these formulas with one of the a's because that's kind of the crucial part of the math right here is these a vectors and you have to like it still seems a bit like magic we have like the nonlinear composition of function and then all of a sudden booby-dee-booby-dee-boop we we have these a vectors and somehow now all is linear but one has to remember that so on the bottom here we have the nonlinearity that not essentially what I do is I take the signal that comes through the network at and I look at the signal at the nonlinearity and there I say well where is the signal such that the ReLU is active and where is the signal such that the ReLU is inactive and it just replaced that by a vector of ones and zeros or the slopes and zeros right but these these vectors are dependent on the signal and that's why the they're gonna look different if the input is different and that's why it's a linear function for a given input in a given very tiny circle right so that's I think that's the connection now the paper also has some experimental result and there is a small claim but there is a claim that the decision tree representation might be advantageous in a computational manner so they have a table one comparing the decision tree and the neural networks for the same function in terms of their computational complexity so it turns out the decision trees have more parameters which is which is odd for a nonparametric function but I guess they're not learned parameters yet the neural networks use more multiplications and additions than the decision tree what do we make of that well computation often is not the same as computation because you may have more multiplications or additions but they may be in a form which is just nicer for you to work with so for example if we look at the trees or like here or let's go back up to the this kind of prototypical tree where effectively we have these these multiplications with the with this x0 input what happens is that we do have fewer multiplications using that structure because effectively we abuse the fact that we don't have to compute the entire matrix we only have to compute the part which is actually going to be relevant for us later on that of course reduces the number of multiplications but on the other hand we now have this spreading out we have more decisions in here and less multiplications and depending how your how your hardware ends up it might be that is it paying for more computation and having less decisions is better that's why training a decision tree on a cpu makes more sense than training it on a gpu on the other hand there are also approaches which take decision trees and basically compile them into what's effectively binary matrix multiplication these algorithms tend to of course for inference in that case but these algorithms tend to be a lot faster simply because even though you do more addition and multiplication and stuff like that you end up having so much parallelism that this what is it a factor of four roughly is not that meaningful or it's closer to three well on the left it's eight but it's two versus sixteen well in any case but but that's that's the point right if if one were to actually implement the decision tree on like a gpu one would actually regain all of these multiplications and additions because it just makes more sense to put the binary vector there with a lot of zeros and then multiply all of these zeros instead of trying to mask out stuff and because the gpu can just parallelize so hard yeah it's mostly that gpus don't tend to do well with lots of decision making and lots of sparsity because just of the way they are designed they're designed to do large operations on a lot of data very basically monotonically they they just do a large matrix multiplication with very little decision making every single one of these thousands of career course effectively does exactly the same thing and that then gives you kind of this boost because of thousands of course doing very simple very repetitive actions and if you have more decision making a have more decision making there that just makes it slower I think I interviewed a near Shavit of neural magic and effectively they're they're doing something very similar where they say okay what we do is we take like a BERT or something like this we prune it very in a in a special way such that the rest is something we can infer on CPU really well which is essentially like very similar to this paper right here so the idea of sort of pruning it down and all of a sudden you may end up with something that sparse requires more if else but then is very much suited to a CPU if we think about maybe the last question for today if we think about okay this this this paper is is it's certainly correct and all but we think it has it has been known or it's it's I don't like the word trivial because nothing like I used to hate that as a student because to me nothing ever was super true and it's even if it's trivial it's good that it's written down explicitly somewhere right you can point to a place I hear but in a sense it is like something that a lot of people have just kind of done on the side because it is fairly like natural a natural outcome of working with these these systems but if we look at a bit beyond that and say is there a a way in which decision trees can kind of make a bit of a comeback in today's world of deep learning maybe not as a substitute but as an augmentation of neural networks can we like what kind of properties does a problem need to have such that a combination of something like decision tree algorithms like the century learning algorithms and neural networks are the best so decision trees really like to have these very very well-defined statistics because that helps them to do their splits effectively neural network scale with gradients so if you can't get gradients you have a hard time and they also scale with size simply because as we've seen here you just get more possible more representational power so it's just better you can effectively simulate a small decision tree inside a large enough neural network but just setting everything else zero around it the trick that makes decision trees work well is if you have these statistics so that's why decision trees work incredibly well on something like tabular data like you can also tabular like deep learning but that's probably like you're going to go you're going to do research you're going to do probably a PhD and outplops a project which may or may not be competitive on tabular data well in the other hand i can just use xj boost and get great results right now what you would want to do to get decision trees to work well is you would want to take these very very high dimension is very very information sparse for example images and transport it into like a lower dimensional space where you can then get the statistics so for example if we have a two-stage approach where you have main neural networks inferring different features of the same thing so you first try to classify whether or not it's a cat or a dog then you try to classify i don't know its size or whatever you put them all down then you can start doing a decision tree learning and the decision tree is probably going to be a lot more performant simply because you get this smaller size through the fact that the neural net that the decision tree is much more optimal in how it uses its splits in capacity it seems like the current wave of self-supervised learning might actually be a good candidate to build something like this on top because the self-supervised algorithm they tend they tend to sort of extract many different kinds of features whereas like if i pre-train a classifier on image net let's say the classifier is going to be attuned to very few features for the bunch of classes it needs to classify but just from what i can observe the self-supervised approaches they they just tend to kind of get this rich representation out of images and we see that if you know we look at at anything that uses a vq-gan encoder nowadays which is almost all of the ai art projects so they're they're so rich such a rich representation so this this could be especially maybe the quantized stuff could be like a very fertile ground to then put like decision trees random forests whatever on top of that yeah cool all right i think that's that's about the paper is kind of really short it's i guess four four or five pages if you if you if you you know it is it is very like i think it's very approachable so you know if you've never heard of any sort of equivalence like this or or any math in this area it's very helpful i think to actually look at it and just see how it's done um i give you a bit of an insight and yeah alexander thank you so much for being here it was a pleasure thank you for having me cool and everyone if you want to hear more rants of alexander and myself we have discussions on discord almost every saturday evening well in at least evening in europe right cool bye everyone bye
 Hello everyone. Today we're talking about neural networks and decision trees. I have
 Alexander Madduck with me, who is, maybe you want to introduce yourself.
 Yeah, I'm currently a student at FAU in Germany. And most people know me probably through Yannick,
 through his Discord. I'm one of the people who manage the paper discussions every week
 and present more of the theoretical papers usually.
 So we came across this paper all across social media. I saw it at one point and I'm like,
 meh. And then I saw it all over LinkedIn being like, whoa, neural networks are no longer
 a black box. We now know what's going on. I saw it on Twitter. I saw it, essentially
 like it really got some push behind it. As I said, when I first saw it, it was like,
 meh, this has been known for a while. So what does this paper say in a general sense? And
 has it been known for a while or is there actually something in there?
 Okay. So basically what this paper does, it shows how you can basically take a neural
 network, which is a sequence of weights with non-linearities in between. And then you can
 kind of each, if you rewrite them by effectively pulling out the right slopes and merging them
 up into new weights. And that would give you effectively this kind of structure.
 It's important to say this is only for if the non-linearity is piecewise linear, for
 example, a ReLU non-linearity. Otherwise we have an approximation, but this is actually
 in the exact mapping that we're doing right here. So we just rewrite the neural network
 somehow and then we get out what?
 So we get out such a tree and effectively you can see these W hats here and these W
 hats, I think they're defined somewhere. Yeah, I think somewhere up here. Yeah, effectively
 just unroll the piecewise slopes always from the layer above. So effectively we go and
 we draw the different cases that happened through the previous layer. We draw them up
 into the subsequent weights and that gives us kind of this tree structure because we
 of course get this unfolding of kind of which path can we go into the neural network and
 then the next layer can kind of enhance that path and so on.
 I think it's still a bit unclear maybe to some people who are not super familiar with
 this. They might be under like the general notion is a neural network is a non-linear
 function, right? Therefore I wouldn't just be able to represent it with a single, even
 if the W and the W hat are different, right? I still at the bottom here I see you know
 X times W something which is a linear function. So why all of a sudden I have a neural network?
 Why do I arrive at a bunch of linear functions?
 This mostly has to do with the fact that neural networks intrinsically are just compositions
 of these piecewise linear functions. For example, there's been more recent work, I think here
 in the Spline Theory of Deep Learning.
 So more recent work, more recent than the paper we're looking at?
 No, recent in a sense of it was published after 2000. This paper from I think 2018 and
 there they make this very very explicit where effectively they show that you can unfold
 almost every network into what is called splines and you can think of splines as kind of regions
 which then in and of itself are affine linear. So it's a linear transform with some bias
 against it and these deep neural networks are just different regions all of which have
 their own slope and bias.
 If we imagine a neural network with ReLU non-linearities, if we imagine a point somewhere in the input,
 if we move that point like just a tiny bit, then we move it small enough so that none,
 it crosses none of these boundaries. ReLU is essentially like this so it has like a boundary
 here where the slope changes. But if we move just small enough that either the signal is
 in the slope so it changes a bit in the slope or it doesn't change at all because it's in
 the zero part. So if we move just a bit, we don't change the ReLU activation pattern and
 that essentially means since all the functions are either linear or piecewise linear but
 we don't switch the piece, that means that within such a ReLU cell, it's essentially
 a linear function. I think that's what we see here at the end of the decision tree.
 The decision tree essentially says with this particular input, which of these ReLU cells
 am I in? And inside of that cell, it's actually a linear function. And that's what's described
 here. The neural network in total is non-linear because obviously we piece together super
 many of these tiny ReLU cell regions and that can make something that appears almost like
 smooth because if we zoom out, then it's like a video game where everything is made of triangles.
 But you zoom out and it kind of looks round, it kind of looks smooth. The paper shows you
 can rewrite the neural network and you get something like this. What does it mean?
 That's an entire different question because there are many different ways of viewing such
 a conversion. One is through a practical lens. Another one is from a lens of what does it
 help us to study decision trees? Another one is how does it help us to study neural networks?
 From a position of studying decision trees, it doesn't really help us that much because
 neural networks are inherently a lot more impenetrable than decision trees. Really studying
 a neural network and that helping us to figure out something about decision trees is rather
 hard. Additionally, we have the problem that decision trees fundamental, so the decision
 tree learning algorithms we built, they themselves don't map to neural networks perfectly. What
 I mean by that is you can take a decision tree like this thing here and transform it
 into a neural network. However, during the decision tree training process, what you usually
 do is you take one of those effectively edges and then you split it up into two lower ones.
 For that, you may need a new neural network because the capacity of the original one does
 not work out anymore. From a perspective of taking a neural network and then helping to
 figure stuff out for decision trees, it is pretty hard. On the other hand, we can use
 these decision trees to find and figure out stuff about neural networks. This is a lot
 more promising, but there is often the case that to do the kind of analysis you can do
 with the decision trees, you don't necessarily have to explicitly build this tree like the
 Spline Theory of Deep Learning paper, which does lots and lots of analysis. For example,
 there was a recent paper which specifically looks at what Batch Norm actually does through
 this lens. They don't need to build the explicit decision tree because they are just interested
 in this piecewise linearity. They are not necessarily interested in how exactly this
 fits to the actual neural network part or the actual tree part.
 Last but not least, we can also analyze it through the view of, let's take an existing
 neural network like a ResNet and try and make it more interpretable. That's where I also
 saw a lot of the hype going on. Because decision trees are more interpretable, you could obviously
 go and take a ResNet, transform it into a decision tree, and have this great interpretability.
 But in practice, this doesn't really line up that well. The reason is, again, kind of
 connected to this idea of decision trees being small and then progressively growing, where
 neural networks are large and just basically large enough to fit everything inside of them.
 That means that the actual size of these neural network trees can become rather gigantic.
 The way we can do analysis with a theoretical lens is by studying something called the VC
 dimension or the Wapnik-Schevonenkin dimension, which effectively just tells us how many different
 points can a network distinguish, which of course for a decision tree, if you have a
 fully balanced tree like this one, would be 2 to the power of the depth of the tree, while
 for a neural network, it's a lot harder to figure out because you have all of these different
 architectures. What you can do though is we can go in, we can bound this. There's been
 lots of work in trying to figure out bounds. For example, the best bound I could find is
 from this paper from 2017, which provides nearly tight bounds. Specifically, they provide
 this kind of theorem for a lower bound, meaning what they basically show is there's some
 universal constant which has this constraint, so effectively the square of it has to be
 less than the number of weights. You get a minimum amount of regions of resolution from
 a neural network of W, so the number of weights, times L, which is the depth of the network,
 times the logarithm of W over L, and then you have this C constant in here. That effectively
 means the number of regions we have scales a little bit more than linearly because we
 have this W in the log, and it stays a little bit less than linearly with the number of
 layers because we divide by L here. If we now take this absolute lower bound, what we
 can say is because we divide by C here, we can just set C square equal to the square
 root of W because that's the worst case scenario. It gives us the smallest bound. We can try
 to run this. I have here this very trivial neural network which has one hidden layer.
 We go from 1 to 1, so like this. Or we can also look at something like 1024 to look at
 something that would happen, for example in a transformer where you have these individual
 layers. If we run this, we get for this relatively small network, we get a depth of this full
 decision tree of about 16. If you would try to plot this, this is not going to run for
 a very very long time.
 16 doesn't seem that much, but this is essentially an exponent. This is an exponent, so it is
 a giant number.
 We have 2 to the power 16. Again, I'm taking here the depth down. 2 to the power 16 different
 regions which is going to crush most algorithms. Even if you could build such a decision tree,
 so actually build one, it becomes rather hard to reason about them. Simply because the reason
 neural networks are hard to interpret is not necessarily because each individual component
 is hard to interpret. It's because the emergent properties of putting all of these things
 together and these billions of parameters or millions of parameters even together, that
 makes the problem hard.
 Yes, and I was just to say that this 16 depth tree, that's kind of the best case scenario.
 That's our bound on what would be possible in order for transferring a neural network
 to... What's the minimum size of tree we need to even represent that? It could be the case
 that it's more. But that was my impression as well is when I look at a decision tree,
 I have sort of one path to go down to make the decisions by. But if I look at a classification
 problem, it's not always one path. It's not just, is the picture bright or dark? Well,
 if it's dark, is it this and this? At some point, you get the same question. Is the picture
 bright or dark? Yes. Is there a small or a large object in it? Let's say. This question,
 you might want to ask whether it's light or dark. You have a matrix, right? Light picture,
 big object, light picture, small object, dark picture, and so on. But these are represented
 by two different nodes in a decision tree. No matter how you structure it, you have to
 ask one question first and the other question later. That means one of these questions is
 necessarily going to be represented by two different nodes in the decision tree. That
 just for me, looking at the decision tree, I no longer notice, I no longer recognize
 or the algorithm doesn't anymore tell me that these two things are actually related in some
 way. So whereas in a neural network, I have internal representation, I have features or
 weights that look at particular features inside of these representations. One set of the neural
 network might look at the lighting condition. The other part of the neural network may look
 at the shape of something and they can work in parallel. In a decision tree, it's one
 after the other and therefore I'm no longer the analysis gets way harder because stuff
 in the decision tree happens everywhere. And it doesn't know algorithm can tell me by the
 way, these things represent the same feature. It kind of boils down to this fundamental
 tension between having parametric and nonparametric approaches. Because the people don't know
 the distinction here is effectively a neural network is a fixed skeleton with lots of blank
 spaces and the objective of fitting the function in the neural network is figuring out what
 should be put into its blank spaces. This is a parametric approach because we have lots
 of parameters. Decision trees are nonparametric approaches. So what you do is you effectively
 say we have this entire family of different trees which not only have parameters like
 this W but also you have effectively the architecture which gets optimized along the way. And if
 you have nonparametric approaches, this usually gives you way different classifiers because
 in a parametric approach, because we have stuff like gradients which make a lot of sense
 in parametric approaches, you can say something like I don't necessarily want an optimal split.
 I just want some split that effectively amounts to you go and you take this W and just move
 it around a little bit to go closer to a good split. But decision trees do it a lot differently
 because decision trees have to work with this gigantic family of functions. We now have
 to do optimal splits, at least to some optimality constraint because you just randomly kind
 of pull out decision trees and try to figure out is this the right decision tree? You're
 never going to be able to finish. This is also why decision trees tend to work well
 in stuff like tabular datasets because you have relatively few features which are very
 well defined and you can compute the statistics for them which help you to figure out what
 would be the perfect split for a specific feature and which feature should I split next.
 While for something like an image, think about it, you have an image which is 224 by 224
 by three RGB channels. The statistics you can get even with a massive dataset are not
 that great, especially since you have to consider things like shifting around the image a little
 bit to basically make the statistics more robust. That means it's very hard to fit a
 decision tree because statistics are always bad. A neural network performs way better
 because it doesn't care about how well it splits, it just does some split and hopes
 for the best. This means that a neural network is by its nature going to be less optimal
 but it's also going to make some progress even if there are only very bad statistics
 where a decision tree always has some sense of optimality if you fit it with something
 like CART because you only do somewhat optimal splits. Of course, at the cost of you have
 to have some notion of what optimal means so you need those statistics. This algorithm
 is a decision tree. It's what one would call a simple function, like Mathematica speaks,
 so decision trees are effectively just nice representations of simple functions but it's
 not really a decision tree as it would be produced by a decision tree algorithm and
 that's the problem what makes them uninterpretable because they just grow without bounds, these
 neural network trees.
 So when we look at, let's get back to the paper at hand, by the way this is still running
 which I like, back to the paper at hand, is the proof sound, the proof that neural networks
 are decision trees, right? It is absolutely sound, it's not wrong, all good. Is it new
 or unknown?
 No. So there are multiple things to that. One is there are already papers in the past
 which did that. So for example, this paper I think is from 1999, yeah November 1999.
 They also showed like algorithm for extraction of decision trees from artificial neural networks.
 So this is known and it's also one of those things that often happens to plop out as a
 corollary. So there are very few people who go and explicitly write this proof down because
 it's kind of a natural thing that occurs. If you have some algorithm which splits the
 world up into kind of classification polygons or simplices or affine regions which for example
 this paper does, then getting this decision tree form is effectively just a corollary,
 it just plops out passively. So this paper here for example, the Spline Theory of Deep
 Learning paper could easily just say well yeah the decision of which spline we are in
 is made hierarchically in the form of a decision tree. So it would be a one sentence and that
 just plops out. The same would be true for many of these theoretical proofs where first
 of all very rarely do you actually need this decision tree kind of realized but oftentimes
 the proof behind it that for example abuses the fact that we have this ReLU max function
 which effectively tells us to go either to the left where you have the zero region or
 to the right where we have new values. That is often just there, you don't need to do
 any more to get the actual decision tree out.
 I also know this from because I used to work quite a bit in the field of adversarial examples
 and there I think it was made oftentimes quite explicit to some degree because obviously
 people as long as stuff is linear you could have some kind of bounds on how worse it can
 get but then as soon as it's non-linear it gets a bit more tricky and you've also shown
 me before like a paper on verification of neural networks which is exactly right sort
 of in this area where people are trying to say well how bad can it get and they use the
 fact that also there we have these essentially these cells of linearity.
 So one of the problems is also what this ReLUplex algorithm, the idea is that you can view this
 max operation effectively as splitting everything up into a simplex then you can make arguments
 about with something like an SMT solver you can try to make arguments okay what happens
 inside the simplex or basically what can happen inside the neural network and you can do that
 to guarantee some safety guarantees but even this algorithm gets crushed at scale and the
 scale as we've seen here I think it's still running yeah it explodes rather quickly so
 and they of course don't explicitly build this but yeah this idea of neural networks
 mapping well to decision trees kind of boils down to the fact that a feed-forward network
 is effectively just a gigantic graph you can just take every you can effectively compute
 the spanning tree of that graph and that gives you a decision tree at least in the case of
 a ReLU and that's basically also what this paper does we compute the spanning tree by
 computing these w hats these double your hats take the slope from a kick appropriate slope
 from the previous layer and come and build up the appropriate double your hats so maybe
 for people so the if you we can just go to these formulas with one of the a's because
 that's kind of the crucial part of the math right here is these a vectors and you have
 to like it still seems a bit like magic we have like the nonlinear composition of function
 and then all of a sudden booby-dee-booby-dee-boop we we have these a vectors and somehow now
 all is linear but one has to remember that so on the bottom here we have the nonlinearity
 that not essentially what I do is I take the signal that comes through the network at and
 I look at the signal at the nonlinearity and there I say well where is the signal such
 that the ReLU is active and where is the signal such that the ReLU is inactive and it just
 replaced that by a vector of ones and zeros or the slopes and zeros right but these these
 vectors are dependent on the signal and that's why the they're gonna look different if the
 input is different and that's why it's a linear function for a given input in a given very
 tiny circle right so that's I think that's the connection now the paper also has some
 experimental result and there is a small claim but there is a claim that the decision tree
 representation might be advantageous in a computational manner so they have a table
 one comparing the decision tree and the neural networks for the same function in terms of
 their computational complexity so it turns out the decision trees have more parameters
 which is which is odd for a nonparametric function but I guess they're not learned parameters
 yet the neural networks use more multiplications and additions than the decision tree what
 do we make of that
 well computation often is not the same as computation because you may have more multiplications
 or additions but they may be in a form which is just nicer for you to work with so for
 example if we look at the trees or like here or let's go back up to the this kind of prototypical
 tree where effectively we have these these multiplications with the with this x0 input
 what happens is that we do have fewer multiplications using that structure because effectively we
 abuse the fact that we don't have to compute the entire matrix we only have to compute
 the part which is actually going to be relevant for us later on that of course reduces the
 number of multiplications but on the other hand we now have this spreading out we have
 more decisions in here and less multiplications and depending how your how your hardware ends
 up it might be that is it paying for more computation and having less decisions is better
 that's why training a decision tree on a cpu makes more sense than training it on a gpu
 on the other hand there are also approaches which take decision trees and basically compile
 them into what's effectively binary matrix multiplication these algorithms tend to of
 course for inference in that case but these algorithms tend to be a lot faster simply
 because even though you do more addition and multiplication and stuff like that you end
 up having so much parallelism that this what is it a factor of four roughly is not that
 meaningful or it's closer to three well on the left it's eight but it's two versus sixteen
 well in any case but but that's that's the point right if if one were to actually implement
 the decision tree on like a gpu one would actually regain all of these multiplications
 and additions because it just makes more sense to put the binary vector there with a lot
 of zeros and then multiply all of these zeros instead of trying to mask out stuff and because
 the gpu can just parallelize so hard yeah it's mostly that gpus don't tend to do well
 with lots of decision making and lots of sparsity because just of the way they are designed they're
 designed to do large operations on a lot of data very basically monotonically they they
 just do a large matrix multiplication with very little decision making every single one
 of these thousands of career course effectively does exactly the same thing and that then
 gives you kind of this boost because of thousands of course doing very simple very repetitive
 actions and if you have more decision making a have more decision making there that just
 makes it slower I think I interviewed a near Shavit of neural magic and effectively they're
 they're doing something very similar where they say okay what we do is we take like a
 BERT or something like this we prune it very in a in a special way such that the rest is
 something we can infer on CPU really well which is essentially like very similar to
 this paper right here so the idea of sort of pruning it down and all of a sudden you
 may end up with something that sparse requires more if else but then is very much suited
 to a CPU if we think about maybe the last question for today if we think about okay
 this this this paper is is it's certainly correct and all but we think it has it has
 been known or it's it's I don't like the word trivial because nothing like I used to hate
 that as a student because to me nothing ever was super true and it's even if it's trivial
 it's good that it's written down explicitly somewhere right you can point to a place I
 hear but in a sense it is like something that a lot of people have just kind of done on
 the side because it is fairly like natural a natural outcome of working with these these
 systems but if we look at a bit beyond that and say is there a a way in which decision
 trees can kind of make a bit of a comeback in today's world of deep learning maybe not
 as a substitute but as an augmentation of neural networks can we like what kind of properties
 does a problem need to have such that a combination of something like decision tree algorithms
 like the century learning algorithms and neural networks are the best so decision trees really
 like to have these very very well-defined statistics because that helps them to do their
 splits effectively neural network scale with gradients so if you can't get gradients you
 have a hard time and they also scale with size simply because as we've seen here you
 just get more possible more representational power so it's just better you can effectively
 simulate a small decision tree inside a large enough neural network but just setting everything
 else zero around it the trick that makes decision trees work well is if you have these statistics
 so that's why decision trees work incredibly well on something like tabular data like you
 can also tabular like deep learning but that's probably like you're going to go you're going
 to do research you're going to do probably a PhD and outplops a project which may or
 may not be competitive on tabular data well in the other hand i can just use xj boost
 and get great results right now what you would want to do to get decision trees to work well
 is you would want to take these very very high dimension is very very information sparse
 for example images and transport it into like a lower dimensional space where you can then
 get the statistics so for example if we have a two-stage approach where you have main neural
 networks inferring different features of the same thing so you first try to classify whether
 or not it's a cat or a dog then you try to classify i don't know its size or whatever
 you put them all down then you can start doing a decision tree learning and the decision
 tree is probably going to be a lot more performant simply because you get this smaller size through
 the fact that the neural net that the decision tree is much more optimal in how it uses its
 splits in capacity it seems like the current wave of self-supervised learning might actually
 be a good candidate to build something like this on top because the self-supervised algorithm
 they tend they tend to sort of extract many different kinds of features whereas like if
 i pre-train a classifier on image net let's say the classifier is going to be attuned
 to very few features for the bunch of classes it needs to classify but just from what i
 can observe the self-supervised approaches they they just tend to kind of get this rich
 representation out of images and we see that if you know we look at at anything that uses
 a vq-gan encoder nowadays which is almost all of the ai art projects so they're they're
 so rich such a rich representation so this this could be especially maybe the quantized
 stuff could be like a very fertile ground to then put like decision trees random forests
 whatever on top of that yeah cool all right i think that's that's about the paper is kind
 of really short it's i guess four four or five pages if you if you if you you know it
 is it is very like i think it's very approachable so you know if you've never heard of any sort
 of equivalence like this or or any math in this area it's very helpful i think to actually
 look at it and just see how it's done um i give you a bit of an insight and yeah alexander
 thank you so much for being here it was a pleasure thank you for having me cool and
 everyone if you want to hear more rants of alexander and myself we have discussions on
 discord almost every saturday evening well in at least evening in europe right cool bye
 everyone bye