reading and coding ...

隠れマルコフモデルのパラメータ推定

2/29/2020, 12:10:13 PM - 140 days ago

単語列のような系列データのラベリング問題を考える. 入力としてある記号列が与えられた際, 適切なラベル列を出力したい.
このような問題に対して HMM(隠れマルコフモデル)というモデルを仮定することが多い. ここでは隠れマルコフモデルにおけるパラメータ推定についてまとめておく.

問題設定

SS: 状態の集合
Σ\Sigma: 出力記号の集合
πi\pi_i: 文頭が状態 ii になる確率
ai,ja_{i, j}: 状態 ii から jj への遷移確率
bi,ob_{i, o}: 状態 ii における記号 oo の出力確率

とする. ただし, iSπi=1,jSai,j=1,oΣbi,o=1\sum_{i \in S} \pi_i = 1, \sum_{j \in S} a_{i, j} = 1, \sum_{o \in \Sigma} b_{i, o} = 1.


もし仮に πi,ai,j,bi,o\pi_i, a_{i, j}, b_{i, o} が分かってしまえば, 入力の記号列から, 最も生成確率の高い状態列(ラベル列)を推定するのは容易である.
これには Viterbi アルゴリズムという名前の付いた動的計画法を使う. その原理は, 時刻 t+1t+1 において状態 kk にいたる状態列のうち, もっとも確率の高くなるものを qt+1(k)q_{t+1}(k) とすると,

qt+1(k)=maxi[qt(i)ai,k]bk,ot+1q_{t+1}(k) = \max_{i} [q_{t}(i)a_{i, k}] b_{k, o_{t+1}}

と再帰的に書けることによる.


ここでは, 学習データからパラメータ πi,ai,j,bi,o\pi_i, a_{i, j}, b_{i, o} を上手く求めることを考えていきたい.

最尤推定

学習データが D={o(k),s(k)}k=1ND=\{\textbf{o}^{(k)}, \textbf{s}^{(k)}\}_{k=1}^{N} という形で書けるような, ラベルを含む教師付きデータである場合は, 直接最尤推定法を使うことができる.

学習データのある1つの入力列とラベル列の組に対して, その生成確率の対数は

logπs1t=1Tast,st+1bst,ot=logπs1+t=1Tlogast,st+1+t=1Tlogbst,ot\log \pi_{s_1} \prod_{t=1}^{T} a_{s_t, s_{t+1}} b_{s_t, o_t} = \log \pi_{s_1} + \sum_{t=1}^{T} \log a_{s_t, s_{t+1}} + \sum_{t=1}^{T} \log b_{s_t, o_t}

という形で書ける.
よって, 制約にも注意すると, ラグランジュ関数は

L=k=1N(logπs1+t=1Tlogast,st+1+t=1Tlogbst,ot)+λπ(1iSπi)+iSλai(1jSai,j)+oSλbi(1oΣbi,o)L = \sum_{k=1}^{N} \left(\log \pi_{s_1} + \sum_{t=1}^{T} \log a_{s_t, s_{t+1}} + \sum_{t=1}^{T} \log b_{s_t, o_t}\right) \\ + \lambda_{\pi} (1 - \sum_{i \in S} \pi_i) + \sum_{i \in S} \lambda_{a_i} (1 - \sum_{j \in S} a_{i, j}) + \sum_{o \in S} \lambda_{b_i} (1 - \sum_{o \in \Sigma} b_{i, o})

というように書ける(実際には sis_iTT は各データのインデックス kk に依存しているので, この式は不正確).
パラメータについて偏微分を取ると

Lπi=C(s1=i)πiλπLai,j=C(i,j)ai,jλaiLbi,o=C(i,o)bi,oλbi\dfrac{\partial L}{\partial \pi_{i}} = \dfrac{C(s_1 = i)}{\pi_{i}} - \lambda_{\pi} \\ \dfrac{\partial L}{\partial a_{i, j}} = \dfrac{C(i, j)}{a_{i, j}} - \lambda_{a_i} \\ \dfrac{\partial L}{\partial b_{i, o}} = \dfrac{C(i, o)}{b_{i, o}} - \lambda_{b_i}

ただし, C(i,j)C(i, j)DD 中の iji \to j の出現回数.

これらについて =0=0 を取ったもの, 及び制約を合わせて考えると, パラメータを求めることができる. 数式は省くが, 具体的には,

πi\pi_i:(状態 ii から始まるデータの個数)/(全データ個数)
ai,ja_{i, j}:(状態 iji \to j の遷移の総数)/(状態 ii から始まる遷移の総数)
bi,ob_{i, o}:(状態 ii が記号 oo を出力する総数)/(状態 ii の総数)

となる.

Baum-Welch アルゴリズム

学習データが D={o(k)}k=1ND=\{\textbf{o}^{(k)}\}_{k=1}^{N} という形で書けるような, ラベルを含まない教師無しデータである場合を考える. ここでは, EM アルゴリズムの一種である Baum-Welch アルゴリズムについて述べる.
EM アルゴリズムは, 一般的には

Eステップ: 前のMステップで求めたパラメータを用いて隠れ変数(期待値)を更新する
Mステップ: 前のEステップで求めた隠れ変数(期待値)を使ってパラメータを更新する

という操作を繰り返す.
Baum-Welch アルゴリズムにおいては, 隠れ変数として

「時刻 tt において状態が ii になる期待値」: γt(i)=p(st=iθold)\gamma_t(i) = p(s_t = i | \theta^{old})
「時刻 tt において, 次の遷移が iji \to j になる期待値」: ξt(i,j)=p(st=i,st+1=jθold)\xi_t(i, j) = p(s_t = i, s_{t+1} = j | \theta^{old})

を用いる.

まずMステップに関しては, 先ほどの最尤推定の結果を, 隠れ変数を使って代用することを考えて,

πi=γ1(i)ai,j=tξt(i,j)jStξt(i,j)bi,o=t  s.t.ot=oγt(i)tγt(i)\begin{aligned} \pi_{i}^{*} =& \gamma_1(i) \\ a_{i, j}^{*} =& \dfrac{\sum_{t} \xi_t(i, j)}{\sum_{j \in S} \sum_{t} \xi_t(i, j)} \\ b_{i, o}^{*} =& \dfrac{\sum_{t \ \ s.t. o_t = o} \gamma_t(i)}{\sum_t \gamma_t(i)} \end{aligned}

と計算できる.

次にEステップについて考えよう. 全ての状態遷移から st=i,st+1=js_t = i, s_{t+1} = j となる系列について考えると 計算量が爆発してしまうので, ここでも動的計画法を活用する.
具体的には, 前のMステップで求めたパラメータから前向き確率, 後ろ向き確率を計算する. 前向き確率 αt(i)\alpha_t(i) は「時刻 tt に状態 ii に至る全ての系列の確率の和」, 後ろ向き確率 βt(i)\beta_t(i) は「時刻 tt の状態 ii から最後に至る全ての系列の確率の和」のことであり, いずれも Viterbi アルゴリズムと同程度の計算量で求めることができる.

前向き確率 αt(i)\alpha_t(i), 後ろ向き確率 βt(i)\beta_t(i) が求まれば,

γt(i)=αt(i)βt(i)kSαT(k)\gamma_t^{*}(i) = \dfrac{\alpha_t(i) \beta_t(i)}{\sum_{k \in S} \alpha_T(k)} \\
ξt(i,j)=αt(i)ai,jbj,ot+1βt+1(j)kSαT(k)\xi_t^{*}(i, j) = \dfrac{\alpha_t(i) a_{i, j} b_{j, o_{t+1}} \beta_{t+1}(j)}{\sum_{k \in S} \alpha_T(k)}

より γt(i),ξt(i,j)\gamma_t(i), \xi_t(i, j) も新しく求まり, これがEステップとなる.