Conditional Random Fields（CRF）入門その1 -主な参考資料と目的関数-

Conditional Random Fields（CRF）がわかりません。何それおいしいの？状態ですが、ここから学習をはじめています。前向きアルゴリズム？後ろ向きアルゴリズム？Viterbiアルゴリズム？どこで使うのそれ？状態ですね。その状態を脱出するため日々奮闘中です。なお、この記事では自分の思考に則って書いていますので、綺麗な教科書的ではないこと（構造学習がなんたら等はあまり触れない）を始めに断っておきます。

脱出するために利用している資料は以下の通りです：

1.「日本語入力を支える技術」（以下IME本）：実装する上では一番初心者にやさしい本です。

日本語入力を支える技術　?変わり続けるコンピュータと言葉の世界 (WEB+DB PRESS plus)

作者: 徳永拓之
出版社/メーカー: 技術評論社
発売日: 2012/02/08
メディア: 単行本（ソフトカバー）
購入: 14人クリック: 322回
この商品を含むブログ (36件) を見る

2.「Crfと素性テンプレート」：具体例があって非常にわかりやすいです。数学ガール風に言えば、「例示は理解の試金石」なので、重要ですね。

Crfと素性テンプレート from Kei Uchiumi

3. An Introduction to Conditional Random Fields for Relational Learning：CRFに関する有名なTutorialです。数式の流れがHMMからの拡張として導出されているのでわかりやすいです。ただし、長い上に数式もかなり出てくるので完全に理解するには数年かかりそうです。

1.と2.は特におすすめです。目的関数の動きのイメージが詳しく書かれているので、わかりやすいです。3.は初心者である自分にとっては詳しすぎる感じがあるので、末永く付き合っていきます。他にもCourseraの授業や、130行で実装されたCRFのPythonコード等があります。しかし、Courseraの授業は確率的トピックモデルからの視点で幅広く説明しており、コードに関しては解説がないので僕には難しいです。

CRFの概要

まず、CRFは機械学習における一つの学習手法です。機械学習の手法は基本的に「重みを目的関数に沿って最適化」しています。では何の重みか？どういう目的関数なのか？というのを順番に見ていきます。

重みに関して

CRFで調整する重みは「素性関数に対する重み」です。ここでは素性（素性関数の引数）としては、１．入力系列、２．直前のラベル、３．ターゲットとしている現在のラベル、４．何番目の状態か（tで表すものとします）。

「例示は理解の試金石」なので、タスクとして、ゲームのタイトルを文字レベルで抽出するタスクを考えます。
入力系列としては以下の文字列、ラベルとしてはB(egin)、I(nside)、O(utside)、として考えましょう。

今日はドラクエとFFをプレイした。

この時、
今：O、日：O、は：O、ド：B、ラ：I、ク：I、エ：I、と：O、F：B、F：I、を：O、プ：O、レ：O、イ：O、し：O、た：O、。：O
が正しいラベル系列であります。１．入力文字ド、２．直前のラベルO、３．現在のラベルB、４．（頭から数えて）4番目の状態になります。素性関数の一例としては、 $\Phi(do, O, B, 4) = 1$ になっています(doは「ド」のことです。日本語が表示できないのでローマ字表記しています)。これらの素性関数一つ一つに重みを割り振っていきます。

目的関数に関して

CRFにおいて、最適化の対象とする目的関数は：
$\150dpi P(y|x) = \frac{exp(w \cdot \Phi(x, y))}{Z}$

ただし、 $Z = \Sigma_y exp(w \cdot \Phi(x, y))}$ です。ここで $\Phi(x, y)$ は素性関数を表し、xは入力系列、yはラベル列を表しています。Zは確率であることを保証している為に用いられています。

この目的関数自体は（前向き後ろ向きアルゴリズム等のキーワードと関連している）直接的なポイントではなく、メインは最適化する際に関係してきます。最適化手法として、ここでは基本的な最適化手法の一つである確率的勾配降下法（Stochastic Gradient Descent, SGD）を使います。これはIME本のp.165にある通り、「すり鉢状になった土地を歩いて...最後にいちばん低いところにたどりつく」「ただし、...自分の近くしか見えない...」というイメージがぴったりだと思います（CourseraのMachine Learningの授業で良いイメージ図があるので、詳しくはそちらを）。蛇足ですが、最急降下法との違いは「必ずしも全学習データを使わない」「一つずつデータを処理するかどうか」の二点です。
（ちなみにIME本にも触れられていますが、IME本で主に使われているFOBOSとSGDの違いは微分不可能な点に対処できるかできないか、です。ただし、2009年の話ですが、L1-SGDなどの手法も提案されているようです。詳しくはL1-SGD等を参照してみてください。またFOBOSに関してはIME本とFOBOSを実装してみた(理論編) - Goto_youthKの徒然日記等を参照してみてください）

以下がSGDによる重みの更新式です：
$\150dpi w_{t+1} = w_t + \eta g$
gは勾配でηは学習率です。

このgを効率良く算出するために、前向き後ろ向きアルゴリズムを用います。また、Viterbiアルゴリズムは実際にCRFモデルを構築した後に、テストケースに関して適用する際に利用します。そこらへんの話はまた今度の記事にて書きます。