![3-2. 理論編：ランダムフォレスト
? 実行速度について(SVM vs RF) データの数
SVM ~ O Dm2
( )
RF ~ O D2
m( )×
D :
m :
RのkernlabとRF(独自実装)で速度比較(データはiris)
SVM10回平均 1.2237[s]
RF(木10本)10回 1.1922[s]
説明変数の数
変数の数に強いが
データの多さに弱い
データの多さに強い
変数の数に弱い
木の本数](https://image.slidesharecdn.com/pdf2-140718192845-phpapp01/85/-27-320.jpg)
机会学习ハッカソン：ランダムフォレスト
- 2. 目次 ? 1. 自己紹介 ? 2. 概要：Random Forestとは ? 3. 理論編 ? ?3-1. 決定木 ? ?3-1. Random Forest ? 4. 実践編(プログラミングの流れ) ? ?4-1. 決定木 ? ?4-1. Random Forest ? 5. デモ ? 6. 参考文献
- 3. 1. 自己紹介 ? 馬場哲平(物理学博士:ニュートリノの研究してました) ? 職業：Webプログラマー ? 動機：MLの難しさをなんとかしたい
- 4. ? 高精度の機会学習アルゴリズム 2. 概要：Random Forestとは? ? 決定木を用いた集団学習を行うモデル ? 識別関数に分類される ? 教師データを必要とする
- 5. 2. 概要：Random Forestとは? ? そもそも決定木とは？ ツリー構造のグラフを作成し、予測/分類を行う機械学習のアルゴリズム。 弱学習器(精度の低い学習器)に分類される。 天気は何か 晴れ 休日、何して過ごす？ 雨 天気は何か 気温が 15℃以下？ YesNo 家でごろ寝 家でごろ寝散歩 時間は？ 夜昼 家でごろ寝
- 7. 2. 概要：Random Forestとは? ? Bagging ? Boosting ? Random Forest 全教師入力データからランダムにとったデータで、複数の学習器を作成、 多数決などで出力を決定する方法 説明変数の重要度を逐次的に変更し、複数の学習器を作成。多数決など で出力を決定する方法 (Baggingと違い、常に全教師データを用いる場合が多い。) 決定木を学習器とする、集団学習アルゴリズム Bagging同様、全教師データからランダムにとったデータで学習を行う。 説明変数もランダムにする点が、Baggingと異なる。 ? 集団学習の種類
- 8. 2. 概要：Random Forestとは? ML界 ※参考：@overlastさんのブログ, http://diary.overlasting.net/2011-06-01-1.html 識別関数 生成モデル 識別モデル SVM パーセプトロン logistic regression CRF ベイズモデル HMM 決定木 ランダムフォレスト
- 9. 2. 概要：Random Forestとは? ? Random Forestとは？ 教師データ 決定木 決定木 教師データ(一部) ブートストラップサンプリング 教師データ(一部) 決定木 決定木 教師データ(一部) 教師データ(一部) ??? 学習器 多数決/平均 予測結果 複数の決定木で集団学習させる事で、精度を高めた集団学習モデル。 2001年 Leo Breimanによって提案された。
- 10. 3. 理論編 ? 3-1. 決定木 ? 3-2. ランダムフォレスト
- 11. 3-1. 理論編：決定木 ? 決定木ができていれば、予測は簡単そう ? では、どうやって決定木を作るの？ 天気は何か 晴れ 休日、何して過ごす？ 雨 お金は あるか 気温が 15℃以下？ YesNo 家でごろ寝 家でごろ寝散歩 今の 時刻は？ 夜昼 家でごろ寝 No
- 12. ? 質問はたくさん情報を引出せる順に並べる 3-1. 理論編：決定木 ? どうやって情報を引出せる順番を判断する のか？ ? 引出せる情報量を数値化する
- 13. ? 情報ゲインは次式で表される。 3-1. 理論編：決定木 ΔI = P Q( )I Q( )? P Ai( )I Ai( ) i ∑ ? ある質問で得る情報量を情報ゲインと呼ぶ。 質問Q 答A1 QP Q( ): I Q( ): 前のノードからノード にくる確率 Qノード におけるエントロピー(関数) 答A2
- 14. 3-1. 理論編：決定木 ? ?? のバリエーション ? ②Gini係数(系の不純度の指標) ? ①エントロピー(系の取りうる状態数の指標) ΔI = P Q( )I Q( )? P Ai( )I Ai( ) i ∑ I A( ) I Q( )= 1? P A |Q( )( ) 2 A ∑ 高い：乱雑な状態 低い：整理整頓された状態 高い：純度が低い状態 低い：純度が高い状態 I Q( )= ? P A |Q( )logP A |Q( ) A ∑ ↑大きいと純度が高い(2回続けて同じ目がでるサイコロは純度が高い！) P k | A( ):ノードAで選択肢kが選ばれる確率※ 色んな目がごっちゃにでるサイコロ ぬるい 冷 温 ? ?
- 15. 3-1. 理論編：決定木 ? どちらにせよ、エントロピー関数?? が低 い値を示すと、情報ゲインが増えます ΔI = P Q( )I Q( )? P Ai( )I Ai( ) i ∑ I A( ) 情報ゲインを最大にする質問を、 各ノードで見つけていく
- 16. 3-1. 理論編：決定木 天気は何か 晴れ 休日、何して過ごす？ 雨 お金は あるか 気温が 15℃以下？ YesNo 家でごろ寝 家でごろ寝散歩 今の 時刻は？ 夜昼 家でごろ寝 No ΔI = P Q( )I Q( )? P Ai( )I Ai( ) i ∑ 情報ゲインを最大にする質問順に並べて木構造を作成する
- 17. 3-1. 理論編：決定木(補足) ? 決定木には種類がある。 連続的な数値を求める ?Gini係数 属するカテゴリを求める ?エントロピー ?Gini係数 ? ②回帰木 ? ①分類木 車速と停止距離の関係 花びらの長さ、幅とアヤメの種類
- 18. 3-2. 理論編：ランダムフォレスト ? なんで集団学習するの？ ? 他の集団学習と違うの？ ? 説明変数の重要度について ? 実行速度について(SVM vs RF)
- 20. 3-2. 理論編：ランダムフォレスト しましまさん：https://www.nescent.org/wg/cart/images/a/a6/Breiman_Arcing_classi?ers.pdf L.Breiman "Arcing Classi?ers" The Annals of Statistics, vol.26, no.3, pp.801-849 (1998) https://www.nescent.org/wg/cart/images/a/a6/Breiman_Arcing_classi?ers.pdf 汎化誤差 = バイアス + バリアンス + σ ※バイアス (学習モデルの単純さに由来する誤差) ※バリアンス(学習データの違いに由来する誤差) ※σ(削除不能な誤差) ■線形の様な単純なモデルでは、バイアスが大きくバリアンスが小さい ■高次の複雑なモデルでは、バイアスは小さいがバリアンスは大きい 単純なモデルなので、ノイズに強いが複雑な表現はできない。 (例)SVM、最小二乗法など 複雑な表現が可能だが、過学習してしまいがち。ノイズも再現してしまう。 (例)ニューラルネット、決定木など 分類/回帰のいずれにおいても、汎化誤差(新たなデータに対する誤認識率)は
- 21. 3-2. 理論編：ランダムフォレスト 汎化誤差 = バイアス + バリアンス + σ ※バイアス (学習モデルの単純さに由来する誤差) ※バリアンス(学習データの違いに由来する誤差) ※σ(削除不能な誤差) Tibshirani, R. (1996). Bias, variance, and prediction error for classi ? cation rules. Technical Report, Statistics Department, University of Toronto http://link.springer.com/chapter/10.1007%2F0-387-25465-X_34 高バイアス 低バリアンス 低バイアス 高バリアンス
- 22. 3-2. 理論編：ランダムフォレスト 汎化誤差 = バイアス + バリアンス + σ ※バイアス (学習モデルの単純さに由来する誤差) ※バリアンス(学習データの違いに由来する誤差) ※σ(削除不能な誤差) ? なんで集団学習するの？ 集団学習はバリアンスを下げる Improving regression estimation: averaging methods for variance reduction with extensions to general convex measure optimization, http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=5207764C9D12331E4F2A6336BD5E3842?doi=10.1.1.34.3566&rep=rep1&type=pdf 複雑な表現が可能だが、過学習してしまいがちなアルゴリズムに向いている
- 23. 3-2. 理論編：ランダムフォレスト ? 他の集団学習と違うの？ 学習の際、説明変数を ランダムに選んで使う x1 x2 x3 xn ??? 全説明変数 実際に使用 する変数 x1 x3 x2 x3 x3 xn??? 全変数 決定木1 決定木2 決定木n???
- 25. 3-2. 理論編：ランダムフォレスト ?説明変数の重要度について Ai : N : 決定木の本数 OOBデータを決定木に使用し、正しく予想を行った時の正解率 Im = 1 N Ai ? Bm( )i( )i=1 N ∑ Bm : OOBデータの説明変数mとなるデータをランダムに並び替え 決定木に使用し、本来正しくないはずの予想を行った時の正解率 説明変数mの重要度Im : Out-Of-Bag(OOB:学習に使われなかった残りのデータ) を使って、説明変数の重要度を計算できる
- 26. 出典：holidayworkingさん http://www.slideshare.net/holidayworking/ss-11948523 3-2. 理論編：ランダムフォレスト ?Out-Of-Bagを用いた説明変数の重要度 Im = 1 N Ai ? Bm( )i( )i=1 N ∑
- 27. 3-2. 理論編：ランダムフォレスト ? 実行速度について(SVM vs RF) データの数 SVM ~ O Dm2 ( ) RF ~ O D2 m( )× D : m : RのkernlabとRF(独自実装)で速度比較(データはiris) SVM10回平均 1.2237[s] RF(木10本)10回 1.1922[s] 説明変数の数 変数の数に強いが データの多さに弱い データの多さに強い 変数の数に弱い 木の本数
- 28. 3-2. 理論編：ランダムフォレスト ? メリット ? ノイズに強い ? 高精度?表現力も高い ? データ量が多くても高速に動く ? デメリット ? パラメータが多い(木の数や使用する説明変数の数) ? 学習データ/説明変数をランダム抽出するので、データと変数 が少なすぎるとうまく学習できない。
- 30. 4. 実装編(プログラミングの流れ) ? 4-1. 決定木 ? 4-2. ランダムフォレスト
- 32. 4-1. 実装編：決定木 (例)動物の分類 動物名 食性(Q1) 繁殖形態(Q2) 体温(Q3) クラス スズメ 肉食 卵生 恒温 鳥類 ライオン 肉食 胎生 恒温 ほ乳類 トカゲ 肉食 卵生 変温 は虫類 ダチョウ 草食 卵生 恒温 鳥類 ウシ 草食 胎生 恒温 ほ乳類
- 33. (例)動物の分類 ①初期のエントロピーを計算 ?(logの底は何でも良いが、今は2にする) I Q( )= ? P A |Q( )log2 P A |Q( ) A ∑ = ? 2 5 log2 2 5 × 2 ? 1 5 log2 1 5 =1.52 4-1. 実装編：決定木 動物名 食性(Q1) 繁殖携帯(Q2) 体温(Q3) クラス スズメ 肉食 卵生 恒温 鳥類 ライオン 肉食 胎生 恒温 ほ乳類 トカゲ 肉食 卵生 変温 は虫類 ダチョウ 草食 卵生 恒温 鳥類 ウシ 草食 胎生 恒温 ほ乳類 P(ほ乳類)=P(鳥類)=2/5、P(は虫類)=1/5
- 34. ΔI = P Q( )I Q( )? P Ai( )I Ai( ) i ∑ 4-1. 実装編：決定木 (例)動物の分類 動物名 食性(Q1) 繁殖携帯(Q2) 体温(Q3) クラス スズメ 肉食 卵生 恒温 鳥類 ライオン 肉食 胎生 恒温 ほ乳類 トカゲ 肉食 卵生 変温 は虫類 ダチョウ 草食 卵生 恒温 鳥類 ウシ 草食 胎生 恒温 ほ乳類 ②全ての説明変数に対し、各々の選択肢に遷移した 場合のエントロピーと遷移する確率を計算する。 質問Q3. 恒/変温? 変温 恒温 は虫類 1 P(変温?Q3)=1/5 P(恒温?Q3)=4/5ほ乳類 2 鳥類 2
- 35. ΔI = P Q( )I Q( )? P Ai( )I Ai( ) i ∑ 4-1. 実装編：決定木 (例)動物の分類 ②全ての説明変数に対し、各々の選択肢に遷移した 場合のエントロピーと遷移する確率を計算する。 質問Q3. 恒/変温? は虫類 1 ほ乳類 2 鳥類 2 I A1( )= ?1× log2 1= ?1× 0 = 0 I A2( )= ? 1 2 × log2 1 2 × 2 + 0 = log2 2 =1 変温(A1) 恒温(A2) P(は虫類)=1 P(ほ乳類)=2/4=1/2 P(鳥類)=1/2 動物名 食性(Q1) 繁殖携帯(Q2) 体温(Q3) クラス スズメ 肉食 卵生 恒温 鳥類 ライオン 肉食 胎生 恒温 ほ乳類 トカゲ 肉食 卵生 変温 は虫類 ダチョウ 草食 卵生 恒温 鳥類 ウシ 草食 胎生 恒温 ほ乳類
- 36. 4-1. 実装編：決定木 (例)動物の分類 ②全ての説明変数に対し、各々の選択肢に遷移した 場合のエントロピーと遷移する確率を計算する。 質問Q3. 恒/変温? ΔI = I Q = Q3( )? P A1( )I A1( )? P A2( )I A2( ) = 1.52 ? 0 ? 4 5 ×1= 0.72 変温 恒温 質問Q3の情報ゲイン 動物名 食性(Q1) 繁殖携帯(Q2) 体温(Q3) クラス スズメ 肉食 卵生 恒温 鳥類 ライオン 肉食 胎生 恒温 ほ乳類 トカゲ 肉食 卵生 変温 は虫類 ダチョウ 草食 卵生 恒温 鳥類 ウシ 草食 胎生 恒温 ほ乳類 ΔI = P Q( )I Q( )? P Ai( )I Ai( ) i ∑
- 37. 4-1. 実装編：決定木 (例)動物の分類 ②全ての説明変数に対し、各々の選択肢に遷移した 場合のエントロピーと遷移する確率を計算する。 質問Q2. 繁殖形態は? ΔI = I Q = Q2( )? P A1( )I A1( )? P A2( )I A2( ) = 1.52 ? 3 5 × 0.92 ? 2 5 × 0 =1.02 卵生 胎生 質問Q2の情報ゲイン ■では、Q2は最初の質問としてふさわしいか？ 動物名 食性(Q1) 繁殖携帯(Q2) 体温(Q3) クラス スズメ 肉食 卵生 恒温 鳥類 ライオン 肉食 胎生 恒温 ほ乳類 トカゲ 肉食 卵生 変温 は虫類 ダチョウ 草食 卵生 恒温 鳥類 ウシ 草食 胎生 恒温 ほ乳類 なかなか高得点ですね… ΔI = P Q( )I Q( )? P Ai( )I Ai( ) i ∑
- 38. 4-1. 実装編：決定木 (例)動物の分類 ②全ての説明変数に対し、各々の選択肢に遷移した 場合のエントロピーと遷移する確率を計算する。 質問Q1. 食生は? ΔI = I Q = Q1( )? P A1( )I A1( )? P A2( )I A2( ) = 1.52 ? 3 5 ×1.59 ? 2 5 ×1= 0.22 肉食 草食 質問Q1の情報ゲイン ■では、Q1は？ 動物名 食性(Q1) 繁殖携帯(Q2) 体温(Q3) クラス スズメ 肉食 卵生 恒温 鳥類 ライオン 肉食 胎生 恒温 ほ乳類 トカゲ 肉食 卵生 変温 は虫類 ダチョウ 草食 卵生 恒温 鳥類 ウシ 草食 胎生 恒温 ほ乳類 ほとんど得点ないです… ΔI = P Q( )I Q( )? P Ai( )I Ai( ) i ∑
- 39. 4-1. 実装編：決定木 (例)動物の分類 ②全ての説明変数に対し、各々の選択肢に遷移した 場合のエントロピーと遷移する確率を計算する。 質問Q2. 繁殖形態は? 卵生 胎生 Q2がもっともたくさんの情報を得られる。最初の問題にふさわしい！ 動物名 食性(Q1) 繁殖携帯(Q2) 体温(Q3) クラス スズメ 肉食 卵生 恒温 鳥類 ライオン 肉食 胎生 恒温 ほ乳類 トカゲ 肉食 卵生 変温 は虫類 ダチョウ 草食 卵生 恒温 鳥類 ウシ 草食 胎生 恒温 ほ乳類
- 40. 4-1. 実装編：決定木 (例)動物の分類 ③決定された最初の質問を質問リストから除き、次の質問を決める。 ?残された各質問に対し、②と同じ要領で確率とエントロピーをそれぞれ ?求め、情報ゲインを計算。 ④③を繰り返し行い、質問がなくなるまで到達させる。 動物名 食性(Q1) 繁殖携帯(Q2) 体温(Q3) クラス スズメ 肉食 卵生 恒温 鳥類 ライオン 肉食 胎生 恒温 ほ乳類 トカゲ 肉食 卵生 変温 は虫類 ダチョウ 草食 卵生 恒温 鳥類 ウシ 草食 胎生 恒温 ほ乳類 同様にして決定木を作成していく
- 41. 4-2. 実装編：ランダムフォレスト (1)学習データ/テストデータをブートストラップサンプリング? ?で抽出する。 (2)下記要領で、決定木をM本作る ? (2-1)全学習データの2/3を目安に、ランダムにデータ抽出する。 ??? 但し、各データセットで重複は許す(行を抽出するイメージ) ? (2-2)抽出したデータから、一部の説明変数だけを残したデータ ????セットを抽出する(列を抽出するイメージ) ? (2-3)抽出したデータセットを元に決定木を作成する ??? ただし使用した説明変数は、決定木と一緒に記録しておく。?? (3)テストデータを用いて予想を行う。作成したM本の決定木に対し ?使用した説明変数でそれぞれ予想し、結果は多数決/平均で決める。
- 42. 5. サンプル実装 https://github.com/watanabetanaka/randomForest/ ?rf.R ：ランダムフォレストの実装(R単体で実装) ?iris.dat ：ランダムフォレストで使用しているデータ ?decisionTree.php ：決定木単体の実装(バグありです) ?animals.dat ：決定木単体で使用しているデータ 時間があればデモします。 git使えない人向けDL用URL http://watatana.com/rf.tar.gz
- 43. 参考文献 ? Breiman, L.: Random Forests,Machine Learning,Vol. 45, No. 1, pp. 5?32 (2001). (http://link.springer.com/article/10.1023%2FA%3A1010933404324) ? 濱田康一(http://www.slideshare.net/hamadakoichi/randomforest-web)
- 44. ????? おわり ?????