Nonparametric Methods

memory-based learning or instance-based learning라고도 한다.

비슷한 inputs는 비슷한 outputs를 가질 것이라는 가정 외에는 Probabilty density/distribution에 대한 어떤 가정도 하지 않는 기법.
distribution을 알거나, 가정하는 Parametric Methods나 semi-Parametric Methods와는 차이가 있다.

데이터의 일부에 대해서 local하게 학습시키는 Local model에 대해서 데이터를 기억하게 하고, 새로운 데이터가 들어오면 비슷한 local model을 이용한다.

즉, 데이터 전체에 걸친 전역전인 패턴을 학습하기 보다는 데이터의 특정 부분을 학습하는 방식이다.

이는 곧, 데이터의 구간에 따라 모델을 달리할 수 있어 유연성이 높아지고 비선형적인 관계를 설명할 수 있다.

Methods

Histogram

특정한 크기 $b$ 로 일정하게 bin을 나누고, 확률을 해당 bin을 이용해 계산하는 방식.
즉, $b$ : bin size

$P (x) = \frac{# { x ^{t} in the same bin as x }}{N b}$ : $b$ 로 나누어, 전체 bin에 대해 각각 확률을 다 더했을때 그 합이 1이 되도록 한다. (Probability에 맞춤.)
bin: $[x_{0} + ib, x_{0} + (i + 1) b]$ : 시작점 $x_{0}$ 에서부터 $i$ 가 변화하며 구간이 설정됨.

문제점

만약 bin안에 어떠한 데이터도 없다면, 확률이 0이 된다.
계단식 개형이 나타나므로, 연속이 아니게 된다.
origin $x_{0}$ 을 어디로 잡는지에 따라 Probability 그래프가 달라지게 된다.

Naive estimator

Histogram을 origin 문제를 해결 가능하다.
허나, 확률이 0이 되거나 연속이 아니게 되는 문제점은 동일하게 발생한다.

$P (x) = \frac{# { x - b /2 < x ^{t} \leq x + b /2 }}{N b}$ : 알고자 하는 $x$ 에 대해 bin size만큼 앞뒤로의 구간.
$= \frac{1}{N b} t \sum w (\frac{x - x ^{t}}{b})$ , when $w (u) = {10 if - 1/2 \leq u < 1/2 otherwise$

Parzen windows

혹은 Kernel estimator 라고도 불린다. 확률이 0이 되는 것을 방지한다.

P (x) = \frac{1}{N b} t \sum K (\frac{x - x ^{t}}{b})

: 이 때의 $K$ 는 Kernel function이며 Guassian Kernel 이 쓰인다.

$K (u) = \frac{1}{2 π} exp (- \frac{u ^{2}}{2})$ : Expectation이 0, Variance가 1인 Guassian Kernel.
각각의 Gaussian Distribution들이 만들어지는 분포라고 볼 수 있다.

이를 이용해 $P (x)$ 를 계산하면: $\frac{1}{N b} t \sum \frac{1}{2 π} exp (- \frac{1}{2} \frac{( x - x ^{t} ) ^{2}}{b ^{2}})$ : 이 때 앞의 $b$ 를 Variance, $x^{t}$ 를 평균인 Gaussian Distribution이라고 볼 수 있다.

K-means Clustering를 이용한 Semi-Parametric Methods density estimation에서, Prior $P (g_{k})$ :가 $\frac{1}{N}$ 으로 전부 동일하게 두었을 때의 확률하고 일치한다.

Multivariate Distribution Kernel Density Estimator

$P (x) = \frac{1}{N b ^{d}} t \sum K (\frac{x - x ^{t}}{b})$
: when $\int K (x) d x = 1$

Guassian Kernel function: $K (u) = \frac{1}{( 2 π ) ^{d /2}} exp (- \frac{∥ u ∥ _{2}^{2}}{2})$ :
평균 벡터가 0, Covariance Matrix가 Indentity Matrix인 꼴로 사용된다.

혹은, Train Data를 이용해 구한 Sample Covariance Matrix $S$ 를 Covariance Matrix로 사용하기도 한다. 이 때, 확률 분포 $P (x)$ 는 Mahalonobis Distance를 가지게 된다.

K-Nearest Neighbor Estimator

KNeighbor 을 이용한 Estimator. 어떠한 data point $x$ 에 대해 가장 가까운 $k$ 개의 이웃 data point를 이용한다.

P (x) = \frac{k}{2 N d _{k} ( x )}

:이 때 변화하는 값은 분모의 $d_{k} (x)$ 뿐이며, $k$ 개의 이웃까지 포함하려면 binSize가 얼마나 커야 하는지를 나타낸다고 볼 수도 있다.

$d_{k} (x)$ : Distance to the $k$ -th nearest neighbor.

확률이 0이 되지 않는다.
연속이다.
모든 샘플을 이용하지 않으므로 계산량이 많지 않다.

Smoothing k-nn estimator

$P (x) = \frac{1}{N d _{k} ( x )} t \sum K (\frac{x - x ^{t}}{d _{k} ( x )})$
: Kernel 함수를 이용한 것으로, $d_{k} (x)$ 는 곧 $k$ 번째 이웃이 멀리 있다면 Variance가 증가함을 의미한다.

Multivariate Distribution K-nearest Neighbor estimator

$P (x) = \frac{k}{N v _{k} ( x )}$
: when $v_{k} (x)$ : $x$ 를 중심으로 하는 반지름이 $d_{k} (x)$ 인 $d$ 차원의 hypersphere의 Volume. 즉, $k$ -nearest neighbor까지만 포함하는 hypersphere이다.