『わかりやすいパターン認識』第5章特徴の評価とベイズ誤り確率 5.4 ベイズ誤り確率と最近傍決定則発表日：5月23日（金）発表者：時田陽一最近傍決定則の誤り確率  ベイズ誤り確率を求めたい確率密度関数が既知の場合解析的に求めることができる一般に確率密度関数は未知観測できるものは、確率密度関数の実現値（確率密度関数に基づいて生成される個々のパターン） NN法によってベイズ誤り確率 eB の近似が可能!! c   eB  eN  eB  2   eB   2eB c 1   • eN：NN法の誤り確率 • c ：クラス数 • NN法の誤り確率はベイズ法によるものの2倍を超えないベイズ誤り確率と最近傍決定則ベイズの誤り確率： eB 1 2 『分布の重なり』が誤り確率を表す最近傍決定則 D1 D2  D1  D2  x  1  D1  D2  x   2 2クラスにおける近似の式の導出〔1〕 • クラスのわかっているn個のプロトタイプを用意: • 入力パターンxに対する最近傍をx’で表す x1 , x2 ,, xn x  x1 , x2 ,, xn  • 入力パターンとその最近傍の属するクラスが異なる場合に誤りが生ずる（NN法） • NN法でパターンxを識別したときの誤り確率（n個のプロトタイプ）：en (x) en ( x)  P1 | xP2 | x  P2 | xP1 | x • 起こりうる全てのxに対する誤り誤差：en en   en ( x) p ( x)dx • これらを用いて eB , eN の関係を求める 2クラスにおける近似の式の導出〔2〕 • プロトタイプ数nを無限大に近づけるとする lim x'  x n  lim P n  i | x'  P i | x  上式より、 lim en ( x)  2P1 | x P 2 | x  n   2 P1 | x 1  P1 | x   2eB ( x)1  eB ( x)  ただし、次の関係式を用いた eB ( x)  minP1 | x , P 2 | x   minP1 | x ,1  P1 | x  1  2 最近傍x’は入力パターンx に限りなく近づくとする 2クラスにおける近似の式の導出〔3〕 • NN法の誤り確率： eN eN   2eB ( x)1  eB ( x)  p ( x)dx eN  lim en n       lim en ( x)  p( x)dx  n     2eB ( x)1  eB ( x)  p( x)dx  2eB 1  eB   2 VareB ( x)   2eB 1  eB  eB (x) の分散   eB ( x)  eB ( x)1  2eB ( x) p ( x)dx  eB   eB ( x)1  2eB ( x)  p ( x)dx  eB 1 eB ( x )  2 2クラスにおける近似の式の導出〔4〕 • 近似の式の導出〔3〕よりまとめると以下のようになる eB  eN  2eB 1  eB   2eB 先に示した近似の式の3項目に c=2 を代入することでこの関係が導かれる coffee break ベイズ決定則による決定境界は事後確率が等しい以下の式を満たす点として定まる P(1 ) p( x |  2 ) P( 2 ) p( x |  2 )  p( x) p ( x) 0 P1 | x   P 2 | x   誤識別は決定境界付近で発生することが多い 決定境界付近ではパターンの確率密度が低い例． p( x | i ) が正規分布で表される場合、正規分布の裾野近くに設定される  NN法のためにプロトタイプを収集したとする確率密度の高いところに多くのプロトタイプが集まる (決定境界付近には少数のプロトタイプしか集まらない) NN法で高い識別率を達成するためには決定境界を決めるのに寄与するプロトタイプのみを残せばよいパターンの分布を忠実に反映することと高い識別性能を実現することが相反する要求となっている編集アルゴリズム(効率的な識別が可能な新しいプロトタイプの集合を作り出す) 誤り確率の計算例[1] ２つのクラスが1次元特徴空間上の[1，0]上に分布しているとする 両クラスの事前確率： P (1 )  P ( 2 )  1 2 両クラスの確率密度関数(下図のように) ： px | 1   2 x p x |  2   2  2 x px | 1   2 x p x |  2   2  2 x x : 1次元の特徴値誤り確率の計算例[2]  xの確率密度関数 p( x)  P(1 ) p( x | 1 )  P( 2 ) p( x |  2 )  1 1  2 x   (2  2 x)  1 2 2 一様分布のパターン  ベイズの定理より P(1 | x)  x P( 2 | x)  1  x N個のプロトタイプ x1 , x2 , xn を用いて未知パターンを識別誤り確率の計算例[3] • NN法での誤り確率 en ( x, x' )  P(1 | x) P( 2 | x' )  P( 2 | x) P(1 | x' )  x(1  x' )  x' (1  x) x’で平均したものを en (x) とおく 1 en ( x)   en ( x, x' )q ( x, x' )dx' 0   x  (1  2 x) x'q ( x, x' )dx' 1 0 1  x  (1  2 x)  x' q ( x, x' )dx' 0  x  (1  2 x) I def 1 I   x' q( x, x' )dx' 0 q (x,x’): 最近傍がx’となる確率誤り確率の計算例[4] • q(x,x’)を求める  0 x 1 2 の場合 n個のプロトタイプの1つが座標値x’に存在し、残り(n-1)個が太線の区間に存在しなければならない 0 1/2 x’ 2x-x’ x x x 1 0  x'  x 2x-x’ x  x' 2 x x’ 2x x’ 2 x  x'  1 誤り確率の計算例[5]  n(1  2 x  2 x' ) n 1  q( x, x' )  n(1  2 x  2 x' ) n 1 n 1  n ( 1  x ' )  (0  x '  x ) ( x  x'  2 x) (2 x  x'  1) 1 I   x' q( x, x' )dx' 0 x   n(1  2 x  2 x' ) 0 n 1 2x x' dx'  n(1  2 x  2 x' ) n 1 x' dx' x 1   n(1  x' ) n 1 x' dx' 2x  x 1 (1  2 x) n (n  1) x  1 n 1 1  q( x, x' )dx'  1 0 誤り確率の計算例[6] • q(x,x’)を求める  1  x 1 2 の場合 n個のプロトタイプの1つが座標値x’に存在し、残り(n-1)個が太線の区間に存在しなければならない 0 1/2 x’ 1 2x-1 0  x'  2 x  1 x x’ x 2x-x’ 2x-x’ x x’ 2 x  1  x'  x x  x ' 1 誤り確率の計算例[7]  n( x' ) n 1  q( x, x' )  n(1  2 x  2 x' ) n 1  n(1  2 x  2 x' ) n 1  (0  x'  2 x  1) (2 x  1  x'  x) ( x  x'  1) 1  q( x, x' )dx'  1 0 1 I   x' q( x, x' )dx' 0  2 x 1 0 n( x ' ) n 1 x' dx'  x 2 x 1 n(1  2 x  2 x' ) n 1 x' dx' 1   n(1  2 x  2 x' ) n 1 x' dx' x  x 1 (2 x  1) n (n  1) x  n n 1 誤り確率の計算例[8] 各範囲での en (x) 0 x 1 の時 en ( x)  x  (1  2 x) I 2 1    x  (1  2 x)  x  (1  2 x) n (n  1) x  1 n 1   1  n 1    (1  2 x) n  2  (1  2 x) n 1  (1  2 x) 2  1 2  n 1  1  x  1 の時 en ( x)  x  (1  2 x) I 2 1    x  (1  2 x)  x  (2 x  1) n (n  1) x  n n 1   1  n 1    (2 x  1) n  2  (2 x  1) n 1  (2 x  1) 2  1 2  n 1  NN法の誤り確率とプロトタイプ数との関係誤り確率の計算例[9]  NN法の誤識別率 1 eN   en ( x) p( x)dx eN 0 1 3n  5   3 2(n  1)(n  2)(n  3)  ベイズ誤識別率 eB 誤り確率　eN 0.5 0.45 0.4 n=1のとき eN  0.35 0.3 n→∞のとき 1 121 eN  limプロトタイプ数 en  n （個） n  3 eB   minP(1 | x), P( 2 | x)p( x)dx 1 0   minx,1  xdx  1 0 1 2 1 4 1 1 3 eB  eN  2eB 1  eB     4 3 8 11 31 coffee break • NN法の誤り確率はベイズ誤り確率の2倍を超える!! 推定値・・・推定に用いたパターンの偏りと分散を伴う NN法における偏り →パターン数とは独立に特徴空間の次元、距離尺度、パターンの分布に大きくかかわってきた誤り確率に大きな偏りが付加されベイズ誤り確率の2倍をはるかに超えてしまう パターンxと最近傍パターンx’の関係特徴空間が2次元・・・n→∞で限りなく近づく特徴空間が高次元・・・xとx’の距離が0という仮定は正しくない (球面集中現象などによって) NN法を望ましい識別機として使用するためには、特徴空間の次元、パターン数、距離尺度をうまく設定することが重要