Как работает градиентный бустинг python numpy

Как работает градиентный бустинг python numpy

Шаг 59.
Введение в машинное обучение с использованием Python. . . Градиентный бустинг деревьев регрессии (машины градиентного бустинга)

На этом шаге мы рассмотрим градиентный бустинг .

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

Основная идея градиентного бустинга заключается в объединении множества простых моделей (в данном контексте известных под названием слабые ученики или weak learners ), деревьев небольшой глубины. Каждое дерево может дать хорошие прогнозы только для части данных и таким образом для итеративного улучшения качества добавляется все большее количество деревьев.

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

Помимо предварительной обрезки и числа деревьев в ансамбле, еще один важный параметр градиентного бустинга — это learning_rate , который контролирует, насколько сильно каждое дерево будет пытаться исправить ошибки предыдущих деревьев. Более высокая скорость обучения означает, что каждое дерево может внести более сильные корректировки и это позволяет получить более сложную модель. Добавление большего количества деревьев в ансамбль, осуществляемое за счет увеличения значения n_estimators , также увеличивает сложность модели, поскольку модель имеет больше шансов исправить ошибки на обучающем наборе.

Ниже приведен пример использования GradientBoostingClassifier на наборе данных Breast Cancer . По умолчанию используются 100 деревьев c максимальной глубиной 3 и скорости обучения 0.1:

[In 6]: from sklearn.ensemble import GradientBoostingClassifier X_train, X_test, y_train, y_test = train_test_split( cancer.data, cancer.target, random_state=0) gbrt = GradientBoostingClassifier(random_state=0) gbrt.fit(X_train, y_train) print("Правильность на обучающем наборе: ". format(gbrt.score(X_train, y_train))) print("Правильность на тестовом наборе: ". format(gbrt.score(X_test, y_test))) Правильность на обучающем наборе: 1.000 Правильность на тестовом наборе: 0.965

Поскольку правильность на обучающем наборе составляет 100%, мы, вероятно, столкнулись с переобучением. Для уменьшения переобучения мы можем либо применить более сильную предварительную обрезку, ограничив максимальную глубину, либо снизить скорость обучения:

[In 7]: gbrt = GradientBoostingClassifier(random_state=0, max_depth=1) gbrt.fit(X_train, y_train) print("Правильность на обучающем наборе: ". format(gbrt.score(X_train, y_train))) print("Правильность на тестовом наборе: ". format(gbrt.score(X_test, y_test))) Правильность на обучающем наборе: 0.991 Правильность на тестовом наборе: 0.972

[In 8]: gbrt = GradientBoostingClassifier(random_state=0, learning_rate=0.01) gbrt.fit(X_train, y_train) print("Правильность на обучающем наборе: ". format(gbrt.score(X_train, y_train))) print("Правильность на тестовом наборе: ". format(gbrt.score(X_test, y_test))) Правильность на обучающем наборе: 0.988 Правильность на тестовом наборе: 0.965

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

И вновь, как и в случае с остальными моделями на основе деревьев, мы можем визуализировать важности признаков, чтобы получить более глубокое представление о нашей модели (рисунок 1). Поскольку мы использовали 100 деревьев, вряд ли целесообразно проверять все деревья, даже если все они имеют глубину 1:

[In 9]: gbrt = GradientBoostingClassifier(random_state=0, max_depth=1) gbrt.fit(X_train, y_train) def plot_feature_importances_cancer(model): n_features = cancer.data.shape[1] plt.barh(range(n_features), model.feature_importances_, align='center') plt.yticks(np.arange(n_features), cancer.feature_names) plt.xlabel("Важность признака") plt.ylabel("Признак") plot_feature_importances_cancer(gbrt)

Архив блокнота со всеми вычислениями, выполненными на 57 и 59 шагах, можно взять здесь.

Рис.1. Важности признаков, вычисленные градиентным бустингом деревьев для набора данных Breast Cancer

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

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

Если вы хотите применить градиентный бустинг для решения крупномасштабной задачи, возможно стоит обратиться к пакету xgboost и его Python -интерфейсу, который на многих наборах данных работает быстрее (а иногда и проще настраивается), чем реализация градиентного бустинга в scikit-learn .

На следующем шаге мы рассмотрим преимущества, недостатки и параметры .

XGBoost

XGBoost [1] — одна из самых популярных и эффективных реализаций алгоритма градиентного бустинга на деревьях на 2019-й год.

История

XGBoost изначально стартовал как исследовательский проект Тяньцзи Чена (Tianqi Chen) как часть сообщества распределенного глубинного машинного обучения. Первоначально он начинался как терминальное приложение, которое можно было настроить с помощью файла конфигурации libsvm. После победы в Higgs Machine Learning Challenge, он стал хорошо известен в соревновательный кругах по машинному обеспечению. Вскоре после этого были созданы пакеты для Python и R, и теперь у него есть пакеты для многих других языков, таких как Julia, Scala, Java и т. д. Это принесло библиотеке больше разработчиков и сделало ее популярной среди сообщества Kaggle [2] , где она использовалось для большого количества соревнований. Программное обеспечение разработано по методологии SCRUM.

Она вскоре стала использоваться с несколькими другими пакетами, что облегчает ее использование в соответствующих сообществах. Теперь у нее есть интеграция с scikit-learn для пользователей Python, а также с пакетом caret для пользователей R. Она также может быть интегрирована в рамах потока данных, таких как Apache Spark [3] , Apache Hadoop [4] , и Apache Flink [5] с использованием абстрактных Rabit [6] и XGBoost4J [7] . Принцип работы XGBoost также был опубликован Тяньцзи Ченом (Tianqi Chen) и Карлосом Гастрин (Carlos Guestrin).

Описание алгоритма

В основе XGBoost лежит алгоритм градиентного бустинга деревьев решений. Градиентный бустинг — это техника машинного обучения для задач классификации и регрессии, которая строит модель предсказания в форме ансамбля слабых предсказывающих моделей, обычно деревьев решений. Обучение ансамбля проводится последовательно в отличие, например от бэггинга. На каждой итерации вычисляются отклонения предсказаний уже обученного ансамбля на обучающей выборке. Следующая модель, которая будет добавлена в ансамбль будет предсказывать эти отклонения. Таким образом, добавив предсказания нового дерева к предсказаниям обученного ансамбля мы можем уменьшить среднее отклонение модели, которое является таргетом оптимизационной задачи. Новые деревья добавляются в ансамбль до тех пор, пока ошибка уменьшается, либо пока не выполняется одно из правил «ранней остановки».

Рассмотрим иллюстрацию бустинга. На ней рассматривается поведение модели на одной точке абстрактной задачи линейной регрессии. Предположим, что первая модель ансамбля [math]F[/math] всегда выдает выборочное среднее предсказываемой величины [math]f_0[/math] . Такое предсказание довольно грубое, поэтому среднеквадратичное отклонение на выбранной нами точке будет довольно большим. Мы попробуем это исправить обучив модель [math]\Delta_1[/math] , которая будет «корректировать» предсказание предыдущего ансамбля [math]F_0[/math] . Таким образом мы получим ансамбль [math]F_1[/math] , предсказание которого будет суммироваться из предсказаний моделей [math]f_0[/math] и [math]\Delta_1[/math] . Продолжая такую последовательность мы приходим к ансамблю [math]F_4[/math] предсказание которого суммируется из предсказаний [math]f_0[/math] , [math]\Delta_1[/math] , [math]\Delta_2[/math] , [math]\Delta_3[/math] , [math]\Delta_4[/math] и предсказывает в точности значение заданного таргета.

Математика за алгоритмом

[math]\mathcal^ = \sum_^n l(y_i,\hat^+f_t(x_i))+\Omega(f_t)[/math] — функция для оптимизации градиентного бустинга, где:

[math]l[/math] — функция потерь, см. Общие понятия.

[math]y_i, \hat^[/math] — значение i-го элемента обучающей выборки и сумма предсказаний первых t деревьев соответственно.

[math]x_i[/math] — набор признаков i-го элемента обучающей выборки.

[math]f_t[/math] — функция (в нашем случае дерево), которую мы хотим обучить на шаге t. [math]f_t(x_i)[/math] — предсказание на i-ом элементе обучающей выборки.

[math]\Omega(f)[/math] — регуляризация функции [math]f[/math] . [math]\Omega(f) = \gamma T + \frac \lambda \lVert w \rVert ^2[/math] , где T — количество вершин в дереве, [math]w[/math] — значения в листьях, а [math]\gamma[/math] и [math]\lambda[/math] — параметры регуляризации.

Дальше с помощью разложения Тейлора до второго члена можем приблизить оптимизируемую функцию [math]\mathcal^[/math] следующим выражением:

[math]\mathcal^ = \sum_^n l(y_i,\hat^ + g_i f_t(x_i) + 0.5 h_i f_t^2(x_i)) + \Omega(f_t)[/math] , где

Поскольку мы хотим минимизировать ошибку модели на обучающей выборке, нам нужно найти минимум [math]\mathcal^[/math] для каждого t.

Минимум этого выражения относительно [math]f_t(x_i)[/math] находится в точке [math]f_t(x_i) = \frac[/math] .

Каждое отдельное дерево ансамбля [math]f_t(x_i)[/math] обучается стандартным алгоритмом. Для более полного описания см. Дерево решений и случайный лес.

Возможности XGBoost

Особенности модели

XGBoost поддерживает все возможности таких библиотек как scikit-learn с возможностью добавлять регуляризацию. Поддержаны три главные формы градиетного бустинга:

• Стандартный градиентный бустинг с возможностью изменения скорости обучения(learning rate).
• Стохастический градиентный бустинг [8] с возможностью семплирования по строкам и колонкам датасета.
• Регуляризованный градиентный бустинг [9] с L1 и L2 регуляризацией.

Системные функции

Библиотека предоставляет систему для использования в различных вычислительных средах:

• Параллелизация построения дерева с использованием всех ваших ядер процессора во время обучения.
• Распределенные вычисления для обучения очень крупных моделей с использованием кластера машин.
• Вычисления для очень больших наборов данных, которые не вписываются в память.
• Кэш Оптимизация структуры данных и алгоритма для наилучшего использования аппаратного обеспечения.

Особенности алгоритма

Реализация алгоритма была разработана для эффективности вычислительных ресурсов времени и памяти. Цель проекта заключалась в том, чтобы наилучшим образом использовать имеющиеся ресурсы для обучения модели. Некоторые ключевые функции реализации алгоритма включают:

• Различные стратегии обработки пропущенных данных.
• Блочная структура для поддержки распараллеливания обучения деревьев.
• Продолжение обучения для дообучения на новых данных.

Основные параметры

• n_estimators — число деревьев.
• eta — размер шага. Предотвращает переобучение.
• gamma — минимальное изменение значения loss функции для разделения листа на поддеревья.
• max_depth — максимальная глубина дерева.
• lambda/alpha — L2/L1 регуляризация.

Для более полного описания параметров модели см. документацию [10] .

Поддерживаемые интерфейсы

• Интерфейс командной строки (CLI).
• C++ (язык, на котором написана библиотека).
• Интерфейс Python, а также модель в Scikit-Learn.
• R интерфейс, а также модель в пакете карета.
• Julia.
• JVM языки, такие как Java, Scala, и платформы, такие как Hadoop.

Пример использования с помощью библиотеки xgboost

from sklearn import datasets iris = datasets.load_iris() X = iris.data y = iris.target 

Разделение датасета на обучающую/тестовую выборку.

from sklearn.cross_validation import train_test_split X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

Импорт XGBoost и создание необходимых объектов.

import xgboost as xgb dtrain = xgb.DMatrix(X_train, label=y_train) dtest = xgb.DMatrix(X_test, label=y_test)

Задание параметров модели.

param = < 'max_depth': 3, 'eta': 0.3, 'silent': 1, 'objective': 'multi:softprob', 'num_class': 3>num_round = 20

bst = xgb.train(param, dtrain, num_round) preds = bst.predict(dtest)

Определение качества модели на тестовой выборке.

import numpy as np from sklearn.metrics import precision_score best_preds = np.asarray([np.argmax(line) for line in preds]) print precision_score(y_test, best_preds, average='macro')

См. также

• Дерево решений и случайный лес
• Бустинг, AdaBoost

Примечания

Источники информации

• Tianqi Chen, Carlos Guestrin. XGBoost: A Scalable Tree Boosting System
• XGBoost Mathematics Explained
• Gradient Boosting and XGBoost
• A Gentle Introduction to XGBoost for Applied Machine Learning

Как работает градиентный бустинг python numpy

XGBoost — это opensource-библиотека, обеспечивающая высокопроизводительную реализацию Деревьев решений (Decision Tree).

В этой статье узнаем, как работает Градиентный бустинг (GB), а затем рассмотрим пример на Python.

В обычном Машинном обучении (ML), таком как дерево решений, мы просто обучаем Модель (Model) на наборе данных и используем ее для прогнозирования:

Мы можем немного поэкспериментировать с параметрами или дополнить данные, но в итоге мы по-прежнему используем ту же модель. Даже если мы строим Ансамбль (Ensemble) – комбинацию моделей, все модели обучаются по отдельности.

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

Gradient Boosting — это подход, при котором новые модели обучаются прогнозировать ошибки предыдущих моделей.

Давайте посмотрим на XGBoost в деле. Для начала установим импортируем ее и другие необходимые библиотеки:

!pip install xgboost

from sklearn import datasets import xgboost as xgb from sklearn.model_selection import train_test_split import numpy as np from sklearn.metrics import precision_score, recall_score, accuracy_score

Мы будем использовать известный Датасет (Dataset) цветов ириса:

iris = datasets.load_iris() X = iris.data y = iris.target

Целевая переменная (Target Variable) y – это числовое обозначение одного из трех видов ириса – Setosa (0), Versicolor (1) или Virginica (2). Разделим набор на Тренировочные (Train Data) и Тестовые данные (Test Data), чтобы проверить качество обучения XGBoost. Тестовые данные составят 20% (0.2):

X_train, X_test, Y_train, Y_test = train_test_split(X, y, test_size=0.2)

Чтобы XGBoost мог использовать наши данные, нам нужно преобразовать их в определенный формат – DMatrix:

D_train = xgb.DMatrix(X_train, label=Y_train) D_test = xgb.DMatrix(X_test, label=Y_test)

Теперь мы можем определить параметры нашего ансамбля:

param = < 'eta': 0.3, 'max_depth': 3, 'objective': 'multi:softprob', 'num_class': 3>steps = 20

Самыми простыми параметрами являются:

• max_depth : максимальная глубина обучаемых деревьев решений
• objective: ‘multi:softprob’ : каждому наблюдению присваивается определенная вероятность принадлежности к каждому классу.
• num_class : количество классов в наборе данных

steps – количество этапов обучения. eta же требует особого внимания.

Согласно нашей теории, Gradient Boosting включает в себя последовательное создание и добавление деревьев решений. Новые деревья создаются для исправления остаточных ошибок.

Из-за характера ансамбля, т. е. нескольких моделей, объединенных в одну очень большую сложную модель, этот метод подвержен Переобучению (Overfitting). eta дает нам шанс предотвратить это.

eta похожа на скорость обучения: вместо того, чтобы просто добавлять прогнозы новых деревьев в ансамбль, ансабль будет учитывать ошибки предыдущих деревьев, то есть назначать Веса (Weights) до 0,3.

Наконец-то мы можем обучить нашу модель:

model = xgb.train(param, D_train, steps)

Давайте теперь проведем оценку:

preds = model.predict(D_test) best_preds = np.asarray([np.argmax(line) for line in preds]) print("Точность результата измерений (Precision): <>".format(precision_score(Y_test, best_preds, average='macro'))) print("Отзыв (Recall): <>".format(recall_score(Y_test, best_preds, average='macro'))) print("Точность измерений (Accuracy): <>".format(accuracy_score(Y_test, best_preds)))

Мы получили довольно высокие показатели, в реальном мире эффективные на 97%+ модели встречаются редко:

Точность результата измерений (Precision): 0.9722222222222222 Отзыв (Recall): 0.9629629629629629 Точность измерений (Accuracy): 0.9666666666666667 

Автор оригинальной статьи: George Seif

Ноутбук, не требующий дополнительной настройки на момент написания статьи, можно скачать здесь.

Подари чашку кофе дата-сайентисту ↑

Статьи об ML / DL с примерами кода

Пишем XGBoost с нуля — часть 2: градиентный бустинг

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

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

Что такое градиентный бустинг? Картинка с гольфистом как нельзя лучше описывает основную идею. Для того, что загнать мяч в лунку, гольфист делает каждый следующий удар с учётом опыта предыдущих ударов — для него это необходимое условие, чтобы загнать мяч в лунку. Еслиочень грубо (я не мастер игры в гольф :)), то при каждом новом ударе первое, на что смотрит гольфист, это на расстояние между мячом и лункой после предыдущего удара. И основная задача — следующим ударом уменьшить это расстояние.

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

Теперь дадим чуть более строгое определение. Введём модель взвешенного голосования:

Здесь — это пространство, из которого берём объекты, — это коэффицент перед моделью и непосредственно сама модель, то есть дерево решений. Допустим, что уже на каком-то шаге с помощью описанных правил удалось добавить в композицию слабый алгоритм. Чтобы научиться понимать, какой-именно должен быть алгоритм на шаге , введем функцию ошибки:

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

Непосредственно перед реализацией вставлю ещё пару слов о том, как именно у нас всё будет устроено. Как и в прошлой статье, в качестве лосса возьмем MSE. Посчитаем её градиент:

Таким образом, вектор антиградиента будет равен . На шаге мы считаем ошибки алгоритма, полученного на прошлых итерациях. Далее обучаем наш новый алгоритм на этих ошибках, а затем со знаком минус и каким-то коэффициентом добавляем к нашему ансамблю.

Теперь приступим к реализации.

1. Реализация обычного класса градиентного бустинга

import pandas as pd import matplotlib.pyplot as plt import numpy as np from tqdm import tqdm_notebook from sklearn import datasets from sklearn.metrics import mean_squared_error as mse from sklearn.tree import DecisionTreeRegressor import itertools %matplotlib inline %load_ext Cython %%cython -a import itertools import numpy as np cimport numpy as np from itertools import * cdef class RegressionTreeFastMse: cdef public int max_depth cdef public int feature_idx cdef public int min_size cdef public int averages cdef public np.float64_t feature_threshold cdef public np.float64_t value cpdef RegressionTreeFastMse left cpdef RegressionTreeFastMse right def __init__(self, max_depth=3, min_size=4, averages=1): self.max_depth = max_depth self.min_size = min_size self.value = 0 self.feature_idx = -1 self.feature_threshold = 0 self.left = None self.right = None def fit(self, np.ndarray[np.float64_t, ndim=2] X, np.ndarray[np.float64_t, ndim=1] y): cpdef np.float64_t mean1 = 0.0 cpdef np.float64_t mean2 = 0.0 cpdef long N = X.shape[0] cpdef long N1 = X.shape[0] cpdef long N2 = 0 cpdef np.float64_t delta1 = 0.0 cpdef np.float64_t delta2 = 0.0 cpdef np.float64_t sm1 = 0.0 cpdef np.float64_t sm2 = 0.0 cpdef list index_tuples cpdef list stuff cpdef long idx = 0 cpdef np.float64_t prev_error1 = 0.0 cpdef np.float64_t prev_error2 = 0.0 cpdef long thres = 0 cpdef np.float64_t error = 0.0 cpdef np.ndarray[long, ndim=1] idxs cpdef np.float64_t x = 0.0 # начальное значение - среднее значение y self.value = y.mean() # начальная ошибка - mse между значением в листе base_error = ((y - self.value) ** 2).sum() error = base_error flag = 0 # пришли на максимальную глубину if self.max_depth self.min_size): # переопределяем самый лучший признак и границу по нему self.feature_idx, self.feature_threshold = feat, x # переопределяем значения в листах left_value, right_value = mean1, mean2 # флаг - значит сделали хороший сплит flag = 1 error = prev_error1 + prev_error2 thres += 1 # ничего не разделили, выходим if self.feature_idx == -1: return # вызываем потомков дерева self.left = RegressionTreeFastMse(self.max_depth - 1) self.left.value = left_value self.right = RegressionTreeFastMse(self.max_depth - 1) self.right.value = right_value # новые индексы для обучения потомков idxs_l = (X[:, self.feature_idx] > self.feature_threshold) idxs_r = (X[:, self.feature_idx] self.feature_threshold: return self.left.__predict(x) else: return self.right.__predict(x) def predict(self, np.ndarray[np.float64_t, ndim=2] X): y = np.zeros(X.shape[0]) for i in range(X.shape[0]): y[i] = self.__predict(X[i]) return y

class GradientBoosting(): def __init__(self, n_estimators=100, learning_rate=0.1, max_depth=3, random_state=17, n_samples = 15, min_size = 5, base_tree='Bagging'): self.n_estimators = n_estimators self.max_depth = max_depth self.learning_rate = learning_rate self.initialization = lambda y: np.mean(y) * np.ones([y.shape[0]]) self.min_size = min_size self.loss_by_iter = [] self.trees_ = [] self.loss_by_iter_test = [] self.n_samples = n_samples self.base_tree = base_tree def fit(self, X, y): self.X = X self.y = y b = self.initialization(y) prediction = b.copy() for t in tqdm_notebook(range(self.n_estimators)): if t == 0: resid = y else: # сразу пишем антиградиент resid = (y - prediction) # выбираем базовый алгоритм if self.base_tree == 'Bagging': tree = Bagging(max_depth=self.max_depth, min_size = self.min_size) if self.base_tree == 'Tree': tree = RegressionTreeFastMse(max_depth=self.max_depth, min_size = self.min_size) # обучаемся на векторе антиградиента tree.fit(X, resid) # делаем предикт и добавляем алгоритм к ансамблю b = tree.predict(X).reshape([X.shape[0]]) self.trees_.append(tree) prediction += self.learning_rate * b # добавляем только если не первая итерация if t > 0: self.loss_by_iter.append(mse(y,prediction)) return self def predict(self, X): # сначала прогноз – это просто вектор из средних значений ответов на обучении pred = np.ones([X.shape[0]]) * np.mean(self.y) # добавляем прогнозы деревьев for t in range(self.n_estimators): pred += self.learning_rate * self.trees_[t].predict(X).reshape([X.shape[0]]) return pred 

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

GDB = GradientBoosting(n_estimators=50) GDB.fit(X,y) x = GDB.predict(X) plt.grid() plt.title('Loss by iterations') plt.plot(GDB.loss_by_iter)

2. Бэггинг над решающими деревьями

Отлично, перед тем как сравнивать результаты, давайте поговорим ещё и о процедуре бэггинга над деревьями.

Тут вс просто: мы хотим защититься от переобучения, и поэтому с помощью выборок с возращением будем усреднять наши предсказания, чтобы случайно не напороться на выбросы (почему это так работает — лучше почитайте по ссылке).

class Bagging(): ''' Класс Bagging - предназначен для генерирования бустрапированного выбора моделей. ''' def __init__(self, max_depth = 3, min_size=10, n_samples = 10): #super(CART, self).__init__() self.max_depth = max_depth self.min_size = min_size self.n_samples = n_samples self.subsample_size = None self.list_of_Carts = [RegressionTreeFastMse(max_depth=self.max_depth, min_size=self.min_size) for _ in range(self.n_samples)] def get_bootstrap_samples(self, data_train, y_train): # генерируем индексы выборок с возращением indices = np.random.randint(0, len(data_train), (self.n_samples, self.subsample_size)) samples_train = data_train[indices] samples_y = y_train[indices] return samples_train, samples_y def fit(self, data_train, y_train): # обучаем каждую модель self.subsample_size = int(data_train.shape[0]) samples_train, samples_y = self.get_bootstrap_samples(data_train, y_train) for i in range(self.n_samples): self.list_of_Carts[i].fit(samples_train[i], samples_y[i].reshape(-1)) return self def predict(self, test_data): # для каждого объекта берём его средний предикт num_samples = test_data.shape[0] pred = [] for i in range(self.n_samples): pred.append(self.list_of_Carts[i].predict(test_data)) pred = np.array(pred).T return np.array([np.mean(pred[i]) for i in range(num_samples)]) 

Отлично, теперь в качестве базового алгоритма можем использовать не одно дерево, а бэггинг из деревьев — так мы, опять же, защитимся от переобучения.

3. Результаты

Сравним результаты наших алгоритмов.

from sklearn.model_selection import KFold import matplotlib.pyplot as plt from sklearn.ensemble import GradientBoostingRegressor as GDBSklearn import copy def get_metrics(X,y,n_folds=2, model=None): kf = KFold(n_splits=n_folds, shuffle=True) kf.get_n_splits(X) er_list = [] for train_index, test_index in tqdm_notebook(kf.split(X)): X_train, X_test = X[train_index], X[test_index] y_train, y_test = y[train_index], y[test_index] model.fit(X_train,y_train) predict = model.predict(X_test) er_list.append(mse(y_test, predict)) return er_list data = datasets.fetch_california_housing() X = np.array(data.data) y = np.array(data.target) er_boosting = get_metrics(X,y,30,GradientBoosting(max_depth=3, n_estimators=40, base_tree='Tree' )) er_boobagg = get_metrics(X,y,30,GradientBoosting(max_depth=3, n_estimators=40, base_tree='Bagging' )) er_sklearn_boosting = get_metrics(X,y,30,GDBSklearn(max_depth=3,n_estimators=40, learning_rate=0.1)) %matplotlib inline data = [er_sklearn_boosting, er_boosting, er_boobagg] fig7, ax7 = plt.subplots() ax7.set_title('') ax7.boxplot(data, labels=['Sklearn Boosting', 'Boosting', 'BooBag']) plt.grid() plt.show()

Мы пока не можем победить аналог из Sklearn, потому что опять не учитываем очень много параметров, которые используются в этом методе. Однако мы видим, что бэггинг чуть-чуть помогает.

Не будем отчаиваться, и перейдём к написанию XGBoost’а.

4. XGBoost

Прежде чем читать дальше, очень советую сначала ознакомиться со следующим видео, в нём очень хорошо объясняется теория.

Вспомним, какую ошибку мы минимизируем в обычном бустинге:

XGBoost явно добавляет регуляризацию в этот функционал ошибки:

Как считать этот функционал? Сначала приближаем его с помощью ряда Тейлора второго порядка, где новый алгоритм рассматривается как приращение, вдоль которого мы будем двигаться, и дальше уже расписываем в зависимости от того, какой у нас лосс:

Необходимо определить, какое дерево мы будем считать плохим, а какое хорошим.

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

В XGBoost идея очень похожа: дерево штрафуется, если сумма нормы значений в листьях в нём очень большая. Поэтому сложность дерева здесь вводится следующим образом:

— значения в листьях, — количество листьев.

В видео есть переходные формулы, мы их здесь выводить не будем. Всё сводится к тому, что новое разбиение мы будем выбирать, максимизируя gain:

Здесь — это числовые параметры регуляризации, а — соответствующие суммы из первых и вторых производных при данном разбиении.

Всё, теория очень кратко изложена, ссылки даны, теперь поговорим, какими будут производные, если мы работает с MSE. Всё просто:

Когда будем считать суммы , к первой просто прибавляем , а ко второй — просто количество.

%%cython -a import numpy as np cimport numpy as np cdef class RegressionTreeGain: cdef public int max_depth cdef public np.float64_t gain cdef public np.float64_t lmd cdef public np.float64_t gmm cdef public int feature_idx cdef public int min_size cdef public np.float64_t feature_threshold cdef public np.float64_t value cpdef public RegressionTreeGain left cpdef public RegressionTreeGain right def __init__(self, int max_depth=3, np.float64_t lmd=1.0, np.float64_t gmm=0.1, min_size=5): self.max_depth = max_depth self.gmm = gmm self.lmd = lmd self.left = None self.right = None self.feature_idx = -1 self.feature_threshold = 0 self.value = -1e9 self.min_size = min_size return def fit(self, np.ndarray[np.float64_t, ndim=2] X, np.ndarray[np.float64_t, ndim=1] y): cpdef long N = X.shape[0] cpdef long N1 = X.shape[0] cpdef long N2 = 0 cpdef long idx = 0 cpdef long thres = 0 cpdef np.float64_t gl, gr, gn cpdef np.ndarray[long, ndim=1] idxs cpdef np.float64_t x = 0.0 cpdef np.float64_t best_gain = -self.gmm if self.value == -1e9: self.value = y.mean() base_error = ((y - self.value) ** 2).sum() error = base_error flag = 0 if self.max_depth best_gain) and (min(N1,N2) > self.min_size): flag = 1 best_gain = gn left_value = -gl / (N1 + self.lmd) right_value = -gr / (N2 + self.lmd) self.feature_idx = feat self.feature_threshold = x thres += 1 self.gain = best_gain if self.feature_idx == -1: return self.left = RegressionTreeGain(max_depth=self.max_depth - 1, gmm=self.gmm, lmd=self.lmd) self.left.value = left_value self.right = RegressionTreeGain(max_depth=self.max_depth - 1, gmm=self.gmm, lmd=self.lmd) self.right.value = right_value idxs_l = (X[:, self.feature_idx] > self.feature_threshold) idxs_r = (X[:, self.feature_idx] self.feature_threshold: return self.left.__predict(x) else: return self.right.__predict(x) def predict(self, np.ndarray[np.float64_t, ndim=2] X): y = np.zeros(X.shape[0]) for i in range(X.shape[0]): y[i] = self.__predict(X[i]) return y

Небольшое уточнение: чтобы формулы в деревьях с gain’ом были красивее, в бустинге обучаем таргет со знаком минус.

Слегка модифицируем наш бустинг, сделаем некоторые параметры адаптивными. Например, если замечаем, что лосс начал выходить на плато, то уменьшаем learning rate и увеличиваем max_depth у следующих эстиматоров. Также добавим новый бэггинг — теперь сделаем бустинг над бэггингами из деревьев с gain’ом:

class Bagging(): def __init__(self, max_depth = 3, min_size=5, n_samples = 10): self.max_depth = max_depth self.min_size = min_size self.n_samples = n_samples self.subsample_size = None self.list_of_Carts = [RegressionTreeGain(max_depth=self.max_depth, min_size=self.min_size) for _ in range(self.n_samples)] def get_bootstrap_samples(self, data_train, y_train): indices = np.random.randint(0, len(data_train), (self.n_samples, self.subsample_size)) samples_train = data_train[indices] samples_y = y_train[indices] return samples_train, samples_y def fit(self, data_train, y_train): self.subsample_size = int(data_train.shape[0]) samples_train, samples_y = self.get_bootstrap_samples(data_train, y_train) for i in range(self.n_samples): self.list_of_Carts[i].fit(samples_train[i], samples_y[i].reshape(-1)) return self def predict(self, test_data): num_samples = test_data.shape[0] pred = [] for i in range(self.n_samples): pred.append(self.list_of_Carts[i].predict(test_data)) pred = np.array(pred).T return np.array([np.mean(pred[i]) for i in range(num_samples)])

class GradientBoosting(): def __init__(self, n_estimators=100, learning_rate=0.2, max_depth=3, random_state=17, n_samples = 15, min_size = 5, base_tree='Bagging'): self.n_estimators = n_estimators self.max_depth = max_depth self.learning_rate = learning_rate self.initialization = lambda y: np.mean(y) * np.ones([y.shape[0]]) self.min_size = min_size self.loss_by_iter = [] self.trees_ = [] self.loss_by_iter_test = [] self.n_samples = n_samples self.base_tree = base_tree # хотим как-то регулировать работу алгоритма на поздних итерациях # если ошибка застряла, то уменьшаем lr и увеличиваем max_depth self.add_to_max_depth = 1 self.init_mse_board = 1.5 def fit(self, X, y): print (self.base_tree) self.X = X self.y = y b = self.initialization(y) prediction = b.copy() for t in tqdm_notebook(range(self.n_estimators)): if t == 0: resid = y else: resid = (y - prediction) if (mse(temp_resid,resid) < self.init_mse_board): self.init_mse_board /= 1.5 self.add_to_max_depth += 1 self.learning_rate /= 1.1 # print ('Alert!', t, self.add_to_max_depth) if self.base_tree == 'Bagging': tree = Bagging(max_depth=self.max_depth+self.add_to_max_depth, min_size = self.min_size) resid = -resid if self.base_tree == 'Tree': tree = RegressionTreeFastMse(max_depth=self.max_depth+self.add_to_max_depth, min_size = self.min_size) if self.base_tree == 'XGBoost': tree = RegressionTreeGain(max_depth=self.max_depth+self.add_to_max_depth, min_size = self.min_size) resid = -resid tree.fit(X, resid) b = tree.predict(X).reshape([X.shape[0]]) # print (b.shape) self.trees_.append(tree) prediction += self.learning_rate * b temp_resid = resid return self def predict(self, X): # сначала прогноз – это просто вектор из средних значений ответов на обучении pred = np.ones([X.shape[0]]) * np.mean(self.y) # добавляем прогнозы деревьев for t in range(self.n_estimators): pred += self.learning_rate * self.trees_[t].predict(X).reshape([X.shape[0]]) return pred

5. Результаты

По традиции, сравним результаты:

data = datasets.fetch_california_housing() X = np.array(data.data) y = np.array(data.target) import matplotlib.pyplot as plt from sklearn.ensemble import GradientBoostingRegressor as GDBSklearn er_boosting_bagging = get_metrics(X,y,30,GradientBoosting(max_depth=3, n_estimators=150,base_tree='Bagging')) er_boosting_xgb = get_metrics(X,y,30,GradientBoosting(max_depth=3, n_estimators=150,base_tree='XGBoost')) er_sklearn_boosting = get_metrics(X,y,30,GDBSklearn(max_depth=3,n_estimators=150,learning_rate=0.2)) %matplotlib inline data = [er_sklearn_boosting, er_boosting_xgb, er_boosting_bagging] fig7, ax7 = plt.subplots() ax7.set_title('') ax7.boxplot(data, labels=['GdbSklearn', 'Xgboost', 'XGBooBag']) plt.grid() plt.show()

Картинка будет следующая:

Самая низкая ошибка у XGBoost, но у XGBooBag ошибка более скученная, что определённо лучше: алгоритм более устойчив.

На этом всё. Очень надеюсь, что материал, изложенный в двух статьях, был полезен, и вы смогли узнать для себя что-то новое. Особую благодарность выражаю Дмитрию за всестороннюю обратную связь и исходники, Антону — за советы, Владимиру — за сложные задания по учебе.