MC sample, MCMC, Gibbs Sampler, Metropolis

 

1. 일반적 방법

1) inverse method

Pr( FF(-1)(u)<F(b))=Pr(u<F(b)=F(b)

 

2) truncated

u~U(F(b), F(a))

 

3) accept - reject

 

4) importance sampling

f/g; f는 target pdf, g는 proposal pdf, f와 관련없는 임의

x~g한 다음 f(x)/g(x) 구함

 

Pr(f(x)/g(x) < b)=Pr(f(x)/g(x)*g(x) <b)

 

흥미로운 생각

E[T(x)] , where x~f

는

E[T(x)*f(x)/g(x)] where x~g

와 같음

 

MCMC

1. Metropolis Algorithm

에너지 E를 최소화

rule

if E(stat(i+1)) >가 아니라 < E(state(i)) then accept state(i+1); 즉 i+1의 state의 에너지가 i state의 에너지보다 작으면 i+1 state로 점프, 에너지 최소화가 목적

 

else

stat(i+1) accept with some prob. s.t as T->0, Prob.->0

 

relaxation: local minimum에 빠지는 것을 막음

Pro.=exp[{(E(i)-E(i+1)}/kT)] where k:Boltzman constant

 

Bolzman 분포로 수렴(균형상태)

 

2. MA 두가지 방향으로 방전

1) Simulated Annealing: Neighborhood construction이 중요: combinatorical 최적, graphic, 뉴런 네트웍: Cerney, Kirkpatrick

 

예:salesman problem

solution space S={모든 가능한 경로}

objective function G(s):거리=Energy where MA

N(s)={s에서 두 도시만 위치 바꿈}

 

도시=(a, b, c, d, e}

solution space S={a->b->c->d->e->a, a->c->b->d->e->a, a->b>e->c->d->a, ...}

N(a->c->b->d->e->a)={a->b->c->e->a, a->d->b->e->a,...}

 

 

2) Hastings 알고리즘; 목적 pdf g 알고 있음

S={모든 가능한 pdf}

N(h)={f|h+e} w/ E(e)=0

 

아이디어 표본 x가 g에서 왔다면 g(x)>f(x)

MA 적용

 

if g(x)> f(x) then accept f(x)==>accept x

else accept f(x)=>accept x  w/ some Prob.

 

3. German & German: image restoration 응용:고대 유물 인식

image=lattice system. pixel=particle

Gibbs Sampler hierarchical Bayes 모델적용

 

Hasting에서 좀 더 빠른 경로가 없을까?

N(h)={f|h+e}에서 f가 알려진 타켓 g와 비슷하다면

f(x,y)=f(x|y)*f(y)=f(ylx)*f(x) 즉 f(x,y)는 f(x|y), f(y|x)와 marginally 비슷

 

S={g(x|y), g(y|x)}

S에서 통상 수치해석처럼 지그재그로 g(x,y)를 찾아감