1/5知能システム論ノート（第11回）
- 隠れマルコフモデル（メイン）
- 系列ラべリング
- 入力：文字列（単語列）、出力：ラベル
- 系列構造をもった問題に適用される
- 音声
- 品詞タグ付け
- かな漢字変換
- 動画認識
- John[N] bought[V] a[冠詞] book[N]
- 隠れマルコフモデル(HMM)
- 状態遷移を表す確率モデル
- 状態を移動しながら、各状態から記号を出力する
- 状態列：s = s1, ・・・, sn
- 記号列：w = w1, ・・・, wn
- 名詞 動詞 冠詞 名詞 （状態列s）
- John bought a book （記号列w）
- 非決定性有限状態オートマトンに確率がついたものだと考えられる。
- 遷移確率：状態を移動する確率
- 出力確率：記号を出力する確率
- 単語列w, 品詞列sの同時確率
- p(w, s) = Π{t = 1 to n} (PT(s[t] | s[t-1]) * PE(w[t] | s[t]))
- PT(s[t] | s[t-1]) : 遷移確率
- PE(w[t] | s[t]) : 出力確率
- いろいろ独立性が仮定されている
- 現在の品詞が来る確率は直前の品詞にのみ依存し、現在の単語は現在の品詞にのみ依存すると仮定
- s[0]は別途定義する
- 定式化
- 隠れマルコフモデルM=<Q, Σ, q0, pT, pE>
- Q:状態集合
- Σ:記号の集合
- q0:初期状態
- pT(a|b):状態bから状態aに遷移する確率
- pE(o|a):状態aから記号oを出力する確率
- 状態・記号列の確率
- p(w, s) = Π{t = 1 to n} (pT(s[t] | s[t-1]) * pE(w[t] | s[t]))
- HMMの諸問題
- HMMをどうやって系列ラべリングに適用するのか？
- HMMのパラメータはどうやって学習するのか？
- HMMを用いたラべリング
- 単語列wが与えられたとき、確率最大の状態列ｓを求める
- s^ = argmax{s} p(s|w) = argmax{s} p(s,w)/p(w) ∝ argmax{s} p(s,w) = argmax{s} Π{t = 1 to n} pT(s[t]|s[t-1])pE(w[t]|s[t])
- すべての状態列を列挙し、確率最大の状態列ｓを出力すればよい＝＞が、難しい（計算量的に）
- 指数爆発
- 状態列sの数は、単語数に対して指数爆発してしまう。
- 品詞が10個だと20単語だと10^20 = 1がい
- 動的計画法で解く
- 指数爆発しないように確率値や状態列を計算
- ビタビアルゴリズム：確率最大の状態列を求める動的計画法
- ビタビ(Viterbi)アルゴリズム
- トレリス
- 状態を縦に並べ遷移可能な状態の間を結ぶ
- トレリス上の遷移系列＝状態列
- 画像はググれ（http://t3.gstatic.com/images?q=tbn:ANd9GcTvLspLQE5mqtZiv7nTdfOpa05LBn8nAEXHSEY0vRrzj35gmqnqOA）
- まずはp(w, s)の最大値を求める問題を考える
- 左から順番に、各状態までの確率の最大値を計算する
- i単語目の品詞がtになる品詞列s[1], ・・・, s[i]の確率の最大値を考える
- δ[i](t) = max{s[1], ・・・s[i-1]} p(w[1]・・・w[i], s[1]・・・s[t-1]s[i]=t)(s[i]がｔとなるような品詞列)
- = max (p(w[i]|s[i]=t) p(s[t]=t|s[i-1]) p(w[1]・・・w[i-1], s[1] ・・・s[i-1]))
- = p(w[i]|s[i]=t) max (s[i-1]p(s[i]=t|s[i-1])δ[i-1](s[i-1]))
- for i = 1 to n
- for t = t1 to tk（品詞）
- δ[i](t) = p(w[i]|s[i]=t) max{s[i-1]} p(s[i] = t| s[i-1]) δ[i-1](s[i-1])
- 計算量 = n * k^2 (単語数 * 品詞数^2)
- 教師あり学習・教師なし学習
- パラメータの学習
- どうやって遷移確率・出力確率を決めるのか
- 教師あり学習：正解つきのデータから確率を学習する
- 教師なし学習：正解なしデータ（ただの記号列）から確率を学習する。
- 教師あり学習
- タグ付きコーパス：人手で正解を付与したデータ
- 教師あり学習＝品詞タグ付きコーパスから最尤推定（C：Count？）
- 遷移確率：品詞の並び<t, s>を数える
- 推移確率：単語と品詞のペア<w, s>を数える
- スムージングしないといけない？
- 教師なし学習
- タグなしコーパス（唯のテキストデータ）ｋらパラメータを学習
- タグなしコーパスは最優推定法では無理
- EMアルゴリズム
- Expectation-Maximizationアルゴリズム
- 不完全データから確率を推定する手法
- アルゴリズム
- パラメータをランダムに初期化
- Eステップ：現在のパラメータで期待値を計算
- Mステップ：期待値を使ってパラメータを更新
- 収束するまでE・Mステップを繰りかえす
- Eステップ
- 各遷移の・各出力の期待値を計算
- E[s[t-1]=ρ, s[t]=τ] = Σ{w, s}p(w, s) = Σp(w[1]・・・w[n], s1・・・s[t-2]ρτs[t+1]・・・s[n])
- E[s[t]=τ, s[t]=ω] = Σ{w, s when s[t] = τ, w[t] = ω}p(w, s)
- = Σp(w[1], ・w[t-1]ωw[t+1]・・w[n], s1 ・・・s[t-1]τs[t+1]・・・s[n])
- その期待値を使ってパラメータを計算
- pT(s'|s) = E[s',s]/E[s]
- pE(w|s) = E[w,s]/E[s]
- 期待値の計算
- 状態を満たすすべての状態列を列挙すると、指数爆発する
- Baum-Welchアルゴリズム
- 前向き・後ろ向きアルゴリズム：前向き・後ろ向き確率を効率的に計算する動的計画法
- Baum-Welchアルゴリズム：前向き・後ろ向き確率を使ったEMアルゴリズム
- 前向き・後向き確率
- 前向き確率
- s[t] = τとなるすべての状態列s[1]、・・・、s[t]の確率の和
- φ[t](τ) = Σp(w[1]・・・w[t], s[1]・・・s[t-1]τ)
- = Σp(w[t]|τ)p(τ|s[t-1])p(w[1]・・・w[t-1], s[1]・・・s[t-1])
- = p(w[t]|τ) Σp(τ|s[t-1])φ[t-1](s[t-1])
- 後ろ向き確率
- s[t] = τとなるすべての状態列s[ｔ]、・・・、s[ｎ]の確率の和
- ψ[t](τ) = ・・・ = p(w[t]|τ) Σp(s[t+1]|τ)ψ[t+1](s[t+1])
- 期待値の計算
- E[s[t-1]=ρ, s[t]=τ] = Σp(w[1]・・・w[n], s[1]・・・s[t-2]ρτs[t+1]・・s[n])=φ[t-1](ρ)pE(w[t]|τ)ψ[t](τ） ＜＝なんか違うらしい
- 動的計画法のポイント
- 分配法則によって積の和を和の積にする
- X1A + X2A + X3A = (X1 + X2 + X3)A
- X1AY1 + X2AY1 + X3AY1 + X1AY2 + X2AY2 + X3AY2 + X1AY3 + X2AY3 + X3AY3 = (X1 + X2 + X3)A(Y1 + Y2 + Y3)
- 確率モデルや線形分類器で使われる動的計画法は、ほとんどこの形
- EMアルゴリズムの特徴
- パラメータ更新ごとに尤度が上がる
- 目的関数は突ではない
- 局所最適値がある（最適とは限らない）
- EMの収束値は初期値に依存する
- ビタビアルゴリズムと前向き・後ろ向きアルゴリズムの関係
- これらのアルゴリズムはほとんど同じ
- ビタビ：積の最大値
- δ[t](τ) = p(w[t]|τ)max{s[t-1]}p(τ|s[t-1])δ[t - 1](s[t-1])
- 前向き・後ろ向き：積の和
- φ[t](τ) = p(w[t]|τ)Σ{s[t-1]}p(τ|s[t-1])φ[t - 1](s[t-1])
- 両方とも分配法則を利用している
- max(AX, AY) = A max(X, Y)
- sum(AX, AY) = A sum(X, Y)