概要

$K$ 近傍密度モデルで定義される密度 $p(\boldsymbol{x})$ が変則分布であることの証明を行う問題。具体的には、 $p(\boldsymbol{x})$ の全空間 $\mathbb{R}^D$ 上での積分が発散することを示す。

$K$ 近傍密度モデル

PRML 2.5 節では、ノンパラメトリック法として以下の2つを紹介している:

カーネル密度推定法 (2.5.1 節)
最近傍法 (2.5.2 節)

$K$ 近傍密度モデルは後者に該当する。前者、後者ともに、 $D$ 次元空間内のある点 $\boldsymbol{x} \in \mathbb{R}^D$ に関する確率密度は以下のように定義される:

\begin{eqnarray}
p(\boldsymbol{x}) = \frac{K}{NV}
\end{eqnarray}

ここで、式中に登場する各文字は以下のような意味をもつ：

$\mathcal{R}$: $\boldsymbol{x}$ の近傍として定義される領域
$V$ は領域 $\mathcal{R}$ の体積
$N$: 観測点の総数
$K$: 領域 $\mathcal{R}$ 内に存在する観測点の総数

カーネル密度推定法では、 $V$ を固定し $K$ をデータから推定する。つまり、 "$\boldsymbol{x}$ の近傍" は体積が $V$ であるような領域であると定義し、そこに含まれる点の個数が多ければ多いほど密度が濃くなる。
一方、最近傍法では、 $K$ を固定し $V$ をデータから推定する。つまり、 "$\boldsymbol{x}$ の近傍" は観測点が $K$ 個含まれる最小の球体（領域）であると定義し、その領域の体積が小さければ小さいほど密度が濃くなる。

問題

（基本） $K$ 近傍密度モデルでは、全空間上での積分が発散する変則分布になることを示せ。

問題の補足

（基本）
- （笑）
変則分布
- いままで「分布が正規化されていることを示せ」という問題を散々やらされてきた
  - 問題 2.1, 2.2, 2.5, 2.9 など
- 分布が正規化されている = 確率変数の定義域全域にわたる確率密度の総和もしくは積分が1になる
- 変則分布は「正規化されていない」分布
- 定数の分布もこれに該当する
  Ref. 変則事前分布 - 機械学習の「朱鷺の杜Wiki」
参考文献
- 解答の大部分は東工大 W8 PRML 読書会の演習2.61解答から

解答

$K$ 近傍密度モデル $p(\boldsymbol{x})$ は、領域 $\mathcal{R}$ の体積 $V$, $\mathcal{R}$ 内の点の総数 $K$, 観測された点の総数 $N$ を用いて以下のように表される:

\begin{eqnarray}
p(\boldsymbol{x}) = \frac{K}{NV}. \tag{PRML, 2.246}
\end{eqnarray}

(2.246) の式自体はカーネル密度推定法のそれと同様のものであるが、 $K$ 近傍密度モデルの場合は $\mathcal{x}$ に対して $p(\mathcal{x})$ を決定する際に以下のような処理が行われる:

$\mathcal{x}$ の近傍の点を近い順に $K$ (定数) 個選ぶ、
それらが全て含まれる超球を決定する、
その超球の体積を $V$ とし、 $K / NV$ を求める。
そのため、$p(\boldsymbol{x})$ は $V$ に反比例する。これより、 $\boldsymbol{x}$ の次元が $D$ であると仮定すると、以下の式が成り立つ:

\begin{eqnarray}
\frac{1}{p(\boldsymbol{x})} \propto V &\leq& \mathrm{const.} \times (\max_i ||\boldsymbol{x} - \boldsymbol{x}_i||)^D \tag{2.1} \\
&\leq& \mathrm{const.} \times (||\boldsymbol{x}|| + R)^D \tag{2.2}
\end{eqnarray}

(2.1) 式の導出の詳細および(2.2) 式の導出の詳細は本記事の末尾に示す。
さて、上式の逆数をとると、 $p(\boldsymbol{x})$ を下から押さえる以下の式を得る:

\begin{eqnarray}
p(\boldsymbol{x}) \geq \frac{\mathrm{const.}}{(||\boldsymbol{x}|| + R)^D}
\end{eqnarray}

それでは、問題の意図に添い、 $p(\boldsymbol{x})$ に関する全空間上での積分に対して上式を適用する:

\begin{eqnarray}
\int_{\mathbb{R}^D} p(\boldsymbol{x}) d\boldsymbol{x} &\geq& \int_{\mathbb{R}^D} \frac{\mathrm{const.}}{(||\boldsymbol{x}|| + R)^D} d\boldsymbol{x} \tag{3.1}\\
&=& \mathrm{const.} \int_0^\infty \frac{r ^{D - 1}}{(r + R)^D}dr \tag{3.2}
\end{eqnarray}

ここで、 (3.1) 式から (3.2) 式の変形の詳細は本記事の末尾に示す。
それでは、(3.2) 式の積分部分について注目する。 $s = r + R$ と変数変換すると、以下のように (3.2) 式の発散を示すことができる:

\begin{eqnarray}
\int_0^\infty \frac{r ^{D - 1}}{(r + R)^D}dr &\xrightarrow{s = r + R}& \int_R^\infty \frac{(s - R)^{D - 1}}{s^D}ds\\
&=& \int_R^\infty \left( \frac{1}{s} - (D - 1) \frac{R}{s^2} + \dots \right) ds\\
&=& [\ln s]_R^\infty + \underbrace{\left[ \frac{\mathrm{const.}}{s} \right]_R^\infty}_{= \ \mathrm{const.}} + \underbrace{\dots}_{= \ \mathrm{const.}}\\
&=& \ln \infty - \ln R + \mathrm{const.}\\
&=& \infty
\end{eqnarray}

以上より、$K$ 近傍密度モデルの密度関数 $p(\boldsymbol{x})$ に関する全空間上での積分は発散する。すなわち、$K$ 近傍密度モデルは変則分布であることが示された。

(2.1) の詳細

証明したいこと

\begin{eqnarray}
V &\leq& \mathrm{const.} \times (\max_i ||\boldsymbol{x} - \boldsymbol{x}_i||)^D
\end{eqnarray}

証明

半径 $r$ の $D$ 次元ユークリッド球面の体積 $V_D(r)$ は以下のように表される ¹:

\begin{eqnarray}
V_D(r) = \frac{\pi^{\frac{D}{2}}}{\Gamma(\frac{D}{2} + 1)} r^D
\end{eqnarray}

これより、 $D$ が固定されたとき、 $V_D(r)$ は $r^D$ に比例する。
半径 $r$ は中心 $\boldsymbol{x}$ から最も遠い点との距離より必ず小さいため、 $r \leq \max_i ||\boldsymbol{x} - \boldsymbol{x}_i ||$ が成立する。
よって、次式が成り立つ:

\begin{eqnarray}
V_D(r) &=& \frac{\pi^{\frac{D}{2}}}{\Gamma(\frac{D}{2} + 1)} r^D \\
&\leq& \mathrm{const.} (\max_i ||\boldsymbol{x} - \boldsymbol{x}_i||)^D
\end{eqnarray}

なお、$K$ = $N$ のとき等号が成立する。

(2.2) の詳細

証明したいこと

\begin{eqnarray}
\mathrm{const.} \times (\max_i ||\boldsymbol{x} - \boldsymbol{x}_i||)^D \leq \mathrm{const.} \times (||\boldsymbol{x}|| + R)^D
\end{eqnarray}

証明

あるデータ点 $\boldsymbol{x}_i$ について考える。

\begin{eqnarray}
R = \max_i (||\boldsymbol{x}_i||)
\end{eqnarray}

とおく。$R$ は今回対象とする全てのデータ点 $ \boldsymbol{x}_i $, $i = 1, \dots, N$ のうち、最も原点から離れている点である。「原点から離れている」ことは問題を解く上では重要ではないが、$R$ が定数であることには注意しておく。
三角不等式より、点 $\boldsymbol{x}$ と点 $\boldsymbol{x}_i$ の間のユークリッド距離 $|| \boldsymbol{x} - \boldsymbol{x}_i ||$ は以下のように上から押さえられる:

\begin{eqnarray}
|| \boldsymbol{x} - \boldsymbol{x}_i || \leq || \boldsymbol{x} || + || \boldsymbol{x}_i || \leq ||\boldsymbol{x}|| + R \tag{1}
\end{eqnarray}

(3.1) から (3.2) の詳細

証明したいこと

\begin{eqnarray}
\int_{\mathbb{R}^D} \frac{\mathrm{const.}}{(||\boldsymbol{x}|| + R)^D} d\boldsymbol{x} = \mathrm{const.} \int_0^\infty \frac{r ^{D - 1}}{(r + R)^D}dr
\end{eqnarray}

証明

(3.1) 式から (3.2) 式の変形においては、 $D$ 次元極座標変換を行っている ²。具体的には、 $\boldsymbol{x} = ( x_1, x_2, \dots, x_D )^T \in \mathbb{R}^D$ を以下のように変換する:

\begin{eqnarray}
\left\{
\begin{array}{l}
x_1 &=& r\cos\theta_1\\
x_2 &=& r\sin\theta_1 \cos\theta_2\\
x_3 &=& r\sin\theta_1 \sin\theta_2 \cos\theta_3\\
&\vdots&\\
x_{D-2} &=& r\sin\theta_1 \sin\theta_2 \sin\theta_3 \dots \sin\theta_{D-3} \cos\theta_{D-2}\\
x_{D-1} &=& r\sin\theta_1 \sin\theta_2 \sin\theta_3 \dots \sin\theta_{D-3} \sin\theta_{D-2} \cos\theta_{D-1}\\
x_D &=& r\sin\theta_1 \sin\theta_2 \sin\theta_3 \dots \sin\theta_{D-3}  \sin\theta_{D-2} \sin\theta_{D-1}
\end{array}
\right.
\end{eqnarray}

ただし、

\begin{eqnarray}
\begin{array}{c}
0 \leq r < \infty \\
0 \leq \theta_i \leq \pi \ \ (i = 1, 2, \dots, D - 2) \\
0 \leq \theta_{D-1} \leq 2\pi
\end{array}
\end{eqnarray}

である。積分の変数変換の際には、積分変数に対する以下の関係が成り立つことに注意する:

\begin{eqnarray}
d\boldsymbol{x} = d x_1 d x_2 \dots d x_D &=& r^{D - 1} \left\{ \prod_{i=1}^{D-1} (\sin \theta_i)^{D - i - 1} \right\} dr d\theta_1 \dots d\theta_{D - 1} \\
&=& r^{D - 1} (\sin \theta_1)^{D - 2} (\sin \theta_2)^{D - 3} \dots (\sin \theta_{D - 2})^{1} (\sin \theta_{D - 1})^{0} dr d\theta_1 \dots d\theta_{D - 1}
\end{eqnarray}

それでは、実際に変数変換を行う。

\begin{eqnarray}
\int_{\mathbb{R}^D} \frac{\mathrm{const.}}{(||\boldsymbol{x}|| + R)^D} d\boldsymbol{x} &=& \int\dots\int \frac{\mathrm{const.}}{(r + R)^D} r^{D - 1} \left\{ \prod_{i=1}^{D-1} (\sin \theta_i)^{D - i - 1} \right\} dr d\theta_1 \dots d\theta_{D - 1}\\
&=& \mathrm{const.} \int_0^\infty \frac{r ^{D - 1}}{(r + R)^D}dr \underbrace{\int_0^{\pi} (\sin \theta_1)^{D - 2} d\theta_1}_{\mathrm{const.}} \dots \underbrace{\int_0^{\pi} (\sin \theta_{D - 2})^{1} d\theta_{D - 2}}_{\mathrm{const.}} \underbrace{\int_0^{2\pi} (\sin \theta_{D - 1})^{0} d\theta_{D - 1}}_{\mathrm{const.}} \\
&=& \mathrm{const.} \int_0^\infty \frac{r ^{D - 1}}{(r + R)^D}dr
\end{eqnarray}

ここで、変形に際しては、以下の点に注意する:

$\boldsymbol{x}$ の原点からの距離 $||\boldsymbol{x}||$ は、変数変換を行うと $||\boldsymbol{x}|| = x_1^2 + x_2^2 + \dots + x_D^2 = r$ となる。
変数変換後の被積分関数 $\frac{r ^{D - 1}}{(r + R)^D}$ は $\theta_i$ に依存しないため、 $\theta_i$ に関連する値は別の積分としてくくり出せる。また、これらの値は 0 にはならないため、定数として扱うことができる ³。