XGBoostを数式で理解しようとするLT

Transcript

1. © 2019 Chura DATA inc. PROPRIETARY & CONFIDENTIAL. XGBoostを数式で理解しようと するLT 発表者 兼城大（見習いデータサイエンティスト）
2. 動機 © 2019 Chura DATA inc. PROPRIETARY & CONFIDENTIAL. ・XGBoostって響きがかっこいい ・何がeXtremeなんだ？ ・Kaggle上位者が使ってるっぽい ・ハイパーパラメータたくさんでよくわからん ・LightGBMの方が流行っぽいぞ（小声） ・XGBoostの中身が知りたい そうだ！勉強しよう！！
3. AGENDA XGBoostを数式で理解しようとするLT １章：ざっくり掴むXGBoost (３スライド) ２章：XGBoostを数式で理解しようとする （7スライド） まとめ：（１スライド） 展望：（１スライド） 主な参考・引用文献：（１スライド） 目次
4. ざっくり掴むXGBoost 1/3 ・バイアス（Bias）とバリアンス（Variance） （ランダムフォレストとXGBoostのちがいを理解するために） © 2019 Chura DATA inc. PROPRIETARY & CONFIDENTIAL. #バイアス（Bias） →実際値と予測値との誤差の平均 （真の値とのずれ） #バリアンス（Variance） →予測値の散らばり度合い 例）②は高バイアス→未学習 ③は高バリアンス→過学習 ※バイアスとバリアンスはトレードオ フの関係にある
5. ざっくり掴むXGBoost 2/3 ・バギングとブースティングの違い（ランダムフォレストとXGBoostのちがいを理解するために） © 2019 Chura DATA inc. PROPRIETARY & CONFIDENTIAL. #バギング → Bootstrap Aggregating（ブートストラップ 法を総計したもの）の略。 →バリアンスを減らす（過学習を防ぐ） →例）ランダムフォレスト（樹木モデルのバギング） #ブートストラップ法 →学習データを復元抽出でランダムに抽出 し、学習する。 #ブースティング →基本モデルの間違った予測に焦点を当てて、 「重み」を加味して次のモデルを改善する。 →バイアスを減らす（未学習を防ぐ） →例）XGBoost（樹木モデルのブースティング） ¥ 引用 https://www.codexa.net/what-is-ensemble-learning/ 引用 Géron, Aurélien. "Hands on Machine Learning with scikit-learn and Tensorflow." (2017)
6. ざっくり掴むXGBoost ・XGBoostとは XGBoost(eXtreme Gradient Boosting)は、樹木モデルの勾配ブー スティングの実装の１つ。 © 2019 Chura DATA inc. PROPRIETARY & CONFIDENTIAL. XGBoostのモデル構築の仕組み （１）決定木を１つ作る。(ො y ) （２）１つ目の決定木の予測値と実測値の差をとる。 （誤差ε = - ො y ） （３）（２）の誤差ε を目的変数として、２つ目の 決定木を構築する。（誤差の予測値ෝ ε ） （４）（３）と（１）の和を取る。（ ො y = ො y + ෝ ε ) （５）実測値 との差をとる。（誤差ε = - ො y ） （６）（５）の誤差を目的変数として、３つ目の決 定木を構築する。（誤差の予測値ෝ ε ） （７）これを繰り返してN本の決定木を作る。 ※(3),(6)を構築するアルゴリズムがミソ。 →どうやって誤差を予測する決定木t を作るの？？ （１） （２） （３） （４） （５） （６）
7. XGBoostを数式で理解しようとする１/7 © 2019 Chura DATA inc. PROPRIETARY & CONFIDENTIAL. ・決定木 の作り方 min () ( ) = min σ =1 ( , ො (−1) + ( )) + + 1 2 損失関数 罰則項 （過学習を防ぐため） ：t本目の決定木 ：番目のデータ(個の説明変数） ＝（ 1 , ⋯ , ), ＝1, ⋯ , ：番目のデータの実測値（ ＝1, ⋯ , ） ො (−1)： ( − 1)本目までの決定木で作られた予測値 ただし、ො (0)=0, 1 = ො (1)とする。 ：二乗誤差関数 (, )= − 2 ：本目の決定木による予測誤差 ＝ ෝ ε () ※誤差を目的変数にしている。 ：Tの大きさに対するペナルティ ：決定木を構築した時の最終ノードの数 ： の大きさに対するペナルティ ：決定木が返すことのできる値のベクトル 【損失関数】 【罰則項】 （次スライドのポイント） 前までの結果（t-1本目までの結果）を使って、 どのようにL() ( )を最小にする決定木 を 構築すれば良いか 2
8. XGBoostを数式で理解しようとする2/7 © 2019 Chura DATA inc. PROPRIETARY & CONFIDENTIAL. ・決定木 の作り方 （ステップ１）決定木 が 返すべき値∗を求める （ステップ２）ステップ１の∗をも とに、決定木 の分岐の仕方を決める min () ( ) = min σ =1 ( , ො (−1) + ( )) + + 1 2 2 3 ∗ 4 ∗ 2 ∗ 1 ∗ これで決定木 が作れる。 まさに、 eXtreme!
9. min ෨ () ( ) = min σ =1 ( − 2 ( −ො (−1) ) + ) + Ω( ) XGBoostを数式で理解しようとする3/7 © 2019 Chura DATA inc. PROPRIETARY & CONFIDENTIAL. （ステップ１）決定木 が返すべき値∗について min () ( ) = min σ =1 ( , ො (−1) + ( )) + Ω( ) ＝ min σ =1 ( − (ො (−1) + ( ))) + Ω( ) ※引用文献には、「損失関数を に関して、0の周りで２次のテーラー展開を行う。」 とあったが、何度計算しても元の関数と変わらなかったため、そのまま計算する。 Ω( )＝ + 1 2 2 2 = min σ=1 (( −ො (−1)) − 2 ( −ො (−1)) + ) + Ω( ) 2 2 最適化に関係のない項、つまり に関わらない項を除いたものを෨ L()とすると、 2 = min σ =1 ( + ) + Ω( ) 2 ＝ −2( −ො (−1))
10. XGBoostを数式で理解しようとする4/7 © 2019 Chura DATA inc. PROPRIETARY & CONFIDENTIAL. （ステップ１）決定木 が返すべき値∗について min ෨ () ( ) = min σ=1 ( + 2 ) + Ω( ) = min σ=1 ( + 2 ) + + 1 2 ＝min σ=1 T (σ∈ + σ∈ ) + + 1 2 σ=1 2 = min σ=1 T (σ∈ + ) + + 1 2 σ=1 2(ℎ は と出力されるノード に含まれるデータの個数) = min σ=1 T (σ∈ + ℎ 2 + 1 2 2) + = min σ=1 T (σ∈ + 1 2 (2ℎ + ) 2) + 2 ∗＝ − σ∈ 2ℎ+ ෨ ()を で微分したものを０とおくと、最適解 ∗は、 となる。これで、決定木 が返すべき値 ∗がわかった。 4 ∗ 2 ∗ 1 ∗ （式の展開のポイント） ・Σをノード 別に計算する ・ 2 を 2で表す ・ノード に含まれるデータの個数をℎ と表す （例：上図のノード３(3 )では、 ℎ3 = 6 ） 3 ∗
11. XGBoostを数式で理解しようとする5/7 © 2019 Chura DATA inc. PROPRIETARY & CONFIDENTIAL. （ステップ１）決定木 が返すべき値∗について（この式が意味するもの（小話）） ∗＝ − σ∈ 2ℎ+ ＝ −2( −ො (−1)) ℎ は と出力される集合 に含まれるデータの個数 ： の大きさに対するペナルティ （罰則項Ω( )＝ + 1 2 の式に出てくる） ∗：決定木 が返すべき値∗のj番目要素（ノード の返すべき出力結果） (1 , 2 , 3 , 4 , 5 ) (1 , 2 , 3 ) (4 , 5 ) （２） ＝4としたときの 1 ∗, 2 ∗の値は、 1 ∗＝ − σ∈1 2ℎ1+ ＝ − −2 1 + −2 1 + −2(1) 2×3+4 = 0.6 2 ∗＝ − σ∈2 2ℎ2+ ＝ − −2 0 + −2 0 + −2(0) 2×2+4 = 0 となり、1 ∗の値が直感的によさそうな値 よりも小さくなっていることがわかる。 →過学習を防いでいる。 罰則項のパラメータの値 によって出力結果 1 ∗, 2 ∗ の値が異なる。 左図において、(1 , 2 , 3 , 4 , 5 ) = 1,1,1,0,0 として、(1 , 2 , 3 ) = 1,1,1 ， 4 , 5 = (0,0)に分かれた とする。このとき、1 ＝1、 2 = 0 と出力されることが直感的によさそうだが・・・ 2 ∗ 1 ∗ （１） ＝0としたときの、 1 ∗, 2 ∗ の値は、 1 ∗＝ − σ∈1 2ℎ1+ ＝ − −2 1 + −2 1 + −2(1) 2×3+0 = 1 2 ∗＝ − σ∈2 2ℎ2+ ＝ − −2 0 + −2 0 + −2(0) 2×2+0 = 0 となり、直感的によさそうな出力と、 1 ∗, 2 ∗の値が一致している。 （ 実は、＝0のときは算術平均と同 じ式になっている）
12. XGBoostを数式で理解しようとする6/7 © 2019 Chura DATA inc. PROPRIETARY & CONFIDENTIAL. （ステップ２）説明変数の分岐方法 ∗＝ − σ∈ 2ℎ+ ෨ () ＝ − 1 2 σ=1 (σ∈ ) 2ℎ+ + 2 を目的関数෨ ()に代入すると、 が得られる。 【分岐方法の考え方】 目的関数෨ ()が小さくなるように、 分岐するためには、分岐前෨ () と 分岐後෨ () のそれぞれの目的関数 の差(෨ () ー ෨ () )が最大になる ように分岐すれば良い。 大 小
13. XGBoostを数式で理解しようとする7/7 © 2019 Chura DATA inc. PROPRIETARY & CONFIDENTIAL. （ステップ２）説明変数の分岐方法（具体例） (100,1,2) (100) (1,2) (100,1,2) (2) (100,1) 1 2 (4×1002 2+λ + 4×32 4+λ ー 4×1032 6+λ ) 1 2 (4×12 2+λ + 4×1022 4+λ ー 4×1032 6+λ ) (1) (100,1,2) (100,2) 1 2 (4×22 2+λ + 4×1012 4+λ ー 4×1032 6+λ ) ෍ ℎ = 2ℎ (ℎ はノード に含まれるデータの個数) ＝ −2( −ො (−1)) ： 出力結果に対するペナルティ (1) (2) (3) 実際に、(100,1,2)という誤 差に対する分岐を考えた とき、すべての考えられ る組み合わせで ෪ ( () ー ෨ () )を計算すると、(1) の場合が最も大きくなる。 n個の要素を2組に分ける ときの考えられる組み合 わせ=(2−1 − 1)通り
14. XGBoostを数式で理解しようとする7/7 © 2019 Chura DATA inc. PROPRIETARY & CONFIDENTIAL. XGBoostのアルゴリズム XGBoostのアルゴリズム（簡易版） （ステップ２）説明変数の分岐方法 前スライドの望ま しい分岐を行うた めの式と同じ→
15. XGBoostを数式で理解しようとする（まとめ） © 2019 Chura DATA inc. PROPRIETARY & CONFIDENTIAL. ・決定木 の作り方 （ステップ１）決定木 が 返すべき値を求める （ステップ２）ステップ１のwをもと に、決定木 の分岐の仕方を決める min () ( ) = min σ =1 ( , ො (−1) + ( )) + + 1 2 これで決定木 が作れる。 まさに、 損失関数 罰則項 （過学習を防ぐため） 2 eXtreme!
16. 主な参考・引用文献 XGBoostの概要 - ともにゃん的データ分析ブログ http://kefism.hatenablog.com/entry/2017/06/11/182959 →本当にお世話になったブログ。このLT資料作成にあたって、５０回はこの サイトに訪問させていただいた。 XGBoost: A Scalable Tree Boosting System https://arxiv.org/pdf/1603.02754.pdf →XGBoostのアルゴリズムを詳説した英語の論文。もっと知りたい人は是非 とも読んでいただきたい。 © 2019 Chura DATA inc. PROPRIETARY & CONFIDENTIAL.