この記事のポイント
ノンパラメトリックなアプローチってなんだろう、というところからヒストグラム、カーネル推定、K近傍法、などをみていき、結局いい感じの密度モデルを得るのって難しいねっていうオチの記事
データ解析において一般的なのは、パラメータを事前に設定しデータを用いてそのパラメータを最適化していくという方法である。
しかし、実際にはそれだけでなく、パラメータに依存しない方法も存在する。それがノンパラメトリックな方法である。
今回の記事では、ヒストグラム密度推定法から始めて、カーネル密度推定法、そして最後にK近傍法まで、ノンパラメトリックな手法を用いたデータ解析の流れを、丁寧に段階的に解説していく。
ノンパラメトリックなアプローチってなに???
まずは、ノンパラメトリックなアプローチについて考える前に、パラメトリックなアプローチについて解説しよう。
このアプローチは、我々が取り扱う確率分布を特定の形式（ガウス分布やベルヌーイ分布など）でモデル化し、その分布のパラメータをデータから推定するものだ。例えば、ガウス分布（正規分布）はこのパラメトリックなアプローチにおける代表的な例で、平均と分散という二つのパラメータを用いて形状が決まる。
つまり、最初に仮定した確率分布の形式とそのパラメータが、全てのデータを説明するという考え方に基づいている。具体的な例としては、身長のデータがガウス分布に従うと仮定し、その平均値と標準偏差（パラメータ）をデータから推定するケースを挙げられる。
しかし、このパラメトリックなアプローチには欠点も存在する。それは、最初に選んだ確率分布がデータの本当の分布をうまく捉えられない場合だ。
例えば、身長のデータが男性と女性の2つの集団からなるようなケースを考えてみよう。全体として見るとデータは2つのピークを持つ多峰性の分布を持つが、ガウス分布（単峰性）でこれを表現することは難しい。つまり、選択したモデルがデータを生成した現象を十分に表現できない場合、パラメトリックなアプローチは有効でないという事実がある。
ここでノンパラメトリックなアプローチが登場する。この手法は、確率分布の形式をあらかじめ決めずにデータから推定するというものだ。
具体的には、データが増えるにつれてモデルの複雑さも増すような方法を指す。つまり、データが複雑な現象や未知の分布を表していても、データから直接その分布を学習しようとする。
ベイズ的なアプローチも存在するが、この記事で紹介するノンパラメトリックな手法は頻度主義的なものである。
ヒストグラム密度推定法
ヒストグラム法はノンパラメトリックな確率密度推定法の一つだ。そのアイディアは単純で、データをいくつかの区間（ビン）に分割し、各区間に含まれるデータ点の数を数え上げる。そして、それぞれの区間での確率密度を計算する。
ヒストグラム法の確率密度
ヒストグラム法における各区間 \( i \) の確率密度 \( p_i \) は、区間 \( i \) に含まれるデータ点の数 \( n_i \)、全データ点の数 \( N \)、そして区間の幅 \( \Delta_i \) を用いて次のように定義される：
$$ p_i = \frac{n_i}{N \Delta_i} $$
この定義から以下のように規格化されている
$$ \int p(x) dx = 1 $$
積分は面積の計算と考えることができる。したがって、全区間にわたる積分は、各区間での「高さ × 幅」（つまり面積）をすべて足し上げたものと考えることができる。この観点から上記の積分を各区間で考えると、
$$ \int p(x) dx = \sum_i \int_{\text{区間} \ i} p(x) dx = \sum_i p_i \Delta_i = \sum_i \frac{n_i}{N} = 1 $$
となる。
ヒストグラム法の利点
この方法は非常に直観的で理解しやすい。データが与えられると、その分布形状を容易に視覚化できる。また、区間の数（つまり区間の幅）を変えることで、大まかな分布形状から細かい形状まで、異なる粒度での分布を見ることができる。
ヒストグラム法の弱点
ヒストグラム法の弱点
- 区間の幅に大きく結果が左右される
- 次元の呪い
最大の欠点は、区間の幅の選択により結果が大きく変わってしまうことだ。区間の幅が大きすぎると、データの細かな特徴を捉えられず、小さすぎるとノイズまで捉えてしまい、結果として過学習（overfitting）が起きる可能性がある。
上の三つのヒストグラム密度推定したグラフを見てほしい、緑の線がデータの生成元となった分布である。区間の幅\(\Delta\)が小さいと得られた密度モデルはトゲトゲ状になり、データ集合を生成したものとの分布には存在しないことがわかり、逆に\(\Delta\)が大きすぎると、結果のモデルはなだらかになり過ぎて、二峰性を捉えられていない。
つまり\(\Delta\)の値は大きすぎても小さすぎてもいけない。
さらに、ヒストグラム法は「次元の呪い」（curse of dimensionality）という問題を抱えている。
ヒストグラム法ではデータを扱うために区間を設けるが、D次元の空間をそれぞれM個の区間に分割すると、区間の数はMのD乗になる。つまり、変数の数が増えると、区間の数も爆発的に増加する。このように、データの次元数が増えると（つまり変数の数が増えると）、必要な計算量やメモリ量が急速に増大する現象を「次元の呪い」という。
例えば、2次元のデータ（つまり2つの変数を持つデータ）をそれぞれ10個の区間に分割すると、必要な区間の数は \(10^2 = 100\) 個となる。しかし、10次元のデータをそれぞれ10個の区間に分割すると、必要な区間の数は \(10^{10}\) 個、つまり100億個にもなる。
また、この問題は計算量だけでなく、データの「密度」にも関わる。次元が増えると、各区間に含まれるデータの数が急速に減少する。つまり、高次元の空間ではデータが非常に「希薄」になり、それぞれの区間にデータがほとんど含まれないという状況が生じる可能性がある。これは、高次元のデータに対してヒストグラム法を直接適用すると、信頼性の低い推定結果を得る可能性があるという問題を示している。
カーネル密度推定法
単純なヒストグラムでは先ほど見たように、次元数の増加に対応しにくいということを見た。
では、ここからは次元数の増加に対応できる二つのノンパラメトリック手法の一つカーネル推定法を見ていく
まず、確率密度関数\( p(\mathbf{x}) \)の領域\( \mathcal{R} \)における積分を考えよう。これは、領域\( \mathcal{R} \)内にデータが存在する確率\( P \)と等しくなる。つまり、 $$ P=\int_{\mathcal{R}} p(\mathbf{x}) \mathrm{d} \mathbf{x} . $$
次に、全データ点の数を\( N \)、領域\( \mathcal{R} \)内に存在するデータ点の数を\( K \)とする。データ点がどの領域に存在するかはランダムな過程であり、その結果の分布は二項分布に従う。つまり、
$$
Bin(K \mid N, P)=\frac{N !}{K !(N-K) !} P^K(1-P)^{1-K} .
$$
二項分布の平均は\( NP \)で、平均まわりの分散は\( P(1-P)/N \)である。データ点の総数\( N \)が大きくなると、二項分布は平均値\( NP \)を中心に鋭く尖った形状になる。つまり、最も確からしいデータ点の数は平均値、すなわち\( NP \)に非常に近くなる。このため、
$$
K \simeq N P
$$
と近似できる。ここで「\( \simeq \)」は近似を表す
近似 \( K \simeq NP \) について考えてみよう。ここで \( K \) は領域 \( \mathcal{R} \) 内に存在するデータ点の数、\( N \) は全データ点の数、\( P \) は領域 \( \mathcal{R} \) にデータ点が存在する確率を表す。\( P \) は領域 \( \mathcal{R} \) に割り当てられた確率で、したがって、全データ点数 \( N \) のうち、大体 \( NP \) の数だけが領域 \( \mathcal{R} \) 内に存在すると期待される。だから、\( K \) は \( NP \) に「近い」（つまり \( K \simeq NP \) ）という理解ができる。
さらに、領域\( \mathcal{R} \)が十分に小さければ、確率密度関数\( p(\mathbf{x}) \)はその領域内でほぼ一定であるとみなせる。したがって、領域\( \mathcal{R} \)内の確率\( P \)は確率密度関数\( p(\mathbf{x}) \)と領域\( \mathcal{R} \)の体積\( V \)の積とほぼ等しくなる。つまり、
$$
P \simeq p(\mathbf{x}) V
$$
と近似できる。
\( P \simeq p(\mathbf{x})V \) の近似について考えてみよう。確率密度関数 \( p(\mathbf{x}) \) は、データ点が特定の値 \( \mathbf{x} \) をとる確率を表す。しかし、実際には、データ点が厳密に特定の値 \( \mathbf{x} \) をとる確率は非常に低い（ほぼゼロ）。したがって、実際の問題では、特定の値 \( \mathbf{x} \) の周辺の小さな領域 \( \mathcal{R} \) を考え、その領域内にデータ点が存在する確率 \( P \) を計算する。
以上の\( K \simeq NP \)と\( P \simeq p(\mathbf{x}) V \)を組み合わせると、次のような確率密度の推定式を得る。
確率密度の推定式
$$ p(\mathbf{x})=\frac{K}{N V} $$
ここで、\( K \)は領域\( \mathcal{R} \)内に存在するデータ点の数、\( N \)は全データ点の数、\( V \)は領域\( \mathcal{R} \)の体積を表す。これが、密度推定の基本的な考え方である。
さて、\( p(\mathbf{x})=\frac{K}{N V} \)には二通りの使い方があって、一つは\(K\)を固定して、データから\(V\)の値を推定するものでこれをK近傍法という。
もう一つは、\(V\)を固定して\(K\)の値をデータから推測するもので、これをカーネル推定法という。
Parzen推定法
ここで使われるカーネル関数とは、あるデータ点が密度を推定したい領域内に存在するかどうかを示す指標で、今回はParzen窓とも呼ばれるカーネル関数を使用する。
Parzen窓は、\( k(\mathbf{u}) \)として以下のように定義される。
Parzen推定のカーネル関数(Parzen窓)
$$ k(\mathbf{u})= \begin{cases}1, & \left|u_i\right| \leq 1 / 2, \quad i=1, \ldots, D \\ 0, & \text { otherwise }\end{cases} $$
ここで、\( \mathbf{u} = (\mathbf{x}-\mathbf{x}_n)/h \)として定義し、すべてのデータ点についてこれを計算する。つまり、\( \mathbf{x} \)を中心とする一辺\( h \)の立方体（\( D \)次元の場合）の内部に存在するデータ点の数\( K \)は次のように表される。
$$ K=\sum_{n=1}^N k\left(\frac{\mathbf{x}-\mathbf{x}_n}{h}\right) $$
この\( K \)を使うと、先程のヒストグラム密度推定と同様に確率密度\( p(\mathbf{x}) \)の推定値を求めることができる。
$$ p(\mathbf{x})=\frac{1}{N} \sum_{n=1}^N \frac{1}{h^D} k\left(\frac{\mathbf{x}-\mathbf{x}_n}{h}\right) $$
しかし、この方法にもヒストグラム密度推定法と同じ問題がある。それは、立方体の縁で人為的な不連続が生じてしまうという点である。
ガウスカーネルを使った推定
それを解決するべく、カーネル関数に滑らかなものを選べば、より滑らかな密度モデルが得られる。
そもそも、カーネル関数\( k(\mathbf{u}) \)は以下の条件がある。
$$
\begin{aligned}
k(\mathbf{u}) & \geq 0 \\
\int k(\mathbf{u}) \mathrm{d} \mathbf{u} & =1
\end{aligned}
$$
これを満たしかつ、滑らかで、よく使われる選択はガウスカーネル関数である。
ガウスカーネル関数は、名前が示す通り、正規分布（ガウス分布）を形状に持つ。そのため、その形状は中心から離れるにつれて滑らかに減衰し、これが高次元でも良い性質を保つために広く用いられる。
ガウスカーネル密度推定は、各データ点の位置にガウスカーネルを置き、その和をとることで全体のデータの分布を推定する方法だ。つまり、各データ点はその位置を中心とするガウス分布として扱われ、それらを全て足し合わせることで確率密度関数が得られる。これが以下の式で表される。
$$
p(\mathbf{x})=\frac{1}{N} \sum_{n=1}^N \frac{1}{\left(2 \pi h^2\right)^{1 / 2}} \exp \left\{-\frac{\left\|\mathbf{x}-\mathbf{x}_n\right\|^2}{2 h^2}\right\}
$$
ここで、\( h \)はバンド幅と呼ばれ、各ガウスカーネルの広がりを調整するパラメータだ。この値が大きいとガウスカーネルが広がり、推定される密度は滑らかになるが、細かな特徴を捉えられなくなる。逆に小さいと、各データ点の近傍のみが強く影響を与え、ノイズに敏感な結果となる。
ガウスカーネルを用いることで得られる滑らかな密度推定は、データの潜在的な構造をうまく捉えられる一方で、バンド幅\( h \)の選択は重要な問題となる。
上図のとおり、ヒストグラムの区間の幅\(\Delta\)と同じく\(h\)が大きくても小さくても生成元となったグラフを捉えられていない。
最近傍法
先ほどの
$$ p(\mathbf{x})=\frac{K}{N V} $$
の\(K\)を固定してデータから\(V\)の値を推定するのが\(K\)近傍法だという話を先ほどした
K近傍法とは、指定された点から近い順にK個のデータ点を選び、それらの特性に基づいて評価や推定を行う手法だ。密度推定におけるK近傍法について説明しよう。
まず、我々が欲しいのはある位置\(x\)における密度の推定値\(p(x)\)である。この\(p(x)\)は、位置\(x\)周辺のデータ点の数（つまり「密度」）に基づいて決まる。
ここでK近傍法を導入する。\(K\)はある点\(x\)から近い順に選ばれたK個のデータ点の数、\(V\)はそれらK個のデータ点が存在する領域の体積、そして\(N\)はデータセット全体のデータ点の数を表す。
したがって、密度推定値\(p(x)\)は、選ばれたK個のデータ点の数\(K\)を、領域\(V\)と全データ点数\(N\)で割ったものとなる。\(N\)で割ることで、全体のデータ数に対する相対的な密度を表現している。
ここで重要な点は、この方法がパラメトリックなモデルを必要とせず、データそのものから直接的に密度を推定することができるという点だ。
この推定された確率密度関数をヒストグラムとカーネル推定の時と同じデータ集合に適応した場合、以下の図のようになる。
今回も\(K\)の値が大きくても小さくてもデータを生成した真の分布の二峰性を捉えられていない。そして、特筆すべきこととして、K近傍法で生成されるモデル（青）は、空間上の積分が発散するということ。
K近傍法によるクラス分類
この密度推定の\(K\)近傍法は、クラス分類問題にベイズの定理を用いて拡張できる。
例としてクラス\(C_k\)に\(N_k\)個の点があり、点の総数は\(\sum_k N_k=N\)
\(x\)を中心とし、\(K\)個の点を含む体積\(V\)の球を考えるとき、この球は、体積が\(V\)で、クラス\(C_k\)の点をそれぞれ\(K_k\)個ずつ含んでいたとする。
各クラスの密度の推定値は
$$
p\left(\mathbf{x} \mid \mathcal{C}_k\right)=\frac{K_k}{N_k V}
$$
そして、クラス条件のない密度は
$$
p(\mathbf{x})=\frac{K}{N V}
$$
一方クラスの事前分布は
$$
p\left(\mathcal{C}_k\right)=\frac{N_k}{N}
$$
よってこの三式にベイズの定理を適用すると、クラスに帰属する事後確率を得ることができる
$$
p\left(\mathcal{C}_k \mid \mathbf{x}\right)=\frac{p\left(\mathbf{x} \mid \mathcal{C}_k\right) p\left(\mathcal{C}_k\right)}{p(\mathbf{x})}=\frac{K_k}{K}
$$
誤分類してしまう確率を最小化するには、\(\frac{K_k}{K}\)の値を最大にするクラスに\(x\)を割り当てればよい。つまり、球の中で多数派のクラスにｘが分類される。
この図だと☆マークは、k=3の時はクラスBに分類され、k=6の時はクラスAに分類される
まとめ
ここまでヒストグラム法、カーネル密度推定法、K近傍法とやってきたが、それらはすべてデータ集合全体を保存しなくてはならない、そのため、データ集合が大きと膨大な計算量が必要になるという短所を抱えている
そのために前処理をしておくことで効率的にデータ集合を探索できるようになるが（決定木の構築）、それでもこれらノンパラメトリック法は制限が非常に強く、そして普通にパラメトリックなモデルをつかっても表現できる分布には制限がある。
参考
