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. 後ろ向きステップ
  - 保存しておいた直前候補を，後ろからたどっていき，最大対数確率値をもつ候補の系列を求める