10.1贝叶斯网络

《10.1贝叶斯网络》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、贝叶斯网络七月算法邹博2015年4月12日复习：换个角度看对偶给定M个整数和某定值s，要求从M个数中选择若干个数(同一个整数不能多次选择)，使得被选中的数的和为s。输出满足条件的选择数目。如：从1、2、3、4、5、6、7、8、9中选择若干数，使得它们的和为40。2/69julyedu.com对偶图：Voronoi图和Delaunay剖分3/69julyedu.comDelaunay三角剖分4/69julyedu.comK近邻图的有趣结论K近邻图中，结点的度至少是KK互近邻图中，结点的度至多是K5/69julyedu.com相对熵

2、相对熵，又称互熵，交叉熵，鉴别信息，Kullback熵，Kullback-Leible散度等设p(x)、q(x)是X中取值的两个概率分布，则p对q的相对熵是pxpxDp

3、

4、qpxlogEpxlogxqxqx说明：相对熵可以度量两个随机变量的“距离”一般的，D(p

5、

6、q)≠D(q

7、

8、p)D(p

9、

10、q)≥0、D(q

11、

12、p)≥0提示：凸函数中的Jensen不等式6/69julyedu.com相对熵的应用思考假定已知随机变量P，求相对简单的随机变量Q，使得Q尽量接近P方法：使用P和Q的K-L距

13、离。难点：K-L距离是非对称的，两个随机变量应该谁在前谁在后呢？假定使用KL(Q

14、

15、P)，为了让距离最小，则要求在P为0的地方，Q尽量为0。会得到比较“窄”的分布曲线；假定使用KL(P

16、

17、Q)，为了让距离最小，则要求在P不为0的地方，Q也尽量不为0。会得到比较“宽”的分布曲线；7/69julyedu.com复习：互信息两个随机变量X，Y的互信息，定义为X，Y的联合分布和独立分布乘积的相对熵。I(X,Y)=D(P(X,Y)

18、

19、P(X)P(Y))p(x,y)I(X,Y)p(x,y)logx,yp(x)p(y)8/69julye

20、du.com复习：信息增益信息增益表示得知特征A的信息而使得类X的信息的不确定性减少的程度。定义：特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D

21、A)之差，即：g(D,A)=H(D)–H(D

22、A)显然，这即为训练数据集D和特征A的互信息。9/69julyedu.com概率条件概率：PABPABPB全概率公式：PAPA

23、BiPBii贝叶斯(Bayes)公式：P(A

24、B)P(B)iiPBAiP(A

25、Bj)P(Bj)j10/69

26、julyedu.com贝叶斯公式的应用8支步枪中有5支已校准过，3支未校准。一名射手用校准过的枪射击，中靶概率为0.8；用未校准的枪射击，中靶概率为0.3；现从8支枪中随机取一支射击，结果中靶。求该枪是已校准过的概率。53PG1PG088解：PA1G10.8PA0G10.2PA1G00.3PA0G00.7PG1A1?5PA1G1PG10.88PG1A10.8163PA1GiPGi0.850.33iG8811/69j

27、ulyedu.com一个实例12/69julyedu.com后验概率c1、c2表示左右两个信封。P(R)，P(B)表示摸到红球、黑球的概率。P(R)=P(R

28、c1)*P(c1)+P(R

29、c2)*P(c2)：全概率公式P(c1

30、R)=P(R

31、c1)*P(c1)/P(R)P(R

32、c1)=2/4P(R

33、c2)=1/3P(c1)=P(c2)=1/2如果摸到一个红球，那么，这个信封有1美元的概率是0.6如果摸到一个黑球，那么，这个信封有1美元的概率是3/713/69julyedu.com朴素贝叶斯的假设一个特征出现的概率，与其

34、他特征(条件)独立(特征独立性)其实是：对于给定分类的条件下，特征独立每个特征同等重要(特征均衡性)14/69julyedu.com以文本分类为例样本：1000封邮件，每个邮件被标记为垃圾邮件或者非垃圾邮件分类目标：给定第1001封邮件，确定它是垃圾邮件还是非垃圾邮件方法：朴素贝叶斯15/69julyedu.com分析类别c：垃圾邮件c，非垃圾邮件c12词汇表，两种建立方法：使用现成的单词词典；将所有邮件中出现的单词都统计出来，得到词典。记单词数目为N将每个邮件m映射成维度为N的向量x若单词w在邮件m中出现过，则

35、x=1，否则，x=0。即邮iii件的向量化：m(x,x……x)12N贝叶斯公式：P(c

36、x)=P(x

37、c)*P(c)/P(x)P(c

38、x)=P(x

39、c)*P(c)/P(x)111P(c

40、x)=P(x