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.
sklearn
uses Cython for its tree-building procedures; the actual boosting is all pure python, but the tree splitting logic gets compiled and static-typed. $\endgroup$Scikit-learn
choose: greedy search or just the first classifier with a margin of error less thangamma
. For the cross-posting, I am sorry, I deleted the other one. $\endgroup$