XGBoostの概要
XGBoostの凄さに最近気がついたので、もうちょっと詳しく知りたいと思って以下の論文を読みました。
XGBoost: A Scalable Tree Boosting System
せっかくなので、簡単にまとめてみたいと思います。。。と思っていたら結構な量になってしいました。
何か間違い等がありましたらコメントをしていただくか、@kefism へ連絡をしてくださると嬉しいです。
XGBoostとは
基本的に内部で行われていることは決定木を複数個作るということです。しかし、その作り方に特徴があります。
ここで記号を定義しておきましょう。
説明変数を次元として、目的変数を、とします。ここではデータの数です。またデータに対する予測値をとします。
まず決定木を1つ構築します。するとその決定木を使用して予測ができるようになります。1つ目の決定木から得られるデータに対する予測値をとしましょう。このときに実測値と予測値の誤差は
となります。上記の誤差は何を表しているかというと、1つ目の決定木では学習することができなかった部分、つまり説明することができなかった部分になります。が0に近い値であれば実測と予測がほほ一致しているわけですから学習ができている、つまり番目のデータについては1つの決定木で説明することができたということになりますし、0から離れた値になっていれば予測が外れているわけですから学習がうまくいっていないことになります。
さて、もしも誤差が予測できたらどうでしょうか。実測値 - 予測値 = 誤差 なわけですから、誤差がわかれば 実測値 = 予測値 + 誤差 ということで、予測値に誤差を足してあげれば実測値になります。そこでXGBoostでは、1つ目の決定木では予測できなかった部分、つまり誤差を目的変数として、2つ目の決定木を構築します。誤差を予測するモデルを作るわけです。
2つ目の決定木を構築したとします。するとその決定木を使用して誤差の予測ができるようになります。2つ目の決定木から得られるデータに対する予測値をとしましょう。つまりは、1つ目の決定木によって説明できなかった部分の予測値です。このときに実測値に対する予測値は、1つ目の決定木の予測値に2つ目の決定木の予測値、つまり予測された誤差を加えて次のようになります:
したがって、2つ目の決定木を構築し終えた時点での実測値と予測値の誤差は
となります。ここでは、2つ目の決定木を構築してもなお学習できなかった部分です。ということで、さらにを目的変数として3つ目の決定木を構築します。繰り返しになりますが、3つ目の決定木を構築し終えた後のデータに対する予測値は、1つ目の決定木で予測された値 + 1つ目の決定木では学習できなかった誤差の予測値(2つ目の決定木の結果) + 2つの決定木を構築してもなお学習できなかった誤差の予測値(3つめの決定木の結果)ということで、次のようになります:
以下、これと同じ操作を繰り返します。この繰り返す回数は分析者が決めるパラメータとなり、クロスバリデーション等でうまく決定してあげる必要があります。
このように、今までに学習したモデルの情報を使って、新たなモデルを構築することでデータの学習を進める方法をブースティング(Boosting)と呼びます。
この記事の冒頭で、XGBoostの内部で行われていることは決定木を複数個作るということと言いました。より正確にはブースティングする際に、つまり1つ前までの決定木の結果を利用して新たな決定木を作る際に、実測値と予測値との誤差がある意味で最小になるように決定木のアルゴリズムを構築したものがXGBoostです。ここで"ある意味で"といったのは、世の機械学習のアルゴリズムは目的関数を最小(または最大)にするようにアルゴリズムを構築するわけですが、まだXGBoostにおける目的関数の説明をしていないからです。
ここで強調しなければならないことは、単純に誤差を目的変数にして新たな決定木を構築するのではなく、前回までの決定木の情報を利用して新たな決定木を構築するということです。というわけで、新たな決定木を構築する際に前回までの情報をどのように利用すればよいのかという話に繋がっていきます。
決定木は、説明変数を分割していって、わかりやすく言えば樹形図を構築するアルゴリズムです。このことから前回までの情報を決定木を構築する際に利用するということは、前回までの情報を利用して説明変数の分割を最適化するということなのです。そして、後で説明しますが、その前回までの情報というのは、目的関数の勾配(Gradient)として取り出すことができます。XGBoostのGはGradientのGです。
XGBoostの定式化
さて、これから説明しなければならないことは、「どのようにして前回までの情報を使った決定木を構築するか」です。そこで今はひとまず個目の決定木そのものを抽象的に関数とします。関数 にデータ を渡すと、そのデータに対する予測値を返してくれます。今までの例だと、, , です。そしてブースティングを回行ったときの、つまり個目の決定木を構築したときの予測値は次のようになります:
まだがどのような形になっているか、つまり「前回までの情報を使った決定木はどういったアルゴリズムか」は分かりません。そこで、色々と計算をすることで、このがどういった性質を満たしていれば良いのかというのを見ていくことにします。
今までの話を数式として表現しましょう。
損失関数 を導入します。損失関数として、例えば回帰の際は多くの場合で二乗誤差
二乗誤差 = (実測値 - 予測値
が用いられますね。今回の説明では損失関数を二乗誤差と設定するのではなく、より一般的な(抽象的な)形で議論を進めていきます。損失関数は微分可能で、(例えば、実測値)と(例えば、予測値)が近ければ近いほど小さい値をとり、遠ければ遠いほど大きな値をとるように設定されます。したがって、今回の「前までの個の決定木の情報を利用して、個目の決定木をどのように構築すれば良いのか」という問題は次のように定式化されます:
この上記の式を最小にする決定木 を構築すればいいということになります。
しかし、このままだと学習に用いたデータに過剰にフィッティングしすぎることによって、予測性能が下がる過学習(over fitting)という現象が起きるでしょう。とくに上記の定式化のままではこれが顕著に現れます。なぜなら、実際に手元に手に入っている と予測の誤差が小さくなることだけを今は考えていて、未来のデータに対する予測のことを一切考慮していないからです。
そこで、次のような罰則項を定義します:
そして、上記の罰則項を損失関数に加えたものを とし、最終的に解きたい問題を以下のように設定します:
ここでは決定木を構築したときの最終ノードの数(つまり、木の大きさ)です。木の大きさを大きく設定すればするほど、過学習を起こしやすくなるのでの部分は小さくなるので目的関数 の値を小さくするように働きますが、の部分は が大きくなるように働きます。結果として、あまりの大きな木は好まれなくなります。はの大きさに対するペナルティーで、のときは過学習なんてどうでもいいから、とにかくの部分が小さくできればいい!!ということを表していて、を設定してやることで、の値が大きければ大きいほどの値が小さい、つまり小さな木が好まれるようになります。したがって は分析者が事前に決めてやる必要のあるパラメータです。
また、 は決定木 が返すことのできる値のベクトルです。例えば下図の木の場合はで、返すことのできる値はの4つということになります。つまり、は がとることのできる値の集合ということになります。
はこの決定木 が返すことのできる値の大きさ調整するパラメータです。大きなを設定すると、小さなが好まれるようになります。個目の決定木を構築し終えた後の予測値は、個目までの結果の和に個目の結果を加えたですから、 の値が小さいということは、実測値と予測値の差をちびちびと更新していくような感じになります。一方で小さなを設定すると、実測値と予測値の誤差が早く小さくなるように大胆に更新をおこなっていきます。つまり、 は新たな決定木を構築したときの更新の幅を調整するパラメータになります。ちびちびと更新すればの数が大きくなる、つまりたくさんの木を構築することになるので学習に時間がかかりますが、その分様々なパターンを表現できる一方、過学習の要因ともなります。大胆に更新をすれば早く実測値と予測値の差が小さくなっていきますが、早く差が小さくなるということは、最終的に構築される決定木の数が少なくなるということなので入力データの色々なパターンをとらえられません。バランスが大切ということで、もクロスバリデーション等で前もって分析者が決めてやる必要があります。
以上でXGBoostの定式化が完了しました。次からは、具体的に
「前までの個の結果を使って、を最小にするように個目の決定木をどのように構築すればいいのか?」
というところを見ていきます。
XGBoostのアルゴリズムの導出
個目の決定木が返すべき値
目的関数の第1項、をに関して0の周りで2次のテーラー展開を行います。
ここで , です。
最適化に関係のない項、つまりが関わっていない項を取り除いたものを とすると
となります。
ここで、最終ノード にあるデータの集合を とします。どういう事かというと、例えば は
上記の図の「ノード4」と書かれたノードの中にあるデータ たちのことです。図では添字の を省略しました。
このときに、さらに を以下のように書き直します:
ここで、2行目から3行目にかけて が となったのは、最終ノードごとについて足し上げてた後に、それらをさらに足し上げた結果と、最初から全データ(がごちゃまぜになっているときに)ついて一度に足し上げたときの結果は同じであることからわかると思います。また、同じく2行目から3行目にかけて をきちんと書き下しています。
さらに、3行目から4行目にかけて が となっているのは、データをノード にあるデータのみに制限したとき、つまり、例えばデータがノード に来たときに決定木 が返す結果は であることを思い出すと理解できると思います。
あとは共通項でくくれるものはくくって、目的関数の式変形はおしまいです。
さて、目的関数を2次形式で書くことができました。したがって、 を で微分したものを0とおいて解くと最適解 は、つまり目的関数を最小にする 個目の決定木の最終ノード が返すべき結果は
となります。
ここで , であったことを思い出します。これらはそれぞれ損失関数の1次、2次の勾配であり、また前までの 個の決定木の結果と手元にある学習データの実測値 を使って計算できる値です。 個の決定木の情報が勾配という形で 個目の決定木を構築する際に利用されています。これがXGBoostです。
勾配情報を利用した木の分岐方法
今までの話は、データが最終ノードに辿り着いた後の話でした。どのように説明変数を分岐させていけばよいのかはまだ説明していません。ですのでこの節では、勾配情報をどのように利用して説明変数を分岐していけば良いのかという話をします。
さて、前節で求めた を に代入すると は次のようになります:
この式を眺めてみると、各最終ノードにおける
の値がが大きければ大きいほど、目的関数 の値はより小さくなります。つまり、あるノードを左(L)と右(R)に分岐するときに、最も目的関数 の値が小さくなるように分岐をするためには、分岐前と分岐後の の値を比べてあげればよいということになります。
どういった比較をすれば良いのか具体的にみていきましょう。下図のように現時点で 個のノードができていて、あるノード を更に分割することを考えます。
ノード を分岐する前の目的関数を
ノード を分岐した後に左側のノードに入るデータの集合を , 右側のノードに入るデータの集合を としたときの () 分岐後の目的関数を
とします。最も目的関数 の値が小さくなるように分岐をするためには、分岐前と分岐後の目的関数の差をとって、もっとも差が大きくなるところで分岐を行えば良いということになります。つまり、
が最大になるような分岐をおこなえば良いです。より詳しく言うと、すべての説明変数 のあらゆる分割の候補のうち、最も を大きくする候補を1つ選んで、そこで分岐を行うということです。
このことをアルゴリズムとしてまとめると、次の図のようになります(論文より引用)。
しかし、すべての説明変数のあらゆる分割の候補を考えることは時間の制約もあり非常に大変なことです。そこで上図のアルゴリズムを近似したものが提案されており、精度としても問題なく使えるアルゴリズムとなっているようです。その近似アルゴリズムは次の図のようになります(論文より引用)。
今回はこのアルゴリズムを詳しく説明することはありません。是非論文を読んでみてください。
以上でXGBoostのアルゴリズムの説明は終了になります。お疲れ様でした。
XGBoostで学習するときのテクニック
XGBoostでは、過学習を防ぐために正則化以外の様々なテクニックが利用されています。
Shrinkage
XGBoostにおいて、ある決定木から返されるノード 結果は でした。この に の値をかけた を返すようにすることを返り値のShrinkageと呼びます。パラメータ と似たような働きがありますが、 は学習時に決定木が返す値の大きさを調整するパラメータでしたが、 は学習後に直接返り値 を修正するパラメータになります。
特徴量のsubsampling
ランダムフォレストでは、複数の決定木を作る際にすべての説明変数を使用するのではなく、ランダムに決められた割合で説明変数の数を選んで決定木を構築します。XGBoostでも同様に、ブースティングをする際の決定木を構築するときに、すべての説明変数を使用するのではなく、ランダムに決められた割合で説明変数の数を選んで決定木を構築します。特徴量のsubsamplingと呼ばれます。1つの決定木を構築する際に使用する特徴量の数が減るので、アルゴリズムが回るスピードも早くなります。
データのsubsampling
ブースティングをする際に 個すべてのデータを使用して決定木を構築するのではなく、ランダムに決められた割合でデータの数を選んで決定木を構築します。これをデータのsubsamplingと呼びます。1つの決定木を構築する際に使用するデータの数が減るので、アルゴリズムが回るスピードも早くなります。
最後に
簡単にまとめるつもりだったのに大作になってしまった。
疲れた