機械学習超入門III 〜機械学習の基礎、パーセプトロンを30分で作って学ぶ〜

計算機科学

機械学習には大きく分けて「識別関数」「識別モデル」「生成モデル」の3つの種類がある。このなかで識別関数は確率を使わないので初心者が入門するのに最適。
識別関数で有名なのはSVM(Support Vector Machine、サポートベクターマシン)。名前を聞いたことがある人も多いと思う。そこで早速SVMを学ぼうとすると敷居が高くて挫折しがち。
実はSVMは(大雑把に言うと)パーセプトロンという基礎的な識別関数に「マージン最大化」と「カーネル関数」という考え方を導入したもの。なので機械学習入門者は最初にパーセプトロンを学ぶのが良いと思われる。
そこで早速パーセプトロンを作ってみよう！というのが本記事の意図するところ。自分で実装できるとモチベーションが維持しやすいので、詳しく理論を学ぶ前にまずは作ってみようという考え。ちなみに実装にはperlを用いた。

参考:


さてパーセプトロンは識別関数のなかでも線形識別関数とよばれるものの一種。実は有名な識別関数はほぼ線形識別関数でSVMも線形識別関数。なのでこれを学ぶだけでSVMに大きく近づいた感がある。で、具体的には

y = wx

w: 重みベクトル
x: 入力ベクトル

という形をしているのが線形識別関数。単純に入力ベクトルと重みベクトルの内積をとっただけ。yが0より大きいか小さいかで入力ベクトルを2つのクラスに分類する。では早速この部分を実装してみる。

sub predict {
  my $w = shift;
  my $x = shift;

  my $y = 0;
  foreach my $f (keys %$x) {
    if ($w->{$f}) { $y += ($w->{$f} * $x->{$f}); }
  }
  return $y;
}

さて上記predict()関数に入力ベクトルxを与えれば識別結果が返ってくるのだが、それには重みベクトルwの値を決める必要がある。この重みベクトルの決定には損失関数(loss function)というのを用いる。
具体的に損失関数をどういう形にするか、という部分が識別関数のアルゴリズムの肝。パーセプトロンの場合には以下のヒンジ損失(hinge loss)という関数を用いる。

loss(w, x, t) = max(0, -twx)

w: 重みベクトル
x: 訓練ベクトル
t: xの正解ラベル(1 or -1)

これはどういう意味かを考える。wx、つまり識別関数の返す値と正解ラベルtの符号が同じならtwxは正の値になる。よってloss()は0を返す。これは識別関数が正しい符号の値を返したので損失は無いよという意味。
一方でwxとtの符号が異なるならloss()はtwxを返す。これは|wx|の大きさだけの損失があるよという意味。


さて。パーセプトロンの損失関数であるヒンジ損失がわかったので、ここからは学習の方法を説明する。
学習にはsgd(stochastic gradient discend)という手法を使う。これは「訓練データ1事例毎に損失関数を重みベクトルwについて微分したものを重みベクトルから引く」という操作を適当な回数繰り返すというもの。
ということでヒンジ損失の微分をする。微分と言うと身構えてしまうかもしれないがそんなに難しくない。具体的には

loss(w, x, t) = max(0, -twx)

をwで微分すると

∂loss() / ∂w = max(0, -tx)

となる。これは何を意味しているかというと識別関数が正解を返したら0を引く(=なにもしない)。間違いを返したら-txを引くつまりtxを足す(=正解ラベルと訓練データを掛けたものを足す)ということ。
しくみがわかったので早速実装してみる。

sub train {
  my $w = shift;
  my $x = shift;
  my $t = shift;

  my $y = predict($w, $x);
  if ($y * $t < 0) {
    foreach my $f (keys %$x) {
      $w->{$f} += ($t * $x->{$f});
    } 
  }
}

さて(1回の)訓練部分が実装できたので全体のプログラムを書いてみる。

#!/usr/local/bin/perl
use strict;
use warnings;

# RGB値を素性とした訓練データ
# 暖色系カラーなら1
# 寒色系カラーなら-1を正解ラベルとする
my @x_list = ({R => 255, G =>   0, B =>   0, bias => 1},
              {R =>   0, G => 255, B => 255, bias => 1},
              {R =>   0, G => 255, B =>   0, bias => 1},
              {R => 255, G =>   0, B => 255, bias => 1},
              {R =>   0, G =>   0, B => 255, bias => 1},
              {R => 255, G => 255, B =>   0, bias => 1},
              );
my @t_list = (1, -1, -1, 1, -1, 1);

# 訓練パート
my $w    = {R => 0, G => 0, B => 0, bias => 1}; # 重みベクトル
my $loop = 10; # 訓練の繰り返し回数
while ($loop) {
  for (my $i = 0; $i < @x_list; $i++) {
    train($w, $x_list[$i], $t_list[$i]);
  }
  $loop--;
}

# 推定パート
while (<>) {
  chomp;
  my @fs = split(/ /);
  if (@fs != 3) {
    warn "invalid input data.\n";
    next;
  }
  my $x = {R => $fs[0], G => $fs[1], B => $fs[2], bias => 1};
  my $t = predict($w, $x);
  if ($t >= 0) { print "> warm color.\n"; }
  else         { print "> cold color.\n"; }
}

ここまででパーセプトロンの実装は完了。perceptron.plなどとして保存しておく。ちょい長いがそんなに難しくはないはず。
なお今回の例ではRGB値に対して暖色系or寒色系を返すパーセプトロンを作った。素性としてRGB値に加えてbiasという素性を入れているが、これはRGB値の例題に限らず線形識別をする際に入れておくべき項なのだが今回は解説を割愛した。値としては何でもよいのだが、とりあえず1を入れておく。詳しくは本記事末尾の参考書を参照されたい。

さて。無事実装できたので推定実験してみよう！入力例として

WEBセーフカラー216色−WEBカラーリファレンス

を使う。

$$ ./perceptron.pl
102 204 255
> cold color
255 51 102
> warm color

といった感じ。上の例では訓練データを基本の6色(赤、青、緑、黄、マゼンタ、シアン)にしたが、これにほかの色を加えて工夫するなど色々遊んで感覚を掴むといいかも。


最後に。パーセプトロンに代表される識別関数の教科書としては「わかりやすいパターン認識(わかパタ)」「サポートベクターマシン入門(赤本)」を推薦しておく。前者は大変わかり易いので最初に読むのに適している。後者は実装、理論両面で優れているが邦訳の質が大変よくないので出来れば原著を読むのがよい。