わかりやすいパターン認識」 第1章:パターン認識とは

「わかりやすいパターン認識」
第1章:パターン認識とは
1.1 パターン認識系の構成
1.2 特徴ベクトルと特徴空間
1.3 プロトタイプと最近傍決定則
4月11日(金)
発表者 新納浩幸
1.1 パターン認識系の構成
パターン認識とは
C  {1 , 2 ,, c }
入力
?
どのクラス
事例、個体、…、あるもの
i
クラスの集合
に対応するか?
パターン認識の例
• 文字認識
C は文字の集合、事例は文字が書かれた画像
• 音声認識
C は単語の集合、事例はある区間の時系列信号
• センサーによる状況の判断
C は判断の集合、事例はセンサーから得た情報
非常に多くの応用がある、知的処理の根幹
事例の表現
?
特徴ベクトルで表現する
d 個の特徴に注目
(例:文字認識、、、文字線の傾き、幅、曲率、面積など)
k 番目の特徴の値を
?
xk
で表す
x  ( x1, x2 ,, xd )
t
簡単な例
問題) 外見から日本人か外人かを識別せよ
C ={日本人,外人}
識別に有効そうな特徴を考える
(とりえる値)
特徴1 身長 ......実数値
特徴2 髪の色 .....赤,ブロンド,黄色,黒
特徴3 目の色 .....黒,青,茶色
A君の特徴ベクトル
( 170,黄色,黒)
とりあえずカテゴリ値は
考えない.属性は実数値
をとるとしておく
認識系の構成
入力パターン
出力
特徴
抽出部
前処理部
ノイズ除去
正規化
識別
演算部
設定してある
特徴を取り出す
識別辞書
x  ( x1, x2 ,, xd )
t
識別部
5
1.2 特徴ベクトルと特徴空間
特徴空間
特徴ベクトルの張る空間のこと
同じクラスを持つ特徴ベクトルは特徴空間上で
まとまった塊(クラスター)となっている
1
2
x
i
c
特徴抽出の例
画像を特徴ベクトルへ
注目する特徴は画像の各位置の濃度
画像を 256 分割し、各メッシュの濃度を8段階で表す
各画素を
8段階に
量子化
256分割
標本化
各メッシュを
8段階に
量子化
256次元のベクトルで表現できる
( x1 , x2 ,, x256 )t
特徴ベクトルで表現できるパターン数は 8256  10231
特徴ベクトルの多様性
手書き数字文字の認識
クラスは 0,1,2,...,9 と reject の 11個
5*5 のメッシュ(25次元)、各メッシュは 0 or 1 の値
(白 or 黒)
数字の2のあるパターン
表せるパターンは
225  33,554,432
各パターンに対してそのクラスを付与しておけば、識別は簡単。
しかしそれはパターン数の膨大さから不可能。
1.3 プロトタイプと最近傍決定則
プロトタイプ
起こりうるすべてのパターンとそのクラスを記憶しておくのは不可能
クラスの代表的なパターンのみを記憶しておく
プロトタイプ
識別は事例と各プロトタイプとの距離を測り、もっとも近い
プロトタイプのクラスを出力する
最近傍法(NN法)
イメージ的には,,,
2
入力された事例は
特徴空間上のある1点
x
1
c
最も近いクラスターに
に属すると考える
i
近さを測るメジャーが
必要,とりあえず
ユークリッドの距離
NN法の定式化
C  {1 , 2 ,, c }
( x1,1 ), ( x2 , 2 ),( xn , n )
クラスの集合
n 個のプロトタイプ
 p C
事例
x
の識別
min
p 1, 2,n
{D( x, x p )}  D( x, xk )
注) D( x, y) は x と y の距離を表す。
xk
のクラス  k
を出力
k-NN法
NN法の拡張、入力事例と距離の近い順にプロトタイプを
k 個取り出し、それらのクラスの多数決でクラスを決定
NN法は 1-NN 法に対応
入力2
1
2
入力1は 1 と識別
入力1
入力2は reject と識別
i
c
プロトタイプの決め方
全数記憶方式
収集できたパターンをすべてプロトタイプにする。
重心
収集できたパターンをクラスごとに分けて、
各クラスのそれらのパターンの重心をプロトタイプとする。
クラスあたり1個のプロトタイプ。
特徴空間の分割
プロトタイプを重心に選ぶ、収集したパターンを完全に分離できた例
1
2
3
赤の線が
決定境界
reject
NN法の適用を考えるとクラスを分離する境界がある
決定境界
図(2次元)では決定境界は2つのプロトタイプの垂直2等分線
Coffee Break
表現することと判別すること
事例を忠実に表現できる特徴が必ずしもよい特徴ではない
クラスを精度よく判別できる特徴がよい特徴
(1)文字認識において画像をビットマップに対応する
特徴ベクトルで表現,,,
表現力は高いけど,これで判別できるかは?
(2)事例を忠実に表現しようとして特徴を増やす(次元を増やす)
のは一般にはよくない。次元は少ないほうが望ましい。
Coffee Break
NN法を見直そう
NN法は単純だけど、奥が深い。近年は計算機の性能が
上がってきたので、実用的な手法になってきている。
参考) 訓練データ(クラスが付与された事例集)が多いと
けっこう強力!
Coffee Break
特徴抽出に王道なし
識別の精度は学習アルゴリズムよりも、どんな特徴に
注目したかの方が効く。
どんな特徴に注目したらよいかは機械的に発見できる
ものではない。問題に精通することが大事。
図形の認識,画像の認識,,,,,奥が深い
自然言語処理の問題は文脈というものを
どのように特徴付けるかが1つのポイント