3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

PRML 問題2.61 解答

Last updated at Posted at 2017-10-23

概要

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

$K$ 近傍密度モデル

PRML 2.5 節では、ノンパラメトリック法として以下の2つを紹介している:
1. カーネル密度推定法 (2.5.1 節)
2. 最近傍法 (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」
  • 参考文献

解答

$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})$ を決定する際に以下のような処理が行われる:
1. $\mathcal{x}$ の近傍の点を近い順に $K$ (定数) 個選ぶ、
2. それらが全て含まれる超球を決定する、
3. その超球の体積を $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)$ は以下のように表される 1:

\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$ 次元極座標変換を行っている 2。具体的には、 $\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 にはならないため、定数として扱うことができる 3

  1. Volume of an n-ball - Wikipedia 

  2. 極座標のヤコビ行列とヤコビアン: n次元 - 倭算数理研究所 

  3. だから多分 (3.1) = (3.2) だと思うんだけど、模範解答だと (3.1) $\geq$ (3.2) になっており、これは不明 

3
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
3
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?