条件付き確率場(CRF)概説 CRF以前編 - 気まぐれエンジニア日記

みなさま, いかがお過ごしでしょうか. 筆者は春休みの研究がちょっと落ちつきまして新しいことをしようかなーと考えています. きっと春休みに研究なんぞしようかと考える学生はそうそういないかと思いますがね. 今日も平常運転, くまちゃんです.

さて, その新しいことをしようかなーの関係でCRFの勉強をしといたほうがいいかなということで, ちょっとドキュメントを読んでいます.
そのドキュメントというのはこちらです
条件付き確率場の理論と実践
今回は, 筆者の頭の整理にお付き合いいただく目的で, CRFについて簡単(図が出てこないので書くのは簡単)にまとめていきたいと思います. 今回は前編でCRFの直前のところについて書いていきます.

1. ロジスティック回帰

まずはデータの2クラス分類問題を考えてみましょう. 2クラス分類問題とは, 入力 $x$ が与えられたとき, それが $A$ , $B = A^c$ のどちらに属するかを推定する問題のことです. 簡単な例をあげると, 入力として英文中の英単語が与えられたとき, それが人の名前であるか人の名前でないかを推定する問題は2クラス分類問題になります. パターン認識の枠組みでは, 入力を特徴ベクトルという何らかの数字の並びにうまく変換して, 特徴ベクトルの格好から1つクラスを推定します.
今, 入力である英文中の英単語全体の集合をX, 特徴ベクトルをd次元の実数の組 $\mathbb{R}^d$ , 出力をクラス全体の集合 $Y = \{1, -1\}$ と書くことにしましょう. 2クラス分類問題ですから, 人の名前であることを1が出力されること, 人の名前でないことを-1が出力されることだとしても問題ないことに注意してください.
すると, 入力から特徴ベクトルを生成する関数(特徴抽出器と呼びます) $\phi$ は, 次の写像です.
$\displaystyle \phi: X \to \mathbb{R}^d$
パターン認識ではこの特徴抽出器をいかに作るかが非常に重要, というか研究することは特徴抽出器の設計に他ならないのだけれど, ここでは研究者が非常に頑張って, うまく特徴抽出器が作れたとしましょう. その上で, どのような基準でクラスを決定するか, もっと言えば1, -1のどちらを出力するかについて考えていきます.

特徴ベクトルが与えられたときに, それが2つのクラスのうちのどちらかであるかを推定するには, 特徴ベクトル全体の空間 $\mathbb{R}^d$ を2つのグループに分けてしまえば良いです. 一方のグループであればそれは一方のクラスの特徴ベクトルだと思うことができるからです. 特徴ベクトル全体の空間 $\mathbb{R}^d$ を2つのグループに分ける方法として, 最も単純なのは1つ平面を決めてしまってそれを境界面にしてしまうことです. 今, ベクトル $\textbf{w} \in \mathbb{R}^d$ を法線ベクトルにもつ境界面が識別平面を与えるとしましょう. そのとき, 識別の条件は次のように書くことができます.

$\displaystyle y = \begin{cases} 1 & \textbf{w}^ T \phi(x) + b > 0 \\ -1 & \textbf{w}^ T \phi(x) + b < 0 \\ \end{cases} \Leftrightarrow y(\textbf{w}^T\phi(x) + b) > 0$

$\displaystyle \left(\begin{matrix} \phi(x) \\ b \end{matrix}\right) \to \phi(x) ~~~ \left(\begin{matrix} \textbf{w} \\ 1 \end{matrix}\right) \to \textbf{w}$
とベクトル拡張した形で書き直せば, $y\textbf{w}^T \phi(x) > 0$ とかけます. さて, $y\textbf{w}^T \phi(x)$ の部分をロジスティック関数
$\displaystyle \sigma (z) := \frac{1}{1+ \exp(-z)}$
に代入してみましょう. ロジスティック関数は値域が $(0, 1)$ であるような単調増加関数です. 入力が $x$ であるときに, 出力が $y \in Y = \{1, -1\}$ となる条件は $y\textbf{w}^T \phi(x) > 0$ と書けますが, この値は大きい方が「安全に」識別できて優位と考えるべきでしょう. したがって,
$\displaystyle \sigma (y\textbf{w}^T \phi(x)) = \frac{1}{1+ \exp(-y\textbf{w}^T \phi(x))}$
は $(0, 1)$ の値を取り, 大きい方が優位と考えることができます. したがって, 今この値は識別平面のパラメータを $\textbf{w}$ とするときに $x$ を入力として $y$ を出力する"条件付き確率"のようなものだとみなすことができます. これは正確には確率ではないので「みなす」だけですが, 1つ評価軸ができたのは非常に大きいです. 確率だと思うことにしようと言いましたから, 記号も確率っぽくしてしまいましょう.
$\displaystyle p(y|x) := \sigma (y\textbf{w}^T \phi(x)) = \frac{1}{1+ \exp(-y\textbf{w}^T \phi(x))}$

2. ロジスティック回帰の学習

$x$ を入力として $y$ を出力する"条件付き確率"のようなもの定義することができましたから, 入力 $x$ と正解ラベル $y^*$ が与えられたときには, $p(y^*|x)$ を最大化するように $\textbf{w}$ を決めてやれば良いということになります. 入力データと正解ラベルの組みが大量に与えられたときには, この確率の積
$\displaystyle L(X, Y) := \prod_{i = 1}^N p(y_i|x_i)$
を最大化するように $\textbf{w}$ を決めてやれば良さそうです. この値は尤度と呼ばれ, 尤度の最大化によるパラメタ推定の手法を最尤推定と呼びます. 時間軸に沿った系列データとして入力データと正解ラベルの組み与えられる場合には, 尤度にはただの積以上の意味を見いだすことができるのですが, ここでは系列データに限らないのでただの積として捉えることにします. ここまでくれば, 識別平面のパラメタ $\textbf{w}$ の決定問題は次の最適化問題として定式化されることになります.
$\displaystyle \textbf{w}^* = \arg\max_{\textbf{w} \in \mathbb{R}^d} L(X, Y)$
ここから先の勾配法を用いて実際に最適解を求める手法については, 他の場所でも広く取り扱われていますから, ここで改めて深く言及する必要はないでしょう. 勾配法と言っても様々なアルゴリズムがありますが, それらについてより知識を得たい方は, 例えばこんなドキュメントがオススメです.
An overview of gradient descent optimization algorithms

3. 多クラス線形識別器

今までは入力データ $x$ が与えられたときに出力を1と-1のどちらにするべきだろうかという2クラス分類問題を考えてきました. しかしながら, 残念なことに世の中の一般の問題は2つのうちのどちらであるかの識別だけでは解くことができないものがほとんどです. $K$ 種類のラベルがあってそのうちのどれであるかを識別したいなんてことはしばしばありますし(例えば, 解決済みですが単語の品詞分類タスク), 2クラス分類問題だけを考えていたつもりでも, クラスAかクラスBか"そのどちらでもない"かが問題となることは珍しくありません. ここからは, 3クラス以上の分類タスクを考えることにしましょう.
先まで考えていたパラメタ $\textbf{w}$ は, 識別平面の法線ベクトルの末尾に切片 $b$ を連結したものとして捉えていました. ここでは, その捉え方を少し変えてみましょう. $\textbf{w}$ はクラスAの代表ベクトルであるという捉え方です. 実際,
$\displaystyle s(1 \cdot \textbf{w}^T \textbf{w}) = \frac{1}{1+ \exp(-\textbf{w}^T \textbf{w})}$
なるスコア値は, (少なくとも $\textbf{w}$ と大きさが等しいベクトルの中では)もっとも値が大きくなりますから, $\textbf{w}$ 自身は真っ先にクラスAに識別されるべきベクトルということになります. 同様に, クラスBの代表ベクトルは $-\textbf{w}$ となります.
他クラス線形識別においては, この代表ベクトルの考え方を採用しましょう. $K$ 個のクラスの代表ベクトルをそれぞれ $\textbf{w}_1, \textbf{w}_2, \cdots, \textbf{w}_K$ とします. $K-1$ 個のクラスの識別ができれば, $K$ 個目のクラスは"それ以外"だと思えばいいので, 実はこれらのベクトルは一次独立ではなくて
$\displaystyle \textbf{w}_1 + \textbf{w}_2 + \cdots + \textbf{w}_K = \textbf{0}$
なる関係式が成り立つとしても良いです. そのため, 実質的なパラメータとしては1つ少ないです. けれども, 以降はこういった細かいことは特に気にしなくても問題ありません. 代表ベクトルが決まってしまえば, 入力が $x$ であるときに, 出力が $y \in Y = \{1, 2, \cdots, K\}$ となる条件は, 2クラス識別問題の時と同様に考えることができて, $\textbf{w}_{y'}^T\phi(x)$ がなるべく大きい方が優位ですから.
$\displaystyle y = \arg \max _{y'\in Y} \textbf{w}_{y'}^T\phi(x)$
とかけます.
上の内積の格好で話を進めてもいいのですが, もう少し一般化をしてみましょう. 上の格好では, 出力である識別クラスの情報を $\textbf{w}_y$ たちが持っていて, 入力の特徴ベクトルの情報を $\phi(x)$ が持っているといったように, 入力と出力がベクトルとして完全に分離できるという制約をおいています. だけれども, この分離可能性の制約は必須ではありません. より複雑な識別をしたいと考えたときには, この制約は邪魔になってしまいます. そこで次のように考えましょう. 何らかの定ベクトル $\textbf{v}$ をうまく決めておきます. そして, 入力 $x$ とクラス $y$ を引数にとって, $x$ を $y$ に分類しようと考えたときの特徴ベクトルを返す関数を $\textbf{f}(x, y)$ を用意します. その上で,
$\displaystyle y = \arg \max _{y'\in Y} \textbf{v}^T \textbf{f}(x, y)$
として識別結果を決めます. $\textbf{f}(x, y)$ が何者であるかはブラックボックスですが, $y$ が, $x$ が分類されるべきクラスであれば有意な値を多く持つベクトルとなるだろうし, そうでなければほとんどゼロベクトルに近いか識別に否定的なベクトルを返す関数であることが期待されます. この方法が先の $\textbf{w}_y$ たちによるものの拡張であることを確認しておきましょう.
$\displaystyle \textbf{v} = \left(\begin{matrix} \textbf{w}_1 \\ \textbf{w}_2 \\ \vdots \\ \textbf{w}_K \\ \end{matrix}\right) ~~~~~ \textbf{f}(x, y) = \left(\begin{matrix} \textbf{0} \\ \vdots \\ \textbf{0} \\ \phi(x) \\ \textbf{0} \\ \vdots \\ \textbf{0} \\ \end{matrix}\right) < y番目$
とおけば(これらは行列ではなくて $d \times K$ 次元の長い列ベクトルです),
$\displaystyle y = \arg \max _{y'\in Y} \textbf{v}^T \textbf{f}(x, y)$
は
$\displaystyle y = \arg \max _{y'\in Y} \textbf{w}_{y'}^T\phi(x)$
と等しくなります. すなわち, $\textbf{f}(x, y)$ による表現方法は $\textbf{w}_y$ による表現も含んでいることが確認できました.
次に, 2クラス分類問題の時と同様に $x$ を入力として $y$ を出力する"条件付き確率"のようなものを定義することを考えましょう. これが定義できれば, あとは最尤推定の問題に帰着されますから, 解くことができます. 2クラス分類問題の時にはロジスティック関数を用いましたが, 多クラスの場合にはそれを拡張したともみれるソフトマックス関数を用いてみましょう.
$\displaystyle p(y|x) := \frac{\exp(\textbf{v}^T \textbf{f}(x, y))}{\displaystyle \sum_{y' \in Y} \exp(\textbf{v}^T \textbf{f}(x, y'))}$
あとは最尤推定の問題として最適化問題を解きます.

CRF以前編は以上です. 次の記事で本格的にCRFを扱います.
お疲れ様でした〜