番外編２ Novikoffの定理 その１

番外編２　Novikoffの定理　その１

線型分離可能であるようなトレーニングデータがパーセプトロンの学習段階でどれくらいの失敗（言い換えれば、重みとバイアスを書き換える）回数があるかということを示すNovikoffの定理を今回と次回に分けて説明します。今回は定理の説明だけを簡単にして、次回は、証明を説明しようかと思います。証明はどうしても長くなりがちなので2回に分けることにしました。そのあと、この定理の証明で行われているようにあらためて、パーセプトロンの学習方法のプログラムを若干修正して、そのときにうまく学習できているかどうかを示します。

ネットでちょっと調べると、収束定理と言っているサイトもあります。その名の通り、トレーニングデータが線型分離可能であるならば、パーセプトロンの学習はNovikoffの定理で示されるように必ず収束することが保証されている、と考えることもできます。

それでは、実際の定理を見てみましょう。

（注：図が小さい場合は、図をクリックすると拡大されます）

まず出てくるRですがこれは、原点を中心にトレーイングデータの集合Sのばらつきをみて、最も離れている入力データの距離としています。woptは正規化されたトレーニングデータの超平面と考えて良いでしょう。トレーニングデータの超平面とそれに最も近いトレーニングデータまでの距離である最大マージンをγとしたときに、パーセプトロンの学習は2Rとγとの比の2乗の失敗の回数以内に収束する、という言い方で、言い換えられるのがこの定理です。

それでは、次回は、証明です。