Sampling, Detailed Balance, Gibbs Sampling, Rejection Sampling MCMC, Dirichlet Process, RBM, Particle Filtering

Sampling - C.D.F , P.D.F

샘플링을 하려면 P.D.F 가 아닌 C.D.F 의 역함수를 알아야한다.
PDF는 확률이 아니다. 확률의 미분값이다(적분한 값이 확률이므로). 따라서 0~1 사이의 확률에 대해 uniform distribution을 가지고 샘플링을 하려면, y축에 대해 [0,1]로 샘플링을 한 다음, C.D.F에서 그 y축에 해당하는 x값을 알아내는 것이 바로 샘플링이다.

당연히 이를 위해서는 CDF의 역함수를 알아야 한다. (y축의 값이 어떤 x에 해당하는지 알아야함.)

그러나 CDF의 역함수는 일반적으로 구하기가 매우 어렵다.

가우시안 분포에서도 CDF가 적분으로 정의만 되어있지 계산이 안된다. 그러나 가우시안 분포는 엔지니어링적으로 샘플링이 거의 가능해서 proposal로 많이사용한다.

Detailed balance

디테일드 벨런스는 Ergodic MC에서, aperiodic과 positively recurrent 조건이 만족될 때 s'->s 로 전이되는 비율과, s->s'으로 전이되는 비율이 동일할 때 전체 분포를 샘플링할 수 있다는 조건이다.

Ergodic MC란, Markov Chain에서 aperiodic 즉, 주기가 1이어야만 각 state가 진동 또는 발산하지 않고, 수렴한다는 것과 관련되어 있다. aperiodic이란, 최소 하나의 state에, 자기자신으로 전이되는 transition probability가 정의 되어야 하는 것을 의미한다. 그러면 주기가 1이아닌, 주기가 2,3,4 등등의 state가 이 state를 이용해서 주기를 1로 만들 수 있다고 한다. (주기의 최대 공약수를 1로 만든다라고 함)

Positively recurrent란, 유한한 시간안에 모든 state에 골고루 접근할 수 있어야 한다는 것 같다. 예를 들어 MC가 끊겨있으면 어떤 state에서 시작하여 모든 다른 state에 도달할 수 없다. 따라서 모든 MC가 서로 연결되어 있어야 한다.

Detailed balance란, 이러한 ergodic MC에서 P(X t = s')*P(X t+1=s|X t=s') = P(X t = s)*P(X t+1=s'|X t=s)  즉, 해석해보면 (s->s')으로 전이될 확률과 (s'->s)로 전이될 확률이 서로 같을 때 원래의 분포를 따르는 샘플링을 할 수 있다는 조건이다.

디테일드 벨런스의 핵심은 결국 두 state 간의 전환 비율을 항상 동일하게 맞추어야 한다는 것이다.
(이를 맞추지 않으면, 원래 분포가 갖는 각 state에서의 수렴 값이 샘플링한 분포에서의 각 state가 갖는 수렴값과 서로 동일하지 않게 된다.)

Rejection Sampling

가우시안 분포를 Rejection Sampling 하면, [0,1]의 확률을 uniform하게 뽑는다. 그러면 0~1사이의 전체 면적이 샘플링이 된다. 이때 가우시안 분포의 P.D.F값만큼 accept를 하고, 당연히 (1-P.D.F)값 만큼 reject를 한다. 이 과정은 크기 1의 전체 면적에서, 가우시안 분포에 해당하는 면적만 남기고 나머지는 지우겠다는 의미이다.

여기서 uniform분포가 아니라, cauchy분포라는 것을 사용하는게 원래의 이론인 것 같다. 코시 분포는 가우시안하고 비슷하게 생겼는데 샘플링이 가능한 (즉, cdf의 역함수를 구할 수 있는 것 같음) 분포이다. 그래서 코시 분포에 1.5정도의 상수값을 곱해서 가우시안 분포를 전부다 덮도록 한 다음, 이 코시 분포에서 샘플링하고 이걸 가우시안 분포의 PDF값을 고려해 accept하여 코시분포의 면적과 가우시안분포의 면적의 차이를 제거한다.

그런데 이러한 방식은 reject rate가 너무 높아서 실질적으로 사용하기가 힘들다.

그래서 나온 방법이 MH 이다

MCMC - Metropolis Hastings 와 Proposal

proposal이란, 샘플링 할 수 있는 분포로 (uniform도 가능) 이를 이용해 샘플링 할 수 없는 분포의 한 점에 가우시안이나 유니폼 분포같은 거를 세우고, 다음 점을 샘플링하는 것이다.

Metropolis Hastings는 한 점에서 다음 점으로 이동할 때 Accept할 비율을 정하는 것인데,

디테일드 벨런스의 P(X t = s')*P(X t+1=s|X t=s') = P(X t = s)*P(X t+1=s'|X t=s) 에서

P(X t+1=s|X t=s') 을 우리가 구하기 힘든거라

P(X t+1=s|X t=s') = Q(x t+1=s|x t=s)*A(s->s') 으로 임의의 proposal 분포 Q를 정의하고, 그 프로포절 Q와 실제 분포 P와의 면적 차이를 매꾸기위한 Accept 함수 A를 정의한다.

Gibbs sampling

MCMC는 N차원의 점에서 바로 N차원의 점으로 모든 차원을 한번에 이동하면서 샘플링을 한 것인 반면, 깁스 샘플링은 한개의 차원을 제외한 나머지는 고정을 시킨다음, 한 차원 씩 샘플링을 해서 총 N번의 이동을 하고 난 다음 진짜 새로운 데이터를 샘플링하는 것이다.

단 깁스 샘플링을 하기 위해서는 말한대로 한개차원을 제외한 나머지를 given으로 고정시켜야한다. 즉 각 차원에 대한 conditional probability를 알아야만 사용이 가능하다.

그러나 RBM 같은 모델의 경우, 우리가 모델을 정의하였으므로 그 conditional probability를 알 수가 있다. 따라서 당연히 깁스 샘플링도 가능하다. 

MH는 1~10차원의 샘플링은 잘 하지만, 수천차원에서의 샘플링은 리젝션 레이트가 너무 높아서 작동을 하지 못한다.

깁스 샘플링이 좋은 이유는 한번에 1개의 차원씩 이동을 하기 때문에, 문제를 훨씬 단순화 시켜서 풀었다는 것이고 그로인해 고차원의 저주와같은 문제가 안발생하는 걸로 보인다. 그래서 고차원 분포의 샘플링에서 훨씬 빠르게 동작하는 것 같다.

RBM - Contrasitive Divergence

RBM에서는 깁스 샘플링을 통해 학습을 하게 된다. RBM은 결국 계산을 하면 시그모이드를 계산하는 것과 동일하다. 
모델이 나타내는 분포를 데이터가 나타내는 분포와 동일하게 만들기 위해 데이터의 point로 비주얼 노드를 초기화 시켜 최대한 모델의 분포를 가깝게 배치해 버닝 타임을 최소화 시킨다.

그다음 RBM은 MRF이기 때문에 conditional independence 조건을 이용할 수 있다. 그래서 원래의 깁스 샘플링대로하면 1개의 노드를 제외한 나머지 전부를 기븐으로 놓고 한 노드씩 샘플링을 해야하지만, c.i 조건을 이용하여 모든 비주얼 노드를 기븐으로 놓으면 히든노드 전부는 각각이 서로 독립이 되므로 한번에 샘플링 할 수가 있다.

반대로 모든 히든노드를 기븐으로 놓고, 비주얼 노드를 한번에 샘플링하는 것도 가능하다.

이를 blocked RBM? 이라고 하는 것 같으며, 따라서 매우 빠르게 2스탭만에 모든 노드들이 샘플링되어진다.

ergodic 하다는 것은 time average = space average 라고 한다..

이게 무슨 말이냐면 1개의 점에서 100번 샘플링한 것과, 100개의 임의 점에서 1번 샘플링한 결과가 같아야 한다는 것.

그런데 RBM을 깁스 샘플링을 이용해 학습 시키는 K-Contrasitive Divergence는 이 space는 모든 데이터의 개수만큼 갖고, 대신 time 은 단 K회만 보는 방식이다. 그런데 놀라운 점은 K=1 이어도 매우 빠르게 잘 학습한다는 것이다.

C.D를 발전시킨 persistent C.D는 성능이 더 좋은데, 여기서는 데이터의 포인터로 비주얼 노드를 학습시키는 게 아니라, 샘플링하기 직전 분포에서의 데이터로 초기화를 한다음 피팅을 하는 방식이라고 한다. 그래서 보다 초기점이 모델의 분포에 가깝게 위치하여 1번의 타임으로도 유의미한 학습을 더 잘하는 것 같다.

Energy based model

RBM은 에너지 베이스드 모델이다. 에너지란 열에너지와 같이 해석하면 된다. 열에너지는 항상 높은 곳에서 낮은 곳으로 이동하여 평행을 이루듯이 에너지 베이스드 모델에서도 낮은 에너지를 향해 이동하려 한다.

즉 낮은 에너지를 가질수록 그 상태가 될 확률이 높아지게 된다. 1/에너지=확률 이라고 해석하면 된다. (한마디로 확률기반의 모델이라는 뜻)

Particle Filtering

파티클 필터링 또한 MCMC 샘플링 기법중 한가지이다. 이 방법은 정성적인 아이디어 측면에서 kernel density estimation과 발상이 비슷하다. KDE는 데이터의 히스토그램, 즉 데이터 자체의 분포를 여러개의 가우시안을 누적시키고 더해서 알아내려는 것이다.

파티클 필터링은 가우시안으로 된 알갱이들을 랜덤하게 뿌린다음 각 알갱이가 원래 분포와 비슷하면 가중치를 높이고, 아니면 가중치를 줄이는 방식으로 샘플링을 하는 것 같다.

이는 시퀀셜 임포턴스 샘플링이라고 하는 것 같다.

(K-Nearest density estimation 은 이 KDE와 거의 비슷하다고 한다. PRML 3장 끝을 보라?)

그리고, 히스토그램은 사실 P.D.F 인데 discrete한 버전일 뿐임. 그 역시 데이터의 분포를 막대기로 이산적으로 표현한 것.

Dirichlet process

디리슐레 프로세스는 multinomial 문제에 대한 bayesian 접근이다. multinomial 이므로 conjugate prior로 dirichlet distribution 을 사용하는 것이고, prior로써 분포의 분포를 가정하는 것 같다.

실질적으로 GMM에 dirichlet을 도입하여, 가우시안이 가질 분산과 평균을 디리슐레 분포로 prior를 준다.

Gaussian processes는 랜덤 function 의 개념이고

Dirichlet processes는 랜덤 measure의 개념이다. 랜덤 매져라는 것은 랜덤 펑션의 분포인거같다... 아마도..

하튼 그래서 DP를 사용하면 처음에 데이터를 안봤을 때는 전부 prior 분포중 하나에서 시작을 하게된다 그러나 데이터를 보면 볼수록 prior의 분포는 무시되고 즉, cluster를 정하면 정할수록 prior분포는 비중이 작아지고 기존 클러스터에 선택이 되게된다.

chinese restaurant processes 를 이해하면 도움이된다고 한다..

http://www.youtube.com/watch?v=PxgW3lOrj60

Conjugate prior

본 블로그의 다른 글을 참조하길....