perlでSGD版SVMを書いてみた
SVM(Support Vector Machine, サポートベクターマシン, サポートベクトルマシン)をperlで書いてみた。
実装が簡単という理由からSGDによるオンライン学習を行っている。カーネル行列(グラム行列)をメモリに持っておかないといけないので本当の意味ではオンライン化されていないが、SVMを理解するためのサンプルとしてはSGDで実装するのは手頃ではないかと思う。
#!/usr/local/bin/perl
# $Id$
use strict;
use warnings;
my $d = 3; # x ∈ R^3
my $n = 6; # number of training data
my $t = 10; # iteration
# label (warm color:1, cold color:-1)
my @yy = (1, -1, -1, -1, 1, 1);
# training data
my @xx = ([1, 0, 0], # red
[0, 1, 0], # green
[0, 0, 1], # blue
[0, 1, 1], # cyan
[1, 0, 1], # magenta
[1, 1, 0] # yellow
);
# alpha parameter
my @aa = (0, 0, 0, 0, 0, 0);
# bias parameter
my $bias = 0;
# estimate alpha
for (my $s = 0; $s < $t; $s++) {
for (my $i = 0; $i < $n; $i++) {
$aa[$i] += (1 - $yy[$i] * margin($xx[$i]));
if ($aa[$i] < 0) { $aa[$i] = 0; }
}
}
# estimate bias
my $max = 0;
my $min = 0;
for (my $i = 0; $i < $n; $i++) {
my $m = margin($xx[$i]);
if ($yy[$i] == -1 and $m > $max) { $max = $m; }
if ($yy[$i] == 1 and $m < $min) { $min = $m; }
}
$bias = ($max + $min) / 2;
# estimate label for new data
while (<>) {
chomp;
my @x = split(/ /);
for (my $i = 0; $i < $d; $i++) { $x[$i] /= 255; }
my $m = margin(\@x) + $bias;
if ($m > 0) { print "> warn color\n"; }
else { print "> cold color\n"; }
}
#### sub routines ####
sub margin {
my $x = shift;
my $m = 0;
for (my $i = 0; $i < $n; $i++) {
$m += ($aa[$i] * $yy[$i] * kernel($xx[$i], $x));
}
return $m;
}
sub kernel {
my $x1 = shift;
my $x2 = shift;
my $k = 0;
for (my $i = 0; $i < $d; $i++) {
$k += ($x1->[$i] * $x2->[$i]);
}
return $k;
}このサンプルは色のRGB値を入力すると、その色が暖色系なのか寒色系なのかを教えてくれるというもの。例えば
を参考にwebセーフカラーをいくつか入力してみる。
$$ ./svm.pl 102 204 255 > cold color 255 51 102 > warn color 00 255 153 > cold color 255 255 51 > warn color
というわけで割と正しく推定されている。
本記事では理論的な部分はほとんど書いていない。なぜこんな記事を書いたかというと、SVMの入門記事を読むと大抵カーネル関数やマージン最大化などの概要がふわっと書いてあるだけで、結局初心者にとってはよく分からないのでいいや、ってなってしまいがちだと思ったから。プログラムがすべてではないけどSVMにはこういう簡単な実装もあるよとわかったら勉強する気も出てくるんじゃないかな、と。
なお本実装は「サポートベクターマシン入門」という書籍の6章から7章を参考にした。翻訳の質はアレだが元が良書なのでSVM作りたい、理解したいという人にはオススメ。(英語に自信のある方は原書で！)
