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

問題点

  • 「ある観測値はその隠れ状態のみに依存している」という仮定が厳しすぎる
    • 前後の品詞を用いた素性などは使えない
  • 分類タスクで必要なのは$P(y|x)$なので,$P(x,y)$ではなく,直接的に$P(y|x)$をモデル化すべき

参考文献