7-概率图 | Zangwei

图模型

$B=\langle G,\Theta\rangle$
- $G$: 有向无环图 (DAG)
- $\Theta$: 条件概率表 (CPT)
  - $\theta_{x_i|\pi_i}=P_B(x_i|\pi_i)$
联合分布：$P(x_1,\cdots,x_n)=\prod_{i=1}^nP(x_i|\text{Parent}(x_i))$

三变量间的典型依赖关系
- 同父结构: $x_3\perp x_4|x_1$
- 顺序结构：$y\perp z|x$
- 冲撞结构(V-structure): $x$⫫$y|z$
  - marginal independece: $z$ 完全未知则独立，给定 $z$ 则不独立
有向分离 (D-seperation，或道德化)
- 转化为无向图 (moral graph)
  - 有向边改无向边
  - V 型结构两个父节点之间加边
- $x$ 与 $y$ 有向分离：$\exists Z$, $x,y$ 在 $G\backslash Z$ 中分属两个连通分支则 $x\perp y|Z$
马尔科夫覆盖

马尔科夫网：
- $V$: 随机变量
- $E$: 变量间的依赖关系
- $x_{{k}}$: 第$k$个团随机变量
无向图为马尔科夫网络 $\iff$ 满足以下三条性质之一
- Pairwise Markov Property: $X_u\perp X_v|X_{V\backslash{u,v}},{u,v}\not\in E$
- Local Markov Property: $X_v\perp X_{V\backslash\text{ne}(v)}|X_{\text{ne}(v)}$
  - $\text{ne}(v)$: 邻居，马尔科夫毯
- Global Markov Property: $X_A \perp X_B|X_S$，$A,B$ 两个子集间任何一条路径都经过子集$S$，则给定 $S$ 后，$A,B$ 两个子集相互条件独立
构造
- 如果满足 $P\not\vDash(X\perp Y|V-{X,Y})$，则 $X,Y$ 加边
- 给定 $X$ 的马尔可夫毯，$X$ 独立于余下的变量
Hammersley-Clifford 定理：$p(x)>0$ 满足局部马尔科夫性质当且仅当可表为马尔科夫网上的吉布斯分布
- 吉布斯分布：$p(x)=\frac{1}{Z}\prod_{c\in\mathcal{C}}\phi_c(x_c)$
- 势函数：$\phi_k(x_{{k}})$
- 配分函数：$Z=\sum_{x\in \mathcal{X}}\prod_{c\in\mathcal{C}}\phi_c(x_c)$
- 势函数：$f_k(x_{{k}})=e^{\omega_k^T\phi_k(x_{{k}})}$
一般定义为玻尔兹曼分布
- $\phi_c(x_c)=\exp(-E_c(x_c))$

对数线性模型（最大熵模型）
- $\phi_c(x_c|\phi_c)=\exp(\theta_c^Tf_c(x_c))$
- $\log p(x;\theta)=\sum_{c\in\mathcal{C}}\theta_c^Tf_c(x_c)-\log Z(\theta)$
- 条件最大熵模型（Softmax 回归模型）：$p(y|x;\theta)=\frac{\exp(\theta^Tf(x,y))}{\sum_{y}\exp(\theta^Tf_y(x,y))}$
条件随机场（CRF）：$p(y|x;\theta)=\frac{1}{Z(x;\theta)}\exp(\sum_{c\in\mathcal{C}}\theta_c^Tf_c(x,y_c))$
- 线性链条件随机场
马尔科夫逻辑网 (MLN) = Markov Net + 一阶逻辑
- 判断一个知识库中是否包含公式 $F$，$F$ 在所有满足知识库的世界中恒真
  - 公式附加权值的一阶逻辑知识库
  - 基本思想：将一阶逻辑的限制放松，即一个可能世界违反公式越多，其发生的概率越小
- $L$：${(F_i,w_i)}$
  - $F_i$: 一阶逻辑闭规则（无变元）
  - $w_i$: 实数表示权重
  - $C$: 有限常数集
- 马尔科夫逻辑网 $M_{L,C}$
  - $L$ 中的任意闭原子对应一个二值结点，真为 $1$，假为 $0$
  - $L$ 任意闭规则对应一个特征值，若规则为真，特征值为 $1$ 否则为 $0$。权重为 $\omega_i$
  - $P(X=x)=\frac{1}{Z}\text{exp}(\sum_{i=1}^F\omega_in_i(x))$
    - $n_i$: $F_i$ 在 $X$ 中所有取真值的公式的数量

有向图：$L(D,\theta)=\frac{1}{N}\sum_{n=1}^N\sum_{k=1}^K\log p(x_k^{(n)}|x_{\pi_k}^{(n)};\theta_k)$
无向图：$L(D,\theta)=\frac{1}{N}\sum_{n=1}^N\log p(\sum_{c\in\mathbb{C}}\theta_c^Tf_c(x_c^{(n)}))-\log Z(\theta)=E_{x\sim\tilde p(x)}f_c(x_c)-E_{x\sim p(x;\theta)}f_c(x_c)=\frac{1}{N}\sum_{n=1}^Nf_c(x_c^{(n)})-\sum_xp(x;\theta)f_c(x_c)$
- 采样近似第二个期望
- 坐标上升法：固定其它参数，优化一个参数

变分推断（变分贝叶斯）：寻找简单分布 $q^*(z)$ 近似条件概率密度 $p(z|x)$
泛函优化问题：$q^*(z)=\argmin_{q(z)\in Q}\text{KL}(q(z)|p(z|x))=\arg\max_{q(z)\in Q}\text{ELBO}(q,x)$
候选分布族 $Q$
- 平均场分布族：$q(z)=\prod_{m=1}^Mq_m(z_m),z_m\subseteq Z$
- 神经网络拟合 $p(z|x)$
$\text{ELBO}(q,x)=\int \prod_{m=1}^Mq_m(z_m)(\log p(x,z)-\sum_{m=1}^M\log q_m(z_m))dz=\int q_j(\int\prod_{m\neq j}q_m\log p(x,z)dz_m)dz_j-\int q_j\log q_j dz_j+C$
- $\text{ELBO}(q,x)=\int q_j\log \tilde p(x,z_j)dz_j-\int q_j\log q_j dz_j+C$
- $\log \tilde p(x,z_j)=E_{q(z_{\backslash j})}\log p(x,z) + C$ 关于 $z_j$ 未归一化分布
- 最优化 $q_j^*(z_j)=\tilde p(x,z_j)$
坐标上升法：迭代优化 $q_j^*(z_j),j=1,\cdots,M$，使其收敛到局部最优解

随机采样：cdf 递增，则在 cdf 逆函数上进行均匀采样
拒绝采样
- 未归一化分布 $\hat p(x)$
- 采样样本 $\hat x$
- 提议分布（参考分布） $q(x),\exists k,\forall x,kq(x)\geq \hat p(x)$
- 接受概率：$\alpha(\hat x)=\frac{\hat p(\hat x)}{kq(\hat x)}$
重要性采样：从参考分布中采样
- $E_p[f(x)]=\int_x f(x)p(x)dx=E_q(f(x)\omega(x)]$
- 重要性权重：$\omega(x)=\frac{p(x)}{q(x)}$
- 未归一：$E_p(f(x))=\frac{\int_x\hat p(x)f(x)dx}{\int_x\hat p(x)dx}\approx\frac{\sum_{n=1}^Nf(x^{(n)}\hat\omega(x^{(n)}))}{\sum_{n=1}^N\hat\omega(x^{(n)})}$
拒绝采样和重要性采样的效率随空间维数的增加而指数降低
MCMC 方法采样
- 预烧期（Burn-in Period）
- 相邻样本高度相关：每间隔 $M$ 次随机游走取一个样本
Metropolis-Hastings 算法
- 根据 $q(x|x_t)$ 采样 $\hat x$
- 以如下概率接受：$A(\hat x,x_t)=\min(1,\frac{p(\hat x)q(x_t|\hat x)}{p(x_t)q(\hat x|x_t)})$
Metropolis 算法：MH 算法中提议分布对称
- $A(\hat x,x_t)=\min(1,\frac{p(\hat x)}{p(x_t)})$
Gibbs Sampling：使用全条件概率作为提议分布，$A=1$
- $p(x_m|x_{\backslash m})=p(x_n|x_1,\cdots,x_{m-1},x_{m+1},\cdots,x_M)$
- 按下标顺次采样