番外編２ Novikoffの定理 その3

Novikoffの定理の証明の２回目です。

今回は、テキストで言う[二つ目の不等式]の説明をします。

さて、まず、ノルムという概念を説明しましょう。これは、数学の専門用語で、簡単に言ってしまえば、以前説明した距離（ユークリッド距離）と同じ意味です。距離は次のように定義されているのでしたね。

ベクトルの大きさと思ってもらえば結構です。わざわざノルムと言い換える理由は良く分かりませんが、数学は抽象化を目的とした学問でもあるので、より抽象化された言い方になっているのだと思います。

さて、下の不等式では、ノルムの二乗が使われていますが、二乗をすると、ノルムの定義式からルートが取れますよね。あと、二乗されると、その式の符号が必ず正になります。そのような意味もあって二乗が使われているのだと理解して下さい。（数式の図が小さいときはクリックで拡大します）

これら二つの不等式を使うと、下のような不等式が出てきます。少し見にくいですが、解説も数式の図に書いています（Webでの表記上の問題です）。ちなみに下の不等式の第一項と第二項の関係は[二つ目の不等式]を、まず一つ目と同様にt回演繹した不等式を作り、そのあとその両端を平方根を取った関係です。

この不等式はその両端の項の関係とwt、woptを正規化したベクトルであるとしたことから、失敗の回tの上限が次のような不等式で表せることを示唆しています。

       

これは、すでに書いているようにwoptが正規化したベクトルであること、拡張した時に付け加えられる新たな次元の数bopt/R≦1であることを利用しています。つまり

‖w’opt‖‖w’opt‖≦‖wopt‖‖wopt‖+1≦２

となることを利用しています。

以上、証明終わり