Undirected Graphical Models

Definition

$E_\theta : \Omega \to \mathbb{R}$ is an energy function, and

$$P_\theta(x) \propto e^{-E_\theta(x)}$$

Scaling $E_\theta$ controls sharpness, $P_\theta(x) \propto e^{-\beta E_\theta(x)}$ with $\beta = 1/T$. In terms of potentials, $-E_\theta(x) = \langle \theta, \phi(x) \rangle$, where each $\phi$ is a function of some of the random variables.

Example For $x \in \{-1, 1\}^n$,

$$P(x) \propto e^{\langle h, x \rangle + \frac{1}{2}\langle x, Ax \rangle} = \exp\Big(\sum_{i=1}^{n} h_i x_i + \frac{1}{2}\sum_{i,j=1}^{n} A_{ij} x_i x_j\Big)$$

with $A$ symmetric. If $A_{ij} = 0$ there is no direct relation between $x_i$ and $x_j$. Not easy to sample, but the conditionals are simple. Only the terms with $x_i$ survive in

$$P(x_i = 1 | x_{-i}) = \frac{P(x_i = 1, x_{-i})}{P(x_i = 1, x_{-i}) + P(x_i = -1, x_{-i})} = \frac{e^{a_i}}{e^{a_i} + e^{-a_i}}, \qquad a_i = h_i + \sum_{j \neq i} A_{ij} x_j$$

which only depends on the neighbours of $i$. So $X_i \perp X_{(\{i\} \cup N(i))^c} \mid X_{N(i)}$.

Factorization

With $\mathcal{C}$ the maximal cliques of $G$, $P$ factorizes with respect to $G$ if

$$P(x) \propto e^{-E(x)}, \qquad -E(x) = \sum_{c \in \mathcal{C}} \phi_c(x_c), \qquad P(x) \propto \prod_{c \in \mathcal{C}} \psi_c(x_c), \quad \psi_c = e^{\phi_c(x_c)}$$

Independences

• Global Markov For all $A, B, C$ such that $C$ separates $A$ and $B$, $X_A \perp X_B \mid X_C$.
• Local Markov $X_v \perp X_{(\{v\} \cup N_v)^c} \mid X_{N_v}$.
• Pairwise Markov For nonadjacent $v, w$, $X_v \perp X_w \mid X_{\{v, w\}^c}$.

Belief Propagation

For $P(x) \propto \prod_i \phi_i(x_i) \prod_{(i,j) \in E} \phi_{ij}(x_i, x_j)$, the message from $X_k$ to its neighbour $X_m$ is

$$\phi_{X_m}^{X_k \to X_m}(x_m) = \sum_{x_k} \phi_{X_k}(x_k)\, \phi_{X_k, X_m}(x_k, x_m) \prod_{X_i \in N(X_k) \setminus \{X_m\}} \phi_{X_k}^{X_i \to X_k}(x_k)$$