『わかりやすいパターン認 識』 第 5 章 特徴の評価とベイズ誤り確率 5.4 ベイズ誤り確率と最近傍決定則 発表日： 5 月 23 日（金） 発表者：時田 陽一
最近傍決定則の誤り確率 ベイズ誤り確率を求めたい 確率密度関数が既知の場合解析的に求めることができる 一般に確率密度関数は未知 観測できるものは、確率密度関数の実現値 （確率密度関数に基づいて生成される個々のパターン） NN 法によってベイズ誤り確率 の近似が可能 !! ： NN 法の誤り確率 c ：クラス数 NN 法の誤り確率はベイズ法によるものの 2 倍を超えない
ベイズ誤り確率と最近傍決定則 ベイズの誤り確率： 『分布の重なり』が 誤り確率を表す 最近傍決定則
2 クラスにおける近似の式の導出 〔 1 〕 クラスのわかっている n 個のプロトタイプを用意 : 入力パターン x に対する最近傍を x ’ で表す 入力パターンとその最近傍の属するクラスが異なる場合に誤りが生 ずる（ NN 法） NN 法でパターン x を識別したときの誤り確率（ n 個のプロトタイ プ）： 起こりうる全ての x に対する誤り誤差： これらを用いて の関係を求める
2 クラスにおける近似の式の導出 〔 2 〕 プロトタイプ数 n を無限大に近づけるとする 上式より、 ただし、次の関係式を用いた 最近傍 x ’ は入力パターン x に限りなく近づくとする
2 クラスにおける近似の式の導出 〔 3 〕 NN 法の誤り確率： の分散
2 クラスにおける近似の式の導出 〔 4 〕 近似の式の導出〔 3 〕より まとめると以下の ようになる 先に示した近似の式の 3 項目に c=2 を代入することでこの関係が導かれる
coffee break ベイズ決定則による決定境界は事後確率が等しい以下の式を満たす点として定 まる 誤識別は決定境界付近で発生することが多い 決定境界付近ではパターンの確率密度が低い 例． が正規分布で表される場合、正規分布の裾野近くに設定される NN 法のためにプロトタイプを収集したとする 確率密度の高いところに多くのプロトタイプが集まる ( 決定境界付近には少数のプロトタイプしか集まらない ) NN 法で高い識別率を達成するためには 決定境界を決めるのに寄与するプロトタイプのみを残せばよい パターンの分布を忠実に反映することと高い識別性能を実現することが 相反する要求となっている 編集アルゴリズム ( 効率的な識別が可能な新しい プロトタイプの集合を作り出す )
誤り確率の計算例 [1] ２つのクラスが 1 次元特徴空間上の [1 ， 0] 上に分布しているとする 両クラスの事前確率 ： 両クラスの確率密度関数 ( 下図のように ) ： x : 1 次元の特徴値
誤り確率の計算例 [2] x の確率密度関数 一様分布のパターン ベイズの定理より N 個のプロトタイプ を用いて 未知パターンを識別
誤り確率の計算例 [3] NN 法での誤り確率 x ’ で平均したものを とおく q (x,x ’ ): 最近傍が x ’ となる確率
誤り確率の計算例 [4] q(x,x ’ ) を求める の場合 0 1 1/2 x x’x’ 2x-x ’ x x’x’ x 2x x’x’ n 個のプロトタイプの 1 つが座標値 x ’ に存在し、残り (n-1) 個が 太線の区間に存在しなければならない
誤り確率の計算例 [5]
誤り確率の計算例 [6] q(x,x ’ ) を求める の場合 0 1 1/2 x x’x’ 2x-1 x x’x’ 2x-x ’ x x’x’ n 個のプロトタイプの 1 つが座標値 x ’ に存在し、残り (n-1) 個が 太線の区間に存在しなければならない
誤り確率の計算例 [7]
誤り確率の計算例 [8] 各範囲での の時
NN 法の誤識別率 誤り確率の計算例 [9] ベイズ誤識別率 n=1 のとき n→∞ のとき
coffee break NN 法の誤り確率はベイズ誤り確率の 2 倍を超える !! 推定値・・・推定に用いたパターンの偏りと分散を伴う NN 法における偏り → パターン数とは独立に特徴空間の次元、距離尺度、 パターンの分布に大きくかかわってきた 誤り確率に大きな偏りが付加されベイズ誤り確率の 2 倍をはるかに超えてしまう パターン x と最近傍パターン x ’ の関係 特徴空間が 2 次元・・・ n→∞ で限りなく近づく 特徴空間が高次元・・・ x と x ’ の距離が 0 という仮定は正しくない ( 球面集中現象などによって ) NN 法を望ましい識別機として使用するためには、特徴空間の次元、 パターン数、距離尺度をうまく設定することが重要