확률 분포 추정

확률밀도 함수가 주어지지 않았을 때는 어떻게 풀 것인가

→ Gaussian확률 밀도함수가 주어졌을 때는 bayesian 결정이론을 사용했음

→ 확률 분포(확률밀도 함수) 를 추정해야함

베이지안 분류기에서 우리가 알아야 되는것은

1. 사전확률 ( sample / N(표본수) ) 

    bias가 있을것이라고 생각이 된다면 사전확률은 무시해도 됨

    (주사위 면적이 다를 것이라고 생각된다면)

2. 확률 밀도함수 (클래스 별)

     a. parameter를 알면 추정할 수 있음 = parameter density function

         (likelihood: 최대우도법)

     b. non-parametric density function (비모수 추정법)

         → Parzen windown density / knn density estimation 방법을 사용

** 확률밀도 함수 조건: 항상 양수이며, 곡선의 아랫부분의 합은 1인 것

차원의 저주를 해결하기 위해서는

N은 충분히 크고, d는 작아야 함

** discrete할 경우에 차원의 저주가 더 많을 수 있음

   왜냐하면, 빈 공간을 채우기 위해 더많은 차원을 쓰므로

최대우도 추정방법(ML)

각 주어진 x에 해당한 P(x|theta)를 구함 (i.i.d)

아래식의 최대값을 만드는 theta를 찾아야됨

→ 미분함. 미분해서 0으로 만드는 매개변수를 찾는 것임

 

아래 파란색으로 넘어갈 때

아래의 식을 사용한 것임

결론

→ sample mean : 

→ sample covariance: 

 

 

MAP(Maximum A posteriori: 사후확률적으로 parameter를 추정한다는 뜻)

 사전확률을 안다면(mu0 를 알고있다면 = 그림에서는 P(theta) )

 ML추정에서 나온 theta값이 mu0에 의해 변화될 수 있음

theta값이 가질 수 있는 확률(=사전확률)을 고려하는 것

왼쪽 그림ML에서는 P(theta)가 constant하므로 무시하는 것임

비모수방법 - 1. 파젠창

전히 매끄럽지 않은 함수  

예를 들어 그림 3.6(a)에서 x를 오른쪽 옮기면 

계속 두 개이다가 어느 순간 에 3으로 바뀜. 

따라서 불연속인 pdf

→ non-parametric 함수

 

 

 

이때 커널 함수를 사용하여 매끄럽게 만들 수 있음

 

커널 함수로 가우시언을 채택하면 매끄러운 pdf를 얻게 된다.

 

 

 

 

파젠 창의 특성

 차원의 저주에서 자유로운가?

→ 그렇지 않을 수 있음

→ sample이 sparse할 때 차원이 많아지면 안좋으므로

 추정한 pdf가 실제에 가까우려면 N과 h는 어떻게 되어야 하나

→ sample의 개수는 충분히 많고, h를 충분히 작게할 수 있다면 파젠창의 특성이 유효할 수 있음

 

 

 

비모수방법 - 2. KNN density estimation (K-nearest neighbor)

KNN : 

x를 중심으로 창을 씌우고 k 개 샘플이 안에 들어올 때까지 확장하고

그 순 간의 창의 크기를 h라 한다.

즉 k가 고정되고 h가 가변이다.

** 파젠 창에서는 h가 고정되고 k가 가변이다

위의 식에서, h↑ → P(x) ↓

즉, k개를 포함하기위해 h가 작아지면 그때의 확률밀도(pdf)는 높아짐.

 

 

 

 

KNN의 시간복잡도

k가 클수록, 차원이 높을 수록, N이 많을 수록 더 복잡해짐

kdN에 비례함

→ 보로노이 도형으로 복잡도를 줄일 수 있음

(미리 구성해야함) 

보로노이 도형을 미리 구해 놓음

1-NN을 구할 수 있는 보로노이 도형

3-NN을 구하기 위해서는 위와 다른 도형이 미리 구해져야지 됨

 

 

 

KNN분류기

윈도우 안에 k개의 샘플이 들어올 때 까지 윈도우를 확장하여 knn분류기를 만들 수 있음

3.14는 i번째 클래스의 샘플개수 / 전체 샘플 수

 

3.13 = 우도, 3.14 = 사전확률

 

그러므로 1 class로 분류할 확률이 높고

따라서, knn 분류기는 

q = argmax Ki 일 때, x를 k로 분류함

 

 

 

knn에서의 복잡도

train할때 걸리는 시간은 0

test 할 때 걸리는 시간은 N(n개랑 거리를 비교해야되기 때문에)

** 보로노이 도형알고리즘의 복잡도는 n^2임

→ 그러므로 보로노이 도형을 미리 만들어놓으면 상수정도의 시간이 걸림

→ 보로노이 도형 알고리즘의 복잡도가 train할 때 걸리는 시간이 될 수 있음

 

 

 

k-NN 분류기의 오류율 특성

k-NN에서 sample 수가 무한대로 커지면 최선의 경우인 bayesian 분류기의 오류율과 같은 범위에 있음

기억하기!

 

 

 

k-NN 분류기의 오류율 특성

위의 식을 유도해보자.

Enn = (P+Pnne-) + (P-Pnne+)

*  (P+Pnne-) :내가 플러스인데 knn에서 -이니까 오류인 것임

* Pnne-: 주변샘플이 "-" 일 확률

* n →∞ 이면 주변샘플의 확률하고 내 확률이 거의 같아짐

* P+: 올바르게 분류될 확률 = 1-e

* 1-P+ : 틀리게 분류될 확률 = e

* 1-e는 1보다는 작은 값이므로 부등호가 성립함

 

 

 

 

3.4 혼합모델

보통 가우시안 확률분포를 사용함

노란색의 경우, identical 한 분산을 가지고 있음 (x1과 x2의 상관관계가 없음)

즉, 행렬로 표현하면 아래와 같은 공분산을 가지고 있음

 

아래의 pdf식을 보면 1/3과 2/3의 가중치를 줬으므로 총합은 1이 됨

 

위의 식을 일반화 하면

 

 

 

 

GMM의 최대우도추정(i.i.d라고 할 때)

 

미분으로 풀기 어려움

→ EM알고리즘으로 풀기

 

 

 

 

EM 알고리즘 (Expectation maximization 알고리즘)

membership을 결정한다 = 가중치를 결정한다

membership의 변화가 더이상 없을때 stop을 함

→ 단점. local minima에 빠지게 될 수 있음

 

 

 

 

EM 알고리즘 상세

1. expectation

→  나머지를 0으로 표현하는 것은 hard membership임

 

→  위의 내용은 확률 분포(우도) 

노란색은 3.15유도 필기내용이 반영된것으로 생각하면 됨

위 식도 참고해야함

 

 

 

2. maximization

최대우도추정(평균)에 대한 정리

(7페이지에서 sample mean유도식을 그대로 적용하면 됨)

3.26식은 sample mean에서 j가 1로 속할 확률을 곱해준 것임

 

 

 

 

 

최대우도추정(공분산, 혼합계수 pi)에 대한 정리

3.29는 가중치와 같은 의미임을 알 수 있음

 

 

 

EM 특성