10.1贝叶斯网络.pdf

立即下载 作者: 猫南北
上传时间: 2024-04-25
关键词: july 分布 距离 随机 edu.com 选择 69 假定 变量 近邻图
大小 3.6 MB
描述
贝叶斯网络
七月算法 邹博
2015年4月12日
2/69 julyedu.com
复习：换个角度看对偶
 给定M个整数和某定值s，要求从M个数中选
择若干个数(同一个整数不能多次选择)，使
得被选中的数的和为s。输出满足条件的选
择数目。
 如：从1、2、3、4、5、6、7、8、9中选择若干
数，使得它们的和为40。
3/69 julyedu.com
对偶图：Voronoi图和Delaunay剖分
4/69 julyedu.com
Delaunay三角剖分
5/69 julyedu.com
K近邻图的有趣结论
 K近邻图中，结点的度至少是K
 K互近邻图中，结点的度至多是K
6/69 julyedu.com
相对熵
 相对熵，又称互熵，交叉熵，鉴别信息，Kullback
熵，Kullback-Leible散度等
 设p(x)、q(x)是X中取值的两个概率分布，则p对q的
相对熵是
 说明：
 相对熵可以度量两个随机变量的“距离”
 一般的，D(p||q) ≠D(q||p)
 D(p||q)≥0、 D(q||p) ≥0
 提示：凸函数中的Jensen不等式
     
   
 
 xq
xp
E
xq
xp
xpqpD xp
x
loglog|| 
7/69 julyedu.com
相对熵的应用思考
 假定已知随机变量P，求相对简单的随机变量Q，
使得Q尽量接近P
 方法：使用P和Q的K-L距离。
 难点：K-L距离是非对称的，两个随机变量应该谁在前谁
在后呢？
 假定使用KL(Q||P)，为了让距离最小，则要求在P为
0的地方，Q尽量为0。会得到比较“窄”的分布曲
线；
 假定使用KL(P||Q)，为了让距离最小，则要求在P不
为0的地方，Q也尽量不为0。会得到比较“宽”的分
布曲线；
8/69 julyedu.com
复习：互信息
 两个随机变量X，Y的互信息，定义为X，Y
的联合分布和独立分布乘积的相对熵。
 I(X,Y)=D(P(X,Y) || P(X)P(Y))

yx ypxp
yxp
yxpYXI
, )()(
),(
log),(),(
9/69
目录
july/分布/距离/随机/edu.com/选择/69/假定/变量/近邻图/ july/分布/距离/随机/edu.com/选择/69/假定/变量/近邻图/