20. Exact inference for graphical models

20.1. Introduction

앞에서는 전방-후방 알고리즘을 이용해 이산은닉 변수 \mathbf{x}와 가측 변수 \mathbf{v}에 대한 연쇄 구조 그래프 모델의 사후주변분포 p(x_{t} | \mathbf{v}, \mathbf{\theta})을 계산하는 법을 알아보았다. 이 알고리즘을 수정하여 사후최빈값과 사후표본을 구할 수 있다. 선형 가우시안 연쇄 그래프 모델에 대해서는 칼만 다듬질이라는 더 간단한 알고리즘이 적용 가능하다. 이 장의 목적은 이런 정확한 추론 알고리즘을 임의의 그래프에 대해 일반화하는 것이다. 이는 방향그래프와 비방향그래프 모두에 적용 가능하다.

20.2. Belief propagation for trees

트리에 대한 전방-후방 알고리즘은 믿음 전파(BP) 또는 합-곱 알고리즘으로 알려져 있다.

20.2.1. Serial protocol

우선 모델이 쌍별 마르코프 무작위 장(또는 조건적 무작위 장)인 경우를 가정하자. 즉, \phi_{s}를 정점 s의 국소적 증거량, \phi_{st}를 간선 s – t에 대한 잠재함수라 할 때 p(\mathbf{x} | \mathbf{v}) = \frac{1}{Z(\mathbf{v})} \prod_{s \ in \mathcal{V}} \phi_{s}(x_{s}) \prod_{(s, t) \in \mathcal{E}} \phi_{s, t} (x_{s}, x_{t})의 꼴인 것이다.

비방향 트리에 대한 믿음 전파 알고리즘을 구현하는 과정은 다음과 같다. 임의의 정점을 루트로 삼고 간선의 방향을 루트로부터의 방향으로 정의한다. 이후 리프들로부터 루트로 메시지를 전송한다 (증거 수집), 그리고 루트로부터 리프로 메시지를 전송한다 (증거 분배) 이는 전방-후방 알고리즘과 유사하다.

더 자세히 알아보자면, 정점 t의 믿음 상태를 계산하고 싶다고 할 때, 최초에는 트리에서 정점 t의 후손들의 믿음 상태에 대해서만 조건을 건다. 즉, \mathrm{bel}_{t}^{-}(x_{t}) = p(x_{t} | \mathbf{v}_{t}^{-})로 놓는다. 이제 t의 자식 노드 s에 대해 s를 루트로 하는 부분 트리에 대해 t가 알아야 하는 정보를 메시지 m_{s \to t}^{-}(x_{t}) = p(x_{t} | \mathbf{v}_{st}^{-})로 두면, 최종 믿음 상태는 다음과 같다.

\mathrm{bel}_{t}^{-}(x_{t}) = p(x_{t} | \mathbf{v}_{t}^{-}) = \frac{1}{Z_{t}} \phi_{t}(x_{t}) \prod_{c \in \mathrm{ch}(t)} m_{c \to t}^{-} (x_{t})

즉, 노드의 국소적 증거와 자식 노드로부터 오는 정보들을 전부 곱한 뒤 표준화하는 것이다. 그러면 자식 노드로부터 오는 정보 메시지는 어떻게 계산해야 할까? 이는 다음과 같다.

m_{s \ to t}^{-}(x_{t}) = \sum_{x_{s}} \phi_{st}(x_{s}, x_{t}) \mathrm{bel}_{s}^{-}(x_{s})

즉, 정점 s에 대한 믿음 상태를 정점 t에 대한 믿음 상태와 s와 t를 잇는 간선의 잠재 함수에 대한 식으로 치환한 것이다. 이를 루트에 도달할 때까지 반복한다. 루트에서는 트리 내의 모든 증거량을 관측하였으므로 루트의 국소적 믿음 상태는 다음을 이용해 계산할 수 있다.

\mathrm{bel}_{r}(x_{r}) = p(x_{r} | \mathbf{v}) = p(x_{t} | \mathbf{v}_{r}^{-}) \propto \phi_{r}(x_{r}) \prod_{c \in \mathrm{ch}(r)} m_{c \to r}^{-}(x_{r}).

이는 알고리즘의 상승 방향 부분을 완성시킨다. 부가적으로, 증거량에 대한 확률을 표준화 상수의 곱으로 계산할 수도 있다: p(\mathbf{v}) = \prod_{t} Z_{t}

이제 루트로부터 메시지를 내려보내 보자. 정점 t에서 자식 s로 보내는 메시지를 m_{t \to s}^{+} (x_{s}) = p(x_{t} | \mathbf{v}_{st}^{+})라 하면 \mathrm{bel}_{s}(x_{s}) = p(x_{s} | \mathbf{v}) \propto \mathrm{bel}_{s}^{-}(x_{s}) \prod_{t \in \mathrm{pa}(s)} m_{t \to s}^{+}(x_{s})이 된다.

그러면 아래쪽 방향으로 보내는 메시지는 어떻게 계산할까? 이는 다음과 같다.

m_{t \to s}^{+}(x_{s}) = p(x_{s} | \mathbf{v}_{st}^{+}) = \sum_{x_{t}} \phi_{st}(x_{s}, x_{t}) \frac{\mathrm{bel}_{t}(x_{t})}{m_{s \to t}^{-}(x_{t})} = \sum_{x_{t}} \phi_{st}(x_{s}, x_{t}) \prod_{c \in \mathrm{ch}(t), c \neq s} m_{c \to t}^{-} (x_{t}) \prod_{p \in \mathrm{pa}(t)} m_{p \to t}^{+}(x_{t})

즉, 자식 s를 제외한 모든 노드로부터 정점 t로 오는 모든 메시지들을 곱한 뒤 이를 간선 s – t에 대한 잠재 함수로 전파한다. 연쇄 구조인 경우에는 (즉, 트리에서 자식과 부모가 하나인 경우) 위는 다음과 같다.

m_{t \to s}^{+}(x_{s}) = p(x_{s} | \mathbf{v}_{st}^{+}) = \sum_{x_{t}} \phi_{st}(x_{s}, x_{t}) \phi_{t}(x_{t}) m_{p \to t}^{+}(x_{t})

아래쪽 방향으로 보내는 메시지를 계산할 때 나눗셈을 이용하는 방법을 믿음 업데이트라 하고, 모든 메시지를 하나 제외하고 곱하는 방법을 합-곱 방법이라 한다. 전자는 칼만 다듬질, 후자는 전방-후방 알고리즘의 후방 부분과 비슷하다.

20.2.2. Parallel protocol

위의 경우에는 트리에만 적용 가능하다. 순환이 있는 그래프에 대해 적용하려면 병렬 버전의믿음 전파 알고리즘이 필요하다. 이는 똑같은 결과를 내지만 효율성은 더 떨어진다.

기본 발상은 모든 노드가 그 근방으로부터 메시지를 병렬로 받고, 믿음 상태를 업데이트한 뒤, 그 근방으로 새 메시지를 다시 보내는 것이다. 이를 수렴할 때까지 반복한다. 이를 심수축 배열이라 한다. 정확히는, 모든 메시지를 원소가 전부 1인 벡터로 초기화한다. 그리고, 병렬로, 각 노드들이 그 근방으로부터 \mathrm{bel}_{s}(x_{s}) \propto \phi_{s}(x_{s}) \prod_{t \in \mathrm{nbr}_{s}} m_{t \to s}(x_{s})의 형태로 메시지를 흡수한다. 그리고, 다시 병렬로, 각 노드가 그 근방 각각으로 m_{s \to t}(x_{t}) = \sum_{x_{s}} (\phi_{s}(x_{s}) \phi_{st}(x_{s}, x_{t}) \prod_{u \in \mathrm{nbr}_{s} \setminus t} m_{u \to s}(x_{s}))의 형태로 메시지를 전송한다. T번째 반복에서, \mathrm{bel}_{s}(x_{s})은 그래프 내에서 x_{s}와 T만큼 떨어진 증거량에 조건이 걸린 사후 믿음을 나타낸다. D(G) 단계 이후에, (D(G)는 그래프의 반경), 모든 노드는 다른 모든 노드의 정보를 알게 된다. 이 시점에서 국소적 믿음 상태는 정확히 사후주변분포와 일치한다. 트리의 반경은 트리의 정점 수를 넘지 않으므로 알고리즘은 선형 시간에 수렴한다.

이 알고리즘을 상방-하방 버전으로 변경시킬 수도 있는데, 노드가 다른 근방으로부터 메시지를 전부 받았을 때에만 메시지를 전송할 수 있도록 조건을 걸면 된다. 따라서 이 때에는 리프 노드들로부터 시작해야 한다. 이후 메시지들은 루트로 상향 전파된 뒤 다시 돌아온다. 노드들을 무작위 순서로 업데이트할 수도 있는데, 이 때에는 각 노드가 D(G)번만큼 업데이트되어야 한다는 조건은 필요하다.

20.2.3. Gaussian belief propagation

이제 p(\mathbf{x} | \mathbf{v})가 결합가우시안으로 가우시안 쌍별 마르코프 무작위 장으로 표현될 수 있다고 하자. 이 절에서는 가우시안 믿음 전파를 알아볼 것이다. 정점과 간선 잠재 함수는 다음의 형태로 가정한다.

\phi_{t}(x_{t}) = e^{-\frac{1}{2} A_{tt} x_{t}^{2} + b_{t}x_{t}}

\phi_{st}(x_{s}, x_{t}) = e^{-\frac{1}{2} x_{s} A_{st} x_{t}}

이 때 전체 모델은 p(\mathbf{x} | \mathbf{v}) \propto e^{-\frac{1}{2} \mathbf{x}^{T} \mathbf{A} \mathbf{x} + \mathbf{b}^{T} \mathbf{x}} 의 형태가 된다.

국소적 증거량도 다음 형태의 가우시안이다: \phi_{t}(x_{t}) \propto \mathcal{N}(\frac{b_{t}}{A_{tt}}, A_{tt}^{-1}) = \mathcal{N}(m_{t}, l_{t}^{-1})

이제 사후정점주변분포 p(x_{t} | \mathbf{v}) = \mathcal{N}(\mu_{t}, \lambda_{t}^{-1})을 계산하는 법을 알아보자. 그래프가 트리면 정확히 계산 가능하다. 그래프에 순환이 있다면 사후평균은 정확히 계산 가능할 수 있지만 사후분산은 너무 작을 수도 있다. 정밀도 행렬 \mathbf{A}가 희소행렬일지라도 사후평균을 계산하려면 역행렬을 계산해야 하는데 이는 O(D^{3})의 시간이 든다. 대신에 믿음 전파 알고리즘을 쓰면 O(D) 시간에 계산 가능하다.

모델이 결합가우시안이므로, 모든 주변분포와 모든 메시지는 가우시안이다. 핵심은 가우시안의 곱은 가우시안이라는 것이다.

이제 메시지 m_{s \to t}(x_{t}) = \mathcal{N}(\mu_{st}, \lambda_{st})라 할때 정점 s의 믿음 상태는 다음과 같다.

\mathrm{bel}_{s}(x_{s}) = \phi_{s}(x_{s}) \prod_{t \in \mathrm{nbr}(s)} m_{ts}(x_{s}) = \mathcal{N}(x_{s} | \mu_{s}, \lambda_{s}^{-1})

\lambda_{s} = l_{s} + \sum_{t \in \mathrm{nbr}(s)} \lambda_{ts}

\mu_{s} = \lambda_{s}^{-1} (l_{s} m_{s} + \sum_{t \in \mathbf{nbr}(s)} \lambda_{ts} \mu_{ts})

메시지는 다음과 같이 계산한다.

m_{s \to t}(x_{t}) = \int_{x_{s}} \phi_{st} (x_{s}, x_{t}) f_{s \setminus t} (x_{s}) dx_{s}

여기서 f_{s \setminus t}(x_{s}) = \phi_{s}(x_{s}) \prod_{u \in \mathrm{nbr}(s) \setminus t} m_{u \to s}(x_{s})은 국소적 증거와 t를 제외한 다른 노드들에서 오는 메시지를 곱한 값이다.

f_{s \setminus t}(x_{s}) = \mathcal{N}(x_{s} | \mu_{s \setminus t}, \lambda_{s \setminus t}^{-1})

\lambda_{s \setminus t} = l_{s} + \sum_{u \in \mathrm{nbr}(s) \setminus t} \lambda_{us}

\mu_{s \setminus t} = \lambda_{s \setminus t}^{-1} (l_{s} m_{s} + \sum_{u \in \mathrm{nbr}(s) \setminus t} \lambda_{us} \mu_{us})

이를 대입하면 메시지는 다음과 같다.

m_{s \to t}(x_{t}) = \mathcal{N}(\mu_{st}, \lambda_{st}^{-1})

\lambda_{st} = \frac{A_{st}^{2}}{\lambda_{s \setminus t}}

\mu_{st} = \frac{A_{st} \mu_{s \setminus t}}{\lambda_{st}}

이 알고리즘은 다변수 가우시안 설정으로 확장할 수 있다. 또한, 비 가우시안 잠재 함수에 대해서는 샘플링을 통해 연관된 적분을 근사할 수 있다. 이를 비매개적 믿음 전파라 한다.

20.2.4. Other BP variants

믿음 전파 알고리즘에는 여러 변형이 있다.

20.2.4.1. Max-product algorithm

합 연산을 max 연산으로 바꿈으로써 믿음 전파 알고리즘의 최대-곱 버전을 유도할 수 있다. 이를 통해 각 노드의 국소적 최대사후확률근사 주변분포를 구할 수 있다. 그러나 극값이 여러 개일 때 이는 전역적으로 일관적이지 않을 수 있다. 이는 비터비 알고리즘을 트리로 일반화해서 해결할 수 있다.

20.2.4.2. Sampling from a tree

전방 필터링/후방 샘플링 알고리즘을 일반화해서 트리 구조 모델에서 샘플링을 할 수 있다.

20.2.4.3. Computing posteriors on sets of variables

이전에 은닉 마르코프 내의 2층 분포를 \zeta_{t, t + 1}(i, j) = p(x_{t} = i, x_{t+1} = j | \mathbf{v}) = \alpha_{t}(i) \psi_{t+1}(j) \beta_{t+1}(j) \psi_{t, t+1}(i, j)을 이용해 계산하는 법을 알아보았다. 이는 메시지 f_{t}, \psi_{t}x_{t}로 전송하고 (f_{t} = p(x_{t} | \mathbf{v}_{1 : t-1})은 전방 메시지), \beta_{t+1}, \phi_{t+1}x_{t+1}로 전송하고, 이를 \mathbf{\Psi} 행렬로 혼합하는 것으로 볼 수도 있다. 이는 x_{t}x_{t+1}을 단일한 큰 노드로 보고, 국소적 인자들과 들어오는 메시지를 곱하는 것으로 볼 수 있다.

20.3. The variable elimination algorithm

주변분포 p(\mathbf{x}_{q} | \mathbf{x}_{v})을 연쇄 구조 또는 트리뿐만 아니라 임의의 그래프에 대해 구해 보자.

먼저 방향그래프일 경우 비방향그래프로 치환한다. 이는 필수는 아니지만, 똑같은 알고리즘으로 방향그래프와 비방향그래프일 경우 모두를 다룰 수 있게 된다. 이를 위해서는 모든 조건부확률분포에 대해 잠재함수나 인자함수를 정의하면 된다. 모든 잠재 함수들이 국소적으로 표준화되어 있으므로 전역적 표준화 상수는 필요 없다. 이 과정에서 자식을 공유하나 이어지지 않은 노드들을 연결시켜주는 교화가 필요하다.

이제 주변확률을 계산하기 위해서는 다른 모든 확률변수의 모든 경우의 수를 합치면 되는데, 이는 경우의 수가 많으므로 합을 곱 안에 밀어넣는 방법인 변수 제거, 또는 버킷 제거, 껍질 벗기기 알고리즘을 활용한다. 이 방식은 임의의 주변분포에 대해 계산할 수 있으며, 조건분포를 계산하려면 주변분포의 비율로 계산하면 된다. 이 때 일반적으로 다음이 성립한다:

p(\mathbf{x}_{q} | \mathbf{x}_{v}) = \frac{p(\mathbf{x}_{q}, \mathbf{x}_{v})}{p(\mathbf{x}_{v})} = \frac{\sum_{\mathbf{x}_{h}} p(\mathbf{x}_{h}, \mathbf{x}_{q}, \mathbf{x}_{v})}{\sum_{\mathbf{x}_{h}} \sum_{\mathbf{x}_{q}^{\prime}} p(\mathbf{x}_{h}, \mathbf{x}_{q}^{\prime}, \mathbf{x}_{v})}

이 때의 분모를 증거확률이라 한다.

20.3.1. The generalized distributive law

변수 제거는 p(\mathbf{x}_{q} | \mathbf{x}_{v}) \propto \sum_{\mathbf{x}} \prod_{c} \phi_{c} (\mathbf{x}_{c})을 계산하는 것으로 생각할 수 있다. 이 때 비연속 동적 계획법을 사용한다. 그래프 모델에 대해 주변분포 외에 최대사후확률추정을 계산할 때에도 비슷한 방법을 쓸 수 있는데, 이 때는 역추적을 사용한다. 일반적으로 변수 제거는 분배 법칙가환적 반-환에 대해서는 항상 성립한다.

20.3.2. Computational complexity of VE

변수 제거법의 수행 시간은 최대 인자의 크기, 즉 그래프의 유도 두께의 지수에 비례한다. 다중 합을 처리하는 순서를 제거 순서라고 하는데, 이 순서는 중간에 임시로 생성되는 인자의 크기에 큰 영향을 준다. 이를 판단할 때, 변수와 인자를 공유하는 모든 변수와 보강 간선을 연결시킨다. 트리 두께를 그래프의 최소 유도 두께로 정의했을 때, 임의의 그래프에 대해 이를 찾아내는 것은 NP-난해 문제이다. 일반적으로는 탐욕법을 통해 충분히 좋은 두께를 찾아서 사용한다.

어떤 경우에는 최적 제거 순서를 알아내기 쉽다. 마르코프 연쇄와 마르코프 트리의 경우에는 위상 정렬이 가능하므로 트리 두께는 1이다. 그러므로 추론이 항상 O(VK^{2}) 시간에 가능하다. 이것이 마르코프 연쇄와 마르코프 트리가 자주 쓰이는 이유 중 하나이다. 다른 그래프들은 이렇지는 않다. m x n 격자의 경우 트리 두께는 O(\min\{m, n\})이다.

20.3.3. A weakness of VE

트리 두께에 대해 지수적인 시간을 소모한다는 것 외에도 변수 제거 알고리즘의 단점은 같은 증거에 대한 복수의 요청들을 계산하기에는 비효율적이라는 것이다. 전방-후방 알고리즘처럼 중간에 생성된 메시지를 캐싱해서 재활용하지 않기 때문이다. 뒤에서 이를 응용하는 법을 알아본다.

20.4. The junction tree algorithm

접합 트리 알고리즘(JTA)은 믿음 전파를 트리에서 임의의 그래프로 일반화한다.

20.4.1. Creating a junction tree

연결 트리 알고리즘은 우선 변수 제거 알고리즘을 적용해 현형 그래프를 만든다. 이 경우에는 최대 클리크를 효율적으로 구할 수 있다. 이런 형태의 그래프를 분해 가능하다고 한다. 현형 그래프의 클리크들을 재배열해서 동작 교집합 특성, 즉 어떤 변수를 포함하는 임의의 노드의 집합은 연결 요소가 된다는 특성을 만족하는 접합 트리를 만들 수 있다. 이를 이용하면, 노드가 두 인접한 트리의 노드가 된다면, 해당 트리들은 해당 변수에 대한 정보를 공유할 수 있다. 이 경우에 믿음 전파 알고리즘을 쓰면 트리의 모든 노드, 즉 그래프의 클리크 c들에 대해 p(\mathbf{x}_{c} | \mathbf{v})를 정확히 계산할 수 있다. 이후 노드와 간선 주변분포 p(x_{t} | \mathbf{v}), p(x_{s}, x_{t} | \mathbf{v})을 클리크 분포를 주변화해서 추출할 수 있다.

20.4.2. Message passing on a junction tree

접합 트리를 통해 추론하는 법은 두 버전이 있는데 하나는 합-곱 알고리즘인 샤퍼-셰노이 알고리즘을 쓰는 것이고 하나는 믿음 업데이트 알고리즘인 후긴, 라우리첸스피겔할터 알고리즘을 쓰는 것이다. 여기선 후자를 다룬다.

원본 모델은 p(\mathbf{x}) = \frac{1}{Z} \prod_{c \in \mathcal{C}(G)} \phi_{c}(\mathbf{x}_{c})의 꼴을 가진다. 접합 트리의 특성에 의해 이는 p(\mathbf{x}) = \frac{\prod_{c \in \mathcal{C}(T)} \phi_{c}(\mathbf{x}_{c})}{\prod_{s \in \mathcal{S}(T)} \phi_{s}(\mathbf{x}_{s})}의 형태를 가져야 한다. (\mathcal{C}(G)는 원본 그래프의 클리크, \mathcal{C}(T)는 현형 그래프의 클리크, \mathcal{S}(T)는 트리의 분할자)

우선 \phi_{s} = 1, \phi_{c} = 1로 초기화한다. 이제 각각의 클리크 c \in \mathcal{C}(G)에 대해 c \subseteq c^{\prime}c^{\prime} \in \mathcal{C}(T)를 잡는다. 이후 \phi_{c}\phi_{c^{\prime}}에 곱한다. 그러면 \prod_{c \in \mathcal{C}(T)} \phi_{c}(\mathbf{x}_{c}) = \prod_{c \in \mathcal{C}(G)} \phi_{c}(\mathbf{x}_{c})를 얻는다.

이제 리프 노드로부터 루트로 메시지를 전송한 뒤 (루트로 모으기) 회신받는다 (루트로부터 분배). 리프에서 루트로 전송할 때에는 노드 i가 부모 j에 메시지 m_{i \to j}(S_{ij}) = \sum_{C_{i} \setminus S_{ij}} \phi_{i}(C_{i})을 보낸다. 이는 i가 아는 노드 중 j와 상관없는 노드들을 제거한 뒤 보내는 것이다. 모든 자식 노드들에 대해 메시지를 받은 뒤에는 믿음 상태를 \phi_{i}(C_{i}) \propto \phi_{i}(C_{i}) \prod_{j \in \mathrm{ch}(i)} m_{j \to i} (S_{ij}) 로 업데이트한다. 이를 루트에 도달할 때까지 반복한다.

루트에서 리프 노드로 메시지를 회신할 때에는 노드 i가 자식 j에 메시지 m_{i \to j}(S_{ij}) = \frac{\sum_{C_{i} \setminus S_{ij}} \phi_{i}(C_{i})}{m_{j \to i}(S_{ij})}을 보낸다. 증거확률을 이중으로 세는 것을 막기 위해 자식이 노드로 보낸 메시지로 나눠 줘야 하는데, 이것 때문에 상향 단계에서 보냈던 메시지들을 캐싱해둬야 하는 것이다. 노드가 부모로부터 메시지를 받으면 최종 믿음 상태를 \phi_{j}(C_{j}) \propto \phi_{j}(C_{j}) m_{i \to j}(S_{ij})을 이용해 계산할 수 있다.

다른 방식으로는 분할자 잠재 함수에 메시지를 저장하는 흐름 전달계기법도 있다. 자식에서 부모로 메시지를 전달할 때에는 분할자 잠재 함수 \phi_{ij}^{\ast} (S_{ij}) = \sum_{C_{i} \setminus S_{ij}} \phi_{i}(C_{i})를 계산하고 수신자 잠재 함수를 \phi_{j}^{\ast}(C_{j}) \propto \phi_{j}(C_{j}) \frac{\phi_{ij}^{\ast}(S_{ij})}{\phi_{ij}(S_{ij})}로 업데이트한다. 부모에서 자식으로 메시지를 전달할 때에는 분할자 잠재 함수 \phi_{ij}^{\ast \ast} (S_{ij}) = \sum_{C_{i} \setminus S_{ij}} \phi_{i}^{\ast}(C_{i})를 계산하고 수신자 잠재 함수를 \phi_{j}^{\ast\ast}(C_{j}) \propto \phi_{j}^{\ast}(C_{j}) \frac{\phi_{ij}^{\ast\ast}(S_{ij})}{\phi_{ij}^{\ast}(S_{ij})}로 업데이트한다.

20.4.2.1. Example: jtree algorithm on a chain

접합 트리 알고리즘을 연쇄에 적용하면 전방-후방 알고리즘이 된다.

20.4.3. Computational complexity of JTA

각 노드가 K개의 이산적인 상태를 가지면, 접합 트리 알고리즘은 O(\lvert \mathcal{C} \rvert K^{w+1}) 시간복잡도를 가진다. (\lvert \mathcal{C} \rvert는 클리크 수, w는 트리 두께)

접합 트리 알고리즘을 조금 수정하면 가우시안 그래프 모델을 다룰 수 있다. 그래프 이론적 부분은 바뀌지 않고 메시지값을 계산하는 부분만 바뀐다. 가우시안 잠재 함수를 곱하고, 나누고, 주변화하는 것만 하면 된다. 이는 O(\lvert \mathcal{C} \rvert w^{3}) 시간과 O(\lvert \mathcal{C} \rvert w^{2}) 공간복잡도를 갖는다. 연쇄 그래프에 적용하면 칼만 다듬질 알고리즘과 같다.

20.4.4. JTA generalizations

사후주변분포를 계산하는 것 말고도 다른 목적으로 접합 트리 알고리즘을 적용할 수 있다. 기반 수의 집합이 가환 반-환이기만 하면 된다.

20.5. Computational intractability of exact inference in the worst case

앞서 보았듯, 변수 제거와 접합 트리 알고리즘은 트리 두께에 지수적인 시간을 가진다. 이는 SAT 문제의 변형으로 볼 수 있기 때문에 시간 면에서 극적인 개선이 이루어진 알고리즘을 얻기는 어려울 것이다.

20.5.1. Approximate inference

세상엔 정확한 추론이 가능하지 않은 모델이 많다. 심지어 \mathbf{\theta} \to \mathbf{x} 같은 모델도 \mathbf{\theta}의 사전분포가 가능도 p(\mathbf{x} | \mathbf{\theta})와 켤레분포가 아니라면 정확한 추론이 불가능할 수도 있다.

따라서 평균 장, 순환 믿음 전파, 중요도 샘플링, 깁스 샘플링 등의 근사 추론법이 필요하다. 하지만 이것도 대부분 시간이 오래 걸리며, 정확도나 수행 시간이 보장되지 않는 경우가 많다. 그래서 대신 휴리스틱을 쓰는 경우도 많다.

요점 정리

  • 그래프 모델에 대해 정확한 추론을 하는 여러 방법들이 존재한다.
  • 그 중 하나는 트리에 대한 믿음 전파 알고리즘이다. 이는 리프에서 출발해 자식 노드에서 부모 노드로 메시지를 전달한 뒤 루트까지 이를 반복하고, 루트에서 출발해 부모 노드에서 자식 노드로 메시지를 회신한 뒤 자식까지 이를 반복하는 것으로 이루어진다.
  • 트리가 아닌 그래프에 대해서는 변수 제거 알고리즘을 사용한다. 수행 시간이 지수 시간이라는 단점이 있다.
  • 상향 단계에서의 결과를 캐싱해두는 트리의 장점을 활용하기 위해서는 변수 제거 알고리즘을 개선한 접합 트리 알고리즘을 사용한다. 이것도 역시 수행 시간은 지수 시간이다.
  • 변수 제거와 접합 트리 알고리즘은 최악의 경우 계산 가능하지 않다. 근사적 추론이나 휴리스틱을 사용한다.

답글 남기기

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

WordPress.com 로고

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

Google photo

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

Twitter 사진

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

Facebook 사진

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

%s에 연결하는 중