条件付き確率場(CRF)メモ

機械学習

条件付き確率場とは？

  • 対数線形モデルを系列ラベリング問題へ適用したもの
  • 一般には、系列だけでなくグラフの頂点のラベルにも適用できる
    • 系列の場合は、「linear-chain CRF」と呼ばれる
  • 条件付き確率P(y|x)がMarkov確率場の構造を持つモデル
    • これを仮定するので、一つ前のもののみを考えてもよいことになるっぽい
系列ラベリング
  • 系列
    • 要素が連なったもの(単語が並んでいる「文章」など)
  • 系列ラベリング
    • 系列の各要素にラベルを付けること
  • 分類モデルでは、多クラス分類でも高々数十個に分類するだけ
  • 系列ラベリングでは、分類の可能性はラベルの付け方だけあり得る
    • 例えば、ラベルが10種類で要素が20個ならばラベル列は10^20通り(のクラス分類)になってしまう
  • データの形式
    • D={(x_1, y_1),(x_2, y_2),...,(x_n, y_n)}
    • x_i : 素性ベクトル
    • y_i : ラベルベクトル
条件付き確率場(CRF)
  • 条件付き確率
    • 対数線形モデルと一緒(dはxで表されるので、最初からxを使う)
    • P(y|x)=\frac{1}{Z_{x,w}}{exp(w \cdot \phi(x,y) )}
    • Z_{x,w}=\sum_y{exp(w \cdot \phi(x,y) )} : 正規化のための係数
  • 分類
    • 対数線形モデル : y^* = argmax_y \frac{1}{Z_{x,w}} exp( w\cdot \phi(x,y) )
    • このままだと、w \cdot \phi(x,y)で最大になるyを求めるのに全部のラベル列の組み合わせを考えないといけない
      • (ラベルの種類)^(ラベル列の長さ)通りできて多すぎぱない
    • なので、以下の仮定をする
    • \phi_k(x,y)=\sum_t \phi_k(x,y_t,y_{t-1})
      • ラベルyの全部を考えるのではなく、一個前のラベルとの組み合わせのみ(tとt-1のみ)を考慮
    • すなわち、y^* = argmax_y \sum_t w \cdot \phi(x,y_t,y_{t-1})を解く
    • ビタビアルゴリズムで高速に解ける
    • 拡張として、t,t-1だけでなくt-2も考慮することができる
  • 学習
    • (実際には準ニュートン法、確率的勾配法(SGD)が用いられたりする)
    • 最急勾配法で更新するとき周辺確率P(y|x)を計算する必要があるが、上記の仮定を用いると、前向き・後ろ向きアルゴリズム(Baum-Welch algorithm)が適用できる
      • 一般化した手法に「確率伝播法」がある

参考文献