여행하는 세일즈맨 문제, MCMC, 베이지안, Gibbs sampler

 

1. travelling sales man problem(여행하는 세일즈 맨 문제)

 

전산학과에 P-NP 문제라는 것이 있는데 이게 NP문제인지는 모르겠네요.

 

이 문제는 한번 쓴 적이 있는 것 같은데 여기서 다시 한번 쓰겠습니다.

 

하여간 이 문제는 영업사원이 50개 도시를 돌아다니는데 가장 짧은 경로를 찾는 문제입니다.

 

이것 머리로 생각하면 매우 간단합니다.

 

1) 모든 경로를 센다.

 

2) 각 경로의 거리를 잰다.

 

3) 이 중 가장 짧은 거리를 가지는 경로를 찾는다.

 

 

그런데 실제로 하면 이 문제가 간단하지 않습니다. 문제는 이 경로의 경우의 수가 어마어마하게 많다는 것입니다.

 

따라서 도시 수가 50이 아니라 100, 1000, 10000 이렇게 무한정 커져 가면 이건 슈퍼컴퓨터로도 쉽지 않겠지요.

 

여기서 완벽한 답은 아니지만 거의 정확한 답을 총알같이 구하는 방법이 있습니다. 여기에 MCMC의 원형인 Metropolis 알고리즘이 나옵니다. 물론 simulated annealing이라는 알고리즘도 들어가지만요.

 

옛날에 제가 제 웹페이지에서 자바로 짜서 올린 적이 있는데 그 코드를 잃어버려서요. 제 홈페이지에 들어와서 클릭하면 50개 도시가 랜덤하게 찍히고 그리고 시작 버턴을 누르면 가장 짧은 거리를 가진 경로를 찾아가는 모습을 그래프로 보여줍니다. 옛날 386컴퓨터에서 몇 초만에 끝납니다.

 

 

우리가 산 정상에 오르거나 아니면 하산을 할 때 항상 높은 방향이나 낮은 방향으로 가는 것은 아닙니다.

 

산 정상을 오르는 경우를 생각하면 중간에 잠깐 내려가는 길도 있고 그렇죠.

 

무조건 높은 방향으로만 가면 산 정상이 아니라 중간 작은 봉우리에서 멈춰버리거나 아니면 높은 절벽같은 곳을 만날 수 있습니다.

 

그래서 간혹 낮은 방향으로 가는 경우도 선택을 해야 합니다.

 

 

이 문제는 전산과 수치해석에서 골치 아픈 문제입니다. 함수가 봉우리가 하나(uni modal)가 아니고 여러 개인 경우 기존의 초보적인 수치해석 방법으로 계속 높은 곳만 찾아가면 global maximum이 아닌 local maximum에 빠질 수가 있다는 것이죠. 즉, 똥통에 빠진 것이죠.

 

 

 

그리고 세일즈맨 문제에서 거리가 최소가 되는 경로를 찾아야 하는데 이 경우도 가끔 거리가 커지는 경우도 선택해야 local minimum이 아니고 global minimum인 경로를 찾을 수가 있습니다.

 

 

그럼 이 문제를 어떻게 해결할까요. 5개 도시 A, B, C, D, E가 있다고 하죠.

 

1) 아무런 초기 경로인 경로0을 하나 설정합니다. A에서 출발한다고 하죠.

 

경로0: A->C->E->D->B->A

 

2) 경로0의 주변, 또는 이웃인 경로를 생각합니다. Neighborhood라고 합니다. 수학에 나오는 open set이죠. 이 이웃을 어떻게 만들지가 핵심입니다.

 

여기서 이웃 경로는 이전 경로에서 두 도시만 살짝 바꾸는 것으로 하죠.

 

그럼 Neighborhood(경로0)은

 

{ (A->E->C->D->B->A), (A->D->E->C->B->A), (A->C->D->E->B->A), (A->B->E->C->B->A), ...}

 

 

3) 이 이웃에서 하나의 경로, 경로1*를 선택하여 경로0하고 경로1*하고 거리를 비교합니다.

 

4) 만약 경로1*가 경로0보다 거리가 짧으면 다움 경로1<-경로1*을 선택합니다.

 

만약 경로1*이 경로0보다 거리가 길어도 어떤 확률값을 줘서 선택합니다. 선택하지 않으면 다음 경로1<-경로0, 즉 이전의 경로를 계속 유지합니다.

 

즉

 

if  경로1*의 거리 < 경로0의 거리

then pr(경로1<-경로1*)=확률a,

        pr(경로1<-경로0)=확률 1-a

 

만약 새로운 경로1로 바뀌면 이 바뀐 경로1의 이웃을 다시 생각합니다.

 

이런식으로 계속 경로1, 경로2, 경로3으로 찾아가면 나중에는 가장 짧은 거리를 가진 경로를 찾아 낼 수 있습니다.

 

 

알파고의 경우도 아마 비슷할겁니다. 100수까지 뒀다고 생각하고 이후 두는 수는 5수까지만 앞을 본다고 하죠. 백 차례고요. 그럼 백-흑-백-흑-백 이렇게 두겠죠.

 

그런데 바둑판의 점을 세일즈맨 문제에서 도시라고 생각하시면 되겠죠. 바둑판도 좌표가 있잖아요, 그리고 상대방 흑도 자신도 최선의 수를 선택하려고 노력하겠죠, 그럼 흑, 백 구별은 그리 중요한 것 같지는 않습니다. 제 느낌에요.

 

그럼 다음 경로는 바둑판 자표로 (64, 57)->(57, 58)->(43, 24)->(38, 45) -> (42, 57), 이렇게 세일즈 맨 문제처럼 경로를 생각할 수 있을 겁니다. 그런 다음 이 경로의 이웃을 생각하고 여기서 이길 확률이 높으면 항상 선택하고, 이길 확률이 낮아도 어떤 확률을 가지고 선택하고 한다는 것이죠.

 

이길 확률은 지금까지 사람들이 둔 수많은 바둑판에서 이미 계산이 되어 있겠죠. 빅데이터죠.

 

 

아마 이것과 비슷한 개념으로 하지 않았을까 생각합니다. 논문을 읽어보지는 않아서요.

 

여기서 우리가 기억해야 할 것이 있습니다.

 

1) 쓸데없이 버리는 경우가 있습니다. 열심히 새 경로를 찾아서 계산을 했는데 새 경로로 이동하지 못하고 옛날 경로를 계속 유지해야 하는 경우가 있습니다.

 

2) 마음에 안드는데도 어떤 확률을 가지고 새로운 경로로 이동해야 하는 경우가 있습니다. 그럼 이 확률값은 어떻게 줘야 할까요.

 

여기서 Metropolis 알고리즘은 역열학에서 나오는 수식을 사용합니다. 그 다음 Hastings에 의해 이 확률 수식이 일반화가 됩니다.

 

그래서 Metropolis-Hastings 알고리즘이라고도 합니다. 이게 바로 MCMC입니다. pr(다음 경로j | 현재 경로i)가 정의되는데 이게 Markov Chain 모양을 하기 때문입니다.

 

 

2. 몬테칼를로 시뮬레이션과 유사성

 

 

일반적으로 어떤 확률 분포 f(x)에서 랜덤넘버를 생성하는 방법은 inverse 방법을 사용합니다.

 

inverse 방법은 누적확률분포 F(x)를 사용합니다. 누적확률분포가 0에서 1 사이에 값을 취하기 때문에

 

F(X) ~ U[0, 1]

 

을 할거라고 기대할 수 있습니다. 실제로 누적확률분포 F(X)는 0과 1 사이의 균등분포를 합니다. 증명은 보면 너무 쉽습니다. 한 줄도 안됩니다.

 

F(X)=U이기 때문에 X=invF(U) 됩니다. 따라서 확률분포 f(x)에서 랜덤넘버 x를 생성하려면 균등분포 U에서 랜덤넘버 u를 생성한 다음 위 공식에 넣어 x를 구하면 됩니다.

 

그래서 매우 간단한데 문제는 누적확률분포 F(x)를 구하기가 쉽지 않다는 것입니다. 대표적으로 정규분포 f(x)의 누적확률분포 F(x)는 정확한 수식을 아직도 모릅니다.

 

그래서 f(x)가 골치아픈 모습을 할 때는 어떻게 랜덤넘버를 생성할 수 있을까 하는 생각을 할 수 있습니다. 이때 쓰는 방법이 rejection 방법입니다.

 

f(x)와 비슷하고 쉽게 계산할 수 있는 g(x)라는 새로운 분포를 생각합니다. 기본적인 생각은 그런 다음 g(x)에서 랜덤넘버 x를 생성한 다음 f(x)와 g(x)를 비교합니다. f(x)/g(x)를 계산합니다.

 

만약 g(x)에서 x를 생성한 다음

 

1) g(x)=1/4, 즉 확률 1/4, f(x)=1/3, 즉 확률 1/3이면

 

이 x를 선택하면 나중에 어떻게 될까요, 랜덤넘버 10000만 생성하면 이 중 x가 10000개 중 1/3 정도 나와야 하는데 실제로는 10000개 중 1/4만 나옵니다. 우리의 목적은 f(x)에서 난수를 생성하는 것이지 g(x)에서 난수를 생성하는 것이 아닙니다. 그래서 원래 나와야 하는 것보다 훨씬 적게 뽑혀 나옵니다.

 

2) 반대로 g(x)=1/4, 즉 확률 1/4, f(x)=1/5, 즉 확률 1/5이면

 

10000개 중 원래는 1/5 정도 나와야 하는데 1/4 정도 나와서 이젠 너무 많이 뽑혀 나옵니다.

 

이걸 해결하기 위해 g(x)에서 1보다 큰 값 B를 곱해서 g(x)를 크게 한 다음 해서 어떤 확률을 가지고 선택하거나 포기하는 방법을 사용합니다.

 

그런데 이렇게 선택하지 못하고 포기하는 난수가 너무 많으면 이 알고리즘은 너무 비효율적입니다. 그래서 나온 것이 importance sampling입니다.

 

여기서 선택하고, 포기하는 것, 그리고 선택할 확률, 포기할 확률을 결정하기 위해서 어떤 새로운 확률뷴포 g(x)를 생각한다는 점이 MCMC 알고리즘과 일맥상통하는 점이 있습니다.

 

 

3. 베이지안(Bayesan)

 

 

앞에서 몬테칼를로 알고리즘을 이용해서 다양한 기댓값을 구할 수 있다고 했습니다.

 

통계학에서 가장 중요한 값이 평균 E[X]입니다. 관심있는 현상의 전반적인 경향성을 보여주는 값이기 때문입니다.

 

그럼

 

E[X]=∫x*f(x)

 

에서 지난번에 하듯이 f(x)에서 랜덤넘버 x1, x2, x3,..., xn 을 뽑아낸 다음 (x1+x2+, ..., xn)/n 하면 이 적분값, 즉 기댓값을 구할 수 있습니다. 즉 표본평균을 구한 것입니다. 이 표본평균이 n이 무한대로 가면 E[X]로 수렴을 하는 것입니다.

 

 

이것은 베이지안에서는 매우 중요합니다. 베이지안의 경우(u는 우리가 추정해야 할 모수입니다).

 

E[U]=∫u*f(u|x)=∫u*사후확률분포

 

여기서 사후확률분포 f(u|x)가 매우 복잡하면 우리가 계산하듯이 E[U}를 풀어 낼 수가 없습니다. 따라서 대부분 이 사후확률분포가 간단하게 나올 수 있게끔 만드는 사전확률 g(u)를 고려합니다. conjugate family라고 하죠.

 

그러나 사후확률분포가 복잡하더라도 앞에서 이야기한 몬테칼를로 알고리즘을 사용하면 그냥 f(u|x)에서 랜덤넘버를 생성해서 표본평균을 구하기만 하면 됩니다.

 

 

그러나 또 하나의 난관이 있습니다. 우리가 추정해야 하는 모수 u가 하나이면 위의 방법을 쓰면 되는데 모수가 여러 개 즉, u1, u2, u3,...일 경우 어떻게 해야 할 건가입니다. 이건 특히 Hierarchical Bayesian model에서 중요한 문제입니다.

 

이 문제를 해결해 줄 수 있는 알고리즘이 Gibbs sampler입니다. Geman & Geman의 이미지 복원 논문에서 나온 유명한 알고리즘입니다. 이 알고리즘이 MCMC의 특수한 경우로 이미 증명되어 있습니다.