HMM

概要

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

ラベル付きコーパスからの訓練

  • 定義
    • 同時確率: P(x,y)=P(xiyi)P(yiyi1)P ({\bold x}, {\bold y}) = \prod P(x_i | y_i) P(y_i | y_{i-1})
      • 右辺の第1項が「ある観測値はその隠れ状態のみに依存している」という仮定,第2項がマルコフ性の仮定を表している
    • 訓練データD=(x(1),y(1)),,(x(N),y(N))D = {(x^{(1)}, y^{(1)}), \ldots ,(x^{(N)}, y^{(N)}) }
  • 対数尤度
    • logP(D)=x,yn((x,y),D)logP(xy)+y,yn((y,y),D)logP(yy)\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(xy)=n((x,y),D)xn((x,y),D),P(yy)=n((y,y),D)yn((y,y),D)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) }

分類

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

問題点

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

参考文献