kNNとベイズ誤り確率

この記事は古川研究室 Workout_calendar 21日目の記事です．
本記事は古川研究室の学生が学習の一環として書いたものです．内容が曖昧であったり表現が多少異なったりする場合があります．

はじめに

前回はkNNについてこちらで記事にしました．

kNNについて勉強していたところ，$k=1$の場合のkNN，通常の最近傍法（以下NN）の説明として，その誤り率の上限と下限がベイズ誤り確率によって決められるという説明を目にしました[1]．そちらの文献の式を追うとともに，理解の過程としてこの章で紹介させていただきます．

ベイズ誤り確率とは

本記事で登場する「誤り確率」という言葉は，一貫して「分類器が分類を誤る確率」のことをいいます．

ベイズ誤り確率とは，データの特徴そのものの不完全さに起因する「必然的な誤り」であり，特徴空間上での「分布の重なりの度合い」と解釈することのできる誤り確率のことです．

参考資料[1]にて，ベイズ誤り確率のわかりやすい説明がありました．以下に要約してご紹介します．

目の前にいる人物が男性か女性を機械で自動判定する場合，特徴量として身長や体重，髪の毛の長さなどの特徴を抽出することができれば，ある程度の性別の判定が可能である．しかし，平均的な身長や体重は男性のほうが女性よりも大きいという傾向はあるものの，個々を見たときに必ずしも傾向に当てはまらないケースはたくさんある．平均的な男性の身長より高身長な女性もいるし，その逆に平均的な女性の体重よりも軽量な男性もいる．そのため，これらの特徴量によって性別を誤りなく判定することは不可能である．

上の図は特徴量によってクラスが一意に決められないことをイメージできるように作成しました．身長における$171$は男性平均，$157$は女性平均を表し，体重における$68$は男性平均，$51$は女性平均を表しています．全体として，各クラスはその平均あたりにサンプルが集中しますが，そうではないケースもあるということをわかっていただければ幸いです．

特徴量の傾向による判定の誤りは，男性と女性の特徴量の分布が重なり合っていることが原因であると言えます．そもそも判定の誤りが必ず生じるような特徴ということです．これは，特徴量が持っている本質的な不完全さであり，ベイズ誤り確率とは，特徴そのものの不完全さに起因する必然的な誤りといえます．

ベイズ誤り確率の定式化

この章では，前章で述べたベイズ誤り確率を，2クラス分類において式で表現します．

既知の確率

2つのクラス $C_1$（男），$C_2$（女） があり，それぞれの生起確率が $P(C_1)$，$P(C_2)$ であるとします．

$$
P(C_1) + P(C_2) = 1 \tag{1}
$$

分類対象としているデータはすべて，以下の確率密度関数に基づいて生起していると仮定します．

$$
p(\boldsymbol x | C_i) \quad (i=1,2) \tag{2}
$$

$p(\boldsymbol x | C_i)$ は，クラス $C_i$ に属する $\boldsymbol x$ が生起する確率を表しています．

この節で登場した確率は全て，過去の観測経験にもとづいて予測されたものであり，既知なものとして具体的な値を得られると仮定します．

既知の確率より導出される確率

$(2)$ 式をクラスについて周辺化することで， 周辺確率 $p(\boldsymbol x)$ を得ることができます．

$$
p(\boldsymbol{x}) = p(\boldsymbol{x}|C_1)P(C_1) + p(\boldsymbol{x}|C_2)P(C_2) \tag{3}
$$

$(3)$ 式は，所属クラスに関わらず $\boldsymbol x$ が生起する確率を表しています．

また，ベイズの定理より以下の等式が得られます．

$$
P(C_1|\boldsymbol{x}) = \frac{p(\boldsymbol{x}|C_1)P(C_1)}{p(\boldsymbol{x})} \tag{4}
$$

$$
P(C_2|\boldsymbol{x}) = \frac{p(\boldsymbol{x}|C_2)P(C_2)}{p(\boldsymbol{x})} \tag{5}
$$

$(4)$ 式と $(5)$ 式は，観測された $\boldsymbol x$ がクラス $C_1$，$C_2$に属する確率（事後確率）を表しています．

$$
P(C_1|\boldsymbol{x}) + P(C_2|\boldsymbol{x}) = 1 \tag{6}
$$

この節で登場した3つの確率は，既知の確率から導出されたものであり，観測から直接得られるものではありません．

2クラス分類器のベイズ誤り確率

観測サンプル $\boldsymbol x$ を引数として受け取り，そのサンプルのクラスラベルを出力するクラス分類器 $f()$ が手元にあるとします．

$$
f(\boldsymbol x) = C_i \quad (i=1,2)
$$

観測されたクラス未知のサンプル $\boldsymbol{x}$ に対し，分類器 $f()$ を用いてクラス判別を行うと，分布の重なりに起因する分類器の分類誤り確率 $P(\varepsilon=1|f,\boldsymbol x)$ は以下のようになります．

$$
P(\varepsilon=1|f,\boldsymbol x) = \begin{cases}
P(C_2|\boldsymbol{x}) \quad \mbox{if} \quad f(\boldsymbol x) = C_1 \tag{7} \
P(C_1|\boldsymbol{x}) \quad \mbox{if} \quad f(\boldsymbol x) = C_2 \
\end{cases}
$$

ただし，$\varepsilon={0, 1}$ は分類器が分類を誤ったかどうかを表す事象です．分類を誤った場合は $\varepsilon = 1$ ，分類を誤ってない場合は $\varepsilon=0$ の値をとります．

観測されうるすべての $\boldsymbol{x}$ に対する分類器 $f()$ の誤り確率 $P_e(\varepsilon=1|f)$ は，各 $\boldsymbol{x}$ の生起確率 $p(\boldsymbol x)$ とその $\boldsymbol x$ に対する分類器 $f()$ の誤り確率 $P_e(\varepsilon=1|f,\boldsymbol{x})$ との積を，$\boldsymbol{x}$ で積分することで求まります（$\boldsymbol x$ についての周辺化）．

\begin{align}
P(\varepsilon=1|f) &= \int{P(\varepsilon=1, \boldsymbol x|f)}{d\boldsymbol{x}} \tag{8} \\
&= \int{P(\varepsilon=1|f,\boldsymbol x)p(\boldsymbol{x})}{d\boldsymbol{x}} \tag{9}
\end{align}

$P(\varepsilon=1|f)$ を最小化するには，$(9)$ 式における $P(\varepsilon=1|f,\boldsymbol x)$ として $P(C_1|\boldsymbol{x})$，$P(C_2|\boldsymbol{x})$ の小さい方が選ばれるように，分類器 $f()$ のクラス判別ルールを以下のようにします．

$$
f(\boldsymbol x) = \begin{cases}
C_1 \quad \mbox{if} \quad P(C_1|\boldsymbol{x}) > P(C_2|\boldsymbol{x}) \tag{10} \
C_2 \quad \mbox{if} \quad P(C_2|\boldsymbol{x}) > P(C_1|\boldsymbol{x}) \
\end{cases}
$$

これは結果として，クラス判別における事後確率 $P(C_i|\boldsymbol{x})\quad(i=1,2)$ を最大化する $C_i$ を判別結果として出力する判別方法であり，このような判別方法をベイズ決定測と呼ぶそうです．

$(9)$ のルールに従う $f()$ を使い，最小化した $P(\varepsilon=1|f, \boldsymbol x)$ を $e_B(\varepsilon=1|f, \boldsymbol x)$ で表すと以下のようになります．

$$
e_B(\varepsilon=1|f, \boldsymbol x)=\min_{f}P(\varepsilon=1|f, \boldsymbol x) = \min_{i}{P(C_i|\boldsymbol{x})}_{i=1}^2 \tag{11}
$$

この $e_B(\varepsilon=1|f, \boldsymbol x)$ を条件付きベイズ誤り確率といいいます．
ここでいう条件とは，$\boldsymbol x$ が観測されたという事象のことをいいます．
$\boldsymbol x$ が観測された，という条件のもとで $\boldsymbol x$ に対するクラス判別の誤り確率を最小に抑えたものが $(11)$ 式です．

$(6)$式と$(7)$式より，最小の $P_e(\varepsilon=1|f)$ を $e_B(\varepsilon=1|f)$ で表すと以下のようになります．

\begin{align}
e_B(\varepsilon=1|f) &= \min_{f}P(\varepsilon=1|f) \\ &= 
\int{e_B(\varepsilon=1|f, \boldsymbol{x})p(\boldsymbol{x})d\boldsymbol{x}} \\ &=
\int{\min_{f}P(\varepsilon=1|f,\boldsymbol x)p(\boldsymbol{x})}{d\boldsymbol{x}} \\ &=
\int{\min_{i}\{P(C_i|\boldsymbol{x})\}_{i=1}^2p(\boldsymbol{x})d\boldsymbol{x}} \tag{12}
\end{align}

この $e_B(\varepsilon=1|f)$ こそベイズ誤り確率です．

ベイズ誤り確率 $e_B(\varepsilon=1|f)$ は $(9)$ 式において常に $P_e(\varepsilon=1|f,\boldsymbol{x})$ の最小値を選んでいるため，これ以上小さくすることはできません．$e_B$ は分布の重なりによる必然的な誤りを最小に抑えたものとなっています．

以上で，2クラス分類におけるベイズ誤り確率 $e_B(\varepsilon=1|f)$ を定式化することができました．

ベイズ誤り確率と最近傍法の誤り確率

ベイズ誤り確率について紹介したところで，本題のベイズ誤り率とNNの関係について述べていきます．

クラス未知の観測サンプルのクラスを予め所属クラスの分かっている $n$ 個のサンプルに基づいてNNによって決めることを考えます．
まず，所属クラスが既知のサンプルを $n$ 個用意します．

$$
D = {\boldsymbol x_1,...,\boldsymbol x_n}
$$

観測データ $\boldsymbol{x}$ に対する最近傍サンプルを $\boldsymbol{x}'$ で表すと，$\boldsymbol{x}'$ は必ず $D$ の中から選ばれるので

$$
\boldsymbol{x}' \in D
$$

となります．

NNにおいては，観測データとその最近傍サンプルの所属クラスが異なる場合に分類の誤りが発生します．なので，$n$ 個のサンプルを用いたNNで観測データ $\boldsymbol{x}$ のクラスを判別したとき，識別を誤る確率 $e_n(\boldsymbol{x})$ は

$$
e_n(\boldsymbol{x}) = P(C_1|\boldsymbol{x})P(C_2|\boldsymbol{x}') + P(C_2|\boldsymbol{x})P(C_1|\boldsymbol{x}') \tag{12}
$$

となります．

ここで重要な仮定を導入します．サンプル数を無限大に近づけていくと，観測データ $\boldsymbol{x}$ の最近傍サンプル $\boldsymbol{x}'$ は $\boldsymbol{x}$ に限りなく近づくという仮定です．

観測空間において，隙間なくぎっしりとサンプルが分布しており，どの点でクラス未知のデータが観測されたとしても，かならず同じ位置にクラス既知のサンプルがあるイメージです．

これを式で表すと以下のようになります．

$$
\lim_{n\rightarrow\infty} \boldsymbol{x}' = \boldsymbol{x} \tag{13}
$$

$(12)$式から，以下の等式が成り立ちます．

$$
\lim_{n\rightarrow\infty} P(C_i|\boldsymbol{x}') = P(C_i|\boldsymbol{x})\quad (i=1, 2) \tag{14}
$$

これは，特徴空間においてサンプル数を膨大な数用意するとき，観測データとその最近傍サンプルが，あるクラス$C_i$に属する確率が等しいことを意味します．

そして，$(11)$ 式と $(13)$ 式より，以下の式が得られます．

\begin{align}
\lim_{n\rightarrow\infty} e_n(\boldsymbol{x})  &= 2P(C_1|\boldsymbol{x})P(C_2|\boldsymbol{x}) \tag{15} \\ &=
2P(C_1|\boldsymbol{x})(1-P(C_1|\boldsymbol{x})) \tag{16} \\ &=
2P(C_2|\boldsymbol{x})(1-P(C_2|\boldsymbol{x})) \tag{17} 
\end{align}

ここで，前節で説明した条件付きベイズ誤り確率を使います．
条件付きベイズ誤り確率は以下のような式でした．

$$
e_B(\boldsymbol{x})=\mbox{min}P(\boldsymbol{x}) = \mbox{min}{P(C_1|\boldsymbol{x}),P(C_2|\boldsymbol{x})}
$$

$(14)$式における$P(C_1|\boldsymbol{x})$と$P(C_2|\boldsymbol{x})$のどちらを$e_B(\boldsymbol{x})$としても，結果的に得られる式は変わらず，以下のようになります．

$$
\lim_{n\rightarrow\infty} e_n(\boldsymbol{x}) = 2e_B(\boldsymbol{x})(1-e_B(\boldsymbol{x})) \tag{18}
$$

そして，条件付きベイズ誤り確率を導入したので，考えうるすべての観測データ$\boldsymbol{x}$に対するNN法の分類誤り確率を求めることができます．以下のようになります．

$$
\begin{align}
e_N &= \lim_{n\rightarrow\infty}e_n \ &=
\int (\lim_{n\rightarrow\infty}e_n(\boldsymbol{x}))p(\boldsymbol{x})d\boldsymbol{x} \ &=
\int 2e_B(\boldsymbol x)(1-e_B(\boldsymbol x))p(\boldsymbol x)d\boldsymbol x \ &=
2e_B(1-e_B)-2\cdot\mbox{Var}(e_B(\boldsymbol x)) \ &\leq
2e_B(1-e_B)
\end{align}
$$

更に，$e_N$ について以下も成り立ちます．

$$
\begin{align}
e_N &= \lim_{n\rightarrow\infty}e_n \ &=
\int 2e_B(\boldsymbol x)(1-e_B(\boldsymbol x))p(\boldsymbol x)d\boldsymbol x \ &=
\int {e_B(\boldsymbol x)+e_B(\boldsymbol x)(1-2e_B(\boldsymbol x))}p(\boldsymbol x)d\boldsymbol x \ &=
e_B + \int e_B(\boldsymbol x)(1-2e_B(\boldsymbol x))p(\boldsymbol x)d\boldsymbol x \ &\geq
e_B
\end{align}
$$

以上の式をまとめると以下のようになります．

$$
e_B \leq e_N \leq 2e_B(1-e_B) \leq 2e_B \tag{19}
$$

$(19)$ 式が意味しているのは，NNによる2クラス分類において，分類の誤り確率の下限はベイズ誤り確率であり，上限はベイズ誤り確率の2倍以下であるということです．

おわりに

今回はkNNとベイズ誤り確率の関係について記事にしました．
シンプルなアルゴリズムのkNNですが、勉強してみると面白く、ためになる部分が多々ありました。
ベイズ誤り確率の導入部分について、初めて知った時は少し楽しくなりました。「分布の重なりに起因する避けられない分類の誤り」ってなんだかかっこいいですよね。

今回の記事を通して、確率を含んだ数式に対する苦手意識が少し薄れたので、引き続き勉強に取り組んでいきたいと思います。

参考資料

[1] わかりやすいパターン認識．石井健一郎，上田修功，前田英作，村瀬洋