😸

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

3 min read

この記事は2020年2月29日に書かれた別ブログの記事をZennに移行したものです。

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

問題設定

S: 状態の集合
\Sigma: 出力記号の集合
\pi_i: 文頭が状態 i になる確率
a_{i, j}: 状態 i から j への遷移確率
b_{i, o}: 状態 i における記号 o の出力確率

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


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

q_{t+1}(k) = \max_{i} [q_{t}(i)a_{i, k}] b_{k, o_{t+1}}

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


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

最尤推定

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

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

\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 = \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})

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

\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)D 中の i \to j の出現回数.

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

\pi_i:(状態 i から始まるデータの個数)/(全データ個数)
a_{i, j}:(状態 i \to j の遷移の総数)/(状態 i から始まる遷移の総数)
b_{i, o}:(状態 i が記号 o を出力する総数)/(状態 i の総数)

となる.

Baum-Welch アルゴリズム

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

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

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

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

を用いる.

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

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

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

\gamma_t^{*}(i) = \dfrac{\alpha_t(i) \beta_t(i)}{\sum_{k \in S} \alpha_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)}

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

Discussion

ログインするとコメントできます