9장 Message Passing Algorithms

Contents

9.1 - Introduction

9.2 - Belief Propagation
- 9.2.1 - Hidden Markov Models
- 9.2.2 - The Forwards Algorithm
- 9.2.3 - The Forwards-Backwards Algorithm
- 9.2.4 Forwards Filtering Backwards Smoothing
- 9.2.5 - Time and Space Complexity
- 9.2.6 - The Viterbi Algorithm
- 9.2.7 - Forwards Filtering Backwards Sampling

9.3 - Belief Propagation on Trees
- 9.3.1 - Directed vs Undirected Trees
- 9.3.2 - Sum-Product Algorithm
- 9.3.3 - Max-Product Algorithm

9.4 - Loopy Belief Propagation
- 9.4.1 - Loopy BP for Pairwise Undirected Graphs
- 9.4.2 - Loopy BP for Factor Graphs
- 9.4.3 - Gaussian Belief Propagation
- 9.4.4 - Convergence
- 9.4.5 - Accuracy
- 9.4.6 - Generalized Belief Propagation
- 9.4.7 - Convex BP
- 9.4.8 - Application: Error Correcting Codes
- 9.4.9 - Application: Affinity Propagation
- 9.4.10 - Emulating BP with Graph Neural Nets

9.5 - The Variable Elimination (VE) Algorithm
- 9.5.1 - Derivation of the Algorithm
- 9.5.2 - Computation Complexity of VE
- 9.5.3 - Picking a Good Elimination Order
- 9.5.4 - Computational Complexity of Exact Inference
- 9.5.5 - Drawbacks of VE

9.6 - The Junction Tree Algorithm (JTA)

9.7 - Inference as Optimization
- 9.7.1 - Inference as Backpropagation
- 9.7.2 - Perturb and MAP

9.1 Introduction

나아가기 전에, 이전 장들에서 다룬 중요한 Preliminaries 에 대해서 얘기해보겠습니다.

Probabilistic Graphical Model

이것은 확률 분포를 그래프 구조로 표현하는 모델입니다. 간단히 말하자면 Graphical Model 에서 Nodes & Edges 가 다음과 같으면 PGM 이라고 불립니다.

Nodes : 확률변수

Edges : 확률변수 (Nodes) 간의 의존관계 (Probabilistic Dependencies). 책에서의 4장에서는 Lack of Edges 를 Random Variables 간의 Conditional Independence Assumption 을 나타난다 함.
4장 Graphical Model 의 첫번째 부분. p.g 143

그러면 대략적으로 이해를 하자면 PGM 을 통해서 확률변수들을 그래프 구조로 시각화 해준다고 보시면 됩니다.
이때 그래프 구조에 따라서 다음과 같이 바뀝니다.

Directed PGM : Bayesian Network

Undirected PGM : Markov Random Field

왼쪽 : Bayesian Network
오른쪽 : Undirected PGM $=$ Markov Random Field

9.2 Belief Propagation on Chains

9.2 에서는 다음을 만족하는 PGM 의 Inference 만 고려합니다.

Graph Structure 이 1D-Chain 이다.

그래프가 Directed 만 고려한다.

모든 Hidden Variable 이 Discrete 이라고 가정한다 (Continuous 는 8장 & 13장 에 다룬다고 합니다).

9.2.1 Hidden Markov Models (HMM)

통계에서도 생각보다 많이 사용되는데요 (특히 스포츠 통계에서) 그냥 얼핏 봤을 때는 RNN 과 매우 유사한 형태입니다. 하지만 RNN 과는 다르게 Gate 개념이 전혀 없습니다.

위의 Figure 에 보이시는 바와 같이 Hidden Variable $z_t$ 들을 통해서 Output (Observation) $y_t$ 를 뱉는게 목표입니다. 이때 만약에 모든 Latent Variable 들이 Discrete 하다면, 위의 모델을 저희는 Hidden Markov Model (HMM) 이라고 부릅니다. 이것의 Joint Distribution $p(\boldsymbol{y}_{1:T}, \boldsymbol{z}_{1:T})$ 은 다음과 같습니다.

p\left(\boldsymbol{y}_{1: T}, \boldsymbol{z}_{1: T}\right)=\left[p\left(\boldsymbol{z}_1\right) \prod_{t=2}^T p\left(\boldsymbol{z}_t \mid \boldsymbol{z}_{t-1}\right)\right]\left[\prod_{t=1}^T p\left(\boldsymbol{y}_t \mid \boldsymbol{z}_t\right)\right]

참고로 PGM 자체에 이미 Markov Property 가 내재되어 있기에 HMM 도 Markov Property 가 있습니다.

수식어 설명
$\begin{aligned} p\left(\boldsymbol{y}_{1: T}, \boldsymbol{z}_{1: T}\right)&= p\left(\boldsymbol{z}_{1: T}\right) \cdot p\left(\boldsymbol{y}_{1: T}\mid \boldsymbol{z}_{1: T}\right) \\&= p(z_1, z_2, \cdots, z_T) \cdot p(y_1, y_2, \cdots, y_T\mid z_{1:T})\\&= p(z_1) \cdot p(z_2, \cdots, z_T \mid z_1) \cdot p(y_1 \mid z_{1:T}) \\ &\quad \cdot p(y_2, \cdots, y_T \mid y_1, z_{1:T})\\ &= p(z_1)\cdot p(z_2 \mid z_1) \cdots p(z_T \mid z_1, \cdots z_{T-1}) \\& \quad \cdot p(y_1 \mid z_{1:T}) \cdot p(y_2 \mid y_1, z_{1:T}) \\&\quad \cdots p(y_T \mid y_1, \cdots, y_{T-1}, z_{1:T}) \\ \text{(Markov Property)} &= p(z_1) \cdot \prod_{t=2}^{T} p(z_t \mid z_{t-1}) \\ &\quad \cdot p(y_1 \mid z_{1:T}) \cdot p(y_2 \mid y_1, z_{1:T}) \\ &\quad \cdots p(y_T \mid y_1, \cdots, y_{T-1}, z_{1:T}) \\ \text{(Emission Independence)} &= \left[p(z_1) \cdot \prod_{t=2}^{T} p(z_t \mid z_{t-1}) \right] \cdot \left[\prod_{t=1}^T p\left(\boldsymbol{y}_t \mid \boldsymbol{z}_t\right)\right] \end{aligned}$

Hidden State 가 Continuous 인 상황을 고려하는 것이 SSM 이며 8장에서 다룬다고 합니다.

9.2.1.1 Example: Casino HMM

9.2.1 내내 이 예시를 가지고 놀기 때문에 확실히 짚고 넘어가도록 하겠습니다.

Occasionally Dishonest Casino 상황을 고려해보겠습니다. 카지노에서 주사위를 돌리고 있는데, 주사위 중 하나는 Fair Die 이지만 다른 하나는 Loaded (Unfair) Die 라고 가정하겠습니다. 이때 저희가 하고 싶은 것은 이 주사위가 Fair / Loaded 인지를 알고 이 점을 이용해서 미래에 대한 예측을 하는 것입니다.

그러면 정확한 상황을 다음과 같이 보여드리겠습니다.

보이시는 바와 같이, Fair Die 는 좌측과 같이 모든 숫자가 $1/6$ 일 확률, Loaded Die 는 숫자 $6$ 에만 $5/10$ 인 주사위입니다. 우리가 돌리는 주사위가 어떤 시점에서는 Fair, 다른 시점에서는 Loaded 이며 주사위 자체를 Categorical Distribution 을 따르는 확률변수이라고 표현할 수 있습니다.

이때 시점 $t$ 에 Fair 인지 Loaded 인지에 대한 확률은 이전 시점에 의해 결정이 되며, 이것이 바로 State Transition Probability 입니다. 이때 Notation 을 다음과 같이 정의하겠습니다.

$z_t \in \{ 1, 2 \}$ : 시점 $t$ 에서의 Unknown Hidden State. $1$ 이면 Fair, $2$ 이면 Loaded.

$y_t \in \{ 1, \cdots, 6 \}$ : 주사위의 Outcome.

$A_{jk} = p(z_t = k \mid z_{t-1} = j)$ : State Transition Matrix, 이전 주사위가 Fair / Loaded 인지에 따라서 현재 주사위가 Fair / Loaded 일지에 대한 확률.

$B_{kl} = p(y_t = l \mid z_t = k)$ : Observation Matrix, 이 Observation Distribution 은 $z_t$ 에 해당하는 주사위 (확률변수) 의 Categorical Distribution 과 똑같다.

그러면 Observation Distribution 을 다음과 같이 적어줄 수 있습니다.

\begin{aligned}& p\left(y_t \mid z_t=1\right)=\operatorname{Cat}\left(y_t \mid[1 / 6, \ldots, 1 / 6]\right) \\& p\left(y_t \mid z_t=2\right)=\operatorname{Cat}\left(y_t \mid[1 / 10,1 / 10,1 / 10,1 / 10,1 / 10,5 / 10]\right)\end{aligned}

이 분포에서 샘플링을 한다면 샘플들이 다음과 같이 나올 수도 있습니다.

번외 (코드)
번외로 $A_{jk}, B_{kl}$ 을 그림에 보이시는 값들로 채워주게 된다면 $300, 3000$ 번 돌렸을 때 결과가 다음과 같습니다.
$300$ 번 돌렸을 때 :
$3000$ 번 돌렸을 때 :

9.2.1.2 Posterior Inference

처음에 말씀드린 바와 같이, 저희의 궁극적인 목표는 Hidden State 들을 Infer 한 다음에 Outcome 을 예측하는 것입니다. 하지만 Outcome 을 Predict 하기 전에는 당연히 Hidden State 을 Infer 해줘야 합니다. 데이터 / Observation 을 이용해서 이를 Infer 해야되지만, Hidden State 에 대한 Posterior $p(z_t\mid y_{1:T})$ 도 구해야 합니다.

그럼 왜 하필 Hidden State 에 대한 Posterior 를 구해야할까요?
저희는 사실 이 주사위가 Fair Die 인지 Loaded Die 인지 모르는 상태입니다. 다시 말하자면 현재 Hidden State 이 무엇인지 모른다는 얘기입니다. 아무리 관측 값들이 있다고 하더라도 이것은 모른다는 얘기죠.
그래도 관측 값들을 이용해서 모델링을 해줘서 미래 Outcome 에 대해서 예측을 해야겠죠? 그러기 위해서는 모델링을 해줘야 합니다. 즉 아 주사위는 두 개의 State 가 있고 각각의 주사위는 6가지 중 하나를 뱉는다는 세팅을 만들어준다 이라는 모델을 구축해야하며, 이것을 Posterior 으로 표현했을 뿐인 것입니다.
그렇다면 만약에 우리의 믿음으로는 주사위 종류가 Fair / Loaded 밖에 없다고 생각해서 모델링을 관측 값들에 의해서 그렇게 구성했지만, 실제로 관측 값들은 Fair / Loaded 1 / Loaded 2 으로 만들어진다면 어떻게 될까요?
$\rightarrow$ 당연하게도 추론 (Inference) 가 왜곡이 됩니다. 한 마디로 잘못된 Belief 가 생기며 이럴 때는 다르게 세팅하거나 Non-Parametric 모델도 고려해볼 수가 있습니다.

여기에서 정의를 몇개 해주는데, 그거에 대한 설명입니다.

Smoothing Distribution $p(z_t\mid y_{1:T})$ : 모델의 모든 Hidden 노드들에 대한 Posterior.

Filtering Distribution / Belief State $p(z_t = j \mid y_{1:t})$ (근데 정확하게는 =j 가 없어도 되긴 하다) : 현시점 + 현시점의 이전 시점들의 관측값들이 주어진 상태에서 현 시점 $t$ 의 Hidden 노드에 대한 확률.
이것을

그러면 Casino 상황에서의 Smoothing Distribution 은 다음과 같이 나오게 됩니다.

\begin{aligned} p\left(\boldsymbol{z}_t=j \mid \boldsymbol{y}_{t+1: T}, \boldsymbol{y}_{1: t}\right) &\propto p\left(\boldsymbol{z}_t=j, \boldsymbol{y}_{t+1: T} \mid \boldsymbol{y}_{1: t}\right) \\&=p\left(\boldsymbol{z}_t=j \mid \boldsymbol{y}_{1: t}\right) p\left(\boldsymbol{y}_{t+1: T} \mid \boldsymbol{z}_t=j, \boldsymbol{y}_{1: t}\right) \\&=p\left(\boldsymbol{z}_t=j \mid \boldsymbol{y}_{1: t}\right) p\left(\boldsymbol{y}_{t+1: T} \mid \boldsymbol{z}_t=j\right) \end{aligned}

수식어 설명 :
$\begin{aligned} p\left(\boldsymbol{z}_t=j \mid \boldsymbol{y}_{t+1: T}, \boldsymbol{y}_{1: t}\right) &= \frac{p\left(\boldsymbol{z}_t = j, \boldsymbol{y}_{t+1:T} \mid \boldsymbol{y}_{1:t} \right)}{p\left( \boldsymbol{y}_{t+1:T} \mid \boldsymbol{y}_{1:t} \right)} \\&\propto p\left(\boldsymbol{z}_t=j, \boldsymbol{y}_{t+1: T} \mid \boldsymbol{y}_{1: t}\right) \\&=p\left(\boldsymbol{z}_t=j \mid \boldsymbol{y}_{1: t}\right) p\left(\boldsymbol{y}_{t+1: T} \mid \boldsymbol{z}_t=j, \boldsymbol{y}_{1: t}\right) \\\text{(Markov property)} &=p\left(\boldsymbol{z}_t=j \mid \boldsymbol{y}_{1: t}\right) p\left(\boldsymbol{y}_{t+1: T} \mid \boldsymbol{z}_t=j\right) \end{aligned}$

Hidden Node 에 대한 Posterior 인 Smoothing Distribution 을 구축했으니 이제는 다음을 할 것입니다.

Forwards in Time (앞에서 시작하는 것) 으로 가면서 Belief State $p(z_t = j \mid y_{1:t})$ 를 구하는 것.

Backwards in Time (뒤에서 시작하는 것) 으로 가면서 $p(y_{t+1 : T} \mid z_t = j)$ 를 구하는 것.

두 개를 합쳐서 Smoothing Distribution 을 구해주기.

1번과 2번 Passes 가 둘다 $(TK^2)$ 만큼의 시간이 걸린다고 한다. $K$ : # of Discrete Hidden States (2).

번외
- Filtering Distribution 과 Belief State 는 사실상 똑같은데, Robotics 에서 후자 텀을 사용한다고 한다.

9.2.2 The Forwards Algorithm

넘어가기 앞서서 잠시 TMI 를 하자면, Bayes Filter 이란 것은 $p(z_t \mid y_{1:t})$ 를 구하기 위해서 Prior Belief $p(z_{t-1} \mid y_{1:t-1})$ 과 새로운 관측인 $y_t$ 그리고 모델을 이용하는 알고리즘이라고 하며 8.1.2 에서 배운다고 한다. HMM 관점에서는 이 알고리즘을 그저 Forwards Algorithm 이라고 부른다.

HMM 은 Latent State $z_t$ 가 Discrete 합니다. 그렇기에 정의를 다음과 같이 하겠습니다.

$\alpha_t(j) \triangleq p(z_t = j \mid \boldsymbol{y}_{1:t})$ : Belief State (벡터)

$\lambda_t(j) \triangleq p(\boldsymbol{y}_t \mid z_t = j)$ : Local Evidence (벡터)

$A_{i,j} = p(z_t = j \mid z_{t-1} = i)$ : Transition Matrix (행렬)

이렇게 정의를 했다면, Predict Step 은 다음과 같이 표현할 수 있습니다.

\begin{aligned} \alpha_{t \mid t-1}(j) &\triangleq p\left(z_t=j \mid \boldsymbol{y}_{1: t-1}\right)\\&= \sum_i p\left(z_t=j \mid z_{t-1}=i\right) \cdot p\left(z_{t-1}=i \mid \boldsymbol{y}_{1: t-1}\right)=\sum_i A_{i, j} \alpha_{t-1}(i) \end{aligned}

수식 설명
$\begin{aligned} p\left(z_t=j \mid y_{1: t-1}\right)= & p\left(z_t=j \mid z_{t-1}\right) \cdot p\left(z_{t-1} \mid y_{1: t-1}\right) \\= & p\left(z_t=j \mid z_{t-1}=i_1\right) \cdot p\left(z_{t-1}=i_1 \mid y_{1: t-1}\right) \\& + p\left(z_t=j \mid z_{t-1}=i_2\right) \cdot p\left(z_{t-1}=i_2 \mid y_{1: t-1}\right) \\& +\cdots \\& + p\left(z_t=j \mid z_{t-1}=i_K\right) \cdot p\left(z_{t-1}=i_K \mid y_{1: t-1}\right)\end{aligned}$
마지막 $=$ 의 경우 Marginalization for Discrete Case 를 생각해보면 됩니다.

Update Step 은 다음과 같이 나오게 됩니다. $\alpha_t(j) = p(z_t = j \mid y_{1:t})$

\begin{aligned} \alpha_t(j)&=\frac{1}{Z_t} p\left(\boldsymbol{y}_t \mid z_t=j\right) p\left(z_t=j \mid \boldsymbol{y}_{1: t-1}\right) \\&=\frac{1}{Z_t} \lambda_t(j) \alpha_{t \mid t-1}(j)=\frac{1}{Z_t} \lambda_t(j)\left[\sum_i \alpha_{t-1}(i) A_{i, j}\right] \end{aligned}

이때 나오는 Normalization Constant for each Time Step $Z_t$ 는 다음과 같습니다.

Z_t \triangleq p\left(\boldsymbol{y}_t \mid \boldsymbol{y}_{1: t-1}\right)=\sum_{j=1}^K p\left(\boldsymbol{y}_t \mid \boldsymbol{z}_t=j\right) p\left(\boldsymbol{z}_t=j \mid \boldsymbol{y}_{1: t-1}\right)=\sum_{j=1}^K \lambda_t(j) \alpha_{t \mid t-1}(j)

수식 설명
Update Step 이란 것은 Belief State 을 이전에 구했던 Predict Step 을 이용해서 구하는 것입니다.
$\begin{aligned} \alpha_t(j) &= p(z_t = j \mid y_{1:t}) = p(z_t = j \mid y_t, y_{1:t-1}) \\&= \frac{p(y_t \mid z_t = j, y_{1:t-1}) \cdot p(z_t = j \mid y_{1:t-1})}{p(y_t \mid y_{1:t-1})} \\&=\frac{1}{Z_t} \cdot p(y_t \mid z_t = j, y_{1:t-1}) \cdot p(z_t = j \mid y_{1:t-1}) \\&=\frac{1}{Z_t} \cdot p(y_t \mid z_t = j) \cdot \underbrace{p(z_t = j \mid y_{1:t-1})}_{\text{Predict Step}} \end{aligned}$
Normalization Constant 의 경우 그저 Marginalization for Discrete Case 를 생각해보면 됩니다. 어차피 저희가 지금 궁금한 것은 “ $z_t$ 가 어떤 State 에 있을까?” 에 대해서이기 때문에 $z_t$ 가 없는 확률에 대해서는 신경을 안 써도 됩니다.

Update Step 의 경우 그러면 다음과 같은 Matrix-Vector Notation 으로 표현해줄 수 있습니다.

\boldsymbol{\alpha}_t=\operatorname{normalize}\left(\boldsymbol{\lambda}_t \odot\left(\mathbf{A}^{\top} \boldsymbol{\alpha}_{t-1}\right)\right)

이것에 대해서 실제로 Dishonest Casino 에 적용을 시켜보았을 때 다음과 같이 결과가 나왔다고 합니다.

회색 부분들이 Loaded, 흰색 부분들이 Fair 이며 y-축은 $p(\text{loaded})$ 입니다. 정확하지는 않지만 대략적으로 잘 맞추는 모습을 보이고 있지만, Smooth 하지 않다는 것을 알 수가 있습니다.

9.2.3 The Forwards-Backwards Algorithm

여기에서는 HMM 에서 Smoothing 하기 위해서 가장 많이 사용되는 방법인 Forward-Backward / FB Algorithm 에 대해서 설명합니다.

Forward Pass 에서 저희는 $\alpha_t(j) = p(z_t = j \mid y_{1:t})$ 에 대해서 구했습니다. 하지만 Backward Pass 에서는 9.2.1 에서도 설명했듯이 다음을 구하는게 목적입니다.

\beta_t(j) \triangleq p\left(\boldsymbol{y}_{t+1: T} \mid \boldsymbol{z}_t=j\right)

Forward 과 Backward 를 합쳐서 다음을 구하게 됩니다.

\begin{aligned}\gamma_t(j) & =p\left(\boldsymbol{z}_t=j \mid \boldsymbol{y}_{t+1: T}, \boldsymbol{y}_{1: t}\right) \propto p\left(\boldsymbol{z}_t=j, \boldsymbol{y}_{t+1: T} \mid \boldsymbol{y}_{1: t}\right) \\& =p\left(\boldsymbol{z}_t=j \mid \boldsymbol{y}_{1: t}\right) p\left(\boldsymbol{y}_{t+1: T} \mid \boldsymbol{z}_t=j, \cancel{\boldsymbol{y}_{1: t}}\right)=\alpha_t(j) \beta_t(j)\end{aligned}

TMI
Forward 이랑 Backward Pass 둘다 Local Evidence $p(\boldsymbol{y}_t \mid \boldsymbol{z}_t)$ 가 필요하며, 마지막에는 둘다 합쳐져서 Two-Filter Smoothing 이라고 불립니다.

9.2.3.1 Backwards Recursion

Backwards Pass 는 $p(y_{t+1:T} \mid z_t = j)$ 를 구하는게 목표이며, 이것을 구하기 위해서 다음과 같이
오른쪽 $\rightarrow$ 왼쪽 으로 Recursive 하게 구할 수가 있습니다.

\begin{aligned}\beta_{t-1}(i) & =p\left(\boldsymbol{y}_{t: T} \mid \boldsymbol{z}_{t-1}=i\right) \\& =\sum_j p\left(\boldsymbol{z}_t=j, \boldsymbol{y}_t, \boldsymbol{y}_{t+1: T} \mid \boldsymbol{z}_{t-1}=i\right) \\& =\sum_j p\left(\boldsymbol{y}_{t+1: T} \mid \boldsymbol{z}_t=j, \cancel{\boldsymbol{y}_t}, \cancel{\boldsymbol{z}_{t-1}=i}\right) p\left(\boldsymbol{z}_t=j, \boldsymbol{y}_t \mid \boldsymbol{z}_{t-1}=i\right) \\& =\sum_j p\left(\boldsymbol{y}_{t+1: T} \mid \boldsymbol{z}_t=j\right) p\left(\boldsymbol{y}_t \mid \boldsymbol{z}_t=j, \cancel{\boldsymbol{z}_{t-1}=i}\right) p\left(\boldsymbol{z}_t=j \mid \boldsymbol{z}_{t-1}=i\right) \\& =\sum_j \beta_t(j) \lambda_t(j) A_{i, j}\end{aligned}

이것도 비슷하게 Matrix-Vector Form 으로 다음과 같이 표현해줄 수 있습니다.

\boldsymbol{\beta}_{t-1}=\mathbf{A}\left(\boldsymbol{\lambda}_t \odot \boldsymbol{\beta}_t\right)

Base Case 인 $t = T$ 일 때의 경우는 다음과 같습니다.

\beta_T(i)=p\left(\boldsymbol{y}_{T+1: T} \mid \boldsymbol{z}_T=i\right)=p\left(\emptyset \mid \boldsymbol{z}_T=i\right)=1

번외
$\boldsymbol{\beta}_t$ 는 사실 엄밀히 따지자면 State 에 대한 확률분포는 아닙니다. 왜냐하면 $\sum_j \beta_t(j) = 1$ 을 만족할 필요가 없기 때문입니다.
$\sum_j \beta_t(j) = \sum_j p(\boldsymbol{y}_{t+1:T} \mid \boldsymbol{z}_{t} = j)$
하지만 그래도 Normalize 을 시킨다고 하며, 이는 Underflow 방지 때문이라고 합니다.

9.2.3.2 Example

Forward-Backwards Algorithm 을 Dishonest Casino 에 구현해본 결과는 다음과 같습니다.

9.2.3.3 Two-slice Smoothed Marginals

다시 또 정리를 하자면, Notation 은 다음과 같습니다.

$\alpha_t(j) = p({z}_t = j \mid \boldsymbol{y}_{1:t})$

$\alpha_{t \mid t-1}(j) = p\left(z_t=j \mid \boldsymbol{y}_{1: t-1}\right)$

$\beta_{t+1}(j) = p(\boldsymbol{y}_{t+2:T} \mid {z}_{t+1} = j)$

$\gamma_t(j) \propto p( z_t = j, \boldsymbol y_{t+1:T} \mid \boldsymbol y_{1:t}) = \alpha_t(j) \beta_t(j)$

$\lambda_t(j) = p(\boldsymbol{y}_t \mid z_t = j)$

$A_{i,j} = p(z_t = j \mid z_{t-1} = i)$ , (그림에서의 Notation 은 조금 다른 듯 합니다)

Two-slice Joint Distribution $p(z_t, z_{t+1} \mid \boldsymbol{y}_{1:T})$ 을 구하기 위한 과정을 그림 표현하면 다음과 같습니다.

파랑색 선들이 $z_t$ 에 대한 분포를 알기 위해서 필요한 정보 (Message) 이라고 보시면 될 것 같습니다. 이때의 Message 종류는 Forward Message $\alpha_{t \mid t-1}$ , Backward Message $\beta_{t+1}$ , 그리고 Local Evidence Message $\lambda_t$ 들입니다. 위의 Two-slice Marginal 인 $p(z_t, z_{t+1} \mid \boldsymbol{y}_{1:T})$ 를 구하기 위해서 다음과 같이 전개시킬 수 있습니다.

\begin{aligned} p\left(\boldsymbol{z}_t, \boldsymbol{z}_{t+1} \mid \boldsymbol{y}_{1: T}\right) & =p\left(\boldsymbol{z}_t, \boldsymbol{z}_{t+1} \mid \boldsymbol{y}_{1: t}, \boldsymbol{y}_{t+1: T}\right) \\& \propto p\left(\boldsymbol{y}_{t+1: T} \mid \boldsymbol{z}_t, \boldsymbol{z}_{t+1}, \boldsymbol{y}_{1: t}\right) p\left(\boldsymbol{z}_t, \boldsymbol{z}_{t+1} \mid \boldsymbol{y}_{1: t}\right) \\& =p\left(\boldsymbol{y}_{t+1: T} \mid \boldsymbol{z}_{t+1}\right) p\left(\boldsymbol{z}_t, \boldsymbol{z}_{t+1} \mid \boldsymbol{y}_{1: t}\right) \\& =p\left(\boldsymbol{y}_{t+1: T} \mid \boldsymbol{z}_{t+1}\right) p\left(\boldsymbol{z}_t \mid \boldsymbol{y}_{1: t}\right) p\left(\boldsymbol{z}_{t+1} \mid \boldsymbol{z}_t\right) \\& =p\left(\boldsymbol{y}_{t+1}, \boldsymbol{y}_{t+2: T} \mid \boldsymbol{z}_{t+1}\right) p\left(\boldsymbol{z}_t \mid \boldsymbol{y}_{1: t}\right) p\left(\boldsymbol{z}_{t+1} \mid \boldsymbol{z}_t\right) \\& =p\left(\boldsymbol{y}_{t+1} \mid \boldsymbol{z}_{t+1}\right) p\left(\boldsymbol{y}_{t+2: T} \mid \boldsymbol{z}_{t+1}, \boldsymbol{y}_{t+1}\right) p\left(\boldsymbol{z}_t \mid \boldsymbol{y}_{1: t}\right) p\left(\boldsymbol{z}_{t+1} \mid \boldsymbol{z}_t\right) \\& =\underbrace{p\left(\boldsymbol{y}_{t+1} \mid \boldsymbol{z}_{t+1}\right)}_{\lambda_{t+1}} \cdot \underbrace{p\left(\boldsymbol{y}_{t+2: T} \mid \boldsymbol{z}_{t+1}\right)}_{\beta_{t+1}} \cdot \underbrace{p\left(\boldsymbol{z}_t \mid \boldsymbol{y}_{1: t}\right)}_{\alpha_t} \cdot \underbrace{p\left(\boldsymbol{z}_{t+1} \mid \boldsymbol{z}_t\right)}_{A_{i,j}} \end{aligned}

이것을 다음과 같이 간단화 시킬 수 있게 됩니다.

p\left(z_t = i, z_{t+1} = j \mid \boldsymbol{y}_{1: T}\right) = \xi_{t, t+1}(i,j) \propto \lambda_{t+1}(j) \cdot \beta_{t+1}(j) \cdot \alpha_t(i) \cdot A_{i,j}

혹은 다음과 같이 Matrix-Vector Form 으로도 바꿀 수가 있습니다.

\boldsymbol{\xi}_{t, t+1} \propto \mathbf{A} \odot\left[\boldsymbol{\alpha}_t\left(\boldsymbol{\lambda}_{t+1} \odot \boldsymbol{\beta}_{t+1}\right)^{\top}\right] \propto \mathbf{A} \odot\left[\left(\boldsymbol{\lambda}_t \odot \boldsymbol{\alpha}_{t \mid t-1}\right) \odot\left(\boldsymbol{\lambda}_{t+1} \odot \boldsymbol{\beta}_{t+1}\right)^{\mathrm{T}}\right]

9.2.3.4 Numerically Stable Implementation

(조금 TMI 가 있는 절)

대부분의 HMM 관련 논문들은 Unnormalized Joint Probability 를 사용합니다 ( $\alpha^\prime_t(j) = p(z_t = j , \boldsymbol{y}_{1:t})$ ). 하지만 저희는 Forward Message 를 Normalized Conditional Probability 를 사용하며 ( $\alpha_t(j) = p(z_t = j \mid \boldsymbol{y}_{1:t})$ ), 이에 대한 이유는 다음과 같습니다.

Numerical Underflow 유도, Joint 확률 자체가 작기에.

해석하기도 더 어렵다. State 에 대한 정확한 분포이기에.

알고리즘 적으로는 사실 $\texttt{normalize}$ 를 사용하냐 안하냐 차이 이긴 하지만, 그래도 Normalized 버전을 사용하는 것이 훨씬 구현하기도 쉽기에 교재에서 강조하고 싶다고 합니다.

9.2.4 Forwards Filtering Backwards Smoothing

앞서 말씀드린 Forwards Backwards Algorithm 와는 달리 Smoothing 시키는 방법이 또 있으며, 이는 Forwards Filtering 과 Backwards Filtering 을 사용하는 것이며, 이 방법은 연속적인 Latent State 가 있는 SSM 들이 자주 사용하는 방법이라고 합니다.

일단은 Induction 으로 다음이 이미 계산되었다고 가정하겠습니다.

\gamma_{t+1}(j) \triangleq p\left(\boldsymbol{z}_{t+1}=j \mid \boldsymbol{y}_{1: T}\right)

그러면 $\xi_{t, t+1}(i,j)$ 의 정확한 값을 다음과 같이 구할 수 있습니다.

\begin{aligned}\xi_{t, t+1}(i, j) & \triangleq p\left(\boldsymbol{z}_t=i, \boldsymbol{z}_{t+1}=j \mid \boldsymbol{y}_{1: T}=p\left(\boldsymbol{z}_t=i \mid \boldsymbol{z}_{t+1}=j, \boldsymbol{y}_{1: t}\right) p\left(\boldsymbol{z}_{t+1}=j \mid \boldsymbol{y}_{1: T}\right)\right. \\& =\frac{p\left(\boldsymbol{z}_{t+1}=j \mid \boldsymbol{z}_t=i\right) p\left(\boldsymbol{z}_t=i \mid \boldsymbol{y}_{1: t}\right) p\left(\boldsymbol{z}_{t+1}=j \mid \boldsymbol{y}_{1: T}\right)}{p\left(\boldsymbol{z}_{t+1}=j \mid \boldsymbol{y}_{1: t}\right)} \\& =\alpha_t(i) A_{i, j} \frac{\gamma_{t+1}(j)}{\alpha_{t+1 \mid t}(j)}\end{aligned}

One-step Prediction 은 다음과 같으며,

\alpha_{t+1 \mid t}(j)=p\left(\boldsymbol{z}_{t+1}=j \mid \boldsymbol{y}_{1: t}\right)=\sum_{i^{\prime}} A\left(i^{\prime}, j\right) \alpha_t\left(i^{\prime}\right)

Two-sliced smoothed Distribution 이 있으니 이것을 Marginalize 시키면 One slice smoothed distribution 이 다음과 같이 나오게 됩니다.

\gamma_t(i)=p\left(\boldsymbol{z}_t=i \mid \boldsymbol{y}_{1: T}\right)=\sum_j \xi_{t, t+1}(i, j)=\alpha_t(i) \sum_j\left[A_{i, j} \frac{\gamma_{t+1}(j)}{\alpha_{t+1 \mid t}(j)}\right]

9.2.5 Time and Space Complexity

실제로 구현을 하면 $O(K^2 T)$ 만큼 필요하며, 이는 매 시점마다 Forward + Backward 둘다 State $j$ 에 대해서 Summation (시그마 텀) 과 모든 State $j$ 에 대해서 Compute 를 해야하기 때문입니다. $K$ 가 매우 크다면 이게 문제가 되지만, Transition Matrix 가 Sparse 하다면 줄일 수 있게 됩니다.

예시로 만약에 Transition Matrix 가 $A_{i,j} \propto \rho(z_j - z_i)$ 의 관계를 만족하며 $\rho(\cdot)$ 이 어떠한 Scalar Cost function 이면, 우리가 구해야 되는 식 중 하나인 $\alpha_{t\mid t-1}(j)$ 를 다음과 같이 Convolution 형태로 연산시켜주면 됩니다.

\alpha_{t \mid t-1}(j)=p\left(z_t=j \mid \boldsymbol{y}_{1: t-1}\right)=\sum_i \alpha_{t-1}(i) A_{i, j}=\sum_i \alpha_{t-1}(i) \rho(j-i)

이렇게 한다면 $O(TK \log K)$ 시간으로 줄일 수 있게 됩니다.

9.2.6 The Viterbi Algorithm

MAP Estimate 정의로는 Posterior 확률을 최대화 시켜주는 것과 같으며, 이것을 저희의 HMM 상황에 도입하면 다음과 같습니다.

\begin{aligned}\boldsymbol{z}_{1: T}^* & =\underset{\boldsymbol{z}_{1: T}}{\operatorname{argmax}}\ p\left(\boldsymbol{z}_{1: T} \mid \boldsymbol{y}_{1: T}\right)=\underset{\boldsymbol{z}_{1: T}}{\operatorname{argmax}} \log p\left(\boldsymbol{z}_{1: T} \mid \boldsymbol{y}_{1: T}\right) \\& =\underset{\boldsymbol{z}_{1: T}}{\operatorname{argmax}} \log \pi_1\left(\boldsymbol{z}_1\right)+\log \lambda_1\left(\boldsymbol{z}_1\right)+\sum_{t=2}^T\left[\log A\left(\boldsymbol{z}_{t-1}, \boldsymbol{z}_t\right)+\log \lambda_t\left(\boldsymbol{z}_t\right)\right]\end{aligned}

이때 Notation 이 또 다시 헷갈릴 수도 있으니 다음과 같이 정리하겠습니다.

$\pi_1(z_1) = p(z_1)$

$\lambda_1(z_1) = p(y_1 \mid z_1)$

$A(z_{t-1}, z_t) = p(z_t \mid z_{t-1})$

$\lambda_t(z_t) = p(y_t \mid z_t)$

바로 다룰거긴 하지만, 위의 식에 대한 MAP Estimate 을 구하는 것은 다음의 Trellis Diagram 에서 가장 짧은 Path 을 구하는 것과 똑같습니다.

일반적인 HMM 과는 다르게 시점 t (x-축) 에 나는 확실하게 State i (y-축) 에 속해있다는 것을 알려줌.

이것은 Viterbi Algorithm 을 통해서 $O(TK^2)$ 만에 구하는게 가능하다고 합니다.

9.2.6.1 Forwards Pass

Unnormalized Forwards Equation 은 다음과 같습니다.

\alpha_t^{\prime}(j)=p\left(\boldsymbol{z}_t=j, \boldsymbol{y}_{1: t}\right)=\sum_{\boldsymbol{z}_1, \ldots, \boldsymbol{z}_{t-1}} p\left(\boldsymbol{z}_{1: t-1}, \boldsymbol{z}_t=j, \boldsymbol{y}_{1: t}\right)

이때 Summation 부분을 Maximum 으로 바꿔줍니다. Viterbi Algorithm 의 경우 확률을 뱉는 것이 아닌 가장 나올 것 같은 값을 뱉어야 하기에 이렇게 Maximum 을 사용해줍니다.

\delta_t(j) \triangleq \max _{\boldsymbol{z}_1, \ldots, \boldsymbol{z}_{t-1}} p\left(\boldsymbol{z}_{1: t-1}, \boldsymbol{z}_t=j, \boldsymbol{y}_{1: t}\right) = \lambda_t(j)\left[\max _i \delta_{t-1}(i) A_{i, j}\right]

여기에 로그까지 씌워준다면 Numerical Issue 도 피할 수 있으며, 다음과 같이 마무리할 수 있게 됩니다.

\delta_t^{\prime}(j)=\lambda_t^{\prime}(j)+\left[\min _i \delta_{t-1}^{\prime}(i)+A^{\prime}(i, j)\right]

$\delta_t^{\prime}(j)=-\log \delta_t(j)$

$\lambda^\prime_t(j) = -\log p(\boldsymbol{y}_t \mid z_t = j)$

$A^\prime(i,j) = -\log p(z_t = j \mid z_{t-1} = i)$

근데 이때 Minimum 값을 주었던 $i$ 값도 알아야 하기에 다음과 같은 $a_t(j)$ 값도 저장을 해줘야합니다 (Backwards Pass 에서 사용됨).

a_t(j) \triangleq \underset{i}{\operatorname{argmax}} \delta_{t-1}(i) A_{i, j}=\underset{i}{\operatorname{argmin}} \delta_{t-1}^{\prime}(i)+A^{\prime}(i, j)

초깃값은 다음과 같습니다. $\delta_1(j) = \pi_j \lambda_1(j)$

9.2.6.2 Backwards Pass

여기에서 저희는 어떤 State 들이 가장 일어날만 한지 골라주기만 하면 되며,

9.2.6.3 Example

Dishonest Casino 에서의 결과는 다음과 같습니다.

다른 예시도 있으며 이는 다음과 같습니다.

9.2.6.4 Time and Space Complexity

Time Complexity : $O(K^2 T)$

Space Complexity : $O(KT)$

9.2.6.5 N-best List

가끔씩은 Likelihood 값이 똑같을 때가 있습니다. 이것은 특히 Speech Recognition 에서 많이 보인다고 하는데요, 이것은 그저 시점 $t$ 에서 Top-N 개를 저장시켜준 다음에 다음 시점들에 대해서 이 값들을 비교하면서 가장 좋은 Path 를 Rerank 시켜주면 됩니다.

9.2.7 Forwards Filtering Backwards Sampling

Forwards Filtering Backwards Smoothing 알고리즘에서는 Marginal 을 구했었는데, 이렇게 하기 보다는 Posterior 에서 여러 Path 들을 샘플링을 우선적으로 하는게 효과적입니다. 이것을 바로 Forwards Filtering Backwards Sampling 이라고 불리며, Backwards Pass 에서의 Joint 를 다음과 같이 적을 수 있습니다.

\begin{aligned} p\left(\boldsymbol{z}_{1: T} \mid \boldsymbol{y}_{1: T}\right) & =p\left(\boldsymbol{z}_T \mid \boldsymbol{y}_{1: T}\right) p\left(\boldsymbol{z}_{T-1} \mid \boldsymbol{z}_T, \boldsymbol{y}_{1: T}\right) p\left(\boldsymbol{z}_{T-2} \mid \boldsymbol{z}_{T-1}, \cancel{\boldsymbol{z}_T}, \boldsymbol{y}_{1: T}\right) \cdots \\ &\cdots p\left(\boldsymbol{z}_1 \mid \boldsymbol{z}_2, \cancel{\boldsymbol{z}_{3: T}}, \boldsymbol{y}_{1: T}\right) \\& =p\left(\boldsymbol{z}_T \mid \boldsymbol{y}_{1: T}\right) \prod_{t=T-1}^1 p\left(\boldsymbol{z}_t \mid \boldsymbol{z}_{t+1}, \boldsymbol{y}_{1: T}\right)\end{aligned}

그러면 Step $t$ 에서 Product 에서의 뒷텀인 $p(\boldsymbol z_t \mid \boldsymbol z_{t+1}, \boldsymbol y_{1:T})$ 에서 $\boldsymbol z_t^s$ 를 샘플링 해주면 됩니다.

9.3 Belief Propagation on Trees

저희가 배웠던 Forwards-Backwards Algorithm 의 경우 Chain 구조의 Graphical Model 에서 Message Passing Algorithm 으로 사용될 수 있으며, 이번 장에서는 그 알고리즘들이 Tree 와도 상호작용이 가능하게끔 만들어줍니다.

9.3.1 Directed vs Undirected Trees

Pairwise Undirected Graphical Model 을 다음과 같이 고려해볼 수 있습니다.

p^*(\boldsymbol{z}) \triangleq p(\boldsymbol{z} \mid \boldsymbol{y}) \propto \prod_{s \in \mathcal{V}} \psi_s\left(z_s \mid \boldsymbol{y}_s\right) \prod_{(s, t) \in \mathcal{E}} \psi_{s, t}\left(z_s, z_t\right)

$\psi_{s,t}(z_s, z_t)$ : Pairwise Cique Potential (One per Edge), Chain 에서는 $p(z_t \mid z_{t-1})$ 이다.

$\psi_s(z_s \mid \boldsymbol y_s)$ : Local Evidence Potentials (One per Node), Chain 에서는 $p(y_t \mid z_t)$ 이다.

$\mathcal{V}$ : Set of Nodes

$\mathcal E$ : Set of Edges

편의성을 위해서 $\boldsymbol y_s$ 에 대해서의 Conditioning 은 잠시 생략한다고 합니다. 위와 같은 구성을 저희는 Tree 로 상상할 수 있으며, Undirected 인 경우 하단의 (a) 처럼 생기게 됩니다.

Directed Tree 으로 만들기 위해서는 그저 임의의 노드를 Root 으로 잡고 그 Node 부터 Edge 들을 구성시켜주면 됩니다.

예시 1 (b) : 노드 1 에서 시작.

p^*(\boldsymbol{z}) \propto p^*\left(z_1\right) p^*\left(z_2 \mid z_1\right) p^*\left(z_3 \mid z_2\right) p^*\left(z_4 \mid z_2\right)

예시 2 (c) : 노드 2 에서 시작.

p^*(\boldsymbol{z}) \propto p^*\left(z_2\right) p^*\left(z_1 \mid z_2\right) p^*\left(z_3 \mid z_2\right) p^*\left(z_4 \mid z_2\right)

다시 Undirected Tree 으로 돌아오자면, 다음과 같이 정의를 하게 된다면

$\psi_s(z_s) \propto p^*(z_s)$

$\psi_{s,t} (z_s, z_t) = p^*(z_s, z_t)$

저희는 Undirected Tree 를 다음과 같이 쓸 수 있게 됩니다.

p^*(\boldsymbol{z}) \propto \prod_{s \in \mathcal{V}} p^*\left(z_s\right) \prod_{(s, t) \in \mathcal{E}} \frac{p^*\left(z_s, z_t\right)}{p^*\left(z_s\right) p^*\left(z_t\right)}

분모의 경우 이미 $p^*(z_s, z_t)$ 가 $p^*(z_s), p^*(z_t)$ 에 대한 정보를 내포하고 있기 때문에 노드 $z_s$ 를 Edge 마다 한번 더 고려하게 된다는 것입니다. 그렇기에 분모 자리에 나눠주게 됩니다.

번외
(a) 의 경우에는 다음과 같이 쓸 수 있게 됩니다.
$p^*\left(z_1, z_2, z_3, z_4\right) \propto p^*\left(z_1\right) p^*\left(z_2\right) p^*\left(z_3\right) p^*\left(z_4\right) \frac{p^*\left(z_1, z_2\right) p^*\left(z_2, z_3\right) p^*\left(z_2, z_4\right)}{p^*\left(z_1\right) p^*\left(z_2\right) p^*\left(z_2\right) p^*\left(z_3\right) p^*\left(z_2\right) p^*\left(z_4\right)}$
(c) 의 경우에는 Undirected Graph 식에서 Cancel 을 하면 다음과 같이 쓸 수 있게 됩니다.
$\begin{aligned}p^*\left(z_1, z_2, z_3, z_4\right) & \propto p^*\left(z_1, z_2\right) \frac{p^*\left(z_2, z_3\right)}{p^*\left(z_2\right)} \frac{p^*\left(z_2, z_4\right)}{p^*\left(z_2\right)} \\& =p^*\left(z_1\right) p^*\left(z_2 \mid z_1\right) p^*\left(z_3 \mid z_2\right) p^*\left(z_4 \mid z_2\right) \\& =p^*\left(z_2\right) p^*\left(z_1 \mid z_2\right) p^*\left(z_3 \mid z_2\right) p^*\left(z_4 \mid z_2\right)\end{aligned}$
즉 Tree 는 Undirected / Directed Graph 으로 표현이 가능합니다.

9.3.2 Sum-Product Algorithm

Undirected Tree 라고 가정하며 임의의 노드를 Root 으로 그리고 이 노드로부터 아래로 퍼지는 모든 Edge 들을 고려해볼 겁니다. 그렇게 된다면 모든 노드들이 Unique 한 Parent 를 가지게 됩니다. (Directed Tree 의 경우에는 다양한 Node Ordering 을 고려할 수 있습니다.)

그러면 $p^*(z)$ 에 대해서 구하기 이전에 Order 에 대해서 설명하겠습니다. Root 가 맨 좌측에서 시작해서 Left Subtree, Right Subtree 으로 간다고 가정하겠습니다.

Pre-order : Root $\rightarrow$ Left Sub-tree $\rightarrow$ Right Sub-tree, Root $\rightarrow$ Leaves

Post-order : Right Sub-tree $\rightarrow$ Left Sub-tree $\rightarrow$ Root, Leaves $\rightarrow$ Root

그러면 Post-Order 부터 진행하겠습니다.

Post-Order (Generalization of Forwards Pass)

$m_{s\rightarrow t}(z_t)$ : Node $s$ 에서 Node $t$ 으로 가는 Message, 즉 $s-t$ Edge 밑에 있는 모든 Evidence 가 주어진 상태에서 $z_t$ 에 대한 Belief State 를 요약해준다.

$\operatorname{bel}_s(z_s) \propto p(z_s \mid \text{All Observations Known})$

$\operatorname{ch}_s$ : Set of Children Nodes of Node $s$ .

그러면 Belief State 을 업데이트 할 때는 다음을 구해주면 됩니다.

\operatorname{bel}_s\left(z_s\right) \propto \psi_s\left(z_s\right) \prod_{t \in \mathrm{ch}_s} m_{t \rightarrow s}\left(z_s\right)

밑에서 시작하는 것이기 때문에 $s = \text{bottom}$ 이면 Children 이 없기에 $\prod_{t \in \operatorname{ch}_s} m_{t \rightarrow s}(z_s) = 1$ 이 됩니다.

이것을 구한 다음에는 노드 $s$ 의 Parent 를 $t$ 라고 하며 Parent $t$ 에게 보낼 메시지를 다음과 같이 구해줍니다.

m_{s \rightarrow t}\left(z_t\right)=\sum_{z_s} \psi_{s t}\left(z_s, z_t\right) \operatorname{bel}_s\left(z_s\right)

저희가 $z_s$ 에 대해서 Marginalize 시켜야하는 이유는 바로 Node $s$ 가 가질 수 있는 모든 State $z_s$ 에 대해서 Marginalize 시키고 난 다음에 $z_t$ 에 대한 함수로 표현하기 위함입니다.

Root 까지 도달하면 Belief State $\operatorname{bel}_t(z_t) = p(z_t \mid \boldsymbol y)$ 는 모든 Evidence 를 본 상태입니다. 이 상태에서 다시 Root 에서 아래로, 즉 Pre-Order 를 진행시키면 됩니다.

Pre-Order

노드 $s$ 가 Child $t$ 에게 보내는 메시지는 $s$ 가 $t$ 이외의 Child Node 에게 받은 메시지를 내포하고 있어야 합니다. 그렇기에 다음과 같이 구성이 됩니다. 아래 식과 같이 모두 연산하기 보다는 Post-Order 에서 구한 것을 활용하면 연산량이 훨씬 적어집니다.

m_{s \rightarrow t}\left(z_t\right)=\sum_{z_s}\left(\psi_s\left(z_s\right) \psi_{s t}\left(z_s, z_t\right) \prod_{u \in \mathrm{ch}_s \backslash t} m_{u \rightarrow s}\left(z_s\right)\right) = \sum_{z_s} \psi_{s t}\left(z_s, z_t\right) \frac{\operatorname{bel}_s\left(z_s\right)}{m_{t \rightarrow s}\left(z_s\right)}

이것을 통해서 또 다시 Belief State 을 다음과 같이 업데이트 시켜줍니다.

\operatorname{bel}_t\left(z_t\right) \propto \operatorname{bel}_t\left(z_t\right) m_{s \rightarrow t}\left(z_t\right)

전체적인 Pseudo-code 는 다음과 같습니다.

번외
도움이 될만한 Figure

9.3.3 Max-Product Algorihtm

Sum-Product Algorithm 의 경우 결국에는 다음과 같은 Posterior Marginal 을 구했습니다.

\operatorname{bel}_i(k)=\gamma_i(k)=p\left(z_i=k \mid \boldsymbol{y}\right)=\sum_{\boldsymbol{z}_{-i}} p\left(z_i=k, \boldsymbol{z}_{-i} \mid \boldsymbol{y}\right)

이때 우측 Term 의 Summation 을 $\max$ 으로 바꿔주기만 하면 Max-Product Belief Propagation 이 됩니다. 그러면 다음과 같이 구할 수 있게 됩니다.

\zeta_i(k)=\max _{\boldsymbol{z}_{-i}} p\left(z_i=k, \boldsymbol{z}_{-i} \mid \boldsymbol{y}\right)

일종의 Viterbi Algorithm 이라고 생각하면 편합니다. 이때 2 가지 MAP 와 비슷한 Estimate 을 구할 수 있다고 하며, 이는 다음과 같습니다.

Maximizer of Posterior Marginal (MPM) : $\hat{z}_i = \argmax_k \gamma_i(k)$

Maximizer of the Max Marginal (MMM) : $\tilde{z}_i = \argmax_k \zeta_i(k)$

너무 중요하지 않은 것 같으니 넘어가도록 하겠습니다.

9.4 Loopy Belief Propagation (LBP)

여태까지는 Loop 없이 Belief Propagation 을 했었지만, 이제부터는 Loop 가 있다면 어떻게 진행할지에 대해서 알아봅니다. 처음에는 Belief Propagation 을 진행하는 경우 수렴을 못할 수도 있기에 불가능하다고 하지만, 다양한 그래프 모델들에 Empirically 적용할 때 가능하다고 하며 특정 케이스에서의 이론도 존재한다고 합니다.

9.4.1 Loopy BP for Pairwise Undirected Graphs

우선은 그래프가 Tree 라는 형태를 띄운다는 가정을 버립니다. 노드들에 대한 자연스러운 Ordering 이 없기 때문입니다.

기본적인 아이디어는 모든 Belief 들을 한꺼번에 그리고 병렬적으로 업데이트 시켜준 다음에 Message 들을 한꺼번에 그리고 병렬적으로 업데이트 시켜주는 것입니다. 이러한 아키텍쳐를 systolic array 이라고 부릅니다.

(초깃값은 모든 메시지를 $1$ -벡터인 상태)
병렬적으로 모든 노드들의 Belief 를 다음과 같이 업데이트 시켜줍니다.
( $\operatorname{nbr}_s$ : Node $s$ 의 Neighboring Set)
$\operatorname{bel}_s\left(z_s\right) \propto \psi_s\left(z_s\right) \prod_{t \in \mathrm{nbr}_s} m_{t \rightarrow s}\left(z_s\right)$

병렬적으로 모든 노드가 Neighbor 들에게 보내주는 메시지를 다음과 같이 업데이트 시켜줍니다.
$m_{s \rightarrow t}\left(z_t\right)=\sum_{z_s}\left(\psi_s\left(z_s\right) \psi_{s t}\left(z_s, z_t\right) \prod_{u \in \mathrm{nbr}_s \backslash t} m_{u \rightarrow s}\left(z_s\right)\right)$

1번과 2번을 수렴할 때까지 반복합니다.

그래프가 Tree 구조를 띄우면 $D(G)$ iterations 이후에 수렴한다고 합니다.
( $D(G)$ : Diameter of Graph / Longest Distance between 2 Nodes)

9.4.2 Loopy BP for Factor Graphs

다음과 같은 Bipartite Factor Graph 를 고려해보겠습니다.

이때의 메시지는 사실 2 종류밖에 없으며 이는 다음과 같습니다.

Variables to Factors $(x \rightarrow f)$
$m_{x \rightarrow f}(x)=\prod_{h \in \operatorname{nbr}(x) \backslash\{f\}} m_{h \rightarrow x}(x)$

Factors to Variables $(f \rightarrow x)$
$m_{f \rightarrow x}(x)=\sum_{\boldsymbol{x}^{\prime}} f\left(x, \boldsymbol{x}^{\prime}\right) \prod_{x^{\prime} \in \operatorname{nbr}(f) \backslash\{x\}} m_{x^{\prime} \rightarrow f}\left(x^{\prime}\right)$

위 두 메시지가 수렴하게 된다면 Belief 를 다음과 같이 계산하면 됩니다.

m_{f \rightarrow x}(x)=\sum_{\boldsymbol{x}^{\prime}} f\left(x, \boldsymbol{x}^{\prime}\right) \prod_{x^{\prime} \in \operatorname{nbr}(f) \backslash\{x\}} m_{x^{\prime} \rightarrow f}\left(x^{\prime}\right)

이때 어떤 Message 들을 고르는지에 대해서는 Heuristic 을 통해서 결정된다고 합니다.

9.4.3 Gaussian Belief Propagation

Gaussian BP 의 예시로 1-차원에서 Noisy Data 를 Interpolating 한다고 생각해보면 편합니다. Notation 을 다음과 같이 사용하겠습니다.

$f: \mathbb{R} \rightarrow \mathbb{R}$ - 우리가 궁금한 Unknown Function, 그리고 데이터가 이거에 의해서 $N$ 개 만큼 만들어 졌다고 가정

$x_i$ : 데이터 / 관측 값 중 Location (Input) 을 의미
$x$ 자체의 의미는 그거지만, $x_i$ 의 경우 $g_i$ Grid Location 에서 관측이 된 가장 가까운 Location 을 의미함.

$y_i$ : 데이터 / 관측 값 중 Measurement (Output) 을 의미

$g_i$ : Location 중 우리가 궁금한 Location 이며 이것은 총 $G$ 개만큼 있다고 가정.

$z_i = f(g_i)$

그러면 Measurement Factor 가 다음과 같다고 가정을 해보겠습니다.

\begin{aligned}\psi_i\left(z_{i-1}, z_i\right) & =\frac{1}{\sigma^2}\left(\hat{y}_i-y_i\right)^2 \\\hat{y}_i & =\left(1-\gamma_i\right) z_{i-1}+\gamma_i z_i \\\gamma_i & =\frac{x_i-g_i}{g_i-g_{i-1}}\end{aligned}

여기에 Smoothness Potential 까지 고려하기 위해서 다음과 같은 Prior 도 두겠습니다.

\begin{aligned}\phi_i\left(z_{i-1}, z_i\right) & =\frac{1}{\tau^2} \delta_i^2 \\\delta_i & =z_i-z_{i-1}\end{aligned}

최종적으로 모델은 다음과 같이 구성시킬 수가 있습니다.

p\left(\boldsymbol{z} \mid \boldsymbol{x}, \boldsymbol{y}, \boldsymbol{g}, \sigma^2, \tau^2\right) \propto \prod_{i=1}^G \psi_i\left(z_{i-1}, z_i\right) \phi_i\left(z_{i-1}, z_i\right)

이것을 사인 함수에 대해서 적용시켰을 때의 결과는 다음과 같습니다.

9.4.4 Convergence

Loopy BP 의 경우 수렴을 안하거나 굉장히 느리게 수렴할 수도 있습니다. 그렇기에 수렴성의 확률을 높이거나 수렴 속도를 키우는 방법들에 대해서 다룬다고 합니다.

9.4.4.1 When will LBP Converge?

보통 이런 분석을 할 때는 Computation Tree 를 사용한다고 하며, 정확한 디테일은 Out-of-Scope 이라고 합니다. 예시로는 아래와 같습니다.

여기서의 핵심은 Loopy Graph 에서 $T$ Iterations 은 Computation Tree 에서의 $T+1$ Iterations 과 같다는 것입니다. Edge 들에 대한 Connection 이 약하다면 수렴성이 나타날 것입니다.

9.4.4.2 Making LBP Converge

LBP 가 수렴을 안하게 된다면 수렴할 확률을 올리기 위해서 다양한 방법들이 있으며, 그 중 간단한 것은 바로 Damping 입니다.

Iteration $k$ 때, 메시지 업데이트를 다음과 같은 형태로 사용합니다.

m_{t \rightarrow s}^k\left(x_s\right)=\lambda m_{t \rightarrow s}\left(x_s\right)+(1-\lambda) m_{t \rightarrow s}^{k-1}\left(x_s\right)

$\lambda = 1$ : Standard Message Update

$\lambda < 1$ : Partial Update from Previous Iteration

이렇게 진행하면 결과가 예시로 다음과 같습니다.

Double Loop 알고리즘도 있다고는 하지만, 느리고 복잡해서 별로라고 합니다.

9.4.4.3 Increasing the Convergence Rate with Adaptive Scheduling

보통은 LBP 를 다음과 같이 한꺼번에 업데이트를 합니다.

\boldsymbol{m}_{1: E}^{k+1}=\left(f_1\left(\boldsymbol{m}^k\right), \ldots, f_E\left(\boldsymbol{m}^k\right)\right)

$f_i(m)$ : Edge $i$ 에 대한 메시지 함수.

그렇다면 이것을 Asynchronous 하게 업데이트를 시키게 된다면 더 빠르게 업데이트를 한다고 합니다.

\boldsymbol{m}_i^{k+1}=f_i\left(\left\{\boldsymbol{m}_j^{k+1}: j<i\right\},\left\{\boldsymbol{m}_j^k: j>i\right\}\right)

그러면 이때 올 수 잇는 질문이 어떤 순서로 메시지를 업데이트를 시키는 것이며, 이는 간단하게 고정적인 순서, 랜덤 순서 등이 있겠지만 가장 Uncertain 한 애들을 업데이트 시켜주는 것입니다.

위의 결과에서 Asynchronous 부분에 이 결과가 있습니다.

9.4.5 Accuracy

Max-Product of LBP 는 Single Loop 그래프에서 정확한 MAP Estimate 을 구하는게 가능하다.

이론적으로 Error 를 Bound 시키는 것이 가능하다.

Gaussian 모델에서는 더 정확한데, 이때 분산은 또 아예 모른다고 한다.

9.4.6 Generalized Belief Propagation

노드들을 Cluster 시켜서 Tight Loop 을 만들어주는게 Cluster Variational Method / Generalized Belief Propagation 이라고 합니다. Cluster 시키면 Hypergraph 가 만들어지며 2개의 Nodes 를 잇는 Edge 가 아닌 2개의 Set of Nodes 를 잇는 Hyper-edges 가 만들어집니다.

9.4.7 Convex BP

보통은 Non-convex 한 BP 를 Convex 한 문제로 바꾸는 것이라고 합니다.

9.4.8 Application: Error Correcting Codes

Error Correcting Codes 는 다른게 아니라 그저 Source Message $\boldsymbol{x} \in \{0, 1\} ^m$ 을 Noisy 한 Channel 으로 보내서 Noisy Measurements $\boldsymbol {y} \in \{ 0, 1 \}^m$ 을 기반으로 $\boldsymbol x^* = \argmax_{\boldsymbol x} p(\boldsymbol x \mid \boldsymbol y) = \argmax_{\boldsymbol x} \tilde p (\boldsymbol x)$ 를 구하는 것이 목표인 것입니다.

이때 $\tilde p ( \boldsymbol x)$ 를 Factor Graph 으로 표현해주는 것이 가능하다고 합니다.

예시를 (2,3) LDPC Code 으로 주었으며, 이는 각각의 Bit (동그라미) 가 2개의 Parity Factor 함수들과 연결되어 있으며, 각각의 Parity Factor (네모) 가 3개의 Bit 와 연결되어 있다고 말합니다.

이때 각각의 Parity Factor 는 다음과 같은 구조를 띈다고 합니다. $(\otimes : \text{XOR Operator})$

\psi_{s t u}\left(x_s, x_t, x_u\right) \triangleq \begin{cases}1 & \text { if } x_s \otimes x_t \otimes x_u=1 \\ 0 & \text { otherwise }\end{cases}

Factor Graph 으로 표현하면 다음 그림과 같이 나오게 됩니다.

이것을 저희가 풀었던 Loopy BP 으로 풀게 된다면 Shannon’s Channel Coding Theorem 의 Lower Bound 에 근접한 결과들이 나오게 됐다고 합니다.

9.4.9 Application: Affinity Propagation

K-medoids Clustering 의 Improvement 이라고 보시면 되며, Pairwise Similarity Matrix 를 Input 으로 받습니다. 목적함수를 다음과 같이 최대화 시키는 것으로 구성합니다.

J(\boldsymbol{c})=\sum_{i=1}^N S\left(i, c_i\right)+\sum_{k=1}^N \delta_k(\boldsymbol{c})

$S(i, c_i)$ : Similarity between 데이터 $i$ and Centroid $c_i$

$\delta_k(\boldsymbol{c})= \begin{cases}-\infty & \text { if } c_k \neq k \text { but } \exists i: c_i=k \\ 0 & \text { otherwise }\end{cases}$
Penalty Term 이며 $k$ 는 본인을 고르지 않았는데 다른 점 $i$ 가 $k$ 를 Centroid 으로 골랐을 경우.

이에 대한 결과는 다음과 같습니다.

9.4.10 Emulating BP with Graph Neural Nets

정말로 제목 이외에 할 얘기가 없어서 넘어가겠습니다.

9.5 The Variable Elimination (VE) Algorithm

여기서부터는 Posterior Marginal $p(\boldsymbol z_Q \mid \boldsymbol y)$ 가 아무 Query Set $Q$ 에 대해서 구해지는게 가능한 알고리즘에 대해서 알려줍니다. Cycle 이 있어도 정확한 답을 구하는게 가능하다고 합니다.

$p$ : Graphical Model

All Hidden Nodes are Discrete

9.5.1 Derivation of the Algorithm

저희가 궁금한게 $p(J=1)$ : Marginal Probability a person will get a Job 이며, 다른 알파벳들은 모두 Binary Variable 들이라고 Assume 하겠습니다.

그러면 모든 변수들에 대해서 고려하면 다음과 같은 Joint 가 나옵니다.

p(J)=\sum_L \sum_S \sum_G \sum_H \sum_I \sum_D \sum_C p(C, D, I, G, S, L, J, H)

근데 이것은 $O(2^7)$ 만큼 걸리기에 Summation 을 Product 안에다가 넣어주면 완화가 됩니다. 이렇게 하는 것 자체가 사실상 Variable Elimination 의 끝입니다.

그러면 문제 상황을 조금 더 다루자면, 다음과 같이 전개가 될 수 있습니다 (Dependencies 고려했을 때)

\begin{aligned}p(J) & =\sum_{L, S, G, H, I, D, C} p(C, D, I, G, S, L, J, H) \\& =\sum_{L, S, G, H, I, D, C} \psi_C(C) \psi_D(D, C) \psi_I(I) \psi_G(G, I, D) \psi_S(S, I) \psi_L(L, G) \\& \times \psi_J(J, L, S) \psi_H(H, G, J) \\& =\sum_{L, S} \psi_J(J, L, S) \sum_G \psi_L(L, G) \sum_H \psi_H(H, G, J) \sum_I \psi_S(S, I) \psi_I(I) \\& \times \sum_D \psi_G(G, I, D) \sum_C \psi_C(C) \psi_D(D, C)\end{aligned}

Variable Elimination 은 그러면 그저 이것들을 하나씩 차근차근 다음과 같이 구하는 것이 끝입니다.

9.5.2 Computation Complexity of VE

당연하게도 지수적으로 가장 큰 Factor 에 따라서 연산이 많아지며, 이에 대해서 완화하기 위해서는 Elimination 순서를 고려해야 됩니다. 예시로 원래 기존 식에서는 $G, I, S$ 셋다 고려하는 Factor 는 없었지만 3번째 식에서 저희는 $G, I, S$ 에 대해서 곱하기에 새로운 Factor 가 만들어진 모습입니다.

Summation 을 어떤 순서로 진행할지가 바로 Elimination Order 입니다.

아래와 같이 다른 순서로 진행하게 된다면 Eliminate 을 하면서 고려하는 Factor 가 훨씬 줄어든 모습을 볼 수가 있습니다.

9.5.3 Picking a Good Elimination Order

결국에는 알고리즘을 통해서 이것도 정해야하며, 이에 대한 예시는 다음과 같습니다.

min-fill heuristic : 그냥 Greedy 하게

min-weight heuristic

AMD (Approximate Minimum Degree ordering algorithm)

이것을 Graph 으로 푸는 것도 가능하며, 노드가 각각의 확률변수, Edge 가 이 두 변수가 같은 Factor 에 있다를 의미합니다. Path 내에서 Fill-in Edges 들이 최소화 되게끔 만들면 성공이라고 보시면 됩니다.

9.5.4 Computation Complexity of Exact Inference

정확한 Inference 는 #P-Hard 말고는 좋은 얘기가 없어서 넘기겠습니다.

9.5.5 Drawbacks of VE

$p(z_T \mid \boldsymbol{y})$ 를 구하려면 $z_1 \sim z_{T-1}$ 의 노드들을 지워가면서 진행해야 됩니다. 하지만 만약에 갑자기 $p(z_{T-1}\mid \boldsymbol y)$ 가 궁금하면 다시 또 VE 를 돌려야하기에 굉장히 비효율적입니다.

Tree 에 적용시켜도 비슷합니다.

9.6 The Junction Tree Algorithm (JTA)

Variable Elimination 에 대한 Generalization 이며 그저 VE 그래프를 Tree 형태로 푸는방식입니다. 이렇게 진행한다면 9.5.5 에서 얘기한 단점들이 완화가 된다고 합니다.