Undirected Graphical Model

Markov random field Markov network

remember the conditional independence

preference, affinity

comparison of DGM and UGM

no DGM can represent the conditional independencies encoded by this UGM

no UGM can represent the marginal independencies encoded by this DGM

Hammersley-Clifford theorem

A positive distribution $p(y) > 0$ satisfies the CI properties of an undirected graph $G$ iff $p$ can be represented as a product of factors, one per maximal clique.

$$p(y | \theta) = \frac{1}{Z(\theta)} \prod_{c \in \mathscr{C}} \phi_c (y_c | \theta_c)$$

where $\mathscr{C}$ is the set of all the maximal cliques of $G$, and $Z(\theta)$ is the partition function given by $Z(\theta) = \sum_{x} \prod_{c \in \mathscr{C}} \phi_c (y_c | \theta_c)$

Boltzmann distribution, Gibbs distribution

$p(y | \theta) = \frac{1}{Z(\theta)} \exp(- \sum_c E(y_c | \theta_c))$

where $E(y_c) > 0$, energy associated with the variables in clique $c$.

energy based models.

• maxmimum entropy models
• log-linear models

HMM vs MEMM vs CRF

inference vs learning

learning of maxent models

$p(y | \theta) = \frac{1}{Z(\theta)} \exp(\sum_c \theta_c^T \phi_c(y))$$

\begin{align} l(\theta) &= \frac{1}{N} \sum_i \log p(y_i | \theta) \\ &= \frac{1}{N} \sum_i [\sum_c \theta_c^T \phi_c (y_i) - \log Z(\theta)] \end{align}

$$\frac{\partial l}{\partial \theta_c} = \frac{1}{N} \sum_i [\phi_c (y_i) - \frac{\partial}{\partial \theta_c} \log Z(\theta)]$$

$$\frac{\partial \log Z(\theta)}{\partial \theta_c} = E[\phi_c(y) | \theta] = \sum_y \phi_c(y) p(y | \theta)$$

$$\frac{\partial l}{\partial \theta_c} = [\frac{1}{N} \sum_i \phi_c (y_i)] - E[\phi_c (y)] = E_{p_{emp}}[\phi_c(y)] - E_{p(\cdot | \theta)}[\phi_c (y)]$$

moment matching

$p(y_i | y_{i-1})$, $p(x_i|y_i)$

$p(x, y) = \prod_i p(y_i | y_{i - 1}) p(x_i | y_i)$

$p(x_i | y_i) = ?$

if we observe hidden state sequences, easy. if unobservable, perform EM.

loaded die vs fair die? or how about coins?

generative

$p(x, y | \theta) = \prod p(y_i | y_{i - 1}, \theta) p(x_i | y_i, \theta)$

$p(y|x, \theta) = \prod p(y_i | y_{i - 1}, x, \theta)$

label bias problem

$p(y|x, \theta) = \frac{1}{Z(x, \theta)} \prod \psi(y_i | x, \theta) \cdot \phi(y_{i-1}, y_i|x, \theta)$

HMM