MLエンジニアへの道 #11 - XGBoost

ML

Last Edited: 8/15/2024

このブログ記事では、XGBoostの仕組みについて紹介します。

ML

XGBoost（EXtreme Gradient Boostingの略）は、現在最も人気があり、強力な機械学習アルゴリズムと言っても過言ではありません。 XGBoostは高速で、汎用性が高く、実装も簡単であり、これらはすべて機械学習アルゴリズムに求められる望ましい特性です。本記事では、XGBoostの動作の仕組みと、 なぜそれが非常に効果的であるかを紹介します。

XGBoost

XGBoostのアルゴリズムは以下のように定義できます：

入力: Data (xi,yi)I=1n{(x_i, y_i)}_{I=1}^{n} と微分可能なコスト関数 L(y,F(x))L(y, F(x))

ステップ1: 定数値F0(x)F_0(x)でモデルを初期化します。

ステップ2: m=1m=1からMMまで:

  • rim=−[∂L(yi,F(xi))∂F(xi)]F(x)=Fm−1(x)r_{im} = -[\frac{\partial L(y_i, F(x_i))}{\partial F(x_i)}]_{F(x) = F_{m-1}(x)}を i=1,…,ni = 1,…,nに対して計算する
  • rimr_{im}の値に適合する木を構築し、端末領域(リーフノード) RjmR_{jm}をj=1,…,Jmj = 1, … , J_m に対して作成する
  • j=1,…,Jmj = 1, … , J_m に対してOjm=arg min⁡O∑xi∈RijL(yi,Fm−1(xi)+O)+12λO2O_{jm} = \argmin_{O} \sum_{x_i \in R_{ij}} L(y_i, F_{m-1} (x_i) + O) + \frac{1}{2}\lambda O^2を計算する
  • Fm(x)=Fm−1(x)+ν∑j=1JmOmI(x∈Rjm)F_m (x) = F_{m-1} (x) + \nu \sum_{j=1}^{J_m} O_m I(x \in R_{jm}) を更新する

これらのステップは通常の勾配ブーストの定義と非常に似ていますが、ここで明示されていない定義や実装にいくつかの違いがあります。

正則化

通常の勾配ブーストとXGBoostの最も顕著な違いは正則化です。両方のブースティング手法で木を構築した後に行われる剪定に加えて、 XGBoostはコスト関数に正則化項を追加してL2正則化を適用します。

L(y,F(x)+Ovalue)reg=[12(y−(F(x)+Ovalue))2]+12λOvalue2L(y,pF(x)+Ovalue)clf=−[ylog(pF(x)+Ovalue)+(1−y)log(1−(pF(x)+Ovalue))]+12λOvalue2 L(y, F(x) + O_{value})_{reg} = [\frac{1}{2} (y-(F(x)+O_{value}))^2] + \frac{1}{2} \lambda O_{value}^2 \\ L(y, p_{F(x)} + O_{value})_{clf} = -[y log(p_{F(x)}+O_{value}) + (1-y) log(1-(p_{F(x)}+O_{value}))] + \frac{1}{2} \lambda O_{value}^2

（XGBoostでは、出力値はγ\gammaの代わりにOvalueO_{value}と表記され、γ\gammaは剪定のためのペナルティ率として使用されます。）この正則化項は、 コスト関数の微分を取るときに計算を簡素化するために2で割られています。この正則化項は、木の構築方法や出力値の計算方法に影響を与えます。XGBoostの 回帰における出力値を計算して、違いを観察してみましょう。

∂∂Ovalue∑xi∈RijL(yi,Fm−1(xi)+Ovalue)=∑xi∈Rij(yi−(Fm−1(xi)+Ovalue))+λOvalue∑xi∈Rij(yi−Fm−1(xi)+Ovalue)+λOvalue=0(R+λ)Ovalue=∑xi∈Rij(yi−Fm−1(xi))Ovalue=∑xi∈Rij(yi−Fm−1(xi))(R+λ) \frac{\partial}{\partial O_{value} } \sum_{x_i \in R_{ij}} L(y_i, F_{m-1}(x_i) + O_{value}) = \sum_{x_i \in R_{ij}} (y_i-(F_{m-1}(x_i)+O_{value})) + \lambda O_{value} \\ \sum_{x_i \in R_{ij}} (y_i- F_{m-1}(x_i) + O_{value}) + \lambda O_{value} = 0 \\ (R+\lambda) O_{value} = \sum_{x_i \in R_{ij}} (y_i- F_{m-1}(x_i)) \\ O_{value} = \frac{\sum_{x_i \in R_{ij}} (y_i- F_{m-1}(x_i))}{(R+\lambda)}

ここでRRは葉における残差の数です。 勾配ブーストのように単に残差の平均を取るのではなく、XGBoostは正則化率λ\lambdaを分母に追加することで、 正則化率が増加するにつれて出力値が小さく調整されるようにしています。交差検証を使用して、最適な結果を得るために正則化率を調整できます。

分類の場合も同様の正規化による効果が見られますが、コスト関数に対してテイラー近似が行われるため、数学的には少し複雑になります。

∑xi∈RijL(yi,Fm−1(xi)+Ovalue)≈∑xi∈Rij[L(yi,Fm−1(xi))+ddFL(yi,Fm−1(xi))Ovalue+12ddF2L(yi,Fm−1(xi))Ovalue2]+12λOvalue2∂∂Ovalue∑xi∈RijL(yi,Fm−1(xi)+Ovalue)≈∑xi∈RijddFL(yi,Fm−1(xi))+ddF2L(yi,Fm−1(xi))Ovalue+λOvalue∑xi∈RijddFL(yi,Fm−1(xi))+ddF2L(yi,Fm−1(xi))Ovalue+λOvalue=0Ovalue=−∑xi∈RijddFL(yi,Fm−1(xi))∑xi∈RijddF2L(yi,Fm−1(xi))+λ \sum_{x_i \in R_{ij}} L(y_i, F_{m-1} (x_i) + O_{value}) \approx \sum_{x_i \in R_{ij}} [L(y_i, F_{m-1} (x_i)) + \frac{d}{dF} L(y_i, F_{m-1} (x_i))O_{value} + \frac{1}{2} \frac{d}{dF^2} L(y_i, F_{m-1} (x_i))O_{value}^2] + \frac{1}{2} \lambda O_{value}^2 \\ \frac{\partial}{\partial O_{value}} \sum_{x_i \in R_{ij}} L(y_i, F_{m-1} (x_i) + O_{value}) \approx \sum_{x_i \in R_{ij}} \frac{d}{dF} L(y_i, F_{m-1} (x_i)) + \frac{d}{dF^2} L(y_i, F_{m-1} (x_i)) O_{value} + \lambda O_{value} \\ \sum_{x_i \in R_{ij}} \frac{d}{dF} L(y_i, F_{m-1} (x_i)) + \frac{d}{dF^2} L(y_i, F_{m-1} (x_i)) O_{value} + \lambda O_{value} = 0 \\ O_{value} = - \frac{\sum_{x_i \in R_{ij}} \frac{d}{dF} L(y_i, F_{m-1} (x_i))}{\sum_{x_i \in R_{ij}} \frac{d}{dF^2} L(y_i, F_{m-1} (x_i))+\lambda}

前の記事で計算した通り、コスト関数の一次および二次導関数はそれぞれy−py-pおよびp(1−p)p(1-p)であることから、上記を次のように書き換えることができます：

Ovalue=−∑xi∈Rijyi−pFm−1(xi)∑xi∈RijpFm−1(xi)(1−pFm−1(xi))+λ O_{value} = - \frac{\sum_{x_i \in R_{ij}} y_i - p_{F_{m-1}(x_i)}}{\sum_{x_i \in R_{ij}} p_{F_{m-1}(x_i)}(1-p_{F_{m-1}(x_i)})+\lambda}

XGBoostが回帰と分類の両方で、ターミナル領域の出力値を計算する際に正則化率λ\lambdaを分母に追加することを確認できます。

木の構築

コスト関数に正則化項を追加することで、木の構築方法にも影響があります。分岐の質を評価する際、XGBoostは類似度スコア(Similarity Score) と呼ばれる尺度を使用します。これは、各リーフの最適な出力値を選んだときのコストに相当します。回帰の場合、コスト関数と出力値は以下のようになります。

L(y,F(x)+Ovalue)reg=[12(y−(F(x)+Ovalue))2]+12λOvalue2Ovalue=∑xi∈Rij(yi−Fm−1(xi))(R+λ) L(y, F(x) + O_{value})_{reg} = [\frac{1}{2} (y-(F(x)+O_{value}))^2] + \frac{1}{2} \lambda O_{value}^2 \\ O_{value} = \frac{\sum_{x_i \in R_{ij}} (y_i- F_{m-1}(x_i))}{(R+\lambda)}

OvalueO_{value}をコスト関数に代入して式を整理すると（詳細はここでは示しませんが、自分で試してみることをお勧めします）、次のようになります。

L(y,F(x)+Ovalue)reg=12∑xi∈Rij(yi−Fm−1(xi))2−(∑xi∈Rij(yi−Fm−1(xi)))2R+λ L(y, F(x) + O_{value})_{reg} = \frac{1}{2}\sum_{x_i \in R_{ij}}(y_i - F_{m-1}(x_i))^2 - \frac{(\sum_{x_i \in R_{ij}} (y_i- F_{m-1}(x_i)))^2}{R+\lambda}

コスト関数を最小化する際には、第2項を最小化することで自動的に第1項も最小化されるため（第1項を計算するのは高コストで冗長なので、コストを最小化するために計算する必要はありません）、 第2項を類似度スコアとして使用します。

Similarityscore=(∑xi∈Rij)2R+λ Similarity_{score} = \frac{(\sum_{x_i \in R_{ij}})^2}{R+\lambda}

回帰の場合、類似度スコアは、リーフ内の残差の和の二乗を残差の数と正則化率で割ったものになります。コスト関数が負の形で定義されているため、 最小値ではなく最大値を選んで分岐を決定します。許可された最大のリーフ数に達するか、類似度スコアの改善が見られない場合に、木の構築を停止します。

分類でも同様の方法で類似度スコアを計算できます。

∑xi∈RijL(yi,Fm−1(xi)+Ovalue)≈∑xi∈Rij[L(yi,Fm−1(xi))+ddFL(yi,Fm−1(xi))Ovalue+12ddF2L(yi,Fm−1(xi))Ovalue2]+12λOvalue2Ovalue=−∑xi∈Rijyi−pFm−1(xi)∑xi∈RijpFm−1(xi)(1−pFm−1(xi))+λL(y,F(x)+Ovalue)clf≈∑xi∈RijL(yi,Fm−1(xi))−12(∑xi∈Rij(yi−Fm−1(xi)))2∑xi∈RijpFm−1(xi)(1−pFm−1(xi))+λ \sum_{x_i \in R_{ij}} L(y_i, F_{m-1} (x_i) + O_{value}) \approx \sum_{x_i \in R_{ij}} [L(y_i, F_{m-1} (x_i)) + \frac{d}{dF} L(y_i, F_{m-1} (x_i))O_{value} + \frac{1}{2} \frac{d}{dF^2} L(y_i, F_{m-1} (x_i))O_{value}^2] + \frac{1}{2} \lambda O_{value}^2 \\ O_{value} = - \frac{\sum_{x_i \in R_{ij}} y_i - p_{F_{m-1}(x_i)}}{\sum_{x_i \in R_{ij}} p_{F_{m-1}(x_i)}(1-p_{F_{m-1}(x_i)})+\lambda} \\ L(y, F(x) + O_{value})_{clf} \approx \sum_{x_i \in R_{ij}} L(y_i, F_{m-1} (x_i)) - \frac{1}{2} \frac{(\sum_{x_i \in R_{ij}} (y_i- F_{m-1}(x_i)))^2}{\sum_{x_i \in R_{ij}} p_{F_{m-1}(x_i)}(1-p_{F_{m-1}(x_i)})+\lambda}

回帰と同様に、コストを最小化する際に第1項を最小化する必要がないため、第2項を使用して、それを反転させたものが分類の類似度スコアになります。 （また、第2項を2倍するのは、相対的なコストだけを気にするためです。）

Similarityscore=(∑xi∈Rij(yi−Fm−1(xi)))2∑xi∈RijpFm−1(xi)(1−pFm−1(xi))+λ Similarity_{score} = \frac{(\sum_{x_i \in R_{ij}} (y_i- F_{m-1}(x_i)))^2}{\sum_{x_i \in R_{ij}} p_{F_{m-1}(x_i)}(1-p_{F_{m-1}(x_i)})+\lambda} \\

分類の類似度スコアは、「残差」の和の二乗を、以前に予測された確率と1からそれを引いた値の積に正則化率を加えたもので割ったものとなります。

木を剪定する際には、全ての子ノードの類似度スコアと親ノードの類似度スコアの差、ゲイン(Gain)、とペナルティγ\gammaを比較し、ゲインが γ\gammaより小さい場合に木を剪定します。λ\lambdaが高いと類似度スコアとゲインが低くなるため、λ\lambdaは出力値を小さくすることで正則化 するだけでなく、剪定も手助けします。

大規模データセットとの互換性

正則化や独自のツリー構築がモデルの性能に寄与していますが、それだけではXGBoostの人気を十分に説明できません。XGBoostが人気なのは、主に大規模でスパース なトレーニングデータセットに対応するための多くの最適化が施されているからです。データセットが大きい場合、XGBoostはそれをランダムに選ばれた特徴量と行を 含むブロックに分割し、最良の木の分岐を並列で見つけます。(並列学習)

全ての分岐の候補をテストする代わりに、加重分位点だけをテストします。（加重分位点スケッチ）分類の場合、重みは pFm−1(x)(1−pFm−1(x))p_{F_{m-1}(x)}(1-p_{F_{m-1}(x)})で計算され、以前に予測された確率が0.5に近いデータの周りに小さい分位点が細かく描かれるようにしています。 （回帰の重みは均一です。）

スパースなデータセットには多くの欠損値が含まれることが多く、他の機械学習アルゴリズムはそのようなデータに対応しておらず、前処理が必要です。しかし、 大規模なデータセットではこの前処理が大変になります。XGBoostは、欠損値が左側のノードに割り当てられた場合と右側のノードに割り当てられた場合の ゲインを計算し、どちらの枝にそれらを割り当てるかを決定することで、前処理を行わずに欠損値に対応します。（スパース対応分岐探索）

また、大規模なデータセットでの使用を可能にするため、メモリ使用の最適化も行います。例えば、出力値やゲインなど、頻繁に使用される重要なデータはメモリへのアクセスが最も速い CPUキャッシュに格納されます。（キャッシュ対応アクセス）適度に使用されるデータはRAMに格納され、ディスクストレージ内に格納される他のデータへのアクセスは非常に遅いため、 圧縮とシャーディング（圧縮ブロックを複数のディスクに割り当てる）を活用して可能な限り高速にしています。（アウトオブコア計算）

結論

XGBoostは、正則化、独自の木の構築、並列学習、加重分位点スケッチ、スパース対応分岐探索、キャッシュ対応アクセス、アウトオブコア計算を活用して、 あらゆる側面を最適化し、可能な限り高速で高性能にするために、勾配ブーストを極限まで最適化しています。大規模で複雑でスパースなデータを扱えるため、 前処理が少なくて済みます。

また、線形回帰やSVMのように基底関数やカーネルを選ぶ必要がないため、データに関する背景知識が少なくて済み、専門家とのコミュニケーションの労力も 削減されます。これが、XGBoostが高性能であるだけでなく、多くの業界でデータサイエンティストに非常に人気がある理由です。XGBoostについて数学的かつ 概念的に理解できたところで、次の記事ではPythonでのXGBoostの実装方法を紹介します。

リソース

TOPに戻る↑