最近、XGBoostやLightGBMなどがKaggleではよく使用されています。
これらの手法は非常に強力ですが、上手く動かすためには多数のパラメータを適切に設定する必要があります。
各パラメータの働きを改めて見直すために、スクラッチから決定木アルゴリズムを作成してみました。
その中で今回は、決定木アルゴリズム関係でよく使用される単語についてまとめました。（実際の実装などは今後書いていく予定…）
ちなみに、この度勉強に利用したのは「作ってわかる!アンサンブル学習アルゴリズム入門（坂本俊之／著）」です。
誤字が気になりましたが、本当に単純な決定木アルゴリズムから勾配ブースティングまで、非常にわかりやすくまとまっている良本だと感じました。
一方で、XGBoostやLightGBMの細かい実装を知るには不十分なので、それらの詳細を知りたい場合は自分で勉強する必要があります。
下記の説明の順序はテキトウです。
データの分割基準（Splitting Criteria）
決定木の各ノードで行われるデータ分割において、分割基準に利用される指標です。
使用される指標として有名なのは、ジニ不純度（Gini Impurity）、情報利得（Information gain）、分散（Variance）でしょうか。
データを分割するときには、ノード内のデータが上手く分類できる条件を探すことになりますが、上手いか下手かを決めるのがこれらの指標です。
こちらのサイトがよくまとまっていると思います。
https://towardsdatascience.com/the-simple-math-behind-3-decision-tree-splitting-criterions-85d4de2a75fe
ジニ不純度(Gini Impurity)
分類問題のときに使用される指標で、計算式は下記です。
$$ I_G(n) = 1 – \sum^{C}_{i}(p_i)^2 $$
(n)はノード、(C)はノード内に含まれるクラス数、(p_i)はノード(n)でのクラス(i)のデータ数の割合です。
不純度が最低になるときは (p_i=1)（ノード内のすべてのデータが同じクラスに属する）です。
一方で、不純度が最高になるときは (p_i=\frac{1}{C})（ノード内のすべてのデータが異なるクラスに属する）です。
つまり、不純度が最低のときにデータを上手く分割できていることになるので、ジニ不純度をデータの分割指標として利用するときは、分割後のノードのジニ不純度が最低になる基準を探すことになります。
情報利得（Information Gain）
こちらも、分類問題のときに使用される指標で、計算式は下記になります。
$$ I_H(n) = – \sum^{C}_{i}p(i)\log p(i) $$
各変数はジニ不純度と同様です。
こちらも、ノード内のデータがすべて同じクラスに属するときに最低値（(I_H(n)=0)）となり、ノード内のデータが全て異なるクラスに属するときに最高値（(I_H(n)=\log C)）となります。
分散（Variance）
こちらは、回帰問題に利用される指標となります。
単純に分散を求めます。
$$ V(n) = \frac{1}{N}\sum( X – \overline{X})^2 $$
(N)はノード内のデータ数で、(X)は目的変数の平均です。
ノード内のデータの目的変数がすべて同じ値のとき(V=0)、値の予測が簡単になるので、分散を利用するときには分散が小さくなる基準を探すことになります。
アンサンブル学習（Ensemble Learning）
複数の機械学習モデルを組み合わせる手法のことです。
精度の低いモデルを弱学習器と呼んだりしますが、アンサンブル学習では弱学習器を複数利用して最終的な出力を得ます。
アンサンブル学習を学ぶ上でよく現れる単語として、ブートストラップ・バギング・スタッキング・ブースティングなどが挙げられます。
ブートストラップサンプリング（Bootstrap Sampling）
訓練データからランダムにデータを取り出して、訓練データの部分集合を作り出す手法のことです。
このとき、データの重複は許されます。（手法によっては重複を禁止にすることもあります）
重複ありのランダムサンプリングではデータが偏るのではないかと思いますが、もとの訓練データ数が十分にある場合、ブートストラップによって作り出された集合の統計値はもとの訓練データの統計値に近づくことが知られています。
バギング（Bootstrap AGGregatING）
Bootstrap Aggregatingから作られた造語で、ブートストラップで作成された訓練データを用いて弱学習器を作成し、弱学習器の出力をまとめたものを最終出力とする手法です。
例えば、ブートストラップによりm個の訓練データを作成した場合、m個の弱学習器を作成します。
最終的な出力は、m個の弱学習器の足し合わせとなります。
分類問題ではm個の弱学習器の多数決等で決定し、回帰ではm個の弱学習器の出力の平均を利用します。
ランダムフォレスト（Random Forest）
バギングを利用している決定木アルゴリズムとしては、ランダムフォレストがよく知られています。
純粋なバギングでは、学習データの数が多くなるとすべての弱学習器が同じように学習されてしまい、複数の弱学習器を足し合わせる利点が失われてしまう問題点があります。
そこでランダムフォレストでは、ブートストラップで訓練データを作成する際に、使用する説明変数もランダムに決定します。
各弱学習器で使用する説明変数が異なるため、性質の異なる弱学習器を作成することが可能になり、全体としての汎化性能が高まります。
また、汎化性能を高めるために、決定木のノード数に制限を設ける手法なども導入されています。
ブースティング（Boosting）
弱学習器を逐次的に作成していく手法のことです。
バギングでは弱学習機は並列的に作成されましたが、ブースティングでは逐次的にモデルが作成されます。
ブースティングを利用した有名な決定木アルゴリズムとして、AdaBoostや勾配ブースティングが挙げられます。
また、LightGBMやXGBoostなども有名ですね。
AdaBoost
訓練データ内にある学習が困難なデータを重要視（重み付け）することで、全体として学習器の性能を高めることを目指した手法です。
この手法でポイントとなるのは、各弱学習器の性能を評価する損失関数（微分可能関数）と、学習データ一つ一つに与えられる重みです。
まず、学習データに与える重みを初期化し、１つ目の弱学習器であるモデルAをすべての訓練データから作成します。
そして、損失関数を用いて、訓練データに対するモデルAの出力と正解データからモデルの性能を評価します。
最後に、その性能をもとに学習データに与える重みを更新し、1回目の学習が終了です。
次に、２つ目の弱学習器であるモデルBを最新の重みを用いて学習します。
モデルAとモデルBの出力を足し合わせた出力と正解データから、モデルの性能を評価し、再び重みを更新します。
上記を繰り返すことで複数の弱学習器を作成し、それらの弱学習器の出力を足し合わせたものを最終的な出力とします。
勾配ブースティング（Gradient Boosting）
勾配ブースティングでは弱学習器の出力と正解データの残差を目的変数として弱学習器を作成します。
まず、１つ目の弱学習器であるモデルAがすべての訓練データ（手法により異なります）を用いて作成されます。
次に、訓練データに対するモデルAの出力と正解データから、出力の異なり具合（残差）を求めます。
２つ目の弱学習器であるモデルBは、モデルAの残差を目的変数として学習を行います。
3つ目のモデルCは、モデルAとモデルBの出力の足し合わせと正解データから計算される残差を目的変数として学習されます。
上記を繰り返す手法が、勾配ブースティングと呼ばれています。
勾配ブースティングでは最終的な汎化性能を高めるために、弱学習器を作成する際に訓練データと説明変数のランダムサンプリングが行われることもあります。
スタッキング（Stacking）
異なる機械学習手法によって作成された複数のモデルの出力を説明変数とする学習データを作成し、作成された学習データを利用して最終的なモデルを学習する手法です。
1段目に作成される学習器は、与えられた説明変数を利用して学習を行います。
2段目では、1段目に作成された学習器の出力を説明変数とするデータで学習器を作成します。
汎化性能を高めるため、学習データを複数に分割しそれぞれのデータに対して学習器を作成する手法なども提案されています。
また、層を増やして数段重ねることもあります。
XGBoost
主要なGradient Boosting Decision Tree(GBDT)のアルゴリズムになります。
決定木の学習ではノードでのデータ分割に計算コストがかかります。
この辺を上手に解決しようとしたのがこちらの手法になります。
XGBoostと下記のLightGBMは別の記事にまとめる予定です。
LightGBM
XGBoostより後発のGBDTのアルゴリズムです。
後発＋Microsoftが管理しているということもあり、最近はXGBoostよりも人気かもしれません。
GBDT + Gradient-based One-side Sampling(GOSS) + Exlusive Feature Bunding(FEB)による手法と言われています。
簡単にいうと、GOSSは訓練データの分布を調整する手法で、FEBはデータ分割の処理を効率的に行う手法です。
枝刈り（pruning）
決定木のサイズ削減や、過学習の抑制のために使用される手法です。
ノードに枝が一本しかついていないときはノードを削除することや、一定の基準を満たさない分類条件を削除するなどの手法が存在します。
まとめ
簡単にまとめようと思っていたら、結構な文字数になってしまいました。
いくつかの項目については、別記事で深堀りしたと思います。
