Document

パターン認識と学習のアルゴリズム
上坂吉則
尾関和彦
文一総合出版
宮崎大輔2003年6月28日(土)
1 ベイズの識別規則
病気の診断
• 100人のうち30人が病気、70人が健康
• このデータをもとに、ランダムに患者が来たときに誤
診の少ないように診断したい
パターン
• パターンXとしてr個の属性X1,…,Xrの組を考える
X  ( X1 ,, X r )
t
• 各属性Xkは任意の実数値をとり得る確率変数とする
• 病気の診断の例の場合
– X1: 熱があるかないか(熱がないX1=0, 熱があるX1=1)
– X2: せきが出るか出ないか(せきが出ないX2=0, せきが出
るX2=1)
– r=2
クラスと確率
• パターンクラスとして c1 , c2
の2つを考え、これらの発生
確率を P1 , P2 とする
• クラス c i の中からパターン
x  ( x1 ,, xr )
が発生する条件付き確率密
度を
p( x | ci )  p( x1,, xr | ci )
とする
• 病気診断の例
–
–
–
–
c1=健康
c2=病気
P1 = (50+10+5+5)/100 = 0.7
P2 = (2+3+20+5)/100 = 0.3
5.0 / 7 ( x1  0, x2  0, i  1のとき )
1.0 / 7 ( x  0, x  1, i  1のとき )
1
2

0.5 / 7 ( x1  1, x2  0, i  1のとき )

0.5 / 7 ( x1  1, x2  1, i  1のとき )
p ( x1 , x2 | ci )  
0.2 / 3 ( x1  0, x2  0, i  2のとき )

0.3 / 3 ( x1  0, x2  1, i  2のとき )

2.0 / 3 ( x1  1, x2  0, i  2のとき )
0.5 / 3 ( x1  1, x2  1, i  2のとき )
ベイズの識別規則
•
f1 ( x)  p( x | c1 ) P1
f 2 ( x)  p( x | c2 ) P2
f ( x)  f1 ( x)  f 2 ( x)
としたとき
 f ( x)  0ならば xはc1に属する

 f ( x)  0ならば xはc2に属する
• 病気の診断の例
(5.0 / 7)  0.7  (0.2 / 3)  0.3  0.48 ( x  (0,0)のとき )
 (1.0 / 7)  0.7  (0.3 / 3)  0.3  0.07 ( x  (0,1)のとき )

f ( x)  
(0.5 / 7)  0.7  (2.3 / 3)  0.3  0.15 ( x  (1,0)のとき )
(0.5 / 7)  0.7  (0.5 / 3)  0.3  0
( x  (1,1)のとき )
がベイズの識別規則(=認識の誤
り確率が最小となる識別規則)と
なる
• あるいは
f1 ( x)
g ( x)  log
を使って
f 2 ( x)
 g ( x)  0ならば xはc1に属する

 g ( x)  0ならば xはc2に属する
とも書ける。このgが識別関数
となるので、
– 熱がなければ(x1=0)健康
– 熱があってせきが出なければ
(x1=1,x2=0)病気
– 熱がありせきが出る場合
(x1=1,x2=1)は病気と判断しても
健康と判断しても平均的な誤り確
率は変わらない
連続分布の場合
• 条件付き確率密度関数をそれぞれ平均ベクトル 1 , 2
で共分散行列 の正規分布の密度関数とする
p( x | ci ) 
 1

t 1
exp

(
x


)

(
x


)

i
i 
(2 ) r / 2 |  |1/ 2
2


1
• 最終的にgは以下のようになる
1
P
g ( x)  x t  1 ( 1  2 )  ( 1  2 )t  1 ( 1  2 )  log 1
2
P2
連続分布のパターン認識
2 古典パーセプトロンの学習
パーセプトロン
重み
w1,…,wn
出力
y
パターン
x1,…,xn
感覚層
(入力素子)
連合層
(隠れ素子)
反応層
(出力)
認識機械としてのパーセプトロン
• 入力x=(x1,…,xn)tが与えられたとき、重みwiを使って
出力yを計算する
w0  w1x1   wn xn
• このとき、出力が負ならxはクラスX0に属し、正ならx
はクラスX1に属するようにする
x  X 0 : w0  w1 x1    wn xn  0

x  X 1 : w0  w1 x1    wn xn  0
• 入力群と出力群が与えられたとき、重みを自動的に
決定したい
弛緩法による構成
• 重み w(k )  (w0 , w1 ,, wn )
t
x
(
k
)

(
x
,
x
,

,
x
)
x0  1
• パターン
0 1
n ,
• X0とX1に属するすべてのパターンを適当に無限に並
べる
x(1), x(2),, x(k ),
• 重みw(1)に適当な初期値(例えば(0,…,0))を入れ、
以下を収束するまで計算
t
 w(k )
x(k )  X 0かつ w(k )t x(k )  0のとき

t
w
(
k
)
x
(
k
)

X
かつ
w
(
k
)
x(k )  0のとき

1
w(k  1)  
t
w
(
k
)

x
(
k
)
x
(
k
)

X
かつ
w
(
k
)
x(k )  0のとき
0

w(k )  x(k ) x(k )  X 1かつ w(k ) t x(k )  0のとき
学習の簡単な例
x(2)=(1,0,1)t
=x(6)=x(10)=…
クラスX0
x(1)=(1,0,0)t
=x(5)=x(9)=…
x(4)=(1,1,1)t
=x(8)=x(12)=…
クラスX1
x(3)=(1,1,0)t
=x(7)=x(11)=…
学習の簡単な例(つづき)
w(1)t x(1)  (0,0,0)(1,0,0)t  0
w(2)t x(2)  (1,0,0)(1,0,1)t  1
w(3)t x(3)  (1,0,0)(1,1,0)t  1
w(4)t x(4)  (0,1,0)(1,1,1)t  1
w(5)t x(5)  (0,1,0)(1,0,0)t  0
w(6)t x(6)  (1,1,0)(1,0,1)t  1
w(7)t x(7)  (1,1,0)(1,1,0)t  0
w(8)t x(8)  (0,2,0)(1,1,1)t  2
w(9)t x(9)  (0,2,0)(1,0,0)t  0
w(10)t x(10)  (1,2,0)(1,0,1)t  1
w(11)t x(11)  (1,2,0)(1,1,0)t  1
w(12)t x(12)  (1,2,0)(1,1,1)t  1
w(2)  w(1)  x(1)  (0,0,0)t  (1,0,0)t  (1,0,0)t
w(3)  w(2)  (1,0,0)t
w(4)  w(3)  x(3)  (1,0,0)t  (1,1,0)t  (0,1,0)t
w(5)  w(4)  (0,1,0)t
w(6)  w(5)  x(5)  (1,1,0)t
w(7)  w(6)  (1,1,0)t
w(8)  w(7)  x(7)  (0,2,0)t
w(9)  w(8)  (0,2,0)t
w(10)  w(9)  x(9)  (1,2,0)t
w(11)  w(10)  (1,2,0)t
w(12)  w(11)  (1,2,0)t
w(13)  w(12)  (1,2,0)t
パーセプトロンは
1  2  x1  0  x2  1  2 x1
となり、パターンクラスを分割する識別面はx1=1/2になる
X
0
適用例
に
属
す
る
10
個
の
パ
タ
ー
ン
X
1
に
属
す
る
10
個
の
パ
タ
ー
ン
パターンの成分の数n=9
適用例(つづき)
適用例(つづき)
3 現代パーセプトロンの学習
シグモイド関数
1
 (s) 
s
1 e
ニューロンのアナログモデル
•
•
•
•
第2層の重みwij
第3層の重みvj
出力素子の出力 zk  gk ( y)   (v0k  v1k y1   vmk ym ), k  1,, l
隠れ素子の出力 y j  f j ( x)   (w0 j  w1 j x1   wnj xn ), j  1,, m
パーセプトロンの認識関数 h  g  f , h( x)  g ( f ( x))
誤差
1
2
E


(
x
)
||
h
(
x
)

d
(
x
)
||
• 誤差

2 | X | xX
• 学習パターン集合Xに属する学習パターンxとその認
識結果d(x)を人間が与えて学習させ、Eを最小化す
るパーセプトロンhを求めたい(dは目標関数と呼ば
れる)
• αは各パターンxにおけるhとdの近さに関する重要さ
の程度を表す重み、既知
• |X|はパターンの個数、||z||はユークリッドノルム
誤差逆伝搬学習法
• 第3層の重みの更新式
old
v new

v
jk
jk 

 2 k ( x) f j ( x) ( j  0,, m; k  1,, l )

|X| x
• 第2層の重みの更新式
wijnew  wijold 
•
•
•
•

1 j ( x) xi

|X| x
(i  0,, n; j  1,, m)
Δは十分小さな値
第3層の誤差  2k ( x)   (l x)[hk ( x)  dk ( x)]hk ( x)(1  hk ( x))



(
x
)


(
x
)
v
 2 k
jk  f j ( x)(1  f j ( x))
第2層の誤差 1 j
 k 1

δ1j(x)を求めるのにδ2k(x)を使う→誤差が出力側から
入力側に流れる→誤差逆伝搬学習法
1入力1出力のパーセプトロンの学習
N=5個の学習パターン
290回の重みの更新
4 KL展開
`
Karhunen-Loeve展開
• N個の属性を持つパターンX
X  ( X1, X 2 ,, X N )
t
• 実数値Wn(n=1,…,N)
• パターンXを以下で表現できる→KL展開
N
X  Wn  n
n 1
• 固有ベクトルを正規化したもの
 ,, 
1
N
近似
• これをK項(K≦N)までで打ち切り
K
X  Wk  k
k 1
• 固有値λkを大きい順に並べて
1  2    N  1
• λkに対応する固有ベクトルをμkとしたとき、上の打ち
切ったXは最も良い近似を与える
固有値問題
• 固有値問題    を解く
• N次元パターンJ個が入力
X 1  ( X 11 ,  , X 1N ),

X J  ( X 1J ,  , X NJ )
• ΣはパターンXの共分散行列(N次正方行列)
  E( X1, X 2 ,, X N )t ( X1, X 2 ,, X N )
1 J
  ( X 1j ,, X Nj )t ( X 1j ,, X Nj )
J j 1
適用例
N=10の学習パターン
□標準基底
○固有ベクトル
(c) Daisuke Miyazaki 2003
All rights reserved.
http://www.cvl.iis.u-tokyo.ac.jp/