条件随机场 - Ciallo Wiki

1 基本概念と定義

1.1 確率的グラフィカルモデル

1.1.1 無向グラフとマルコフ確率場

確率的グラフィカルモデルの一種である無向グラフモデルでは、各頂点が確率変数を表し、辺が変数間の依存関係を表す。マルコフ確率場（Markov Random Field, MRF）は、この無向グラフ上で定義され、結合確率分布がクリーク上のポテンシャル関数の積で表現される。マルコフ性として、ある頂点の値はその近傍にのみ依存する（局所マルコフ性）という性質を持つ。

1.1.2 条件付き分布の定式化

条件付き確率場（CRF）は、観測変数が常に与えられたもとで、ラベル変数の条件付き分布を直接モデル化する。すなわち、観測系列$\mathbf{x}$が与えられたとき、ラベル系列$\mathbf{y}$の条件付き確率$p(\mathbf{y}	\mathbf{x})$を、無向グラフ上のポテンシャル関数を用いて定式化する。これにより、観測データの生成過程を仮定せずに、ラベリングに特化した学習が可能となる。

1.2 CRFの数学的定式化

1.2.1 ポテンシャル関数と特徴関数

CRFでは、各クリークに対してポテンシャル関数$\Psi_c(\mathbf{y}_c, \mathbf{x})$を定義する。通常、このポテンシャルは指数族の形をとり、特徴関数$f_k(\mathbf{y}_c, \mathbf{x})$とその重みパラメータ$\lambda_k$を用いて、$\Psi_c(\mathbf{y}_c, \mathbf{x}) = \exp\left(\sum_k \lambda_k f_k(\mathbf{y}_c, \mathbf{x})\right)$と表される。特徴関数は、観測とラベルの局所的な関係を捉える役割を果たす。

1.2.2 分配関数とパラメータベクトル

条件付き確率$p(\mathbf{y}	\mathbf{x})$は、全クリークのポテンシャル関数の積を、すべての可能なラベル系列にわたる和（分配関数$Z(\mathbf{x})$）で正規化して得られる。すなわち、$p(\mathbf{y}	\mathbf{x}) = \frac{1}{Z(\mathbf{x})} \prod_c \Psi_c(\mathbf{y}_c, \mathbf{x})$。パラメータベクトル$\mathbf{\lambda} = \{\lambda_k\}$は、特徴関数の重みをまとめたものであり、学習により推定される。

2 モデルの種類と構造

2.1 線形鎖CRF

2.1.1 系列ラベリングへの適用

線形鎖CRFは、最も基本的なCRFの形態であり、ラベル変数が1次元の鎖状に並んだグラフ構造を持つ。観測系列$\mathbf{x} = (x_1, x_2, \dots, x_T)$が与えられたとき、ラベル系列$\mathbf{y} = (y_1, y_2, \dots, y_T)$の条件付き確率をモデル化する。系列ラベリングタスク（品詞タグ付け、固有表現抽出など）で広く用いられる。

2.1.2 クリークと局所特徴

線形鎖CRFでは、クリークは連続する2つのラベル変数$(y_t, y_{t+1})$（辺クリーク）および各時刻のラベルと観測のペア$(y_t, \mathbf{x})$（頂点クリーク）からなる。特徴関数は、隣接ラベルの遷移パターンや、観測とラベルの対応関係を捉える局所特徴として設計され、モデルの表現力を支える。

2.2 一般グラフCRF

2.2.1 木構造CRF

木構造CRFは、ラベル変数がツリー状の無向グラフを構成するモデルである。木構造は閉路を持たないため、信念伝播法などの効率的な推論アルゴリズムが適用可能であり、構文解析や意味解析などの階層的なラベリング問題に利用される。

2.2.2 格子CRFと画像解析

格子CRFは、ラベル変数が2次元格子状に配置されたモデルであり、画像解析で頻繁に用いられる。各画素や領域に対応するラベル間の近傍関係（4近傍や8近傍）を辺で表現し、画像セグメンテーションやノイズ除去などのタスクにおいて、空間的な平滑性を考慮したラベル割り当てを実現する。

3 学習アルゴリズム

3.1 最尤推定と対数尤度

3.1.1 勾配法と確率的勾配降下法

CRFのパラメータ学習は、訓練データに対する条件付き対数尤度$L(\mathbf{\lambda}) = \sum_i \log p(\mathbf{y}^{(i)}	\mathbf{x}^{(i)})$の最大化により行われる。対数尤度の勾配は、特徴関数の経験期待値とモデル期待値の差として計算され、勾配法や確率的勾配降下法（SGD）を用いてパラメータを逐次更新する。

3.1.2 正則化（L1, L2正則化）

過学習を防ぐため、対数尤度に正則化項を追加する。L2正則化は$\frac{1}{2\sigma^2}\sum_k \lambda_k^2$を加えてパラメータのノルムを抑制し、L1正則化は$\alpha\sum_k	\lambda_k	$を加えてスパースな解を促す。L1正則化は特徴選択の効果も持つ。

3.2 パラメータ推定の高速化

3.2.1 L-BFGS法

L-BFGS法は、準ニュートン法の一種で、勾配情報を用いてヘッセ行列を近似しながらパラメータを更新する。CRFの学習では、対数尤度関数が凸であるため、L-BFGS法は高速で安定した収束を実現し、大規模な特徴量を扱う場合に有効である。

3.2.2 サンプリング手法の導入

モデル期待値の計算には分配関数が必要であり、特に一般グラフCRFではその計算が高コストとなる。そこで、MCMCサンプリング（例：ギブスサンプリング）を用いて期待値を近似する手法が導入される。これにより、大規模なグラフや複雑なクリーク構造を持つモデルでも学習が可能となる。

4 推論アルゴリズム

4.1 ビタビアルゴリズム

4.1.1 最適パスの探索

推論タスクの一つは、与えられた観測系列に対して、最も確率の高いラベル系列（最適パス）を見つけることである。ビタビアルゴリズムは、この最適パスを効率的に探索する動的計画法であり、線形鎖CRFにおいて広く用いられる。

4.1.2 動的計画法の仕組み

ビタビアルゴリズムは、各時刻$t$でラベル$y_t$を取る場合の最大対数確率を漸化的に計算する。時刻$t$での値を$\delta_t(y_t)$とし、$\delta_{t+1}(y_{t+1}) = \max_{y_t}[\delta_t(y_t) + \psi(y_t, y_{t+1}, \mathbf{x})]$のように更新する（$\psi$はポテンシャルの対数）。最終時刻で最大値を与えるラベルを選び、バックトラックにより最適パスを得る。

4.2 周辺確率の計算

4.2.1 Forward-Backwardアルゴリズム

各時刻におけるラベルの周辺確率$p(y_t	\mathbf{x})$や、隣接ラベル対の周辺確率$p(y_t, y_{t+1}	\mathbf{x})$の計算には、Forward-Backwardアルゴリズムが用いられる。前向きに伝播するforward変数$\alpha_t(y_t)$と後ろ向きに伝播するbackward変数$\beta_t(y_t)$を計算し、それらの積から周辺確率を効率的に求める。

4.2.2 信念伝播法

一般グラフCRFでは、周辺確率の計算に信念伝播法（Belief Propagation, BP）が使われる。木構造グラフでは正確な周辺確率が得られるが、閉路を含むグラフでは近似解となる（ループ信念伝播法）。各ノードが隣接ノードとメッセージを交換し合い、収束するまで繰り返すことで、周辺確率を近似的に計算する。

5 関連モデルとの比較

5.1 隠れマルコフモデルとの差異

5.1.1 生成モデルと識別モデル

隠れマルコフモデル（HMM）は生成モデルであり、観測系列とラベル系列の結合確率$p(\mathbf{x}, \mathbf{y})$をモデル化する。一方、CRFは識別モデルであり、観測が与えられたもとでのラベルの条件付き確率$p(\mathbf{y}	\mathbf{x})$を直接モデル化する。このため、CRFは観測データの分布を仮定する必要がなく、より柔軟な特徴設計が可能である。

5.1.2 観測独立性の仮定

HMMでは、各時刻の観測はその時刻のラベルにのみ依存する（観測独立性の仮定）という強い制約がある。CRFはこの仮定を課さず、任意の観測特徴とラベルとの依存関係を特徴関数として自由に記述できる。その結果、CRFは長距離の文脈依存関係や複雑な観測パターンを扱える。

5.2 最大エントロピーマルコフモデルとの関係

5.2.1 ラベリングバイアス問題

最大エントロピーマルコフモデル（MEMM）は、CRFと同様に識別モデルであるが、ラベルの系列確率を各時刻の条件付き確率の積として分解する（局所的正規化）。このため、遷移確率が観測に依存する際に、訓練データで頻出するラベルへのバイアスが生じる（ラベリングバイアス問題）。この問題により、全体として確率が低いラベル系列が過小評価されやすい。

5.2.2 対策としてのCRF

CRFは、系列全体の条件付き確率を一つの分配関数で正規化する（大域的正規化）ことで、ラベリングバイアス問題を解決する。これにより、観測に依存した遷移を適切に扱いながら、系列全体として整合性のあるラベリングを実現する。ただし、大域的正規化は計算コストが高くなる。

6 応用事例

6.1 自然言語処理

6.1.1 固有表現抽出

固有表現抽出（Named Entity Recognition, NER）は、テキスト中の人名、地名、組織名などの固有表現を識別するタスクである。線形鎖CRFは、単語の表層形、品詞、周辺単語などの特徴を組み合わせて、各トークンに固有表現ラベル（B-PER, I-PER, Oなど）を割り当てるモデルとして標準的に用いられる。

6.1.2 品詞タグ付けとチャンキング

品詞タグ付けでは、各単語に品詞ラベル（名詞、動詞など）を付与し、チャンキングでは、句の境界を特定する。CRFは、隣接ラベル間の遷移制約を自然にモデル化できるため、これらの系列ラベリングタスクで高い性能を示す。特に、文脈情報を特徴として取り込みやすい利点がある。

6.2 バイオインフォマティクス

6.2.1 遺伝子予測

ゲノム配列から遺伝子領域を予測するタスクでは、DNA塩基配列を観測として、各塩基がエクソン、イントロンなどの機能的領域に属するかをラベリングする。CRFは、配列上の長距離相互作用やスプライス部位のパターンを特徴として組み込むことで、高精度な遺伝子予測を実現する。

6.2.2 タンパク質構造解析

タンパク質のアミノ酸配列から、二次構造（αヘリックス、βシートなど）や膜貫通領域を予測する問題にCRFが応用される。アミノ酸の物理化学的性質や進化的情報を特徴とし、配列上の局所的な相互作用をモデル化することで、構造予測の精度を向上させる。

6.3 画像解析とコンピュータビジョン

6.3.1 画像セグメンテーション

画像セグメンテーションでは、各画素に物体カテゴリラベル（空、道路、建物など）を割り当てる。格子CRFは、画素間の空間的な近接性をポテンシャル関数で表現し、色やテクスチャの類似性を考慮しながら、滑らかで意味的に一貫した領域分割を実現する。

6.3.2 物体認識

物体認識タスクでは、画像中の部分領域に対して物体の有無や位置を推定する。CRFは、複数の物体候補間の空間的関係（例：隣接関係や重なり）をモデル化することで、個別の検出結果を統合し、全体として矛盾のない認識結果を得るために利用される。