`python-m5p` - M5 Prime regression trees in python, compliant with scikit-learn

Speaker 1 [00:03]

Well, I'm very happy to be here, to see that this room is actually quite full, so I'm happy. Thanks, and I really thank the organizers because it really feels nice to be in presence after so many times remotely. So I'm Sylvain Marier, I work at Schneider Electric, and during my time there, I had the opportunity to apply AI on machine learning techniques to smart grids, building energy efficiency, asset monitoring, you know, manufacturing improvement, and many, many other tasks. So this is my two seconds ad here. We are hiring data scientists and data engineers. Please have a look online. okay so what about m5 and m5 prime so when you say what I was starting to write this talk actually I tried to remember when it all started and it was 10 years ago already so nothing very new but you know it's time to talk about it so at that time I was developing our first analytics as a service cloud platform, and it was not based on Python. It was based on an open source stack named RapidMiner, and actually it was embedding a few plug-ins, a bit like the framework that we saw just before. And among those plug-ins, the great Weka library, machine learning in Java, and M5P was quite a famous model there. And, you know I was coming from more traditional optimization based machine learning support vector machine or even neural network classic ones so it was a bit doubtful about decision trees but actually on some examples it was working quite nice so yeah we used it unfortunately when we migrated from our first analytics platform to the second one in Python nothing was there in in scikit-learn for this specific kind of model. We could find decision tree regressor, but not models where the leaf is a linear model. Let me backtrack a little bit then about what is actually M5 and M5P. So M5, it's from Quinlan in the 20th century. So the idea is really to, it was invented, it was a bit of a competition between him and Bremen about all the trees, and his idea was to grow a regression tree model like what was done in CART, same spirit, but trying to get more compact and more smooth models. So the idea is really to, it starts exactly the same. You have your data set and you divide by finding optimal splits where in the subparts your target variable will be more and more constant, less varying. So I start from the top node and I try to find an attribute that will reduce the variability of my target variable as much as possible. I find it, I split it and I do it again and again and again. This is the main idea of CART, and at the very end of the tree you put a constant value, that is the average of the samples reaching the node. So it starts exactly the same, but what changes is that afterwards you train a linear model for all of the nodes in the tree, even the intermediate ones, and you train it on the samples that reach that node. Also there was this kind of simplification where the linear models are simplified by greedily removing parameters if they are not useful. And finally, you prune the tree. That means that, for example, this LM3 node that is on the right, if its error is almost the same as the combined error of the two leaves it's the leaves are pruned away and we keep only the linear model and you go back track backwards this way so that you know you simplify the tree and of course since you know the leaves will always be the best performing in absolute there is this notion of penalty that you know two leaves containing two linear models or two constants have more parameters than a single linear model. So that's how the single one can win, and you can actually prune. So this is how the pruning is done. And finally, there is a last step in the M5 algorithm that is smoothing. Smoothing is using all the trees that are remaining, but in all the linear models that are remaining in the tree, is basically to prevent big gaps between the predictions that all the leaves are doing. And for this, Quinlan is proposing some kind of recursively weighted sum of the model with its parents across the whole chain. So this is how it looks, basically. you on some kind of nonlinear curve you can actually instead of having constant leaves such as in in in standard the regression tree we've got we've constantly you you can have linear models piecewise linear models to approximate the nonlinear curve you can note that you know in in some places is it's worse but it's much more simple in term of tree of model so that was the why Quinlan was saying that it would be useful because I think his sentence is that data scientists sometimes are more interested into insights gained from the model than from the predictive accuracy itself. And that's why he was proposing this. Now, based on this M5 original, M5 Prime was a second paper written by Wang and Witten. And the authors basically thought thought that The m5 was not very well documented at that time and there was no reference implementation So it was a bit hard for anyone to actually make it work So I proposed a few clarifications on you know, some tiny details. They proposed the reference implementation and two Improvements that make it easy to use in the in the real world data sets adoption of a specific strategy for categorical variables and tackling a specific method to handle missing values. And also there seems to be another improvement, it's very fun, if someone knows I would love to hear the answer. In this paper they talk about a very specific improvement that they made that is supposed to be very, you know, reducing the tree size a lot. But actually, it's not explained in the paper. It's just stated at the beginning and at the end. So I would love to see that. I think I found it in the code from Weka. There seems to be this kind of new pruning factor here that appears. And that is actually as an effect on the, if you increase it, it forces the tree to be pruned more. But it's actually not described in the paper. OK, so in terms of Python implementation, so M5Py, it was first written for an internal project a few years ago. And I opened a pull request at Scikit-Learn again a few years ago. However, it was difficult to get the bandwidth to reach the required quality of code and documentation. I know it because I could compare with other pull requests that did make it to the core. But still, I was puzzled because I could just stop working on it. But several community members were posting, saying, oh, I would like to try it. I would like to try it. And also, I think it's just for sharing the knowledge. If someone wants to educate people to teach a class about RegoGentry, might want to have a look and give an example. So anyway, I ended up putting it online. I think it's now online on PyPI, so it's version 0.3.0, and you can find it at this page. I think if I click it, I will be able to show you view here. Yeah. So that's the yeah, it's so recent but it has no download scores. Basically I sorry, sorry, sorry. Thanks. Let me duplicate that. Yeah. Okay. So I just included really two examples. So, I think the interesting one here is the one that was originally in the Quinlan article. It's an artificial data set where you have random variables that are actually drawn from linear models with a condition. So, you have a variable that, you know, when it's above zero, you use linear model one, and under zero, you get the other linear model. and on top of this there is some noise and well when you run various kind of trees so the traditional scikit-learn decision tree regressor but also the m5 prime on with various settings on it you can actually see the scikit-learn tree which is very big and the unpruned m5p3 which is very big as well and the pruned and smoothed m5p3 which is really one split and two linear models as you would expect okay i think we are out of time so um i will um sorry I will jump above the caveats, and this is more for discussion. Yeah. So I did not implement all of it. can talk about it later it's it's here it's really for the community we can all then discuss and and see what we want to do and doing this you know this research about about how to create it I obviously found many more newer techniques that are really worth looking at and that you know you can try compare and they are already implemented so that's that's it for this presentation

Speaker 2 [12:45]

Two questions. So I will replace the first one to put a bit of context. So when you are in scikit-learn that you use, for instance, the trees, you have the mean decrease in impurity that you can use as a feature importance, and somehow you might use that to know what is there. How do you interpret, like, how can you just inspect the tree there and what does it mean? I mean, like, is it easy or not to interpret it because you have a linear leaf everywhere on there.

Speaker 1 [13:16]

Okay, so trying to decode what Quinlan is proposing is, oh, your question made my PC stop. I think it's, there are really two approaches to this impurity topic. either you think about impurity as the resulting one using the linear model and in that case it's not the M5 algorithm for sure, it's rather the one that is implemented in light GVM you would start from the top and you would create linear models corresponding to your split and look at the impurity as a change, as a variance of the prediction error of the linear models. Quinlan is not trying to do that, and I think it's quite costly, actually, in terms of performance to try to do that. So he's really assuming that, anyway, if you start from the bottom and look just at the impurity in terms of, you know, target variable noise, you will still be able to group neighbor nodes will still correspond to places of the space that are consistent with each other in terms of input and therefore that can be grouped consistently in a linear model so there is no relation between the impurity that was used to split and the one that is resulting at the end of the model

Speaker 2 [14:58]

And so the second question was, did you have any benchmark in terms of performance?

Speaker 1 [15:05]

So, I will refer to the paper. In the paper, there are two benchmarks, Quinlan and the other paper, so there are two papers related to M5 and M5 Prime. Both provide numbers, both use data sets that are open and public, so one of the open issues in the GitHub repository for M5Py is to reproduce the same numbers and hopefully get the same results. I'm not sure we will be able to do that, to get exactly the same numbers for many implementation differences, but at least it's a challenge to at least reproduce something that is similar.

Speaker 2 [15:54]

So I still have more. So in terms of computational performance, how do you, I mean, what you gain by having linear things? If you compare it to a back tree or to a random forest where you have an ensemble, I mean, how does it compare like here?

Speaker 1 [16:12]

I mean, it's obviously not something you want to compare, some ensemble method and non-ensemble method. So what you want to compare is linear model, a tree with linear model, so M5, with another model tree implementation, such as the one I was displaying at the end. I don't know where it's of. Or with traditional decision tree. So these can be compared, and then you can make ensemble models on all of them. So, actually, in the packages from Light GBM, I think there is a random version of the linear model tree. So this one, you could compare it with the traditional random forest. You don't want to compare an ensemble and non-ensemble method.

Speaker 2 [16:59]

Okay, and last questions are the M5 prime trees, linear splines, where you learn the notes.

Speaker 1 [17:07]

No, it's not splines of Well, I Think in the original Quinlan article he was referring to another method where Splines were used but no, it's it's it's really in a regression standard linear regression

Speaker 2 [17:30]

So thanks again