Question

1. 贝叶斯网络Bayesian network借助于有向无环图来刻画特征之间的依赖关系，并使用条件概率表Conditional Probability Table:CPT来描述特征的联合概率分布。

   这里每个特征代表一个随机变量，特征的具体取值就是随机变量的采样值。

2.1 条件独立性

1. 一个贝叶斯网 $ MathJax-Element-150 $ 由结构 $ MathJax-Element-279 $ 和参数 $ MathJax-Element-120 $ 两部分组成，即 $ MathJax-Element-138 $ ：

   • 网络结构 $ MathJax-Element-279 $ 是一个有向无环图，其中每个结点对应于一个特征。

     若两个特征之间有直接依赖关系，则他们用一条边相连。

   • 参数 $ MathJax-Element-120 $ 定量描述特征间的这种依赖关系。设特征 $ MathJax-Element-302 $ 在 $ MathJax-Element-279 $ 中父节点的集合为 $ MathJax-Element-119 $ ， 则 $ MathJax-Element-120 $ 包含了该特征的条件概率表：

   $ \theta_{X_i\mid \Psi_{X_i}}=P(X_i\mid \Psi_{X_i}) $

2. 贝叶斯网结构有效地表达了特征间的条件独立性。

   给定父节点集，贝叶斯网络假设每个特征与它的非后裔结点表达的特征是相互独立的。于是有：

   $ P(\mathbb X)=P(X_1,X_2,\cdots,X_n)=\prod_{i=1}^{n}P(X_i\mid \Psi_{X_i})=\prod_{i=1}^{n}\theta_{X_i\mid \Psi_{X_i}} $

   推导过程：

   $ P(\mathbb X)=P(X_1,X_2,\cdots,X_n)=P(X_1\mid X_2,\cdots,X_n)P(X_2,\cdots,X_n)\\ =P(X_1\mid \Psi_{X_1})P(X_2,\cdots,X_n)\\ =P(X_1\mid \Psi_{X_1})P(X_2\mid X_3,\cdots,X_n)P(X_3,\cdots,X_n)\\ =P(X_1\mid \Psi_{X_1})P(X_2\mid \Psi_{X_2})P(X_3,\cdots,X_n)=\cdots $

3. 贝叶斯网络中三个结点之间典型依赖关系如下图：

   

   • 同父结构：给定父节点 $ MathJax-Element-159 $ 的取值， 则 $ MathJax-Element-160 $ 与 $ MathJax-Element-135 $ 条件独立，即：
     
   $ P(X_2,X_3\mid X_1)=P(X_2\mid X_1)P(X_3\mid X_1) $

   • 顺序结构：给定中间节点 $ MathJax-Element-159 $ 的取值， 则 $ MathJax-Element-160 $ 与 $ MathJax-Element-135 $ 条件独立，即：
     

     $ P(X_2,X_3\mid X_1)=P(X_2\mid X_1)P(X_3\mid X_1) $

     即：在 $ MathJax-Element-159 $ 给定的条件下， $ MathJax-Element-128 $ 之间被阻断。因此它们关于 $ MathJax-Element-159 $ 条件独立。

   • V 型结构：给定子节点 $ MathJax-Element-159 $ 的取值，则 $ MathJax-Element-160 $ 与 $ MathJax-Element-135 $ 必定不是条件独立的。即： $ MathJax-Element-133 $ 。

     事实上 $ MathJax-Element-160 $ 与 $ MathJax-Element-135 $ 是独立的（但不是条件独立的），即 $ MathJax-Element-136 $ 。

4. 为了分析有向图中节点之间的条件独立性，可以使用有向分离技术：

   • 找出有向图中的所有V型结构，在V型结构的两个父节点之间加上一条无向边。
   • 将所有的有向边改成无向边。

   这样产生的无向图称作道德图moral graph。父节点相连的过程称作道德化moralization。基于道德图能直观、迅速的找到结点之间的条件独立性。

2.2 网络的学习

1. 贝叶斯网络的学习可以分为参数学习和结构学习两部分

   • 参数学习比较简单。只需要通过对训练样本“计数”，估计出每个结点的条件概率表即可。

     但是前提是必须知道网络结构。

   • 结构学习比较复杂，结构学习被证明是NP难问题。

2. 贝叶斯网络的结构学习通常采用评分搜索 来求解。

   • 先定义一个评分函数，以此评估贝叶斯网络与训练数据的契合程度。然后基于这个评分函数寻找结构最优的贝叶斯网。

   • 最常用的评分函数基于信息论准则：将结构学习问题视作一个数据压缩任务。

     • 学习的目标是找到一个能以最短编码长度描述训练集数据集的模型。这就是最小描述长度 Minimal Description Length:MDL准则。
     • 此时的编码长度包括了：描述模型自身所需要的字节长度，和使用该模型描述数据所需要的字节长度。

3. 给定训练集 $ MathJax-Element-137 $ ，贝叶斯网络 $ MathJax-Element-138 $ 在 $ MathJax-Element-505 $ 上的评分函数定义为：

   $ score(\mathcal B\mid \mathbb D)=f(\theta) |\mathcal B|-L(\mathcal B\mid \mathbb D) $

   其中： $ MathJax-Element-140 $ 表示描述每个参数 $ MathJax-Element-141 $ 所需的字节数； $ MathJax-Element-142 $ 是贝叶斯网络的参数个数；
   

   $ L(\mathcal B\mid\mathbb D)=\sum_{i=1}^{N}\log P(\mathbf {\vec x}_i) $

   是贝叶斯网 $ MathJax-Element-150 $ 的对数似然。因此：

   • 第一项 $ MathJax-Element-144 $ 是计算编码贝叶斯网络 $ MathJax-Element-150 $ 所需要的字节数。
   • 第二项 $ MathJax-Element-146 $ 是计算 $ MathJax-Element-150 $ 所对应的概率分布 $ MathJax-Element-148 $ 需要多少字节来描述 $ MathJax-Element-505 $ 。

4. 现在结构学习任务转换为一个优化任务，即寻找一个贝叶斯网络 $ MathJax-Element-150 $ 使评分函数 $ MathJax-Element-151 $ 最小。

   问题是，从所有可能的网络结构空间中搜索最优贝叶斯网络结构是个NP难问题，难以快速求解。

   有两种方法可以在有限时间内求得近似解：

   • 贪心算法。如从某个网络结构出发，每次调整一条边，直到评分函数不再降低为止。
   • 增加约束。通过给网络结构增加约束来缩小搜索空间，如将网络结构限定为树形结构等。

5. 贝叶斯网络训练好之后就能够用来进行未知样本的预测。

   最理想的是直接根据贝叶斯网络定义的联合概率分布来精确计算后验概率，但问题是这样的“精确推断”已经被证明是NP难的。

   此时需要借助“近似推断”，通过降低精度要求从而在有限时间内求得近似解，常用的近似推断为吉布斯采样(Gibbs sampling)。