半歩ずつ進める機械学習　～scikit-learn アンサンブル学習～

##前回まで
[前回の投稿][1]でSVRについて学びました
今回はアンサンブル学習について学びます。

##御注意
自分自身が勉強中なので、最大限気を付けていますが正確でない情報があるかもしれません（たぶんあります...）
アレレ？おかしくないかな、と思った時は素直にGoogleで検索して補完をお願いします。
ついでに間違いにお気づきの方はご指摘頂けましたら幸いです。

##Ensemble
前回までは、ずっと回帰分析用(Regression）のモデルを学んできましたが
アンサンブル学習自体は分類でも回帰でも利用されます。

##ブートストラップ集約
アンサンブル学習の手法について学ぶ前に
まずは**ブートストラップ集約**という訓練データの水増し方法について学びます。
ブートストラップ集約は、訓練データから重複ありでランダムにデータを抜き出して
新たな訓練データとする手法です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/316551/1fed578b-b179-5beb-0019-6447780dd6f8.png)

上記画像の例では、1個の2*2の訓練データから、3個の2*2訓練データを作り出しています。
また、ランダムに重複ありで抽出するので、元のデータには存在するが抜き出されなかったデータが存在します。
※上記画像の例で言うと、一番左のデータでは4　中2　右1と3
これらのデータの事を**OOB(Out-of-Bag)**と言います。

##アンサンブル学習の手法
一言にアンサンブル学習と言っても複数の手法があるようですが
メジャーな方法として以下のものがあるようです。

+ **バギング**
ブートストラップで任意のN個のデータセットを作成します。
各々のデータセットでN個の学習器を訓練して
各学習器の予測値の**単純平均値**を最終的な予測値とする方法


+ **スタッキング**
※ネットで検索すると複数の定義がありました。
どちらがメジャーかは分かりません
バギングと同様の方法で学習器を作ります
各学習器の出力を**加重平均**して、最終的な予測値とする方法

学習器の出力を次の学習器への入力とする手法


+ **バンピング**<br>
バギングと同様の方法で学習器を作ります
各学習器で元の訓練データ（訓練データ全体）に対する予測精度を調べて
**最も予測精度の高いモデルの出力を最終的な出力として採用**する方法

上記の3種の手法は、最初にブートストラップでN個のデータを作って
N個の学習器を同時に学習する**並列処理**が可能です。

+ **ブースティング**<br>
ブースティングは上記3種と異なり、まず1個の学習器が学習を行い
その学習器の出力を受けて、次の学習器が学習する。といった**連続的・逐次的**な学習を行います。
メジャーなブースティングの手法として、**AdaBoost**と**勾配ブースティング**があります。


##**AdaBoost(Adaptive boosting)**
AdaBoostは回帰にも使えるんですが、詳しい解説を行っている日本語の資料が見当たらなかった為
ここでは分類問題を例にして勉強していきます。

まずイメージとして以下の様なデータがあるとします。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/316551/b5058c51-d56d-5791-99be-60b5545fc99e.png)

$x$ と $y$ のデータから○か△かを分類する分類器をAdaBoostで作ります。
与えられるデータは、それぞれの $x$ と $y$ と正解ラベル $t$ (1or-1)です。
データは8件あるんで、以下のような感じですね

```math
\boldsymbol{x} = (x_1,x_2,,,x_8)\\
\boldsymbol{y} = (y_1,y_2,,,y_8)\\
\boldsymbol{t} = (1,1,1,-1,-1,-1,-1,1)(△=1,○=-1)\\
```

これに追加して各データを誤分類した場合の損失の重みを用意します。

```math
\boldsymbol{w} = (w_1,w_2,,,w_8)
```

最初の重みは(1/サンプル件数)で初期化するので、$w$ は全て1/8です。
以上のデータから、以下の損失関数が最小になるように1個目の分類器 $f_1(x,y)$ を作ります。

```math
I=指示関数\\
\sum_{n=1}^{8}(w_nI(f_1(x_n,y_n)\neq t_n))
```

$I()$ は指示関数と呼ばれる物で、括弧内の式が成立していれば1を、そうでなければ0を返します
上の式を言葉で表すと、**誤分類したサンプルの重みの総和を最小化**です
最初は重みは全て同じなので、誤分類の件数を最小化するのと同じです。
線形な分類器だと以下のような形になるかと思います。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/316551/cfc2c206-8555-74c1-9694-ea615515c1b0.png)

青い線より上が△、下は○と判断する分類器です。
次に、この分類器を元に以下の計算を行います。

```math
\epsilon = \frac{\sum_{n = 1}^{8}w_nI(f(x_n,y_n)\neq t_n)}{\sum \boldsymbol{w}}...(1)\\
\alpha = log(\frac{1-\epsilon}{\epsilon})...(2)
```

まず(1)の式ですが、数式にするとゴチャゴチャ分かり難いですが
早い話が$\frac{誤分類した重み}{全体の重み}$です。
今回のケースいうと$\frac{\frac{1}{8}}{1}$なんで$\frac{1}{8}$です

で(2)の式は計算してみると $log_e7$ です。
この $\alpha$ という値は、誤分類の数が少なければ少ない程大きくなります。
つまり、この分類器の精度・信頼性を表していると言えます。

これでとりあえず1個分類器が出来たので、2個目の分類器を作りたい所ですが
このまま何もデータを変えずにやっても同じ結果になるので、以下の式で**重みの更新**を行います

```math
w_n = w_n exp(\alpha I(f(x_n,y_n) \neq t_n)
```

言葉で書くと、前回の分類器で誤分類されたサンプルの重さは$exp(\alpha)$倍になる。です
今回のケースでは$exp(\alpha) = 7$なので7倍になって$w_8 = \frac{7}{8}$になります。

これで重みの更新が終わったので再び損失関数が最小になるように2個目のモデルを作ります。
8番目のサンプルだけ重みが他のより7倍になってるんで、8番のサンプルだけは誤分類するワケには行きません。
恐らく $f_2(x,y)$ は以下の様な形になると思います。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/316551/a0279e38-6cf6-a403-db81-56ebe8a7c311.png)

青線より下が△、上で○と判断する分類器ですが、今度は1,2,3の△が誤分類されました。
もう計算しませんが、$f_2(x,y)$ に誤分類されたサンプルの重みを更新して $f_3(x,y)$ を作ります。
こんな感じでドンドン分類器を作って行きます。

任意のM個の分類器が出来たら、その時には各分類器の信頼性を表す $\alpha$ もM個出来て居るハズです。

最後に、M個の分類器と $\alpha$ を使って以下のアンサンブルモデルを作ります。

```math
\sum_{m=1}^{M}(\alpha_m f_m(x,y))
```

M個の分類器にデータを入れて、その出力を信頼性で重みづけして合計します。
結果の符号がマイナスならｰ1と判断、プラスなら1と判断します。

##**勾配ブースティング(Gradiend boosting)**
scikit-learnではありませんが、Kaggle等で頻繁に使われている**XGBoost**で使われている手法です。
まずは以下の画像を見て下さい

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/316551/5d5832eb-ee0f-0b34-9104-e0209ed57ff2.png)
引用：Géron, Aurélien. "Hands on Machine Learning with scikit-learn and Tensorflow." (2017).

一番左上のデータが、訓練データ $x$ と教師データ $y$ の図です。
$y = nx^2 + b$ にノイズを加えたような形をしていますね


まず一番初めに画像左上のように回帰木を使ってモデル $h_1(x)$ を作ります。

画像2段目左のデータ点は $(y-h_1(x))$ 、つまり1個目の回帰木の予測値と各教師データの残差の散布図です。
次に $h_1(x)$ との残差にフィットした回帰木 $h_2(x)$ を作ります（画像2段目左）
この二つを足したモデル $h_1(x) + h_2(x)$ の出力が画像2段目右になります。
更にこのモデルと $y$ の残差を計算して、それにフィットした回帰木 $h_3(x)$ を作ります（画像3段目左）

このように**残差にフィット**した回帰木を積み重ねて行くことで、絶対値誤差を最小にする表現力の高いアンサンブルモデルを作る事が出来ます。

これが勾配ブースティングの**イメージ**です。

この時点だと、なんで**勾配ブースティング**という名前なの？って感じです
上の例では損失関数に絶対値誤差を用いていましたが、二乗誤差を使った場合を考えてみます。

まず $h_1(x)$ の時点での各サンプルとの二乗誤差は $(y_n - h_1(x_n))^2$ です。

次に一旦損失関数を $h_1(x_n)$ で微分して、各サンプル点の $h_1(x_n)$ の変化に対する勾配を計算します

```math
\begin{eqnarray}
v &=& h_1(x_n) \\
E  &=& (y_n - v)^2 \\
E &=& y_n^2 - 2y_nv + v^2\\
E' &=& 2v-2y_n\\
E' &=& 2h_1(x_n) - 2y_n\\
\end{eqnarray}
```

損失関数は定数倍しても最小の点は変わらないので、分かり易くする為2で割って $E' = h_1(x_n)-y_n$ にします。
これで各サンプル点毎の $h_1(x)$ に対する勾配が出ました。
この傾きがマイナスであれば、$h_1(x)$ は、そのサンプル点との誤差が最小となる点よりマイナス方向にあり
プラスであれば、プラス方向にあるという事になります。
手書きで分かり難いかもしれませんが、以下のような感じです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/316551/4b9408dc-da5f-3d00-157e-db5a02b7c1ea.png)

では勾配とは逆方向の適切な値を返す関数 $h_2(x)$ を加えれば誤差が最小になりますよね
勾配の逆方向の値なんで　$h_2(x) = -n(h_1(x) - y) = n(y-h_1(x))$ です。

ここで $y - h_1(x)$ に注目してください。
これは勾配ブースティングの項の初めに掲載した画像2段目左と同じ状態です
絶対値の時には**残差にフィット**と表現していましたが、これは言い換えれば**勾配とは逆方向の適切な値にフィット**と同じ意味です。
これが**勾配ブースティング**のいう名前の由縁です。

勾配ブースティングでは、この適切な値を**勾配降下法**で探します。
例えば、 $h_2(x)$ の計算を行う時に、ある葉に振り分けられたサンプルが持つ $h_1(x)$ との勾配が以下のようになっていたとします。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/316551/ddc8e397-4aa8-95ff-f618-2de43148c47b.png)

この場合、勾配の平均値を出して、0からスタートしてその方向に少しずつ $h_2(x)$ の出力を動かして行って、最小の点を探します。
上記の例では平均は明らかにプラス方向なので、0から少しずつ $h_2(x)$ の出力を高めて行って、最終的に $E = \sum_{n=1}^{N}(y_n - (h_1(x_n)+h_2(x_n)))^2$が最小になる点を $h_2(x)$ の出力とします。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/316551/b9560315-7c32-8989-1382-ede267f3c4bb.png)

あとは好きな回数だけこれを繰り返して、$\sum_{M}^{m=1}(h_m(x))$をモデルとします。

この様に次段の学習器を、前段までの学習器と教師データとの損失の勾配にフィットさせる事で
**微分可能な損失関数**を広く採用する事が出来るそうです。
また、今回は回帰木を例に勉強しましたが、基本的に回帰木以外のモデルを結合させる事も出来るようです。

##次回へ
次回は今まで勉強した回帰モデルを総動員してボストン住宅価格を予測するモデルを作ってみようと思います
今回は長くなったので、実際のコードは書きませんでしたが、次回の投稿で纏めて勉強したいと思います。

機械学習の初心者が、学んだ知識の確認と備忘用に投稿しています。
間違っている部分や、何かお気づきの事がありましたらご指摘頂けますと幸いです
あと、独学者なので「私も今勉強中なんです！」みたいな人がいればコメント貰えると喜びます。

[1]:https://qiita.com/Mukomiz/items/f9d84e659cd84624989f