以前勉強会では飛ばしていいか、と思った14章（boostingとかアンサンブルの話）だが、やっぱやりたい気がしたので自分担当でやる事に。

という事でここに予習内容とか書いていきます。

ざっと最後まで読んでみた

comittee、adaboost、conditional mixtuer modelという内容。 決定木は思ったよりページ数無くて、mixtuer modelが多い。

gradient boostとかは無いのね。

adaboostはexponential errorからの解釈が書かれていて、ここの内容はなかなか良いが、最初のアルゴリズムの提示の方が先に出てくるのでこちらは分かりにくい。

幾つか重要な式変形が練習問題に回されているのでやっても良い気はする。

どうしよっかね。とりあえずこの本に沿ってまとめてみるか、それともboostingにフォーカスしてGBDTとかそのヒストグラムの話を掘り下げるか…

勉強会をどう進めるかはおいといて、ひとまず教科書の内容をまとめてみよう。

14.1 Bayesian model averagingとの違い

14.1では初めに、本章で扱う手法とBayesian model averagingの違いについて言及している。

結論としてはBayesian model averagingは、全部のデータがどれか一つのモデルから生成されていて（式14.6）、でもそれがどれかが分からない、データが増えればだんだんと一つに収束していく、というもの。

一方で複数のモデルをcombineする場合は、例えば式14.5の場合などでは、各データ点ごとに別々のlatent variableが考えられて、だからおのおののデータ点が別々の構成要素から生成される。

式の形は似てるけど、意味合いは違いますよ、という話っぽい。

14.2 Committees

スペルが難しいな。mもtもeも全部ダブるのね。どうでもいいが。

この節では、モデルを複数作って平均を取る、という方法を考える。（14.7） 一番簡単には、データを最初に分割して別々にトレーニングする。これをbootstrap aggregationとかbaggingと言うらしい。

14.8のようにあらわして、モデルが独立なら平均取るとエラー項が減ってく、という話をしている。 ただ普通相関があるのでこんなうまく行かないとか。そりゃそうだ。

14.3 Boosting

committeeの一種との事。 複数のモデルを組み合わせるのがcommittee、そのうち単に平均するのがbagging、順番にモデルを作り、この時前のモデルを使うのがboostingか。

この節ではadaboostの話をしている。

AdaBoostのアルゴリズム

まずp658に、アルゴリズムが載っている。 どうしてこういう式になるのか、については、次の14.3.1で解説がある。

問題設定としては、-1か1のどちらかをpredictするモデルを作る、というもの。

アルゴリズムの基本的なアイデアとしては、

  1. 間違えたデータの重みを重くしたコスト関数を使って次のモデルをトレーニングする（wと14.15式）
  2. 重み付きのデータに大して間違いの少なかったモデルを重視し、間違いが多いモデルは軽視する（アルファ）
  3. 具体的なデータの重み計算では、重視するモデルの間違いをより重く見る

という感じ。

これらの式がちょうど良い物になってるかとかはこの時点では分からない。 あくまでこういう物だ、という事だけが羅列されている。

14.3.1 exponential errorによる解釈

adaboostのアルファやwがこの形である必然性は、アルゴリズムだけを見ると良く分からない。 14.3.1はexponential errorを最小化する、という問題を考えると自然とこれらの式が出てくる、という話。

今回もターゲットは1か-1。

こんなエラーを最小化していくように、fmを追加していく事を考える。

分類器yとアルファを動かして、Eを最小化する事を考える。

ただし全体を最適化するのは難しいので、greedyに求める。 つまりm-1期までの解を前提に、m期のfだけを最適化して追加する、という事を1期から繰り返す。

この式からアルファとwmの更新の式とymの学習の式が得られる。

wmの漸化式

mを一期進めると、wmの漸化式が出てくる。ymをIndicator functionで書き直して14.26が得られて、これがwの更新の式となる。 ただしymを使ってるので、先にymをトレーニングする必要アリ。

ymのコスト関数

という事でymをトレーニングする式を考える。 上の和を、ymが正しく分類した物とそうでない物に分けると、以下のように書ける。

ymの最適化では第二項は定数なので第一項の最適化となる。これはadaboostのアルゴリズムの説明でのymの式と同じになる。（式14.15）

アルファmの計算

さらにこの式で、アルファmで微分してイコール0と置くと、

これは整理すれば式14.17になりそう。

こうして求めたfmは、もともと14.20を最小化する物だったので、この符号をpredictionで使えば良い。 これがadaboostと同じ事になる。

14.3.2 普通のError functionとの比較

このexponentialの誤差関数は、普通の誤差関数とは少し違う。14.3.2ではそれらがどう違うのか、という話をしている。

普通の誤差関数

普通の誤差関数というとロジスティック回帰の時の負の対数尤度という事になるが、これは0, 1だった。 1と-1にしたものは7.1.2でやったらしい。一応計算しておく。

尤度は

となるので、負の対数尤度は

となる。特に難しい事は無いが、0, 1のケースと違って見慣れてないので出しておかないとピンと来ないやね。

14.4 Tree-based Models

いわゆる決定木のモデル。アンサンブル関係ないじゃん？という気もするが、treeのnodeごとのモデルを組み合わせている、と考えて14章に入ってる模様（だいたい定数だが…）

人間に解釈しやすいのが魅力、とか。

基本的なアイデア

特定のフィーチャーのsplit点より大きいか小さいかで二分木を作る。 これらはフィーチャースペースを軸と垂直な線で領域に分割していく事に相当する。 で、各領域に最終的な値を割り当てる。

これで、各サンプルが、どの領域に行くかを木をたどって判定し、最後に領域に割り当てられた値をpredictionの値とする。

これで、あとはどう分割するか、と割り当てる値をどするか、の二点の問題となる。

regressionの場合、greedyに二乗誤差をへらす

ある領域のpredictionを、そこに属してるトレーニングサンプルの、ラベルの平均とする。

で、この平均と各ラベルとの二乗誤差をコストとし、このコストを最小にするように分割するフィーチャーと点を決めていく、というのが基本的な考え。

これだと2つのフィーチャーの組み合わせでめっさ二乗誤差が減るが一つだと駄目、みたいな時に分割出来ない気がするが…

14.4の最後にそんな事書いてあるな。

pruning

木をどこまで伸ばすかは意外と難しくて、分割で二乗誤差があまり減らない所まで来た後も、しばらく分割を続けるとまた減り始める、という事があるらしい。

そこで一旦大きめに分割した後に、木を枝刈りしていく、という手続きを踏むらしい。 枝刈りは二乗誤差に末端のノードの数をregularizationっぽく加えたコストを最小化するように行う、とか。（式14.31）

classificationの場合、クロスエントロピーかGini係数を使う

classificationでは、なるべくどれか一つのクラスに偏っていく方がいいので、各領域内で、あるクラスに属す確率が0か1の両極端だと低くなるようなコストを課したい。

という事でクロスエントロピーかGini係数を使うとか。

14.5 Conditional Mixture Models

14.5は複数の線形回帰とかロジスティック回帰のモデルの混合分布を考える、という話。 個々のモデルを条件付き確率と解釈すると、そのmixingは混合分布となる。

さらにmixing coefficientを入力の関数とみなすと、mixiture of expertsというモデルになる。

あんま面白くないので軽く流す。

14.5.1 線形回帰のモデルの混合

線形回帰を確率的に解釈すると、ファイとwの積を平均とするガウス分布と解釈出来る、という話があった。

そこで、K個の線形回帰のモデルを重ね合わせると、混合ガウス分布みたいな形になる。

パラメータを最尤推定する為には、各データがどの線形モデルに対応するかを表すlatent variableを考えて、EM法を適用する。

14.5.2 混合ロジスティックモデル

タイトルのまんま。ロジスティック回帰は条件付き確率と解釈できるので、そのまんま混合分布を考える事が出来る。

パラメータはやっぱり同じような感じでEM法で求まる。

なんというか、そのまんまの内容で別段驚きが無い。

14.5.3 Mixtures of experts

mixing coefficientを定数じゃなくてxの関数とすると、mixture of expertsというモデルになる。 係数は足すと1となる制約を満たす必要がある。

この係数をgating functionというらしい。LSTMみたいやね。

このgating functionをさらに多段にした物をhierarchical mixture of expertsと呼ぶ、と名前だけ紹介して本は終わる。

まぁこの辺はいいだろう。

GBとかまで含めたboostingの話

幾つか論文を読んでみた

Friedman 2001はGradient boostの原典と思うが、XGBoostのコードや論文とは微妙に内容が違うので、原典の方をGB1、XGBoostの方をGB2と呼ぶ事にする。

adaboost、GB1、GB2は比較した方がわかりやすいと思うのだが、それぞれ微妙にノーテーションとか違って分かりにくいのでここに自分なりのまとめ方でまとめてみる。

両者共通の問題の定式化

まず、\(\{y, x\}\)という母集団から、\(\{y_i, x_i\}^N_1\)をサンプリングする。

あるxの関数Fとyとのロス関数Lがある。

\[L\{y, F(x)\}\]

この時に、この「母集団での」ロスの期待値を最小化する関数を\(F^*\)とする。

\[F^* = arg \min_F E_{y, x}L\{y, F(x)\}\]

この\(F^*\)を、additive expressionで近似したい。

addtitive expressionとは、

\[F(x) = \sum^M_{m=1}f_m(x)\]

という形。

この時に、一般の形でこれを求めるのは難しいので、\(f_m\)をm=1から順番に求めていき、各段階でそれ以前の\(f_m\)は所与としてロスを最小化する（greedyにstage wiseに求める）。

こうすると、m-1期までをGと置いて、

\[f(x) = arg \min_f E_{y, x}L\{y, G(x)+f(x)\}\]

を満たすfを関数空間の中から探していく問題に帰着出来る。

以下、期待値は母集団についてとるので、たんにEと書いたら母集団の期待値とする。

だが、当然母集団の期待値は分からないので、どこかでサンプルの期待値に置き換える近似を行う。 自分の理解では最初の段階でサンプル期待値に置き換えても全部成り立ってると思うのだけど、自信が持てないので（特にGB1の時に自信が無い）原典と同じタイミングでサンプリング期待値への置き換え近似を行う事にする。

ここまではadaboost、GB1、GB2は全て同様。

GB1の導出

Freidman 2001に書いてあるGradient boostingの導出を、adaboostやGB2との関係も視野に入れた形で導出してみる。

無限次元のgradient descentと思う

このロスは、Fを引数とする汎関数とみなす事が出来る。 Functionalっぽく花文字で置こう。

\[\mathscr{L}(F) \equiv E_{y, x}[L\{y, F(x)\}]\]

これはFを無限次元のベクトルと見ると、ある無限次元の点Fに対応した値を取る、と解釈出来て、これの最小化というのは、この無限次元のベクトルを少しずつ変更して最小となる点を探す問題と考えられる。

gradient descentの手続きをこれに適用すると、変分の方向にlearning rateだけ進む、と書ける。

\[G + f = G + \rho \delta \mathscr{L}(G)\]

ここで\(\rho\)はlearning rateに相当するものだが、GB1ではこの\(\rho\)はその時点でロスの期待値を最小化するように選ぶ。

これを2つの最適化問題として解く。

1つ目、変分の方はregression treeとして学習する。ただ、変分そのものではなく、変分と同じ方向ベクトルが同じ物を学習し、絶対値は気にしない。

2つ目、最適な\(\rho\)を選ぶ。

最適化問題1 変分の方向を学習する

ここで\(\delta \mathscr{L}(G)\)は（ロスの形式次第だがよくあるロスなら）汎関数微分で簡単に求める事が出来る。

ただし、その結果は普通xとyを含むので、無限次元の方向ベクトルを得るには無限個のxと、それに対応したyの組が必要になる。 だが得られているのはN個のサンプルのみ。

そこでGB1では、探索する関数空間内で、このN個のサンプル点をもっとも良く近似する物を探す。

2つの関数が一致する、というのは、本来なら全てのxでf(x)の値が近くないといけない訳だが、それを有限個のサンプル点で近い物を探して、それで置き換える、という近似をしている事になる。これはトレーニングセットで求めた物が汎化している事を期待する、という通常の機械学習の話でもある。

N個の点で変分の値がわかってるので、それにマッチングするregression treeを最小二乗法で求める。 探索する関数空間をregretion treeとして、その関数をb、パラメータを\(\mathbf{a}\)と置くと、

となる。 偏微分となるのは、微分を含まない汎関数微分の関係から。

ここで、あとでlearning rateに相当するものは別途最適化するので、ここでは方向だけを最適化するように大きさは別のパラメータとしてベータを置いている。このベータは以後は使わない。

最適化問題2 最適なローを探す

さて、こうして変分と近い方向を持っていると期待出来るbが得られたので、これを用いてgradient descentの手続きをしたい。

GB1ではlearning rateに相当するものを、毎回その時点でexpected lossを最小化する値として選ぶ。 つまり近似が成り立つ少しの差分でなく、ロスを一番減らすように選ぶ。 これのjustificationは良く分からない。 もともと小さい差分なら変分の値が変わらないという事を期待出来る、というロジックな気はするが。 ただ、これだと二次以降の項を定数の調整で織り込める可能性はあるかも。

これまた母集団の値は分からないので、サンプルでの期待値をもって近似とする。

以上2つの最適化問題に帰着するのがFriedman 2001で提唱されているGradient boosting。

ただしLAD Treeのところでは\(\rho\)の最適化を各ノードごとの最適化に拡張して、より良いフィッティングを行っている。

fによるテイラー展開で二次までを残す

adaboostとGB2は、\(\mathscr{L}\)をfでテイラー展開して二次の項まで残し、その範囲で最小になるfを選ぶ、 という所までは同様で、そこから先の仮定が異なる。

まず\(\mathscr{L}(G+f)\)をfでテイラー展開して二次の項まで残そう。

ここで1階の偏微分をg、二階の偏微分をHと置く。

これを最小化するfを求めたい。

必要なのはfだけなので、fに依存しない最初の項は無視出来る。

adaboost

以上の近似を元に、さらに幾つかの仮定を追加するとadaboostとなる。

adaboostの仮定

  1. ターゲットは1, -1
  2. fを \(\rho b(x; \mathbf{a})\)の形に限定
  3. bを1と-1だけをとる形に限定
  4. Lは\(exp(-y F(x))\)
  5. 母集団の期待値をサンプルの期待値で近似する

これらの仮定を上記のarg max の式に入れていく。

adaboostのobjective

まず、Lの導関数を求めておく。

ここで、yが1か-1なので、yの二乗はどちらにせよ1になる。これはbも同様。

それらをarg minの式に代入して、以下を得る。

これをローの最適化とbの最適化に分けて考える。

bの最適化問題

bの最適化を考える時には、一項目だけ考えれば良い。 計算していくと以下のようになる。

ここで最後はサンプリングの期待値に置き換える近似を行った。

さらに、

となる。これはadaboostの弱評価器のcriteriaであるPRML 14.15式と一致する。

ローの最適化はテイラー展開前の式を直接解けて、14.17が出る。

GB2の導出

XGboostやLightGBMのGradient boostingの実装は、regression treeを前提にしていろいろな近似による最適化が入っているが、基本的なアイデアの段階でGB1と異なっているように見えるので、ここでそれをまとめておく。

一般のクライテリアの整理

基本的なアイデアは、二次のテイラー展開した汎関数の最大値のサンプル期待値を、直接ツリーのsplitのcriteriaに使う、というもの。

まずmimizeのcriteriaを母集団の期待値からサンプリング平均に置き換えた物を書く。

ここまではサンプリング平均に置き換える近似をしただけで一般的な式。

ここに、fをregression treeという仮定を導入して分割のクライテリアを作る。

分割のクライテリアを求める

fをregiession treeに限定して\(\mathscr{L}\)を変形していく。

あらすじとしては、まずツリーの構造を所与と考えて\(\mathscr{L}\)の値を求める。

こうして求まった値はregressionのノードの値、\(w_j\)でパラメータ化されている。そこでまずロスを最小化する\(w_j\)を求める。こうして求まった\(\mathscr{L}\)が、分割のクライテリアのベースとなる。

では実際に求めてみよう。

ツリーがJ個のノードに分割されるとする。 ノードのインデックスは小文字のjで表す。

そしてj番目のノードに行く\(x_i\)の集合の、インデックスだけ集めた物を\(I_j\)とする。

まず図解してみよう。

厳密に定義すると、ツリーの構造をqとした時、\(I_j = \{i │q(x_i) = j \}\)が\(I_j\)の定義。

で、各ノードjのpredictionの値を\(w_j\)とする。

するとmimizeのクライテリア、\(\mathscr{L}\)は、以下のように書ける。

これをmimizeする\(w_j\)は平方完成ですぐ分かって、

となる。これはNewton Raphsonの更新式の重心となっているので、Newton Raphsonのyを近似している事になる。

さて、mimizeする\(w_j\)は分かったので、これを\(\mathscr{L}\)に代入すると、

これが分割でmimizeすべきコストとなる。

分割の前後での変化に着目したいので、添字の集合がIのノードを\(I_R\)と\(I_L\)に分割した時のコストの変化は、

と表せる。 これを最小化するように分割をしていく。

splitの効率化について

splitのcriteriaは、そのノード内のgradとヘッシアンの和にしか依存してない事に注目する。

各サンプルをフィーチャーの順にsortして、それを例えば10パーセンタイルずつのbinに分ける。

そしてbinの中のgradの和とHの和を保持しておけば、10パーセンタイルずつのsplitのロスは簡単に計算出来る。 特に下から順に10パーセンタイル、20パーセンタイル、と求めていくと、次のLeftのgradの和は前のLeftのgradの和に次のbinのgradを足せば求まり、Rightはbinのgradを引けば求まるので、一回の演算で求まる。 ヘッシアンも同様。

このようにbinの境界点でのロスは高速に計算出来て、その値をsplit点として使う。

パーセンタイルの点は厳密に求めるのはコストが掛かるので、Quantile Sketchという近似を使うらしい。

なおXGBoostではこのパーセンタイルをヘッシアンの重みを考慮した物に改善したアルゴリズムを使って分割候補点を列挙するらしい。