Support Vector Machine
昨日の話の続き。
実験で学習をするロボットを作るということで、学習のためのアルゴリズムをいくつか調べた。そこで最終的に採用したのがSupport Vector Machine(SVM)。詳しい説明は各サイトでどうぞ。
提案された当初のSVMは線形分離可能な2クラスを識別するためのアルゴリズムだったのだけど、カーネルトリックと呼ばれる手法を取り入れることによって非線形な集合の識別にも適用することができるようになった。実際に使ってみると、確かににょろーんとした境界を張って識別してくれるんだよなあ。不思議。
Javaアプレットでデモを作ってみたので、よかったら遊んでみてください。
- http://nya3.jp/files/SVMDemo/SVMDemo.html (Javaアプレット)
- http://nya3.jp/files/SVMDemo/example1.png (例1)
- http://nya3.jp/files/SVMDemo/example2.png (例2)
- http://nya3.jp/files/SVMDemo/jp/nya3/SVMDemo/ (ソースコード)
Classボタンで追加するサンプルのクラス(赤/青)を選んで、クリックでサンプルを配置できる。カーネルは線形/多項式/ガウスを選択可能で、スライダーを動かすことでカーネルパラメータを調整できる。両クラスのサンプルを配置したら、Learnボタンを押せば判別曲線の計算が始まり、結果が表示される。
ソフトマージンを適当に導入しているので、多項式/ガウスカーネルはけっこう速く収束するけど、あまり細かい領域に違うクラスを密集させると誤判別が起きるので注意。線形カーネルはソフトマージンがあっても線形非分離な場合はなかなか収束してくれないので、最適化のイテレーションを5000回で打ち切るようにしてある。最適化アルゴリズムには平易で実装が手軽なSMO(もどき)を使っている。
実は非線形SVMはただの余興で、実験には線形SVMしか使わないのだけどね...
(追記)
単純なUIのバグで、多項式カーネルの結果だと思っていたものは実はガウスカーネルのものでした... アプレットを修正しておきました。