PGM是现代信号处理（尤其是机器学习）的重要内容。
PGM通过图的方式，将多个随机变量之前的关系通过简洁的方式表现出来。因此PGM包括图论和概率论的相关内容。
PGM理论研究并解决三个问题：
1）表示（如何通过图来刻画多个随机变量之间的关系）（注：这个是PGM的基础）
2）学习（如何通过已知数据来确定图的参数） （注：机器学习主要研究这个问题）
3）推断（如果根据已知图，来推断出想要的统计结论） （注：消息传递主要研究这个问题）
表示（Representations）
首先，PGM里面主要使用三种类型的图，
a）贝叶斯网络（Bayesian Network），有向图
b）马尔科夫网络（Markov Network）或者叫马尔科夫随机场（MRF，Markov Random Field），无向图
c）因子图（Factor Graph）
三种图有不同的特点和应用场景。
先定义一些图论中的基本概念：
Graph：A graph $\mathcal{G}=(X,E)$ is a tuple consist of a set of vertices $X$ and a set of edges $E$.
Directed Graph：A graph $\mathcal{R}=(X,E)$ is directed if all edges are directed.
Parent and Child: for a directed graph, $ \mathbf{Pa}(X_j) = \{ X_i \mid (X_i \to X_j) \in \mathbf(E) \} $ $ \mathbf{Ch}(X_i) = \{ X_j \mid (X_i \to X_j) \in \mathbf(E) \} $
Neighbor: for a undirected graph, $ \mathbf{Nb}(X_j) = \{ X_i \mid (X_i - X_j) \in \mathbf(E) \} $
Ancestor and Desendant: $ \mathbf{Anc}(X_j) = \{ X_i \mid \text{ exists a directed path from } X_i \text{ to } X_j \} $
$ \mathbf{Desc}(X_i) = \{ X_j \mid \text{ exists a directed path from } X_i \text{ to } X_j \} $
$ \mathbf{NonDesc}(X_i) = \mathbf{X} - X_i - \mathbf{Desc}(X_i) - \mathbf{Pa}(X_i) $
Bayesian Network (BN)
（注：我们经常遇到的dynamic Bayesian network is a Bayesian network unrolled over time (at each time slice, the BN has the same structure).）
- Definition:
对于随机变量 X,X,...,X，如果联合概率分布可以表示为
$P(X_1,...,X_N) = \prod\limits_{i=1}^N P_{X_i}(X_i \mid \mathbf{Pa} (X_i))$
A Bayesian Network consist of a DAG $\mathcal{G}=(X, E)$ and the conresponding conditional probability distribution $P_{X_i}(X_i \mid \mathbf{Pa} (X_i))$.
- Conditional Indepandence Properties
PGM为啥能简化表达大量随机变量之间的关系，就是因为这些随机变量之间存在一些独立特性，而PGM通过图的形式将这些独立特性表达了出来。
Theorem 1
$ X_i \perp \mathbf{NonDesc}(X_i) \mid \mathbf{Pa}(X_i) \; \forall i, $
Markov Network (MN)
- Definition:
对于随机变量 X,X,...,X，如果联合概率分布可以表示为
$P(X_1,...,X_N) = \frac{1}{Z} \prod\limits_{l=1}^L \Psi_{\mathbf{C}_l}(\mathbf{C}_l)$
则，Markov network由对应的 undirected graph $\mathcal{G}=(X,E)$ 和 一系列最大团的势函数 $\Psi_i: \, \mathbf{val}(C_i) \to \mathbb{R}_{+} $ (nonnegative functions) 表示
条件独立性：
Local Markov property
Pairwise Markov property
Global Markov property
Factor Graph (FG)