【はじめてのパターン認識】第5章 k最近傍法

はじめてのパターン認識を読んでいる。
その個人的メモ。

はじめてのパターン認識

漸近仮定とkNN誤り率の期待値

2クラス問題を考える。
条件付きベイズ誤り率は、事後確率の小さい方 $$ \epsilon (x) = \min{ [ P(C_1|x), P(C_2|x) ]} $$ である。
ベイズ誤り率は、その期待値が $$ \epsilon \ast = \int \epsilon (x) p (x) dx $$ で表される。
入力の最近傍鋳型をとする。
N個の鋳型の集合をとする。
このとき以下の漸近仮定が成り立てば、 $$ \lim_{N \to \inf} T_{N} \Rightarrow d(x, x_{1NN}) \to 0 $$ kNN誤り率とベイズ誤り率の間には、次の関係が成り立つ。 $$ \frac{1}{2} \epsilon \ast \geq \epsilon_{2NN} \geq \epsilon_{4NN} \geq \cdots \geq \epsilon \ast \geq \cdots \geq \epsilon_{3NN} \geq \epsilon_{1NN} \geq \epsilon_{1NN} \geq 2 \epsilon \ast $$

教科書にはこの証明が載っていてかなり面白い。