テイラー展開と勾配ブースティング(XGBoost)についての考察
上記の記事で勾配ブースティング(Gradient Boosting)について取り扱ったのですが、関連でXGBoostの論文を確認した際に2次のテイラー展開(the second order method)が用いられており、残差を予測するだけなので不要ではないかと疑問が生じたため諸々を調べてまとめてみることにしました。
[1603.02754] XGBoost: A Scalable Tree Boosting System
結論から述べると、lossの設定次第であり、最尤法(MLE; Maximum Likelihood Estimation)と同様の文脈で理解すると良いというものでした。この記事の内容を理解するにあたっては、最尤法の理解がある方が望ましいので、途中でわからなくなった方は下記などを参照してみてください。
https://www.amazon.co.jp/dp/B08FYMTYBW
以下、当記事の目次になります。
1. XGBoost論文におけるテイラー展開
2. 関連の論文の確認(Gradient Boostingなど)
3. まとめ
1. XGBoost論文におけるテイラー展開
1節ではXGBoostの論文におけるテイラー展開について確認を行います。
[1603.02754] XGBoost: A Scalable Tree Boosting System
XGBoostの論文のSection2の冒頭の記載ではGradient Boosting関連の論文のAuthorのFriedmanの"second order method"に簡単な改善を試みたと記載されています。
（中略）
大体の計算の流れは上記のようにlossを学習器の和(Boostingによってそれまで得られている学習器の総和)などを用いて表現した際に、新しく加える学習器をとした際にこれを2次のテイラー展開を行って、(5)式などで新しく加える学習器のパラメータを解析的に求める（ここでは回帰木のため葉の持つ重みを計算する）というのが主な流れです。
勾配ブースティング(Gradient Boosting)を理解する - Liberal Art’s diary
ここで疑問が生じるのが、上記の勾配ブースティングの記事のように残差をフィッティングする方がパラメータを解析的に求めることができるし話の流れ的にも直感的にもわかりやすいのではないかということです。残差を用いればそれまでの学習器が予測できていないところを次の学習器で予測するというシンプルな理解ができるのにも関わらず、XGBoostの論文ではなぜ残差をそのまま用いずに複雑なテイラー展開を用いて計算を行うのでしょうか。
その答えは「lossの設定にあり、最尤法をベースとする様々な確率モデリングの手法を統一的に取り扱うためではないか」という仮説を立てて関連の論文について調べましたので、詳しくは2節でご紹介できればと思います。
2. 関連の論文の確認(Gradient Boostingなど)
2節では1節でまとめた内容を受けてGradient Boostingについての論文などの確認を行います。1節で取り扱ったXGBoostで残差を用いた学習ではなく、テイラー展開を行った理由ですが、Gradient Boostingの論文である"J. Friedman. Greedy function approximation: a gradient boosting machine., 2001."のAlgorithm 1とAlgorithm 2を見比べるとわかりやすいです。
https://statweb.stanford.edu/~jhf/ftp/trebst.pdf
上記が論文のAlgorithm 1とAlgorithm 2ですが、それぞれの3行目に着目するとAlgorithm 1では勾配の計算で表現されている式がAlgorithm 2では残差によって計算が行われています。Algorithm 2については残差を目的変数として学習させることでBoosting（逐次的な学習器の構築）を行うことができますが、Algorithm 1ではlossの設定の仕方により計算が複雑になる可能性があることも考慮してXGBoostではテイラー展開を導入したと考えて良いかと思います。1節でも言及したXGBoostの論文で"second order method"として参照した"J. Friedman et al. Additive logistic regression: a statistical view of boosting., 2000."では下記のような記載がなされています。
https://people.csail.mit.edu/torralba/courses/6.869/lectures/lecture6/boosting.pdf
論文のAbstractではロジスティック回帰を行うにあたってベルヌーイ分布を元にした最尤法を用いた(maximum Bernoulli likelihood as a criterion)と記載があります。最尤法について考えた際に目的変数が正規分布に従う場合は最小二乗法になるので残差を用いるで大丈夫なのですが、ロジスティック回帰などでは式が少々複雑になるため"second order method"を用いた例として考えて良さそうです。（この論文はGradient Boostingより前の論文のようなので、AdaBoostの流れで"second order method"を論じていることに注意が必要ですが、目的変数の確率分布に正規分布を仮定できない場合は計算が複雑になることには変わりないのでここでは流すことにします。）
ここまでの流れから「XGBoostにおいてテイラー展開を用いることで計算効率の向上が可能なのはlossに二乗和誤差を設定する以外のケースではないだろうか」という仮説を考えることができます。すなわち通常の回帰分析であれば残差を元に決定木の構築を行うで十分ではないかということです。（XGBoost論文のSection3に記載のあるSplit Findingのアルゴリズムではテイラー展開の項を用いて議論を行っているなどもう少し読み込みが必要のため、当記事ではあくまで指摘にとどめておこうと思います。とはいえ、Split Finding自体はある程度独立して用いることができる考え方であると思われるので、なんとなく問題設定によってはテイラー展開は冗長なのではという印象も受けます。テイラー展開は全てのケースに対しての計算効率の向上ではなく、様々なlossに対して汎用的なアルゴリズムを提供することを目的としたのではないかというのが今のところの認識です。）
3. まとめ
1節、2節でXGBoostの論文におけるテイラー展開についてGradient Boosting関連の論文の記載などから考察を行いました。3節ではまとめとして誤差関数(loss)と最尤法について改めて考察してみます。
誤差関数については手法問わず最尤法から導出されることが多いですが、基本的には目的関数の性質によって決められることが多いです。たとえばオーソドックスな回帰問題であれば正規分布を前提とすることが多いので二乗和誤差を用いることが多いし、ロジスティック回帰であればクロスエントロピーのような誤差関数になります。また、正則化についてもパラメータの初期の分布を与えることで導出できるなどもあるため、この辺は問題設定にかなり依存します。
勾配ブースティングの文脈でどのようなlossが良いのかについてはもう少し調査や考察が必要のため、当記事では「XGBoostにおいてテイラー展開を用いることで計算効率の向上が可能なのはlossに二乗和誤差を設定する以外のケースではないだろうか」という仮説を提示するにとどめ、まとめとしたいと思います。
