はじめに

本資料では，系列ラベリング問題を解くための手法である条件付き確率場についての解説を行う． 系列ラベリングとは，ある系列のそれぞれの要素にラベルを付与するタスクのことであり，自然言語処理における品詞タグ推定などが代表的な例である．

系列ラベリングと条件付き確率場

品詞タグ推定とは，系列ラベリングの一種であり，自然言語の文が与えられたときに文に含まれる各単語に対して適切な品詞タグを推定するタスクである． 条件付き確率場は系列ラベリング問題を解くために用いられる確率モデルである． 条件付き確率場をグラフィカルモデルによって表すと図\ref{fig:graphical_model}のようになる． ここで，$X=(x_1, x_2, x_3, x_4)$は観測されている系列（品詞タグ推定では単語）であり， $Y=(y_1, y_2, y_3, y_4)$はラベル列（品詞タグ推定では品詞タグ）である． $x_0$と$x_5$は文の開始と終了を示すためのダミー要素である． 条件付き確率場の条件付き確率は

\begin{eqnarray} P(\mathbf{y}|\mathbf{x}) = \frac{1}{Z_{\mathbf{x},\mathbf{w}}} \exp{(\mathbf{w} \cdot \mathbf{\Phi{(\mathbf{x}, \mathbf{y})}})} \end{eqnarray}

という式で表される．$\phi(\cdot)$は素性関数と呼ばれる関数であり，系列$\mathbf{x}$とラベル列$\mathbf{y}$を引数にとって素性値を返す． また，$\mathbf{w}$は素性に対する重みベクトルである．この重みベクトル$\mathbf{w}$を最適化するような学習を行うことになる． $Z_{\mathbf{x}, \mathbf{w}}$は規格化定数であり， $Z_{\mathbf{x}, \mathbf{w}} = \sum_{\mathbf{y}} \exp(\mathbf{w} \cdot \mathbf\Phi{(\mathbf{x}, \mathbf{y})})$と定義される．

単純な条件付き確率場のグラフィカルモデルは以下のようになる．

条件付き確率場における予測

条件付き確率場における予測は，条件付き確率$P(\mathbf{y}|\mathbf{x})$を最大化するような$\mathbf{y}$を求めることで達成される． この計算は一般にコストが高いため，条件付き確率場では素性関数について$\phi_k(\mathbf{x}, \mathbf{y}) = \sum_t \phi_k(\mathbf{x}, y_t, y_{t-1})$と仮定を置く． これにより，素性関数は以下のように変形できる．

\begin{eqnarray} \mathbf{w} \cdot \Phi(\mathbf{x}, \mathbf{y}) &=& \mathbf{w} \cdot \sum_{t} \Phi(\mathbf{x}, y_t, y_{t-1}) \\ &=& \sum_{t} \mathbf{w} \cdot \Phi(\mathbf{x}, y_t, y_{t-1}) \end{eqnarray}

これにより，条件付き確率を最大化するラベル列$\mathbf{y_{opt}}$は以下のように求めることができる．

\begin{eqnarray} \mathbf{y_{opt}} &=& argmax_{\mathbf{y}} \frac{1}{Z_{\mathbf{x}, \mathbf{w}} \exp(\mathbf{w} \cdot \Phi(\mathbf{x}, \mathbf{y}))} \\ &=& argmax_{\mathbf{y}} \mathbf{w} \cdot \Phi(\mathbf{x}, \mathbf{y}) \\ &=& argmax_{\mathbf{y}} \sum_t \mathbf{w} \cdot \Phi(\mathbf{x}, y_t, y_{t-1}) \end{eqnarray}

この形の最大化はViterbi algorithmによって高速に計算することができる．

条件付き確率場の学習

条件付き確率場の学習とは，目的関数$L(\mathbf{w})$をもっとも小さくするような重みベクトル$mathbf{w}$を求めることである． 条件付き確率場の学習は教室あり学習であり，教師データを系列とラベル列を用いて

\begin{eqnarray} D = \left\{ (x^{(1)}, y^{(1)}), (x^{(2)}, y^{(2)}), \dots, (x^{(|D|)}, y^{(|D|)}) \right\} \end{eqnarray}

と表す． 一方で，目的関数は

\begin{eqnarray} L(\mathbf{w}) = \sum_{D} \log{P(\mathbf{y}|\mathbf{x})} \end{eqnarray}

とかける．この目的関数の最適化には勾配降下法が用いられることが多い． 最急降下法の更新式は，

\begin{eqnarray} \mathbf{w_{new}} = \mathbf{w_{old}} + \alpha \frac{\partial{L(\mathbf{w_{old}})}}{\partial{\mathbf{w}}} \end{eqnarray}

であり，$\alpha$は学習率と呼ばれるハイパーパラメータである． 右辺の第２項の偏微分されている部分は勾配と呼ばれ，

\begin{eqnarray} \frac{\partial{L(\mathbf{w_{old}})}}{\partial{\mathbf{w}}} &=& \sum_{(x^{(i)}, y^{(i)}) \in D} \bigl( \Phi(\mathbf{x^{(i)}}, \mathbf{y^{(i)}}) - \sum_{\mathbf{y}|\mathbf{x^{(i)}}} \Phi(\mathbf{x^{(i)}}, \mathbf{y}) \bigr) \end{eqnarray}

である．素性関数に対する仮定により，右辺の和の２項目は

\begin{eqnarray} \sum_{\mathbf{y}|\mathbf{x}} \Phi(\mathbf{x}, \mathbf{y}) &=& \sum_{\mathbf{y}} P(\mathbf{y}|\mathbf{x}) \sum_{t} \Phi(\mathbf{x}, y_t, y_{t-1}) \\ &=& \sum_{t} \sum_{y_t, y_{t-1}} P(y_{t-1}, y_t|\mathbf{x}) \Phi(\mathbf{x}, y_t, y_{t-1}) \end{eqnarray}

と変形することができる． 素性関数についてはすでに定義がなされているので，勾配を計算するためには残りの$P(y_{t-1}, y_t|\mathbf{x})$が計算できればよい．

条件付き確率$P(y_{t-1}, y_t|\mathbf{x})$は，観測されている系列$\mathbf{x}$の系列長を$T$と，$y_0 = BOL$，$y_{T+1} = EOL$というダミーラベルを用意して，

\begin{eqnarray} P(y_{t-1}, y_t|\mathbf{x}) &=& \sum_{\mathbf{y_0}, \mathbf{y_1}, \dots, \mathbf{y_{t-2}}} \sum_{\mathbf{y_{t+1}}, \dots, \mathbf{y_{T+1}}} P(\mathbf{y}|\mathbf{x}) \\ &=& \sum_{\mathbf{y_0}, \mathbf{y_1}, \dots, \mathbf{y_{t-2}}} \sum_{\mathbf{y_{t+1}}, \dots, \mathbf{y_{T+1}}} \frac{1}{Z_{\mathbf{x}, \mathbf{w}}} \exp{(\mathbf{w} \cdot \Phi(\mathbf{x, \mathbf{y}}))} \\ &=& \frac{1}{Z_{\mathbf{x}, \mathbf{w}}} \sum_{\mathbf{y_0}, \mathbf{y_1}, \dots, \mathbf{y_{t-2}}} \sum_{\mathbf{y_{t+1}}} \prod_{t^{\prime}} \exp(\mathbf{w} \cdot \Phi(\mathbf{x}, y_{t^{\prime}}, y_{t^{\prime}-1})) \\ &=& \frac{\exp(\mathbf{w} \cdot \Phi(\mathbf{x}, y_t, y_{t-1}))}{Z_{\mathbf{x}, \mathbf{w}}} \sum_{\mathbf{y_0}, \mathbf{y_1}, \dots, \mathbf{y_{t-2}}} \sum_{\mathbf{y_{t+1}}} \prod_{t^{\prime} \neq t} \exp(\mathbf{w} \cdot \Phi(\mathbf{x}, y_{t^{\prime}}, y_{t^{\prime}-1})) \end{eqnarray}

と変形する．さらに，総和の項を$t-1$までの項と$t+1$からの項に分解すると，

\begin{eqnarray} && \frac{\exp(\mathbf{w} \cdot \Phi(\mathbf{x}, y_t, y_{t-1}))}{Z_{\mathbf{x}, \mathbf{w}}} \sum_{\mathbf{y_0}, \mathbf{y_1}, \dots, \mathbf{y_{t-2}}} \sum_{\mathbf{y_{t+1}}} \prod_{t^{\prime} \neq t} \exp(\mathbf{w} \cdot \Phi(\mathbf{x}, y_{t^{\prime}}, y_{t^{\prime}-1})) \\ &=& \bigl( \sum_{y_0, \dots, y_{t-2}} \prod_{t^{\prime}}^t \exp(\mathbf{w} \cdot \Phi(\mathbf{x}, y_{t^{\prime}}, y_{t^{\prime}})) \bigr) \bigl( \sum_{y_{t+1}, \dots, y_{T+1}} \prod_{t^{\prime} = t+1}^{T+1} \exp(\mathbf{w} \cdot \Phi(\mathbf{x}, y_{t^{\prime}}, y_{t^{\prime}})) \bigr) \end{eqnarray}

となる．ここで，

\begin{eqnarray} \alpha(y_t, t) &=& \sum_{y_0, \dots, y_{t-2}} \prod_{t^{\prime}}^t \exp(\mathbf{w} \cdot \Phi(\mathbf{x}, y_{t^{\prime}}, y_{t^{\prime}})) \\ \beta(y_t, t) &=& \sum_{y_{t+1}, \dots, y_{T+1}} \prod_{t^{\prime} = t+1}^{T+1} \exp(\mathbf{w} \cdot \Phi(\mathbf{x}, y_{t^{\prime}}, y_{t^{\prime}})) \end{eqnarray}

とおくと（ただし$\alpha(y_0, 0) = 1$，$\beta(y_{T+1}, T+1) = 1$とする），

\begin{eqnarray} P(y_t, y_{t-1}|\mathbf{x}) = \frac{\exp(\mathbf{w} \cdot \Phi(\mathbf{x}, y_t, y_{t-1}))}{Z_{\mathbf{x}, \mathbf{w}}} \alpha(y_{t-1}, t-1) \beta(y_t, t) \end{eqnarray}

となる．$\alpha(y_t, t)$を変形すると，

\begin{eqnarray} \alpha(y_t, t) &=& \sum_{y_0 \dots, y_{t-1}} \prod_{t^{\prime}}^t \exp(\mathbf{w} \cdot \Phi(\mathbf{x}, y_{t^{\prime}}, y_{t^{\prime}-1})) \\ &=& \sum_{y_{t-1}} \exp(\mathbf{w} \cdot \Phi(\mathbf{x}, y_t, y_{t-1})) \sum_{y_0 \dots, y_{t-2}} \prod_{t^{\prime}}^t \exp(\mathbf{w} \cdot \Phi(\mathbf{x}, y_{t^{\prime}}, y_{t^{\prime}-1})) \\ &=& \sum_{y_{t-1}} \exp(\mathbf{w} \cdot \Phi(\mathbf{x}, y_t, y_{t-1})) \alpha(y_{t-1}, t-1) \end{eqnarray}\begin{eqnarray} \beta(y_t, t) &=& \sum_{y_{t+1}, \dots, y_{T+1}} \prod_{t^{\prime} = t+1}^{T+1} \exp(\mathbf{w} \cdot \Phi(\mathbf{x}, y_{t^{\prime}}, y_{t^{\prime}})) \\ &=& \sum_{y_{t+1}} \exp(\mathbf{w} \cdot \Phi(\mathbf{x}, y_{t^{\prime}}, y_{t^{\prime}})) \sum_{y_{t+2}, \dots, y_{T+1}} \prod_{t^{\prime} = t+2}^{T+1} \exp(\mathbf{w} \cdot \Phi(\mathbf{x}, y_{t^{\prime}}, y_{t^{\prime}})) \\ &=& \sum_{y_{t+1}} \exp(\mathbf{w} \cdot \Phi(\mathbf{x}, y_{t^{\prime}}, y_{t^{\prime}})) \beta(y_{t+1}, t+1) \end{eqnarray}

が得られ，これらは動的計画法を用いて高速に計算することができる．