贝叶斯网络.ppt

贝叶斯网络 北京10月机器学习班 邹博 2014年11月9日 历史遗留：对偶问题 邹博 在解决具体某个问题P的时候，往往由于参数、定义域等问题，不好直接处理。但可以把问题P转换成与之等价的问题Q。通过解决Q问题，来得到P问题的解。这时，Q问题就叫做P问题的“对偶问题”。 July 很抽象，跟没说一样 对偶问题 给定M个整数和某定值s，要求从M个数中选择若干个数（同一个整数不能多次选择），使得被选中的数的和为s。输出满足条件的选择数目。 如：从1、2、3、4、5、6、7、8、9中选择若干数，使得它们的和为40。 对偶图：Voronoi图和Delaunay剖分 Delaunay三角剖分 K近邻图的遗留问题 K近邻图中，结点的度至少是K K互近邻图中，结点的度至多是K 复习：相对熵 相对熵，又称互熵，交叉熵，鉴别信息，Kullback熵，Kullback-Leible散度等 设p(x)、q(x)是X中取值的两个概率分布，则p对q的相对熵是 两点说明： 在一定程度上，相对熵可以度量两个随机变量的“距离” 一般的，D(p||q) ≠D(q||p) 复习：互信息 两个随机变量X，Y的互信息，定义为X，Y的联合分布和独立分布乘积的相对熵。 I(X,Y)=D(P(X,Y) || P(X)P(Y)) 主要内容和目标 掌握朴素贝叶斯分类的原理和具体步骤 掌握概率图模型PGM的思想 理解贝叶斯网络 链式网络 树形网络 因子图 非树形网络转换成树形网络的思路 Summary-Product算法 了解马尔科夫链、隐马尔科夫模型的网络拓扑和含义 一个实例 后验概率 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/7 朴素贝叶斯的假设 一个特征出现的概率，与其他特征(条件)独立（特征独立性） 其实是：对于给定分类的条件下，特征独立 每个特征同等重要（特征均衡性） 以文本分类为例 样本：1000封邮件，每个邮件被标记为垃圾邮件或者非垃圾邮件 分类目标：给定第1001封邮件，确定它是垃圾邮件还是非垃圾邮件 方法：朴素贝叶斯 分析 类别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) 分解 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出现的概率 关于朴素贝叶斯的若干探讨 遇到生词怎么办？ 拉普拉斯平滑 编程的限制：小数乘积怎么办？ 问题：一个词在样本中出现多次，和一个词在样本中出现一次，形成的词向量相同 由0/1改成计数 如何判定该分类器的正确率 样本中：K个生成分类器，1000-K个作为测试集 交叉验证 贝叶斯网络 把某个研究系统中涉及的随机变量，根据是否条件独立绘制在一个有向图中，就形成了贝叶斯网络。 贝叶斯网络(Bayesian Network)，又称有向无环图模型(directed acyclic graphical model)，是一种概率图模型，借由有向无环图(Directed Acyclic Graphs, DAG)中得知一组随机变量{X1,X2...Xn}及其n组条件概率分布(Conditional Probability Distributions, CPD)的性质。 贝叶斯网络 一般而言，贝叶斯网络的有向无环图中的节点表示随机变量，它们可以是可观察到的变量，或隐变量、未知参数等。连接两个节点的箭头代表此两个随机变量是具有因果关系（或非条件独立）。若两个节点间以一个单箭头连接在一起，表示其中一个节点是“因(parents)”，另一个是“果(children)”，两节点就会产生一个条件概率值。 每个结点在给定其