Градиентный бустинг (AdaBoost)

Градиентный бустинг нужен для задач классификации и регрессии, похож на случайный лес. Это сложная тема, в том числе и из-за сложной интерпретации метода, то есть возможность понятным языком объяснить менеджеру банка, на основе каких правил было принято решение. В прошлых уроках про линейную регрессию было явно видно, у какого признака какой вес и нас сколько он влияет на результат. Градиентный бустинг нужен для регрессии, классификации, применим везде, где есть размеченные данные. Например, ранжирование ответов от нейросети в голосовых помощниках. Исключение — компьютерное зрение, НЛП, это лучше реализовать на нейронках. В практических задачах чаще берут легко интерпретируемые алгоритмы, например в финтехе. А в маркетинге уместны сложные алгориты, типа градиентного бустинга.

Мы рассмотрим частный случай градиентного бустинга под названием AdaBoost (adaptive boosting), совмещает сразу несколько разных моделей, и это далеко не только деревья, но в основном хороший результат получается на деревьях. Работает по принципу перевзвешивания результатов.

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

Алгоритм итеративный, но возможно распараллеливание. То есть у нас есть дерево 1, на его результатах строится дерево 2, на его результатах строится дерево 3, и так далее. На каждой итерации дается вес алгоритмам. Каждый новый алгоритм корректирует ошибки предыдущих до получения хорошего результата.

Давайте разберем подробнее основной принцип AdaBoost: подгонка слабых «учащихся» (т.е. модели, которые лишь немного лучше, чем случайные догадки) под многократно модифицированные версии данных. Следующим шагом прогнозы по всем из них объединяются с помощью голосования для получения окончательного прогноза. Модификации данных на каждой так называемой повышающей итерации состоят из применения N-весов к каждому из тренировочных образцов. Первоначально все эти веса устанавливаются на 1/N, так что на первом этапе просто тренируется слабый ученик на исходных данных. Для каждой последовательной итерации выборочные веса индивидуально модифицируются, и алгоритм обучения применяется еще раз к повторно взвешенным данным. На данном этапе те тренировочные данные, которые были неправильно спрогнозированы моделью с прошлого этапа, имеют увеличенные веса, в то время как веса, которые были спрогнозированы правильно, уменьшаются. По мере выполнения итераций все большее вливания приоритета идет на те участки, которые трудно предсказать.

from sklearn import model_selection
from sklearn.datasets import load_digits
plt.imshow(X[9].reshape(8,8))
 
X, y = load_digits(return_X_y=True)
from sklearn.preprocessing import MinMaxScaler
scaler = MinMaxScaler()
X = scaler.fit_transform(X)
X_train, X_test, y_train, y_test = model_selection.train_test_split(X, y, test_size=0.32)
def get_error(pred, y):
    return sum(pred != y) / len(y)

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

Возьмем метрику accuracy, это не лучшая метрика, она больше для сбалансированых классов, но вы можете поменять метрику на ту, которую сочтете нужной. sample_size это размер выборки, а classes_amount будет содержать классы. В моем примере начальные веса деревьев будут равны 1, все деревья имеют одинаковый вес и записаны в models.

from sklearn.tree import DecisionTreeClassifier
 
def adaboost(X, y, N):
    sample_size = len(X)
    classes_amount = len(np.unique((y)))
 
    w = np.ones(sample_size, dtype=np.float32)
    w = np.ones(sample_size) / sample_size
    models = []
 
    for n in range(N):
 
        clf = DecisionTreeClassifier(max_depth=2, splitter='best', criterion='gini').fit(X,y, sample_weight=w)
        print('Accuracy using the defualt gini impurity criterion...',clf.score(X, y))
 
        predictions = clf.predict(X)
        e = get_error(predictions, y)
        if e==0 or e>=  1 - 1 / classes_amount:
            break
 
        alpha = 0.5 * np.log((1 - e) / e) + np.log(classes_amount - 1) 
        match = predictions == y
 
        w[~match] *= np.exp(alpha)
 
        w /= w.sum()
        models.append((alpha, clf))
 
    return models

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

Обучим алгоритм на 500 деревьев. AdaBoost генерирует последовательность слабых классификаторов, где на каждой итерации алгоритм находит лучший классификатор, основываясь на текущих весах выборки. Правильная классификация получает меньший вес, неправильная — больший, и так до тех пор, пока не будет найдена оптимальная модель. Увеличение веса происходит за счет w[~match] *= np.exp(alpha). Мы просто «объединяем» нескольких слабых учащихся в одного сильного ученика. Слабый учащийся это обычно не дерево, а пенёк, в бустинге принято над деревьями использовать пеньки (глубиной ~3).

import numpy as np
N = 500
 
models = adaboost(X_train, y_train, N)
def predict(X, models):
    sample_size = len(X)
 
    y_pred = np.zeros((sample_size, 10))
 
    for alpha, clf in models:
        prediction = clf.predict(X)
        y_pred[range(sample_size), prediction] += alpha
 
    y_pred = np.argmax(y_pred, axis=1)
    return y_pred
 
print(f'Обучающая выборка, точность алгоритма: {(1 - get_error(predict(X_train, models), y_train)) * 100:.3f}')
print(f'Тестовая выборка, точность алгоритма: {(1 - get_error(predict(X_test, models), y_test)) * 100:.3f}')
Accuracy using the defualt gini impurity criterion... 0.26863226863226863
Accuracy using the defualt gini impurity criterion... 0.2334152334152334
Accuracy using the defualt gini impurity criterion... 0.28501228501228504
Accuracy using the defualt gini impurity criterion... 0.1294021294021294
Accuracy using the defualt gini impurity criterion... 0.24815724815724816
Accuracy using the defualt gini impurity criterion... 0.19737919737919737
Accuracy using the defualt gini impurity criterion... 0.1891891891891892
Обучающая выборка, точность алгоритма: 97.707
Тестовая выборка, точность алгоритма: 92.188 

И визуализируем:

import matplotlib.pyplot as plt
train_errors = []
test_errors = []
 
for n in range(1, 26):
    mods = adaboost(X_train, y_train, n)
    train_errors.append(get_error(predict(X_train, mods), y_train))
    test_errors.append(get_error(predict(X_test, mods), y_test))
 
x = list(range(1, 26))
 
plt.xlim(0, 25)
plt.plot(x, train_errors, color= 'r', linestyle=":", lw = 2, label='train errors')
plt.plot(x, test_errors, color= 'c', linestyle="--", lw = 2, label='test errors')
plt.title('Classifier')
plt.xlabel('N')
plt.ylabel('Accuracy')
plt.legend(loc='upper right')
Accuracy using the defualt gini impurity criterion… 0.20802620802620803
Accuracy using the defualt gini impurity criterion… 0.24897624897624898
Accuracy using the defualt gini impurity criterion… 0.3407043407043407
Accuracy using the defualt gini impurity criterion… 0.21703521703521703
Accuracy using the defualt gini impurity criterion… 0.23832923832923833
Accuracy using the defualt gini impurity criterion… 0.32186732186732187
Accuracy using the defualt gini impurity criterion… 0.27764127764127766
Accuracy using the defualt gini impurity criterion… 0.20147420147420148
Accuracy using the defualt gini impurity criterion… 0.2547092547092547
Accuracy using the defualt gini impurity criterion… 0.3284193284193284

На графике видно, что ошибок на тесте больше, чем на трейне. Но при достижении количества деревьев в районе 80 графики выходят на условное плато. Значит, меньше 80 деревьев нет смысла применять. На практике применяют и 1000, и 5000 деревьев, но на таких количествах обычно никакой разницы нет, ошибка становится минимальной.

Плюсы использования AdaBoost:

  • AdaBoost легко реализовать, достаточно класса моделей и их количества.
  • Он итеративно исправляет ошибки слабого классификатора и повышает точность путем объединения слабых учащихся.
  • Мы можем использовать многие базовые классификаторы с AdaBoost.
  • AdaBoost не склонен к переоснащению.

Из минусов можно отметить:

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

Если брать готову реализацию, то по табличным данным для серьезных проектов я бы брал современный градиентный бустинг (CatBoost, XGboost, LightGBM). Если не табличные, то это нейронные сети.

Где место adaBoost в жизни продуктового дизайнера? На реальных задачах часто нужно сказать бизнесу прогноз по retention. В этом случае процесс может быть такой: определить, по каким значениям мы считаем отток клиентов → бинарная классификация + пройденный нами градиентный бустинг → детализация фичами → a/b тест с группой клиентов, которые вроде как собираются уходить. Или более примитивные задачи, оценка стоимости авто по его характеристикам.