OOB Error をランダムフォレストで使う【機械学習】
1. 概要
機械学習でよく使われるランダムフォレストとOOB errorについて説明する．
また， バギングやブートストラップのようなランダムフォレスト周りの用語についても簡単にまとめる．
2. ランダムフォレスト
ランダムフォレストは，決定木ベースのアンサンブル学習手法の一つであり，スケーラビリティが高く，使いやすいことで知られている．解釈が比較的容易で，ある程度の精度のあるモデルを手早く作成できるので，よく使われているアルゴリズムである．
この手法は，学習データからいくつかの決定木を学習し，それらを平均することでより汎化性能の高いモデルを構築することができる．
ランダムフォレストでは，ブートストラップ と バギング という手法を用いる．
ブートストラップ
ブートストラップは，機械学習アルゴリズムにおいてバリアンスを減らすために用いられる統計的手法である．つまり過学習に対処するための方法である．簡単にいえば，N個の学習データからn個のデータをランダムに復元抽出を行い，新たな学習データとして定義し直すものである．この新たな学習データをブートストラップ標本と呼ぶ．
復元抽出とは母集団から重複を許してサンプリングを行うことである．例えばサイコロのように一回の試行ごとに6つの値の中から一つが選ばれる．よって，同じ値が複数回出現する．反対に非復元抽出は宝くじのように，一旦くじを引くとそのくじをもとに戻さずに次のくじを引くので，同じ番号のくじが二度引かれることがない．このような形態のサンプリングのことを非復元抽出という．
ブートストラップ手法では，復元抽出でサンプリングを行う．つまり，ブートストラップ標本の中には全く同じデータが複数入っている可能性がある．反対に，一回もブートストラップ標本として選ばれていないサンプルも存在する．
バギング
バギングも，学習時のバリアンスを減らすための手法で，特にノイズの多い学習データのときによく使われる．
下の図のように分類（回帰）モデルを複数作成し，それぞれのモデルに対して予測値を相対多数決を取ることで最終的な予測値を決定する方法だ．複数モデルを作成することでそれぞれのモデルで発生したノイズを埋め合わせることができる．
作成するモデルはどの形式でもよく，ランダムフォレストでは決定木が用いられる．
ランダムフォレストの仕組み
ランダムフォレストは，ブートストラップとバギングを組み合わせた手法である．
以下が具体的な手順である．
- 学習データからn個のランダムなブートストラップ標本を復元抽出する
- ブートストラップ標本から決定木を成長させ，モデルを作る
- 手順2~3をk回繰り返す
- 決定木ごとの予測をまとめ，相対多数決に基づいてクラスラベルを割り当てる（分類タスクの場合）
まとめると，ブートストラップ標本をもとにk個のモデルが生成され，k個のモデルの出力を合算して最終的な予測値を出している．
3. Out-of-bag Error
Out-of-bag Errorは，学習モデルを検証するための方法の一つで，特にランダムフォレストにおいては，クロスバリデーションなどと比べても信頼のできる評価方法である．
Out-of-bagとはなにか
ブートストラップの説明の際に，ランダム復元抽出を行うので，元の学習データの中には一回も選ばれないレコードが存在すると述べた．Out-of-bagとはまさにこのモデル作成の際に使用しなかった標本のことである．Out-of-bagのサイズは36%前後になることが多いと言われている．
モデル作成の際に使用しなかったサンプルなので，各決定木のOut-of-bagを検証に使用することができ，これがOOB Errorと呼ばれる．
Out-of-bagのサイズ
Out-of-bagのサイズは，元のデータが十分大きければその36%程度になることが知られている．これを理論的に求めてみる．
まず，もとの訓練データに含まれるある一つのレコードに着目してみる．このレコードがブートストラップで選ばれないということは，n回の試行すべてで自分以外のレコードが選ばれることを表しているので，その確率は
ここでnのサイズを無限大にとばすと，ネイピア数eの定義より
となり，元のデータが十分大きければ36%程度のサイズになることがわかる
OOB Error
OOB Errorは以下の手順で算出することができる．
- データセット
S - ランダムフォレストを
k - ランダムフォレストを
S - ランダムフォレスト中の各決定木
T_i
4-1.S_i = T_i
4-2.S_i^c = S \backslash S_i
4-3.P_i = T_i S_i^c - 予測値を元に全体の誤差率を計算する
まとめると，ブートストラップ標本で使用しなかったデータを各決定木で予測し，その誤り率を平均して全体の誤り率としている．
4. まとめ
この記事では，ランダムフォレストを中心に，バギング，ブートストラップ，OOB Errorを解説した．OOBを使ってモデルの評価を行う方法は様々な文献で出てくるので，知っておいて損はないはず．
5. 参考文献
なにか間違い等があればコメントなどで指摘いただけると幸いです．
Discussion