HMM

概要

隠れマルコフモデル (Hidden Markov Mode; HMM)
- 隠れ
  - 状態は直接観測できない
  - ただし，言語処理においてはラベル付き訓練データのラベルが与えられる，「隠れ」ではないことが多い
- 単純マルコフ過程
  - ある観測要素$x_i$は，それの直前の観測要素$x_{i-1}$のみに依存
  - ある隠れ状態$y_i$は，それの直前の隠れ状態$y_{i-1}$のみに依存
- パラメータは，遷移確率 $P(y | y_{i-1}) $と出力確率 $P(x|y)$の2つ
生成モデル
- 観測変数と目的変数の同時確率$P ({\bold x}, {\bold y})$を考える
- 観測列${\bold x}$とラベル${\bold y}$を生成するような確率分布の存在を仮定するため生成モデル

定義
- 同時確率: $P ({\bold x}, {\bold y}) = \prod P(x_i | y_i) P(y_i | y_{i-1}) $
  - 右辺の第1項が「ある観測値はその隠れ状態のみに依存している」という仮定，第2項がマルコフ性の仮定を表している
- 訓練データ$D = {(x^{(1)}, y^{(1)}), \ldots ,(x^{(N)}, y^{(N)}) }$
対数尤度
- $\log P(D) = \sum_{x,y} n \left( (x,y), D \right) \log P(x|y) + \sum_{y',y} n \left((y',y), D\right) \log P(y|y') $
- ラグランジュ法でこれを最大化するパラメータを求めると
  - $P(x|y) = \frac{ n((x,y),D) }{ \sum_x n((x,y), D) } , P(y|y') = \frac{ n((y',y),D) }{ \sum_y n((y',y), D) } $

やりたいことは，最大確率値をもつ隠れ状態列を求めること
隠れ状態列の候補は指数関数的に増えるため，全列挙は非現実的
- アンダーフローを避けるため確率を直接考えるのではなく，対数確率を考える
- 対数確率は$\log P(x, y) = \sum_j \log P(x_j, y_j | x_{j-1}, y_{j-1})$である（「直前要素のみ依存した値」の和）
ビタビアルゴリズム
1. 前向きステップ: 最短経路を動的計画法で求める
  - $y_j$の各候補について，「どの直前候補に接続すると$y_1$から$y_j$までの系列として対数確率が最大になるか」と「その最大値」，を保存しておく
  - $y_{j+1}$を考えるときは，保存しておいた$y_j$の各候補の最大値を使って，同様に「どの直前候補に接続すると$y_1$から$y_{j+1}$までの系列として対数確率が最大になるか」と「その最大値」を保存する
  - これを最後まで繰り返すと，（$y_1$から$y_N$までの）全体の系列としての対数確率の最大値が求まる
2. 後ろ向きステップ
  - 保存しておいた直前候補を，後ろからたどっていき，最大対数確率値をもつ候補の系列を求める