パーセプトロンはマージン最大化の夢を見るか？

　前回の記事は長くなりすぎたので、長文を読みたくない人のために、まず三行であらすじをまとめる。

  • ソフトマージンSVMがマージン最大化してるって言うけど、ちゃんと理解するの結構難しくない？
  • なんか自分の中で議論を進めると、正則化項つきパーセプトロンもマージン最大化に分類されるんだけど大丈夫？
  • こうなったらもう、正則化項つきパーセプトロンを実装して、実験してみるしかない…次回に続く

　という話であった。
　さて、前回の落ち穂ひろいから始めよう。前回「マージン最大化はSVMの特権ではなく、MIRAとかAveraged Perceptronとか、ラージマージン分類器と呼ばれる分類器はいくつもある」と書いたが、ここでは、「マージン最大化」という概念と、「ラージマージン」という、似たようだが違うかもしれない概念が混同して提示されている。どうも、この二つの用語は分けて考えた方が良さそうに思える。
　その観点からググッた結果、echizen_tmさんのコメントが見つかった。どうやら、同じことを考えている人は他にもいるようである、という事でやや安心をして、議論を先に進めることにする。
　「マージン最大化」と「ラージマージン」を分けて考えるとして、それぞれの単語の定義はどうなるのだろうか。まずは「マージン最大化」の方から。
　ここでは、もう一度ソフトマージンSVMの目的関数を思い出してみることにする。ソフトマージンSVMでは、

  • マージンをはみ出るものにはペナルティを与える
  • マージンをはみ出なかったものに関しては、ハードマージンの場合と同じくマージンを最大化する

　という二つの項の和を最適化するのであった。
　「マージンをはみ出る」とは言うが、これは具体的にはどういう場合を指すのだろうか。分離超平面を超えなければはみ出てはいない…ように思えるが、数式をよく見ると、分離超平面からある程度の余裕を持って正しく分類されていない場合はペナルティが課せられる。いわゆるヒンジロスという奴である。
　あれ、そもそもなんでこういう形になってんだっけ、という事を考えると、ハードマージンSVMの時の制約に思い当たる。ハードマージンSVMには以下のような不等式制約がある。

y w.cdot(x) >= 1

　ハードマージンSVMでは|w|とか|w|^2を最小化するわけだが、これがマージンの最大化になるというのは、上記の不等式制約があっての話である。今手元に教科書がないので適当なことを書いてしまっているかもしれないが、マージンの値はy(w・x + b)として書けるが、wを定数倍することでこの値は自由に調整することができるので、サポートベクターのマージンを1と決めてしまうと、|w|の最小化がマージンの最大化になる、という話なのであった。>= 1の= 1の部分がサポートベクターの場合を表しているということになる。
　wをスカラー倍することでマージンの値は操作できちゃうので、サポートベクターのマージンを「0.5」に決めてしまったり「3.14」に決めてしまったりしても、上記と同様の議論は成り立つ。ただ、0にしてしまうとマージンの値が0になってしまうのでそれはよくない。0より大きな実数にする必要がある。
　パーセプトロンの場合はここが0になる訳で、それが意味するところはマージンを最大化していない、ということである。wを無限倍することを考えるとSVMと同様の議論が成り立つ可能性はあるが、そこを追求することにあまり意味もなかろう。
　という訳で、当初の「正則化項つきパーセプトロンもマージン最大化に分類されるんだけど大丈夫？」という疑問に対する答えは「正則化項をつけたところでパーセプトロンはマージン最大化になりません」ということになる。違う、という結論が出てしまったので、実験は行わないことにする。
　まとめると、

  • マージン最大化には、マージンとして0より大きな実数を要求すること、|w|（か|w|^2）の最小化、の2つの条件が必要である。もしくは、これと等価な条件を要求しなければならない。
  • 正則化項つきパーセプトロンの場合は前者が満たされていないのでマージン最大化にはなっていない
  • 要するに前回の話には誤りが含まれている

　という話になった。
　世間ではよく「正則化=マージンの最大化」という扱いがされているような気がするのだが、「マージンとして0より大きな実数を要求すること」という条件も、（分かっている人には自明なのかもしれないけれど）もっと強調された方がいい、と思った。

ではマージンパーセプトロンの場合はどうなのか

　と、ここまでで終わろうと思ったのだが、マージンパーセプトロン（Perceptron with Marginsの方が一般的な表記のようだが、カタカナで書くと長すぎるので以下マージンパーセプトロンと表記する）とかはどうなんだろう、という疑問が湧いてきたので、まとめを書いた後だがもうちょっと話を続けることにしたい。
　マージンパーセプトロンというのはパーセプトロンで条件分岐の式をy w.cdot(x) >= λ みたいな形に書き換えたものである。ただし、正則化項はついていない。マージンパーセプトロンに正則化項をつければ、上記の議論からはマージン最大化の範疇に入ると言えそうだ。
　ところで、これまでいくつか実験してきた際の実感としては、マージン最大化に重要なのは|w|の最小化よりもむしろマージンとして0より大きな実数を要求すること、の方であるように思われる。
　そこで、調査班はさらなる文献の調査を続け、とある論文において以下の重大なフレーズを発見した。というか、Abstractの一行目に書いてあった。"A new incremental learning algorithm is described which approximates the maximal margin hyperplane w.r.t. norm p ≥ 2 for a set of linearly separable data." つまり、この論文では最大マージンの近似を行うオンライン学習アルゴリズムが記述されている。この論文はALMAというアルゴリズムの元論文であり、そもそもALMAという名前自体が「Approximate Large Margin algorithm」の頭文字を取ったものであるようだ。
　ALMAとマージンパーセプトロンは学習率の計算とかマージン(？)の計算とかでALMAの方がちょっと凝っているが、ほぼ同じものである。ここから、ALMAもマージンパーセプトロンも、「Max Marginの近似になっている」と言えそうだ。（本当に言いたかったらマージンパーセプトロンの方は証明が必要だが…）
　ALMAの名前からすると、Max MarginもLarge Marginも用語として明確な区別はないけれど、学習ループを何回も回した際に最終的に収束先がマージン最大化であればMax Margin、マージン最大化の保証がなければLarge Margin、ぐらいの使い分けをしてもいいのかなぁ、という気がした。
　ついでに、Passive Aggressiveのアルゴリズムもマージンパーセプトロンとほとんど一緒で、違うのは現在のサンプルを正しく分類できるように大きく動かすというところぐらいなので、Max Marginの近似（上記の使い分けをするならLarge Margin）と言ってよいだろう。（しつこいがこれも言いたければ本当は証明が必要だよ）
　以下、後半をまとめる。

  • マージン最大化には、マージンとして0より大きな実数を要求すること、|w|（か|w|^2）の最小化、の2つの条件が必要である。もしくは、これと等価な条件を要求しなければならない。
  • マージンとして0より大きな実数を要求することで、マージンを最大化とまではいかなくても、マージンを大きくする効果があるので、Large Marginと呼んで良いのではなかろうか。ただし証明は今のところない。

　なんか、当初の自分の実感とほぼ同じようなところに議論が着地したのでちょっとホッとしているのだが、連休明けぐらいに「間違ってるよ」とかコメントがつきそうで怖い。でも間違ったまま放置してしまうのはもっと怖いのでみなさんガンガン突っ込んでくださいね！

参考リンク