番外編２ Novikoffの定理 その2

Novikoffの定理の証明に入ります。テキストp.18-19に相当する部分をできるだけ分かりやすく説明します。ただし、テキストと異なり、Webでの文章の表記の問題と説明の都合上、ベクトル行列転置について説明せず、また、後に出てくる拡張入力ベクトルをxi’、拡張重みベクトルをwt’と表記することにします。

※このブログの性質上、正確さよりもわかりやすさを優先するためです。ご専門の方や高度な教育を受けられている方にはご不満もおありでしょうが、ご理解頂きますよう宜しくお願いします。

まず、入力ベクトルxiを1次元増やしRというデータを付け加えます。入力ベクトルはn次元のデータでしたが、このRを付け加えた新しい入力ベクトル（これをxi’としましょう）はn+1次元のベクトルとなりますよね。これを、拡張入力ベクトルと呼ぶことにします。拡張入力ベクトルは入力ベクトルxiを使って表記すると、次のように表せます。

　　　　xi’=((xi1,xi2,………,xin),R)

　　　　　(注：数学的には正確な表記でありませんが、

　　　　　　　　意味的には理解できると思われるのでこの表記にします）

同じように、重みベクトルwに関しても一次元増やし、そこにはバイアスbを取り入れ次のように拡張することにし、これを拡張重みベクトルw’と呼ぶことにします。

　　　　w’=((w1,w2,………,wn),b/R)

　　　　　(注：xi’と同様に数学的には正確な表記でありませんが、

　　　　　　　　意味的には理解できると思われるのでこの表記にします）

また、t回目の失敗により、補正された拡張重みベクトルをwt’と表わすことにします。一つ前の拡張重みベクトルはwt−1’と表わされ、これから、t回目の失敗の時に修正される値は、関数マージンの定義、

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

を用いて、次のように修正されるとします。

  wt’ =wt−1’+η|yi <w’・xi’>| (ただしηは学習率を表わす）

この修正の式の意味は、t-1回目で入力ベクトルxiで関数マージンyiが負ならば、失敗という事であるので、拡張重みベクトルを（η|yi <w’・xi’>|）分、正の方向に増やしておけば、t回目で同じ入力が入ったときに、関数マージンyiが０以上に成り、正しく分類されるだろう、ということを表わしています。拡張重みベクトルには、バイアスも含まれていますので、当然バイアスに関しても修正されます。

（注：ここでは、xi’=((xi1,xi2,………,xin),R)、w’=((w1,w2,………,wn),b/R)を使って展開して問題ないということの証明は省きます。まずは、およその流れを理解することを主眼にしたいからです。

　また、以前（パーセプトロンの学習アルゴリズムの回）に紹介したプログラムとは重みベクトルの修正の仕方が違いますが、今回の証明で使われる修正のやり方に基づいたアルゴリズムのプログラムは証明の説明が終わった後、改めて説明します。）

上記の式と、トレーニングデータの元々の超平面の拡張重みベクトルwopt’ との内積を取ると、修正されるときは、マージンyiが負の時、つまり、パーセプロンが出す答えが失敗したときで、最大マージンγがトレーニングデータの超平面とトレーニングデータの集合Ｓとの間の最も小さいマージンであった、ということを思い出して頂くとと次のような不等式が得られる事が分かると思います。

　　　　<wt’・wopt’ > = <wt-1’・wopt’ >+η|yi <xi’・wopt>|

≧  <wt-1’・wopt’ > + ηγ

≧  <wt-2’・wopt’ > + ηγ + ηγ

  ………

≧  <w1’・wopt’ > + (t-1)ηγ

≧ tηγ

　　　（2011/05/04：一行目の等式の右辺第2項が間違っていた為、

　　　　修正しました。）

   

テキストに習って、これを、[一つ目の不等式]と呼びましょう。

つぎに、[二つ目の方程式]というものを説明し、この二つを使って、最終的に修正の回数の上限が求められるのですが、ここまでやや難解で長くなったことを考慮して、証明を二度に分けて説明しようと思います。どうぞご了承下さい。

以上、次回は[二つ目の方程式]から最終的な結論までの説明となります。