4.7 Population Monte Carlo
Population-Based MCMC. population이란? 즉, multiple 체인을 돌린다는 것. 로컬 트랩 문제를 회피하기 위해서. 이는 이하의 조건을 탄다.
- 각 체인이 가지는 분포는 서로 달라야 하지만, 아예 그 분포들끼리 아예 무관해서는 안된다. (2번을 위해)
- 체인들 간에 정보의 교환이 이루어져야 한다. 서로가 가지고 있는 정보를 공유하는 것으로 체인들의 타겟 분포로의 수렴을 가속시키는 것이 이 여러개의 체인의 존재 목적이기 때문이다.
이는 패러렐 컴퓨팅을 가능하게 한다.
- Embarrassingly Parallel MCMC
언급하였듯 위의 다중체인은 서로간에 정보의 교환이 이루어져 속도가 다소 느려지는 측면이 분명히 생긴다. 이러한 발목잡힘을 피하기 위해 체인간의 정보교환이 전혀 없는 MCMC.
타겟분포 \(f(x)\)에서 샘플 생산.
f(x_1 , , x_N)=_{i=1}^N f_i (x_i)
이때 f(x)와 f_i(x_i) 사이에는 반드시 연관이 존재해야 하며, 적어도 하나의 i값에 대해 f(x) = f_i(x_i)를 만족해야 함.
N은 체인의 갯수, 혹은 population의 size.
4.7.3 Parallel Tempering
temperature 개념 사용. 따라서 T_1>T_2>>T_n=1 이어야 하며, T_n은 타겟분포에 상응한다. 이때 각 temperature에 대응하는 pdf f_i(x) ( - )
simulated tempering은 temperature를 생산해서 해당 temperature를 accept한 후 해당 temperature로 이동. Parallel Tempering은 n개의 온도에 대응하는 체인 n개를 만들어 각각의 온도에 대응시킨 후 n개의 체인을 병렬적으로 돌림. 이때 높은 온도인 T_1은 넓은 space를 탐색하고 낮은 온도인 T_n은 좁은 space를 탐색. 이때 태생의 온도에 따라 탐색시키는 것은 탐색 효율이 떨어지므로 체인이 일정 경과할 때마다 swapping (Exhange) opertation을 하여 출신 이외의 다른 체인과 서로 바꿈. 이 바꿈은 인접한 체인과만 발생. 이를 통해 상황이 맞아떨어지면 T_1 출신의 탐색자가 T_n까지 가서 탐색하는 상황도 나올 수 있음. 이러한 swapping opertation을 Auxiliary Variable Generation까지 확장시킨 것이 Exhange Algorithm.
Proceeds: 1. local MH. MH 알고리즘을 통해 X_i^{(t)} X_i^{(t+1)} 로 업데이트. 2. Exhange 스텝. 인접한 체인이 2개라면 각각으로 이동할 확률을 0.5로 잡고, 1개라면 서로밖에 교환 못하니 이는 1로 설정. 이후 해당 교환을 accept할지 여부는 확률 { 1, ; ; ; }에 따라 결정. 이외면 교환 안 한 채로 남긴다.
이를 고차원으로 확장시키면 Sequential Parallel Tempering.
4.7.4 Evolutionary MC
Combinatorial Optimization Problem, 무수히 많은 조합 중에 local optimal 찾는 문제에서 가장 자주 사용되는 방법론인 genetic Algorithm, 의 MC 버전이라고 볼 수 있다. 다른 모델, 크로스오버 (스위치), 뮤테이션.
다만 Evolutionary MC 자체는 Combinatorial Optimization을 푼다기보단 Multimodal 문제를 푸는 용도에 가까움. genetic Algorithm과 Evolutionary MC 둘 모두 local mode를 찾는 알고리즘, local Trap 문제를 해결하는 알고리즘.
또한 Evolutionary MC는 local trap 해결 이외에 Variable Selection에도 아주 유용하며 자주 사용됨. 이 Variable Selection 자체가 일종의 Combinatorial Optimization 문제로 생각될 수 있음. 가용 변수의 조합 중 어떤 조합을 써야 효율이 잘 나올 것인가를 고민하는 거니까.
Evolutionary MC 또한 temperature 개념을 사용하므로 parallel Tempering과 유사. 온도 설정과 온도에 따른 체인 설정 후 탐색은 완전히 똑같지만, parallel tempering의 swapping operator가 바로 인접한 체인과의 교환만 발생했던 반면 evolutionary MC는 crossover operator를 사용하여 인접한 것만이 아닌 모든 체인 중에 교환할 체인을 선정. 이렇게 교환 범위가 넓기 때문에 parallel tempering보다 성능이 훨씬 좋음.
Proceeds:
1. Mutation은 자주 일어나는 일이 아니므로 확률로 판정하여 Mutation과 Crossover 둘 중 하나만 일어나도록 함. Mutation의 확률은 q_m, Crossover의 확률은 1-q_m. 이 확률 q_m은 uniform에서 획득. 잘 모르면 0.5.
1. Local MH. 이는 genetic Algorithm에서의 Mutation에 대응.
x_1 , , x_N 중 1개를 균일확률로 선정해서 뽑고 뽑은 그 x_k 1개에 대응하는 y_k = x_k + e_k 를 만들어 이로 대체할 것을 제안. 이는 (1, r_m)의 확률로 accept되고, 이때 accpetance ratio r_m = { - } . 이때 뒤쪽의 fraction은 proposal density에 해당.
2. Crossover Operator: (1) 현 population x에서 x_i를 고른 후, (2) x / x_i 에서 x_j 를 고른다. 이때 x_j를 선정할 때 ( - )의 확률에 따라 선정한다. k는 앞서 선정되었던 i를 제외한 모든 수. (3) e=x_i - x_j, y_i = x_j + r e. 이때 r은 direction에 해당하며 모든 실수일 수 있고, r의 선정은 density f(r) r ^{d-1} f(x_i + re)에 따른다. (4) 여기서 획득한 y_i로 x_i를 교체한 후 이렇게 교체한 집합을 새로운 population으로 삼는다.
3. Exchange 스텝. 이를 통해 X 내용물을 구성하는 \(x_i\), 즉 각 온도 H(x_i) 에 대응하는 chromosome들의 교환이 이루어짐. Exchange Operator: parallel tempering과 마찬가지로 양옆의 것들과 확률 판정해서 교환.