# 📏论文中的数学

# 概率图模型

图片截取自机器学习-白板推导系列 (opens new window)，感谢shuhuai008 (opens new window)大佬。

# 概率图模型基础-背景介绍

背景知识

其中，条件概率 $p(b|a)$ 表示随机事件 $a$ 发生的条件下， $b$ 发生的概率，公式为 $p(b|a) = \frac{p(b,a)}{p(a)}$ 。其实条件概率还是可以按照“频数/总数”的方式进行理解，分母部分 $p(b,a)$ 表示事件发生频数部分，即 $a,b$ 同时发生的概率，总数部分是 $a$ ，即 $a$ 发生的所有情况，合起来就是所有 $a$ 发生的情况下， $a,b$ 同时发生的概率，就是 $p(b|a)$ 。

类似的，公式 $p(a,b) = p(a) \cdot p(b|a)$ 可以用乘法原理进行理解，即将 $p(a,b)$ 理解为两个事件，事件1是a发生，事件2是a发生时b发生，合起来就是a和b同时发生。当然，从事件b的角度看也是一样的，事件1
是b发生，事件2是b发生时a发生，即 $p(a,b) = p(b) \cdot p(a|b)$ 。

# 贝叶斯网络-条件独立性

上图为本次推导的基础。

tail-to-tail结构

这是第一种结构，叫做“tail-to-tail”，上图中，如果a被观测，则b和c被阻隔，a没被观测时，b和c只是在条件a中独立，一旦a被观测，则b和c独立。

其中， $p(c|a,b) \cdot p(b|a)$ 的推导来源于多变量贝叶斯公式，对于两变量，贝叶斯公式为 $p(a|b)=\frac{p(a,b)}{p(b)}$ ，在三变量中，例如对于 $p(c|a,b)$ ，将 $a,b$ 看成一个整体 $\Delta$ ，那么同样有 $p(c|a,b) = p(c|\Delta)=\frac{p(c,\Delta)}{p(\Delta)}= \frac{p(c,a,b)}{p(a,b)}$ ，即 $p(c|a,b) = \frac{p(c,a,b)}{p(a,b)}$ ，将此带入上式，有：

$\begin{aligned} p(c|a,b) \cdot p(b|a) & = \frac{p(c,a,b)}{p(a,b)} \cdot \frac{p(b,a)}{p(a)} \\ & = \frac{p(c,a,b)}{p(a)} \\ & = p(c,b|a) \end{aligned}$

head-to-tail结构

这是第二种结构，叫做head-to-tail结构。

head-to-head结构

这是第三种结构“head-to-head”，这个结构比较特殊，默认情况下a和b是独立的，但是 $c$ 被观测之后，路径相通， $a,b$ 相互之间就不独立了。

# 贝叶斯网络

上图是背景知识，也是第二节推导出的部分。

上图解释了为什么“head-to-head”结构中，当c观测之后，a和b不是条件独立的。即判断等式 $p(a|c) = p(a|c,b)$ 是不是相等？如果相等，则代表c发生的条件下a发生的概率，等于c和b同时发生时a发生的概率，即b发不发生对于c发生的条件下a发生没影响，那么b,c条件独立。

简要解释：由于a（酒量小）和b（心情不好）都是小明喝醉了的原因，因此当知道小明喝醉了这个结果以及其中一个原因“酒量小” $p(a|c)$ ，肯定会影响对“小明是不是心情不好”这个原因的判断。

# 贝叶斯网络概述

从单一到混合，从有限到无限，分为空间和时间两个方面。空间是指随机变量取值可以从离散到连续。

常用单一模型：朴素贝叶斯，其中 $X$ 中每个分量 $x_i$ 都是独立的，如下图所示。

Naive Bayes

混合模型常用的高斯混合模型（GMM）

GMM

时间上相关的模型有：马尔科夫链和高斯过程。

连续模型：主要用高斯贝叶斯网络。

混合模型和时间维度结合起来就是动态系统（动态模型），这是一个大的体系，最常见的有HMM（隐马尔科夫模型，隐状态是离散的、卡尔曼滤波（连续高斯，线性）、粒子滤波（非连续高斯、非线性）

总结如下：

# 马尔科夫随机场

背景知识如下：

背景知识

团的推导：

完整总结，团的部分之前没介绍过，所以有点晕。

# 概率图模型推断（Inference）

推断就是“求概率”，一是求边缘概率，可能是已知联合概率，求某个变量的边缘概率。二是求条件概率，已知一部分求另一部分。三是求最大后验，期望后验概率达到最大。

精确推断和近似推断，精确推断用变量消除法（VE）、信念传播算法（BP，脱胎于VE，克服了VE的一些缺点，很重要，一般针对树结构）、联合树算法（针对图结构）。

近似推断：采用BP思想，处理有环图结构，称为Loop Belief Propagation；基于采样的蒙特卡洛推断方法，常用的有Importance Sampling和MCMC；确定性近似。

以隐马尔科夫模型为例，进行举例。

本节总结：

# 变量消除法

背景条件：

以马尔科夫链为例，讲解变量消除法，已知前 $a,b,c$ 三个变量的情况，求边缘概率 $p(d)$ 。很显然，他是 $p(a,b,c,d)$ 的边缘概率，就是对除了 $d$ 以外的其他变量求和，然后采用因子分解

为什么 $p(d) = \sum\limits_{a,b,c}{p(a,b,c,d)}$ ？首先需要注意的是，边缘概率 $p(d)$ 也是一个函数，一个关于 $d$ 的函数，即当 $d=1, d=2$ 时概率应该是多少的函数。 $p(d)$ 是求边缘概率，即在其他各种情况下变量 $d$ 的概率值。那么其他各种情况是指谁呢，那就是除了变量 $d$ 以外的所有变量，即 $a,b,c$ 。求值中，对于 $\sum\limits_{a,b,c}{p(a,b,c,d)}$ ，每一次 $a,b,c$ 取定一个值，都会得到一个关于 $d$ 的函数 $p(a,b,c,d)$ ，将它求和即可。例如 $a,b,c,d$ 都是只能选0或1的二值变量，那么p(d)=p(0,0,0,d)+p(1,0,0,d)+\dots+p(1,1,1,d)。

如果“硬上”，那么对于最简单的0-1二值，3个变量，也需要加 $2^3=8$ 次，如上图所示，而且随着维度 $p$ 增加，需要加的次数 $K^p$ 呈指数增长。那么采用最简单的变量消除思想，将每一个需要加的变量分离，例如先只考虑 $a$ 变量，除非是所有变量全连接，否则他只跟他相连接的变量有值，其他都是0。