Алгоритмы AdaBoost (SAMME & R2). Принцип работы и реализация с нуля на Python

Следующим мощным алгоритмом машинного обучения является AdaBoost (adaptive boosting), в основе которого лежит концепция бустинга, когда слабые базовые модели последовательно объединяются в одну сильную, исправляя ошибки предшественников.

В AdaBoost в качестве базовой модели используется пень решений (могут использоваться другие модели) — дерево с небольшой глубиной, которому присваивается вектор весов размера N, каждое значение которого соответствует определённому значению y_train и изначально равно 1 / N, где N — количество образцов в обучающей выборке. Каждый следующий пень обучается с учётом весов, рассчитанных на основе ошибок предыдущего прогноза. Также для каждого обученного пня отдельно рассчитывается вес, используемый для оценки важности итоговых прогнозов.

Ноутбук с данными алгоритмами можно загрузить на Kaggle (eng) и GitHub (rus)

Принцип работы адаптивного бустинга для классификации

SAMME (Stagewise Additive Modeling using а Multiclass Exponential loss function) — версия AdaBoost для многоклассовой классификации. Если же базовые модели оценивают вероятности классов, то такая версия называется SAMME.R, где R (Real) — вещественный и, в целом, обладает более высокой точностью.

Алгоритм строится следующим образом:

каждому значению y_train присваивается одинаковый вес;
пень глубиной 1 обучается на X_train и вычисляется доля неверных прогнозов, на основе которой рассчитывается взвешенная частота ошибки;
на основе взвешенной частоты ошибки рассчитывается вес пня;
для неверных прогнозов обновляются (увеличиваются) и нормализуются веса с учётом веса пня;
следующий пень обучается на X_train с учётом обновлённых весов: строится новая выборка того же размера, в которой чаще будут встречаться неправильно классифицированные образцы (те, у которых больше веса);
шаги 2-5 повторяются для каждого пня;
каждый обученный пень делает прогноз 1 образца X_test;
далее для каждого предсказанного класса суммируются веса пней;
класс с максимальной суммой весов и будет конечным прогнозом;
данная процедура повторяется для всех образцов в тестовом наборе данных.

Формулы для расчётов

Взвешенная частота ошибок j-го пня:

$r_j = \sum\limits_{i=1}^{m} w_i (\hat{y_j}^{(i)} \neq {y}^{(i)})$

Вес пня:

$α_j = η \ log(\frac{1 - r_j}{r_j}) + log(K - 1)$

Установить вес пня как (после чего нормализовать):

$w^{(i)} \leftarrow w^{(i)} exp(α_j) \ (\hat{y_j}^{(i)} \neq {y}^{(i)})$

Итоговый прогноз:

$\hat{y}(x) = argmax \sum\limits_{j=1}^{N} α_j (\hat{y}_j(x) = k)$

j-й прогноз i-го образца: $\hat{y_j}^{(i)}$

скорость обучения:

число уникальных классов .

Принцип работы адаптивного бустинга для регрессии

В случае регрессии AdaBoost.R2 работает похожим образом за исключением некоторых особенностей: для оценки качества прогнозов пней используется абсолютная ошибка, а конечный прогноз выполняется с помощью взвешенной медианы, суть которой заключается в присвоении весов отсортированным элементам списка и выборе того, чья кумулятивная сумма больше половины от общей.

Алгоритм строится следующим образом:

каждому значению y_train присваивается одинаковый вес;
пень глубиной 3 обучается на X_train и вычисляется абсолютная ошибка для каждого спрогнозированного образца;
после рассчитываются скорректированные ошибки для образов и пня, а также коэффициент β на их основе;
на основе коэффициента β находится вес пня;
далее для всех образцов обновляются и нормализуются веса с учётом веса пня;
следующий пень обучается на X_train с учётом обновлённых весов: строится новая выборка того же размера, в которой чаще будут встречаться образцы с большими весами;
шаги 2-6 повторяются для каждого пня;
производится прогноз всех образцов X_test на каждом обученном пне;
производится поиск индекса медианного прогноза для каждого образца;
прогнозы из шага 8 на основе индексов медианного прогноза для каждого образца и будут конечными прогнозами.

Формулы для расчётов

Абсолютная ошибка для спрогнозированного образца:

$e_{abs} = |\hat{y_j}^{(i)} - {y}^{(i)}|$

Скорректированная ошибка для спрогнозированного образца:

$e_{l} = \frac{e_{abs}}{max(e_{abs})}$

Скорректированная ошибка для пня:

$\overline{e} = \sum\limits_{i=1}^{n} w^{(i)} e_l^{(i)}$

Коэффициент β:

$β = \frac{\overline{e}}{1 - \overline{e}}$

Вес пня:

$w^{(i)} = η \ ln(\frac{1}{β})$

Обновить вес пня по следующем правилу (а затем нормализовать):

$w^{(i)} \leftarrow w^{(i)} β_i^{1 - e_{l}}$

Итоговый прогноз:

$\hat{y}(x) = weighted \ median (\hat{y_j}^{(i)})$

j-й прогноз i-го образца: $\hat{y_j}^{(i)}$

Cкорость обучения: .

Импорт необходимых библиотек

import numpy as np import pandas as pd import matplotlib.pyplot as plt from sklearn.preprocessing import LabelEncoder from sklearn.model_selection import train_test_split from sklearn.metrics import accuracy_score, mean_absolute_percentage_error from sklearn.datasets import load_diabetes from sklearn.tree import DecisionTreeClassifier, DecisionTreeRegressor from sklearn.ensemble import AdaBoostClassifier, AdaBoostRegressor from mlxtend.plotting import plot_decision_regions

Реализация на Python с нуля

class AdaBoost:     def __init__(self, regression=False, n_estimators=50, learning_rate=1.0, random_state=0):         self.regression = regression         self.n_estimators = n_estimators         self.learning_rate = learning_rate         self.random_state = random_state         self.stumps = []         self.weights = []      def _update_weights(self, args):         if self.regression:             weights, beta, loss_function = args             weights *= beta ** (1 - loss_function)         else:             weights, wrong_predictions, stump_weight = args             weights[wrong_predictions] *= np.exp(stump_weight)          return weights      @staticmethod     def _normalize(weights: np.ndarray):         return weights / sum(weights)      def fit(self, X, y):         n_samples = len(y)         self.K = len(np.unique(y.values))   # num unique classes         weights = np.ones(n_samples) / n_samples          for _ in range(self.n_estimators):             if self.regression:                 stump = DecisionTreeRegressor(max_depth=3, random_state=self.random_state)                 stump_predictions = stump.fit(X, y, sample_weight=weights).predict(X)                  abs_instance_errors = abs(stump_predictions - y)                 adjusted_instance_errors = abs_instance_errors / max(abs_instance_errors)                 adjusted_stump_error = sum(weights * adjusted_instance_errors)                  if adjusted_stump_error >= 0.5:                     self.stumps.pop(-1)                     break                  beta = adjusted_stump_error / (1 - adjusted_stump_error)                 stump_weight = self.learning_rate * np.log(1 / beta)                 args = [weights, beta, adjusted_instance_errors]             else:                 stump = DecisionTreeClassifier(max_depth=1, random_state=self.random_state)                 stump_predictions = stump.fit(X, y, sample_weight=weights).predict(X)                  wrong_predictions = stump_predictions != y                 r = sum(weights[wrong_predictions])   # weighted_error_rate                 stump_weight = self.learning_rate * np.log((1 - r) / r) + np.log(self.K - 1)                 args = [weights, wrong_predictions, stump_weight]              self.stumps.append(stump)             self.weights.append(stump_weight)             weights= self._update_weights(args)             weights = self._normalize(weights)      def _max_weighted_votes(self, samples):         n_samples = len(samples)         sample_indexes = np.array(range(n_samples))         prediction_weights = np.zeros((n_samples, self.K))          for i in range(self.n_estimators):             stump_prediction = self.stumps[i].predict(samples)             prediction_weights[sample_indexes, stump_prediction] += self.weights[i]          return np.argmax(prediction_weights, axis=1)      def _weighted_median_prediction(self, samples):         n_samples = len(samples)         sample_indexes = np.arange(n_samples)         predictions = np.array([stump.predict(samples) for stump in self.stumps]).T         sorted_pred_indexes = np.argsort(predictions, axis=1)          # Find index of median prediction for each sample         cumsum_weights = np.array(self.weights)[sorted_pred_indexes].cumsum(axis=1)         is_over_median = cumsum_weights >= 0.5 * sum(self.weights)   # True/False matrix         median_indexes = is_over_median.argmax(axis=1)         median_prediction_indexes = sorted_pred_indexes[sample_indexes, median_indexes]          return predictions[sample_indexes, median_prediction_indexes]      def predict(self, samples):         if self.regression:             return self._weighted_median_prediction(samples)         else:             return self._max_weighted_votes(samples)

Код для отрисовки графика

def decision_boundary_plot(X, y, X_train, y_train, clf, feature_indexes, title=None):     feature1_name, feature2_name = X.columns[feature_indexes]     X_feature_columns = X.values[:, feature_indexes]     X_train_feature_columns = X_train.values[:, feature_indexes]     clf.fit(X_train_feature_columns, y_train.values)      plot_decision_regions(X=X_feature_columns, y=y.values, clf=clf)     plt.xlabel(feature1_name)     plt.ylabel(feature2_name)     plt.title(title)

Загрузка датасетов

Для обучения моделей будет использован Glass Classification датасет, где необходимо верно определить тип стекла по его признакам. В случае регрессии используется Diabetes датасет из scikit-learn.

df_path = "/content/drive/MyDrive/glass.csv" glass_df = pd.read_csv(df_path) X1, y1 = glass_df.iloc[:, :-1], glass_df.iloc[:, -1] y1 = pd.Series(LabelEncoder().fit_transform(y1)) X1_train, X1_test, y1_train, y1_test = train_test_split(X1, y1, random_state=0) print(glass_df)             RI     Na    Mg    Al     Si     K    Ca    Ba   Fe  Type 0    1.52101  13.64  4.49  1.10  71.78  0.06  8.75  0.00  0.0     1 1    1.51761  13.89  3.60  1.36  72.73  0.48  7.83  0.00  0.0     1 2    1.51618  13.53  3.55  1.54  72.99  0.39  7.78  0.00  0.0     1 3    1.51766  13.21  3.69  1.29  72.61  0.57  8.22  0.00  0.0     1 4    1.51742  13.27  3.62  1.24  73.08  0.55  8.07  0.00  0.0     1 ..       ...    ...   ...   ...    ...   ...   ...   ...  ...   ... 209  1.51623  14.14  0.00  2.88  72.61  0.08  9.18  1.06  0.0     7 210  1.51685  14.92  0.00  1.99  73.06  0.00  8.40  1.59  0.0     7 211  1.52065  14.36  0.00  2.02  73.42  0.00  8.44  1.64  0.0     7 212  1.51651  14.38  0.00  1.94  73.61  0.00  8.48  1.57  0.0     7 213  1.51711  14.23  0.00  2.08  73.36  0.00  8.62  1.67  0.0     7

X2, y2 = load_diabetes(return_X_y=True, as_frame=True) X2_train, X2_test, y2_train, y2_test = train_test_split(X2, y2, random_state=0) print(X2, y2, sep='\n')             age       sex       bmi        bp        s1        s2        s3  \ 0    0.038076  0.050680  0.061696  0.021872 -0.044223 -0.034821 -0.043401    1   -0.001882 -0.044642 -0.051474 -0.026328 -0.008449 -0.019163  0.074412    2    0.085299  0.050680  0.044451 -0.005670 -0.045599 -0.034194 -0.032356    3   -0.089063 -0.044642 -0.011595 -0.036656  0.012191  0.024991 -0.036038    4    0.005383 -0.044642 -0.036385  0.021872  0.003935  0.015596  0.008142    ..        ...       ...       ...       ...       ...       ...       ...    437  0.041708  0.050680  0.019662  0.059744 -0.005697 -0.002566 -0.028674    438 -0.005515  0.050680 -0.015906 -0.067642  0.049341  0.079165 -0.028674    439  0.041708  0.050680 -0.015906  0.017293 -0.037344 -0.013840 -0.024993    440 -0.045472 -0.044642  0.039062  0.001215  0.016318  0.015283 -0.028674    441 -0.045472 -0.044642 -0.073030 -0.081413  0.083740  0.027809  0.173816                s4        s5        s6   0   -0.002592  0.019907 -0.017646   1   -0.039493 -0.068332 -0.092204   2   -0.002592  0.002861 -0.025930   3    0.034309  0.022688 -0.009362   4   -0.002592 -0.031988 -0.046641   ..        ...       ...       ...   437 -0.002592  0.031193  0.007207   438  0.034309 -0.018114  0.044485   439 -0.011080 -0.046883  0.015491   440  0.026560  0.044529 -0.025930   441 -0.039493 -0.004222  0.003064    [442 rows x 10 columns] 0      151.0 1       75.0 2      141.0 3      206.0 4      135.0        ...   437    178.0 438    104.0 439    132.0 440    220.0 441     57.0 Name: target, Length: 442, dtype: float64

Обучение моделей и оценка полученных результатов

В случае классификации низкая точность обусловлена тем, что AdaBoost плохо работает с несбалансированными данными, стараясь минимизировать ошибку на объектах из меньшего класса, что часто приводит к переобучению на этих объектах и к снижению точности модели в целом.

В случае регрессии ошибка меньше, чем в алгоритме случайного леса (чуть позже про него выйдет статья, в которой будут использоваться такие же данные) так как в используемых данных наблюдается относительно высокая степень корреляции между признаками, с которой AdaBoost справляется лучше. Следует отметить, что большинстве случаев, при хорошей подготовке данных AdaBoost будет справляться лучше своих предшественников как в задачах регрессии, так и классификации.

Данный пример хорошо показывает, что более сильные алгоритмы способны далеко не всегда показывать лучшие результаты «из коробки».

Полученные результаты приведены ниже.

Классификация

adaboost_clf = AdaBoost(random_state=0) adaboost_clf.fit(X1_train, y1_train) adaboost_clf_pred_res = adaboost_clf.predict(X1_test) adaboost_clf_accuracy = accuracy_score(adaboost_clf_pred_res, y1_test) print(f'adaboost_clf_accuracy: {adaboost_clf_accuracy}') print(adaboost_clf_pred_res, '', sep='\n')  sk_adaboost_clf = AdaBoostClassifier(random_state=0, algorithm='SAMME') sk_adaboost_clf.fit(X1_train, y1_train) sk_adaboost_clf_pred_res = sk_adaboost_clf.predict(X1_test) sk_adaboost_clf_accuracy = accuracy_score(sk_adaboost_clf_pred_res, y1_test) print(f'sk_adaboost_clf_accuracy: {sk_adaboost_clf_accuracy}') print(sk_adaboost_clf_pred_res)  feature_indexes = [1, 3] title1 = 'AdaBoostClassifier surface' decision_boundary_plot(X1, y1, X1_train, y1_train, sk_adaboost_clf, feature_indexes, title1)   adaboost_clf_accuracy: 0.46296296296296297 [5 0 0 3 1 0 0 0 0 0 1 0 1 1 0 5 0 0 0 0 1 0 5 5 1 0 5 0 0 0 0 4 0 1 0 0 0  0 0 5 1 4 0 0 0 0 0 0 0 0 0 1 5 0]  sk_adaboost_clf_accuracy: 0.46296296296296297 [5 0 0 3 1 0 0 0 0 0 1 0 1 1 0 5 0 0 0 0 1 0 5 5 1 0 5 0 0 0 0 4 0 1 0 0 0  0 0 5 1 4 0 0 0 0 0 0 0 0 0 1 5 0]

Регрессия

adaboost_reg = AdaBoost(regression=True, random_state=0) adaboost_reg.fit(X2_train, y2_train) adaboost_reg_pred_res = adaboost_reg.predict(X2_test) mape = mean_absolute_percentage_error(adaboost_reg_pred_res, y2_test) print(f'adaboost_mape {mape}') print(adaboost_reg_pred_res, '', sep='\n')  sk_adaboost_reg = AdaBoostRegressor(random_state=0, loss='linear') sk_adaboost_reg.fit(X2_train, y2_train) sk_adaboost_reg_pred_res = sk_adaboost_reg.predict(X2_test) sk_mape = mean_absolute_percentage_error(sk_adaboost_reg_pred_res, y2_test) print(f'sk_adaboost_mape {sk_mape}') print(sk_adaboost_reg_pred_res)   adaboost_mape 0.31162122370993556 [239.42353344 230.0610339  167.83786364 109.90928178 184.64646203  239.42353344 101.90476455 212.98494882 140.80423233 234.56903421  149.26846999 194.19445742 117.43386255 108.94790608 242.1290679  113.80597432 154.09826483  98.94335581 115.9061429  215.42377993  174.95712248 153.4188609  156.40651525 101.90476455 212.98494882  167.10327877 124.65270476 101.84145017 192.87682861 155.83747832  199.62919177 101.90476455 117.43386255 149.26846999 149.26846999  154.09826483 153.4188609  154.49247636 101.3830624  209.29518647  109.90928178 161.72545559 157.26677336 164.34687775 194.42677031  101.84145017 121.14501461 138.47917841 118.20881026 221.76239616  142.75885825 106.54153274 115.59244578 156.73838581 228.18233286  159.23529268 188.06281057 115.59244578 136.36747076 179.90046612  235.54909423 136.36747076 146.94594595 117.30376558 235.54909423  156.55259315 109.14947399 222.75       216.80587827 117.30376558  101.3830624  149.26846999 124.65270476 138.47917841 121.14501461  164.34687775 129.01990679 215.42377993 237.65169877 173.94597477  140.80423233 210.13587296 101.3830624  222.95089406 126.1623703  102.63869452 155.06486638 198.82203583 109.90928178 153.9068871  113.80597432 115.9061429  101.85242259 155.83747832 113.80597432  102.63869452 216.80587827 211.45665899 109.90928178 160.62212018  153.4188609  109.65526344 163.575      106.94547559 230.1457969  140.80423233 215.42377993 234.56903421 109.65526344 115.9061429  216.80587827]  sk_adaboost_mape 0.3108613573264116 [258.32911392 227.87142857 176.77325581 112.12676056 189.65263158  240.23529412  97.56934307 215.65217391 131.52777778 228.77894737  148.55223881 161.68085106 115.83916084 106.13636364 259.90697674  117.94565217 147.52941176  95.01538462 117.94565217 229.88429752  175.55696203 133.24277457 174.94444444 113.         213.70093458  169.35955056 133.24277457  95.67142857 195.7173913  156.20253165  206.96875    101.32330827 117.94565217 148.55223881 148.55223881  155.86893204 149.32352941 149.32352941  96.05932203 200.54545455  115.83916084 171.         143.02857143 169.8        196.54054054   99.05617978 123.4375     112.12676056 117.17213115 227.87142857  148.09195402  99.05617978 121.2826087  167.92592593 227.87142857  150.0106383  169.35955056 104.71794872 133.24277457 200.54545455  231.56934307 121.2826087  139.78205128 113.08602151 234.00735294  131.52777778 106.92380952 218.64705882 215.3        113.69172932   97.56934307 147.29166667 126.87591241 113.69172932 118.26470588  168.76       123.16037736 200.89473684 234.00735294 189.65263158  133.24277457 226.15686275  95.03703704 233.25       134.91428571  101.32330827 133.24277457 200.54545455 113.08602151 149.32352941  113.08602151 117.94565217  95.03703704 154.67532468 113.69172932   97.56934307 227.43037975 221.58433735 126.87591241 155.86893204  148.09195402 102.25714286 169.52147239 104.71794872 227.87142857  142.38461538 218.64705882 247.9122807  112.12676056 117.94565217  226.15686275]

Преимущества и недостатки AdaBoost

Преимущества:

высокая точность при правильной подготовке данных;
работа со сложными, нелинейными зависимостями в данных;
высокая обобщающая способность.

Недостатки:

низкая скорость обучения при работе с большими датасетами;
склонен к переобучению при большом числе базовых моделей;
нестабильность при работе с несбалансированными данными, а также чувствительность к шуму и выбросам.

Другие модификации адаптивного бустинга

Поскольку при работе с зашумленными данными обобщающая способность AdaBoost может заметно снизиться, были разработаны другие, более стабильные модификации. Среди наиболее интересных можно выделить следующие:

L2-Boost — модификация, которая использует L2-регуляризацию для функции потерь для штрафов менее важных признаков, что делает его более подходящим вариантом в задачах регрессии;
LogitBoost — улучшение, которое применяется в задачах классификации на основе логистической функции потерь, что ускоряет обучение и в ряде случаев делает алгоритм более устойчивым;
BrownBoost — более продвинутая модификация, в основе которой лежит использование лимита на обучение по данным с неверными прогнозами, то есть модель старается штрафовать сильнее трудно классифицируемые объекты.

Дополнительные источники

Статьи:

«Multi-class AdaBoost», Ji Zhu, Hui Zou, Saharon Rosset and Trevor Hastie;
«Boosting for Regression Transfer», David Pardoe and Peter Stone;
«L2 Boosting for Economic Applications», Ye Luo and Martin Spindler;
«Robust LogitBoost and Adaptive Base Class (ABC) LogitBoost», Ping Li;
«An adaptive version of the boost by majority algorithm», Yoav Freund.

Документация:

Видео: один, два, три.

? Бэггинг и случайный лес | Градиентный бустинг и его модификации ?

ссылка на оригинал статьи https://habr.com/ru/articles/800499/