Guides
1281 記事 20 ドメイン

勾配ブースティングの理論と実装 — XGBoost/LightGBMの数理

アンサンブル

ランダムフォレストが「多数の木の平均」でバリアンスを下げるのに対し、勾配ブースティング（Gradient Boosting）は全く異なるアプローチをとります。弱い学習器を順番に追加し、前のモデルが間違えた部分を次のモデルが修正する——このように残差を逐次的に学習することでバイアスを下げていくのです。

たとえるなら、ランダムフォレストは「100人の専門家が独立に意見を述べ、多数決をとる」のに対し、勾配ブースティングは「1人目の専門家が診断し、2人目が1人目の間違いを修正し、3人目が2人目の修正の残りを修正する…」という逐次改善プロセスです。

勾配ブースティングは実務で最も強力なアルゴリズムの一つであり、KaggleなどのMLコンペティションで圧倒的な実績を持ちます。XGBoostやLightGBMといった高速な実装が広く使われています。

勾配ブースティングを理解すると、以下のような場面で活用できます。

  • テーブルデータの予測: 構造化データではニューラルネットワークに匹敵する性能
  • XGBoost/LightGBMの内部動作の理解: ハイパーパラメータの意味と調整方法
  • カスタム損失関数: 任意の微分可能な損失関数への適用
  • 学習率と木の数のトレードオフ: 正則化の効果

本記事の内容

  • Boostingの基本概念とAdaBoostからの発展
  • 勾配ブースティングの理論（関数空間での勾配降下法）
  • XGBoostの正則化とNewtonステップ
  • LightGBMの高速化テクニック
  • Pythonでのスクラッチ実装と可視化

前提知識

この記事を読む前に、以下の記事を読んでおくと理解が深まります。

Boostingの基本概念

AdaBoostから勾配ブースティングへ

AdaBoost（Adaptive Boosting; Freund & Schapire, 1997）は、誤分類されたサンプルに大きな重みを与え、次の弱学習器がそのサンプルに集中するようにする手法です。これは指数損失の最小化と等価であることが後に示されました。

Friedman (2001) は、AdaBoostのアイデアを一般化し、任意の微分可能な損失関数に適用可能な勾配ブースティングを提案しました。鍵となるアイデアは、ブースティングを関数空間での勾配降下法として捉えることです。

関数空間での勾配降下法

通常の勾配降下法はパラメータ空間で行われます。$\bm{w}_{t+1} = \bm{w}_t – \eta \nabla_{\bm{w}} J$。

勾配ブースティングは関数空間で行います。予測関数 $F$ を直接更新対象とし

$$ F_{t+1}(\bm{x}) = F_t(\bm{x}) – \eta \frac{\partial J}{\partial F(\bm{x})} $$

損失関数 $J = \sum_i L(y_i, F(\bm{x}_i))$ の $F(\bm{x}_i)$ に関する「勾配」は

$$ r_i = -\frac{\partial L(y_i, F(\bm{x}_i))}{\partial F(\bm{x}_i)} $$

これは擬似残差（pseudo-residual）と呼ばれます。MSEの場合、$L = \frac{1}{2}(y – F)^2$ なので $r_i = y_i – F(\bm{x}_i)$ と通常の残差に一致します。

新しい木 $h_t$ を擬似残差にフィットすることで、$F_{t+1} = F_t + \eta h_t$ と関数空間での勾配降下ステップを近似するのが勾配ブースティングの本質です。

勾配ブースティングのアルゴリズム

完全なアルゴリズム

入力: 訓練データ $\{(\bm{x}_i, y_i)\}_{i=1}^n$、損失関数 $L$、木の数 $M$、学習率 $\eta$

ステップ1: 初期予測の設定

$$ F_0(\bm{x}) = \arg\min_\gamma \sum_{i=1}^n L(y_i, \gamma) $$

回帰の場合は $y$ の平均、分類の場合は対数オッズの初期値など。

ステップ2: $m = 1, \ldots, M$ について以下を繰り返す

（2a）擬似残差の計算:

$$ r_{im} = -\left[\frac{\partial L(y_i, F(\bm{x}_i))}{\partial F(\bm{x}_i)}\right]_{F = F_{m-1}} $$

（2b）擬似残差に回帰木 $h_m$ をフィットし、葉の領域 $R_{jm}$ を得る

（2c）各葉の最適値を計算:

$$ \gamma_{jm} = \arg\min_\gamma \sum_{\bm{x}_i \in R_{jm}} L(y_i, F_{m-1}(\bm{x}_i) + \gamma) $$

（2d）モデルを更新:

$$ F_m(\bm{x}) = F_{m-1}(\bm{x}) + \eta \sum_j \gamma_{jm} \mathbb{1}[\bm{x} \in R_{jm}] $$

ステップ3: 最終モデル $F_M(\bm{x})$ を出力

学習率（shrinkage）の役割

学習率 $\eta \in (0, 1]$ は各木の寄与を縮小します。小さい $\eta$ は「ゆっくり学習する」ことを意味し、過学習を防ぐ正則化効果があります。ただし、同じ性能を達成するのにより多くの木が必要になります。

一般に 小さな $\eta$ + 多くの木 の方が 大きな $\eta$ + 少ない木 よりも汎化性能が高いことが経験的に知られています。

XGBoostの数理

正則化付き目的関数

XGBoost（Chen & Guestrin, 2016）は勾配ブースティングに明示的な正則化を導入します。

$$ \begin{equation} \text{Obj}^{(m)} = \sum_{i=1}^n L(y_i, F_{m-1}(\bm{x}_i) + h_m(\bm{x}_i)) + \Omega(h_m) \end{equation} $$

正則化項は

$$ \Omega(h) = \gamma T + \frac{1}{2}\lambda\sum_{j=1}^T w_j^2 $$

$T$ は葉の数、$w_j$ は葉 $j$ の値です。$\gamma$ は葉の数にペナルティ（枝刈り効果）、$\lambda$ は葉の値にL2ペナルティを課します。

Newtonの方法による近似

XGBoostは損失関数の2次テイラー展開を用いて各木の構造を効率的に決定します。

$$ L(y_i, F_{m-1} + h_m) \approx L(y_i, F_{m-1}) + g_i h_m(\bm{x}_i) + \frac{1}{2}h_i h_m(\bm{x}_i)^2 $$

$g_i = \frac{\partial L}{\partial F}|_{F_{m-1}}$ は勾配、$h_i = \frac{\partial^2 L}{\partial F^2}|_{F_{m-1}}$ はヘシアンです。

最適な葉の値とスコアの利得は解析的に計算でき、分割の判定が非常に効率的になります。

$$ w_j^* = -\frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda}, \quad \text{Gain} = \frac{1}{2}\left[\frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} – \frac{(G_L+G_R)^2}{H_L+H_R+\lambda}\right] – \gamma $$

$G = \sum g_i$, $H = \sum h_i$ は勾配とヘシアンの和です。

Pythonでのスクラッチ実装

import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeRegressor

class GradientBoostingRegressorScratch:
    """勾配ブースティング回帰のスクラッチ実装"""

    def __init__(self, n_estimators=100, learning_rate=0.1, max_depth=3):
        self.n_estimators = n_estimators
        self.lr = learning_rate
        self.max_depth = max_depth
        self.trees = []
        self.train_losses = []

    def fit(self, X, y):
        # 初期予測: 平均値
        self.init_pred = np.mean(y)
        F = np.full(len(y), self.init_pred)

        for m in range(self.n_estimators):
            # 擬似残差（MSEの場合は通常の残差）
            residuals = y - F

            # 残差に回帰木をフィット
            tree = DecisionTreeRegressor(max_depth=self.max_depth)
            tree.fit(X, residuals)
            self.trees.append(tree)

            # モデル更新
            F += self.lr * tree.predict(X)

            # 損失の記録
            self.train_losses.append(np.mean((y - F) ** 2))

        return self

    def predict(self, X):
        F = np.full(len(X), self.init_pred)
        for tree in self.trees:
            F += self.lr * tree.predict(X)
        return F

# テスト: 非線形回帰
np.random.seed(42)
n = 300
X = np.sort(np.random.uniform(0, 10, n)).reshape(-1, 1)
y = np.sin(X.ravel()) + 0.5 * np.cos(2 * X.ravel()) + np.random.normal(0, 0.3, n)

fig, axes = plt.subplots(2, 2, figsize=(14, 10))

# (a-c) 異なるステージでの予測
X_plot = np.linspace(0, 10, 500).reshape(-1, 1)
y_true = np.sin(X_plot.ravel()) + 0.5 * np.cos(2 * X_plot.ravel())

stages = [1, 10, 100]
for ax, n_trees in zip(axes.flat[:3], stages):
    gb = GradientBoostingRegressorScratch(n_estimators=n_trees, learning_rate=0.1, max_depth=3)
    gb.fit(X, y)
    y_pred = gb.predict(X_plot)

    ax.scatter(X, y, c="gray", s=10, alpha=0.3, label="Data")
    ax.plot(X_plot, y_true, "g--", linewidth=2, label="True function")
    ax.plot(X_plot, y_pred, "b-", linewidth=2, label=f"GB ({n_trees} trees)")
    ax.set_title(f"Gradient Boosting: {n_trees} tree(s)", fontsize=13)
    ax.set_xlabel("x", fontsize=12)
    ax.set_ylabel("y", fontsize=12)
    ax.legend(fontsize=9)
    ax.grid(True, alpha=0.3)

# (d) 学習曲線
ax = axes[1, 1]
for lr, color in [(0.01, "blue"), (0.1, "green"), (0.5, "red")]:
    gb = GradientBoostingRegressorScratch(n_estimators=200, learning_rate=lr, max_depth=3)
    gb.fit(X, y)
    ax.plot(gb.train_losses, color=color, linewidth=2, label=f"lr={lr}")

ax.set_xlabel("Number of Trees", fontsize=12)
ax.set_ylabel("Training MSE", fontsize=12)
ax.set_title("Learning Rate Effect", fontsize=13)
ax.legend(fontsize=10)
ax.grid(True, alpha=0.3)
ax.set_yscale("log")

plt.tight_layout()
plt.savefig("gradient_boosting.png", dpi=150, bbox_inches="tight")
plt.show()

このグラフから、勾配ブースティングの逐次学習プロセスが読み取れます。

  1. 1本の木（左上）: 初期段階ではデータのざっくりとした傾向しか捉えられていません。3深さの決定木は表現力が限られているためです

  2. 10本の木（右上）: 非線形なパターンが徐々に捉えられ始めています。各木が前の木の残差を学習することで、フィットが改善されています

  3. 100本の木（左下）: 真の関数に非常に近いフィットが得られています。100本の弱い木の累積効果で、複雑な非線形関数を高精度に近似できています

  4. 学習率の効果（右下）: 大きな学習率（$\eta=0.5$、赤）は速く収束しますが最終的な損失が高く、過学習のリスクがあります。小さな学習率（$\eta=0.01$、青）は収束が遅いですが最終的により低い損失に到達します。$\eta=0.1$（緑）は良いバランスです

LightGBMの高速化

LightGBM（Ke et al., 2017）は、大規模データに対する勾配ブースティングの計算効率を改善するいくつかの工夫を導入しています。

Histogram-based split: 連続値の特徴量をビン（ヒストグラム）に離散化してから分割点を探索します。候補点が256程度に減り、計算が大幅に高速化されます。

Leaf-wise growth: 通常の決定木はlevel-wise（各レベルの全ノードを分割）ですが、LightGBMはleaf-wise（最も利得の大きい葉のみを分割）で成長させます。同じ葉の数で、より高い精度を達成できます。

GOSS (Gradient-based One-Side Sampling): 勾配が小さいサンプル（既にうまく予測できているサンプル）をランダムにサブサンプリングし、計算量を削減します。

まとめ

本記事では、勾配ブースティングの理論と実装について解説しました。

  • 勾配ブースティングは関数空間での勾配降下法であり、擬似残差に木をフィットすることで逐次的にバイアスを低減する
  • 任意の微分可能な損失関数に適用可能で、MSE、交差エントロピー、カスタム損失関数に対応
  • XGBoostは2次テイラー展開と正則化により、効率的かつ正則化された勾配ブースティングを実現
  • LightGBMはHistogram-based split、Leaf-wise growth、GOSSにより大規模データへのスケーラビリティを改善
  • 学習率と木の数はトレードオフの関係にあり、小さな学習率+多くの木が汎化性能に優れる

次のステップとして、以下の記事も参考にしてください。

関連記事

前の記事

ランダムフォレストの理論と実装を解説

次の記事

SVM（サポートベクターマシン）の理論と双対問題を導出する

関連タグ: LightGBM XGBoost アンサンブル 勾配ブースティング 機械学習 決定木