はじめに

本記事は、Sansan Advent Calendar 2023の6日目の記事です。

こんにちは、研究開発部の齋藤です。

固有表現認識にCRFを試す場面が最近あり、CRFのパラメータ学習を少し勉強しました。折角なのでまとめておこうかと思います。

CRF とは？

CRFはConditional Random Fieldsの略語であり、日本語では条件付き確率場と呼ばれます。系列ラベリングに対数線形モデルを適用したものであり、品詞のタグ付けや、固有表現認識においてよく用いられます。

CRFは入力 $\mathbf{x}$ に対し、解析結果 $\mathbf{y}$ が出力される条件付き確率 $P(\mathbf{y}|\mathbf{x})$ を以下のような式で計算します。

$\displaystyle P(\mathbf{y}|\mathbf{x}) = \frac{\exp(\mathbf{w} \cdot \phi(\mathbf{x}, \mathbf{y}))}{Z}$

ここで、 $\mathbf{x}$ は入力を、 $\mathbf{y}$ は全ての解候補を表します。また、 $\phi(\mathbf{x}, \mathbf{y})$ は素性（そせい）ベクトルであり、 $\mathbf{w}$ は重みベクトルを意味します。素性ベクトルとは、分類や予測をするための手がかりです。 $\mathbf{w} \cdot \phi(\mathbf{x}, \mathbf{y})$ はスコアと考えることができます。後ほど具体例を用いて説明するため、今は「何かしらのスコアが入る」ぐらいで理解をしてください。最後に、 $Z$ は $Z = \sum_{\mathbf{y} \in \mathcal{Y}(\mathbf{x})} \exp(\mathbf{w} \cdot \phi(\mathbf{x}, \mathbf{y}))$ を表し、すべての解析結果の確率の和を1にするための正規化項です。

CRFにおいて、以下の計算で、 $\mathbf{w} \cdot \phi(\mathbf{x}, \mathbf{y})$ を最大化する $\mathbf{y}$ を求めます。

\begin{align*} \mathbf{y^*} &= \underset{\mathbf{y} \in \mathcal{Y}(\mathbf{x})}{\mathrm{arg\,max}} \ P(\mathbf{y}|\mathbf{x}) \\ &= \underset{\mathbf{y} \in \mathcal{Y}(\mathbf{x})}{\mathrm{arg\,max}} \ \left(\frac{\exp(\mathbf{w} \cdot \phi(\mathbf{x}, \mathbf{y}))}{Z}\right) \\ &= \underset{\mathbf{y} \in \mathcal{Y}(\mathbf{x})}{\mathrm{arg\,max}} \ (\mathbf{w} \cdot \phi(\mathbf{x}, \mathbf{y})) \end{align*}

CRFの目的関数は以下となります。

\begin{align*} l_{\text{crf}}(\mathbf{w}, \mathbf{x}, \mathbf{y}) &= - \log P(\mathbf{y}|\mathbf{x}) \\ &= -\mathbf{w} \cdot \phi(\mathbf{x}, \mathbf{y}) + \log(Z) \\ &= \log \left( \sum_{\mathbf{y} \in \mathcal{Y}(\mathbf{x})} \exp(\mathbf{w} \cdot \phi(\mathbf{x}, \mathbf{y})) \right) - \mathbf{w} \cdot \phi(\mathbf{x}, \mathbf{y}) \end{align*}

$Z$ が目的関数に入ることにより、CRFがexp（指数分布）で表現されている点が考慮されています。

CRFを例えばSGDのような最適化手法で最適化する場合、勾配の計算が必要になります。 $l_{\text{crf}}$ を $\mathbf{w}$ で微分すると以下のような式になります。導出過程は省略します。

$\displaystyle \nabla_{l_{\text{crf}}} (\mathbf{w}, \mathbf{x}, \mathbf{y}) = - \phi(\mathbf{x}, \mathbf{y}) + \sum_{\mathbf{y} \in \mathcal{Y}(\mathbf{x})} \phi(\mathbf{x}, \mathbf{y}) P(\mathbf{y}|\mathbf{x})$

上記の第二項は、全ての解の候補 $\mathbf{y}$ についての計算していますが、解の候補 $\mathbf{y}$ は入力 $\mathbf{x}$ の長さが長くなると、指数的にその候補数が増えていきます。そこで、動的計画法を用いて解の候補を効率的に計算しています。詳細は割愛します。

以上より、理解したことをまとめます。

CRFは入力 $\mathbf{x}$ に対し、解析結果 $\mathbf{y}$ が出力される条件付き確率 $P(\mathbf{y}|\mathbf{x})$ を計算していること。
CRFのパラメータ学習における目的関数は、 $\log \left( \sum_{\mathbf{y} \in \mathcal{Y}(\mathbf{x})} \exp(\mathbf{w} \cdot \phi(\mathbf{x}, \mathbf{y})) \right) - \mathbf{w} \cdot \phi(\mathbf{x}, \mathbf{y})$ であり、exp（指数分布）で表現されること。
勾配の計算の際に、解の候補 $\mathbf{y}$ が増えるため、そこで動的計画法による効率的な計算が行われていること。

スコアについての具体例

スコアを具体的な例で考えてみましょう。

$\mathbf{w} \cdot \phi(\mathbf{x}, \mathbf{y})$ はスコアであり、 $\mathbf{w}$ は重みベクトルを、 $\phi(\mathbf{x}, \mathbf{y})$ は素性ベクトルを意味していると説明しました。「Sansan株式会社はEightを運営する」というテキストを分かち書きし、B-組織名, I-組織名, O(その他)のタグのどれかに分類する固有表現認識のタスクを考えてみましょう。今回は、「その言葉がアルファベットのみで構成されているか」という素性ベクトルを適用してみます。その際、スコアがどのように計算されるかを以下の図に示します。