图与概率

这是一篇关于图与概率的思维导图。从图论、术语、联合概率、链式法则、马氏相容、d分离、应用这几个方面作了介绍。

1.2 图与概率

• 图论
  • 无父为根，无子为汇
  • 图中每一个节点表示一个随机变量
  • 有向连线——>表示变量之间的关系（时序、因果、其他）
• 术语
  • 有向无环图：DAG，至少有1个根1个汇
  • 祖先 包含父母，后代 包含孩子
  • 族：本节点+父节点
  • 单亲为树，单子为链
• 联合概率
  • 由于 P(x1,...,xn) 中一定存在某些变量无法观测，因此无法直接得出联合概率
• 链式法则
  • 将 联合概率 转为 条件概率，条件概率在生活中更可观测
  • 是恒等的，但并未减少计算量与复杂度
• 马氏父母
  • 马氏父母是影响概率的最小集，只要知道父母即可确定概率，不用管其他变量，因此进一步降低了观测难度
  • 马氏性可大幅节约计算与存储
  • 当DAG中的箭头由马氏父母指向子女，即构成贝叶斯网络，贝叶斯网络可表示满足马氏性的P
• 贝叶斯网络
  • 利用 族(马氏父母及其子) 之间的递归性质， 可构建贝叶斯网络
    • 1）根据先验知识，若i<j，则 Xj 不可能是 Xi 的马氏父母
    • 2）根据先验知识，以马氏父母为起点X1，画箭头指向其子X2
    • 3）判断X3与X1、X2之间的阻断关系，从而找出X3的马氏父母，从马氏父母画箭头指向X3
    • 4）重复步骤2，即判断Xi与{ X1, ..., X i-1 }任一节点的阻断关系并画箭头
• 马氏相容
  • 若概率P可分解为G图中所有 给定马氏父母时的条件概率 之乘积，则称为P与G马氏相容或马氏相关
  • 数学上将以上DAG与P的关系，严格定义为
• d分离
  • 用图来判断条件独立性，当X、Y、Z为不相交变量集，若P(X|Z)=P(X|Z,Y)，定义为X、Y被Z d分离，如下两个表示方法等价
  • 在链结构、叉结构、对撞结构中，给定中间节点 都会导致改变 两边节点之间的独立性/依赖性
  • 定理
    • 1）
    • 2）一个G对应一个P，一个P可对应多个G
    • 3） P与G马氏相容的充要条件是：给定图G中的马氏父母后，每个变量都与自己的祖先独立
    • 4）若任意P既与G1马氏相容，又与G2马氏相容，则称这两个图G1与G2观测等价；两个观测等价的图：骨架一样，对撞结构一样
• 应用
  • 以上d分离相关定理，论证了G与P之间的关系，从而在应用中可放心地借助贝叶斯网络图做概率推理
• 概率、贝叶斯、条件独立性前节已讲，本节探讨用“图”语言表达概率与条件独立性。