はじめてのパターン認識

11章

Created by 2GMon

話の流れ

  • ノーフリーランチ定理
  • 決定木
  • バギング
  • AdaBoost
  • ランダムフォレスト

今回は細かい理論の話は結構端折ってますm(__)m

ノーフリーランチ定理

全ての識別問題に対して、他の識別器より識別性能が良い識別器は存在しないことを主張する定理

ある識別器が他よりも汎化性能が良いと言えるのは、特定の問題に関してのみで、対称の問題領域を指定しなければ 汎化性能は全て同じになる

問題領域が規定されても1つの識別器で良い性能が得られない場合は、複数の識別器を組み合わせる場合がある

決定木(1/3)

単純な識別規則を組み合わせて複雑な識別境界を得る方法

特徴軸ごとに識別規則に基づいて判断することで識別が可能になる

識別の仮定は決定木として表現ができる

根ノードと内部ノードを合わせた非終端ノードで識別を行って次のノードを辿っていき、到達した終端ノード によって属するクラスが決められる

決定木(2/3)

決定木を構成する方法にはボトムアップ型とトップダウン型がある

現在はトップダウン型が主流

  • ボトムアップ型
    • ある1つの学習データを正しく識別できる特徴の集合を探して特殊な識別規則を作り、特徴に対する制約を緩めながら 他の学習データも正しく識別できるように規則を一般化していく
  • トップダウン型
    • 根ノードで全ての学習データをできるだけ誤りの少ないように分けられる特徴を探して特徴空間を2分割し、 分けられた学習データを誤りが少ないように分けられる特徴を探して2分割することを繰り返す

決定木(3/3)

トップダウン型で決定木を構成するには以下について考える必要がある

  • 各ノードにおいて特徴空間分割規則を構成するための特徴軸と閾値の選択
  • 1つの終端ノードに1つの学習データが含まれるまで分割を繰り返すのか、複数のクラスのデータが含まれていてもよいのかなど
  • 終端ノードに対する多数決によるクラスの割当


代表的な手法にはCARTとID3や後継のC4.5と呼ばれるものがある

CARTは2分木しか認めていないが、C4.5は多分木による分割を認めている

バギング

学習データのブートストラップサンプルを用いて複数の識別器を学習させ、新しい入力データのクラスはそれらの識別器の多数決で決める方法

個々の識別器の性能はランダム識別器よりも少し良ければいいので、弱識別器とよばれる

決定木は学習データの少しの変化で識別器の性能が大きく変化してしまうので不安定な識別器だが、複数の決定木からの結果の多数決を取ることで 1つの決定木よりも安定で性能の良い識別器を構成できる

ブートストラップサンプルによる学習なので、個々の識別器の学習は独立に並列に実行できる

ブートストラップサンプルのデータが偏った場合、決定木間の性能が似通ってしまい、十分に性能強化できない場合がある

AdaBoost(1/2)

複数の弱識別器を用意して、学習を直列的にし、前の弱識別器の学習結果を参考にしながら1つずつ弱識別器を学習する

弱識別器の学習データはそれまでの学習結果から、次の学習にとってもっとも有益なものが選ばれる

各弱識別器は学習データに対する誤り率が $\epsilon \leq 1/2 - \gamma \;\; (\gamma > 0)$ をみたすように学習される

AdaBoost(2/2)

弱識別器の学習結果に従って、誤った学習データに対する重みを大きくし、正しく識別された学習データに対する重みを小さくすることで 後に学習する識別器ほど、誤りの多い学習データに集中して学習するようにする

AdaBoostは2クラス問題の識別器で、多クラス問題に対応するためには$K-1$個の1対多識別器を構成する必要がある

弱識別器の数が大きいと過学習が生じるので、交差検定などで選ぶ必要がある

ランダムフォレスト(1/2)

バギングは、ブートストラップサンプルの偏りによって、生成された決定木の相関が高くなる

一般に、分散$\sigma^2$をもつ$M$個の独立な確率変数$X_i$の平均 $\bar{X} = 1/M \sum_{ i = 1 }^{ M } X_i $ の分散は $Var\{ \bar{X} \} = \sigma^2 / M $ となるが、任意の2つの確率変数間に正の相関$\rho$がある場合には、平均の分散は $$ Var\{\bar{X}\} = \frac{ 1 - \rho }{ M } \sigma^2 + \rho \sigma^2 $$ となる

ブートストラップサンプル数の$M$を増やせば第1項は減るが、第2項は減らない

ランダムフォレストは$\rho$を減らす仕組みを入れてバギングを強化した手法

ランダムフォレスト(2/2)

決定木の各非終端ノードにおいて識別に用いる特徴をあらかじめ決められた数だけランダムに選択することで、 相関の低い多様な決定木を生成できるようにした手法

ランダムフォレストは多数決によって多クラス問題に自然に拡張できる