Scikit-learn: MAE criterion using mean (rather than median)

Question

Scikit-learn's absolute_error criterion for decision trees and random forests (i.e., the MAE Criterion class: https://github.com/scikit-learn/scikit-learn/blob/main/sklearn/tree/_criterion.pyx) scales poorly compared to the default squared_error criterion.

See discussion here: https://github.com/scikit-learn/scikit-learn/issues/9626

I'm working with a dataset that is too large to reasonably be able to use MAE, however, I'd like to do a little experimentation with MAE, or at least an approximation of it if possible. Reading about how MAE works, I understand that it's based on using the median of individual leaves rather than the mean, which is what causes it to scale poorly compared to MSE.

Based on an incredibly shallow understanding of how the decision tree training process works, I would assume that I might be able to modify the MSE Criterion class to get an approximation to MAE. Specifically, if MSE uses squared error, I would think that somewhere in there, I could just apply square roots to existing calculations to get absolute error.

For example, something like the following in the MSE class (see the first link):

for k in range(self.n_outputs):
    impurity_left[0] -= (self.sum_left[k] / self.weighted_n_left) ** 2.0
    impurity_right[0] -= (self.sum_right[k] / self.weighted_n_right) ** 2.0

might become:

for k in range(self.n_outputs):
    impurity_left[0] -= ((self.sum_left[k] / self.weighted_n_left) ** 2.0)**0.5
    impurity_right[0] -= ((self.sum_right[k] / self.weighted_n_right) ** 2.0)**0.5

However, all of my experimentation is leading to individual tree estimators that don't fit beyond one leaf and therefore predict the same value for all samples.

I'm just wondering whether this approach actually makes sense and, if so, what I would need to modify to make it work.

user_16043632 · Answer

I think there are a few bits of confusion here. Firstly, with regard to scaling of MAE vs MSE, MSE can scale $O(n)$ whereas according to the Github issue you linked, MAE in scikit-learn scales $O(n^2)$, but MAE could be implemented to scale $O(n*log(n))$ (for details see the discussion about the PR which failed the unit tests in the link you provided). So if you want an efficient MAE, you may be able to implement one yourself and get that faster runtime.

With regard to your attempt/issues modifying mean squared error, I think you are a bit misguided. The error is squared to account for the fact that the calculated difference could be positive or negative, and error should be something monotonically increasing as you stray from 0 and a deviation of $x$ and $-x$ are equal. As a result, unfortunately you can not just "take the square root" - it will not work and can have unintuitive results.

As a side note, hopefully you will find this valuable (from the linked issue in your question):

PSA, users are encouraged to use HistGradientBoostingRegressor with loss='least_absolute_deviation' which will be considerably faster

Scikit-learn: MAE criterion using mean (rather than median)

1 Answers