Scikit's permuted features in decision tree implementation

Question

In the Scikit's docummentation of decision trees I found a note:

"The features are always randomly permuted at each split. Therefore, the best found split may vary, even with the same training data and max_features=n_features"

However, according to my knowledge decision trees make exhaustive search and look for the best split, according to given criterion, among all the features. Where do the permutations come from then and why are they there?

Answer 1

From the documentation:

The features are always randomly permuted at each split. Therefore, the best found split may vary, even with the same training data and max_features=n_features, if the improvement of the criterion is identical for several splits enumerated during the search of the best split. To obtain a deterministic behaviour during fitting, random_state has to be fixed.

This is saying that in the case that 2 or more features are tied for the best split, then which feature is chosen will depend on this random permutation.

The permutations are used to randomly sample which features to use. If your data has 10 features and you specify max_features=2, then the permutation is used to find the split from among the features. I surmise this works by permuting and then testing the quality of each feature until the termination criterion is met. The termination criterion will depend on the other model hyperparameters. Usually this will terminate because max_features has been exhausted (so if you find a valid split, it won’t test more than 2 in this example), but minimum information gain, minimum samples per leaf, etc. are also relevant here. Importantly, more than max_features will be considered if no valid partition is found among the sampled features.

OP writes:

However, according to my knowledge decision trees make exhaustive search and look for the best split, according to given criterion, among all the features. Where do the permutations come from then and why are they there?

This is not an accurate description of how the sklearn.tree.DecisionTreeClassifier class works. How many features to consider is governed by max_features.

max_features : int, float, string or None, optional (default=None) The number of features to consider when looking for the best split:

The number of features to consider when looking for the best split:

• If int, then consider max_features features at each split.

• If float, then max_features is a fraction and int(max_features * n_features) features are considered at each split.

• If “auto”, then max_features=sqrt(n_features).

• If “sqrt”, then max_features=sqrt(n_features).

• If “log2”, then max_features=log2(n_features). If None, then max_features=n_features.

Note: the search for a split does not stop until at least one valid partition of the node samples is found, even if it requires to effectively inspect more than max_features features.