[베이지안 추론] Metropolis Algorithm(1)

Chapter 7. Inferring a Binomial Proportion via the Metropolis Algorithm

A simple case of the Metropolis algorithm

사전 확률 분포가 우도 함수와 conjugate 하다면 분석적으로 풀어낼 수 있는 사후 확률 분포를 만들 수 있다. 하지만 theta 값의 분포가 베타 분포를 따르지 않고 따라서 풀기 힘든 경우들도 있다. Grid approximation을 활용해서 이 문제를 어느 정도 해결 할 수도 있다. 하지만 이것 또한 단일 변수를 포함하는 모델의 경우이고, 더욱 변수가 많은 모델의 경우에는 어떻게 될까. 만약 우리가 6개의 변수를 가진 모델을 가졌다고 가정하자. 이런 상황에서 1000개의 격자(grid)로 나누어 모든 경우의 수를 생각하면 10의 18승에 해당하는 엄청 큰 공간을 탐색해야 한다. 이렇게 격자 방법론도 통하지않는 경우에, 새로운 방법론을 써야만 한다.
이 챕터는, 우리가 쉽게 알아낼 수 있는(evaluate)함수를 통해 사전 확률 분포가 추정 될 수 있음을 알려준다. 아주 쉽게 말하면, 우리가 $\theta$ 값을 특정하기만 하면, 우리는 $P(\theta)$값을 알아낼 수 있다는 것이다. 분포로부터 샘플링 할 수 있는 많은 수의 theta 값들로 부터 우리는 사후 확률 $p( \theta |D)$의 추정값(approximation)을 얻어낼 수 있다. 카지노 게임에서 우리가 계속해서 랜덤한 값을 얻을 때, 그를 이용하여 분포를 추정할 수 있듯이, 우리가 사후 확률 분포로부터 계속해서 랜덤으로 얻어낸 값들을 활용하여 사후 확률 분포를 알아낼 수 있다. 이러한 접근법을 Monte Carlo 방법이라고 한다.

베이지안 추론의 목표는, 파라미터 들에 의한 사후 확률 분포에 대한 좋은 이해를 하는 것이다. 그렇게 하는 한가지 좋은 방법은, 사후 확률 분포로부터 많은 수의 대표값들을 추출하고, 그 값들로부터 분포에 대한 descriptive 통계 수치들을 계산하는 것이다.

우리가 추정하길 원하는 사후분포에서 데이터들을 계속해서 얻어내고, 이 값들을 이용해 평균이나 표준편차 등을 계산하는 것을 말한다. 우리가 알아내고자 하는 사후 분포는 특정 함수의 형태 또는 수식이라고 볼 수 있는데, 이 함수에서 특정 값을 얻어내고 그 값의 획득을 반복하며, 해당 값들의 특징을 추정하고 마지막으로 함수에 대한 이해를 하는 것이라고 이해하면 편하다.

예를 들어, 베타 분포($beta(\theta|a,b)$) 에서 우리는 분포의 평균 값과 표준 편차 값이 $a , b$에 의해 분석적으로 계산되고 표현 될 수 있다는 것을 배웠다. 하지만, 우리가 평균과 표준편차에 대한 분석적 공식을 모르고, cumulative probabilities 또한 계산할 직접적인 방법이 없다고 가정해보자. 하지만, 우리는 현재 그 분포로부터 대표값들을 추출해 낼 방법은 있다고 가정해보자. 이러한 랜덤 값들은 spinner(시계나 다트판 같은) 로부터 만들X어 질 수 있고, 이 값들은 0에서 1까지의 연속적인 값을 갖는다 : possible $\theta$ value라고 하자. 이 스피너의 $\theta$ 값들은 $beta(\theta|a,b)$ 분포에 따라서 편향(biased)돼 있다.

베타 분포의 경우엔, 우리가 모수 a,b를 아는 경우 해당 분포 함수를 명확하게 그릴 수 있을 뿐더러, 해당 값들의 평균 값과 표준편차 또한 쉽게 계산할 수 있다. 하지만 대부분의 real value data들이 베타 분포를 따르는 경우가 아니므로, 우리는 차선책에 대해 공부할 필요가 있다.

우리는 이 스피너를 수천 번 돌렸고, 그 값들을 모두 기록한다. 이 값들은 기저에 놓인 베타 분포의 대표값들이고, 이 샘플 값들이 나오게 된 population(모수?) 가 베타 분포가 된다. 이 샘플들의 평균 값은, 기저에 놓인 분포의 평균 값과 거의 비슷할 것이고, 표준편차 또한 그러할 것이다. percentile들도 마찬가지. 다르게 말하면, 우리가 만약 매우 충분한 양의 대표값들을 얻어내면 그 값들이 모분포의 특징을 잘 나타내주는 값들을 대신할 수 있다는 것이다. 그렇다면 다음 질문은 무엇일까?

그래서 어떻게 충분히 많은 양의 대표값들을 분포로부터 얻어낼 것인가?

7.1.1 A politician stumbles upon the Metropolis algorithm

재미있는(?) 그럴듯한 예시를 들어보자. 대중의 눈높이에 맞춰 머무르길 원하는 한 정치인이 섬에서 섬으로 여행을 끊임 없이 하고 있다. 이 정치인이 거주하는 이 섬나라는 여러 개의 섬이 연결 된 long chain 형태이다. 끊임 없는 사진 찍기와 모금 운동(…)이 끝나갈 무렵, 그는 현재 섬에 머무를지, 근접 서쪽 섬으로 움직일지, 근접 동쪽 섬으로 움직일 지 결정을 해야만 한다. 그의 목표는 섬들의 상대적인 인구에 비례하여 모든 섬들을 방문하는 것이다.

그는 인구가 가장 많은 섬에서 가장 오래 머무르길 원하며, 인구가 가장 적은 섬에서는 그에 비례하여 가장 적은 시간을 머무르길 원한다. 이 정치인은 전체 섬이 몇 개인지도 모르며, 전체 인구가 몇인지도 모른다. 그의 보좌진들은 이러한 무능력에도 불구하고 최소한의 정보를 얻는 데에는 능력이 있다고 한다. 그들이 모금 운동에 엄청 바쁘지 않을 때, 그들이 머무르고 있는 섬의 시장에게 해당 섬에 얼마나 많은 사람들이 있는지 물어볼 수 있다고 한다. 그리고 이 정치인이 근접 섬에 방문하기로 제안을 할 때, 그들은 그 근접 섬의 시장에게 얼마나 많은 사람들이 그 섬에 있냐고 또한 물어볼 수 있다. 이 정치인은 제안된 섬으로 여행을 할지 말지 결정할 간단한 경험적 법칙을 갖고 있다

평평한 코인을 던져서, 동쪽으로 갈지 서쪽으로 갈지 결정한다. 만약 해당 섬이 현재 섬보다 많은 인구가 있다면 그는 그 섬으로 당연히 가야한다.

뒤에서 다시 나오겠지만 여기에서 ‘코인을 던져서 얻게 되는 확률’ 과 관련된 함수를 proposal function이라고 부른다. 미리 숙지하면 편하다.

반면에 만약 제안된 섬이 현재 섬보다 적은 인구를 갖고 있다면, 그는 해당 섬에 오직 확률적으로 방문하는데, 이때 확률은 지금 방문하려는 섬과 현재 섬의 인구 비율로 결정한다. (만약 지금 머무르는 섬의 인구가 100이고 가려는 섬이 60이라면, 60%의 확률로 방문한다는 뜻)

위의 논리를 간단히 표현하면, $P_(move) = P_(proposed) / P_(current)$가 된다. 이 정치인은 0부터 1까지의 숫자들이 유니폼하게 적혀있는 공평한 스피너를 돌려가며 이러한 선택을 계속 한다.

위의 그림과 같이 4번 섬에서 출발한 정치인은 random walk를 지속하게 된다. 4번 섬에서 7번 섬까지는 인구에 따라 계속해서 오른쪽으로 이동하다가 확률적으로 왼쪽으로 가는데에는 힘들어하는 모습이 보인다.

7.1.2 A random walk

이런식으로 움직이는 정치인의 island hopping에 대해 휴리스틱(계속 경험해보며)하게 더 살펴보자. 이 chain들에 총 7개의 섬이 있다고 가정해보자. 해당 섬의 상대적 인구들은 Figure 7.1의 아래 막대 그래프로 나타내 있다. 해당 섬들의 상대적 인구는 $p(\theta) = \theta$에 선형적으로 비례해서 증가한다.(중요)

가운데에 있는 trajectory path는 가능한 경우의 수들 중 하나이다. 이러한 random path를 따라 움직임을 반복하다보면 가운데 위의 세 개 plot들 중 가운데 plot이 보여주는 path accumulation을 얻게 되고, 이를 이용해 빈도 히스토그램을 그리게 되면 맨 위와 같다.

7.1.3 General properties of a random walk

Figure 7.2는 각각의 포지션에 있을 확률을 시간의 함수로 보여준다. 맨 처음 $t = 1$에서 이 정치인은 $\theta = 4$ 에 있었다. 다음 시간 $t = 2$에서 어떤 포지션에 있을 지에 대한 확률을 결정하기 위해서, 움직임의 과정으로 부터 확률들을 고려해보자.

$t = 1$ 에서 $t= 99$ 값으로 계속 시행 함에 따라, 특정 점이 특정 theta에 위치할 확률은 시간에 따라 위 그래프와 같게 된다.

조금 더 구체적으로 살펴보자. $t = 1$ 시점에서 동전을 한 번 던지고, 이 동전은 우리가 서쪽으로 갈지, 동쪽으로 갈지 정해준다. 만약 동전이 우리에게 서쪽으로 갈 것을 제안(proposal)했다고 생각해보자. 하지만 현재 우리가 위치한 4번 섬에 비해 3번 섬의 인구는 $3/4$밖에 되지 않으며, 따라서 $1/4$의 확률로 해당 제안은 reject된다. 그에 반해, 만약 동전이 동쪽으로 이동하길 제안한 경우, 우리가 위치한 4번 섬의 인구보다 5번 섬의 인구가 많기 때문에 이 제안은 무조건적으로 받아들여진다.

이와 같은 논리로 $t$가 지남에 따라 각각의 $P(\theta)$값이 표현된다.

$ t = 4$ 정도 까지는 직접 계산해보길 추천한다. 그렇다면 우리가 이 과정에 어떤 문제와 고민을 안게 되는지 이해할 수 있다. 뒤에 나오는 간단한 matrix arithmetic에 관해서도 동기와 목적이 이해될 것이다.

7.1.4 Why we care

이렇게 간단하게 경험한 랜덤 워크 프로세스에서 우리가 할 수 있어야만 하는 것들!

We must be able to generate a random value from the proposal distribution (to create $\theta_{proposed}$).
We must be able to evaluate the target distribution at any proposed position (to compute $P(\theta_{proposed})/P(\theta_{current})$).
We must be able to generate a random value from a uniform distribution (to make a move according to $p_{move}$)

Proposal 분포에서 랜덤 값을 추출할 수 있어야만 한다. 어떠한 proposed 포지션에서도 타겟 분포의 값을 평가할 수 있어야만 한다.(Figure 7.2처럼 시행에 따라 계산을 하고 만들 수 있어야 한다.)

$p_{move}$ 에 따라서 움직임을 가져갈 수 있도록 유니폼 분포에서 랜덤 값을 생성해낼 수 있어야만 한다. 위의 세가지 과정을 우리가 할 수 있음에 따라, 우리가 직접적으로 할 수 없던 무엇인가 를 간접적으로 해낼 수 있다. target distribution으로부터 랜덤 샘플을 우리가 추출하는 것, 더 나아가서 target 분포가 normalized 돼있지 않아도 우리는 target 분포로부터 랜덤 샘플링을 진행할 수 있다. $P(\theta)$ 라는 타겟 분포가 $P(D|\theta) * P(\theta)$에 비례하는 사후 분포이면 이 기술은 더욱 더 유용하다. 단지, $p(D|\theta) * p(\theta)$ 값만 알아냄으로 인해서, 우리는 사후 분포의 랜덤한 대표 값들을 생성해낼 수 있다. 이런 방법을 활용하면 우리는 $P(D)$ (evidence) 값을 계산하지 않아도 되어 매우 편리해 진다. 특히 이 evidence 값은 베이지안 추론에서 가장 어려운 부분이기 때문에 더욱 유용하다고 볼 수 있다. MCMC 테크닉을 사용함으로써, 우리는 베이지안 추론을 더욱 더 풍부하고 복잡한 모델에서도 진행 할 수 있다. 베이지안 추론이 더욱 복잡한 데이터 분석에서 활용 가능하게 됐던 것은 오직 MCMC 기술의 발전 덕분이다. 그리고 더욱 많은 사람들에게 접근 가능하게 된 것은 값 싸고 빠른 컴퓨터의 보급 덕이라고 볼 수 있다.

——— MCMC 덕에 베이지안 확률 추론이 가능해 졌다. 이 부분에 대해 더욱 직관적인 이해가 필요하다. ————

7.1.5 Why it works

이 알고리즘의 작동 뒤에 숨어 있는 수학적 이해에 대해 조금 더 설명해보자. 이 간단한(?) 케이스에 대한 수학적 설명을 제공하는 것의 목표는, 다음 섹션에서 이 직관적 이해를 조금 더 의미화 시켜서 더욱 일반적 알고리즘으로 도약하기 위함이다. 이 섹션에서 만약 우리가 좋은 시작 점을 잡아 놓는 다면, 다음 섹션에서 더욱 쉽게 도약할 수 있을 것이다. (ㅎㅇ) 왜, 어떻게 이 알고리즘이 작동 하는지에 대한 직관을 얻기 위해, 근접한 (adjacent) 두 개의 포지션을 고려하자, 그리고 한 점에서 다른 점으로 이동하는 확률에 대해 생각을 해보자. 근접한 두 점 사이에서 상대적인 transition(movement) 확률은 정확하게 target 분포의 상대적 값과 같다는 것에 대해 살펴볼 것이다. 매우 긴 시간에 걸쳐 우리가 계속해서 이 시행을 반복하게 되면, 각각의 포지션이 방문될 확률은 해당 타겟 값과 비례할 것이다. 위치 $\theta$ 에서 다음 위치 $\theta + 1$ 로 이동할 확률을 $p(\theta -> \theta+1)$ 이라고 표현하자. 그리고 이것은 해당 방향으로 움직이라고 제안할 확률과, 그 제안이 받아들여질 확률의 곱과 같다 ; $0.5 * min(P(\theta+1) / P(\theta), 1)$.

위의 식을 통해서, 앞 뒤 근접 포지션으로 움직이는 transition들 동안, 상대적 transition들의 혹률은 정혹하게 타겟 분포의 상대적 값과 일치한다는 것을 알 수 있다.이 식을 통해 우리는 직관적인 이해를 얻었다. ( 타겟 분포의 값에 비례하여 우리가 결과적으로 해당 포지션에 방문한다는 것) 이 직관을 조금 더 우리가 단단하게 방어할 수 있기 위해서, 우리는 약간의 디테일을 더해줘야 한다. 이를 위해 매트릭스 arithmetic을 봐보자. 이 책에서 유일하게 matrix arithmetic이 나타나니까, 이 내용이 이해가 안될지라도 너무 겁먹지 말자. 우리가 놓칠 수도 있는 것은, Figure 7.2의 기저에 놓여 있는 수학에 대한 설명인데, 그 수학적 설명은 해당 타겟 분포가 stable하다고 하는 것이다.(결국 랜덤하게 어떻게 걷더라도 마지막 분포는 같은 값으로 수렴한다는 것이다.)포지션 $\theta$에서 다른 포지션으로 이동하는 확률을 생각해보자. 이 간단한 현재 시나리오에서 오직 포지션 $\theta-1$ 과 $\theta+1$ 만을 고려하는 proposal 분포가 있다. 만약 제시된 포지션이 받아들여지지 않는다면, 우리는 $\theta$ 위치에 머무르게 된다. 포지션 $\theta - 1$로 이동하게 될 확률은, 해당 포지션으로 이동하라고 제안을 할 확률과, 그 제안이 받아 들여질 확률의 곱과 같다. $\theta + 1$로 이동하게 될 확률 또한 마찬가지이다. 제 자리에 머물게 될 확률은 위의 두 확률의 여집합의 합과 같다.

방금의 이야기를 $\theta - 2$ 에서 $\theta + 2$까지의 행렬로 나타내면 다음과 같다.

위의 행렬을 계산식으로 표현하면 아래와 같다.

위와 같이 transition 확률들을 매트릭스 안에 표현하는 것은 유용하다. 이 매트릭스를 사용해서, 모든 장소로 최종적으로 위치하게 될 확률을 확률들의 곱으로 나타낼 수 있다.

Z는 모든 $P(\theta)$의 합이며 이것은 타겟 분포에 대한 normalizer로 역할을 한다. $P(\theta)와 P(\theta-1)$, $P(\theta+1)$과의 각각의 대소 관계는 총 4가지 경우의 수를 갖는다.

케이스 1의 경우에, 식 (7.4)는 다음과 같다.

각 계산식 단계를 따라 정리를 해보면 마지막으로 $P(\theta)/Z$ 를 얻게된다. stay한다는 결론을 얻을 수 있다. Metropolis 알고리즘 하에서 타겟 분포가 stable하다는 것을 보여주었다. 이는 우리가 어떤 지점에서 시작하던지 상관 없이 같은 결과를 이끌어 낸다는 것 또한 보여준다. 우리가 어떤 시작점에서 이 알고리즘을 시작하는 가와 상관없이, 이 분포는 자연스럽게 확산(diffusion)하여 다른 포지션으로 이동한다. 이러한 확산은 어떤 안정적인 상태로 자리잡게 되고, 우리의 분포 또한 결국 확정적 상태에 머무르게 될 것을 보여준다.

PREVIOUS [코드리뷰] TFFM: TensorFlow FactorizationMachine

NEXT [베이지안 추론] Metropolis Algorithm(2)