データ学習アルゴリズム」

「データ学習アルゴリズム」
報告者佐々木稔
2003年8月1日
第3章複雑な学習モデル
3.2 競合学習
3.2.1 確率競合モデル
3.2.2 混合正規モデルの推論
3.2.3 混合分布の最急降下法
3.2.4 確率競合モデルとEMアルゴリズム
3.2.5 EMアルゴリズム
3.2.6 ノンパラメトリック学習
3.2.7 自己組織化写像
一般的なモデルでのEMアルゴリズム
確率モデル p(x, u | w)
競合的な確率変数 U は観測されない
確率変数 X はモデルから観測される
観測データ x1, x2, ･･･, xn
最適な分布となるパラメータを学習する
EMアルゴリズムの概略図
山の形（分散）は同じで中心（分布の平均）が最適な場所に移動
学習データ
中心の初期値
から
に
中心移動が繰り
返される
損失関数
n
nLn ( w)   log p( xi | w)
i 1
損失関数を最小にするパラメータを見つける
w を固定したとき、u の関数 f(u) の平均
Eu  f (u ) | x, w   f (u ) p(u | x, w)du
u は 0 と 1 だけとるので、
n
Gw1 , w2    Eu log p( xi , u | w2 ) | xi , w1
i 1
EMアルゴリズム
n
Gw1 , w2    Eu log p( xi , u | w2 ) | xi , w1
i 1
1. w1 を初期化
2. w1 を固定して G(w1, w2) が
最小となるように w2 を定める。（Eステップ）
3. w1 := w2 として 2. に戻り、以降 2. 3. を
適当な回数だけ繰り返す。（Mステップ）
n
G w1 , w2    Eu log p( xi | w2 ) p(u | xi , w2 )  | xi , w1
i 1
n
n
i 1
i 1
  log p( xi | w2 )   Eu log p(u | xi , w2 ) | xi , w1
n
 nLn ( w2 )   Eu log p(u | xi , w2 ) | xi , w1
i 1
w2 における損失関数
n
G * w1 , w2   G w1 , w2    Eu log p(u | xi , w1 ) | xi , w1
i 1


p(u | xi , w1 )
 nLn ( w2 )   Eu log
| xi , w1 
p (u | xi , w2 )
i 1


n
右辺第2項はカルバックの擬距離
G*(w1, w2) は、
「w2 が Ln(w2) を最小にし、かつ w1=w2」
のとき最小で、最小値は「nLn(w2) の最小値」と等しい
1. w1 を固定し、G(w1, w2) を最小にする w2 を見つける
n
G w1 , w2   Gw1 , w2    Eu log p(u | xi , w1 ) | xi , w1
*
i 1
最小値
G*(w1, w2) の値は減少する
w2 には関係ない定数
2. w1 に w2 を代入する


p(u | xi , w1 )
G w1 , w2   nLn ( w2 )   Eu log
| xi , w1 
p(u | xi , w2 )
i 1


n
*
w1、w2 が同じ値なので、擬距離は 0
G*(w1, w2) の値は、最適化したい
損失関数 nLn(w2) に等しくなる
Ln(w2) を小さくするパラメータ w2 が見つかる
［注２７］
局所解に落ちた場合
• その局所解に収束してしまうかどうか
• 繰り返しで局所解から脱出するのかどうか
詳しい動作はまだ明らかになっていない
「だいたいよい推定量」を探すことも多い
理論的にも実用的にも重要な問題
確率競合モデルのEMアルゴリズム
パラメータ w :
H


H
w  ah , bh h1;  ah  1, ah  0
h 1


確率変数 X, U
n
p( xi , u | w2 )   ah q( xi | bh )
uh
h 1
n
log p( xi , u | w2 )   uh log ah  log q( xi | bh )
h 1
ここで、パラメータ bh での確率分布 q(x | bh)
q( x | bh ) 
1
2 
2
h
M
2
 x  h
exp 
2

2

h

2




固定したパラメータ w1 = w = (ah, bh), bh = (ξh, σh)
最適化するパラメータ w2 = w = (ah, bh), bh = (ξh, σh)
w に固定したときの uh の平均 Ei(h)
Ei (h)  Eu {uh | xi , w} 
u
u h 0 ,1
h
p(u | xi , w) 
ah q( xi | bh )
p( xi | w)
u の平均値 Ei(h) をすべての xi に関して和を求める
n
H
Gn ( w, w)   Ei (h)log ah  log q( xi | bh )
i 1 h 1
Gn(w, w) が最小となる w を求める
1 n
ah   Ei (h)
n i 1



（係数）
n
h
E
(
h
)
x
i
i
i 1
n
i 1
Ei (h)


n
( h )
2
（正規分布の平均）
i 1
Ei (h) xi   h
M i 1 Ei (h)
n
（正規分布の分散）
［注２８］
与えられたデータをいくつかのクラスタに分類
K-means 法
データ {xi ∈ RM; i = 1, 2, ･･･, n}
データを H 個のクラスタに分類する
クラスタ Ch の重心 ξh
データ xi を距離 || xi – ξh|| が最小になる
クラスタ Ch に分類し、重心 ξh を再計算
h



iCh
iCh
xi
1
クラスタの重心 {ξh} を繰返し求めて最適化
［注２８］の続き
EMアルゴリズムを使う場合の注意
• クラスタの大きさに偏りがある場合、
偏りを緩和させる必要
• クラスタの個数 H を最適化する際、
 情報量規準を使うことはできない
 損失関数の2次近似をすることができない
比較的大きめな H を決めて、EMアルゴリズムを
少ない回数で停止させるとクラスタの偏りが緩和
例４６確率競合型モデルと3層パーセプトロンの比較
10人が描いた 8×8 ピクセルの ○、△、× の
画像 600 例を学習
同じく10人が描いた 8×8 ピクセルの
画像 600 例をテストに用いる
確率競合型モデル
K-means法で初期化したパラメータを最急降下法で学習
3層パーセプトロン
誤差逆伝播法で学習
中間ユニット数 20 までの場合の認識率
確率競合型モデル
96～98.5％
3層パーセプトロン
98～98.5％
中間ユニット数 20 までの場合の認識率
確率競合型モデル
98.5～99％
3層パーセプトロン
98～98.5％

Download Report