Negative/Positive Thinking

2011-09-29

条件付き確率場(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)が適用できる
      • 一般化した手法に「確率伝播法」がある

参考文献

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/jetbead/20110929/1317253922