22. More variational inference

22.1. Introduction

앞 장에서는 주변분포의 곱으로 사후분포를 근사하는 평균 장 추론법에 대해 알아보았다. 이는 각 변수에 대해 다른 매개화를 가능케 해서 통계적 모델의 매개변수에 대한 베이지안 추론을 할 수 있게 한다.

이 장에서는 약간 다른 종류의 변분 추론을 다룬다. \tilde{p}가 표준화되지 않은 정확한 사후분포일 때 J(q) = \mathbb{KL}(q \vert \vert \tilde{p})를 최소화시키는 것은 똑같으나, q가 인수분해된다는 가정을 하지 않고, 심지어 전역적으로 올바른 결합분포라는 가정도 하지 않는다. 대신, 오로지 국소적으로 일관적인 분포라는 것만을 가정한다. 즉, 두 개의 인접한 노드의 결합분포가 해당되는 주변분포와 맞는다는 것을 가정한다. 또한, 이산적인 그래프 모델에 대한 최대사후확률상태추정에 대한 근사를 수행한다. 이는 주변분포를 계산하는 근사법과 비슷하다.

22.2. Loopy belief propagation: algorithmic issues

이산적이거나 가우시안인 그래프 모델에 대한 간단한 근사 추론 알고리즘으로 순환적 믿음 전파(LBP)가 있다. 기본 아이디어는 믿음 전파 알고리즘을 트리가 아닌 그래프에 대해서도 사용하는 것이다. 이 알고리즘은 잘 동작한다.

22.2.1. A brief history

믿음 전파 알고리즘은 순환이 있는 그래프에 적용했을 때 올바른 결과를 낸다는 보장이 없으며 수렴한다는 보장도 없다. 하지만 근사의 방법으로서는 적용 가능하다.

22.2.2. LBP on pairwise models

먼저 쌍별 인자가 있는 비방향 그래프 모델에 순환적 믿음 전파를 적용하는 법을 알아보자. 방법은 그저 노드간 메시지의 전송/수신을 수렴할 때까지 반복하는 것이다.

22.2.3. LBP on a factor graph

고차 클리크 잠재함수가 있는 모델을 다루기 위해서는 그래프의 표현을 인자 그래프라는 표현으로 바꾼다.

22.2.3.1. Factor graphs

인자 그래프는 방향그래프와 비방향그래프 모델을 통합하는 그래프 표현으로서 특정한 메시지 패싱 알고리즘을 간소화한다. 정확히는, 인자 그래프는 두 종류의 노드가 있는 비방향 이분그래프이다. 동그란 노드는 변수, 사각형 인자는 인자를 나타내며, 모든 변수에 대해 그를 언급하는 인자에 대해 간선을 긋는다.

22.2.3.2. BP on a factor graph

이제 인자 그래프에 적용되는 믿음 전파 알고리즘을 유도해 보자. 변수에서 인자로 가는 메시지는 다음과 같다:

m_{x \to f}(x) = \prod_{h \in \mathrm{nbr}(x) \setminus \{ f \} } m_{h \to x}(x)

인자에서 변수로 가는 메시지는 다음과 같다:

m_{f \to x}(x) = \sum_{\mathbf{y}} f(x, \mathbf{y}) \prod_{y \in \mathrm{nbr}(f) \setminus \{ x \} } m_{y \to f}(y)

수렴시에 최종 믿음 상태는 수신 메시지의 곱으로 나타내어진다.

\mathrm{bel}(x) \propto \prod_{f \in \mathrm{nbr}(x)} m_{f \to x}(x)

22.2.4. Convergence

순환적 믿음 전파는 항상 수렴하지는 않고, 잘못된 값으로 수렴할 수도 있다. 그러면 언제 수렴하는가? 수렴할 확률을 높이려면 어떻게 해야 하는가? 수렴율을 높이려면 어떻게 해야 하는가?

22.2.4.1. When will LBP converge?

순환적 믿음 전파가 수렴하는지를 알아보기 위해서는 계산 트리를 사용한다. 이는 알고리즘이 진행되면서 메시지가 전파되는 것을 시각화한다. 또한, 순환적 믿음 전파에서 T번째 반복은 높이 T + 1의 트리에서 정확한 계산을 하는 것과 동일하다는 것을 사용한다. 간선간 연결의 세기가 충분히 약하다면, 루트에서 리프까지의 영향은 시간에 따라 소멸하므로, 수렴하게 될 것이다.

22.2.4.2. Making LBP converge

실제로 써 봤을 때 수렴하지 않으면 어떻게 해야 하나? 진동할 확률을 낮추기 위한 방법은 감쇠이다. 즉, 메시지 M_{ts}^{k} 대신 감쇠 인자 0 \leq \lambda \leq 1에 대해 \tilde{M}_{ts}^{k}(x_{s}) = \lambda M_{ts}(x_{s}) + (1 - \lambda)\tilde{M}_{ts}^{k-1}(x_{s})의 메시지를 보내는 것이다. 보통 \lambda \sim 0.5를 쓴다.

이중 루프 알고리즘 같은 또 다른 방법도 가능하다. 이는 순환적 믿음 전파가 최소화하는 목적 함수의 국소적 해로 수렴함이 보장되어 있다. 하지만 느리고 복잡하다는 단점이 있으며, 결과 주변분포의 정확도도 일반적인 순환적 믿음 전파에 비해 뛰어나지 않다.

22.2.4.3. Increasing the convergence rate: message scheduling

순환적 믿음 전파가 수렴하더라도, 이는 오래 걸린다. 그래서 이를 구현할 때는 동기적 업데이트를 수행한다. 즉, 모든 노드가 메시지를 병렬로 수신하고, 병렬로 송신하는 것이다. 즉, 반복 k + 1에서의 새 메시지를 \mathbf{m}^{k+1} = (f_{1}(\mathbf{m}^{k}, \cdots, f_{E}(\mathbf{m}^{k})) 로 계산하는 것이다.

또한, 비동기적 업데이트를 수행해 선형 방정식의 계를 푸는 것이 더 빠르기도 하다. 이는 \mathbf{m}_{i}^{k+1} = f_{i}(\{\mathbf{m}_{j}^{k+1} ; j < i\}, \{\mathbf{m}_{j}^{k} : j > i\})의 업데이트를 수행한다. 여기서 중요한 것은 어떤 순서로 메시지를 업데이트할 것이냐인데, 고정된 순서를 사용하든가 무작위 순서를 사용하는 것이 있다.

더 현명한 접근법은 신장 트리의 집합을 선택한 뒤 다른 메시지는 고정시켜 두고 한 번에 하나씩 신장 트리를 통한 상방에서 하방으로의 메시지 전파를 수행하는 것이다. 이를 트리 재매개화라 한다.

더 좋은 방법도 있다. 가장 불확실한 변수에 집중하는 것인데, 이를 잔여 믿음 전파라 하며, 이전 값과의 크기에 따라 메시지 전파 순서를 조절하는 방법이다. 즉, 새 메시지 m_{st}의 k번째 반복에서의 나머지를 r(s, t, k) = \lVert \log m_{st} - \log m_{st, k} \rVert_{\infty} = \max_{i} \lvert \log \frac{m_{st}(i)}{m_{st, k}(i)} \rvert로 정의해 우선 순위 큐에 넣고 나머지가 가장 높은 것을 보내는 것이다. 이 때 m_{st}가 전송되면 이에 의존하는 다른 메시지는 재계산되어 다시 큐에 추가된다. 이를 더 보완시켜, 메시지 나머지를 직접 계산하지 않고 전송할 때만 계산하고 나머지는 상한을 둬서 수렴시키는 방법도 있으며, 이것이 더 빠르다.

22.2.5. Accuracy of LBP

단일 루프가 있는 그래프에서는, 순환적 믿음 전파의 최대-곱 버전이 올바른 최대사후확률추정을 찾아낸다. 더 일반적인 그래프에 대해서는 순환적 믿음 전파로 계산된 근사 주변분포의 오차의 상한을 계산할 수 있다. 가우시안의 경우에는 더 강한 조건을 걸 수 있는데, 만약 수렴한다면 그 해의 평균은 정확하다. 분산은 그렇지는 않다.

22.2.6. Other speedup tricks for LBP

여러 속도를 향상시키는 방법이 있다.

22.2.6.1. Fast message computation for large state spaces

믿음 전파에서 각 메시지를 계산하는 복잡도는 O(K^{f})이다. K는 상태의 수, f는 인자의 최대 크기이다. 이미지 같은 경우 K = 256, f = 2 등인 경우가 많으므로, O(K^{2})도 너무 느리다. 하지만 쌍별 잠재 함수가 \phi_{st} (x_{s}, x_{t}) = \phi(x_{s} - x_{t})의 형태라면 메시지 계산이 M_{st, k}(x_{t}) = \sum_{x_{s}} \phi(x_{s} - x_{t}) h(x_{s}), h(x_{s}) = \phi_{s}(x_{s}) \prod_{v \in \mathrm{nbr}(s) \setminus t} M_{vs, k-1}(x_{s})의 컨볼루션 꼴이 되어 빠른 푸리에 변환을 이용해 O(K \log K)에 계산할 수 있다. 잠재 함수 \phi(z)가 가우시안 형태라면 적은 박스 필터와 컨볼루션을 단계적으로 취함으로써 컨볼루션을 O(K)에 계산할 수 있다.

최대-곱 경우에는 거리 변환을 사용해 메시지를 O(K) 시간에 계산할 수 있는데, 이는 \phi(z) = e^{-E(z)}에서 E(z)가 이차 함수, 절단 선형 함수, 파츠 모델 중 하나인 경우에만 가능하다.

22.2.6.2. Multi-scale methods

2차원 격자 구조에 대한 문제는 다중 격자법에 기반한다. 이는 선형 방정식의 계의 빠른 해를 찾는 방법에 널리 쓰이는데, 이는 가우시안 마르코프 무작위 장의 최대사후확률추정을 구하는 것과 같다. 컴퓨터 비전에서는 믿음 전파를 가속시키는 휴리스틱이 있는데, 격자를 큰 것부터 작은 것까지 만들고, 큰 격자에서 메시지를 구하고, 이를 이용해 아래 층위에서의 메시지를 초기화한다. 아래 층에 도달하면, 일반적인 믿음 전파 알고리즘을 수 차례 반복하는 것만으로도 충분하다.

22.2.6.3. Cascades

또 다른 트릭은 속도와 정확성간 트레이드오프를 갖는 계층적 폭포수 모델을 적용하는 것인데, 이는 정확한 추론에도 이용할 수 있다.

22.3. Loopy belief propagation: theoretical issues

순환적 믿음 전파 알고리즘의 이론적 배경을 알아보자.

22.3.1. UGMs represented in exponential family form

분포를 다음의 형태로 가정하자:

p(\mathbf{x} | \mathbf{\theta}, G) = \frac{1}{Z(\mathbf{\theta})}e^{\sum_{s \in \mathcal{V}} \theta_{s}(x_{s}) + \sum_{(s, t) \in \mathcal{E}} \theta_{st}(x_{s}, x_{t})} (\mathcal{V}는 정점의 집합, \mathcal{E}는 간선의 집합)

이는 지수족으로 다음과 같이 쓸 수 있다.

p(\mathbf{x} | \mathbf{\theta}) = \frac{1}{Z(\mathbf{\theta})} e^{-E(\mathbf{x})}, E(\mathbf{x}) = -\mathbf{\theta}^{T} \mathbf{\phi}(\mathbf{x})

이 때 \mathbf{\theta}는 모든 정점과 간선 매개변수, \mathbf{\phi}(\mathbf{x})은 정점과 간선의 지시 함수이다. 충족 통계량의 평균은 다음과 같다.

\mathbf{\mu} = \mathbb{E}[\mathbf{\phi}(\mathbf{x})] = (\{\mu_{s;j}\}_{s}, \{\mu_{st;jk}\}_{s \neq t})

이는 정점과 간선 주변분포를 포함한 벡터로, 분포를 완전히 정의한다. 따라서 모델 그 자체를 나타내는 통계량으로 볼 수도 있다.

첫 번째 식은 표준 과완전 표현식이라 불리는데, 과완전이라고 불리는 이유는 합이 1이 되는 조건을 무시하기 때문이다. 이를 받아들여 표현식을 간소화시킬 수도 있다.

22.3.2. The marginal polytope

\mathbf{\mu}의 가능한 값들의 공간은 주변 폴리토프 \mathbb{M}(G) = \{\mathbf{\mu} \in \mathbb{R}^{d} : \exists p s.t. \mathbf{\mu} = \sum_{\mathbf{x}} \mathbf{\phi}(\mathbf{x}) p(\mathbf{x}) \mathrm{for some} p(\mathbf{x}) \geq 0, \sum_{\mathbf{x}} p(\mathbf{x}) = 1\}로, 가능한 확률분포로부터 생성될 수 있는 모든 평균 매개변수의 집합이다. 이는 특성 집합의 볼록 껍질 \mathrm{conv}\{\phi_{1}(\mathbf{x}), \cdots, \phi_{d}(\mathbf{x})\}로 볼 수도 있다.

22.3.3. Exact inference as a variational optimization problem

변분 추론의 목적은 다음의 에너지 함수 L(q) = -\mathbb{KL}(q \vert \vert p) + \log Z = \mathbb{E}_{q} [\log \tilde{p}(\mathbf{x})] + \mathbb{H}(q) \leq \log Z을 최대화시키는 분포 q를 찾는 것이다. \log \tilde{p}(\mathbf{x}) = \mathbf{\theta}^{T} \mathbf{\phi}(\mathbf{x})로 쓰고 q = p로 놓는다면, 정확한 에너지 함수는 \max_{\mathbf{\mu} \in \mathbb{M}(G)} \mathbf{\theta}^{T} \mathbf{\mu} + \mathbb{H}(\mathbf{\mu}) = \log Z(\mathbf{\theta})가 된다. 즉, 정확한 추론을 변분 최적화 문제로 변경시킬 수 있다.

22.3.4. Mean field as a variational optimization problem

평균 장 추론법을 변분 최적화 문제로 볼 수도 있다. F를 원본 그래프 G의 간선 부분그래프라 하고 \mathcal{I}(F) \subseteq \mathcal{I}를 F의 클리크들에 연관된 충족 통계량의 부분집합이라 하자. \Omega를 전체 모델의 자연 매개변수의 집합이라 하고 자연 매개변수의 공간을 \Omega(F) = \{\mathbf{\theta} \in \Omega : \mathbf{\theta}_{\alpha} = 0 \forall \alpha \in \mathcal{I} \setminus \mathcal{I}(F)\}로 정의하자. 즉, 조건은 선택하지 않은 충족 통계량과 관련된 모든 자연 매개변수가 0이 되도록 하는 것이다.

이후, 제한된 모델에 대한 평균 매개변수 공간을 다음과 같이 정의한다.

\mathbb{M}_{F}(G) = \{\mathbf{\mu} \in \mathbb{R}^{d} : \mathbf{\mu} = \mathbb{E}_{\mathbf{\theta}}[\mathbf{\phi}(\mathbf{x})] \mathrm{for some} \mathbf{\theta} \in \Omega(F)\}

\mathbb{M}_{F}(G) \subseteq \mathbb{M}(G)이므로, 이는 주변 폴리토프에 대한 내근사라 불린다. 이는 볼록 집합이 아니기 때문에 국소적 해가 여럿 있을 수 있다.

이 근사에 대한 엔트로피 \mathbb{H}(\mathbf{\mu}(F))를 부분모델 F에 정의된 분포 \mathbf{\mu}의 엔트로피로 정의한다. 이후 평균 장 에너지 함수 최적화 문제 \max_{\mathbf{\mu} \in \mathbb{M}_{F}(G)} \mathbf{\theta}^{T} \mathbf{\mu} + \mathbb{H}(\mathbf{\mu}) \leq \log Z(\mathbf{\theta})를 정의하고, 이를 푸는 것이다. 이는 대개 좌표 상승법으로 최적화된다.

22.3.5. LBP as a variational optimization problem

순환적 믿음 전파도 변분 추론 문제로 볼 수 있다.

22.3.5.1. An outer approximation to the marginal polytope

모델에 대해 마르코프인 모든 확률분포를 고려하고 싶다면, 모든 \mathbf{\mu} \in \mathbb{M}(G) 을 고려해야 한다. \mathbb{M}(G)의 크기는 지수함수적이므로 일반적으로는 제한 조건을 완화해 조합적 최적화를 수행한다. 즉, 다음의 국소적 일관성 조건 \sum_{x_{s}} \tau_{s} (x_{s}) = 1, \sum_{x_{t}} \tau_{st}(x_{s}, x_{t}) = \tau_{s}(x_{s})을 만족시키는 \mathbf{\tau}만을 고려하는 것이다. 그 뒤 모든 정점에 대해 첫 번째 조건이, 모든 간선에 대해 두 번째 조건이 성립하는 \mathbf{\tau} \geq 0의 집합을 \mathbb{L}(G)로 정의한다. 이를 \mathbb{M}(G)에 대한 볼록 외근사라 한다. 이 때 \tau_{s}, \tau_{st} \in \mathbb{L}(G)유사 주변분포라 하는데, 이들이 올바른 주변분포가 된다는 보장은 없기 때문이다. \mathbb{M}(G) \subseteq \mathbb{L}(G)가 성립하며, 등호 조건은 G가 트리인 것과 동치이다.

22.3.5.2. The entropy approximation

분포 \mathbf{\mu} \in \mathbb{M}(T)가 트리 구조 분포일 때에는 정확한 엔트로피를 계산할 수가 있다.

\mathbb{H}(\mathbf{\mu}) = \sum_{s \in V} H_{s} (\mu_{s}) - \sum_{(s, t) \in E} I_{st} (\mu_{st})

H_{s}(\mu_{s}) = -\sum_{x_{s} \in \mathcal{X}_{s}} \mu_{s}(x_{s}) \log \mu_{s} (x_{s})

I_{st}(\mu_{st}) = \sum_{(x_{s}, x_{t}) \in mathcal{X}_{s} \times \mathcal{X}_{t}} \mu_{st}(x_{s}, x_{t}) \log \frac{\mu_{st}(x_{s}, x_{t})}{\mu_{s}(x_{s})\mu_{t}(x_{t})}

이는 다음과 같이 쓸 수도 있다.

\mathbb{H}(\mathbf{\mu}) =-\sum_{s \in V} (d_{s} - 1)H_{s} (\mu_{s}) - \sum_{(s, t) \in E} H_{st} (\mu_{st}) (d_{s}는 노드 s의 차수)

엔트로피의 베테 근사는 단순히 위의 식을 트리 구조가 아닐 때에도 적용한 것으로, \mathbb{H}_{\mathrm{Bethe}}(\mathbf{\tau}) = \sum_{s \in V} H_{s} (\tau_{s}) - \sum_{(s, t) \in E} I_{st} (\tau_{st})다. 이 때 베테 자유 에너지F_{\mathrm{Bethe}}(\mathbf{\tau}) = -[\mathbf{\theta}^{T} \mathbf{\tau} + \mathbb{H}_{\mathrm{Bethe}}(\mathbf{\tau})]로 정의한다. 이에 음수를 취한 것이 베테 에너지 함수이다.

22.3.5.3. The LBP objective

엔트로피에 대한 베테 근사와 외근사를 결합하면, 다음의 베테 변분 문제를 얻는다.

\min_{\mathbf{\tau} \in \mathbb{L}(G)} F_{\mathrm{Bethe}}(\mathbf{\tau}) = \max_{\mathbf{\tau} \in \mathbb{L}(G)} \mathbf{\theta}^{T} \mathbf{\tau} + \mathbb{H}_{\mathrm{Bethe}}(\mathbf{\tau})

이 때 최적화하는 집합의 범위는 볼록집합이지만 목적함수 자체는 오목함수가 아니기 때문에 이 문제에는 국소적 해가 여럿 존재할 수 있다. 이로 인해 얻어지는 값은 \log Z(\mathbf{\theta})에 대한 근사인데, 트리의 경우에는 이 근사가 정확한 값이 되고, 특정한 성질을 만족하는 잠재 함수에 대해서는 이 근사는 상한이 된다.

22.3.5.4. Message passing and Lagrange multipliers

순환적 믿음 전파 알고리즘의 고정점은 위의 조건 걸린 목적 함수에 대한 안정점을 정의한다. 표준화 상수를 C_{ss}(\mathbf{\tau}) = 1 - \sum_{x_{s}} \tau_{s}(x_{s}), C_{ts}(x_{s}; \mathbf{\tau}) = \tau_{s}(x_{s}) - \sum_{x_{t}} \tau_{st}(x_{s}, x_{t})와 같이 정의하자. 이제 라그랑지안을 다음과 같이 쓸 수 있다:

\mathcal{L}(\mathbf{\tau}, \mathbf{\lambda};\mathbf{\theta}) = \mathbf{\theta}^{T} \mathbf{\tau} + \mathbb{H}_{\mathrm{Bethe}}(\mathbf{\tau}) + \sum_{s} \lambda_{ss} C_{ss}(\mathbf{\tau}) + \sum_{s, t} [\sum_{x_{s}} \lambda_{ts}(x_{s}) C_{ts}(x_{s}; \mathbf{\tau}) + \sum_{x_{t}} \lambda_{st}(x_{t}) C_{st}(x_{t}; \mathbf{\tau})]

이 때, \nabla_{\mathbf{\tau}} \mathcal{L} = \mathbf{0}\tau_{s}(x_{s}) = \sum_{x_{t}} \tau(x_{s}, x_{t})임을 이용하면, 다음을 얻는다.

\log \tau_{st}(x_{s}, x_{t}) = \lambda_{ss} + \lambda_{tt} + \theta_{st}(x_{s}, x_{t}) + \theta_{s}(x_{s}) + \theta_{t}(x_{t}) + \sum_{u \in \mathrm{nbr}(s) \setminus t} \lambda_{us}(x_{s}) + \sum_{u \in \mathrm{nbr}(t) \setminus s} \lambda_{ut}(x_{t})

M_{ts}(x_{s}) = e^{\lambda_{ts}(x_{s})}로 정의하면, 위의 식은 다음과 같이 쓸 수 있다.

\tau_{s}(x_{s}) \propto e^{\theta_{s}(x_{s})} \prod_{t \in \mathrm{nbr}(s)} M_{ts}(x_{s})

\tau_{st}(x_{s}, x_{t}) \propto e^{\theta_{st}(x_{s}, x_{t}) + \theta_{s}(x_{s}) + \theta_{t}(x_{t})} \prod_{u \in \mathrm{nbr}(s) \setminus t} M_{us}(x_{s}) \prod_{u \in \mathrm{nbr}(t) \setminus s} M_{ut}(x_{t})

즉, 순환적 믿음 전파에서 정점과 간선의 주변분포에 대한 표현식을 얻게 됨을 알 수 있다. 메시지의 다른 메시지에 대한 표현식을 알려면 주변 조건 \sum_{x_{t}} \tau_{st}(x_{s}, x_{t}) = \tau_{s}(x_{s})을 쓰면 된다. 이렇게 되면 다음을 얻는다.

M_{ts}(x_{s}) \propto \sum_{x_{t}} [e^{\theta_{st}(x_{s}, x_{t}) + \theta_{t}(x_{t})} \prod_{u \in \mathrm{nbr}(t) \setminus s} M_{ut}(x_{t})]

22.3.6. Loopy BP vs mean field

일반적인 평균 장 법과 순환적 믿음 전파에는 몇 가지 차이가 있다. 첫째로 순환적 믿음 전파는 트리에 한정해서는 정확한 알고리즘이 되지만 평균 장 법은 그렇지 못하다. 둘째로 순환적 몯음 전파는 정점과 간선 주변분포에 대한 최적화를 수행하지만, 평균 장 법은 정점 주변분포에 대한 최적화만을 수행한다. 셋째로, 두 방법에서의 자유 에너지 근사가 같아지는 시점은 간선 주변분포의 참값이 \mathbf{\mu}_{st} = \mathbf{\mu}_{s} \mathbf{\mu}_{t}의 꼴로 인수분해될 때이다.

덜 명료한 차이점으로는 평균 장 법은 순환적 믿음 전파법보다 국소적 최적해를 더 많이 가져서 최적화하기 더 힘들다는 것도 있다. 또한, 믿음 전파 주변분포로 평균 장 법을 초기화했을 때에는 결과가 좋게 나온다는 점으로부터, 문제점은 평균 장 법의 목적함수의 비볼록성과 경사 하강법의 약점으로부터 나온다는 것을 알 수 있다. 그러나 평균 장 법에도 이점은 있는데, 기본적으로 하한을 제공하는 방법이기 때문에 학습 알고리즘의 서브루틴으로 쓰기 좋고, 이산 분포와 가우시안 분포를 제외한 분포로도 확장하기 좋다. 직관적으로, 이는 평균 장법은 주변분포에 대해서만 작동하고, 쌍별 분포를 필요로 하지 않기 때문이라고 생각할 수 있다.

22.4. Extensions of belief propagation

순환적 믿음 전파의 여러 확장을 알아보자.

22.4.1. Generalized belief propagation

순환적 믿음 전파의 정확도는 타이트한 루프를 형성하는 노드를 주위로 클러스터링함으로써 개선할 수 있다. 이를 클러스터 변분법이라 한다. 이를 적용하면 간선 대신 초간선이 존재하는 초그래프 모양이 된다. 초그래프 내의 최대 초간선의 크기를 t라 하자. 이를 트리 두께와 일치시키면 초그래프를 트리로 나타낼 수 있고, 변분법이 근사가 아닌 정확한 계산이 된다.

\mathbb{L}_{t}(G)를 최대 초간선의 크기가 t + 1인 초그래프 내에서 표준화와 주변화 조건이 성립하는 유사주변분포의 집합이라 하자. 이 때 다음과 같이 엔트로피를 근사할 수 있다:

\mathbb{H}_{\mathrm{Kikuchi}}(\mathbf{\tau}) = \sum_{g \in E} c(g) H_{g}(\tau_{g}) (H_{g}(\tau_{g})은 g 내의 정점들 위에서의 결합분포의 엔트로피, c(g)는 g의 더 많이 센 수) 이들은 집합론에서의 뫼비우스 수와 관계가 있다. 이를 통해, 다음의 키쿠치 자유 에너지를 정의할 수 있다.

F_{\mathrm{Kikuchi}}(\mathbf{\tau}) = -[\mathbf{\theta}^{T} \mathbf{\tau} + \mathbb{H}_{\mathrm{Kikuchi}}(\mathbf{\tau})]

이후 다음의 변분 문제를 얻는다.

\min_{\mathbf{\tau} \in \mathbb{L}_{t}(G)} F_{\mathrm{Kikuchi}}(\mathbf{\tau}) = \max_{\mathbf{\tau} \in \mathbb{L}_{t}(G)} \mathbf{\theta}^{T} \mathbf{\tau} + \mathbb{H}_{\mathrm{Kikuchi}}(\mathbf{\tau})

베테 자유 에너지 때처럼, 이는 오목함수가 아니기 때문에 일반화된 믿음 전파 등의 국소적 최적화 알고리즘을 적용해야 한다. 이는 계산량이 크다는 단점이 있다.

22.4.2. Convex belief propagation

평균 장 에너지 함수는 오목함수이지만, 최대화되는 대상 집합이 주변 폴리토프의 비볼록 내근사이다. 베테와 키쿠치 에너지 함수는 오목함수가 아니지만, 최대화되는 대상 집합이 주변 폴리토프의 볼록 외근사이다. 그러므로, 평균 장과 순환적 믿음 전파에서 모두 복수의 최적값이 존재하기 때문에, 초기 조건을 잘 설정해야 한다. 오목함수의 볼록집합 위에서의 최적화는 정확하므로, 이를 통한 근사를 생각해 볼 수 있다.

그 중 하나는 볼록 믿음 전파로, 트리나 평면 그래프같은 계산 가능한 부분 모델들 \mathcal{F}로부터 시작한다. 각각의 모델 F \subset G에 대해, 엔트로피는 더 크므로 (\mathbb{H}(\mathbf{\mu}(F)) \geq \mathbb{H}(\mathbf{\mu}(G))), 이런 부분그래프의 볼록 결합 또한 더 높은 엔트로피를 갖는다.

\mathbb{H}(\mathbf{\mu}(G)) \leq \sum_{F \in \mathcal{F}} \rho(F) \mathbb{H}(\mathbf{\mu}(F)) = \mathbb{H}(\mathbf{\mu}, \rho), \rho(F) \geq 0, \sum_{F} \rho(F) = 1

이 때 볼록 자유 에너지를 다음과 같이 정의한다:

F_{\mathrm{Convex}}(\mathbf{\tau}) = -[\mathbf{\theta}^{T} \mathbf{\tau} + \mathbb{H}(\mathbf{\mu}, \rho)]

오목 에너지 함수는 이에 음수를 취하면 정의된다.

엔트로피에 대한 상한이 정의되었으므로, 이제는 평균 매개변수의 주변 폴리토프의 볼록 외근사를 고려해야 할 차례이다. 이 집합에서의 임의의 벡터에서 엔트로피를 구할 수 있음을 보장하기 위해, 해당 벡터의 부분그래프 G에 대한 사영이 \mathbb{M}의 F에 대한 사영에 속한다는 제한 조건을 건다.

\mathbb{L}(G; \mathcal{F}) = \{ \mathbf{\tau} \in \mathbb{R}^{d} : \mathbf{\tau}(F) \in \mathbb{M}(F) \forall F \in \mathcal{F}\}

이는 \mathbb{M}(F)가 볼록집합에 대한 사영이므로 역시 볼록집합이다. 따라서 다음의 변분 문제를 얻는다.

\min_{\mathbf{\tau} \in \mathbb{L}(G; \mathcal{F})} F_{\mathrm{Convex}}(\mathbf{\tau}, \rho) = \max_{\mathbf{\tau} \in \mathbb{L}(G; \mathcal{F})} \mathbf{\tau}^{T} \mathbf{\theta} + \mathbb{H}(\mathbf{\tau}, \rho)

이는 볼록 집합에서 최적화되는 오목 함수이므로 유일한 최적해를 갖는다.

22.4.2.1. Tree-reweighted belief propagation

\mathcal{F}가 모든 신장 트리들의 집합인 경우를 고려해 보자. 트리에 대해 엔트로피는 정확히 구할 수 있다. 모든 트리에 대해 평균낸 상한을 구하기 위해서는 상호 정보량 I_{st}가 가중치 \rho_{st} = \mathbb{E}_{\rho}[\mathbb{I}((s, t) \in E(T))]을 부여받는다는 것을 이용한다. (간선 등장 확률) 즉 다음의 엔트로피에 대한 상한을 얻는다.

\mathbb{H}(\mathbf{\mu}) \leq \sum_{s \in V} H_{s}(\mu_{s}) - \sum_{(s, t) \in E} \rho_{st} I_{st} (\mu_{st})

위의 간선 등장 확률은 신장 트리 폴리토프 집합 내에 존재한다. 이는 이들의 존재 조건이 트리들에서의 분포로부터 정의되기 때문이다.

최적화하는 집합에 대해서는 어떻게 이야기할 수 있을까? 각각의 트리 T에 대해 \mathbf{\mu}(T) \in \mathbb{M}(T)이므로 표준화와 국소적 일관성이 보장된다. 모든 간선에 대해 이것이 성립하므로 \mathbb{L}(G;\mathcal{F}) = \mathbb{L}(G)이 된다. 즉, 마지막으로 다음의 최적화 문제를 얻는다.

\max_{\mathbf{\tau} \in \mathbb{L}(G)} [\mathbf{\tau}^{T} \mathbf{\theta} + \sum_{s \in V} H_{s}(\tau_{s}) - \sum_{(s, t) \in E(G)} \rho_{st} I_{st}(\tau_{st})]

이는 \rho_{st} 가중치가 부여된 순환적 믿음 전파 목적 함수와 같다. 모든 간선에 대해 \rho_{st} > 0인 한, 이는 유일한 최적해가 존재하는 단조오목함수가 된다.

그 유일한 최적해는 어떻게 찾는가? 가장 간단한 것은 트리 재가중 믿음 전파(TRW, TRBP)이다. 정점 t에서의 메시지는 t의 근방로부터 오는 메시지들뿐만 아니라 모든 정점으로부터 오는 메시지에 대한 함수임을 이용하는 것이다. 즉,

M_{ts}(x_{s}) \propto \sum_{x_{t}} e^{\frac{1}{\rho_{st}} \theta_{st}(x_{s}, x_{t}) + \theta_{t}(x_{t})} \frac{\prod_{v \in \mathrm{nbr}(t) \setminus s} [M_{vt}(x_{t})]^{\rho_{vt}}}{[M_{st}(x_{t})]^{1 - \rho_{ts}}}

수렴 시에, 정점과 간선 유사주변분포는 다음과 같다.

\tau_{s}(x_{s}) \propto e^{\theta_{s}(x_{s})} \prod_{v \in \mathrm{nbr}(s)} [M_{vs}(x_{s})]^{\rho_{vs}}

\tau_{st}(x_{s}, x_{t}) \propto \varphi_{st}(x_{s}, x_{t}) \frac{\prod_{v \in \mathrm{nbr}(s) \setminus t} [M_{vs}(x_{s})]^{\rho_{vs}}}{[M_{ts}(x_{s})]^{1 - \rho_{st}}}\frac{\prod_{v \in \mathrm{nbr}(t) \setminus s} [M_{vt}(x_{t})]^{\rho_{vt}}}{[M_{st}(x_{t})]^{1 - \rho_{ts}}}

\varphi_{st}(x_{s}, x_{t}) = e^{\frac{1}{\rho_{st}} \theta_{st}(x_{s}, x_{t}) + \theta_{s}(x_{s}) + \theta_{t}(x_{t})}

모든 간선에 대해 \rho_{st} = 1이라면 이는 일반 순환적 믿음 전파와 같아진다. 하지만 이것이 가능할 때는 원본 그래프가 트리일 때 뿐이다. 일반적으로, 이 메시지 전파 방식은 유일한 전역 최적해로 수렴함이 보장되지는 않는다. 이중 순환 방법으로 수렴을 보장할 수는 있지만, 실제로는 감쇠 업데이트를 쓰는 것으로 충분히 수렴시킬 수 있다. 또한, 키쿠치 자유 에너지의 볼록 버전을 쓸 수도 있다.

트리 재가중 믿음 전파 엔트로피 근사는 \log Z의 상한을 갖는다.

22.5. Expectation propagation

기대값 전파(EP)는 메시지가 근사된 형태의 믿음 전파이다.이는 사후분포의 함수 형태를 특정한 형태로 가정한 뒤 근사를 하는 가정된 밀도 필터링(ADF) 알고리즘의 일반화로 볼 수 있다. 이 때 사후분포는 \mathbb{KL}(p \vert \vert q)에 대해 단일 항에 대한 최적화를 수행하는 모멘트 매칭을 하여 계산될 수 있다. 이는 순차적 베이지안 업데이트에 대해서는 잘 동작하지만, 데이터가 관측된 순서에 답이 의존한다는 단점이 있다. 기대값 전파는 데이터에 대한 복수의 패스를 진행함으로써 이 단점을 해소한다. 즉, 기대값 전파는 오프라인 내지 배치 추론 알고리즘이다.

22.5.1. EP as a variational inference problem

기대값 전파는 변분 추론의 일종으로 볼 수 있다. 결합분포에서 계산 가능한 매개변수를 \mathbf{\theta}, 불가능한 매개변수를 \tilde{\mathbf{\theta}}로 분리할 때, 이를 다음의 지수족 형태로 쓸 수 있음을 가정하자:

p(\mathbf{x} | \mathbf{\theta}, \tilde{\mathbf{\theta}}) \propto f_{0}(\mathbf{x}) e^{\mathbf{\theta}^{T} \mathbf{\phi}(\mathbf{x})} \prod_{i=1}^{d_{I}} e^{\tilde{\mathbf{\theta}}_{i}^{T} \mathbf{\Phi}_{i}(\mathbf{x})}

관측 모델이 하나는 \mathbf{x}, 하나는 \mathbf{0}을 평균으로 하는 2개의 가우시안의 혼합일 때 미지의 벡터 \mathbf{x}를 추론하는 방해 문제가 좋은 예가 될 수 있다. 정확한 추론은 가능하지 않지만, 추론 불가능한 항 중 하나만 포함한 \mathbf{\Phi}_{i} 증강 모델을 생각하면 이는 2개의 가우시안의 혼합이므로 계산할 수 있다.

기대값 전파의 핵심은 \mathbf{\Phi}_{i} 증강 분포를 반복적으로 다루는 것이다. 먼저, 볼록 집합 \mathcal{M}(\mathbf{\phi}, \mathbf{\Phi}) = \{(\mathbf{\mu}, \tilde{\mathbf{\mu}}_{i}) = \mathbb{E}[(\mathbf{\phi}(\mathbf{X}), \mathbf{\Phi}_{i}(\mathbf{X}))]\}을 다음의 더 큰 볼록 집합 \mathcal{L}(\mathbf{\phi}, \mathbf{\Phi}) = \{(\mathbf{\tau}, \tilde{\mathbf{\tau}}) : \mathbf{\tau} \in \mathcal{M}(\mathbf{\phi}), (\mathbf{\tau}, \tilde{\mathbf{\tau}}_{i}) \in \mathcal{M} (\mathbf{\phi}, \mathbf{\Phi}_{i})\}로 근사하는 것이다. (\mathcal{M}(\mathbf{\phi}) = \{\mathbf{\mu} = \mathbb{E}[\mathbf{\phi}(\mathbf{X})]\})

이후 엔트로피를 다음의 항별 근사로 근사한다.

\mathbb{H}_{\mathrm{ep}}(\mathbf{\tau}, \tilde{\mathbf{\tau}}) = \mathbb{H}(\mathbf{\tau}) + \sum_{i=1}^{d_{I}} [\mathbf{H}(\mathbf{\tau}, \tilde{\mathbf{\tau}}_{i}) - \mathbb{H}(\mathbf{\tau})]

즉 기대값 전파 문제는 다음과 같다.

\max_{(\mathbf{\tau}, \tilde{\mathbf{\tau}}) \in \mathcal{L}(\mathbf{\phi}, \mathbf{\Phi})} \mathbf{\tau}^{T} \mathbf{\theta} + \tilde{\mathbf{\tau}}^{T} \mathbf{\theta} + \mathbb{H}_{\mathrm{ep}}(\mathbf{\tau}, \tilde{\mathbf{\tau}})

22.5.2. Optimizing the EP objective using moment matching

이제 위의 기대값 전파 목적 함수를 최적화하는 방법을 알아보자. \tilde{\mathbf{\tau}}_{i}만을 취했을 때 부분적 라그랑지안은 다음과 같다.

L(\mathbf{\tau}; \mathbf{\lambda}) = \mathbf{\tau}^{T} \mathbf{\theta} + \mathbb{H}(\mathbf{\tau}) + \sum_{i=1}^{d_{i}}[\tilde{\mathbf{\tau}}_{i}^{T} \tilde{\mathbf{\theta}}_{i} + \mathbb{H}((\mathbf{\tau}, \tilde{\mathbf{\tau}}_{i})) - \mathbb{H}(\mathbf{tau})]

이에 대해 \nabla_{\mathbf{\tau}} L(\mathbf{\tau}; \mathbf{\lambda}) = \mathbf{0}을 풀면 다음을 얻는다.

\mathcal{M}(\mathbf{\phi}) = q(\mathbf{x} | \mathbf{\theta}, \mathbf{\lambda}) \propto f_{0}(\mathbf{x}) e^{(\mathbf{\theta} + \sum_{i=1}^{d_{I}} \mathbf{\lambda}_{i})^{T} \mathbf{\phi}(\mathbf{x})}

\nabla_{(\mathbf{\tau}, \tilde{\mathbf{\tau}}_{i})} L(\mathbf{\tau}; \mathbf{\lambda}) = \mathbf{0}을 풀면 다음을 얻는다.

\mathcal{M}(\mathbf{\phi}, \mathbf{\Phi}_{i}) = q_{i}(\mathbf{x} | \mathbf{\theta}, \tilde{\mathbf{\theta}}_{i}, \mathbf{\lambda}) \propto f_{0}(\mathbf{x}) e^{(\mathbf{\theta} + \sum_{j \neq i} \mathbf{\lambda}_{j})^{T} \mathbf{\phi}(\mathbf{x}) + \tilde{\mathbf{\theta}}_{i}^{T} \mathbf{\Phi}_{i}(\mathbf{x}) }

이를 종합하면 다음과 같다.

\int q(\mathbf{x} | \mathbf{\theta}, \mathbf{\lambda}) \mathbf{\phi}(\mathbf{x}) d \mathbf{x} = \int q_{i}(\mathbf{x} | \mathbf{\theta}, \tilde{\mathbf{\theta}}_{i}, \mathbf{\lambda}) \mathbf{\phi}(\mathbf{x}) d \mathbf{x})

이를 풀어 설명하면 다음과 같다. 우선 \mathbf{\lambda}_{i}를 초기화한다. 이후, i를 선택한 뒤, q_{i}를 계산하고, \mathbb{E}_{q_{i}}[\mathbf{\phi}(\mathbf{X})] = \mathbb{E}_{q}[\mathbf{\phi}(\mathbf{X})]을 풀어 \mathbf{\lambda}_{i}를 q에 대해 업데이트한다.

이런 식으로 볼 수도 있다. 분포의 참값을 p(\mathbf{x} | \mathcal{D}) = \frac{1}{Z} \prod_{i} f_{i}(\mathbf{x})이라 두고 각각의 f_{i}\tilde{f}_{i}로 근사한 뒤 q(\mathbf{x}) = \frac{1}{Z} \prod_{i} \tilde{f}_{i}(\mathbf{x})로 놓는다. 이후,

  1. \tilde{f}_{i}를 선택한다.
  2. 사후분포로부터 이를 제거한다. 즉, q_{-i}(\mathbf{x}) = \frac{q(\mathbf{x})}{\tilde{f}_{i}(\mathbf{x})}로 놓는다.
  3. \min_{q_{\mathrm{new}}(\mathbf{x})} \mathbb{KL}(\frac{1}{Z_{i}} f_{i}(\mathbf{x}) q_{-i}(\mathbf{x}) \vert \vert q_{\mathrm{new}}(\mathbf{x}))을 풀어 새 사후분포를 계산한다.
  4. 새 인자 (메시지)를 계산한다. \tilde{f}_{i}(\mathbf{x}) = Z_{i} \frac{q_{\mathrm{new}}(\mathbf{x})}{q_{-i}(\mathbf{x})}

수렴 후, 주변가능도는 p(\mathcal{D}) \simeq \int \prod_{i} \tilde{f}_{i}(\mathbf{x}) d \mathbf{x}으로 근사할 수 있다.

22.5.3. EP for the clutter problem

방해 문제에 대해 기대값 전파를 적용해 보자. 사전분포 p(\mathbf{x}) = \mathcal{N}(\mathbf{0}, b\mathbf{I}), 사후분포의 근사 q(\mathbf{x}) = \mathcal{N}(\mathbf{m}, v \mathbf{I})로 정의한다. 근사 인자들은 다음과 같을 것이다. \tilde{f}_{i}(\mathbf{x}) = s_{i} \mathcal{N}(\mathbf{x} | \mathbf{m}_{i}, v_{i} \mathbf{I}) 이제 다음을 수행한다.

  1. \tilde{f}_{i}(\mathbf{x})q(\mathbf{x})로 나누어, q_{-i}(\mathbf{x}) = \mathcal{N}(\mathbf{m}_{-i}, v_{-i}\mathbf{I})을 얻는다.

v_{-i}^{-1} = v^{-1} - v_{i}^{-1}

\mathbf{m}_{-i} = \mathbf{m} + v_{-i}v_{i}^{-1} (\mathbf{m} - \mathbf{m}_{i})

2. 새 사후분포 q_{\mathrm{new}}(\mathbf{x})을 얻는다.

\mathbf{m} = \mathbf{m}_{-i} + \rho_{i} \frac{v_{-i}}{v_{-i} + 1} (\mathbf{y}_{i} - \mathbf{m}_{-i})

v = v_{-i} - \rho_{i} \frac{v_{-i}^{2}}{v_{-i} + 1} + \rho_{i} (1 - \rho_{i}) \frac{v_{-i}^{2} \lVert \mathbf{y}_{i} - \mathbf{m}_{i}\rVert^{2}}{D(v_{-i} + 1)^{2}}

\rho_{i} = 1 - \frac{w}{Z_{i}} \mathcal{N}(\mathbf{y}_{i} | \mathbf{0}, a \mathbf{I})

Z_{i} = (1 - w)\mathcal{N}(\mathbf{y}_{i} | \mathbf{m}_{-i}, (v_{-i} + 1) \mathbf{I}) + w \mathcal{N}(\mathbf{y}_{i} | \mathbf{0}, a \mathbf{I})

3. 새 인자 \tilde{f}_{i}를 얻는다.

v_{i}^{-1} = v^{-1} - v_{-i}^{-1}

\mathbf{m}_{i} = \mathbf{m}_{-i} + (v_{i} + v_{-i}) v_{-i}^{-1} (\mathbf{m} - \mathbf{m}_{-i})

s_{i} = \frac{Z_{i}}{(2 \pi v_{i})^{\frac{D}{2}} \mathcal{N}(\mathbf{m}_{i} | \mathbf{m}_{-i}, (v_{i} + v_{-i}) \mathbf{I})}

수렴 시에, 주변가능도에 대한 근사는 다음과 같다.

p(\mathcal{D}) \simeq (2 \pi v)^{\frac{D}{2}} e^{\frac{c}{2}} \prod_{i=1}^{N} s_{i} (2 \pi v_{i})^{-\frac{D}{2}}

c = \frac{\mathbf{m}^{T} \mathbf{m}}{v} - \sum_{i=1}^{N} \frac{\mathbf{m}_{i}^{T} \mathbf{m}_{i}}{v_{i}}

22.5.4. LBP is a special case of EP

순환적 믿음 전파는 기대값 전파의 특수한 경우이다. 각각의 간선에 대한 증강 분포로 기대값 전파를 수행했을 때 전체 분포의 엔트로피에 대한 기대값 전파 근사는 베테 근사와 일치하고, 기대값 전파가 최적화하는 볼록 집합은 순환적 믿음 전파가 최적화하는 볼록 집합과 일치하기 때문이다.

이로부터 착안해 다음의 확장을 하는 것도 가능하다. 기본 분포를 완전 인수분해된 분포 대신 트리 구조를 갖게 한 뒤, 한 번에 하나씩의 간선을 추가시키고, 그 효과를 흡수한 뒤, 결과 분포를 새 트리로 근사하는 것이다. 이를 트리 기대값 전파라 하며, 순환적 믿음 전파보다 정확하고 가끔 빠르기도 하다.

22.5.5. Ranking players using TrueSkill

트루스킬이라는 기대값 전파의 응용 알고리즘이 있다. 이는 게임에 참가하는 참가자들의 기량을 근사하는 것이다. 과정은 다음과 같다.

  1. 기량에 대한 사후분포를 계산한다.
  2. 기량 변수로부터 경기 인자로의 메시지를 계산한다.
  3. 경기 인자로부터 팀간 기량차 변수로의 메시지를 계산한다.
  4. 팀간 기량차 변수에 대한 사후분포를 계산한다.
  5. 기량차 변수로부터 경기 인자로의 상향 메시지를 계산한다.
  6. 경기 인자로부터 기량 변수로의 상향 메시지를 계산한다.
트루스킬의 적용례.

22.5.6. Other applications of EP

infer.net 같은 또 다른 용례도 있다.

22.6. MAP state estimation

이산 상태 그래프 모델의 가장 가능성 높은 변수의 상태 조합, 즉 최대사후확률추정을 찾는 문제를 알아보자. 즉, 다음의 문제이다.

\mathbf{x}^{\ast} = \mathrm{argmax}_{\mathbf{x} \in \mathcal{X}^{m}} p(\mathbf{x} | \mathbf{\theta}) = \mathrm{argmax}_{\mathbf{x} \in \mathcal{X}^{m}} \mathbf{\theta}^{T} \mathbf{\phi}(\mathbf{x})

22.6.1. Linear programming relaxation

위의 목적 함수는 다음과 같이 변분 매개화할 수 있다.

\mathrm{argmax}_{\mathbf{x} \in \mathcal{X}^{m}} \mathbf{\theta}^{T} \mathbf{\phi}(\mathbf{x}) = \mathrm{argmax}_{\mathbf{\mu} \in \mathbb{M}(G)} \mathbf{\theta}^{T} \mathbf{\mu}

즉 이산 상태에 대한 최적화 문제가 확률분포 \mathbf{\mu}에 대한 최적화 문제로 바뀌는 것이다. 이는 볼록 집합에 대한 선형 식이므로 최적화 자체는 쉽지만, 볼록 집합의 크기가 지수적이라는 문제가 있다. 이를 해결하기 위해 볼록 외근사를 이용해 \max_{\mathbf{x} \in \mathcal{X}^{m}} \mathbf{\theta}^{T} \mathbf{\phi}(\mathbf{x}) \leq \max_{\mathbf{\tau} \in \mathbb{L}(G)} \mathbf{\theta}^{T} \mathbf{\tau}로 식을 완화시키는 방법이 있다. 이를 선형 계획법 완화라 한다.

정확한 최적화는 어떻게 수행하는가? 그래프 모델에 대해서는 선형 계획법보다 더 좋은 방법이 있다.

22.6.2. Max-product belief propagation

최대사후확률추정 목적함수는 엔트로피 항을 제하면 순환적 믿음 전파에서의 추론 목적 함수와 같다. 이를 이용하기 위한 휴리스틱은, 엔트로피가 0이 되는 확률분포의 0도 극한을 차는 것이다. 이 경우 합 연산자는 최대 연산자로 바꿀 수 있으므로, 이는 최대-곱 믿음 전파라 불린다.

순환적 믿음 전파에 대해서는 어떻게 되나? 최대-곱 순환적 믿음 전파로는 최대사후확률추정의 선형 계획법 완화 문제를 풀 수 없다. 베테 에너지 함수가 오목함수가 아니기 때문이다. 하지만, 트리-재가중 믿음 전파에서는 목적 함수가 오목함수이므로 트리 재가중 믿음 전파의 최대-곱 버전을 쓰면 위의 선형 계획법 완화 문제를 풀 수 있다. 이를 순차적으로 진행하는 순차적 트리 재가중 믿음 전파 (TRBP-S, TRW-S) 는 항상 수렴함이 알려져 있다. 또한, 병렬 업데이트보다 더 빠르다. 기본 발상은 노드를 임의의 순서로 배열한 뒤 이 순서의 부분집합이 되는 트리들을 구성한 뒤 최대-곱 믿음 전파를 수행하고 트리 중 하나를 통해 역방향 패싱을 수행하는 것이다.

22.6.3. Graphcuts

이산 상태 모델에 대한 최대사후확률추정은 그래프에 대한 최대 흐름 최소 절단 알고리즘으로 풀 수 있다. 이를 그래프컷이라 한다.

22.6.3.1. Graphcuts for the generalized Ising model

가장 쉬운 경우로는 일반화된 아이싱 모델에 대해 그래프컷을 적용할 수 있다.

22.6.3.2. Graphcuts for binary MRFs with submodular potentials

더 일반화하면, 에너지 함수가 서브모듈러 함수일 경우, 즉 E_{uv}(1, 1) + E_{uv}(0, 0) \leq E_{uv}(1, 0) + E_{uv}(0, 1)의 조건을 만족할 경우에도 그래프컷을 적용할 수 있다. 이는 이끌림 마르코프 무작위 장 또는 연관 마르코프 무작위 장이라고도 불린다.

22.6.3.3. Graphcuts for nonbinary metric MRFs

상태가 이진 상태가 아니라면어떻게 할까? 이 경우에는 쌍별 에너지 함수가 거리함수여야 한다. 이를 거리 마르코프 무작위 장이라 한다. 한 버전으로는 알파 확장이 있는데, 상태 하나를 고정시킨 뒤 이 상태가 되는지 아닌지로 이진 상태를 새롭게 정의해 그래프컷 문제를 푸는 것이다. 이는 각 단계에서 강한 국소적 최적해를 얻는다. 또 다른 버전으로는 알파-베타 교환이 있는데, 각 단계에서 두 상태를 선택한 뒤 한 상태를 다른 상태 쪽으로 전부 변환시키되, 에너지를 줄이는 방향으로 변환시키는 것이다.

22.6.4. Experimental comparison of graphcuts and BP

격자 구조 조건적 무작위 장과 같은 문제들에서, 그래프컷과 트리 재가중 최대-곱 믿음 전파가 가장 좋은 성능을 낸다. 그래프컷이 가장 빠르다.

22.6.5. Dual decomposition

그래서 원래의 목적 함수 p^{\ast} = \max_{\mathbf{x} \in \mathcal{X}^{m}} \sum_{i \in V} \theta_{i}(x_{i}) + \sum_{f \in F} \theta_{f} (\mathbf{x}_{f})을 어떻게 계산해야 할까? 그대로는 계산이 불가능하다. 방법은 각각의 항을 독립적으로 최적화하되, 국소적 추정값의 변수들이 일치하도록 조건을 거는 것이다.

22.6.5.1. Basic idea

위의 조건을 식으로 표현하면 다음과 같다.

p^{\ast} = \max_{\mathbf{x}, \mathbf{x}_{f}} \sum_{i \in V} \theta_{i}(x_{i}) + \sum_{f \in F} \theta_{f}(\mathbf{x}_{f, f}), x_{i, f} = x_{i} \forall f, i \in f

이에 대해 라그랑주 승수를 적용하면 다음의 상한을 얻는다.

L(\mathbf{\delta}) = \max_{\mathbf{x}, \mathbf{x}_{f}} L(\mathbf{\delta}, \mathbf{x}, \mathbf{x}_{f}) = \sum_{i} \max_{x_{i}} (\theta_{i}(x_{i}) + \sum_{f : i \in f}\delta_{f_{i}}(x_{i})) + \sum_{f} \max_{\mathbf{x}_{f}} (\theta_{f}(\mathbf{x}_{f}) - \sum_{i \in f} \delta_{f_{i}}(x_{i})) \geq p^{\ast}

이 상한을 최적화하는 것을 쌍대 분해 또는 라그랑주 완화라 한다. 이 문제는 선형 계획 완화 문제와 쌍대적 무네임이 알려져 있다. 이 방식의 이득은 여러 다른 최적화 알고리즘을 편리하게 혼합할 수 있다는 점이다.

22.6.5.2. Theoretical guarantees

위의 경우 부분 문제들의 최적해를 일치시키면 전역 최적해를 얻을 수 있음이 이론적으로 보장된다.

22.6.5.3. Subgradient descent

L(\mathbf{\delta})은 볼록집합이고 연속이지만, 극값이 복수 존재하는 점에서는 미분가능하지 않다. 하나의 방법은 부분경사 하강법을 이용하는 것이다. 이는 수렴함이 보장되어 있다. 상황에 따라 이것보다 더 효율적인 방법을 쓰는 것도 가능하다.

  • 트리 두께가 작은 그래프 모델.
  • 이분 그래프 매칭이 적용되는 인자.
  • 잠재 함수가 슈퍼모듈러일 경우.
  • 특정 상태를 갖는 노드의 수가 제한되어 있을 경우.
  • 인자가 일부 값을 제외하면 상수일 경우.

22.6.5.4. Coordinate descent

\mathbf{\delta}를 한 번에 업데이트하는 대신 블록 좌표 하강법을 사용하는 방법이 있다. 좌표들을 쪼개서 각각에 최대 합 선형 계획법을 적용하는 것이다. 이는 경사 하강법보다 훨씬 빠르다.

22.6.5.5. Recovering the MAP assignment

\mathbf{\delta}^{\ast}로부터 \mathbf{x}^{\ast}를 복원하려면 \bar{\theta}_{i}^{\mathbf{\delta}^{\ast}}이 유일한 전역 최적해를 가져야 한다. 즉, \mathbf{\delta}^{\ast}\mathbf{x}^{\ast}국소적으로 복호화 가능해야 한다.

요점 정리

  • 여러 다른 변분 추론법이 있다.
  • 그 중 하나는 순환적 믿음 전파로, 믿음 전파 알고리즘을 트리가 아닌 그래프에 대해서도 사용하는 것이다.
  • 순환적 믿음 전파는 변분 문제로도 볼 수 있다.
  • 믿음 전파 알고리즘은 여러 변종이 존재한다.
  • 기대값 전파는 메시지를 근사시키는 믿음 전파이다. 순환적 믿음 전파는 기대값 전파의 일부이다.
  • 그래프컷 알고리즘을 이용해 이산적 상태 모델에 대한 최대사후확률추정을 할 수 있다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중