パターン認識論 #8

パターン認識論 第８回 いとう あきのり 1

決定木 ◦If-thenルールだけで分類をする x<2 Yes No y>3 Yes No x<4 Yes No y>2.8 Yes No 2

決定木 ◦決定木のよいところ ◦ いくらでもノードを作ってよければ、どん な学習データも完全に分類できる ◦ 過学習の問題がある ◦ 連続値、離散値、カテゴリーのいずれにつ いても分類が可能 3

カテゴリーの決定木 ◦メタボ判定 ◦ 入力データ𝑥 = (𝐺, 𝑊)=(性別、腹囲) G=男性？ Yes No W≥85? Yes W ≥ 90? No Yes No 4

決定木の学習 ◦概略 ◦ 最初は全データをどちらかの（最も学習 データが多い）クラスに分類する ◦ データを2つに分ける「質問」を用意する ◦ ある質問を選び、その質問に対するYes/No でデータを2つに分けたとき、分けられた データの「質」を測る ◦ 最も「質」が向上する質問を選び、それを 使ってデータを2つに分ける ◦ 分けられた２つのデータに対して以下同文 5

決定木の学習 全学習データ 最もサンプルが多 いクラスに分類 次に分けるべき データを選ぶ 質問１ 質問２ 質問３ 2つに分けたデータの「質」が最もよく なる質問を選ぶ 質＝それぞれのデータ内にできるだ け同じクラスのデータだけがある 質問ｎ 質問ｎ 質問ｎ 質問ｎ 質問１ 質問２ 質問３ 6

考慮すべきこと ◦質問をどう用意するか ◦データの「質」 ◦ 何を持って「質」と考え、どう定義するか ◦分割すべきデータをどう選ぶか ◦分割をいつ停止するか ◦ いったん分割したデータをもう一度併合し 直すこともある 7

数学的準備 ◦学習データ集合 𝐷𝑛 :𝑛 は木のノード ◦𝑁 𝐷𝑛 , 𝜔 : 𝐷𝑛 に含まれるクラス𝜔のサン プル数 ◦ 𝑃 𝜔 𝐷𝑛 = 𝑁(𝐷𝑛 , 𝜔)/ 𝐷𝑛 ◦𝑄𝑦 𝐷𝑛 , 𝑞 : 𝐷𝑛 の中で、質問qに対して yesであるサンプルの集合 ◦𝑄𝑛 𝐷𝑛 , 𝑞 : 𝐷𝑛 の中で、質問qに対して noであるサンプルの集合 8

データの質 ◦あるデータの中に、単一クラスのサン プルだけがあればよい ◦ 同じクラスのサンプルだけから成る場合に 最良 ◦ すべてのクラスのサンプルが同数含まれて いる場合に最悪 ◦これを「不純度」(impurity) 𝐼 𝐷 で表 す ◦ 低いほどよい 9

不純度(impurity) ◦定義はいくつかある ◦ジニ関数 ◦ 𝐼 𝐷 = 1 − σ𝜔 𝑃 𝜔 𝐷 2 ◦エントロピー ◦ 𝐼 𝐷 = − σ𝜔 𝑃 𝜔 𝐷 log 𝑃(𝜔|𝐷) ◦誤分類率 ◦ 𝐼 𝐷 = 1 − max 𝑃(𝜔|𝐷) 𝜔 10

分割したときの良さ ◦分割することで不純度が下がるのが望ま しい ◦ 分割後にあるサンプルがYesかNoのデータに含 まれる確率 ◦ 𝑃 𝑎 𝐷, 𝑞 𝑄𝑎 (𝐷,𝑞) = , 𝑎 ∈ {𝑦, 𝑛} 𝐷 ◦ 不純度の減少量 ◦ 𝐺 𝐷, 𝑞 = 𝐼 𝐷 − σ𝑎∈ 𝑦,𝑛 𝑃 𝑎 𝐷, 𝑞 𝐼 𝑄𝑎 𝐷, 𝑞 ◦ これは「データDを質問qで分割したときの良さ」 11

質問を用意する ◦ データが多次元連続値である場合 ◦ 𝑥 = (𝑥1 , … , 𝑥𝑛 ) ◦ ある次元の値の大小で分ける ◦ 𝑞 = (𝑗, 𝜃) ◦ 𝑄𝑦 𝐷, 𝑞 = 𝑥 𝑥 ∈ 𝐷, 𝑥𝑗 < 𝜃 ◦ 𝑄𝑛 𝐷, 𝑞 = {𝑥|𝑥 ∈ 𝐷, 𝑥𝑗 ≥ 𝜃} ◦ 線形識別 ◦ 𝑞 = (𝑤, 𝑏) ◦ 𝑄𝑦 𝐷, 𝑞 = 𝑥 𝑥 ∈ 𝐷, 𝑤 𝑡 𝑥 + 𝑏 ≥ 0 ◦ 𝑄𝑛 𝐷, 𝑞 = {𝑥|𝑥 ∈ 𝐷, 𝑤 𝑡 𝑥 + 𝑏 < 0} 12

質問を用意する ◦データがカテゴリである場合 ◦ 𝑥 ∈ 𝑋 = {𝑥1 , … , 𝑥𝑁 } ◦ある値かどうか ◦ 𝑄𝑦 𝐷, 𝑞 = 𝑥 𝑥 = 𝑥𝑞 ◦ 𝑄𝑛 𝐷, 𝑞 = {𝑥|𝑥 ≠ 𝑥𝑞 } ◦部分集合 ◦ 𝑄𝑦 𝐷, 𝑞 = 𝑥 𝑥 ∈ 𝑋𝑞 , 𝑋𝑞 ⊂ 𝑋 ◦ 𝑄𝑛 𝐷, 𝑞 = 𝑥 𝑥 ∈ 𝑋 ∖ 𝑋𝑞 , 𝑋𝑞 ⊂ 𝑋 13

アルゴリズム ◦現在の決定木のすべての葉ノード𝑙について ◦ 𝑙,መ 𝑞ො = arg max 𝐺 𝐷𝑙 , 𝑞 𝑙,𝑞 ◦停止基準が満たされるならば終了 መ ◦ 𝑙に2つの子ノードを作り，それぞれに 𝑄𝑦 𝐷𝑙መ , 𝑞ො , 𝑄𝑛 𝐷𝑙መ , 𝑞ො を割り当てる ◦最初に戻る 14

停止基準 いくつか考えられる ◦一定回数以上分割したら終了 ◦分割による良さの向上𝐺(𝐷𝑙መ , 𝑞)がある値 ො より小さくなったら終了 ◦ノードに割り当てられるサンプル数 |𝐷𝑙መ |がある値より小さくなったら終了 15

演習 Irisデータセットで４つの次元それぞれを選ん だ時に、最適な閾値とそのときの不純度減少 分を求めよう。 ◦ データセット𝐷, 𝐷 = 150 ◦ 特徴量を𝒙𝑖 ∈ 𝐷とする（1 ≤ 𝑖 ≤ 150） ◦ ラベルを𝑦𝑖 ∈ {𝑠𝑒𝑡𝑜𝑠𝑎, 𝑣𝑒𝑟𝑠𝑖𝑐𝑜𝑙𝑜𝑟, 𝑣𝑖𝑟𝑔𝑖𝑛𝑖𝑐𝑎}とする ◦ 選択する次元を𝑑とする（1 ≤ 𝑑 ≤ 4） ◦ 選択した次元での閾値を𝜃とする 16

演習 ◦ 不純度の定義を（たとえば）誤分類率にする 𝑁(𝐷,𝜔) ◦𝑃 𝜔 𝐷 = , 𝜔 ∈ {𝑠𝑒𝑡𝑜𝑠𝑎, 𝑣𝑒𝑟𝑠𝑖𝑐𝑜𝑙𝑜𝑟, 𝑣𝑖𝑟𝑔𝑖𝑛𝑖𝑐𝑎} |𝐷| ◦ 𝐼 𝐷 = 1 − max 𝑃(𝜔|𝐷) 𝜔 ◦ データを分割する ◦ 𝑄𝑦 𝐷, 𝑑, 𝜃 = 𝑥 𝑥𝑑 < 𝜃 ◦ 𝑄𝑛 𝐷, 𝑑, 𝜃 = 𝑥 𝑥𝑑 ≥ 𝜃 ◦ 𝐼 𝑄𝑦 𝐷, 𝑑, 𝜃 መ + 𝐼 𝑄𝑛 𝑆, 𝑑, 𝜃 が最小となる𝜃 = 𝜃を求める ◦ 𝐼 𝑄𝑦 𝐷, 𝑑, 𝜃መ መ + 𝐼 𝑄𝑛 𝑆, 𝑑, 𝜃መ が最小となる𝑑 = 𝑑を求める መ 𝜃መ ◦ 𝐺 𝐷 = 𝐼 𝐷 − 𝐼 𝑄𝑦 𝐷, 𝑑, መ 𝜃መ + 𝐼 𝑄𝑛 𝑆, 𝑑, ◦ 最適な次元とその時の閾値はどうなるか。 17

演習 計算はExcelでもできる （もちろんプログラムを書いてもよい） ここから上の各カ テゴリのデータ数 この次元でソート Sepal.Length Sepal.Width Petal.Length 5 2 Petal.Width 3.5 Species ここから上のデー ここから下のデー タの不純度 タの不純度 setosa versicolor virginica I(Qy) 1versicolor 0 1 0 I(Qn) I(Qy)+I(Qn) 総合不 0 0.662162 0.662162162 純度 0 0.659864 0.659863946 0 0.66443 0.66442953 6 2.2 4 1versicolor 0 2 0 6.2 2.2 4.5 1.5versicolor 0 3 0 6 2.2 5 1.5virginica 0 3 1 0.25 0.657534 0.907534247 4.5 2.3 1.3 0.3setosa 1 3 1 0.4 0.662069 1.062068966 5 2.3 3.3 1versicolor 1 4 1 0.333333 0.659722 0.993055556 5.5 2.3 4 1.3versicolor 1 5 1 0.285714 0.657343 0.943056943 6.3 2.3 4.4 1.3versicolor 1 6 1 4.9 2.4 3.3 1versicolor 1 7 1 0.222222 0.652482 0.874704492 5.5 2.4 3.7 1versicolor 1 8 1 5.5 2.4 3.8 1.1versicolor 1 9 1 0.181818 0.647482 0.829300196 5.1 2.5 3 1.1versicolor 1 10 1 0.166667 0.644928 0.811594203 5.6 2.5 3.9 1.1versicolor 1 11 1 0.153846 0.642336 5.5 2.5 4 1.3versicolor 1 12 1 0.142857 0.639706 0.782563025 0.25 0.2 これが最小の 点を探す 0.65493 0.904929577 0.65 0.85 0.79618192 18

アンサンブル学習 ◦複数の識別器を組み合わせて判定する ◦識別関数 ◦ 𝑔 𝑥 = σ𝑘 𝑤𝑘 𝑔𝑘 (𝑥) ◦ 𝑔𝑘 (𝑥)：弱識別器 ◦ 𝑔(𝑥)：強識別器 ◦次の場合に性能が改善 ◦ 複数の弱識別器のエラー率が低い(<50%) ◦ 複数の弱識別器が独立 19

バギング(Bagging) ◦1つの学習データから複数の学習デー タを生成→複数の弱識別器を構成 ◦学習データ𝐷 = {𝑥 1 , … , 𝑥 𝑛 } ◦ブートストラップサンプル ◦ 𝐷𝑘 = 𝑥 𝑛𝑘,1 , … 𝑥 𝑛𝑘,𝑛 ◦ 1 ≤ 𝑛𝑘,𝑖 ≤ 𝑛 乱数で決める 重複を許す抽出 ◦データ𝐷𝑘 から弱識別器𝑔𝑘 (𝑥)を学習 ◦𝑔 𝑥 1 = σ𝑘 𝑔𝑘 (𝑥) 𝑛 20

バギング(Bagging) ◦利点 ◦ 方法が単純 ◦ 単一の弱識別器よりも性能が改善 ◦ 過学習が起きにくい ◦欠点 ◦ 後述のブースティングより性能が低い 21

ブースティング(Boosting) ◦𝑔 𝑥 = σ𝑘 𝑤𝑘 𝑔𝑘 (𝑥) = σ𝑘 𝑤𝑘 𝑔(𝑥; 𝜃𝑘 ) ◦重み𝑤𝑘 とパラメータ𝜃𝑘 を最適化する ◦AdaBoost (Adaptive Boosting) アル ゴリズムが有名 ◦ 重みの最適化は難しいので，弱識別器を1 個ずつ増やしながら逐次最適化 22

AdaBoost ◦準備 ◦ 学習データ 𝑥1 , … , 𝑥𝑛 ，正解 𝑦1 , … , 𝑦𝑛 ◦ 𝑦𝑖 ∈ {1, −1} ◦ 識別関数 𝑔 𝑥𝑖 ; 𝑊, Θ = σ𝑘 𝑤𝑘 𝑔(𝑥𝑖 , 𝜃𝑘 ) ◦ 正しい識別→ 𝑦𝑖 𝑔 𝑥𝑖 ; 𝑊, Θ > 0 ◦ 損失関数 ◦ 𝐿 = σ𝑖 exp −𝑦𝑖 𝑔 𝑥𝑖 ; 𝑊, Θ → min 23

損失関数 ◦ 𝐿 = σ𝑖 exp(−𝑦𝑖 𝑔 𝑥𝑖 ) = σ𝑖 exp −𝑦𝑖 σ𝑘 𝑤𝑘 𝑔𝑘 (𝑥𝑖 ) ◦ 𝛾𝑘 𝑥𝑖 , 𝑦𝑖 = exp −𝑦𝑖 𝑤𝑘 𝑔𝑘 𝑥𝑖 とおくと ◦ 𝐿 = σ𝑖 ς𝑘 𝛾𝑘 (𝑥𝑖 , 𝑦𝑖 ) ◦ 𝐿𝑚 = σ𝑖 ς𝑚 𝑘=1 𝛾𝑘 (𝑥𝑖 , 𝑦𝑖 ) とする ◦ 𝐿𝑚 = σ𝑖 𝛾𝑚 (𝑥𝑖 , 𝑦𝑖 ) ς𝑚−1 𝑘=1 𝛾𝑚−1 (𝑥𝑖 , 𝑦𝑖 ) ◦ このときmを逐次的に決める 24

損失関数 ◦𝐿𝑚 = σ𝑖 𝛾𝑚 (𝑥𝑖 , 𝑦𝑖 ) ς𝑚−1 𝑘=1 𝛾𝑚−1 (𝑥𝑖 , 𝑦𝑖 ) こっちを求めたい ここまで決まってる =𝐷𝑚−1 𝑖 とおく ◦𝐿𝑚 = σ𝑖 𝛾𝑚 𝑥𝑖 , 𝑦𝑖 𝐷𝑚−1 (𝑖) 識別を間違っている場合に 大きい（誤識別率） 25

損失関数 ◦𝐿𝑚 = σ𝑖 𝐷𝑚−1 (𝑖)𝛾𝑚 𝑥𝑖 , 𝑦𝑖 ◦ = σ𝑖 𝐷𝑚−1 𝑖 exp(−𝑦𝑖 𝑤𝑚 𝑔𝑚 𝑥𝑖 ) ◦ここで𝐿𝑚 を計算するときの誤り率が大 きいほどexp(−𝑦𝑖 𝑤𝑚 𝑔𝑚 𝑥𝑖 )を小さくす る 1 1−𝜖𝑚 ◦ 𝑤𝑡 = ln 2 𝜖𝑚 ◦ 𝜖𝑚 : m番目の 識別誤り率 26

AdaBoostアルゴリズム 1. サンプル分布 𝐷1 𝑖 = 1/𝑛とおく 2. For 𝑘 ← 1, … , 𝑚 do 3. 分布𝐷𝑘 (𝑖)のもとで，誤識別率の期待 値を最小化する識別器𝑔𝑘 (𝑥)を学習 4. 𝑔𝑘 (𝑥)の誤識別率𝜖𝑘 を算出 1 1−𝜖𝑚 5. 𝑤𝑡 = 2 ln 𝜖 𝑚 6. 𝐷𝑘+1 (𝑖) ← 𝐷𝑘 𝑖 exp −𝑦𝑖 𝑤𝑘 𝑔𝑘 𝑥𝑖 7. End for /𝑍𝑡 27

誤識別率の期待値を最小化？ ◦通常の場合（誤り率最小化） ◦ σ𝑖 𝑦𝑖 − 𝑔(𝑥𝑖 ) を最小にする𝑔(𝑥)を探す （𝑔 𝑥 ∈ {1, −1}) ◦誤りの期待値最小化 ◦ σ𝑖 𝐷𝑘 (𝑖) 𝑦𝑖 − 𝑔(𝑥𝑖 ) を最小にする𝑔(𝑥)を探 す 28

AdaBoost ◦その他コメント ◦ 弱識別器には何を使ってもよいが，決定木 が使われることが多い ◦ 弱識別器に線形識別を使うと全体も線形識別にな る→非線形識別を使うべき ◦ 弱識別器のエラー率が50%を超えたら強制 終了 29

Random Forests 決定木のアンサンブル学習の一種 ➢Baggingの発展形 ➢Baggingは学習サンプルの中からサン プリングして複数の決定木を学習 ➢Random Forestsは学習サンプルの中 からサンプリングすると同時に，利用 する特徴ベクトルの次元もサンプリン グする 30

Random Forests 学習 サンプル Bagging 31

Random Forests 学習 サンプル Random Forests 32