Open karino2 opened 5 years ago
comittee、adaboost、conditional mixtuer modelという内容。 決定木は思ったよりページ数無くて、mixtuer modelが多い。
gradient boostとかは無いのね。
adaboostはexponential errorからの解釈が書かれていて、ここの内容はなかなか良いが、最初のアルゴリズムの提示の方が先に出てくるのでこちらは分かりにくい。
幾つか重要な式変形が練習問題に回されているのでやっても良い気はする。
どうしよっかね。とりあえずこの本に沿ってまとめてみるか、それともboostingにフォーカスしてGBDTとかそのヒストグラムの話を掘り下げるか…
勉強会をどう進めるかはおいといて、ひとまず教科書の内容をまとめてみよう。
14.1では初めに、本章で扱う手法とBayesian model averagingの違いについて言及している。
結論としてはBayesian model averagingは、全部のデータがどれか一つのモデルから生成されていて(式14.6)、でもそれがどれかが分からない、データが増えればだんだんと一つに収束していく、というもの。
一方で複数のモデルをcombineする場合は、例えば式14.5の場合などでは、各データ点ごとに別々のlatent variableが考えられて、だからおのおののデータ点が別々の構成要素から生成される。
式の形は似てるけど、意味合いは違いますよ、という話っぽい。
スペルが難しいな。mもtもeも全部ダブるのね。どうでもいいが。
この節では、モデルを複数作って平均を取る、という方法を考える。(14.7) 一番簡単には、データを最初に分割して別々にトレーニングする。これをbootstrap aggregationとかbaggingと言うらしい。
14.8のようにあらわして、モデルが独立なら平均取るとエラー項が減ってく、という話をしている。 ただ普通相関があるのでこんなうまく行かないとか。そりゃそうだ。
committeeの一種との事。 複数のモデルを組み合わせるのがcommittee、そのうち単に平均するのがbagging、順番にモデルを作り、この時前のモデルを使うのがboostingか。
この節ではadaboostの話をしている。
まずp658に、アルゴリズムが載っている。 どうしてこういう式になるのか、については、次の14.3.1で解説がある。
問題設定としては、-1か1のどちらかをpredictするモデルを作る、というもの。
アルゴリズムの基本的なアイデアとしては、
という感じ。
これらの式がちょうど良い物になってるかとかはこの時点では分からない。 あくまでこういう物だ、という事だけが羅列されている。
adaboostのアルファやwがこの形である必然性は、アルゴリズムだけを見ると良く分からない。 14.3.1はexponential errorを最小化する、という問題を考えると自然とこれらの式が出てくる、という話。
今回もターゲットは1か-1。
こんなエラーを最小化していくように、fmを追加していく事を考える。
分類器yとアルファを動かして、Eを最小化する事を考える。
ただし全体を最適化するのは難しいので、greedyに求める。 つまりm-1期までの解を前提に、m期のfだけを最適化して追加する、という事を1期から繰り返す。
この式からアルファとwmの更新の式とymの学習の式が得られる。
mを一期進めると、wmの漸化式が出てくる。ymをIndicator functionで書き直して14.26が得られて、これがwの更新の式となる。 ただしymを使ってるので、先にymをトレーニングする必要アリ。
という事でymをトレーニングする式を考える。 上の和を、ymが正しく分類した物とそうでない物に分けると、以下のように書ける。
ymの最適化では第二項は定数なので第一項の最適化となる。これはadaboostのアルゴリズムの説明でのymの式と同じになる。(式14.15)
さらにこの式で、アルファmで微分してイコール0と置くと、
これは整理すれば式14.17になりそう。
こうして求めたfmは、もともと14.20を最小化する物だったので、この符号をpredictionで使えば良い。 これがadaboostと同じ事になる。
このexponentialの誤差関数は、普通の誤差関数とは少し違う。14.3.2ではそれらがどう違うのか、という話をしている。
普通の誤差関数というとロジスティック回帰の時の負の対数尤度という事になるが、これは0, 1だった。 1と-1にしたものは7.1.2でやったらしい。一応計算しておく。
尤度は
となるので、負の対数尤度は
となる。特に難しい事は無いが、0, 1のケースと違って見慣れてないので出しておかないとピンと来ないやね。
いわゆる決定木のモデル。アンサンブル関係ないじゃん?という気もするが、treeのnodeごとのモデルを組み合わせている、と考えて14章に入ってる模様(だいたい定数だが…)
人間に解釈しやすいのが魅力、とか。
特定のフィーチャーのsplit点より大きいか小さいかで二分木を作る。 これらはフィーチャースペースを軸と垂直な線で領域に分割していく事に相当する。 で、各領域に最終的な値を割り当てる。
これで、各サンプルが、どの領域に行くかを木をたどって判定し、最後に領域に割り当てられた値をpredictionの値とする。
これで、あとはどう分割するか、と割り当てる値をどするか、の二点の問題となる。
ある領域のpredictionを、そこに属してるトレーニングサンプルの、ラベルの平均とする。
で、この平均と各ラベルとの二乗誤差をコストとし、このコストを最小にするように分割するフィーチャーと点を決めていく、というのが基本的な考え。
これだと2つのフィーチャーの組み合わせでめっさ二乗誤差が減るが一つだと駄目、みたいな時に分割出来ない気がするが…
14.4の最後にそんな事書いてあるな。
木をどこまで伸ばすかは意外と難しくて、分割で二乗誤差があまり減らない所まで来た後も、しばらく分割を続けるとまた減り始める、という事があるらしい。
そこで一旦大きめに分割した後に、木を枝刈りしていく、という手続きを踏むらしい。 枝刈りは二乗誤差に末端のノードの数をregularizationっぽく加えたコストを最小化するように行う、とか。(式14.31)
classificationでは、なるべくどれか一つのクラスに偏っていく方がいいので、各領域内で、あるクラスに属す確率が0か1の両極端だと低くなるようなコストを課したい。
という事でクロスエントロピーかGini係数を使うとか。
14.5は複数の線形回帰とかロジスティック回帰のモデルの混合分布を考える、という話。 個々のモデルを条件付き確率と解釈すると、そのmixingは混合分布となる。
さらにmixing coefficientを入力の関数とみなすと、mixiture of expertsというモデルになる。
あんま面白くないので軽く流す。
線形回帰を確率的に解釈すると、ファイとwの積を平均とするガウス分布と解釈出来る、という話があった。
そこで、K個の線形回帰のモデルを重ね合わせると、混合ガウス分布みたいな形になる。
パラメータを最尤推定する為には、各データがどの線形モデルに対応するかを表すlatent variableを考えて、EM法を適用する。
タイトルのまんま。ロジスティック回帰は条件付き確率と解釈できるので、そのまんま混合分布を考える事が出来る。
パラメータはやっぱり同じような感じでEM法で求まる。
なんというか、そのまんまの内容で別段驚きが無い。
mixing coefficientを定数じゃなくてxの関数とすると、mixture of expertsというモデルになる。 係数は足すと1となる制約を満たす必要がある。
この係数をgating functionというらしい。LSTMみたいやね。
このgating functionをさらに多段にした物をhierarchical mixture of expertsと呼ぶ、と名前だけ紹介して本は終わる。
まぁこの辺はいいだろう。
幾つか論文を読んでみた
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 \minF 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 \minf E{y, x}L{y, G(x)+f(x)}$$
を満たすfを関数空間の中から探していく問題に帰着出来る。
以下、期待値は母集団についてとるので、たんにEと書いたら母集団の期待値とする。
だが、当然母集団の期待値は分からないので、どこかでサンプルの期待値に置き換える近似を行う。 自分の理解では最初の段階でサンプル期待値に置き換えても全部成り立ってると思うのだけど、自信が持てないので(特にGB1の時に自信が無い)原典と同じタイミングでサンプリング期待値への置き換え近似を行う事にする。
ここまではadaboost、GB1、GB2は全て同様。
Freidman 2001に書いてあるGradient boostingの導出を、adaboostやGB2との関係も視野に入れた形で導出してみる。
このロスは、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$$を選ぶ。
ここで$$\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に相当するものは別途最適化するので、ここでは方向だけを最適化するように大きさは別のパラメータとしてベータを置いている。このベータは以後は使わない。
さて、こうして変分と近い方向を持っていると期待出来るbが得られたので、これを用いてgradient descentの手続きをしたい。
GB1ではlearning rateに相当するものを、毎回その時点でexpected lossを最小化する値として選ぶ。 つまり近似が成り立つ少しの差分でなく、ロスを一番減らすように選ぶ。 これのjustificationは良く分からない。 もともと小さい差分なら変分の値が変わらないという事を期待出来る、というロジックな気はするが。 ただ、これだと二次以降の項を定数の調整で織り込める可能性はあるかも。
これまた母集団の値は分からないので、サンプルでの期待値をもって近似とする。
以上2つの最適化問題に帰着するのがFriedman 2001で提唱されているGradient boosting。
ただしLAD Treeのところでは$$\rho$$の最適化を各ノードごとの最適化に拡張して、より良いフィッティングを行っている。
adaboostとGB2は、$$\mathscr{L}$$をfでテイラー展開して二次の項まで残し、その範囲で最小になるfを選ぶ、 という所までは同様で、そこから先の仮定が異なる。
まず$$\mathscr{L}(G+f)$$をfでテイラー展開して二次の項まで残そう。
ここで1階の偏微分をg、二階の偏微分をHと置く。
これを最小化するfを求めたい。
必要なのはfだけなので、fに依存しない最初の項は無視出来る。
以上の近似を元に、さらに幾つかの仮定を追加するとadaboostとなる。
これらの仮定を上記のarg max の式に入れていく。
まず、Lの導関数を求めておく。
ここで、yが1か-1なので、yの二乗はどちらにせよ1になる。これはbも同様。
それらをarg minの式に代入して、以下を得る。
これをローの最適化とbの最適化に分けて考える。
bの最適化を考える時には、一項目だけ考えれば良い。 計算していくと以下のようになる。
ここで最後はサンプリングの期待値に置き換える近似を行った。
さらに、
となる。これはadaboostの弱評価器のcriteriaであるPRML 14.15式と一致する。
ローの最適化はテイラー展開前の式を直接解けて、14.17が出る。
以前勉強会では飛ばしていいか、と思った14章(boostingとかアンサンブルの話)だが、やっぱやりたい気がしたので自分担当でやる事に。
という事でここに予習内容とか書いていきます。