贝叶斯网络全解.ppt

*/63 感谢大家！ 恳请大家批评指正！ */63 举例说明这三种情况 */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的子孙； */63 有向分离的举例 Gas和Radio是独立的吗？给定Battery呢？Ignition呢？Starts呢？Moves呢？(答：IIIDD) */63 再次分析链式网络 由D-separation可知，在xi给定的条件下，xi+1的分布和x1,x2…xi-1条件独立。即：xi+1的分布状态只和xi有关，和其他变量条件独立，这种顺次演变的随机过程，叫做马尔科夫链。 后面的课中，会再次专门讲解马尔科夫链。 */63 Markov Blanket 一个结点的Markov Blanket是一个集合，在这个集合中的结点都给定的条件下，该结点条件独立于其他所有结点。 即：一个结点的Markov Blanket是它的parents,children以及spouses(孩子的其他parent) */63 Markov Blanket 补充知识：Serum Calcium(血清钙浓度)高于2.75mmo1/L即为高钙血症。许多恶性肿瘤可并发高钙血症。以乳腺癌、骨肿瘤、肺癌、胃癌、卵巢癌、多发性骨髓瘤、急性淋巴细胞白血病等较为多见，其中乳腺癌约1/3 可发生高钙血症。 */63 贝叶斯网络的用途 诊断：P(病因|症状) 预测：P(症状|病因) 分类：maxclassP(类别|数据) 通过给定的样本数据，建立贝叶斯网络的拓扑结构和结点的条件概率分布参数。这往往需要借助先验知识和极大似然估计来完成。 在贝叶斯网络确定的结点拓扑结构和条件概率分布的前提下，可以使用该网络，对未知数据计算条件概率或后验概率，从而达到诊断、预测或者分类的目的。 */63 应用实例 由ATT贝尔实验室开发的APRI系统 从数据中学习和使用贝叶斯网络，用来识别那些有赖账倾向的客户 NASA vista系统 预测推进系统的失败率 分析更精确的时间窗口，提供高可靠度的行动 动态决定显示哪些信息 */63 应用实例 */63 贝叶斯网络的推断 */63 计算过程 */63 推导贝叶斯推断的通用公式 由贝叶斯网络得到因子图(Factor Graph) 通过在因子图中消息传递的思想，计算概率 */63 因子图 */63 因子图的构造 由贝叶斯网络构造因子图的方法： 一个因子对应因子图中的一个结点 贝叶斯网络中的每一个变量在因子图上对应边或者半边 结点g和边x相连当且仅当变量x出现在因子g中 */63 因子图举例 马尔科夫链 */63 因子图举例 隐马尔科夫模型 */63 边缘分布 由联合概率分布求边缘概率分布 */63 分配率 如果有 那么 试想： a*b + a*c：2次乘法，1次加法 a*(b + c)：1次乘法，1次加法 */63 举例说明该算法 */63 提取公因子：即“分配率” */63 使用“消息传递”的观点 */63 box内部的消息传递 */63 Sum-Product算法 */63 Sum-Product算法 从计算来看， Sum-Product算法是将计算需要的中间过程进行了保存。如果计算多个概率分布，往往更有效。 Sum-Product算法有点类似动态规划的思想：将一个概率分布写成两个因子的乘积，而这两个因子可以继续分解或者通过已知得到。 */63 试给出该贝叶斯网络的因子图 */63 上述贝叶斯网络的因子图 */63 无向环 可以发现，若贝叶斯网络中存在“环”（无向），则因此构造的因子图会得到环。而使用消息传递的思想，这个消息将无限传输下去，不利于概率计算。 解决方法： 删除贝叶斯网络中的若干条边，使得它不含有无向环 重新构造没有环的贝叶斯网络 */63 原贝叶斯网络的近似树结构 */63 将两图的相对熵转换成变量的互信息 */63 最大权生成树MSWT的建立过程 1. 对于给定的分布P(x)，对于所有的i≠j，计算联合分布P(xi|xj)； 2.使用第1步得到的概率分布，计算任意两个结点的互信息I(Xi,Yj)，并把I(Xi,Yj)作为这两个结点连接边的权值； 3.计算最大权生成树(Maximum-weight spanning tree) a. 初始状态：n个变量(结点)，0条边 b. 插入最大权重的边 c. 找到下一个最大的边，并且加入到树中；要求加入后，没有环生成