Introduction to Information Retrieval輪講 第16回

場所は今回も初台のDeNAさんの会議室でした。読んだのは15章の「サポートベクターマシンと文書の機械学習」という章です。15.4の前まで読みました。

実は今回ほとんど予習していない状態で行ってしまい、内容も難しくて数学が苦手な私にはよく理解できませんでした。この章は理論は解説してくれるのですが、疑似コードなど実装の話は出てきません。分かりやすいという話を聞いたオーム社の『サポートベクターマシン』を帰宅後注文しました。引き続き勉強するとして、とりあえず分かったことだけ書きます。

サポートベクターマシン（SVM）は、前回のRocchioなどと同じように、教師付き学習を用いた、ベクトル表現に基づく分類器の一種と考えていいようです。Rocchioとは違い、クラスの重心を考えるのではなくて、境界線をどこに引くかを考える方法だそうです。そのためにクラス分布の端にある文書だけを考えます。この文書一つ一つのことをサポートベクトルと呼びます。

境界線から一番近くの文書までの距離をマージンといいますが、SVMはこれが最大になるような境界を見つけようとします。この境界に基づいて、新しい入力を分類すれば、大体合っているだろうというわけです。

と書くと簡単っぽいですが、高次元でこれをやるのがSVMの偉いところなんでしょう。ナイーブベイズだと70%の精度、SVMだと80%の精度、というのが現場の感覚らしいです。とは言え、正直言って、なぜSVMが優れた性能を持ち、複雑な計算による学習を必要とするのかがちゃんと理解できていないです。

マージンを最大化する問題は、二次計画問題に還元できるそうです。ここで、サポートベクトルを決定するためにラグランジュの未定乗数法というのを使います。この辺が分からないと実装できないわけですが、さっぱりです。

というわけで、基本が分かっていないので後はキーワードだけ書きます。

ソフトマージン分類法は多少の例外を認めるという拡張。SVMにおける学習の複雑度は、文書数の3乗オーダーだが、経験的には1.7乗オーダーになる。cutting planesというものを使うと1乗になる（!?）。文書ベクトルを高次元にマップするカーネルトリックを使うことで、ノンリニアの問題に対応できる。（でもロイター21578というデータセットでの実験結果によると、リニアバージョンとほとんど変わってない。）

うーん、もうちょっと勉強します。まずちゃんと予習して行かないと。