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)

05-19 19:04