条件じょうけん付つき確率かくりつ場じょう

条件じょうけん付つき確率かくりつ場じょう（じょうけんつきかくりつば、英語えいご: Conditional random field、略称りゃくしょう: CRF）は無む向むかいグラフにより表現ひょうげんされる確かく率りつ的てきグラフィカルモデルの一ひとつであり、識別しきべつモデルである。これは自然しぜん言語げんご処理しょり、生体せいたい情報じょうほう工学こうがく、コンピュータビジョンなどの分野ぶんやで連続れんぞくデータの解析かいせきなどによく利用りようされる。特とくにCRFは形態素けいたいそ解析かいせき、固有こゆう表現ひょうげん抽出ちゅうしゅつ、ゲノミクスに応用おうようされ、隠かくれマルコフモデルに関連かんれんするような問題もんだいにおいて、代かわりとしても用もちいることができる。コンピュータビジョンにおいては、物体ぶったい認識にんしき、画像がぞう領域りょういき分割ぶんかつ（セグメンテーション）などに使用しようされる。

概要がいよう

CRFは無む向性こうせいのグラフィカルモデルであり、それぞれの頂点ちょうてんは分布ぶんぷが推論すいろんされるべき確かく率りつ変数へんすうを表現ひょうげんする。辺あたりは二に確かく率りつ変数へんすう間あいだの依存いぞん性せいを表現ひょうげんする。詳細しょうさいはグラフィカルモデルの項こうを参照さんしょうのこと。モデルにおいては、確かく率りつ変数へんすう間あいだの対たいでの依存いぞん性せいのみがモデル化かされる。一般いっぱん的てきな場合ばあいは、高次こうじCRFsを参照さんしょうのこと。各かくノードやモデル全体ぜんたいは指数しすう分布ぶんぷ族ぞくとなることが多おおい。この分布ぶんぷはギブス分布ぶんぷにあるようにエネルギー項こうを記述きじゅつする。おおよそ興味きょうみある分布ぶんぷに相当そうとうするグラフ構造こうぞうは既知きちであると仮定かていされる。一方いっぽうで分布ぶんぷのパラメータは学習がくしゅうされる。CRFのパラメータの学習がくしゅうの基本きほん的てきな前提ぜんていは、変数へんすう$Y_{i}$が推論すいろんされるべきであるのに対たいし変数へんすう$X_{i}$は常つねに観測かんそくされるということである。このことは、同時どうじ確かく率りつ$p(Y_{i},X_{i})$の最大さいだい化かとは対照たいしょう的てきに、条件じょうけん付つき確かく率りつ$p(Y_{i}|X_{i})$の最大さいだい化かを可能かのうにさせる。この計算けいさんはモデルの識別しきべつ学習がくしゅうに相当そうとうする。

マルコフ確率かくりつ場じょうとの関連かんれん性せい

CRFは特徴とくちょう的てきに訓練くんれんされたマルコフ確率かくりつ場じょうである。したがって、観測かんそく変数へんすうの分布ぶんぷをモデル化かする必要ひつようはなく、モデル内ないの観測かんそく変数へんすうの複雑ふくざつな特徴とくちょうを任意にんいに含ふくめられる。

推論すいろん

CRFにおける厳密げんみつな推論すいろんは、一般いっぱんのグラフでは困難こんなんである。これは基本きほん的てきにマルコフ確率かくりつ場じょうにおけるものと同おなじである。ただし、連鎖れんさや木き構造こうぞうグラフなどの特殊とくしゅケースでは、厳密げんみつ推論すいろんが可能かのうである。その場合ばあいに使用しようされるアルゴリズムは、HMMで使用しようされるフォワードバックワードアルゴリズムやビタビアルゴリズムに類似るいじしていて、動的どうてき計画けいかく法ほうなどが用もちいられる。

パラメータの学習がくしゅう

パラメータ$\theta$の学習がくしゅうは通常つうじょう$p(Y_{i}|X_{i};\theta )$について最尤法さいゆうほうを用もちいて行おこなわれる。もし全すべてのノードが指数しすう的てきな分布ぶんぷを持もち訓練くんれんにおいて観測かんそくされるのなら、この最適さいてき化か関数かんすうは凸とつ型がたである。L-BFGS法ほうアルゴリズムのような勾配こうばい法ほう半はんニュートン法ほうを使用しようしてサンプルに沿そって解とかれる。一方いっぽうで、いくつかの変数へんすうが観測かんそくされないとき、推定すいてい問題もんだいは観測かんそくされない変数へんすうについても解とかれる必要ひつようがある。これは一般いっぱん的てきなグラフにおいて厳密げんみつに推定すいていするため手てに負おえず、推測すいそくが使用しようされる必要ひつようがある。

例れい

連続れんぞくモデルにおいて、関心かんしんのあるグラフは連鎖れんさグラフであることが多おおい。観測かんそく変数へんすう$X$の入力にゅうりょく列れつは観測かんそく列れつを表現ひょうげんし、$Y$は観測かんそくによって推測すいそくされるべき必要ひつような隠かくれた(若もしくは未知みちの)状態じょうたい変数へんすうを表現ひょうげんする。$Y_{i}$は連鎖れんさ形がたに構成こうせいされ、各かく$Y_{i-1}$と$Y_{i}$間あいだに辺あたりを持もつ。入力にゅうりょく列れつのそれぞれの要素ようそに対たいして”ラベル”として$Y_{i}$の簡単かんたんな説明せつめいを持もつのと同様どうように、このレイアウトは次つぎの事柄ことがらに対たいして効果こうか的てきなアルゴリズムを導みちびく。

• モデルの訓練くんれん: 訓練くんれんデータ中ちゅうのあるコーパスから$Y_{i}$と特徴とくちょう関数かんすうの間あいだの条件じょうけん付つき分布ぶんぷを学習がくしゅうする
• 推定すいてい： 与あたえられた$X$に対たいして与あたえられたラベル列れつ$Y$の確かく率りつを決定けっていする
• 解読かいどく：与あたえられた$X$に対たいして尤もっともらしいラベル列れつ$Y$を決定けっていする

$X$における各かく$Y_{i}$の条件じょうけん付つき従属じゅうぞくは$f(i,Y_{i-1},Y_{i},X)$形かたちの”特徴とくちょう関数かんすう”の不変ふへん集合しゅうごうを通とおして定義ていぎされる。それは$Y_{i}$に対たいして各々おのおのの可能かのうな値ねの尤ゆう度どを部分ぶぶん的てきに決定けっていする入力にゅうりょく列れつの測はかりとして、くだけて考かんがえられる。このモデルはそれぞれの特徴とくちょうに数値すうち的てきな重おもみを割わり当あてて、$Y_{i}$に対たいして一定いっていの値ねの確かく率りつを決定けっていするためにそれらを統合とうごうする。

線形せんけい連鎖れんさCRFは、概念がいねん上じょうの簡単かんたんな隠かくれマルコフモデル（HMM）として同様どうようの応用おうようを多おおく持もつが、HMMに対たいして入力にゅうりょくおよび出力しゅつりょく列れつの分布ぶんぷについての制約せいやくを緩ゆるめたものである。HMMは、状態じょうたい遷移せんいと出力しゅつりょくをモデル化かするために決けつ まった分布ぶんぷを使用しようするような特殊とくしゅな特徴とくちょう関数かんすうを持もつCRFとして大雑把おおざっぱに理解りかいされる。逆ぎゃくにCRFは、隠かくれた状態じょうたい列れつの中なかで自由じゆうに変化へんかする任意にんいの関数かんすうの中なかに一定いってい の遷移せんい分布ぶんぷを入力にゅうりょく列れつに依存いぞんして生成せいせいするようなHMMの一般いっぱん化かとして大雑把おおざっぱに理解りかいされる。

HMMに対たいしては特とくに対照たいしょう的てきに、CRFsは特徴とくちょう関数かんすうを幾いくつも含ふくめることができ、また特徴とくちょう関数かんすうは観測かんそくにおける様々さまざまな点てんで入力にゅうりょく列れつ$X$の全体ぜんたいを精査せいさでき、その値域ちいきは確かく率りつ的てき解釈かいしゃくを必要ひつようとしない。

高次こうじCRFsとセミマルコフCRFs

CRFsは整数せいすう$o$に指定していされた手前てまえの変数へんすう$Y_{i-o},...,Y_{i-1}$に依存いぞんする$Y_{i}$を考かんがえることでより高次こうじのモデルに拡張かくちょうされる。訓練くんれんと推定すいていは実際じっさいには$o$の小ちいさい値ねに対たいしてのみ行おこなわれる。これは計算けいさんコストが$o$に従したがって指数しすう的てきに増加ぞうかするためである。

別べつのCRFsの一般いっぱん化かとして、セミマルコフ条件じょうけん付つき確率かくりつ場じょう (semi-CRF) があり、これはラベル列れつ$Y$の可変長かへんちょうセグメンテーションをモデル化かしたものである。これは$Y_{i}$の計算けいさんコストの大おおきい長ちょう値域ちいき依存いぞん性せいをモデル化かすることで高次こうじCRFsに相当そうとうする能力のうりょくを提供ていきょうする。

ソフトウェア

以下いかはCRFを実行じっこうするためのソフトウェアの例れいである。

• Conrad CRF based gene predictor (Java)
• MALLET (Java)
• Kevin Murphy's MATLAB CRF code (Matlab)
• Sunita Sarawagi's CRF package (Java)
• HCRF library (including CRF and LDCRF) (C++, Matlab)
• CRFSuite Fast CRF implementation (C)
• CRF++ (C++)：和製わせい
• JProGraM (Java)
• Stanford Named Entity Recognizer (NER) (Java)
• BANNER (Java)
• Monte Python

参考さんこう文献ぶんけん

• McCallum, A.: Efficiently inducing features of conditional random fields. In: Proc. 19th Conference on Uncertainty in Artificial Intelligence. (2003)
• Wallach, H.M.: Conditional random fields: An introduction. Technical report MS-CIS-04-21, University of Pennsylvania (2004)
• Sutton, C., McCallum, A.: An Introduction to Conditional Random Fields for Relational Learning. In "Introduction to Statistical Relational Learning". Edited by Lise Getoor and Ben Taskar. MIT Press. (2006) Online PDF
• Klinger, R., Tomanek, K.: Classical Probabilistic Models and Conditional Random Fields. Algorithm Engineering Report TR07-2-013, Department of Computer Science, Dortmund University of Technology, December 2007. ISSN 1864-4503. Online PDF

関連かんれん項目こうもく

• ベイジアンネットワーク
• マルコフ過程かてい
• マルコフ確率かくりつ場じょう