機械学習超入門IV 〜SVM(サポートベクターマシン)だって30分で作れちゃう☆〜
ニーズがあるのかさっぱりわからない機械学習超入門だけどひっそり続けていきたい。
前回は識別関数の基礎であるパーセプトロンの簡単な説明とPerlによる実装を解説した。実はこの時点でかの有名なSVM(Support Vector Machine、サポートベクターマシン)もほぼ完成していたのだ！というわけで今回はSVMをPerlで作ってしまうお話。
参考:
さて、前回ちょっと触れたのだがSVMはパーセプトロンに「カーネル関数」と「マージン最大化」を加えたもの。この2つがそれぞれどんなものかを説明する。
「カーネル関数」は簡単に言うとSVMの「パワーアップ装備」のようなもので複数の種類があり用途に応じて使い分ける。前回登場した線形識別関数は
y = wx w: 重みベクトル x: 入力ベクトル
というかたちをしていた。これに「カーネル関数」を導入すると
y = Σ_i {ai * k(xi, x)}
xi: i番目のSV(サポートベクトル)
ai: i番目のSVの重み
x : 入力ベクトルとなる。突然SVというのが出てきたが、この記事で説明する線形カーネルでは一旦忘れて大丈夫なので気にしないように。このk(xi, x)がカーネル関数で、これまでに複数提案されている。が、カーネル関数を利用したSVMは処理が重いということもあり実務でありがちな「大規模データを高速に処理する」という場面では最も簡単なカーネルである「線形カーネル」を使う。線形カーネルは
k(xi, x) = xi * x
y = Σ_i {ai * k(xi, x)}
= Σ_i {ai * xi * x}
= wxと定義されている。つまり線形識別関数y=wxは線形カーネルを利用した識別関数であると言える。よって線形カーネルを使うことにすればひとまず「カーネル関数」については忘れてしまって良い。詳しく学びたい人は赤穂先生の「カーネル多変量解析」が役に立つ。
話を戻して次は「マージン最大化」。これは「VC理論」というものによって「マージンを最大化すれば未知のデータに対する分類性能が最大化される」とされていることからマージンを最大化することで未知のデータを正しく分類しよう！というもの。この「マージン最大化」を加味して損失関数を考えたい(損失関数こそが識別関数のアルゴリズムの肝だということを前回書いた)。
でマージンとはなんぞ、というと
margin(w) = λ / w^2
で定義される量。直感的な言い方だと識別関数の絶対値がλ(ラムダ)以下になってほしくないですよ、という量。つまり例えばλ=1なら、y=wxの値がy=0.5とかy=-0.7とかだったら「ちょっとスコアが小さすぎて信用できませんね」ということ。
この事実を加味すれば「マージン」を加味した損失関数が作れる。
つまり
loss(w, x, t) = max(0, λ - twx) w: 重みベクトル x: 訓練ベクトル t: xの正解ラベル(1 or -1)
loss(w, x, t) = max(0, -twx)
という損失関数を使っていたので、識別関数が正しく分類した場合にtwxは正の値をとるため、-twxは負の値なりmax(0, -twx)はゼロを返した(つまり損失はないとした)。
ところがSVMでは損失関数をmax(0, λ - twx)としている。これによってtwxが正の値をとったとしてもλより小さければ(λ - twx)という損失が発生する。つまり既に述べたようにλよりも小さいスコアになってほしくないため損失が発生するようになっている。
さてこれでSVMの損失関数は万全・・・ではない！マージンの考えを組み込んだことで確かにλよりも小さいスコアになりにくくなったが、まだ肝心のマージンが最大化されていない。
ではどうやって最大化するか。マージンをよく見てみよう。
margin(w) = λ / w^2
マージンの分母にw^2というのがある。これに着目する。分母であるw^2が小さい値をとれば全体の値は大きくなる。つまりマージンが最大化される！
ということでこの考えを早速SVMの損失関数に組み込む。
loss(w, x, t) = max(0, λ - twx) + α * w^2 / 2
これこそがSVMの真の損失関数。損失関数にw^2を加えたのでw^2が大きくなるほど損失が大きくなる、という効果が得られる(よって学習はwが極力小さくなるように行われる)。
αはこの「wを小さくする」の影響の大きさ。ユーザが調整することができるパラメータ。αを大きくし過ぎるとwがずっと小さいままで学習が上手くいかず、αが小さいと今度はマージンが最大化されなくなる。このあたりはデータとにらめっこしつつ調整する。
ついでに、なんで2で割っているかというと、前回やったようにsgdアルゴリズムでの学習は損失関数を微分する。w^2を微分すると2 * w^2となるので事前に2で割っておけば先頭の2が消えてきれいというわけ。
というわけで損失関数ができたのでsgdのために損失関数を微分する。
∂loss(w, x, t) / ∂w = ∂(λ - twx + α * w^2 / 2) / ∂w = - tx + αw
これを実際のPerlのコードに組み込むとtrainは以下のようになる。
sub train {
my $w = shift;
my $x = shift;
my $t = shift;
my $lambda = shift;
my $alpha = shift;
my $y = predict($w, $x);
if ($y * $t < $lambda) {
foreach my $f (keys %$x) {
my $wt = $w->{$f};
$w->{$f} += ($t * $x->{$f});
$w->{$f} -= ($alpha * $wt);
}
}
}
パーセプトロンのtrainから変更した箇所は太字にした。説明は長かったがコードとしてはパーセプトロンからの変更はあまり多くない。λとαをいろいろ動かして遊んでみると良いかも。
余談だが今回紹介したようなカーネル関数を線形カーネルに限定し、sgdアルゴリズムで学習するようなSVMはオンラインSVMと呼ばれており昔ながらのSVMに比べて精度面で若干劣るものの、高速に大規模データを処理できるという利点から近年盛んに利用されている。オンラインSVMの実装としてはLeon氏のsgdsvmが優れている。コードも大変参考になる。
またパーセプトロンとSVMの関連についてはtkng氏が詳しいので是非参考にされたい。
追記。うっかりしていたがsleepy_yoshiさんの下記発表資料にもパーセプトロンとSVMの関係がとても分かりやすく書いてある。オススメ。
