系列ラベリング問題メモ

機械学習

はじめに

系列ラベリング問題についてちょっと調べてみたのでメモ。

系列ラベリング(系列分類)問題とは

  • ある系列xの各要素に適切なラベル列yを付与する問題
    • 例えば「This is a pen」という文書の各単語に「This(代名詞) is(動詞) a(冠詞) pen(名詞)」のように品詞ラベルをつける問題(品詞タグ付け)
  • 系列だけでなく木構造などへの適用もされている
    • 構造学習
      • ラベル、木、グラフ、順序集合など
  • 応用
    • 品詞分類
    • 形態素解析(ラティスのコスト計算なども)
    • チャンキング(基本名詞句(Base NP)同定、固有表現抽出、文節まとめあげなど)
      • 系列セグメンテーション問題
    • 時系列解析や画像認識
    • など

系列ラベリング問題の特徴

普通の多値分類との違いは、「注目している要素xi以外の情報も使えること」と「クラスの数が膨大になりやすいこと」がある。

注目している要素以外の情報も使える
  • 多値分類では、その要素xiがどのクラスyjに属するかを判定する
    • 与えられる情報は、その要素xiだけ
  • 系列ラベリングでは、その要素意外の他の要素の情報も使える
    • 与えられる情報は、要素の系列x(=x1,x2,x3,...)
    • 例えば、「形容詞の後には名詞が来やすい」などの情報を考慮できる
クラスの数が膨大になりやすいこと
  • 上記の例では、品詞の数がn個ならば、その組み合わせはn^4通りになる
  • クラス：「代名詞 代名詞 代名詞 代名詞」「代名詞 代名詞 代名詞 名詞」...
  • うまく計算してあげないと大変なことになる

問題解決のためのモデル

とりあえず、具体的な学習法や推定法についてはのちのち勉強していきたいとしてとりあえずメモ。

■隠れマルコフモデル(Hidden Markov Model)
  • 生成モデル
    • 1990年の主流らしい
  • パラメータ推定(学習)時には、ラベル付き訓練データを与えて学習する(教師あり)
    • 学習時には隠れてない→ちょっと違和感？
    • 教師なしならば前向き後ろ向きアルゴリズムを使う
  • 問題点
    • P(y|x)を計算するのにP(y,x)を使っている(P(x)まで余分に推定)
    • 観測変数の独立性を仮定してたりして、相互作用のある素性などを考慮できない
■多値分類器の逐次適用
  • 多値分類器を順番に適用して、ひとつひとつラベルを決めていく方法
  • すべてのxとそれまで決めたラベルyを素性として使える
    • 「それまで決めたラベル」の確信度などは考慮しない
    • しかし自由に使う素性(xやyの要素)を選べる(相互作用のある素性をいれたりなど)
  • 案外うまくいくっぽい
  • 問題点
    • 系列全体としてそのラベルが正しいかが考慮されていない
      • label biasやlength biasに弱い
■条件付き確率場(Conditional Random Fields,CRF)
  • 逐次適用の自由に使う素性を選べる利点を残しつつ、系列全体でのラベルの確からしさも考慮
    • P(y|x)を直接求める識別モデル
■Conditional Neural Fields(CNF)
  • CRFに隠れ層を追加して非線形にしたもの
■隠れマルコフパーセプトロン(Structured Perceptron)
  • パーセプトロンが構造学習に適用できる！(Collins, 2002)
    • しかも非常にいい感じ
  • CRFでは「訓練データのyが出力される確率を最大にするように学習」していた
    • 別に最大にするんじゃなくて、「目的のyが他のy'より確率が高ければいい」という考え
    • このため、学習も予測もどちらもargmax操作でできる
■Max-Margin Markov Networks(MMMN)
■Passive-Aggressive(PA)アルゴリズム
■双対分解による構造学習
■Confidence Weighted Learning(CW)

参考文献