パターン認識論 #2

パターン認識論 第２回 伊藤 彰則 [email protected] @akinori_ito 1

ＮＮ法と線形識別関数（１） ◼ プロトタイプとパターンの距離が最小になる プロトタイプpiを選ぶ || x − pi ||→ min || x − pi || → min 2 ( x − pi ) t ( x − pi ) =|| x || 2 −2 x  pi + || pi || 2 → min 1 x  pi − || pi || 2 → max 2 2

補足：ベクトルの内積  x1    t x = ( x1 , x2 ,..., xd ) =    x   d  y1    t y = ( y1 , y2 ,..., yd ) =    y   d d x  y = x y =  xi yi t i =1 d || x || 2 = x t x =  xi2 i =1 3

線形識別関数 ◼ 一般の線形識別関数：xの一次関数 d g ( x ) = w0 + w  x = w0 +  wi xi i =1 ◼ 次のような「拡張特徴ベクトル」を考える 1  w0       x1   w1  x=  w =        x  w   d  d t g ( x) = w x 4

NN法と線形識別関数 NN法 1 2 g ( x ) = pi  x − || pi || 2 ◼ 線形識別関数 ◼ g ( x) = w  x + w0 ◼ NN法は線形識別関数の一種 ◼ 逆は成り立たない 5

多クラスの線形識別関数 ◼ クラス数をcとする t gi ( x) = w i x i = 1,..., c iˆ = arg max g i ( x ) i これがパーセプトロンだ！ 1 x1 x2 x3 x4 w10 w11 w12 w13 w14  g1 ( x )  g 2 ( x)  g3 ( x) 6

パーセプトロン学習 パーセプトロンの重みを学習するアルゴリ ズム ◼ サンプルx1 ,..., x nのクラス (x1 ),..., (x n ) 1. 2. 3. 重みw1…wCを初期化 k=1,2,…nについて  (x k ) =  iのとき，arg max w l x k = j (i  j ) ならば t l 𝒘𝑖 ← 𝒘𝑖 + 𝜌 ⋅ 𝒙𝑘 𝒘𝑗 ← 𝒘𝑗 − 𝜌 ⋅ 𝒙𝑘 4. (   0) 修正がなければ終了 7

なぜこれでよいのか？ 𝒘′ = 𝒘 + 𝜌 ⋅ 𝒙とする 𝒘′t 𝒙 = (𝒘 + 𝜌 ⋅ 𝒙)t 𝒙 = 𝒘𝑡 𝒙 + 𝜌𝒙𝑡 𝒙 = 𝒘𝑡 𝒙 + 𝜌||𝒙||2 すなわち𝜌 > 0なら𝒘𝑡 𝒙は大きくなり，𝜌 < 0なら小さくなる 内積 𝒘𝑡 𝒙 が誤分類の場合は正しいクラスの値が大きくなり、誤っ たクラスの値が小さくなるように係数を修正 8

線形分離可能性 パーセプトロン学習は「誤りがあったら修正｣ →原理的に誤りが起きる場合は収束しない ◼ 教師データが｢線形分離可能」な場合のみ 収束する ◼ 線形分離可能 線形分離不可能 9

区分的線形識別関数 ◼ 非線型な識別関数を折れ線で近似 ◼ ◼ 例：すべての教師データをプロトタイプとする「全数記 憶方式｣ 一般的な学習アルゴリズムは知られていない ◼ 特殊な場合：全数記憶，学習ベクトル量子化(LVQ)な ど 10

線形分離不可能な場合の学習 ◼ 線形分離不可能な場合 パーセプトロン学習は収束しない ◼ 完璧でなくても，何らかの意味で最善の識別関 数が学習できれば都合が良い ◼ ◼ 望ましい識別関数出力との２乗誤差が最小 になるように学習してみよう 重みw i パターンx pと，その教師信号b p c n ２乗和 (w i x p − b p ) → 最小 t 2 i=1 p =1 11

パーセプトロンと教師信号 1 x1 1のパ ターン x 2 を入力 x3 x4 w10 w11 w12 w13 w14 教師信号bp t g ( x )  1 誤差 = w 1 x − bp  1  g2 ( x)  0  g3 ( x)  0 出力が教師信号に近づくように 重みを学習する 12

δルールによる学習 ◼ 次の式により重みを更新 𝒘𝑖 ← 𝒘𝑖 − 𝜌(𝒘𝑖 𝑡 𝒙𝑝 − 𝑏𝑝 )𝒙𝑝 更新の重みを教師信号との誤差に比例させる ◼ その他の部分はパーセプトロン学習とほぼ同じ ◼ 誤差の２乗和の減少が止まったところで停止 ◼ 13

δルールと勾配法 ◼ δルールは勾配法の一種 入力𝒙、パラメータ𝜽に対して 𝑦 = 𝐹 𝒙, 𝜽 を計算し、𝑦と教師信号𝑦0 から損失𝐿(𝑦, 𝑦0 )を求 める ◼ 損失が最小になるように𝜽を調整する ◼ 𝜽を微小に変化させたときに𝐿が減少する方向 に𝜽を動かす 𝜕𝐿 𝜽←𝜽−𝜌 𝜕𝜽 ◼ 14

δルールと勾配法 ◼ パーセプトロンの場合 ◼ 𝜽 = (𝒘1 , … , 𝒘𝐶 ) 2 𝑡 ◼ 𝐿 = σ𝑐 𝒘𝑐 𝒙𝑝 − 𝑏𝑐𝑝 𝜕𝐿 ◼ = 2(𝒘𝑡𝑐 𝒙𝑝 − 𝑏𝑐𝑝 )𝒙𝑝 𝜕𝒘C 𝜕𝐿 ◼ 𝒘𝑐 ← 𝒘𝑐 − 𝜌 𝜕𝒘𝑐 = 𝒘𝑐 − 2𝜌(𝒘𝑡𝑐 𝒙𝑝 − 𝑏𝑐𝑝 )𝒙𝑝 15

ニューラルネットワーク ◼ 多層パーセプトロン＋非線型＝ニューラル ネットワーク 1 1 x1 x2 x3 x4 入力層 (1) 11 w h1(1) g1(1) ( 2 ) h1( 2) g ( 2) 1 w11 中間層 (隠れ層) 出力層 16

ニューラルネットワーク ◼ 第k層の第ｉユニットの入力と出力 (0) 𝑔𝑖 = 𝑥𝑖 (𝑘) (𝑘) (𝑘−1) ℎ𝑖 = ෍ 𝑤𝑗𝑖 𝑔𝑗 𝑗 (𝑘) (𝑘) 𝑔𝑖 = 𝑓(ℎ𝑖 ) 1 𝑓(𝑥) = 1 + 𝑒 −𝑥 f は活性化関数（アクティベーション） 上記は「シグモイド関数」 それ以外にも様々なものがある 17

ニューラルネットワークの能力 ◼ 非線型関数がミソ ◼ 非線型関数がないと，結局パーセプトロンと同 じになる 中間層が多ければ任意の非線型境界が表 現できる（でも学習できるとは限らない) ◼ 極限では区分的線形識別関数と同じ ◼ 効率の良い学習アルゴリズムが知られてい る（誤差逆伝播法） ◼ 18

演習 ◼ 非線形性のない3層ネットワークは，2層の パーセプトロンと等価であることを示せ. ニューラルネットでf(x)=xの場合に相当 ◼ まず下の例から行ってみよう ◼ 1 x1 x2 1 g (x) (1) ij w ( 2) ij w 19

ニューラルネットワークの学習 δルールと同じようなやり方にしたい 𝒘𝑖 ← 𝒘𝑖 − 𝜌(𝒘𝑖 𝑡 𝒙𝑝 − 𝑏𝑝 )𝒙𝑝 入力 𝒙𝑝 出力 𝒘𝑖 𝑡 𝒙𝑝 教師信号 𝑏𝑝 活性化関数が問題になる 入力 𝒙𝑝 出力 𝑓(𝒘𝑖 𝑡 𝒙𝑝 ) 教師信号 𝑏𝑝 20

勾配法による導出 2 𝑡 ⚫ 𝐿 = 𝑓(𝒘 𝒙𝑝 ) − 𝑏𝑝 𝜕𝐿 ⚫ = 2 𝑓 𝒘𝑡 𝒙𝑝 ) − 𝑏𝑝 𝜕𝒘 𝑓 ′ 𝒘𝑡 𝒙𝑝 𝒙𝑝 ⚫ 𝒘 ← 𝒘 − 2𝜌 𝑓 𝒘𝑡 𝒙𝑝 ) − 𝑏𝑝 学習 出力側の誤差 係数 入力 𝒙𝑝 𝑓 ′ 𝒘𝑡 𝒙𝑝 𝒙𝑝 活性化関数 入力 の微係数 ベクトル 出力 𝑓(𝒘𝑖 𝑡 𝒙𝑝 ) 教師信号 𝑏𝑝 21

シグモイド関数の微分 ◼ ◼ 𝑔=𝑓 ℎ 𝑓′ ℎ = 1 = 1+𝑒 −ℎ −𝑒 −ℎ 1 −𝑒 −ℎ = ∙ 2 −ℎ −ℎ −ℎ 1+𝑒 1+𝑒 1+𝑒 =𝑓 ℎ 1−𝑓 ℎ = 𝑔(1 − 𝑔) 22

誤差逆伝播法 ◼ 非線型関数と誤差 ＋ hi( 2 ) g i( 2) = f (hi( 2 ) )  i( 2 ) = ( g i( 2) − bi ) f ' (hi( 2) ) = ( g i( 2 ) − bi ) g i( 2 ) (1 − g i( 2 ) ) ＋ hi(1) 教師信号 ｂｉ g i( 2 ) − bi 1( 2 )  2( 2 )  3( 2 )  4( 2 )  i(1) = (  k( 2 ) wik( 2) ) f ' (hi(1) ) k = (  k( 2 ) wik( 2 ) ) g i(1) (1 − g i(1) ) k 23

誤差逆伝播（BP)法 ◼ 重みの学習 w  w −  g (l ) ij (l ) ij (l ) j ( l −1) i 出力層の誤差 ( 2) ( 2) ( 2) ( 2)  j = ( g j − b j ) g j (1 − g j ) ◼ 中間層の誤差 (1) ( 2 ) ( 2 ) (1) (1)  j =   k w jk g j (1 − g j ) ◼ k 24

ありがちなニューラルネットの例 ◼ ＸＯＲの学習 1 1 1.34 入力x O 入力y ２次元で線形分離不可能 な最小のパターン 3.07 -1.51 2.95 3.75 -2.67 -3.55 出力 3.30 -3.45 学習結果 25

学習結果 26

ニューラルネットと NN法 ◼ XORは１つの線形識別関数では表せない ◼ O 区分的線形な識別関数ならOK O 学習データの各点をプ ニューラルネットでは ロトタイプにすれば完全 このような識別境界 な識別が可能 が学習された O こんな風にプロトタ イプを配置すれば 同じ識別境界が表 現できる 27

パラメトリックな識別 いままでは学習データから識別関数を直接 学習していた ◼ 学習データがある確率分布に従うと仮定 ◼ 確率分布のパラメータを推定する ◼ 確率密度関数を識別関数として利用 ◼ パラメトリックな識別 28

何が違うの？ ◼ １次元の識別 ◼ 識別関数の学習による場合 ◼ 確率密度関数を推定する場合 29

確率密度関数 ◼ あるクラスのパターンxが来る確率密度 p( x |  )  p( x |  )dx = 1 ◼ あるクラスの生起確率 P( i ) c  P( ) = 1 i =1 i 30

代表的な密度関数：正規分布 １次元の場合 (𝑥 − 𝜇)2 𝑝(𝑥) = exp − 2𝜎 2 2𝜋𝜎 2 1 m：平均 s：標準偏差 正規分布 (ガウス分布) 31

◼ d次元での正規分布 1 1 𝑡 Σ −1 (𝐱 − 𝝁) 𝑝(𝐱) = exp − (𝐱 − 𝝁) 2 (2𝜋)𝑑/2 |Σ|1/2 m: 平均ベクトル :共分散行列 𝛍 = (𝜇1 , 𝜇2 , . . . , 𝜇𝑑 ) Σ= 𝜎12 𝜎21 ⋮ 𝜎𝑑1 𝜎21 𝜎22 ⋮ 𝜎𝑑2 ⋯ 𝜎1𝑑 ⋯ 𝜎2𝑑 ⋱ ⋮ ⋯ 𝜎𝑑2 ２次元正規分布 32

共分散行列 ◼ 多次元正規分布を輪切りにすると，断面は 楕円（一般には超楕円体)になる O は単位行列 (m1,m2 ) は対角行列 は対称行列 33

確率から識別関数へ ◼ 確率密度が求まったとして,どう認識するの か パターンx，クラス1…c ◼ パターンxが，あるクラスに属する確率 ◼ P(i | x ) これが最大になるクラスに分類する ◼ この確率をどう計算するか？ 34

Bayesの決定則 𝜔 ෝ = argmax 𝑃(𝜔|𝐱) 𝜔 𝑝(𝐱|𝜔)𝑃(𝜔) = argmax 𝑝(𝐱) 𝜔 = argmax 𝑝(𝐱|𝜔)𝑃(𝜔) 𝜔 あるクラスの確率密度関数×そのクラスの出現確率 35

補足：Bayesの定理 ◼ 同時確率と条件付確率の関係 P(a, b) = P(a ) P(b | a ) = P(b) P (a | b) P (a | b) P(b) P(b | a ) = P(a) 36

パラメータの決定法 分布の推定＝パラメータの推定 ＝学習データから平均ベクトルと共分散行 列を求める ◼ 学習データ 𝑋 = 𝒙1 , 𝒙2 , . . . , 𝒙𝑛 ◼ 最尤(ML)推定法 ：最も普通の推定 ◼ 分布のパラメータをとする ◼ 𝑃(𝑋|𝜽)が最大となるを推定パラメータとする ◼ 37

最尤推定 ◼ 最尤推定で平均と共分散を求めると 𝑛 1 𝝁 = ෍ 𝒙𝑖 𝑛 𝑖=1 𝑛 1 Σ = ෍(𝒙𝑖 − 𝝁)(𝒙𝑖 − 𝝁)t 𝑛 𝑖=1 38

平均はどうして平均なのか？ ◼ 最尤推定による平均の導出 ◼ 分散は既知,平均が未知な正規分布N(m,s2)か ら生成されたサンプルx1…xn p( X | m ) =  i 2  ( xi − m )  1  exp − 2 2s 2 s    ( xi − m ) 2  1 log p ( X | m ) =   − − log s − log 2  2 2s 2 i   d log p( X | m ) = 0とおく dm 2( xi − m ) 1 i − 2s 2 = 0  i xi − nm = 0  m = n i xi 39

普通の識別関数との関係は？ ◼ 確率の対数を識別関数にしてみよう   (x − μ ) t  −1 (x − μ )  1 −  log p ( x |  ) = log exp d /2   2 |  |1 / 2  (2 )   (x − μ ) t  −1 (x − μ ) d 1 =− − log 2 − log |  | 2 2 2 ◼ xとmのマハラノビス距離 −1 d M (x, μ ) = (x − μ )  (x − μ ) 2 t 40

マハラノビス距離 ◼ 距離が一定の点の軌跡を見てみよう （2次元の場合） ユークリッド距離 ◼ 重みつきユーク リッド距離 マハラノビス距離 正規分布による確率的な識別は,マハラノビ ス距離を使ったNN法に近い 41

マハラノビス距離と識別境界 ◼ ２つのクラスで共分散行列が異なる場合 識別境界は２次曲線 になる 42

識別関数による方法と確率分布による方法の比 較 ◼ 識別関数による方法の利点 ◼ ◼ 確率分布による方法の利点 ◼ ◼ 事前に分布の形を仮定する必要がない 識別に関する情報を他の情報(クラスの出現し やすさなど）と組み合わせるのが容易 複雑な形状の分布の扱い 混合正規分布でデータの分布を近似 ◼ 複数プロトタイプのNN法と限りなく近くなる ◼ 43

混合正規分布 ◼ 実際の分布が正規分布であらわせるかどう かは疑問 →複雑な分布を複数の正規分布の和で近 似 𝑝(𝐱) = ෍ 𝜆𝑘 𝑝(𝐱|𝛍𝑘 , Σ𝑘 ) 𝑘 ෍ 𝜆𝑘 = 1 𝑘 44

注意：混合正規分布 ◼ 混合正規分布と正規分布する確率変数の和を混 同してはいけない 平均1cm，標準偏差5mmの棒の束と，平均2cm，標準 偏差7mmの棒の束がある ◼ 両方の束から棒を1本ずつとり,両方を加えた長さを測 る ◼ 正規分布する確率変数の和 ◼ 平均3cm，標準偏差8.6mm ◼ ◼ どちらかの束から棒を1本だけとり,その長さを測る 両方の分布を混合した混合正規分布 ◼ λはそれぞれの束から棒を取り出す確率 ◼ 45