Kernel Averaged Perceptron の話

learning

要約すると、
カーネルパーセプトロンを使うくらいならサポートベクターマシンを使ったほうがいい
という話。


以下、パーセプトロンとかカーネルとか基本的なところばかり書きます。


＜パーセプトロン＞
正負ラベルを予測する二値分類を行うパーセプトロンの場合、以下のアルゴリズムで訓練する。
・以下を、重みが収束するまで繰り返す
　1. サンプル（正解ラベル付き）をランダムにとってくる
　2. 現在の重みとサンプルの内積をとって、その符号（つまり予測されたラベル）が正しければ 1. へ
　3. 重み = 重み - あるべき符号 * サンプル
推論（符号が未知のサンプルに対するラベルの予測）のときも、2. と同様に重みとの内積の結果の符号をとって返す。

パーセプトロンはオンラインで使える。
つまり、サンプルが次々と追加される場合でも、順序がランダム（変な偏りがない）と仮定できるなら、上記のアルゴリズムをそのまま適用してよい。


＜平均化 (averaged)パーセプトロン＞
[2009-03-09-1] 参照。
大雑把には、
・パーセプトロンの重みは、訓練データの線形和
・averaged perceptron の重みは、パーセプトロンの訓練中の過去の重みを平均化したもの
・つまりaveraged perceptron の重みは線形和の線形和 → 単純に計算すると2乗が出てくるけど、有限の線形和の線形和は線形和で書ける
という話。
パーセプトロンの弱点である重みの不安定性（入力順序への依存性）を緩和できているということになっていて、
経験的にも確かにそんな感じ。
計算時間を（実質上）増やさない実装ができるので、
最近パーセプトロンで分類やランキングをするといえば、
ほとんどこれになっている。
NLTKなどに入っている実装もこれ。
原典は Y Freund, RE Schapire Machine learning, 1999 "Large margin classification using the perceptron algorithm".


＜カーネル＞
カーネルは通常、内積の一般化の形をしている。
内積は同じ軸の量同士の符号が似ているほど大きくなる。
内積の代わりにカーネルを使うことによって、異なる軸の量同士の相関をはかることができる。
たとえば多項式カーネルでは、内積の代わりに、内積のN乗をする（Nは固定）。
(x y + a)^N

たとえば3次元のベクトルに対する2次の多項式カーネル を書き下すと、
(x1y1 + x2y2 + x3y3 + 1) ^ 2
= x1y1^2 + x1y1x2y2 + x1y1x3y3 + a x1y1 +
x2y2x1y1 + x2y2^2 + x2y2x3y3 + a x2y2 +
x3y3x1y1 + x3y3x2y2 + x3y3^2 + a x3y3

このようになる。
異なる次元 (たとえば第2項は1次元目と2次元目）の比較が入っていることがポイント。
（ここでは二値分類、つまり値が正か負かだけに注目するので、2つの数の掛け算は2つの数の類似度の一種として扱える）

また、 a != 0 の多項式カーネルは内積そのものに相当する項を持っていること、その項の係数が a であることから、多項式カーネルの符号は、a が大きいほど内積そのものに近づくことが分かる。
逆に a = 0 を選ぶと、内積が入らなくなるので、過学習しやすいかもしれない。

＜カーネルパーセプトロン＞
原典は averaged perceptron と同じく
Y Freund, RE Schapire Machine learning, 1999 "Large margin classification using the perceptron algorithm".
averaged perceptron に出てくる内積を全部カーネルに置き換える。
ただし、非カーネルの平均化パーセプトロンとは違って、カーネルの線形和は線形和で書けないので
誤分類をしたとき、重みに足し算をする代わりに、あとで足せるように係数とどのサンプルだったかを覚えておく。
予測をするときになって、覚えておいたサンプルとのカーネルを計算する。

カーネルを使うと分類精度は少し上がるんだけど、
訓練の途中で誤分類するほど予測が遅くなるというのが欠点。
サンプル数が多い場合はメモリも気になってくる。

パーセプトロンは訓練と推論が同じ予測モジュールによっているので、
訓練も推論もおなじように遅くなる。

そこへいくと、ハードマージンのサポートベクターマシン (SVM) は覚えておくサンプルの数が極端に少ない（実数ベクトルなら2個だったりする）いので、速い。
ソフトマージンであっても、SVMの方が体感的には圧倒的に速い（ただし、独自実装のカーネルパーセプトロンとtinysvmの比較）。

ということで、
せっかくカーネルパーセプトロンを実装したのに遅くて残念（というか早く気づけ）という話でした。


＜今後の課題＞
可能なアプローチとしては
1. キャッシュを使う
2. カーネルを使わず組み合わせ素性（など）で事前に展開する
3. 覚えるサンプルを選択して数を減らす

とりあえず 1. をやってみたけど、
・キャッシュの実装が悪いと効かない（当たり前）
・収束が速い（けれども訓練データに実質的な重複があったりしてサンプルが多い）ときに効かない。これはNLPでよくある。

2. は実用的にはありだと思う。
ただし、カーネルを使うのをあきらめるというのに等しい。

3. は研究方面ですでにいくつか手法が出ている。
Projectron など。
特に、テスト時の計算時間を短くできるのが魅力的。
ただいかんせん線形でしか効かない＆ドラスティックに減らすと性能が落ちるのが明らかなので、決定的な高速化手法ではない。


＜補遺＞
名前は Averaged Kernel Perceptron （平均化カーネルパーセプトロン）という方がいいかもしれない。
↓はそう言っている。
http://alias-i.com/lingpipe/docs/api/com/aliasi/classify/PerceptronClassifier.html
上記のドキュメントは lingpipe の javadoc ですが、アルゴリズムの説明が書かれています。
実装したいときには、論文読むよりわかりやすいかも。

Maybe I missed something but I don't understand why he/she and others say that Kernel Perceptrons is faster than SVMs ...
http://blog.so8848.com/2008/04/26046.html