隠れマルコフモデルのパラメータ推定
2/29/2020, 12:10:13 PM - 409 days ago
単語列のような系列データのラベリング問題を考える. 入力としてある記号列が与えられた際, 適切なラベル列を出力したい.
このような問題に対して HMM(隠れマルコフモデル)というモデルを仮定することが多い. ここでは隠れマルコフモデルにおけるパラメータ推定についてまとめておく.
問題設定
S: 状態の集合
Σ: 出力記号の集合
πi: 文頭が状態 i になる確率
ai,j: 状態 i から j への遷移確率
bi,o: 状態 i における記号 o の出力確率
とする. ただし, ∑i∈Sπi=1,∑j∈Sai,j=1,∑o∈Σbi,o=1.
もし仮に πi,ai,j,bi,o が分かってしまえば, 入力の記号列から, 最も生成確率の高い状態列(ラベル列)を推定するのは容易である.
これには Viterbi アルゴリズムという名前の付いた動的計画法を使う. その原理は, 時刻 t+1 において状態 k にいたる状態列のうち,
もっとも確率の高くなるものを qt+1(k) とすると,
qt+1(k)=imax[qt(i)ai,k]bk,ot+1 と再帰的に書けることによる.
ここでは, 学習データからパラメータ πi,ai,j,bi,o を上手く求めることを考えていきたい.
最尤推定
学習データが D={o(k),s(k)}k=1N という形で書けるような, ラベルを含む教師付きデータである場合は, 直接最尤推定法を使うことができる.
学習データのある1つの入力列とラベル列の組に対して, その生成確率の対数は
logπs1t=1∏Tast,st+1bst,ot=logπs1+t=1∑Tlogast,st+1+t=1∑Tlogbst,ot という形で書ける.
よって, 制約にも注意すると, ラグランジュ関数は
L=k=1∑N(logπs1+t=1∑Tlogast,st+1+t=1∑Tlogbst,ot)+λπ(1−i∈S∑πi)+i∈S∑λai(1−j∈S∑ai,j)+o∈S∑λbi(1−o∈Σ∑bi,o) というように書ける(実際には si や T は各データのインデックス k に依存しているので, この式は不正確).
パラメータについて偏微分を取ると
∂πi∂L=πiC(s1=i)−λπ∂ai,j∂L=ai,jC(i,j)−λai∂bi,o∂L=bi,oC(i,o)−λbi ただし, C(i,j) は D 中の i→j の出現回数.
これらについて =0 を取ったもの, 及び制約を合わせて考えると, パラメータを求めることができる. 数式は省くが, 具体的には,
πi:(状態 i から始まるデータの個数)/(全データ個数)
ai,j:(状態 i→j の遷移の総数)/(状態 i から始まる遷移の総数)
bi,o:(状態 i が記号 o を出力する総数)/(状態 i の総数)
となる.
Baum-Welch アルゴリズム
学習データが D={o(k)}k=1N という形で書けるような, ラベルを含まない教師無しデータである場合を考える. ここでは, EM アルゴリズムの一種である Baum-Welch アルゴリズムについて述べる.
EM アルゴリズムは, 一般的には
Eステップ: 前のMステップで求めたパラメータを用いて隠れ変数(期待値)を更新する
Mステップ: 前のEステップで求めた隠れ変数(期待値)を使ってパラメータを更新する
という操作を繰り返す.
Baum-Welch アルゴリズムにおいては, 隠れ変数として
「時刻 t において状態が i になる期待値」: γt(i)=p(st=i∣θold)
「時刻 t において, 次の遷移が i→j になる期待値」: ξt(i,j)=p(st=i,st+1=j∣θold)
を用いる.
まずMステップに関しては, 先ほどの最尤推定の結果を, 隠れ変数を使って代用することを考えて,
πi∗=ai,j∗=bi,o∗=γ1(i)∑j∈S∑tξt(i,j)∑tξt(i,j)∑tγt(i)∑t s.t.ot=oγt(i) と計算できる.
次にEステップについて考えよう. 全ての状態遷移から st=i,st+1=j となる系列について考えると
計算量が爆発してしまうので, ここでも動的計画法を活用する.
具体的には, 前のMステップで求めたパラメータから前向き確率, 後ろ向き確率を計算する. 前向き確率 αt(i) は「時刻 t に状態 i に至る全ての系列の確率の和」,
後ろ向き確率 βt(i) は「時刻 t の状態 i から最後に至る全ての系列の確率の和」のことであり,
いずれも Viterbi アルゴリズムと同程度の計算量で求めることができる.
前向き確率 αt(i), 後ろ向き確率 βt(i) が求まれば,
γt∗(i)=∑k∈SαT(k)αt(i)βt(i) ξt∗(i,j)=∑k∈SαT(k)αt(i)ai,jbj,ot+1βt+1(j) より γt(i),ξt(i,j) も新しく求まり, これがEステップとなる.