機械学習で利用されるモデルの一つに、条件付き確率場というものがある。 このモデルの尤度関数の勾配を直感的に理解できる説明を思いついたので、 忘れないようにメモしておく(直感的な説明は最後の節なので、 知っている人はそれ以外の節を読み飛ばすと良いです)。

条件付き確率場の基礎知識

マルコフ確率場 (Markov random field) の一種に条件付き確率場 (conditional random field; CRF) というモデルがある。 マルコフ確率場は、無向グラフで複数の確率変数の間にある依存関係を表現するモデルであり、 条件付き確率場は、マルコフ確率場をクラス分類に特化させたようなモデルだ。 特に、依存関係のある複数の対象に対して、同時にクラス分類を行いたいときに便利で、 自然言語処理などでは品詞の推定などに利用している。

個人的に、条件付き確率場そのものについては、

Charles Sutton and Andrew McCallum. An Introduction to Conditional Random Fields. Foundations and Trends (R) in Machine Learning: Vol. 4: No. 4, pp 267-373. 2012. http://dx.doi.org/10.1561/2200000013

がわかりやすかった。親切なことに 著者 (C. Sutton) の Web ページPDF が置いてあるので、 条件付き確率場を知らない人は、読んでみると良い。 英語だけど、専門用語さえ知っていれば、そんなに難しくない。

この記事で必要になる数式を簡単に紹介しておく。 マルコフ確率場はグラフ全体で同時確率(因数分解)を定めるのに対して、 条件付き確率場は条件付き確率

\[p(\bm{y} | G,\bm{x},\bm{w})=\frac{1}{Z(G,\bm{x},\bm{w})} \exp(\bm{w}^\top \bm{f}(G,\bm{x},\bm{y}))\]

を定める。ただし、$G=(V,E)$ は無向グラフ、 $\bm{x}$ は入力(品詞推定では単語)のベクトル、 $\bm{y}$ は出力(品詞推定では品詞、以下ラベルと呼ぶ)のベクトル、 $\bm{w}$ は重みベクトル、 $\bm{f}$ は(グラフ全体に対する)特徴ベクトルを返す関数である。 $Z(G,\bm{x},\bm{w})$ は単なる正規化係数で

\[Z(G,\bm{x},\bm{w})=\sum_{\bm{y}}\exp(\bm{w}^\top \bm{f}(G,\bm{x},\bm{y})\]

と定義される。 総和で束縛される $\bm{y}$ の動く範囲は「可能性のある全てのラベルの割り当て方」だが、 素朴にはラベルの集合 $T$、$\bm{y}$ の次元 $m$ について、$T^m$ を定義域にすれば良い。

パラメータ推定

重みベクトルを求めることをパラメータ推定 (parameter estimation) という。 モチベーションとしては、訓練集合(ラベル付けの正答例の集合) $S = \{(G_i,\bm{x}_i,\bm{y}_i)\mid{}i=1,2,\dots,n\}$ を与えて、 そこから最も良い重みベクトルを求めてほしい。 「最も良い」を決めるためには「良さ」の基準が必要になるが、その決め方は幾つかある。 今日は、一番素朴な「尤度 (likelihood)が大きいほど良い」という考え方で説明する。 尤度は

\[L(S, \bm{w})=\prod^n_{i=1} p(\bm{y}_i G_i,\bm{x}_i,\bm{w})\]

であり、基本的には尤度を最大化するような重みベクトルを求めたい (厳密には、上の式は尤度そのものではなく、訓練集合を使った尤度の近似)。 ただし、上の式は $\bm{w}$ について凸ではないため、 最大化問題の解析解を求めることは困難であり、近似解法に頼ることが多い。 やり方は色々あるが、今回は勾配上昇法について考える。

※ 尤度を良さの基準とし、尤度を最大化する重みを求めることを 最尤推定 (maximum likelihood estimation; MLE) という。 「良さ」の基準として、尤度ではなく、事後確率を考える 最大事後確率 (maximum a posterior estimation; MAP) というものもある。 事前確率の仮定の置き方で色々種類があるが、一番良く使われているのは、 事前確率をゼロ平均のガウス分布と仮定する L2 正則化である。

勾配上昇法

以前書いた、確率的勾配降下法の記事を呼んでくれると、だいたいわかると思う。 今回の主題は最大化問題なので、確率的ではない勾配上昇法 (gradient ascent) について考える (最適化の方向が反対なだけで、本質的には勾配降下法と全く同じ)。

勾配上昇法では、学習率 $\eta$ と適当な初期値 $x^{(0)}$ を決め、 以下の式を反復することにより $f(x)$ を最大化するような $x$ を見つける。

\[x^{(\tau+1)} = x^{(\tau)} + \eta \frac{\mathrm{d}f}{\mathrm{d}x} \quad (\tau = 0,1,2,\dots)\]

今回考えている条件付き確率場のパラメータ推定では、尤度関数を最大化する。 しかし、尤度関数を直接最大化しようとすると、数式が複雑になって数値計算に時間がかかるので、 多くの場合は対数尤度を最大化する(対数は単調増加なので、最大値を保存する)。 つまり、勾配上昇法の式は

\[\bm{w}^{(\tau+1)} = \bm{w}^{(\tau)} + \eta \bm{\nabla} \ln L(S, \bm{w})\]

となる。ただし、

\[\bm{\nabla} = \left(\frac{\partial}{\partial w_1},\dots,\frac{\partial}{\partial w_D} \right)\]

である($D$ は特徴・重みベクトルの次元)。 地道に計算すると、

\begin{align} \bm{\nabla} \ln L(S, \bm{w}) &=\sum^n_{i=1} \bm{\nabla} \ln p(\bm{y}_i|G_i,\bm{x}_i,\bm{w})\
&=\sum^n_{i=1}\left\{ \bm{f}(G_i,\bm{x}_i,\bm{y}_i) -\sum_{\bm{y}’} p(\bm{y}’ | G_i, \bm{x}_i, \bm{w}) \bm{f}(G_i, \bm{x}_i, \bm{y}’)] \right\} \end{align
}

という式が導ける。

勾配の式の意味を理解する

式全体の前に、まず、理解のポイントは 4 つ:

  1. 条件付き確率 $p(\bm{y}|G,\bm{x},\bm{w})$ は「入力 $G,\bm{x}$ に対するラベル $\bm{y}$ のスコア(点数)」だと思うと良い。最も良い(もっともらしい)ラベルならば 100 点 (1.0) となり、最も悪いラベルならば、0 点 (0.0) となる。
  2. 訓練事例は正答例なので、各要素 $(G,\bm{x},\bm{y})\in S$ について、 スコア $p(\bm{y}|G,\bm{x},\bm{w})$ は大きくなるべき。 勾配を大きくすることで、勾配上昇法はスコアが増加する方向に $\bm{w}^{(\tau)}$ を移動させてくれる (必ずスコアが増加するという保証はないけど、概ね増加する)ので、勾配を大きくしたい。
  3. 逆に、$\bm{y}’\ne\bm{y}$ であるような $\bm{y}’$ は不正解なので、 スコア $p(\bm{y}’|G,\bm{x},\bm{w})$ は小さくなるべき。 よって、勾配が小さくなれば良い。
  4. 2 と 3 を達成するためには、$\bm{y}’\ne\bm{y}$ であるような $\bm{y}’$ に対して、 スコアが大きくなってしまった場合に、罰則 (penalty) を与えて、 勾配を減少させれば良い(ここで言う罰則は正則化のそれとは別物)。

これらを踏まえたうえで、 勾配の式の $\sum_{\bm{y}’}$ を $\bm{y}’=\bm{y}_i$(正解した場合)と $\bm{y}’\ne\bm{y}_i$(不正解の場合)で分解すると、

\[\bm{\nabla} \ln L(S, \bm{w}) =\sum^n_{i=1}\Biggl\{(1 - p(\bm{y}_i|G,\bm{x},\bm{w})) \bm{f}(G_i,\bm{x}_i,\bm{y}_i) -\underbrace{\sum_{\bm{y}’\ne\bm{y}} p(\bm{y}’ | G_i, \bm{x}_i, \bm{w}) \bm{f}(G_i, \bm{x}_i, \bm{y}’)}_{\mbox{penalty}}] \Biggr\}\]

となる。上のポイントに沿って、式を解釈すると、

  • 後半の総和は明らかに罰則項で、不正解に対してスコアが大きくなると、 勾配を負の方向に誘導する力が働くようになっている。つまり、不正解の場合のスコアを減らす。
  • 一方で、前半の特徴ベクトルに掛かる係数 $1 - p(\bm{y}_i|G,\bm{x},\bm{w})$ は、 正答例に対するスコア $p(\bm{y}_i|G,\bm{x},\bm{w})$ が小さい場合は、係数が大きくなり、 勾配が大きくなる方向に誘導する。そのため、正答例に対するスコアは大きくなる。 $p(\bm{y}_i|G,\bm{x},\bm{w}) \le 1$ なので、 係数が負になる(=勾配を負の方向に誘導する)ことがない。

というわけで、条件付き確率場の学習における勾配の式は直感的にもわかりやすい、というお話。