기브스 표집

기브스 표집(Gibbs sampling)은 두개 이상의 확률 변수의 결합 확률 분포로부터 일련의 표본을 생성하는 확률적 알고리즘으로, 결합 확률 분포나 그에 관련된 확률 계산을 근사하기 위해 사용된다.^[1]

기브스 표집은 메트로폴리스-해스팅스 알고리즘의 특별한 예이고, 따라서 마르코프 연쇄 몬테 카를로 알고리즘의 한 예이다. 이 알고리즘은 물리학자 조사이어 윌러드 기브스의 이름을 따서 명명되었다.

알고리즘

$n$ 개의 확률변수 $(X_{1},\cdots ,X_{n})$ 의 결합 확률 분포 $p(x_{1},\cdots ,x_{n})$ 로부터 $k$ 개의 표본 $X$ 를 얻으려고 할 때, 기브스 표집은 다음과 같이 동작한다.

임의의 $X^{(0)}=(x_{1}^{(0)},\cdots ,x_{n}^{(0)})$ 을 선택한다.
각 변수 $x_{1},\cdots ,x_{n}$ 에 대하여, 현재의 값을 기반으로 한 새로운 값을 조건부 확률분포 $p(x_{i}^{(t)}|x_{1}^{(t)},\cdots ,x_{i-1}^{(t)},x_{i+1}^{(t-1)},\cdots ,x_{n}^{(t-1)})$ 에서 표집한다.
$X^{(t)}=(x_{1}^{(t)},\cdots ,x_{n}^{(t)})$ 를 $X$ 에 추가한다.

실제 사용 시에는 처음 수집되는 표본을 사용하지 않고 버리게 된다. 이것은 기브스 표집에서 수집되는 표본은 서로 독립적이지 않고 마르코프 연쇄에 속하기 때문인데, 표본의 앞 부분은 초기 상태 $X^{(0)}$ 에 크게 의존하지만 충분히 많은 시행이 지난 후에는 초기 상태에 관계없이 $p$ 에 기반한 표본을 수집할 수 있다.

조건부 확률분포와 결합 확률분포의 관계

위의 조건부 확률분포는 결합 확률분포에 비례한다.

p(x_{j}|x_{1},\dots ,x_{j-1},x_{j+1},\dots ,x_{n})={\frac {p(x_{1},\dots ,x_{n})}{p(x_{1},\dots ,x_{j-1},x_{j+1},\dots ,x_{n})}}\propto p(x_{1},\dots ,x_{n})

수학적 배경

기브스 표집에서 주어진 표본 $x$ 에 대하여, $i$ 번째 변수를 변경하여 다음 표집 $y$ 을 수집할 확률은 다음과 같다.

\Pr(x|y)={\begin{cases}{\frac {p(y)}{\sum _{z\in \Theta :z\sim _{i}x}p(z)}}&x\sim _{i}y\\0&{\text{otherwise}}\end{cases}}

여기에서 $\Theta$ 는 모든 가능한 표본의 집합을 의미하며, $x\sim _{i}y$ 는 $x$ 와 $y$ 가 i번째를 제외한 모든 값이 같다는 것을 의미한다. 이때 다음의 성질이 성립한다.

p(x)\Pr(y|x)=p(y)\Pr(x|y)

이러한 성질은 변수를 하나만 변경하는 것이 아니라 각 변수를 차례대로 변경하여 $x^{(t-1)}$ 에서 $x^{(t)}$ 를 얻을 때에도 동일하게 보존된다.

이때 $\Theta$ 와 위의 표집 확률을 기반으로 하는 마르코프 연쇄를 구성하면, 이 마르코프 연쇄는 가역적(reversible)이다. 가역적 성질은 정상(stationary) 성질을 포함하는데, 이것은 표본을 연속적으로 수집할 때 표본의 수집 확률은 초기 표본에 관계없이 $p$ 에 수렴한다는 것을 의미한다.

단점

기브스 표집은 변수를 하나씩 바꾸어가며 표본을 수집하기 때문에, 중간 상태의 확률이 작을 경우 올바른 근사를 위해 많은 표본이 필요하다는 단점이 있다. 가령 0과 1의 두 값을 갖는 변수 두 개에 대한 확률 분포 $p(x_{1},x_{2})$ 에 대하여, $p(x_{1}=0,x_{2}=0)$ 과 $p(x_{1}=1,x_{2}=1)$ 의 값은 높지만 $p(x_{1}=0,x_{2}=1)$ 과 $p(x_{1}=1,x_{2}=0)$ 의 값이 작을 경우, $(0,0)$ 에서 $(1,1)$ 를 표집하기 위해서는 $(0,1)$ 이나 $(1,0)$ 을 먼저 지나쳐야 하지만 이들의 확률이 작기 때문에 표본이 적을 경우 잘 표집되지 않을 수 있다.^[2] 특히 $p(x_{1}=0,x_{2}=1)$ 과 $p(x_{1}=1,x_{2}=0)$ 이 0일 때에는 표집이 불가능한데, 이것은 기브스 표집이 가정하는 마르코프 연쇄의 정상 성질이 깨지기 때문이다.