勾配ブースティングのしくみ：残差の足し算から XGBoost・LightGBM・CatBoost まで

売上・顧客の属性・センサーの値のような 表の形のデータ の予測では、今でも 勾配ブースティング がいちばんよく使われる手法の 1 つです。データ分析のコンペティションでも、XGBoost・LightGBM・CatBoost のどれかが上位の解法にほぼ必ず入っています。

深層学習以前の機械学習 では「今の予測の残差を小さな木で当てて足していく」という基本の形だけを説明しました。この記事では、その先にある次のことを説明します。

• 学習率と木の本数 はどう関係し、どう決めればよいのか
• XGBoost が使う 2 階微分の近似 で、葉の値と分割の良さ（利得）がどう計算されるのか
• LightGBM の ヒストグラム法 は、何を省いて速くしているのか
• カテゴリ変数 を扱うときに何が問題になり、CatBoost はどう解決したのか

結論を先に書くと、次のように整理できます。

工夫	何をするか	効果
学習率（縮小）	木の出力を 0.1 倍などに縮めて足す	本数は増えるが、過学習しにくく、本数の選び方にも鈍感になる
2 階微分（ニュートン法）	勾配だけでなく曲がり具合も使って葉の値を決める	少ない本数で損失が下がる。正則化を式に入れやすい
ヒストグラム法	特徴の値を数十〜数百のビンにまとめ、しきい値の候補を減らす	精度をほとんど落とさずに分割の探索を速くする
順序つきのターゲット統計	カテゴリを、その行より前のデータだけで計算した平均の目的変数で置き換える	目的変数の情報が漏れて過学習するのを防ぐ

説明の途中に出てくる計算例は、Python と NumPy で実際に動かした結果です。

環境

計算例を動かした環境です。

項目	バージョン
Python	3.13
NumPy	2.5

勾配ブースティングをおさらいする

損失の勾配を次の木で当てる

勾配ブースティングは、予測 F(x) を小さな決定木の足し算で作ります。

F(x) = f₁(x) + f₂(x) + … + f_M(x)

m 本目の木は、それまでの木の合計 F_{m−1}(x) に足したときに損失がいちばん下がるように作ります。2 乗誤差なら、損失を下げる向きは 残差（正解 − 予測）そのものです。一般の損失でも、損失の勾配の逆向きが「損失が下がる向き」なので、それを次の木で当てます。これが名前の「勾配」の由来です。

分類のときは、木の出力の合計を 対数オッズ（log(p / (1 − p))）として扱い、シグモイド関数で確率に直します。損失はロジスティック損失（2 値の交差エントロピー誤差）です。予測の確率を p、正解を y（0 か 1）とすると、対数オッズについての勾配は p − y という簡単な形になります。

計算例に使うデータ

6 個の特徴を持つ架空の 2 値分類のデータを作ります。正解になる確率は、特徴 0 の sin・特徴 1 と 2 の掛け算・特徴 3 のしきい値で決まり、特徴 4 と 5 は関係ありません。線形のモデルでは表しにくい形をわざと入れています。

import numpy as np

def make_data(rng, n):
    X = rng.normal(size=(n, 6))
    logit = 2 * np.sin(X[:, 0] * 1.5) + X[:, 1] * X[:, 2] + (X[:, 3] > 0.5) - 0.5
    y = (rng.random(n) < 1 / (1 + np.exp(-logit))).astype(float)
    return X, y

2 階微分を使う：XGBoost の葉の値と分割の利得

損失を 2 次式で近似する

最初の勾配ブースティング（Friedman, 2001）は、勾配を 2 乗誤差で当てる木を作ってから、葉ごとに値を調整していました。XGBoost（Chen と Guestrin, 2016）は、損失を今の予測のまわりで 2 次式で近似 して、木の作り方と葉の値を 1 つの式から導きます。

1 件ごとの損失の 1 階微分を g、2 階微分を h とすると、ある葉に値 w を足したときの損失の変化は、次の 2 次式で近似できます。λ は葉の値が大きくなりすぎないようにする L2 正則化の強さです。

損失の変化 ≈ Σ (g × w + ½ × h × w²) + ½ × λ × w²

これを w について最小にすると、葉の値と、そのときの損失の下がり方が決まります。G はその葉に入ったデータの g の合計、H は h の合計です。

葉の値 w* = −G / (H + λ)
損失の下がり方 = ½ × G² / (H + λ)

ロジスティック損失では g = p − y、h = p(1 − p) です。h は「その点で損失がどれだけ曲がっているか」で、予測が 0 か 1 に近いほど小さくなります。勾配を h で割るのは、坂の傾きだけでなく曲がり具合まで見て 1 歩の大きさを決める ニュートン法 と同じ考え方です。

1 つの葉で計算してみる

正解が [1, 1, 0, 1] の 4 件が 1 つの葉に入り、今の予測がどれも 0.5 だったとします。

import numpy as np

# 1 つの葉に入った 4 件のデータ（ロジスティック損失）
y = np.array([1, 1, 0, 1])
p = np.full(4, 0.5)            # 今の予測確率（最初はみな 0.5）
g = p - y                      # 1 階微分（勾配）
h = p * (1 - p)                # 2 階微分
lam = 1.0
w = -g.sum() / (h.sum() + lam) # 葉の値（対数オッズに足す量）
print(g, h, round(w, 3))
print(round(1 / (1 + np.exp(-w)), 3))  # 葉の値を足したあとの確率

def score(G, H, lam=1.0):
    return G**2 / (H + lam)

# 分割の利得：左右に分けたときのスコアの増え方
gL, hL = g[:2], h[:2]; gR, hR = g[2:], h[2:]
gain = 0.5 * (score(gL.sum(), hL.sum()) + score(gR.sum(), hR.sum()) - score(g.sum(), h.sum()))
print(round(gain, 4))

実行結果:

[-0.5 -0.5  0.5 -0.5] [0.25 0.25 0.25 0.25] 0.5
0.622
0.0833

G = −1、H = 1 なので、葉の値は −(−1) / (1 + 1) = 0.5 です。確率は 0.5 から 0.622 に上がりました。4 件中 3 件が 1 なので、本当は 0.75 まで上げたいところですが、λ = 1 の正則化で控えめになっています。

分割の利得

木を作るときは、葉を 2 つに分けたときに「損失の下がり方」がどれだけ増えるかで、分け方を選びます。

利得 = ½ × [ G_L² / (H_L + λ) + G_R² / (H_R + λ) − G² / (H + λ) ] − γ

上の例で、[1, 1] と [0, 1] に分けると利得は 0.0833 でした。γ は「葉を 1 つ増やすごとに払う罰則」で、利得が γ より小さい分割はしません。λ・γ と、葉に入る h の合計の下限（XGBoost の min_child_weight）が、木を必要以上に細かくしないための主な正則化です。

木を作るコード

この式で、深さを決めた木を作るコードです。特徴ごとにデータを並べ替えて g と h の累積和を取れば、すべてのしきい値の利得を一度に計算できます。thresholds は後のヒストグラム法で使います。

def build_tree(X, g, h, depth, lam=1.0, gamma=0.0, min_h=1.0, thresholds=None):
    """g, h から 2 階微分の近似で木を作る。thresholds を渡すとその候補だけを試す（ヒストグラム法）"""
    G, H = g.sum(), h.sum()
    leaf = {"value": -G / (H + lam)}
    if depth == 0:
        return leaf
    parent = G**2 / (H + lam)
    best = (0.0, None, None)
    for j in range(X.shape[1]):
        cand = thresholds[j] if thresholds is not None else np.unique(X[:, j])[:-1]
        order = np.argsort(X[:, j])
        xs, gs, hs = X[order, j], np.cumsum(g[order]), np.cumsum(h[order])
        k = np.searchsorted(xs, cand, side="right") - 1   # しきい値以下の最後の位置
        ok = k >= 0
        GL, HL = gs[k[ok]], hs[k[ok]]
        GR, HR = G - GL, H - HL
        gain = 0.5 * (GL**2 / (HL + lam) + GR**2 / (HR + lam) - parent) - gamma
        gain[(HL < min_h) | (HR < min_h)] = -np.inf
        if gain.size and gain.max() > best[0]:
            i = gain.argmax()
            best = (gain[i], j, cand[ok][i])
    if best[1] is None:
        return leaf
    _, j, t = best
    m = X[:, j] <= t
    return {"feature": j, "threshold": t,
            "left": build_tree(X[m], g[m], h[m], depth - 1, lam, gamma, min_h, thresholds),
            "right": build_tree(X[~m], g[~m], h[~m], depth - 1, lam, gamma, min_h, thresholds)}

def predict_tree(node, X):
    if "value" in node:
        return np.full(len(X), node["value"])
    m = X[:, node["feature"]] <= node["threshold"]
    out = np.empty(len(X))
    out[m] = predict_tree(node["left"], X[m])
    out[~m] = predict_tree(node["right"], X[~m])
    return out

def logloss(y, f):
    p = 1 / (1 + np.exp(-f))
    return -np.mean(y * np.log(p + 1e-12) + (1 - y) * np.log(1 - p + 1e-12))

木を足していく部分です。木の出力に学習率 lr を掛けて足し、1 本足すごとに検証用のデータでの損失を記録します。bins はヒストグラム法のビンの数です。

def fit(X, y, Xv, yv, n_trees, lr, depth=3, bins=None):
    thresholds = None
    if bins:
        qs = np.linspace(0, 1, bins + 1)[1:-1]
        thresholds = [np.unique(np.quantile(X[:, j], qs)) for j in range(X.shape[1])]
    f, fv, hist = np.zeros(len(y)), np.zeros(len(yv)), []
    for _ in range(n_trees):
        p = 1 / (1 + np.exp(-f))
        tree = build_tree(X, p - y, p * (1 - p), depth, thresholds=thresholds)
        f += lr * predict_tree(tree, X)
        fv += lr * predict_tree(tree, Xv)
        hist.append(logloss(yv, fv))
    return np.array(hist)

1 階微分だけの場合と比べる

h をすべて 1 にすると、葉の値は「勾配の平均の逆向き」になり、2 階微分を使わない最初の勾配ブースティングに近い形になります。同じ学習率 0.3 で比べます。

def fit_first_order(X, y, Xv, yv, n_trees, lr, depth=3):
    """2 階微分を使わず、勾配を 2 乗誤差で当てる（初期の勾配ブースティング）"""
    f, fv, hist = np.zeros(len(y)), np.zeros(len(yv)), []
    for _ in range(n_trees):
        p = 1 / (1 + np.exp(-f))
        tree = build_tree(X, p - y, np.ones(len(y)), depth, lam=0.0)  # h = 1 なら葉の値は勾配の平均の逆向き
        f += lr * predict_tree(tree, X)
        fv += lr * predict_tree(tree, Xv)
        hist.append(logloss(yv, fv))
    return np.array(hist)

rng = np.random.default_rng(0)
X, y = make_data(rng, 2000)
Xv, yv = make_data(rng, 2000)
for name, hist in (("1 階微分だけ", fit_first_order(X, y, Xv, yv, 300, 0.3)),
                   ("2 階微分も使う", fit(X, y, Xv, yv, 300, 0.3, bins=64))):
    print(f"{name}: 30 本で {hist[29]:.4f}, いちばん良い本数 {hist.argmin() + 1}, 損失 {hist.min():.4f}")

実行結果:

1 階微分だけ: 30 本で 0.5510, いちばん良い本数 253, 損失 0.5142
2 階微分も使う: 30 本で 0.5002, いちばん良い本数 32, 損失 0.4976

2 階微分を使うと、30 本の時点ですでに 1 階微分だけの方法の最良の値（253 本で 0.5142）より損失が低くなりました。ロジスティック損失の勾配 p − y は −1〜1 の範囲に収まるので、勾配の平均をそのまま足すと 1 歩が小さすぎます。h で割ると、確率が 0.5 付近のところでは 1 歩が 4 倍くらいに大きくなり、早く適切な値に近づきます。

学習率と木の本数

学習率を変えて比べる

同じデータで、学習率を 1.0・0.3・0.1 にして 300 本まで木を足し、検証用のデータでの損失を比べます。比べる目安として、データを作った本当の確率を知っているときの損失（これより下がることはふつうない）と、いつも同じ確率を答えるときの損失も計算します。

rng = np.random.default_rng(0)
X, y = make_data(rng, 2000)
Xv, yv = make_data(rng, 2000)
true_logit = 2 * np.sin(Xv[:, 0] * 1.5) + Xv[:, 1] * Xv[:, 2] + (Xv[:, 3] > 0.5) - 0.5
print("本当の確率を知っているときの損失", round(logloss(yv, true_logit), 4))
print("いつも同じ確率を答えるときの損失", round(logloss(yv, np.full(len(yv), np.log(y.mean() / (1 - y.mean())))), 4))

for lr in (1.0, 0.3, 0.1):
    hist = fit(X, y, Xv, yv, 300, lr, bins=64)
    best = hist.argmin()
    print(f"学習率 {lr}: いちばん良い本数 {best + 1:3d}, 検証の損失 {hist[best]:.4f}, 300 本での損失 {hist[-1]:.4f}")

実行結果:

本当の確率を知っているときの損失 0.4755
いつも同じ確率を答えるときの損失 0.6918
学習率 1.0: いちばん良い本数   4, 検証の損失 0.5196, 300 本での損失 0.9413
学習率 0.3: いちばん良い本数  32, 検証の損失 0.4976, 300 本での損失 0.6045
学習率 0.1: いちばん良い本数 144, 検証の損失 0.5024, 300 本での損失 0.5170

読み取れることは 3 つあります。

• 学習率 1.0 は、4 本で最良になり、そのあと急に悪くなる。300 本では、何も学習しないとき（0.6918）より悪い 0.9413 まで上がりました。1 本ごとに学習用のデータへ強く合わせすぎて、すぐに過学習します
• 学習率を下げると、最良になる本数が増える。0.3 では 32 本、0.1 では 144 本でした。最良の損失は 0.4976 と 0.5024 で、1.0 の 0.5196 よりはっきり良くなっています
• 学習率が小さいほど、本数を多めにしても悪くなりにくい。0.1 なら、最良の本数の 2 倍の 300 本まで足しても 0.5170 にとどまります

早期終了で本数を決める

木の本数は、上のように検証用のデータでの損失を見ながら、一定の本数（たとえば 50 本）続けて良くならなかったら止める 早期終了 で決めるのがふつうです（過学習と正則化のしくみ の早期終了と同じ考え方です）。実務では、学習率を 0.05〜0.1 くらいの小さめの値に固定し、本数は早期終了に任せて、ほかの調整の値を探すことが多いです。

学習率を小さくするほど本数が増えて学習と予測に時間がかかるので、最後に学習率をさらに下げて本数を増やし、少しだけ成績を上げる、という使い方もします。

ヒストグラム法：しきい値の候補を減らす（LightGBM）

ビンにまとめても精度はほとんど落ちない

上の build_tree は、分ける特徴としきい値の組み合わせをすべて試しています。データが n 件あると、特徴ごとに n − 1 個のしきい値の候補があり、データが数百万件になると、この探索が学習時間のほとんどを占めます。

LightGBM（Ke ら, 2017）が広めた ヒストグラム法 は、学習の前に特徴の値を数十〜数百の ビン に分けておき、ビンの境目だけをしきい値の候補にします。各ビンの g と h の合計（ヒストグラム）を作れば、分割の利得はビンの数だけの計算で求められます。

ビンの数を変えて、150 本・学習率 0.1 の損失を比べます。ビンの境目は、学習用のデータの分位点（データを件数が等しくなるように分ける点）にしています。

for bins in (None, 256, 64, 16):
    hist = fit(X, y, Xv, yv, 150, 0.1, bins=bins)
    n_cand = len(np.unique(X[:, 0])) - 1 if bins is None else bins - 1
    print(f"ビンの数 {str(bins or '分けない'):>4}: 1 つの特徴あたりの候補 {n_cand:4d}, 150 本での検証の損失 {hist[-1]:.4f}")

実行結果:

ビンの数 分けない: 1 つの特徴あたりの候補 1999, 150 本での検証の損失 0.5081
ビンの数  256: 1 つの特徴あたりの候補  255, 150 本での検証の損失 0.5032
ビンの数   64: 1 つの特徴あたりの候補   63, 150 本での検証の損失 0.5030
ビンの数   16: 1 つの特徴あたりの候補   15, 150 本での検証の損失 0.5175

しきい値の候補を 1999 個から 63 個まで減らしても、損失は悪くなっていません（このデータでは少し良くなっています）。細かすぎるしきい値は、学習用のデータのノイズに合わせた分け方になりやすく、ビンにまとめることが軽い正則化として働くことがあるためです。ただし、16 個まで減らすと、sin の形を細かく表しきれずに損失が悪くなりました。LightGBM のビンの数の初期値は 255 です。

このコードは説明のためにビンの境目だけを候補にしていて、並べ替えは毎回しているので、速さは比べていません。実際のライブラリは、特徴の値を最初に 1 回だけビンの番号（1 バイトの整数）に変えておき、並べ替えをせずにヒストグラムを足し上げることで速くしています。

そのほかの高速化の工夫

LightGBM と XGBoost には、ほかにも次のような工夫があります。

工夫	内容
葉ごとの成長（leaf-wise）	深さをそろえて育てるのではなく、利得がいちばん大きい葉から順に分ける。同じ葉の数で損失が下がりやすいが、深くなりすぎるので num_leaves で葉の数を制限する
ヒストグラムの引き算	親のヒストグラムから小さい方の子のヒストグラムを引けば、大きい方の子のヒストグラムになる。計算が半分で済む
GOSS	勾配の大きいデータは残し、小さいデータは一部だけ使う。勾配の小さいデータは、すでによく当たっているため
EFB	同時に 0 以外の値を取らない特徴（one-hot の列など）を 1 つにまとめ、特徴の数を減らす
欠損値の向きの学習	欠損したデータを左右どちらに送ると利得が大きいかを分割ごとに学習する

カテゴリ変数とターゲットの漏れ（CatBoost）

カテゴリを数に置き換える方法

「都道府県」「商品の種類」のような カテゴリ変数 は、そのままでは「しきい値以下かどうか」で分けられません。代表的な扱い方は 3 つです。

方法	内容	弱点
one-hot	カテゴリごとに 0/1 の列を作る	種類が多いと列が増え、木が 1 回の分割で 1 つのカテゴリしか切り出せない
ラベルの番号	カテゴリに 0, 1, 2, … の番号を振る	番号の大小に意味がないので、分け方が不自然になる
ターゲット統計	カテゴリごとの目的変数の平均（「この都道府県の購入率」）に置き換える	そのまま計算すると、目的変数の情報が漏れて過学習する

そのまま平均を取ると何が漏れるのか

ターゲット統計を全データで計算すると、各行の値に その行自身の正解 が混ざります。極端な例として、1 回しか出てこないカテゴリでは、平均がその行の正解そのものになり、木はこの列だけで学習用のデータを完璧に当ててしまいます。検証用のデータや本番のデータでは、そんな値は手に入らないので、成績が大きく落ちます。このような、予測のときには使えない情報が学習に入り込むことを リーク（漏れ）と呼びます。

CatBoost（Prokhorenkova ら, 2018）は、データをランダムな順番に並べ、各行のターゲット統計を、その行より前に出てきた行だけで計算 します（順序つきのターゲット統計）。その行自身の正解は使わないので、漏れがなくなります。出てきた回数が少ないカテゴリでは、全体の平均に近づける補正（事前分布）も入れます。CatBoost は同じ考え方を勾配の計算にも使っていて（順序つきブースティング）、木を作るのに使ったデータで勾配を計算することによるずれも小さくしています。

主な調整の値

3 つのライブラリで名前は少しずつ違いますが、調整する値はほぼ共通です。

調整の値	XGBoost / LightGBM での名前	大きくすると
学習率	learning_rate	少ない本数で学習が進むが、過学習しやすい
木の本数	n_estimators（早期終了で決める）	学習用のデータに合っていく。多すぎると過学習
木の大きさ	max_depth / num_leaves	特徴どうしの複雑な組み合わせを表せるが、過学習しやすい
葉の最小の大きさ	min_child_weight / min_child_samples	少ないデータだけの葉ができにくくなり、過学習しにくい
L2 正則化	reg_lambda（λ）	葉の値が小さくなり、過学習しにくい
行の抽出	subsample / bagging_fraction	1 より小さくすると、木ごとにデータの一部だけを使い、木どうしが似にくくなる
列の抽出	colsample_bytree / feature_fraction	1 より小さくすると、木ごとに特徴の一部だけを使う

調整の値を探すときは、ベイズ機械学習のしくみ で説明したベイズ最適化がよく使われます。評価は、過学習と正則化のしくみ で説明した交差検証で行います。

ニューラルネットワークとの使い分け

画像・音声・文章のように、生のデータから特徴を見つける必要がある問題では、ニューラルネットワークが圧倒的に強くなりました。一方、列ごとに意味がはっきりした表の形のデータでは、2022 年の比較の研究（Grinsztajn ら）でも、木を使う手法がニューラルネットワークより良い成績を出すことが多いと報告されています。理由としては、次のような点が挙げられています。

• 表のデータには、関係のない列が多く混ざっていることが多い。木は分割に使わない列を無視できる
• 「年齢が 65 歳以上かどうか」のような、急に変わる関係を、木はしきい値 1 つで表せる。ニューラルネットワークはなめらかな関数を作りやすい
• 列ごとに単位や分布がばらばらでも、木は大小の順番しか見ないので、前処理がほとんどいらない

勾配ブースティングの手法の流れ

この記事で紹介した手法を年代順に並べます。

年	手法・出来事	ポイント
1990	ブースティングの理論（Schapire）	当て推量より少し良いだけの学習器を組み合わせれば、強い学習器が作れる
1995	AdaBoost	間違えたデータの重みを上げて、次の学習器に重点的に学習させる
2001	勾配ブースティング（Friedman）	損失の勾配を次の木で当てる。いろいろな損失に使える
2002	確率的勾配ブースティング	木ごとにデータの一部だけを使い、精度と速さを上げる
2016	XGBoost	2 階微分の近似と正則化を式に入れ、並列化して速くした
2017	LightGBM	ヒストグラム法・葉ごとの成長・GOSS・EFB で大きなデータを速く学習する
2018	CatBoost	順序つきのターゲット統計で、カテゴリ変数をリークなしに扱う

まとめ

• 勾配ブースティングは、損失の勾配を次の木で当てて足していく。分類では木の出力の合計を対数オッズとして扱う
• XGBoost は損失を 2 次式で近似し、葉の値を −G / (H + λ)、分割の利得を G² / (H + λ) の増え方で決める。2 階微分を使うと、少ない本数で損失が下がる
• 学習率を下げると、最良になる本数は増えるが、損失は良くなりやすく、本数を多めにしても悪くなりにくい。本数は早期終了で決める
• ヒストグラム法は、しきい値の候補をビンの境目に限る。数十〜数百のビンなら精度はほとんど落ちない
• カテゴリ変数をターゲット統計で置き換えるときは、その行自身の正解が混ざるリークに注意する。CatBoost は前の行だけで統計を計算して防ぐ

参考

• R. E. Schapire, "The Strength of Weak Learnability", Machine Learning 1990
• Y. Freund and R. E. Schapire, "A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting", Journal of Computer and System Sciences 1997
• J. H. Friedman, "Greedy Function Approximation: A Gradient Boosting Machine", The Annals of Statistics 2001
• J. H. Friedman, "Stochastic Gradient Boosting", Computational Statistics & Data Analysis 2002
• T. Chen and C. Guestrin, "XGBoost: A Scalable Tree Boosting System", KDD 2016（arXiv:1603.02754）
• G. Ke et al., "LightGBM: A Highly Efficient Gradient Boosting Decision Tree", NeurIPS 2017
• L. Prokhorenkova et al., "CatBoost: unbiased boosting with categorical features", NeurIPS 2018（arXiv:1706.09516）
• L. Grinsztajn, E. Oyallon and G. Varoquaux, "Why do tree-based models still outperform deep learning on typical tabular data?", NeurIPS 2022 Datasets and Benchmarks Track（arXiv:2207.08815）
• LightGBM のドキュメント（Parameters）
• XGBoost のドキュメント（Introduction to Boosted Trees）