A Hybrid Markov/Semi-Markov Conditional Random Field for Sequence Segmentation (Galen Andrew, 2006)
William Cohenの情報抽出の授業のサイトで知った論文。
http://acl.ldc.upenn.edu/W/W06/W06-1655.pdf (EMNLP 2006)
内容
普通のCRFでは表現されているがSemi-Markov CRFでは表現しづらい素性があることを指摘し、その素性の表現方法を示している。
- 情報抽出や単語区切りのようなセグメンテーション問題に適していると思われるSemi-Markov CRFだが、CRFに負けたという報告も少なくない。
- Semi-Markov CRFではsegment単位の素性（segmentの文字列が辞書にあるか、など）は表しやすいが、segment内のtoken単位の素性は表現しにくい。
- 特に、あるtokensの前後ではセグメントが切れにくいことを表す素性がSemi-Markov CRFでは表しにくい。これまでのSemi-Markov CRFを応用した実験では上記の素性が使われていない。
- 上記の素性は、中国語単語分割では未知語の解析に重要。
- 本質的にはSemi-Markov CRFはCRFを含んでいるので、token単位の素性も表現できることを示す。
- ナイーブに実装すると文長T に対してT３乗の計算時間になるところを、Dynamic Programming でT2乗に落とすアルゴリズムを提案。
- おまけで、generative modelの情報をlog oddsで素性としてCRFに取り入れる手法と合わせて評価。
- Semi-Markov CRFにtoken単位の素性を追加することで中国語単語分割のF値が 95.28から96.46に向上。
- CRF(95.69)にも勝利。
私見
- セグメンテーション問題のデファクトっぽく扱われているSemi-Markov CRFの弱点を指摘しており良い論文。
- ただ、改良方法の解析時間O(T^2)は厳しい。
- Semi-Markov CRFでしか使えないというsegment単位の情報は不完全ながらもCRFの素性に反映出来ないこともないのでCRFでいいような気もする。
