贝叶斯分类器

念念不忘必有回响，有灯就有人。 ——《一代宗师》

贝叶斯网

贝叶斯网亦称“信念网”（belief network），它借助于有向无环图（Directed Acyclic Graph,DAG）来刻画属性之间的依赖关系，并使用条件概率表（Conditional Probability Table,CPT）来描述属性的联合概率分布。

具体来说，一个贝叶斯网B由结构G和参数\Theta两部分构成，即B = <G,\Theta>.网络结构G是一个有向无环图，其每个节点对应于一个属性，若两个属性有直接依赖关系，则它们由一条边连接起来；参数\Theta 定量描述这种依赖关系。假设属性x_i在G中的父节点集为\pi_i,则\Theta包含了每个属性的条件概率表\theta_{x_i|\pi_i}=P_B(x_i|\pi_i)

西瓜问题的一种贝叶斯网络结构以及属性“根蒂”的条件概率表(来源于周志华P157)

结构

贝叶斯网结构有效地表达了属性间的条件概率独立性。给定父节点集，贝叶斯网假设每个属性与它的非后裔属性节点独立，于是B = <G,\Theta>将属性x_1,x_2,...,x_d的联合概率分布定义为

当前状态只跟上一状态有关，跟上上或上上之前的状态无关。这种顺次演变的随机过程，就叫做马尔科夫链（Markov chain）。

一般而言，贝叶斯网络的有向无环图中的节点表示随机变量，它们可以是可观察到的变量，或隐变量、未知参数等。连接两个节点的箭头代表此两个随机变量是具有因果关系(或非条件独立)。若两个节点间以一个单箭头连接在一起，表示其中一个节点是“因(parents)”，另一个是“果(children)”，两节点就会产生一个条件概率值。

以图7.2为例，联合概率分布定义为：

显然，x_3和x_4在给定x_1的条件下独立，x_4和x_5在给定x_2的条件下独立，简记为x_3\perp x_4|x_1和x_4\perp x_5|x_2.

截图自周志华P158

• 在同父结构(tail-to-tail)下，x_3和x_4在给定x_1的条件下相互独立
  • x_1未知，p(x_1,x_3,x_4) = p(x_3|x_1)p(x_4|x_1)p(x_1),无法导出p(x_3,x_4) = p(x_3)p(x_4)
  • x_1已知，p(x_3,x_4|x_1) = \frac{p(x_1,x_3,x_4)}{p(x_1)} = \frac{p(x_3|x_1)p(x_4|x_1)p(x_1)}{p(x_1)} = p(x_3|x_1)p(x_4|x_1) ,即x_1已知条件下，x_3与x_4相互独立
• 在顺序结构(head-to-tail)下，给定x的值，则y和z条件独立
  • x未知，p(x,y,z) = p(z)p(x|z)p(y|x) ,无法导出p(y,z) = p(y)p(z)
  • x 已知，p(y,z|x) = \frac{p(x,y,z)}{p(x)} = \frac{ p(z)p(x|z)p(y|x)}{p(x)} = \frac{p(x,z)p(y|x)}{p(x)} = p(z|x)p(y|x) ,即x已知条件下，y与z相互独立
• V型结构（V-structure,head-to-head）亦称“冲撞结构” ,给定子节点x_4的取值，x_1和x_4一定不独立；奇妙的是，若x_4的 取值完全未知，则V型结构下x_1和x_2是相互独立的：这样的独立性称为"边际独立性".

事实上，一个变量取值的确定与否，能对另两个变量间的独立性发生影响，这个现象并非V型结构所特有。例如在同父结构中，条件独立性x_3 \perp x_4|x_1成立，但若x_1取值未知，则x_3与x_4就不独立；在顺序结构中，y\perp z|x，但y\perp z不成立。

为了分析有向图中变量间的条件独立性，可使用“有向分离”（D-separation）,我们先把有向图转变为一个无向图：

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

D-separation：有向分离 对于任意的结点集A，B，C，考察所有通过A中任意结点到B中任意结点的路径，若要求A，B条件独 立，则需要所有的路径都被阻断(blocked)，即满足下列两个前提之一： 1）A和B的“head-to-tail型”和“tail-to-tail型”路径都通过 ； 2）A和B的“head-to-head型”路径不通过C以及C的子孙. 如果A,B不满足D-separation，A,B有时被称为D-connected。 对于链条x_1\Rightarrow x_2 \Rightarrow x_3 \Rightarrow ... \Rightarrow x_i \Rightarrow x_{i+1} \Rightarrow ... \Rightarrow x_k,由D-separation可知，在x_i给定的条件下，x_{i+1}的分布和x_1,x_2…x_{i-1}条件独立。即：x_{i+1}的分布状态只和x_i有关，和其他变量条件独立，这种顺次演变的随机过程模型，叫做马尔科夫模型。

由此产生的无向图称为"道德图"（moral graph）,令父节点相连的过程称为“道德化” （moralization）Cowell et al.1999.

基于道德图能直接、迅速地找到变量间的条件独立性。假定道德图中有变量x、y和变量集合z = \{z_i\} ,若变量x和y能在图中被z分开，即从道德图中将变量集合z去除后，x和y分属两个连通分支，则称变量x和y被z有向分离，x\perp y|z成立。例如，图7.2所对应的道德图如图7.2所示，从图中能容易地找到所有的条件独立关系x_3\perp x_4|x_1,x_4\perp x_5|x_2,x_3\perp x_2 | x_1,x_3\perp x_5 | x_1,x_3\perp x_5|x_2等。

道德图

学习

若网络结构已知，即属性间的依赖关系已知，则贝叶斯网的学习过程相对简单，只需要通过训练样本“计数”,估计出每个节点的条件概率表即可，但在现实应用中我们并不知晓网络结构，于是，贝叶斯网络学习的首要任务就是根据训练数据集找到结构最“恰当”的贝叶斯网。“评分搜索”是求解这一问题的常用办法。

具体来说，首先我们需要定义一个“评分函数”（score function），以此来评估贝叶斯网与训练数据的契合程度，然后根据这个评分函数来寻找结构最优的贝叶斯网。显然，评分函数的设定纳入了我们希望获得什么样的贝叶斯网的归纳偏好。

常用的评分函数通常基于信息论准则，此类准则将学习问题看做一个数据压缩任务，学习的目标是找到一个能以最短编码长度描述训练数据的模型，此时编码的长度包括了描述模型自身所需的字节长度和使用该模型描述数据所需要的字节长度。对于贝叶斯网学习而言，模型就是一个贝叶斯网，同时，每个贝叶斯网描述了一个在训练数据上的概率分布，自有一套编码机制能使那些经常出现的样本有更短的编码。于是，我们应该选择哪个综合编码长度（综合描述网络和网络数据考虑）最短的贝叶斯网络，这就是“最小描述长度”（minimal description length,简称MDL）准则。

学习与评分函数

给定训练集合D = \{x_1,x_2,...,x_m\}(包含了目标变量y)，贝叶斯网B = <G,\Theta>在D上的评分函数可写为

其中，|B|是贝叶斯网的参数个数；f(\theta)表示描述每个参数\theta所需要的字节数 ；而

是贝叶斯网B的对数似然。

若f(\theta)=1,即每个参数用1字节描述，则得到AIC(Akaike Information Criterion)评分函数

若f(\theta)=1/2log(m),即每个参数用 1/2log(m) 个字节描述，则得到BIC（Bayesian

Information Criterion）评分函数

显然，若f(\theta)=0,即不计算对网络进行编码的长度，则评分函数退化为负对数似然，相应的，学习任务退化为极大似然估计。

不难发现，若贝叶斯网B= <G,\Theta>的网络结构G固定，则评分函数s(B|D)的第一项为常数。此时，最小化s(B|D)等价于对参数\Theta的极大似然估计。（\Theta包含了每个属性的条件概率表\theta_{x_i|\pi_i}=P_B(x_i|\pi_i)），参数\theta_{x_i|\pi_i}能直接在训练数据集上通过经验估计获得，即

其中，\hat{P}_D(·)是D上的经验分布。因此，为了最小化评分函数s(B|D),只需要对网络结构进行搜索，而候选结构的最优参数可直接在训练集上计算得到。

不幸的是，从所有可能的网络结构空间搜索最优贝叶斯网结构是一个NP难问题，难以快速求解。有两种策略能在有限时间内求得近似解：

• 第一种是贪心算法，例如从某个网络结构出发，每次调整一条边（增加、删除或者调整方向），直到评分函数不再降低为止；
• 第二种算法是通过给网络结构施加约束来消减搜索空间，例如将网络结构限定为树形结构等。

例如，TAN将结构限定为树形（半朴素贝叶斯分类器可看做是贝叶斯网络的特例）。

TAN是在最大权生成树MSWT算法的基础上生成的。其建立过程为：

1.对于给定的分布P(x)，对于所有的i≠j，计算联合分布P(x_i|x_j)；

2.使用第1步得到的概率分布，计算任意两个结点的互信息I(x_i,x_j|y) = \sum_{x_i,x_j;c\in Y}p(x_i,x_j|c)log\frac{p(x_i,x_j|c)}{p(x_i|c)p(x_j|c)}，并把I(x_i,y_j) 作为这两个结点连接边的权值；

3.计算最大权生成树(Maximum-weight spanning tree)

a. 初始状态：n个变量(结点)，0条边

b. 插入最大权重的边

c. 找到下一个最大的边，并且加入到树中；要求加入后，没有环生成；否则，查找次大的边；

d. 重复上述过程c过程直到插入了n−1条边(树建立完成)

4.选择任意结点作为根，从根到叶子标识边的方向；

5.可以保证，这棵树的近似联合概率P′(x)和原贝叶斯网络的联合概率P(x)的相对熵最小。

推断

令Q = \{Q_1,Q_2,...,Q_n\}表示待查询变量，E= \{E_1,E_2,...,E_k\}为证据变量，已知其取值为e = \{e_1,e_2,...,e_k\}.目标是计算出后验概率P(Q= q|E=e)，其中q = \{q_1,q_2,...,q_n\}是待查询变量的一组取值。

输入：贝叶斯网络B= <G,\Theta>;

采样次数T;

证据变量E及其取值e;

待查询变量Q及其取值q

过程：

1：n_q= 0

2：q^0为对Q 的随机取值

3：for t = 1,2,...,T do

4: for Q_i\in Q do

5: Z = E \cup Q\setminus \{Q_i\} ;

6: z = e \cup q^{t-1}\setminus \{q_i^{t-1}\};

7: 根据B计算分布P_B(Q_i|Z = z);

8: q_i^t=根据 P_B(Q_i|Z = z) 采样获取Q_i取值

9： q^t = 将q^{t-1}中的q_i^{t-1}用q_i^t替代

10: end for

11: if q^t = q then

12: n_q = n_q + 1

13: end if

14: end for

输出：P(Q= q|E = e)\simeq \frac{n_q}{T}

通过给定的样本数据，建立贝叶斯网络的拓扑结构和结点的条件概率分布参数。这往往需要借助先验知识和极大似然估计来完成。在贝叶斯网络确定的结点拓扑结构和条件概率分布的前提下，可以使用该网络，对未知数据计算条件概率或后验概率，从而达到诊断、预测或者分类的目的。

参考文献：

【1】https://www.cnblogs.com/yongfuxue/p/10094746.html

【2】《机器学习》 周志华，清华大学出版社

本文复制比例奇高，勿喷。仅为个人学习的记录。