0 写在前面

机器学习强基计划聚焦深度和广度，加深对机器学习模型的理解与应用。“深”在详细推导算法模型背后的数学原理；“广”在分析多个机器学习模型：决策树、支持向量机、贝叶斯与马尔科夫决策、强化学习等。强基计划实现从理论到实践的全面覆盖，由本人亲自从底层编写、测试与文章配套的各个经典算法，不依赖于现有库，可以大大加深对算法的理解。

🚀详情：机器学习强基计划(附几十种经典模型源码)

1 从一个例子出发

从一个实例出发介绍变量消除法的动机。考虑经过概率图建模的联合分布

$$P\left(A,B,C,D\right)=P\left(A\right)P\left(B|A\right)P\left(C|B\right)P\left(D|C\right)$$

假设其中均为二值随机变量。若要求边缘分布$P\left(D\right)$，最朴素地方法是对所有条件概率求和，如下所示

值得注意的是，很多因子存在重复计算的现象，例如$P\left(a\right)P\left(b|a\right)$的结构重复计算了4次，若对这些公共结构计算一次后存储，并作为已知量与其他因子完成后续运算，计算将得到大幅节省。将计算过程修正为

定义公共结构的计算结果为消息(message)$m_{\mathbf{X}}\left({\mathbf{X}}^{\ast }\right)$，其中$\mathbf{X}$是公共结构涉及的变量，${\mathbf{X}}^{\ast }$是公共结构运算后剩下的变量。类似地，可以进一步计算新的公共结构

最终计算得到$P\left(D\right)$。直观地，若不存储公共结构，需要计算4×8×2=64次乘法与8×2=16次加法；存储公共结构后只需计算6×2=12次乘法与3×2=6次加法，性能得到明显改善。

2 变量消除法

形式化地，上面的推断过程抽象为

$${\varphi }^{\ast }\left(\mathbf{X}\right)=\sum _{\mathbf{Z}}\prod _{\varphi \in \Phi }\varphi$$

其中待消去变量集合为$\mathbf{Z}$，查询变量集合为$\mathbf{X}$，其并集为全体概率空间$\mathbf{X}\cup \mathbf{Z}=\mathcal{X}$。

根据因子乘法、加法的交换律、结合律(这部分内容请看机器学习强基计划5-3：图文详解因子分解与独立图I-Map(附例题分析+Python实验)，上式的核心是每次对一个随机变量求和：将所有与该变量有关的因子相乘产生乘积因子，并在乘积因子中对该变量边缘化求和，产生可以纳入到待处理因子集中的一个新因子。这个过程也称为和-积变量消除(Sum-Product Variable Elimination, VE)

应用式(4.1)，上面例子的计算式为

$$P\left(D\right)={\sum }_C^{}P\left(D|C\right){\sum }_B^{}P\left(C|B\right){\sum }_A^{}P\left(A\right)P\left(B|A\right)$$

3 动态规划求VE

在计算机执行时采用动态规划，从最内层往外层计算，使内层因子只计算一次。变量消除法的算法流程如表所示

4 Python实验

4.1 建立贝叶斯网络

再次考虑机器学习强基计划5-2：用一个例子通俗理解贝叶斯网络(附例题)的例子

首先建立这个贝叶斯网络

from pgmpy.inference import VariableElimination
from pgmpy.models import BayesianNetwork
from pgmpy.factors.discrete.CPD import TabularCPD

model = BayesianNetwork([('Difficulty', 'Grades'), ('Intelligence', 'Grades'), ('Intelligence', 'SAT'), ('Grades', 'Letter')])

diff_cpd = TabularCPD('Difficulty', 2, [[0.6], [0.4]])
intel_cpd = TabularCPD('Intelligence', 2, [[0.7], [0.3]])
grade_cpd = TabularCPD('Grades', 3, [[0.3, 0.05, 0.9, 0.5],
                                     [0.4, 0.25, 0.08, 0.3],
                                     [0.3, 0.7, 0.02, 0.2]],
                        evidence=['Intelligence', 'Difficulty'], evidence_card=[2, 2])
sat_cpd = TabularCPD('SAT', 2, [[0.95, 0.2], 
                                [0.05, 0.8]],
                     evidence=['Intelligence'], evidence_card=[2])
letter_cpd = TabularCPD('Letter', 2, [[0.1, 0.4, 0.99], 
                                      [0.9, 0.6, 0.01]], 
                        evidence=['Grades'], evidence_card=[3])

model.add_cpds(diff_cpd, intel_cpd, grade_cpd, sat_cpd, letter_cpd)

输出的结果和例子中的条件概率表相同

+---------------+-----+
| Difficulty(0) | 0.6 |
+---------------+-----+
| Difficulty(1) | 0.4 |
+---------------+-----+

+-----------------+-----+
| Intelligence(0) | 0.7 |
+-----------------+-----+
| Intelligence(1) | 0.3 |
+-----------------+-----+

+--------------+-----------------+-----------------+-----------------+-----------------+
| Intelligence | Intelligence(0) | Intelligence(0) | Intelligence(1) | Intelligence(1) |
+--------------+-----------------+-----------------+-----------------+-----------------+
| Difficulty   | Difficulty(0)   | Difficulty(1)   | Difficulty(0)   | Difficulty(1)   |
+--------------+-----------------+-----------------+-----------------+-----------------+
| Grades(0)    | 0.3             | 0.05            | 0.9             | 0.5             |
+--------------+-----------------+-----------------+-----------------+-----------------+
| Grades(1)    | 0.4             | 0.25            | 0.08            | 0.3             |
+--------------+-----------------+-----------------+-----------------+-----------------+
| Grades(2)    | 0.3             | 0.7             | 0.02            | 0.2             |
+--------------+-----------------+-----------------+-----------------+-----------------+

+--------------+-----------------+-----------------+
| Intelligence | Intelligence(0) | Intelligence(1) |
+--------------+-----------------+-----------------+
| SAT(0)       | 0.95            | 0.2             |
+--------------+-----------------+-----------------+
| SAT(1)       | 0.05            | 0.8             |
+--------------+-----------------+-----------------+

+-----------+-----------+-----------+-----------+
| Grades    | Grades(0) | Grades(1) | Grades(2) |
+-----------+-----------+-----------+-----------+
| Letter(0) | 0.1       | 0.4       | 0.99      |
+-----------+-----------+-----------+-----------+
| Letter(1) | 0.9       | 0.6       | 0.01      |
+-----------+-----------+-----------+-----------+

4.2 测试VE算法

下面开始对比VE算法和理论计算的结果。

1. 在对该生其他信息一无所知的前提下，获得好的推荐信的概率

$$P\left(l^1\right)=\sum _{g}P\left(l^1|g\right)P\left(g\right)=\sum _{g}P\left(l^1|g\right)\sum _{i,d}P\left(g|i,d\right)P\left(i\right)P\left(d\right)\approx 50.2\%$$

用VE算法计算的结果

inference = VariableElimination(model)
phi_query = inference.query(['Letter'])

+-----------+---------------+                                                                                                | 0/3 [00:00<?, ?it/s] 
| Letter    |   phi(Letter) |
+===========+===============+
| Letter(0) |        0.4977 |
+-----------+---------------+
| Letter(1) |        0.5023 |
+-----------+---------------+

2. 进一步得知课程比较简单，那么成绩$G$可能得到提升，从而影响其推荐信的质量

$$P\left(l^1|i^0,d^0\right)=\sum _{g}P\left(l^1|g\right)P\left(g|i^0,d^0\right)\approx 51.3\%$$

inference = VariableElimination(model)
phi_query = inference.query(['Letter'], evidence={'Intelligence': 0, 'Difficulty': 0})

+-----------+---------------+
| Letter    |   phi(Letter) |
+===========+===============+
| Letter(0) |        0.4870 |
+-----------+---------------+
| Letter(1) |        0.5130 |
+-----------+---------------+

🔥 更多精彩专栏：

• 《ROS从入门到精通》
• 《机器人原理与技术》
• 《机器学习强基计划》
• 《计算机视觉教程》
• …