Gibbs sampler1

Gibbs sampler가 처음 나온 논문은 geman & geman의 이미지 복원(restoration) 논문입니다. 이 논문 첨부했고요.

 

GemanandGeman84.pdf

8.98MB

 

이미지 복원은 왜곡된, 훼손된 이미지에서 원래 이미지를 찾아가는 과학적 방법을 말합니다. 포토샵에서 이미지에 효과를 주는 기술적이고 예술적인 방법과 다른 것입니다. 물론 포토샵의 효과에서 여러 가지 수학적 방법을 사용하고 있지만요.

 

일반적인 Metropolis 알고리즘을 이해하려면

 

“Simulated Annealing and Boltzman Machines", Aarts & Korst

 

이 책이 허원이 교수가 연구한 조합 문제를 컴퓨터 계산 방식으로 풀려고 한 책입니다. 허원이 교수가 연구한 문제가 colouring 문제이네요. 컬러링 문제에서 경우가 수가 다항식으로 전개되는데 이 다항식의 계수가 log-convex하다 이런 것 같은데요. 하여간 잘 모르는 이야기이니까 넘어 가고요.

 

 

Gibbs sampler의 공식은 간단합니다.

 

예를 들어 3개의 변수 X1, X2, X3가 있다고 하죠. 그럼 1회전은

 

1) X1과 X3에 임의의 숫자를 하나 뽑습니다. 즉 X1=x1, X3=x3

 

2) x2 <-- f(x2|X1=x1, X3=x3) 즉 x2를 조건부 분포 f(x2|X1=x1, X3=x3)에서 뽑습니다.

 

3) x3 <-- f(x3|X1=x1, X2=x2) 즉 x3를 조건부 분포 f(x3|X1=x1, X2=x2)에서 뽑습니다.

 

 

4) x1 <-- f(x1|X2=x2, X3=x3) 즉 x1를 조건부 분포 f(x1|X2=x2, X3=x3)에서 뽑습니다.

 

그러면 1 회전의 데이터 (x1, x2, x3)가 나옵니다. 그럼 2회전은 위에서 구한 (x1, x2, x3) 값을 가지고 다시 똑같이 합니다. 그럼 2회전은 데이터 (x1, x2, x3) 값이 나옵니다. 이런 식으로 한 천번 정도하면 최초의 데이터 (x1, x2, x3)를 구할 수 있습니다.

 

변수	1회전	2회전	.	.	.	1000회전
x1	34.2	28.2				31.3
x2	15.3	11.4				14.7
x3	74.9	82.9				77.3

 

 

마지막 (x1=31.3, x2=14.7, x3=77.3) 이게 첫 번째 데이터입니다. 어느 정도 예측을 하겠지만 처음에는 (x1, x2, x3) 값의 변동이 심합니다. 그러나 회전 수가 많아지면 나중에는 거의 변동이 없이 일정한 값으로 수렴을 합니다.

 

이런 데이터를 똑같은 방법으로 천번, 만번 하면 표본의 크기가 1000, 10000인 자료를 만들 수가 있습니다.

 

 

위 깁스 샘플러를 하려면 조건부 확률분포를 알아야 합니다. 이것도 간단한 문제가 아니죠. 조건부 확률분포가 잘 알려져 있는 경우가 다변량 정규분포입니다.

 

그래서 모든 책에서 Gibbs sampler의 가장 간단한 예로 이변량정규분포(bivariate normal distribution)을 듭니다.

 

이것 R로 짜면 아마 10줄 정도면 될 것 같은데요. 물론 이변량 정규분포뿐만 아니라 다변량 정규분포에서 데이터 만개, 십만개 뽑으려면 명령문 1줄에 다 뽑아줍니다. 이건 단순히 깁스 샘플러 과정을 이해시키기 위해쇼ㅓ 하는 것이 불과합니다.

 

다변량 정규분포에서 데이터를 시뮬레이션 하는 과정을 이해하는 것은 그리 어렵지는 않습니다. 행렬에 대한 어느 정도 기초만 있으면 됩니다.

 

통계학에서는 베이지안에서 많이 사용합니다. 베이지안은 모수 b들이 확률분포를 한다고 가정하죠. 일단 데이터 y가 관찰되면 모수 b를 생성하는 것은 위의 과정과 똑같습니다. b=(b1, b2, b3, b4)가 있다고 하면

 

1회전 b1 <-- f(b1 | b2, b3, b4, y)

2회전 b2 <-- f(b2 | b1, b3, b4, y)

 

이런 식으로 위의 과정과 똑같이 하면 됩니다. 즉 사후조건부 확률분포식만 구할 수 있으면 됩니다.

 

GemanandGeman84.pdf

8.98MB

 

중요presentation4.pdf

0.42MB

그래서 좀 낮은 수준의 논문에서는

 

조건부 확률식만 구해서 simulation을 하면 됩니다.

 

그러나 높은 수준의 논문에서는 자신이 풀고자 하는 문제에서 위 과정이 markov chain의 어떤 특성을 만족한다는 것을 논문에서 입증을 해야 합니다.

 

 

간단한 단순회귀분석에서 깁스 샘플러를 이용한 논문을 첨부합니다. page 29부터 참조

 

중요presentation4.pdf

0.42MB