38贝叶斯信念网络

贝叶斯网络北京10月机器学习班邹博2014年11月9日2/63历史遗留：对偶问题邹博在解决具体某个问题P的时候，往往由于参数、定义域等问题，不好直接处理。但可以把问题P转换成与之等价的问题Q。通过解决Q问题，来得到P问题的解。这时，Q问题就叫做P问题的“对偶问题”。July很抽象，跟没说一样3/63对偶问题给定M个整数和某定值s，要求从M个数中选择若干个数（同一个整数不能多次选择），使得被选中的数的和为s。输出满足条件的选择数目。如：从1、2、3、4、5、6、7、8、9中选择若干数，使得它们的和为40。4/63对偶图：Voronoi图和Delaunay剖分5/63Delaunay三角剖分6/63K近邻图的遗留问题K近邻图中，结点的度至少是KK互近邻图中，结点的度至多是K7/63复习：相对熵相对熵，又称互熵，交叉熵，鉴别信息，Kullback熵，Kullback-Leible散度等设p(x)、q(x)是X中取值的两个概率分布，则p对q的相对熵是两点说明：在一定程度上，相对熵可以度量两个随机变量的“距离”一般的，D(p||q)≠D(q||p)xxpyqxpExqxPxpqpD)()(log)()(log)()||()(8/63复习：互信息两个随机变量X，Y的互信息，定义为X，Y的联合分布和独立分布乘积的相对熵。I(X,Y)=D(P(X,Y)||P(X)P(Y))yxypxpyxpyxpYXI,)()(),(log),(),(9/63主要内容和目标掌握朴素贝叶斯分类的原理和具体步骤掌握概率图模型PGM的思想理解贝叶斯网络链式网络树形网络因子图非树形网络转换成树形网络的思路Summary-Product算法了解马尔科夫链、隐马尔科夫模型的网络拓扑和含义10/63一个实例11/63后验概率c1、c2表示左右两个信封。P(R)，P(B)表示摸到红球、黑球的概率。P(R)=P(R|c1)*P(c1)+P(R|c2)*P(c2)：全概率公式P(c1|R)=P(R|c1)*P(c1)/P(R)P(R|c1)=2/4P(R|c2)=1/3P(c1)=P(c2)=1/2如果摸到一个红球，那么，这个信封有1美元的概率是0.6如果摸到一个黑球，那么，这个信封有1美元的概率是3/712/63朴素贝叶斯的假设一个特征出现的概率，与其他特征(条件)独立（特征独立性）其实是：对于给定分类的条件下，特征独立每个特征同等重要（特征均衡性）13/63以文本分类为例样本：1000封邮件，每个邮件被标记为垃圾邮件或者非垃圾邮件分类目标：给定第1001封邮件，确定它是垃圾邮件还是非垃圾邮件方法：朴素贝叶斯14/63分析类别c：垃圾邮件c1，非垃圾邮件c2词汇表：统计1000封邮件中出现的所有单词，记单词数目为N，即形成词汇表。将每个样本si向量化：初始化N维向量xi，若词wj在si中出现，则xij=1，否则，为0。从而得到1000个N维向量x。使用：P(c|x)=P(x|c)*P(c)/P(x)15/63分解P(c|x)=P(x|c)*P(c)/P(x)P(x|c)=P(x1,x2…xN|c)=P(x1|c)*P(x2|c)…P(xN|c)P(x)=P(x1,x2…xN)=P(x1)*P(x2)…P(xN)带入公式：P(c|x)=P(x|c)*P(c)/P(x)等式右侧各项的含义：P(xi|cj)：在cj(此题目，cj要么为垃圾邮件1，要么为非垃圾邮件0)的前提下，第i个单词xi出现的概率P(xi)：在所有样本中，单词xi出现的概率P(cj)：(垃圾邮件)cj出现的概率16/63关于朴素贝叶斯的若干探讨遇到生词怎么办？拉普拉斯平滑编程的限制：小数乘积怎么办？问题：一个词在样本中出现多次，和一个词在样本中出现一次，形成的词向量相同由0/1改成计数如何判定该分类器的正确率样本中：K个生成分类器，1000-K个作为测试集交叉验证17/63贝叶斯网络把某个研究系统中涉及的随机变量，根据是否条件独立绘制在一个有向图中，就形成了贝叶斯网络。贝叶斯网络(BayesianNetwork)，又称有向无环图模型(directedacyclicgraphicalmodel)，是一种概率图模型，借由有向无环图(DirectedAcyclicGraphs,DAG)中得知一组随机变量{X1,X2...Xn}及其n组条件概率分布(ConditionalProbabilityDistributions,CPD)的性质。18/63贝叶斯网络一般而言，贝叶斯网络的有向无环图中的节点表示随机变量，它们可以是可观察到的变量，或隐变量、未知参数等。连接两个节点的箭头代表此两个随机变量是具有因果关系（或非条件独立）。若两个节点间以一个单箭头连接在一起，表示其中一个节点是“因(parents)”，另一个是“果(children)”，两节点就会产生一个条件概率值。每个结点在给定其直接前驱时，条件独立于其非后继。稍后详细解释此结论19/63一个简单的贝叶斯网络20/63全连接贝叶斯网络每一对结点之间都有边连接21/63一个“正常”的贝叶斯网络有些边缺失直观上：x1和x2独立x6和x7在x4给定的条件下独立x1,x2,…x7的联合分布：22/63对一个实际贝叶斯网络的分析1+2+2+4+4=13vs2^523/63贝叶斯网络：打印机故障诊断17*1+1*2+2*22+3*23+3*24=99226=6710886424/63贝叶斯网络：警报25/63贝叶斯网络：警报全部随机变量的联合分布26/63贝叶斯网络的形式化定义BN(G,Θ)G:有向无环图G的结点：随机变量G的边：结点间的有向依赖Θ：所有条件概率分布的参数集合结点X的条件概率：P(X|parent(X))思考：需要多少参数才能确定上述网络呢？每个结点所需参数的个数：结点的parent数目是M，结点和parent的可取值数目都是K：KM*(K-1)为什么？考察结点的parent对该结点形成了多少种情况（条件分布）27/63特殊的贝叶斯网络M个离散结点形成一条链，每一个结点有K个状态，则需要K-1+(M-1)K(K-1)个参数。这是关于长度M的线性函数。别忘了，如果是全连接，需要KM-1个参数，是关于M的指数函数。28/63通过贝叶斯网络判定条件独立—1P(a,b,c)=P(c)*P(a|c)*P(b|c)则：P(a,b|c)=P(a,b,c)/P(c)带入，得到：P(a,b|c)=P(a|c)*P(b|c)即：在c给定的条件下，a，b被阻断(blocked)，是独立的。条件独立：tail-to-tail29/63通过贝叶斯网络判定条件独立—2P(a,b,c)=P(a)*P(c|a)*P(b|c)即：在c给定的条件下，a，b被阻断(blocked)，是独立的。条件独立：head-to-tail30/63通过贝叶斯网络判定条件独立—3P(a,b,c)=P(a)*P(b)*P(c|a,b)在c未知的条件下，a，b被阻断(blocked)，是独立的：head-to-headP(b)*P(a)),(b)a,|P(c*P(b)*P(a)=c)b,P(a,cbaPc31/63举例说明这三种情况32/63将上述结点推广到结点集D-separation：有向分离对于任意的结点集A，B，C，考察所有通过A中任意结点到B中任意结点的路径，若要求A，B条件独立，则需要所有的路径都被阻断(blocked)，即满足下列两个前提之一：A和B的“head-to-tail型”和“tail-to-tail型”路径都通过C；A和B的“head-to-head型”路径不通过C以及C的子孙；33/63有向分离的举例Gas和Radio是独立的吗？给定Battery呢？Ignition呢？Starts呢？Moves呢？(答：IIIDD)34/63再次分析链式网络由D-separation可知，在xi给定的条件下，xi+1的分布和x1,x2…xi-1条件独立。即：xi+1的分布状态只和xi有关，和其他变量条件独立，这种顺次演变的随机过程，叫做马尔科夫链。后面的课中，会再次专门讲解马尔科夫链。35/63MarkovBlanket一个结点的MarkovBlanket是一个集合，在这个集合中的结点都给定的条件下，该结点条件独立于其他所有结点。即：一个结点的MarkovBlanket是它的parents,children以及spouses(孩子的其他parent)36/63MarkovBlanket补充知识：SerumCalcium(血清钙浓度)高于2.75mmo1/L即为高钙血症。许多恶性肿瘤可并发高钙血症。以乳腺癌、骨肿瘤、肺癌、胃癌、卵巢癌、多发性骨髓瘤、急性淋巴细胞白血病等较为多见，其中乳腺癌约1/3可发生高钙血症。37/63贝叶斯网络的用途诊断：P(病因|症状)预测：P(症状|病因)分类：maxclassP(类别|数据)通过给定的样本数据，建立贝叶斯网络的拓扑结构和结点的条件概率分布参数。这往往需要借助先验知识和极大似然估计来完成。在贝叶斯网络确定的结点拓扑结构和条件概率分布的前提下，可以使用该网络，对未知数据计算条件概率或后验概率，从而达到诊断、预测或者分类的目的。38/63应用实例由AT&T贝尔实验室开发的APRI系统从数据中学习和使用贝叶斯网络，用来识别那些有赖账倾向的客户NASAvista系统预测推进系统的失败率分析更精确的时间窗口，提供高可靠度的行动动态决定显示哪些信息39/63应用实例40/63贝叶斯网络的推断41/63计算过程42/63推导贝叶斯推断的通用公式由贝叶斯网络得到因子图(FactorGraph)通过在因子图中消息传递的思想，计算概率43/63因子图44/63因子图的构造由贝叶斯网络构造因子图的方法：一个因子对应因子图中的一个结点贝叶斯网络中的每一个变量在因子图上对应边或者半边结点g和边x相连当且仅当变量x出现在因子g中45/63因子图举例马尔科夫链46/63因子图举例隐马尔科夫模型47/63边缘分布由联合概率分布求边缘概率分布48/63分配率如果有那么试想：a*b+a*c：2次乘法，1次加法a*(b+c)：1次乘法，1次加法49/63举例说明该算法50/63提取公因子：即“分配率”51/63使用“消息传递”的观点52/63box内部的消息传递53/63Sum-Product算法54/63Sum-Product算法从计算来看，Sum-Product算法是将计算需要的中间过程进行了保存。如果计算多个概率分布，往往更有效。Sum-Product算法有点类似动态规划的思想：将一个概率分布写成两个因子的乘积，而这两个因子可以继续分解或者通过已知得到。55/63试给出该贝叶斯网络的因子图56/63上述贝叶斯网络的因子图57/63无向环可以发现，若贝叶斯网络中存在“环”（无向），则因此构造的因子图会得到环。而使用消息传递的思想，这个消息将无限传输下去，不利于概率计算。解决方法：删除贝叶斯网络中的若干条边，使得它不含有无向环重新构造没有环的贝叶斯网络58/63原贝叶斯网络的近似树结构59/63将两图的相对熵转换成变量的互信息60/63最大权生成树MSWT的建立过程1.对于给定的分布P(x)，对于所有的i≠j，计算联合分布P(xi|xj)；2.使用第1步得到的概率分布，计算任意两个结点的互信息I(Xi,Yj)，并把I(Xi,Yj)作为这两个结点连接边的权值；3.计算最大权生成树(Maximum-weightspanningtree)a.初始状态：n个变量(结点)，0条边b.插入最大权重的边c.找到下一个最大的边，并且加入到树中；要求加入后，没有环生成。否则，查找次大的边；d.重复上述过程c