条件付き確率場のソースを表示

{{Machine learning bar}}
'''条件付き確率場'''（じょうけんつきかくりつば、{{lang-en-short|conditional random field}}、略称: CRF）は[[マルコフ確率場|無向グラフ]]により表現される[[グラフィカルモデル|確率的グラフィカルモデル]]の一つであり、{{仮リンク|識別モデル|en|discriminative model}}である。これは[[自然言語処理]]、[[生体情報工学]]、[[コンピュータビジョン]]などの分野で連続データの解析などによく利用される。特にCRFは[[形態素解析]]、[[固有表現抽出]]、[[ゲノミクス]]に応用され、[[隠れマルコフモデル]]に関連するような問題において、代わりとしても用いることができる。コンピュータビジョンにおいては、[[物体認識]]、画像領域分割（セグメンテーション）などに使用される。

==概要==
CRFは無向性のグラフィカルモデルであり、それぞれの頂点は[[確率分布|分布]]が推論されるべき[[確率変数]]を表現する。辺は二確率変数間の依存性を表現する。詳細は[[グラフィカルモデル]]の項を参照のこと。モデルにおいては、確率変数間の対での依存性のみがモデル化される。一般的な場合は、[[#高次CRFsとセミマルコフCRFs|高次CRFs]]を参照のこと。各ノードやモデル全体は[[指数分布|指数分布族]]となることが多い。この分布は[[ボルツマン分布|ギブス分布]]にあるようにエネルギー項を記述する。おおよそ興味ある分布に相当するグラフ構造は既知であると仮定される。一方で分布のパラメータは学習される。CRFのパラメータの学習の基本的な前提は、変数<math>Y_i</math>が推論されるべきであるのに対し変数<math>X_i</math>は常に観測されるということである。このことは、同時確率<math>p(Y_i,X_i)</math>の最大化とは対照的に、条件付き確率<math>p(Y_i|X_i)</math>の最大化を可能にさせる。この計算はモデルの[[識別モデル|識別学習]]に相当する。

===マルコフ確率場との関連性===
CRFは特徴的に訓練された[[マルコフ確率場]]である。したがって、観測変数の分布をモデル化する必要はなく、モデル内の観測変数の複雑な特徴を任意に含められる。

===推論===
CRFにおける厳密な[[推計統計学|推論]]は、一般のグラフでは困難である。これは基本的にマルコフ確率場におけるものと同じである。ただし、連鎖や木構造グラフなどの特殊ケースでは、厳密推論が可能である。その場合に使用されるアルゴリズムは、[[隠れマルコフモデル|HMM]]で使用される[[フォワードバックワードアルゴリズム]]や[[ビタビアルゴリズム]]に類似していて、[[動的計画法]]などが用いられる。

===パラメータの学習===
パラメータ<math>\theta</math>の学習は通常<math>p(Y_i|X_i; \theta)</math>について最尤法を用いて行われる。もし全てのノードが[[指数分布|指数的な分布]]を持ち訓練において観測されるのなら、この最適化関数は凸型である。[[L-BFGS法]]アルゴリズムのような[[勾配法]]半ニュートン法を使用してサンプルに沿って解かれる。一方で、いくつかの変数が観測されないとき、推定問題は観測されない変数についても解かれる必要がある。これは一般的なグラフにおいて厳密に推定するため手に負えず、推測が使用される必要がある。

===例===
連続モデルにおいて、関心のあるグラフは連鎖グラフであることが多い。観測変数<math>X</math>の入力列は観測列を表現し、<math>Y</math>は観測によって推測されるべき必要な隠れた(若しくは未知の)状態変数を表現する。<math>Y_{i}</math>は連鎖形に構成され、各<math>Y_{i-1}</math>と<math>Y_{i}</math>間に辺を持つ。入力列のそれぞれの要素に対して”ラベル”として<math>Y_{i}</math>の簡単な説明を持つのと同様に、このレイアウトは次の事柄に対して効果的なアルゴリズムを導く。

*  モデルの訓練: 訓練データ中のあるコーパスから<math>Y_{i}</math>と特徴関数の間の条件付き分布を学習する
* 推定： 与えられた<math>X</math>に対して与えられたラベル列<math>Y</math>の確率を決定する
* 解読：与えられた<math>X</math>に対して尤もらしいラベル列<math>Y</math>を決定する

<math>X</math>における各<math>Y_{i}</math>の条件付き従属は<math>f(i, Y_{i-1}, Y_{i}, X)</math>形の”特徴関数”の不変集合を通して定義される。それは<math>Y_{i}</math>に対して各々の可能な値の[[尤度関数|尤度]]を部分的に決定する入力列の測りとして、くだけて考えられる。このモデルはそれぞれの特徴に数値的な重みを割り当て、<math>Y_{i}</math>に対して一定の値の確率を決定するためにそれらを統合する。

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

HMMに対しては特に対照的に、CRFsは特徴関数を幾つも含めることができ、また特徴関数は観測における様々な点で入力列<math>X</math>の全体を精査でき、その値域は確率的解釈を必要としない。

===高次CRFsとセミマルコフCRFs===

CRFsは整数<math>o</math>に指定された手前の変数<math>Y_{i-o}, ..., Y_{i-1}</math>に依存する<math>Y_{i}</math>を考えることでより高次のモデルに拡張される。訓練と推定は実際には<math>o</math>の小さい値に対してのみ行われる。これは計算コストが<math>o</math>に従って指数的に増加するためである。

別のCRFsの一般化として、'''セミマルコフ条件付き確率場''' (semi-CRF) があり、これはラベル列<math>Y</math>の可変長セグメンテーションをモデル化したものである。これは<math>Y_{i}</math>の計算コストの大きい長値域依存性をモデル化することで高次CRFsに相当する能力を提供する。

== ソフトウェア ==
以下はCRFを実行するためのソフトウェアの例である。
* [https://web.archive.org/web/20100112222803/http://www.broadinstitute.org/annotation/conrad/ Conrad] CRF based gene predictor ([[Java]])
* [http://mallet.cs.umass.edu/ MALLET] ([[Java]])
* [http://www.cs.ubc.ca/~murphyk/Software/CRFall.zip Kevin Murphy's MATLAB CRF code] ([[MATLAB|Matlab]])
* [https://crf.sourceforge.net/ Sunita Sarawagi's CRF package] ([[Java]])
* [http://sourceforge.net/projects/hcrf/ HCRF library (including CRF and LDCRF)] ([[C++]], [[MATLAB|Matlab]])
* [http://www.chokkan.org/software/crfsuite/ CRFSuite] Fast CRF implementation ([[C言語|C]])
* [http://taku910.github.io/crfpp/ CRF++] ([[C++]])：和製
* [http://www.dii.unisi.it/~freno/JProGraM.html JProGraM]{{リンク切れ|date=2019年3月}} ([[Java]])
* [http://nlp.stanford.edu/software/CRF-NER.shtml Stanford Named Entity Recognizer (NER)] ([[Java]])
* [https://web.archive.org/web/20100707042144/http://cbioc.eas.asu.edu/banner/ BANNER] ([[Java]])
* [https://montepython.sourceforge.net/ Monte Python]

==参考文献==
* McCallum, A.: Efficiently inducing features of conditional random fields. In: ''Proc. 19th Conference on Uncertainty in Artificial Intelligence''. (2003)
* Wallach, H.M.: [http://www.cs.umass.edu/~wallach/technical_reports/wallach04conditional.pdf 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) [http://www.cs.umass.edu/~mccallum/papers/crf-tutorial.pdf 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. [http://www.scai.fraunhofer.de/fileadmin/images/bio/data_mining/paper/crf_klinger_tomanek.pdf Online PDF]

== 関連項目 ==
* [[ベイジアンネットワーク]]
* [[マルコフ過程]]
* [[マルコフ確率場]]

{{DEFAULTSORT:しようけんつきかくりつは}}
[[Category:機械学習]]
[[Category:グラフ理論]]
[[Category:グラフィカルモデル]]
[[Category:数学に関する記事]]