パーセプトロンが線形分離可能であることの証明 その１

いよいよ、本題であるパーセプトロンが線形分離可能であるということの証明に入ります。証明の大きな流れとしては次のようになります。

1. たとえば、本来y=w・x+bの外側にあるデータが学習途中のパーセプトロンが行う分類では内側にあると判定されたとしましょう。そのときパーセプトロンがy=w・x+b≦0と答えます。つまり、本来と符号が逆ということです。このように間違ったときに負の値を返すような関数をマージンといい、基本的には超平面とトレーニングデータの集合の各要素との距離を表わす関数として定義します。距離ならば負の時は間違いと分かりますよね。
2. 最終的には、パーセプトロンの学習した超平面ともともとの教師用の超平面は一致せずにある距離が生まれるでしょう？これを最大マージンと言ったりもしますが、この間に入るようなデータだけがうまく分類できない可能性があります。その可能性が極めて小さければ、パーセプトロンはトレーニングデータの学習によって線形分離可能だ、と言うことができるでしょう。

さて、本格的に証明する前に、少しだけ準備をしましょう。すでにいくつかは出てきていますが、用語やその他の概念を定義して、説明する必要があるからです。

ここからは、テキスト「サポートベクターマシン入門」のp.16にある定義2.2を以下参照して説明します。

まず、マージンについてです。超平面が法線ベクトルwとバイアスbで表わされ、あるi番目の入力（xi,yi)のマージンγiを以下のように定義します。

　 γi=yi (<w・xi>+b)

ちなみにですが、少し話がそれますが、前回のプログラムにPARAMS.MARGIN_Hというものがあり、学習するときの値の変化に大きく関わっていました。こちらの方は学習率といいます。こちらも覚えといて下さいね。

さて、マージンγiに話を戻しますが、図５に幾何マージン関数マージンを簡単に図示しました。簡単に言うと2点間の距離が幾何マージンで2つの平行する超平面間の距離が関数マージンです。この関数マージン負の時に学習がやり直される、というのが学習のアルゴリズムでの条件でもあります。

さて、トレーニングデータの集合Sがあるとします。トレーニングデータSの各要素ごとに、教師である超平面の方程式と平行な超平面が作ることができ、教師である平面とのそれぞれの距離は幾何マージンと同じになりますよね。

さて、教師である超平面と最も距離の小さい（最も幾何マージンの少ない）トレーニングデータの集合Sの点までの距離（数学的に正確に言うとユークリッド距離）が、学習の結果、これ以上教師である超平面と近づくことのできない関数マージンと考えられるでしょう。これを、最大マージンと言います。また、これを関数マージンで考えればその超平面は最大マージン超平面と言うことができるでしょう。そして、その最大マージンは線形分離可能であれば0以上であることは誰の目にも明らかですよね。

注）ところで、前回の記事でプログラムの結果をお見せしたときに、教師の超平面と学習結果の超平面のだす答えには任意の定数倍の関係があると言いました。今回、そのことはわかりやすさを重要視して説明しておりませんが、基本的に双方が正規化されているという前提でお話しさせて頂いております。これ以降の記事でもその辺りは暗黙の了解であるとして説明致しますのでどうぞご了承下さい。