《有向图与条件独立性.ppt》由会员分享，可在线阅读，更多相关《有向图与条件独立性.ppt（22页珍藏版）》请在三一文库上搜索。
1、有向图与条件独立性有向图与条件独立性 条件独立性条件独立性 定义： 直观地讲，知道了Z，Y并没有提供关于x的额外信息 图的几个术语图的几个术语 图：点集合和边集合的二元组 顶点/节点（vertex/node）变量 边（edge）依存性 无向边/有向边 有向图（directed graph）：所有的边都是有向 边 箭头：原因变量结果变量 路径（path）：从节点Xi开始，中间不重复经 过节点到节点Xj的连续连接的边集合，不管边 的方向 有向路径：路径上所有的边的方向都是朝向Xj 有向环：从Xi到Xi的有向路径 有向有向图图的的类类型型 有向有环图（directed cyclic graph）：有
2、有向环 的图 也称为非递归模型（nonrecursive model） 有向无环图（ directed acyclic graph，DAG）： 没有有向环的图 也称为递归模型（recursive model） X1Y2 Y1 无环图 X1Y2 Y1 有环图 有向非循环图（有向非循环图（DAGSDAGS） 一个有向图是由节点集及连接一对有序节点的 边集组成的。 一条开始和结束都在同一个变量处的有向路是 一个圈，若一个有向图没有圈，则是非循环 的。在这种情况下，称这种图为一个有向非循 环图或DAGS。 DAGDAG的几的几个个术语术语 父节点（parents）：结果变量的直接原因 子节点（chil
3、d/daughter）：原因变量的直接结 果 祖节点（ancestor）：与某变量间有直接路径的 所有变量 后裔节点（descendent）：从某变量出发的直接 路径上的所有变量 所有的父节点都是祖节点 所有的子节点都是后裔节点 有向有向图图示例示例 X1X1X3X4X5 变量的Markov链有向图 X1Y2Y5 Y3Y4 Y1 有分支和扰动的树形图 DAGDAG描述的描述的概概率分布率分布 对于一个DAG，总可以将所有节点排序，使得 每个节点Xj的父节点都排在该节点之前 DAG描述的概率分布为： DAGDAG概率函数的例子概率函数的例子 超重 心脏病 吸烟 咳嗽 MARKOVMARKOV条条
4、件件 令PAj表示节点Xj的父节点的集合，一个DAG描述的概率分布 具有如下的条件独立假 The Markov condition implies that variables will be unconditionally dependent on their parents but conditionally independent of all other nondescendent variables, conditional on parents. 定理：令X、Y和Z为互不相交的节点集，则 当且仅当X和Y被Z有向分离（d-separated） 马尔科夫决策方法 有向分离准有向分离准则
5、则（一）（一） A path is said to be d-separated (or blocked) by a set of nodes Z if and only if p contains a chain im j or a fork im j such that the middle node m is in set Z, or p contains an inverted fork (or collider) im j such that the middle node m is not in set Z and such that no descendent of m is i
6、n Z 如果一个路径不是有向分离的，称为有向连接的（ d-connected） A set Z of variables corresponding to nodes in the DAG is said to be d-separate a set of variables X from Y if and only if Z blocks every path from a node in X to a node in Y. 可用来推断： 起初相关的变量何时变得独立 起初独立的变量如何变得相关 在给定原因条件下，其多个结果之间，如果没有因果关 系的话，是相互独立的 作为原因的多个因素，即使它
7、们之间是相互独立的，但 是给定结果后，这些原因可能变得相关了 很难想象，两个原因相关，给定结果后，这两个原因因 素变得相互独立了 有向分离准则（二）有向分离准则（二） X YZXXYZ YZ W 1、当Y不是一个相遇时，X和Z是有向连通的，但是它们在给定Y 下是有向分离的。 2、若X和Z在Y处相遇，则X和Z是有向分离的，但是它们在给定Y 下是有向连通的。 3、具有后裔节点的相遇与一般的相遇具有相同的结果。因此， 在上面最后一个图中，X和Z是有向分离的，但是它们在给定W下 是有向连通的。 一个例子一个例子 外星人 手表 迟到 得知你朋友已经迟到一定会增加她被绑架 的可能性。但是当得知你忘记把你的
8、手表 设定好时，就会降低你朋友被绑架的可能 性。因此，外星人和手表在给定迟到的条 件下是相互依赖的。 马尔科夫决策方法马尔科夫决策方法 马尔科夫决策是一种风险型决策。 主要研究对象是一个运行系统的状态 和状态的转移。 目的是根据某些变量的现在状态及其 变化趋向，来预测它在未来某一特定 期间可能出现的状态，从而提供某种 决策的依据。 基本方法是用转移概率矩阵进行预测 和决策。 转移概率矩阵转移概率矩阵 设 表示概率值， 表示 步转移概率矩阵，则 有: 矩阵各行概率表示状态 经过k步转移到状态 后的概率。 矩阵各行元素之和为1，即 例子说明马尔科夫决策方法的步骤例子说明马尔科夫决策方法的步骤 （一
9、）建立转移概率矩阵（一）建立转移概率矩阵 根据上表建立得失的转移概率矩阵： 横行表示各公司失去客户到其他公司的概率。 纵列表示各公司从其他公司得到客户的概率。 （二）利用转移概率矩阵进行模拟预（二）利用转移概率矩阵进行模拟预 测测 上例显示8月1日各公司的市场占有率为0.22、 0.49、0.29 。预计9月1日各个公司的市场占有 率的方法是将前一期的市场占有率乘以转移概 率矩阵。具体如下： 若要预测k期的市场占有率，可用本期的占有率 乘上转移概率矩阵的k次方。 （三）求转移概率矩阵的稳定状态（三）求转移概率矩阵的稳定状态 只要转移概率矩阵不变，不管市场占有率如何 改变，最后总会达到稳定状态，
10、这时市场占有 率不再改变，称为最后占有率。 设ABC公司市场占有率分别稳定在X1,X2,X3. 因此有 解得： （四）应用转移概率矩阵进行决策（四）应用转移概率矩阵进行决策 假设A公司为提高市场占有率有2个方案： （1）与B公司竞争，从流失到B公司的客户中 争回5%，转移概率矩阵 求得最后占有率为 （2）与C公司竞争，从流失到C公司的客户中 争回5%，转移概率矩阵如下： 求得最后占有率为 若两个方案费用相同，则A公司应该选择第一 方案。如费用不同，则要比较净盈利进行决 策。 决策特点：决策特点： 转移概率矩阵中的元素是根据近期市场或顾客 的保留与得失流向资料确定的。 下一期的概率只与上一期的预测结果有关，不 取决于更早的概率。 利用转移概率矩阵进行决策，其最后结果取决 于转移矩阵的组成，不取决于原始条件，即最 初占有率。