パターン認識特論 - VRL - Vision and Robotics

パターン認識
ー判別分析ー
担当：和田俊和
部屋 A513
Email [email protected]
講義資料はhttp://vrl.sys.wakayama-u.ac.jp/PRA/WPR-2
判別分析と統計的識別
射影特徴の平均と分散
射影後の位置
y  AT x
A
n
1 n T
T 1
平均値  A xi  A  xi  AT x
n i 1
n i 1
T
1 n
T
T
分散
(
x

x
)
A
(
x

x
)
A

i
i
n i 1


1 n T
  A ( xi  x )( xi  x )T A
n i 1
 AT A

クラス内の分散
クラス１
2
μ2
1
μ1
平均値 AT x1
T
分散 A 1 A
クラス２
AT x 2
AT 2 A
A
クラス内分散の期待値
1
n1 AT 1 A  n2 AT  2 A 

n1  n2
T n11  n2  2
A
A
n1  n2
 AT W A
クラス間分散




n1n2 ( x1  x2 )( x1  x2 )T
B 
(n1  n2 )2

T
1 n
T
全分散V   ( xi  x ) A ( xi  x )T A
n i 1
T
n1 1 n1
T

( xi  x ) A ( xi  x )T A

n1 x1  n2 x2
n1  n2 n1 i 1
x
n
T
n2 1
n1  n2
T
T

(
x

x
)
A
(
x

x
)
A
 i
i
n1  n2 n2 i  n1 1
T
n1

n1 1
n2 ( x1  x 2 ) T  
n2 ( x1  x 2 ) T 

) A   ( xi  x 1 
) A
 ( xi  x1 

n1  n2 n1 i 1 
n1  n2
n1  n2
 

T
n2 1 n 
n1 ( x1  x 2 ) T  
n1 ( x1  x 2 ) T 

) A   ( xi  x 2 
) A
 ( xi  x 2 

n1  n2 n2 i  n1 1 
n1  n2
n1  n2
 

 n   n  n n2  n n2

T
T
2 1
A  1 1 2 2 1 2
( x1  x 2 )( x1  x 2 )  A
3
 n1  n2

 n1  n2 


n n 

n1n2
T
T
T
T
1 1
2 2

A 

(
x

x
)(
x

x
)
A

A

A

A
B A
1
2
1
2
W
2
 n1  n2

n

n


1
2






注意点
• ランクについて
 Bはランク１
Wは， 1 と 2 のランクの高い方になる．

1
B の計算は不可能．
識別に有利な特徴への変換
クラス内分散を小さくし、クラス間分散を大
きくする一次元特徴を求める
2
μ2
1
μ1
W 
A
n11  n2  2
n1  n2
n1n2 ( x1  x 2 )( x1  x 2 )T
B 
(n1  n2 )2
クラス内分散
クラス間分散
A W A
T
A B A
T
AT  B A
フィッシャー比 T
の最大化
A W A
識別に有利な特徴への変換：
判別分析（定式化）
AT  B A の値は変わらないので、
A の大きさが変わっても T
A W A
T
A
A W A  1 という条件の下での B A の最大化問題と見なす。
T
Lagrangeの未定係数法により、次の目的関数が得られる。
J ( A)  AT B A  ( AT W A 1)
この目的関数の最大化により目的の軸 A が決定できる．
識別に有利な特徴への変換：
判別分析（解き方）

J ( A)  2 B A  2W A  0 なので、
A
B A  W A が得られ,これを整理して
 B A   A となる。
1
W
1
W
 B の最大固有値がJの最大値となり、
これに対応する固有ベクトルが、 A になる。
線形判別法：
多クラスの場合
多クラスの場合、Aは複数のベクトルとなる。
c
W   P( i )i
i 1
c
 B   P(i ) P( j )( x i  x j )( x i  x j )T
i 1 j i
これらを最大化する問題は、同じ問題に帰着する。
1
W
 B
の固有ベクトルが、Aになる。
パターン認識
ー統計的識別ー
担当：和田俊和
部屋 A513
Email [email protected]
講義資料はhttp://vrl.sys.wakayama-u.ac.jp/PRA/WPR-2
判別分析と統計的識別
統計的識別とは
• データ xが与えられたときに、それがあるク
ラスωi に属する確率 P(ωi|x)を求める。
• 各クラスについて、 P(ωi|x) を計算し、そ
れを元にしてユーザの定義した損失関数
を最小にする ωi に x を分類する。
P
P(ω2|x)
P(ω1|x)
P(ω3|x)
x
統計的パターン認識のための
数学的準備
クラス：　i (i  1,...,c)
入力データ：x
事前確率：
P(ωi ) ,
P( x)
事後確率：
P(ωi|x), P( x | ωi )
c
 P( )  1,
i 1
i
c
c
 P(ω |x)  1
i 1
P( x)   P(i ) P( x | i )
i 1
i
Bayes 則（定理）： P(i | x) の計算
パターンxが入力されたとき、
それがクラスωiに属する確率
クラスωiに属するパターンx
が生起する確率
P( x |  i )
P( i | x) 
P( i )
P( x)
P
P(ω|x)
P( x | ω)
P(x)
x
識別基準：
Bayes決定則＝期待損失の最小化
期待損失：（
ω j に属するパターン x を分類する際の損失）
c
L( j | x)   l ( j |  i )P( i | x)
i 1
０－１損失基準：
期待損失：
0 if j  i
l ( j | i )  
1 otherwise
c
L( j | x)   P(i | x)  1  P( j | x)
i j
L( j | x)を最小化するこ
にはP( j | x)を最大化す
ればよい
これは、事後確率を最大化するように識別を行えば良いことを意味している。
０-１損失基準に基づく識別
• P(ωi|x) の最大値を与える ωi に
る。
x を分類す
P
P(ω2|x)
P(ω1|x)
P(ω3|x)
x
他の損失基準
期待損失
c
L( j | x)   l ( j |  i )P( i | x)
i 1
識別器の出力：
教師信号：
Ψ( x)  ( y1,, yc )
t  (0,,1,,0)
平均2乗誤差基準：
c
L(Ψ | x)   P(i | x)  || Ψ( x; )  t || p( x | i )dx
i 1
2
連続損失基準
期待損失
c
L( j | x)   l ( j |  i )P( i | x)
i 1
識別器の出力：
誤分類尺度
[甘利]：
Ψ( x; )  ( g1 ( x; ),, gc ( x; ))
1
d i ( x) 
mi
g
j , g j  gi
j
( x; )  gi ( x; )
 1

誤分類尺度
d i ( x)   g i ( x; )  
g j ( x; ) 

c  1 j i


[Juang,Katagiri]：
1/
Bayes 決定則を適用する上での問題
確率 P( x | i ) をどうやって求めるか
P( x |  i )
P( i | x) 
P( i )
P( x)
P( x | i )
を確率密度関数
P( i | x) 
p( x |  i )
p( x |  i )
c
 P(
j 1
j
) p( x |  j )
で代替する。
P( i )
Bayes 決定則に基づく識別
P( i | x) 
ある
p( x |  i )
c
 P(
j
) p( x |  j )
P( i )
j 1
に対して決まる分母は同じ値になるので、
x
gi ( x)  p( x | i ) P(i )
の大小関係を調べて、識別を行えば良い。
確率密度関数の例
d次元正規分布

 1

T 1
exp ( x  i ) i ( x  i )
2


p( x |  i ) 
d /2
1/ 2
(2 ) | i |
p( x | i ) dx  1
x i
 1  x   
exp 

 2   
p( x |  i ) 
2 
例：１次元正規分布
2



Bayes の定理に基づく識別
仮定1 各クラスに属するパターンの事前確率 P(i ) が同じ
であるとすれば、
gi ( x)  p( x | i )
の大小関係を調べて、識別を行えば良いことになる。
正規分布の場合、その対数を求めると、
log P( x |  i ) 

1
T 1
 d log(2 )  log(|  i |)  ( x  i )  i ( x  i )
2
が得られる。このうち、クラスに依存しない項を除けば、
log(| i |)  ( x  i )  ( x  i )
T
1
i
となる。

Bayes の定理に基づく識別
と線形識別関数
仮定2 さらに、各クラスの共分散行列の行列式の値が等しい
とすれば、
D ( x, i )  ( x  i )  ( x  i )
2
M
T
1
i
の値が小さければ、x と μi が似ていることになる。
これを「マハラノビス距離」という。
仮定3 各クラスの共分散行列自体も等しいとすれば、
g 'i ( x)  2  x    i
T
i
1
T
i
1
となり、線形識別関数が得られる。(仮定１が無くても
仮定３のみで、下記の線形識別関数が得られる。)
gi ( x)  2iT 1x  iT 1i  2 log P(i )
確率密度関数の母数の推定（１）
確率密度関数p(x;θ)の形は分かっているが、分布形状を
決定するパラメータ（母数） θが未知である場合、学習サ
ンプルからθを決定したい。
n
p(  , )   p( xk ; i )
k 1
θの関数とみなした
とき、これを「尤度関
数」と呼ぶ
これが、最適なθで、停留すると仮定し,

p(  , )  0

を満たすθを求める。（最尤推定）
これは、全てのxkが同時
に生起するという確率
（同時生起確率）であり、
「全ての学習サンプルを
説明する上で、最も尤も
らしい分布の母数を推
定する」ことを意味してい
る。
パラメータの最尤推定
正規分布の場合(Σ,μ)
p(  , )最大化の結果
共分散行列：
平均：
1
i 
ni
1
i 
ni
 ( x   )( x   )
x
i
i
 x
x
i
i
T
確率密度関数の母数の推定（２）
不偏推定
すべての可能なχに対するθの推定量の期待値が真
の値に対して偏らないように推定する。（不偏推定）
E  ( ) 
true
0
正規分布の場合
共分散行列： 
平均：
i
1
T

( x   i )( x   i )

ni  1 xi
1
i 
ni
 x
x
i
正規分布の推定例
主成分分析
• 共分散行列Σの性質
  12  1 2

2



2 1
2


 


 n 1  n 2
μ
φ
|| φ ||
対称行列なので次式による
対角化が可能
  VV
V  φ1 φ2  φN 
T
1
0



0
0
2

0
  1 n 

  2 n 

 
2 
 n 
0
 0 
 

 n 

共分散行列の性質
D ( x, i )  ( x  i )  ( x  i )
2
M
T
1
i
マハラノビス距離が一定の曲面（曲線）は正規分布の確率密度が
一定の面(線)であり、その形状は楕円面（楕円）になる
1
1
  V  V の意味
T
xTΛ-1x =const
xTΣ-1x=(Vx)TΛ-1(Vx)=const
1
2
空間をVによっ
て回転させると
このように見え
る。
1
2
主成分分析
• 共分散行列Σの性質
  VV
1
0



0
T
V  φ1 φ2  φN 
0

 0
 

 n 

0
2

0
Vは直交行列（回転を表している）：
V V
T
1
|| Vx |||| x ||
VT

V
正規分布の意味
• d次元正規分布
共分散行列を使った二次形式
 1

T 1
exp ( x  i ) i ( x  i )
2


p( x |  i ) 
d /2
1/ 2
(2 ) | i |
共分散行列の行列式
（正規化項：分布の広
がりを表している）
主成分分析によって何が分かるか
• 分散の大きくなる軸の向き φi
• その軸方向の偏差 i 分散 i
• 共分散行列のランクがrである場合、次式が成
r
り立つ
x   (φ・i (x  x))φi  x
i 1
• r未満の数qに対する直交展開
q
x'   (φ・i (x  x))φi  x
i 1
を計算する際に誤差||x-x’||を最小化する基底が
求まっている。

Download Report