Background

Graphical Model

• 변수들간의 상호 의존 관계를 표현한 확률 모델
• 노드 A,B,C,D 는 변수를 의미
• 엣지는 의존 관계를 의미
• directed, undirected으로 나뉨

Undirected graphical model

A UGM define the joint distribution of a set of variables over the structure of an undirected graph.

Nodes → variable / edges → Conditional independence relationship

• Let $\textbf{y} = [y_1, y_2, \dots , y_N]$ be a vector of $N$ variables whose joint probability distribution is defined over an undirected graph $G$ such that following conditional relationships are true.

Local Markov property

$$ p(y_i|\textbf{y}_{\backslash i}) = p(y_i|N(y_i)) $$

Global Markov property

$$ p(y_i|y_j,y_S) = p(y_i|y_S) $$

Then, the joint distribution of the variables $y_1, y_2, \dots , y_N$can be factorized as

$$ p(\textbf{y}) = \frac{1}{Z} \Pi_{C\in\mathcal{C}(G)} \psi_C (\textbf{y}_C) $$

Hammersly-Clifford theorem

• $\mathcal{C}(G)$ : set of all cliques of $G$
• $\textbf{y}_C$ : vector of all nodes inside clique $C$
• $\psi_C (\textbf{y}_C)$ : arbitrary non-negative functions that define interaction between variables inside $C$ → Potential Functions
• $Z$ : Normalizing constant

<aside> 💡 그래프 $G$와 포텐셜 함수 $\psi_C (\textbf{y}_C)$ 에 따라 $y_1, y_2, \dots , y_N$에 대해 다양한 확률 분포를 모델링할 수 있다.

</aside>

Markov Random Fields

• Energy

$$ \psi_C (\textbf{y}_C|\textbf{w}) = exp(-E_C(\textbf{y}_C|\textbf{w})) \\ E_C(\textbf{y}_C|\textbf{w})=-log(\psi_C (\textbf{y}_C|\textbf{w})) $$

• MRF의 결합 확률 분포