XGBoost results are not invariant under monotone predictor transformations?

Question

It is believed by many that tree-based methods are invariant under monotone transformations of the predictors. But recently I've read a paper (https://arxiv.org/pdf/1611.04561.pdf, referred to as the arxiv paper later) that says whether it's invariant depends on how the split threshold is chosen (there are three methods), and according to this paper, xgboost would be invariant under transformations because it uses the sweep left method. This is mentioned in the last paragraph on pp.2 and first paragraph on pp.3.

But when I read the original xgboost paper by Chen, the split algorithm looks much more sophisticated than any method mentioned in the arxiv paper, and it looks like it should be sensitive to transformations. I've tried xgboost on regression for a few data sets, and if I have column subsampling turned on, I do see different results with predictor transformations.

Can anyone give me some confirmation on this topic? I'm confused mostly by the arxiv paper.

Answer 1

A quick experiment suggests that xgboost makes its splits at midpoints between values of a feature in its training set:

https://github.com/bmreiniger/datascience.stackexchange/blob/master/74634.ipynb

---

The history turns out to be relatively complex, and possibly ongoing.

In this github issue there's an indication that the midpoint splits are only for small-cardinality discrete features. That code is gone in the current (at time of posting) version of the code. It was removed in pull 5251, commit 969ebbc, with further discussion pushed into issue 5096.

In the opposite direction, the function AddCutPoints didn't always exist, but the same discrete/continuous optimization shows up here, commit Jan 2017. So it seems that historically left-endpoints were used (at least for continuous data), supporting the arXiv paper, but that currently midpoints are used across the board.

The experiment above finishes with the Wisconsin Breast Cancer dataset, which has well over 16 values for the relevant features, and still has splits appearing at midpoints.

---

Finally, just a couple words about the monotonicity. First, as the arXiv paper mentions, this is entirely a question of how the model will apply to unseen data and a feature value that lands between values in the training data. Using left endpoints will always put such a value to the right side of the split, and so any monotonically increasing transformation won't affect that. A monotonically decreasing transformation will exactly reverse that. A linear(/affine) transformation will preserve the behavior when using midpoints (and also either left/right endpoints, depending on the sign of the transformation).