CRFがよくわからなくてお腹が痛くなってしまう人のための30分でわかるCRFのはなし
機械学習の3大有名手法といえばSVM、CRF、LDAではないだろうか(と勝手に思っている)。
SVM(Support Vector Machine)については以前記事を書いたので今回はCRF(Conditional Random Fields)について書いてみたい。
機械学習超入門IV 〜SVM(サポートベクターマシン)だって30分で作れちゃう☆〜 - EchizenBlog-Zwei
といっても今回はさくっと読んでもらうのを目的にしているので手法の具体的な解説は行わない。具体的な部分は@uchumik氏の資料がとても詳しい｡
また、実装方法については高村本(言語処理のための機械学習入門)がとても詳しい。
さて、具体的な解説をしないなら何をするの？ということだが、今回はそもそもCRFとは何かという話をする。過去の経験上この、そもそもの部分がわかっていない人が圧倒的に多かったのがその理由。
最初に結論。CRFは「系列ラベリング」という問題を解くための手法。その特徴は「識別モデル」であること、「構造学習」をしていることの2つ。
ということで「系列ラベリング」「識別モデル」「構造学習」の3つのキーワードについて解説していく。
機械学習の最も基本的な問題は「分類問題」と呼ばれるもので例えばメールをスパムかどうか分類したりするような問題を扱う。これはパーセプトロンやSVMで解くことができる。
これに対して「系列ラベリング」というのは入力としてデータの列を与えて、出力として個々のデータにラベルを付けてもらう、というもの。具体的には単語列に品詞を与える問題
入力: 私 / は / カレー / を / 食べ / た。 出力: 名詞 / 助詞 / 名詞 / 助詞 / 動詞 / 助動詞
などがある。
この「系列ラベリング」の問題は「分類問題」として解くことができる。どういうことか。上の品詞を与える例で説明する。まず「私」の品詞を分類する問題を解く。次に「は」の品詞を分類する問題を解く。これを繰り返して全ての単語に品詞を与えることができる。
また素性を工夫することで周辺の単語の状態も考慮することができる。どういうことかというと「カレー」を分類するのに「カレー」という単語だけでなく「一つ前の単語が「は」だった」「一つ前の単語の品詞が「助詞」だった」という素性を持たせることができる。
というわけで無事系列ラベリング問題を解くことができた。ここで話を終わらせてしまってもいいのだが、そうすると永遠にCRFは登場しない。
CRFは先に述べたように「識別モデル」という種類の機械学習の手法。パーセプトロンやSVMは「識別関数」と呼ばれる種類の機械学習の手法で、データを分類することしか考えていない。これに対して「識別モデル」はデータがあるクラス(ラベル、カテゴリ)に分類されるかどうかを確率値で得ることができる。単純な「分類問題」に対する「識別モデル」としては対数線形モデル(log-linear model)が最も基本的。別名最大エントロピー法とも呼ばれている。
というわけで対数線形モデルを使えば「単語列に品詞を与える問題」に対して「各単語に対して各品詞が割り当てられる確率を得る」ことができる。なので「別に確率はいらないや」ということならSVMを使ってもなんら差し支えない。
さて「系列ラベリング」問題は各データ毎に「分類問題」を解くことで解決することがわかった。また推定結果が確率であって欲しい場合は「識別モデル」を使って解くことができることもわかった。
ここで最後のキーワード「構造学習」が登場する。構造学習というのは個別にデータのクラスを推定せずにデータを全部渡して、まとめてデータごとのラベルを得る方法。つまり最初に示した
入力: 私 / は / カレー / を / 食べ / た。 出力: 名詞 / 助詞 / 名詞 / 助詞 / 動詞 / 助動詞
をそのままの形で実現する手法。構造学習をすると何が嬉しいのか？通常の分類問題の場合は、個別に品詞を求めるため、個々の品詞として最適なものを与えた結果全体としては最適ではないものを選んでしまう可能性がある。どういうことかというと例えば、以下のひらがな文を漢字変換する問題を考える。
入力: おかし に こ ください 出力: ????
これを前から順番に漢字を割り当てていくと、まず「おかし」に「お菓子」を割り当てる。次に「に」に割り当てる候補として「に」と「二」があったとき、「お菓子」につながりやすいのは「に」のほうなので「に」はそのまま「に」が割り当てられる。
しかしすぐ後ろの「こ」に「個」が割り当てられることがわかっていれば「に」は「二」であることがわかる。このように順番に分類問題を解いていったのでは解決が困難な問題があるので、こういう場合、データを全部渡して、全体として最適な分類結果をもらってしまおうというのが「構造学習」。
この「構造学習」と前述の「識別モデル」によって「系列ラベリング」問題を解く手法がCRFということ。
さてここまで書いてきて「構造学習」が「系列ラベリング」問題に有効っぽいことはなんとなく解ったと思う。が、もうひとつの「識別モデル」はそんなにいらなくね？と思った人もいるかもしれない。
そこで登場するのが構造化パーセプトロンもしくは構造化SVMである。これは識別モデルではなく識別関数を使った構造学習の手法。もし確率はいらないが構造学習で系列ラベリングを解きたいのであればこの構造化SVMなどで十分だったりする。
構造化SVMについてはWEB+DB PRESS Vol.64の日本語入力の記事が詳しい。
というわけでCRFとはなんぞという説明をした。最近自然言語処理から遠ざかっているので例題として出した例が必ずしも適切ではないかもしれないのだが、CRFがどういうものか、どういうときに使えばいいかという説明はできたと思う。ここまで読んで「やはり自分が抱えている問題を解くにはCRFが必要だ」ということであれば高村本を読めばいいと思うし、「別に系列ラベリングなんてしたくなかった」ということならSVMで十分。「系列ラベリングはしたいが確率は必要でもない」なら構造化SVMでOKということになる。
