Scikit-learn's implementation of AdaBoost

Question

I am trying to implement the AdaBoost algorithm in pure Python (or using NumPy if necessary).

I loop over all weak classifiers (in this case, decision stumps), then overall features, and then over all possible values of the feature to see which one divides the dataset better. This is my code:

for _ in range(self.n_classifiers):
    classifier = BaseClassifier()
    min_error = np.inf

    # greedy search to find the best threshold and feature
    for feature_i in range(n_features):
        thresholds = np.unique(X[:, feature_i])

        for threshold in thresholds:
            # here we find the best stump
            error = sum(w[y != predictions])
            if error < min_error:
                min_error = error

The first two loops are not a problem since we usually have some tens of classifiers and features. But the third loop causes the code to be very inefficient.

One way to solve this is to ignore the best weak classifier and choose one with slightly better performance than a random classifier (as suggested in the Boosting: Foundations and Algorithms by Robert E. SchapireYoav Freund, p. 6):

for _ in range(self.n_classifiers):
    classifier = BaseClassifier()
    min_error = np.inf

    # greedy search to find the best threshold and feature
    for feature_i in range(n_features):
        thresholds = np.unique(X[:, feature_i])

        for threshold in thresholds:
            # here we find the best stump
            error = sum(w[y != predictions])
            if error < 0.5 - gamma:
                min_error = error
                break

But in this case, the accuracy of my model is lower than that of Scikit-learn, and the running time is still three times.

I tried to see how Scikit-learn implemented AdaBoost, but the code was not clear to me. I appreciate any comment.

Answer 1

The sklearn implementation of AdaBoost takes the base learner as an input parameter, with a decision tree as the default, so it cannot modify the tree-learning algorithm to short-circuit at a "good-enough" split; it will search all possible splits. It manages to be fast at that because the tree learning is done in Cython.

Another option for improved speed, if you want to stay in pure python: do histogram splitting, as pioneered by LightGBM and now incorporated into XGBoost and sklearn's HistGradientBoosting models.