本节介绍在完整数据集合下如何来构建概率图的模型。主要分为两个部分，一部分是结构的学习，一部分是参数的学习。

结构学习

基于评分-搜索的结构学习

基于评分-搜索的结构学习主要有两部分组成，就是评分函数和搜索算法。常用的评分函数有BDe评分函数。MDL评分函数和BIC评分函数，搜算法包括启发式局部搜索算法和全局搜索算法。

基于贝叶斯理论

BDe评分函数

基于BDe评分函数的结构学习是以贝叶斯统计学为理论基础的，主要的思想是假设参数分布的条件下计算某一个结构的相对于指定数据集的后验分布，将该分布作为选择结构的依据，找出后验分布最大的结构。
对于全部由离散变量结构构成的贝叶斯网络学习，常常将其转化为一系列的多态抽样过程来学习。一般选用多态分布的共轭分布–Dirichlet分布作为参数$\theta$的先验分布。
假设数据变量为离散值， $B_{G}$表示某一个网络结构，由贝叶斯公式可以获得如下的表示

$$P(B_{G}|D)=\frac{P(D|B_{G})P(B_{G})}{P(D)} \tag{2.1}$$

因为数据集合完整， P(D)可以考虑成常数，$P(B_{G})$是网络结构的先验概率，可以当成常数，所以求解上面的公式的关键点是$P(D|B_{G})$，那么有如下表示

$$P(D|B_{G})=\int_{B_{p}}P(D|B_{G},B_{p})f(B_{p}|B_{G}) dB_{p} \tag{2.2}$$

其中$B_{p}$表示相对于$B_{G}$的条件概率分布向量，f( * ) 表示已知$B_{G}$的条件下$B_{p}$的条件概率分布函数。若数据集合中有m个实例$X_{k}$，那么就将公式2.2变成如下形式

$$P(D|B_{G})=\int_{B_{p}} [ \prod_{k=1}^{m} P(X_{k}|B_{G},B_{p}) ] f(B_{p}|B_{G}) dB_{p} \tag{2.3}$$

这里引入参数$\theta$.

$$P(D|B_{G})= \prod_{i=1}^{n}\prod_{j=1}^{q} \int_{k=1}^{m} \theta_{ijk} f(\theta_{ij1},...,\theta_{ijr_{i}}) d\theta_{ij1}...d\theta_{ijr_{i}} \tag{2.4}$$

公式2.3中$\theta_{ijk}$表示$X_{i}$取第k个值的时候，其父节点取第j个组合的时候的概率。这里假设$f(\theta_{ij1},...,\theta_{ijr_{i}})$服从Dirichlet分布，就得到的BDe评分公式的计算方法啦。

$$P(D|B_{G})=\prod_{i=1}^{n} \prod_{j=1}^{q} \frac{\Gamma(a_{ij}')}{\Gamma(a_{ij}'+a_{ij})}\prod_{k=1}^{r_{i}} \frac{\Gamma(a_{ijk}'+a_{ijk})}{\Gamma(a_{ijk}')} \tag{2.5}$$

其中$a_{ij}'=\sum_{k=1}^{r_{i}} a_{ijk}', a_{ij}=\sum_{k=1}^{r_{i}}a_{ijk}$, $\Gamma$表示伽马函数。 伽马函数的几个性质是比较重要的。

1. Γ(n) = (n-1)!
2. Γ(z+1) = z * Γ(z)
   其表达式为

$$\Gamma(n)=\int t^{n-1}e^{-t}dt$$

介绍完伽马函数咱们来你看看几个超参数，$a_{ijk}'$的估计是非线性的，计算起来比较复杂，一般直接设置成1.

基于信息论

MDL评分函数

MDL是最小化编码长度的一种算法，假如给定数据D，如果要对其保存，这么能够尽可能的压缩空间，并且以后能够恢复原始的数据。这就是MDL最开始的使用场景，MDL原理就是要选择总描述长度最小的模型。数据完备的情况下，总的描述长度为

$$DL(G,D)=\sum_{i=1}^{n} |Pa_{i}| \log_{2}^{(n)}+\frac{1}{2} \sum_{i=1}^{n} |Pa_{i}| (|X_{i}|-1) \log(M)+M\sum_{i=1}^{n}H(X_{i}|Pa_{i}) \tag{3.1}$$

其中$H(X_{i}|Pa_{i})$为$X_{i}$对于$Pa_{i}$的条件熵。
MDL的思想是最小化DL(G,D)，可以反过来看如下的表达式

$$-DL(G,D)=-M \sum_{i=1}^{n} H(X_{i}|Pa_{i}) -\frac{1}{2} \sum_{i=1}^{n} |Pa_{i}| (|X_{i}-1|)log M \tag{3.2}$$

其中M为数据集长度。MDL计算过程中没有用到参数的先验值，不需要参数估计，计算也比较简单。

BIC评分函数

BIC评分实质上是对BDe评分的近似计算。一般使用BDe评分函数的时候不会真的计算$P(B_{G|D})$，而是求它的对数$log P(B_{G|D})$，所以BIC评分函数表达如下

$$log P(B_{G}|D)=log P(D|\theta_{G}, B_{G})-\frac{d}{2}logM \tag{4.1}$$

其中d为高斯分布函数的维度，就是变量个数，对于贝叶斯网络来说，$d=\sum_{i=1}^{n} |Pa_{i}|(|X_{i}|-1)$, M为数据集合数目，$\theta_{G}$为$P(\theta_{G}|D,B_{G})$后验分布最大的时候的参数值。

MIT评分

MIT评分的公式如下：

$$S_{MIT}(G,D)=\sum_{i=1, pa(V_{i}) \in NULL}^{n}[2N · MI(V_{i},pa(V_{i}))-\sum_{j=1}^{pa(V_{i})} \phi_{\alpha,l_{i,j}}] \tag{4.2}$$

其中MI表示互信息计算，pa表示父节点， $\phi_{\alpha,l_{i,j}}$表示变量$V_{i}$和它的一个父节点变量之间互信息的阈值。如果低于这个阈值就认为是独立的。
MIT比K2，BIC和BDeu分数有更好的结构精度和数据拟合，MIT分数是可分解单不等价的性质。

总结一下

这一个章节咱们介绍了一些常用的评分函数，在接下来的内容里会提到搜索算法，从而完成模型结构的学习。 与贝叶斯函数相比，信息打分函数是客观且无先验参数的，避免敏感性问题，因此当用户对目标网络的背景知识了解较少的时候，信息论评分函数是一个首选。

注解

这里解释一下什么叫做条件分布函数。若P(Y=y)>0,那么Y=y的时候，X的条件概率函数如下

$$F(x|y)=P(X<x |Y=y)=\frac{P(X<x,Y=y)}{P(Y=y)}$$