SVMのマージン最大化についてしつこく考えてみる
SVMの説明というと、よく出てくるのはマージンの最大化である。しかし、実装を行う場合には、どちらかというと目的関数をどうやって最小化しようかな、というところの方が重要（注：主形式を勾配法で最適化する場合の話です）で、この間にある微妙なギャップを超えるのは微妙ながらも大変なような気がしている。このギャップをどうやったら埋められるのかというところを考えてみたい。考えながら書いてきちんと推敲しておりませんのでご注意ください。
SVMってなに、という説明でよくあるパターンは、線形識別器（というか、SVM）の学習というのはパラメーターをいじって分離(超)平面をいい感じに引くことですよ、というところから始まり、いい感じってなんだろうか、マージンが最大化されるように引くといいっぽいよね、けど分離不可能な場合はマージンの値が負になることがあるよね、そこでソフトマージンというものを定義して、マージンが負になることにはペナルティを与えることにしましょう、という感じではなかろうか。
この最後のソフトマージンのところで私はつまづくのである。ハードマージンのわかりやすさに安心したところに、不意討ちのようにソフトマージンが来るのだが、その難しさにダメージを受けたことに気づくことすら難しい。
ハードマージンの場合は制約であったのに対して、ソフトマージンではペナルティという概念が入っており、根本的にマージンというものに対する考え方を変えないといけなくなっているように思う。少なくとも、念入りに解釈を行う必要はある。
ソフトマージンの場合を考えると、ヒンジロスの和+正則化項という目的関数の方を天下り的に与え、それの解釈としてソフトマージンという概念を後付けした方がよいのではないかと思うのだが、どうだろうか。
マージンの最大化という観点から離れると、別の説明方法も思いつく。SVMをFOBOSで最適化する場合とパーセプトロンとでは、パーセプトロンの場合はパラメーターの更新基準が
if y w.cdot(x) > 0
となっており、正解すればそれでよしとしているのに対し、SVMの場合は
if y w.cdot(x) > 1
という形になっているだけの違いしかない。（パーセプトロンにはそもそも正則化という概念はないけれど、普通に実装できるのでそれについては細かい話であるとしておく）
しかしこの違いが性能の差を産む。パーセプトロンだと分類に成功していればそれでよしとするのに対し、SVMの場合は分類にある程度の余裕を持って成功する必要がある。余裕が足りなかった場合にはパラメーターが更新される。正のクラスと負のクラスの両方からこの押し合いが行われることでマージンが大きくなる（最大化されるかどうかは自明ではない）ことは、直感的に想像しやすい。
しかし、SVMと言えばマージンの最大化とカーネルトリックの組み合わせな訳で、マージンの最大化についてはしっかりと理解しておきたいところである。その意味では、上の説明では不足がある。
ここまで書いてきて、やはり一番大きな問題なのは、ソフトマージンという概念が難しいということであると感じた。
ソフトマージン最大化というのは
- 正しく判別している点については(ハード)マージンを最大化
- 誤判定したデータについてはペナルティの最小化
という2つの目的関数の和であり、どちらを重要視するかがCという定数によって決められる訳だが、ここがどうもまだ直感的に飲み込めない。
極端な例を考えてみよう。Cをとても小さな値、例えば10^-8ぐらいに設定することを考えてみよう。これはつまりマージン最大化を重要視しないということであるが、マージンの最大化を重要視しないということは、ペナルティを最小化することに注力する、ということである。言い換えれば、経験損失の最小化をとにかく頑張ろう、という話である。逆に、マージンの最大化を非常に重要視する例を考えてみる。Cが10^8ぐらいの値であることを考えよう。この時、分類器はとにかくマージンを最大化することを目指す。経験損失が多少高くなろうが、知ったことではない。
さらにここで、正則化という概念も混ざってくる。「言語処理のための機械学習入門」のP.134には「じつは、SVMのマージン最大化も正則化の一種である」とあるが、正則化とマージン最大化の間にはどういう関係があるのだろうか。包含関係なのだろうか。
何がわからないかがよくわからなくなってきたので、今一度整理してみることにする。
- ソフトマージンの最大化が理解しにくい
- 正則化とマージン最大化の関係がわからない
一番目は最初からの課題であり、ソフトマージンという概念を直感的にどう理解すればいいのか、というところでずっと悩んでいるわけだ。これについてはしかし、Cの値を極端に動かした際の挙動を想像することで、ある程度わかってきたように思う。ポイントは経験損失と期待損失の違いで、マージンの最大化というのは期待損失を減らす方向に効果がある。ハードマージンの場合も、マージンの最大化には期待損失を減らす効果があった（というか、期待損失を減らす効果しかない）のだが、ソフトマージンの場合は、期待損失の事を強く意識しないと訳が分からなくなる。
二番目、正則化というのはパラメーターの複雑度に応じてペナルティをかける仕組みで、ソフトマージンSVMの目的関数においては|w|もしくは|w|^2の最小化の部分が正則化項に相当する。
では、正則化項があればそれでいいのか。正則化項つきパーセプトロンはマージンを最大化するのか。先ほど述べたように、SVMの損失関数は、あきらかにパーセプトロンよりも性能が良さそうに見える。正則化が付いていれば、パーセプトロンもマージン最大化なのだろうか。
マージン最大化はSVMの特権ではなく、MIRAとかAveraged Perceptronとか、ラージマージン分類器と呼ばれる分類器はいくつもあるわけであるのだが、単なる正則化項つきパーセプトロンをこの中に入れるというのは、感情的にはなんだか承服しがたい。どうも、自分の一番の悩みはここにありそうな気がしてきた。
論理的には、
という話だと思うのだが、その一方でラージマージン分類器は良いものだ、というこれまでの自分の中の知識が、「あれ、そうすると正則化項つきパーセプトロンはけっこういい性能出るはずなんじゃないの？」という疑問を投げかけてくる。それに対して、自分は明確な回答を用意することができない。
さて、ここまで議論が整理できたのであれば、次は実際に試してみるしかありますまい。という訳で、次回に続く。
