Document

パターン認識と学習のアルゴリズム
上坂吉則
尾関和彦
文一総合出版
宮崎大輔2003年8月7日（木）PBVセミナー
5 時系列パターンの線形予測
目的
• 時系列パターンの認識をおこなうために、スペクトル
を推定する→線形予測法
• 二つのスペクトルの類似度をLPCケプストラム距離
を使う
自己回帰過程
• 時刻を整数とし、時刻nで実数x(n)が決まる時系列を考える
, x(2), x(1), x(0), x(1), x(2), x(3),
• 確率変数の列（確率過程）X(n)を考え、x(n)をX(n)の実現値と
考える
, X (2), X (1), X (0), X (1), X (2), X (3),
• 以下が成り立つ確率過程を自己回帰過程と言う
p
X (n)   k X (n  k )  gauss noise(平均0, 分散 )
k 1
• α1,…,αpを予測係数、pを次数と呼ぶ
• 要は、現在のXを過去p個のXの線形和で表せるってこと
線形予測法
• 2N+1個の時系列値でパラメータ推定
x(n0  N ),, x(n0 ),, x(n0  N )
• 同時確率密度関数
 1
1
P
exp 2
( 2 N 1) / 2
2 ( 2 N 1) / 2
(2 )
( )
 2


 x(n)   k x(n  k )

n  n0  N 
k 1

n0  N
p
2



線形和で近似したときの誤差
• →誤差が小さいと尤度Pが高く、誤差が大きいと尤度
Pが低い
• 最尤法：尤度Pを最大化する
• log Pをσ2で偏微分して0とおき、αkで偏微分して0と
おいた２つの式の連立方程式を解けば良い
窓
y(n)  W (n  n0 ) x(n)
• 方形窓
1;  N  n  Nのとき ,
W ( n)  
0; それ以外のとき
• ハミング窓
0.54  0.46 cos(n / N );  N  n  Nのとき ,
W ( n)  
0;
それ以外のとき

自己回帰過程のスペクトル
• スペクトル密度関数は
S ( ) 

 r (m) exp(im)
m  
•
•
•
•
r (m)  E ( X (n) X (n  m))
区間[-π,π]で定義されている
Eは期待値、exp(-iωm)は複素正弦波
つまりフーリエ変換
2
結局、最終的に S ( ) 
2
p
1    k (exp(ik ))
k 1
LPCケプストラム距離
• 二つのスペクトルSとS’の類似度の定義
1
D( S , S ) 
2



(log S ( )  log S ( )) 2 d
• logS,logS’をフーリエ級数に展開する
log S ( ) 

c
k  
k
log S ( ) 
exp(ik )

 c exp(ik )
k  
k
• Parsevalの公式
1
2




(logS ( )  log S ( )) d  (c0  c0 )  2 (ck  ck ) 2
2
2
• c0,c1,c2,…: LPCケプストラム係数
• LPC=Linear Predictive Coding(線形予測符号化）
• LPCケプストラム距離
D( S , S ) 2  (c  c ) 2  2
0
0
k 1
q
2

(
c

c
)
 k k
k 1
• つまり、フーリエ展開係数の差を二つのスペクトルの距離として用いる
LPCケプストラム係数の計算
c0  log
2
c1  1
1 n1
cn   n   kck nk
n k 1
 j  0 ( j  p)
• c0はスペクトルの大きさだけに関係し、音韻性と無関
係。無視するか十分小さな0<ε≪1を使い
q
2
2
2



D( S , S )   (c0  c0 )  2(1   ) (ck  ck )
k 1
スペクトルの推定
スペクトルの近似
• LPCケプストラム係数q次までを使ってス
ペクトルを近似
• LPCケプストラム距離＝LPCケプストラム
係数で近似し、フーリエ展開係数の距離
6 DPマッチング
類似度
• パターンの要素x,yの類似度dを考える
xがyに似ている  d ( x, y)の値が小さい
x  y  d ( x, y)  0
• パターンA,Bの類似度としてD0を考える
D0 ( A, B)  0
AがBに似ている  D0 ( A, B)の値が小さい
パターン Aはパターン Bを長さ方向に
伸縮したパターンである  D0 ( A, B)  0
I
D0 ( A, B; w)   d (ai , bw(i ) )
i 0
D0 ( A, B)  minD0 ( A, B; w) | w W ( I , J )
• 伸縮写像（端点が一致、各aiに一つのbj、順
序は逆転しない）
DP マッチング
類似度
d(a0,b0)
b2
b1
b0
a0
a1
a2
DP マッチング
類似度
∞
b2
b1
b0
a0
a1
a2
DP マッチング
類似度
d(a1,b0)+d(a0,b0)
b2
b1
b0
a0
a1
a2
DP マッチング
類似度
d(a1,b1)+min(d(a0,b0),d(a0,b1))
b2
b1
b0
a0
a1
a2
DP マッチング
類似度
d(a1,b2)+min(d(a0,b0),d(a0,b1),d(a0,b2))
b2
b1
b0
a0
a1
a2
DP マッチング
類似度
d(a2,b0)+d(a1,b0)
b2
b1
b0
a0
a1
a2
DP マッチング
類似度
d(a2,b1)+min(d(a1,b0),d(a1,b1))
b2
b1
b0
a0
a1
a2
DP マッチング
類似度
d(a2,b2)+min(d(a1,b0),d(a1,b1),d(a1,b2))
b2
b1
b0
a0
a1
a2
DPマッチング
• ある問題を解きたいとき、“それと同じタイプで、それよりサイ
ズが小さい一群の問題”の解を利用する、という原理を動的
計画法と呼ぶ
• 動的計画法を用いて二つのパターンの要素間の対応付け
（整列化）を行い、それによって類似度を計算することをDP
マッチングと呼ぶ
• DP=Dynamic Programming(動的計画法）
• 時系列パターンに対しては、DPマッチングのことを
DTW(Dynamic Time Warping)と呼ぶこともある
傾斜制限
対照的な類似度
• 縦・横・斜め、１マスだけ動ける
脱落と挿入
A’ = * a1 a2 a3 *
* a4 a5
B’ = b1 b2 * b3 b4 b5 b6 *
• *は脱落を表す記号
タンパク質
• 生物のタンパク質＝20種類のアミノ酸の有限列
• A（アラニン）,C（システイン）,D（アスパラギン酸）,E
（グルタミン酸）,F（フェニルアラニン）,G（グリシン）,H
（ヒスチジン）,I（イソロイシン）,K（リジン）,L（ロイシ
ン）,M（メチオニン）,N（アスパラギン）,P（プロリン）,Q
（グルタミン）,R（アルギニン）,S（セリン）,T（スレオニ
ン）,V（バリン）,W（トリプトファン）,Y（チロシン）
チトクロムC
• ヒト
– GDVEKGKKIFIMKCSQCHTVEKGGKHKTGPNLHGLF
GRKTGQAPGYSYTAANKNKGIIWGEDTLMEYLENPK
KYIPGTKMIFVGIKKKEERADLIAYLKKATNE
– 104個
• ミドリムシ
– GDAERGKKLFESRAAQCHSAQKGVNSTGPSLWGVY
GRTSGSVPGYAYSNANKNAAIVWEEETLHKFLENPK
KYVPGTKMAFAGIKAKKDRQDIIAYMKTLKD
– 102個
比較
• ヒト(18個)
– GDVEKGKKIFIMKCSQCH
• ジャガイモ(26個)
– ASFNEAPPGNPKAGEKIFKTKCAQCH
• ミドリムシ(18個)
– GDAERGKKLFESRAAQCH
• クロバエ(22個)
– GVPAGDVEKGKKLFVQRCAQCH
• ウサギ(18個)
– GDVEKGKKIFVQKCAQCH
類似度
a  bのとき
0,

d (a, b)  2,
a  b, a  *, b  *のとき
1, a  b, a  *または b  *のとき

結果
7 NN法とボロノイ図
k-NN法
• 今、あるカテゴリに含まれるパターンの集合（＝標準
パターン（テンプレート））が分かるとする
• あるパターンxが与えられて、それがどのカテゴリに
属するかを知りたいとする
• xに最も近いk個のパターンを選ぶ（k-最近傍）
• そのk個のパターンの中で最も多いカテゴリをxのカ
テゴリとする（多数決）
• これをk-NN法(k-Nearest Neighbor法)と呼ぶ
• k-NN法(k≧2)は1-NN法より良いかのように思われ
るが多くの場合1-NN法のほうが良い
• 1-NN法を略してNN法と書く
標準パターンと勢力圏
• カテゴリを調べるために全ての点との類似度を計算するのは
面倒→各カテゴリに“代表点”を１個当てはめるようにする
• あるカテゴリに属するパターンの集合を勢力圏と言う
• ２次元の場合で、類似度がユークリッド距離の場合、勢力圏
はボロノイ図になる
クラスタリング
• 学習パターンから標準パターンを求めたい→クラスタリング
N
• D( S , S , , S )  D( S )
1
2
N

n 1
n
を最小にするクラスタS1,S2,…,SNに分割したい
D( x, S )   d ( x, y)
yS
D(S )  minD( x, S ) | x V 
• 上の右辺を満たすxをセントロイドC(S)と呼ぶ
C(S )  arg minD( x, S ) | x V 
• 例えばdがユークリッド距離の２乗の場合はセントロイドは重
心になる
LBGアルゴリズム
•
1.
2.
3.
4.
•
LBG=Linde, Buzo, Gray
セントロイドの初期値を適当に設定
セントロイドからクラスタに分割する
そのクラスタのセントロイドを再計算
収束するまで2~3を繰り返す
最小値に到達するとは限らない
–
–
極小値に収束
いくつかの初期値を試す必要がある
LBGクラスタリングの実験
NN法とカテゴリの勢力圏
• c1,c2の学習パターンそれぞれでLBGクラスタリングを行った
8 ヒドンマルコフモデル
HMM(Hidden Markov Model)
いくつのカテゴリに分類するか決める
状態の数、出力記号の数を決める
カテゴリごとに学習パターンを用意
Baum-Welchアルゴリズムで、カテゴリごとにHMM
のパラメータを推定
5. 前向きアルゴリズム（あるいは後向きアルゴリズ
ム）で、未知パターンの出力確率をカテゴリごとに
計算。出力確率が最大となるカテゴリを認識結果と
する。
1.
2.
3.
4.
HMM(Hidden Markov Model)
• 要は、今までと同様、クラス分けをしたい
• つまり、ある未知パターンが与えられたとき、そのパターンが
どのカテゴリに属しているかが知りたい
• そのためにあらかじめ、学習パターンを与えて学習をさせ、い
いクラス分けができるような認識機械を作り上げる
• その認識機械がHMMである
• カテゴリ1にはHMM1をカテゴリ2にはHMM2を対応させる
• カテゴリ1に属する学習パターンをHMM1に与えて学習させ、
カテゴリ2に属する学習パターンをHMM2に与えて学習させる
• 未知パターンが現れたとき、HMM1にその未知パターンを与
えるとその未知パターンがカテゴリ1に属する確率が吐き出さ
れ、HMM2にその未知パターンを与えるとその未知パターン
がカテゴリ2に属する確率が吐き出される
• そこで最も確率の高いカテゴリが未知パターンのカテゴリとな
る
マルコフ連鎖
•
•
•
•
•
状態： s1 , s2 ,, sN
確率変数： S1 , S2 , S3 ,
初期分布： 1,,  N
• 有向グラフで一様なマルコフ連鎖
を表せる
• 頂点＝状態、辺＝推移確率
推移確率： ai , j  P(Si 1  s j | Si  si )
一様なマルコフ連鎖では以下が
成り立つ
P( S1  si (1)  S 2  si ( 2)    St  si (t ) )
  i (1) ai (1),i ( 2) ai ( 2),i (3)  ai (t 1),i (t )
• →時刻1で状態si(1)、時刻2で状態
si(2)…となる確率は、i(1)の初期
分布に、i(1)からi(2)に移る推移
確率をかけ、i(2)からi(3)に移る推
移確率をかけ…、を意味している
一様なヒドンマルコフモデル
•
•
•
•
•
出力記号： o1 , o2 ,, oM
初期分布： 1 ,,  N
状態siから状態sjへの推移確率： ai , j  P(St 1  s j | St  si )
状態sjから出力記号okの出力確率： b j ,k  P(Ot  ok | St  s j )
初期分布：   1 ,,  N 
 a1,1  a1, N 


• 推移確率：
A 
 
a N ,1  a N , N 
• HMMのパラメータ：   (, A, B)
 b1,1  b1, M 

出力確率： B   



bN ,1  bN , M 
  (1,,  N , a1,1,a1,2 ,, aN , N , b1,1, b1,2 ,, bN ,M )
• HMMに関する事象の確率P:
P ( S1  si (1)  O1  ok (1)    St  si (t )  Ot  ok (t ) )
  i (1)bi (1),k (1) ai (1),i ( 2)bi ( 2),k ( 2)  ai (t 1),i (t )bi (t ),k (t )
HMMの例
•
•
•
•
•
状態： s1 , s2
出力： o1 , o2
初期分布：   (0.3,0.7)
推移確率：
0.8 0.2
A

0
.
4
0
.
6


出力確率：
0.1 0.9
B

0
.
5
0
.
5


• 観測できるのは出力記号だけで、
背後にマルコフ連鎖があり、状態
を直接観測できない→Hidden(隠
れ) Markov Model
0.8
• 確率計算の例：
0.2
s2
s1
0.4
P ( S1  s1  O1  o2  O2  o2 )
 0.3  0.9  0.8  0.9  0.3  0.9  0.2  0.5
• これは、時刻１のとき状態がs1で、
時刻１のとき出力がo2で、時刻２
のとき出力がo2である確率
0.6
0.1
0.5
0.5
o1
0.9
o2
HMMによる時系列パターンの認識
• L個のカテゴリそれぞれに対してL個のHMMがあっ
たとする
• 出力記号列： ok (1) , ok ( 2) , ok (3) ,, ok (T )
• がどのカテゴリに属するか、すなわち、どのHMMが
上の記号列を出力する確率が最も高いか、を知りた
い＝パターン認識
• 最尤法：上の記号列の出力確率、すなわち尤度（下
式）を最大とするHMM（カテゴリ）を選べばよい
P (i ) (O1  ok (1)  O2  ok ( 2)  OT  ok (T ) )
• 出力確率を計算する方法としては、前向きアルゴリ
ズムと後向きアルゴリズムがある
出力確率を計算する方法
• 前向きアルゴリズム(Forward Algorithm)
1 ( j)   j b j ,k (1)
N
 t ( j )   t 1 (i)ai , j b j ,k (t )
i 1
N
P (O1  ok (1)  O2  ok ( 2)   OT  ok (T ) )  T ( j )
• 後向きアルゴリズム(Backward Algorithm)
j 1
T (i)  1
N
t (i)   ai , j b j ,k (t 1) t 1 ( j )
j 1
N
P (O1  ok (1)  O2  ok ( 2)    OT  ok (T ) )    i bi ,k (1) 1 (i)
i 1
HMMにおける学習
• 先程は、HMMのパラメータが分かっているとして、与
えられたパターンがどのHMMから出力される確率が
高いかを調べるものだった
• ここでは、学習パターンを与え、そのパターンを出力
する確率（尤度）が最大となるHMMを構成するパラ
メータを求めたい
• 残念ながらこの最大化問題を完全に解く方法はいま
だ発見されていない
• しかし、繰り返し計算により、以前のループ時での出
力確率より現在のループ時での出力確率が必ず、同
じあるいは高くなるようにするアルゴリズムがある
→Baum-Welchアルゴリズム
Baum-Welchアルゴリズム
1 (i) 1 (i)
i 
P ( )
T 1
ai , j 
  (i)a
t
t 1
i, j
T 1
  (i) (i)
t 1
T
b j ,k 
b j ,k (t 1)  t 1 ( j )

t 1
t
t
 t ( j)t ( j)
k ,k (t )
T
 ( j) ( j)
t 1
t
t
HMM(Hidden Markov Model)
いくつのカテゴリに分類するか決める
状態の数、出力記号の数を決める
カテゴリごとに学習パターンを用意
Baum-Welchアルゴリズムで、カテゴリごとにHMM
のパラメータを推定
5. 前向きアルゴリズム（あるいは後向きアルゴリズ
ム）で、未知パターンの出力確率をカテゴリごとに
計算。出力確率が最大となるカテゴリを認識結果と
する。
1.
2.
3.
4.
HMMの学習実験
1  (1.0, 0.0)
0.2 0.8
A1  

0
.
8
0
.
2


0.8 0.2
A2  

0
.
2
0
.
8


0.8 0.2
B1  

0
.
2
0
.
8


0.8 0.2
B2  

0
.
2
0
.
8


Ai  
0.5
~ 0.15
A1  
0.70
~ 0.88
A2  
0.15
0.5
Bi  
0.5
~ 0.87
B1  
0.18
~ 0.74
B2  
0.22
•
HMM1の真値：
•
HMM2の真値：
•
•
Baum-WelchアルゴリズムでHMM1とHMM2のパラメータを推定する
0.5 0.5
初期値：
•
HMM1の推定値：
•
 2  (1.0, 0.0)
i  (1.0, 0.0)
HMM2の推定値：
~
1  (1.0, 0.0)
~
2  (1.0, 0.0)
0.5
0.85
0.30
0.12
0.85
0.5
0.5
0.13
0.82
0.26
0.78
HMMによる認識実験
(c) Daisuke Miyazaki 2003
All rights reserved.
http://www.cvl.iis.u-tokyo.ac.jp/

Download Report