MLPシリーズ サポートベクトルマシン

MLPシリーズの「サポートベクトルマシン」を読んだので中身の備忘録。

第一章：2クラス分類問題
ハードマージン、ソフトマージン、双対表現、カーネルによる一般化、ヒンジ損失について。SVMの基礎的な内容。

第二章：多クラス分類問題
1対1方式、1対多方式、ペアワイズカップリング、誤り訂正出力符号など。SVMに限らず、一般の2クラス識別問題に拡張できる話が多い。

第三章：回帰分析
SVRについて。SV回帰のノイズモデルは識別で用いられるノイズモデルと比べてやや特殊なので、回帰においてスパース性を利用したいときはL1正則化を用いることが多い、というのは実情として納得。というかなるほど。

第四章：教師なし学習のためのサポートベクトルマシン
教師なし学習について概説した後、異常検知のための1-class SVMについての紹介。

第五章：カーネル関数
カーネルの基本的性質の紹介から、文字列カーネルやグラフカーネルなどの紹介など。それほどきっちり説明しているわけではないので、カーネルをしっかり勉強したければ赤穂先生の本を併せて読んだ方がよい。

第六章：最適化概論
KKT条件の説明、及び一般的な最適化方法（アクティブセット法と内点法）について解説。これも最適化をしっかり勉強したければ別の本も併せて読んだ方がよい。

第七章：分割法
大規模データセットに対してパラメータ最適化を行うためのSVM特異な最適化方法。またの名をチャンキング法。基本的には、（同時に全データを扱うことはできないので）作業集合の分割と更新を繰り返して最適解への収束を調べる。カーネルSVMのためのSMOアルゴリズムと、線形SVMのためのDCDMアルゴリズムを紹介。（制約条件の違いで、作業集合が２変数になるか1変数になるかの違いが出る）丁寧に数式が書かれていてわかりやすい

第八章：モデル選択と正則化パス追跡
前半はCVについて。後半は、正則化パラメーターCを変化させたときに、双対変数がどのような軌跡をたどるかを求めるアルゴリズムの紹介。（双対変数の最適解をパラメーターCで表現した式を求める）　これにより、様々なCを振った条件下で改めてパラメーターを最適化するよりも計算時間が少なくて済む。

第九章：逐次学習
SVMの逐次学習。

第十章：サポートベクトルマシンのソフトウェアと実装
RでのSVMの紹介と、LIBSVMの中身で使われているアルゴリズムについて紹介。LIBSVMを使う以上は、実装について知識を持っておいた方がよいので有用な章。

第十一章：構造化サポートベクトルマシン
（最近出てきた？）出力変数として値ではなく構造（木構造など）を学習するSVM。出力と入力を合わせて結合特徴ベクトルとして学習する。出力変数が膨大な空間になるため同時計算が困難だが、切除平面法と呼ばれる最適化法を利用して学習する。具体的には、空の制約集合からスタートして、現在の制約から違反している順番に出力変数を制約に加えていくというもの。名前をちょくちょく聞くが、よくわかっていなかったので勉強になった。

第十二章：弱ラベル学習のためのサポートベクトルマシン
教師データが完全に与えられていないときのための学習方法。具体的には、半教師あり学習とマルチインスタンス学習（事例の集合に対してクラスのラベルが与えられており、負のラベルを与えられているときはその集合の中身は全て負だが、正のラベルを与えられているときはその集合は正と負を含む、といったケース）について。マルチインスタンス学習は薬剤活性分析で元々使われ始めたらしいが、少々特殊な気がしないでもない。

全体の感想
MLPシリーズ第一期の例にもれず、式展開を丁寧に説明しているためわかりやすく、また構造化SVMなど発展的な事も記載されているため非常に勉強になった。途中で「本書では省略する」が多発するところがあったが、最適化法やカーネルについてまでこの本の中で詳述するわけにはいかないので、仕方のない所が多いと思う。PRMLのサポートベクトルマシンの記述は薄い（本書で言えば、1〜3章の内容を薄めたくらい）し、「サポートベクトルマシン入門」に比べてもわかりやすいし発展的な内容を含むので、SVMを勉強するならまず読んで損はないと思われる。