Градиентный бустинг (Gradient Boosting Machine, GBM)

Алгоритм градиентного бустинга (часто обозначаемый как GBM или GBDT — Gradient Boosted Decision Trees) — это один из наиболее мощных и универсальных ансамблевых методов машинного обучения, используемый для решения задач регрессии и классификации . Его ключевая идея заключается в последовательном построении композиции из «слабых» моделей (обычно решающих деревьев), где каждая новая модель обучается исправлять ошибки, допущенные всеми предыдущими моделями .

1. Подробное описание

Постановка задачи. Пусть дана обучающая выборка $\{(\mathbf{x}_i, y_i)\}_{i=1}^\ell$, где $\mathbf{x}_i$ — вектор признаков объекта, а $y_i$ — целевая переменная (вещественное число для регрессии или метка класса для классификации). Требуется построить функцию $F(\mathbf{x})$, которая по входным признакам предсказывает целевую переменную с минимальной ошибкой.

Входные и выходные данные. На вход алгоритм принимает матрицу признаков X и вектор целевых переменных y. На выходе получается ансамбль из M базовых алгоритмов (деревьев решений), который для нового объекта $\mathbf{x}$ выдаёт предсказание $F_M(\mathbf{x}) = \sum_{m=0}^{M} \gamma_m b_m(\mathbf{x})$, где $b_0(\mathbf{x})$ — начальное приближение (например, среднее значение для регрессии), а $b_m(\mathbf{x})$ — деревья, построенные на каждой итерации .

Ключевая идея. В отличие от бэггинга (например, случайного леса), где модели строятся независимо, градиентный бустинг строит модели последовательно. На каждой итерации алгоритм вычисляет антиградиент функции потерь $L(y, F(\mathbf{x}))$ по текущим предсказаниям. Новое дерево обучается аппроксимировать этот антиградиент, то есть указывать направление, в котором нужно изменить текущие предсказания, чтобы минимизировать ошибку на обучающей выборке . Это делает алгоритм чрезвычайно гибким, так как он может работать с любой дифференцируемой функцией потерь .

Исторический контекст. Идея бустинга была предложена Фройндом и Шапиром в 1997 году, а её обобщение в виде градиентного бустинга для произвольных функций потерь было разработано Джеромом Фридманом в 2001 году . С тех пор алгоритм стал одним из стандартов индустрии, а его высокопроизводительные реализации, такие как XGBoost, LightGBM и CatBoost, широко используются в соревнованиях по машинному обучению и на производстве .

2. Принцип работы

Алгоритм начинает работу с создания начального приближения $F_0(\mathbf{x})$, которое минимизирует функцию потерь на всей выборке. Для задачи регрессии с квадратичной функцией потерь $L(y, F) = \frac{1}{2}(y - F)^2$ это будет среднее значение целевой переменной: $F_0(\mathbf{x}) = \bar{y}$ .

Затем на каждой итерации $m = 1, \dots, M$ выполняются следующие шаги :

Вычисление псевдо-остатков. Для каждого объекта $i$ вычисляется значение антиградиента функции потерь по текущему предсказанию: $$ r_{im} = - \left[ \frac{\partial L(y_i, F(\mathbf{x}i))}{\partial F(\mathbf{x}_i)} \right] $$ Для квадратичной функции потерь }$r_{im} = y_i - F_{m-1}(\mathbf{x}_i)$ — это обычные остатки регрессии .
Обучение базового алгоритма. Новое дерево решений $b_m(\mathbf{x})$ обучается предсказывать вычисленные псевдо-остатки $r_{im}$ по входным признакам $\mathbf{x}_i$ .
Поиск оптимального коэффициента. Для каждого листового узла $j$ дерева $b_m$ вычисляется оптимальное значение $\gamma_{mj}$, минимизирующее функцию потерь: $$ \gamma_{mj} = \arg\min_{\gamma} \sum_{\mathbf{x}i \in R_i) + \gamma) $$ где }} L(y_i, F_{m-1}(\mathbf{x$R_{mj}$ — множество объектов, попавших в листовой узел $j$ .
Обновление модели. Предсказания обновляются с добавлением нового дерева, умноженного на коэффициент скорости обучения (learning rate) $\eta$: $$ F_m(\mathbf{x}) = F_{m-1}(\mathbf{x}) + \eta \cdot \sum_{j} \gamma_{mj} \cdot \mathbb{I}(\mathbf{x} \in R_{mj}) $$

Процесс повторяется заданное число итераций $M$ или до сходимости алгоритма . Для бинарной классификации начальное предсказание обычно равно логарифму отношения шансов (log-odds), что соответствует вероятности 0.5, а на каждом шаге используется логистическая функция для преобразования сырых предсказаний в вероятности .

Математическая формулировка (для регрессии с квадратичной функцией потерь)

Пусть функция потерь $L(y, F) = \frac{1}{2}(y - F)^2$. Тогда антиградиент равен $r_i = y_i - F(\mathbf{x}_i)$ .

Шаг 0: $F_0(\mathbf{x}) = \frac{1}{\ell} \sum_{i=1}^{\ell} y_i$.

Шаг m: Для каждого объекта $i$ вычисляется остаток $r_{im} = y_i - F_{m-1}(\mathbf{x}_i)$. Дерево $b_m(\mathbf{x})$ обучается на данных $\{(\mathbf{x}_i, r_{im})\}_{i=1}^{\ell}$. Для каждого листового узла $R_{mj}$ вычисляется $\gamma_{mj} = \text{mean}(r_{im})$ для объектов, попавших в этот лист. Модель обновляется как $F_m(\mathbf{x}) = F_{m-1}(\mathbf{x}) + \eta \cdot b_m(\mathbf{x})$.

Выход: $F_M(\mathbf{x}) = \sum_{m=0}^M \eta \cdot b_m(\mathbf{x})$, где $b_0(\mathbf{x}) = F_0(\mathbf{x})$.

Пояснение: - $F(\mathbf{x})$ — предсказание модели. - $y$ — истинное значение целевой переменной. - $L$ — функция потерь. - $\eta$ — скорость обучения (learning rate), параметр, контролирующий вклад каждого дерева . - $M$ — количество деревьев в ансамбле . - $r_{im}$ — псевдо-остаток для объекта $i$ на итерации $m$ .

3. Пример реализации на Python

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

import numpy as np
from sklearn.tree import DecisionTreeRegressor
from sklearn.datasets import make_regression
from sklearn.model_selection import train_test_split
from sklearn.metrics import mean_squared_error

class SimpleGradientBoostingRegressor:
    """
    Реализация градиентного бустинга для регрессии.
    Основана на последовательном обучении деревьев на псевдо-остатках.
    """
    def __init__(self, n_estimators=100, learning_rate=0.1, max_depth=3, min_samples_split=2):
        self.n_estimators = n_estimators
        self.learning_rate = learning_rate
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.trees = []
        self.F0 = None

    def fit(self, X, y):
        """
        Обучение модели градиентного бустинга.

        Параметры:
        X (np.ndarray): Матрица признаков.
        y (np.ndarray): Вектор целевых переменных.
        """
        # Шаг 0: Инициализация модели средним значением
        self.F0 = np.mean(y)
        F = np.full_like(y, self.F0, dtype=np.float64)

        self.trees = []
        for m in range(self.n_estimators):
            # Вычисление псевдо-остатков (для MSE это просто разность y - F)
            residuals = y - F

            # Обучение дерева на псевдо-остатках
            tree = DecisionTreeRegressor(
                max_depth=self.max_depth,
                min_samples_split=self.min_samples_split,
                random_state=42
            )
            tree.fit(X, residuals)

            # Обновление предсказаний с учётом learning rate
            # Для упрощения используем предсказания дерева напрямую без отдельного поиска gamma
            # (в полной версии для каждого листа вычисляется оптимальное gamma)
            F += self.learning_rate * tree.predict(X)

            self.trees.append(tree)

        return self

    def predict(self, X):
        """
        Предсказание на новых данных.

        Параметры:
        X (np.ndarray): Матрица признаков.

        Возвращает:
        np.ndarray: Вектор предсказаний.
        """
        preds = np.full(X.shape[0], self.F0, dtype=np.float64)
        for tree in self.trees:
            preds += self.learning_rate * tree.predict(X)
        return preds


# Пример использования
if __name__ == "__main__":
    # Генерация синтетического датасета для регрессии
    X, y = make_regression(n_samples=500, n_features=10, noise=10, random_state=42)
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

    # Обучение модели градиентного бустинга
    gbm = SimpleGradientBoostingRegressor(
        n_estimators=50,
        learning_rate=0.1,
        max_depth=3
    )
    gbm.fit(X_train, y_train)

    # Предсказание и оценка качества
    y_pred = gbm.predict(X_test)
    mse = mean_squared_error(y_test, y_pred)

    print(f"Среднеквадратичная ошибка (MSE) на тестовой выборке: {mse:.4f}")
    print(f"Количество деревьев в ансамбле: {len(gbm.trees)}")

4. Достоинства и недостатки

Достоинства:

Высокое качество предсказаний. На табличных данных градиентный бустинг часто показывает результаты, превосходящие другие алгоритмы, включая нейронные сети .
Универсальность. Алгоритм может работать с произвольными дифференцируемыми функциями потерь, что позволяет решать широкий спектр задач (регрессия, классификация, ранжирование и др.) .
Обработка разнородных данных. Деревья решений, используемые в качестве базовых алгоритмов, хорошо работают с категориальными признаками и пропущенными значениями .
Автоматический отбор признаков. В процессе построения деревьев алгоритм оценивает важность каждого признака, что помогает в интерпретации модели .
Сравнительная интерпретируемость. Хотя ансамбль из сотен деревьев сложнее интерпретировать, чем одно дерево, существуют методы визуализации и объяснения предсказаний (например, SHAP), что делает его более прозрачным по сравнению с нейронными сетями .

Недостатки:

Склонность к переобучению. Без правильной регуляризации (ограничение глубины деревьев, использование learning rate, ранняя остановка) модель может хорошо запомнить обучающую выборку, но плохо обобщаться на новые данные .
Высокое время обучения. Последовательный характер построения деревьев затрудняет распараллеливание вычислений (в отличие от случайного леса) .
Чувствительность к выбросам. В отличие от некоторых робастных методов, стандартный градиентный бустинг может сильно смещаться под влиянием аномалий в данных .
Сложность настройки гиперпараметров. Для достижения высокого качества требуется тщательный подбор большого числа параметров: количество деревьев, скорость обучения, глубина деревьев, регуляризация и др. .
Неэффективность на некоторых типах данных. Алгоритм не очень хорошо работает с разреженными текстовыми данными или изображениями, где нейронные сети имеют значительное преимущество .

5. Области применения

Машинное обучение и рекомендательные системы (прогнозирование поведения пользователей, персонализация контента, ранжирование результатов поиска).
Экономика и финансы (кредитный скоринг, прогнозирование цен на активы, оценка рисков, высокочастотная торговля ).
Логистика и управление цепочками (прогнозирование спроса, оптимизация маршрутов доставки, управление запасами ).
Аналитика данных и базы данных (построение прогнозных моделей для бизнес-аналитики, детекция аномалий в транзакциях).
Биотехнологии и медицинская информатика (прогнозирование заболеваний на основе клинических данных, анализ геномных последовательностей ).