有向图与条件独立性

1、定义：,XYX|, ,X YZY Zx y z令和 为随机变量。在给定Z的条件下，和称为条件独立的，记作如果下式对于所有的均成立,|( ,| )( | )( | )X Y ZX ZY Zfx y zfx z fy z直观地讲，知道了Z，Y并没有提供关于x的额外信息图：点集合和边集合的二元组顶点/节点（vertex/node）变量边（edge）依存性无向边/有向边有向图（directed graph）：所有的边都是有向边箭头：原因变量结果变量路径（path）：从节点Xi开始，中间不重复经过节点到节点Xj的连续连接的边集合，不管边的方向有向路径：路径上所有的边的方向都是朝向Xj有向环：从Xi到Xi

2、的有向路径有向有环图（directed cyclic graph）：有有向环的图也称为非递归模型（nonrecursive model）有向无环图（ directed acyclic graph，DAG）：没有有向环的图也称为递归模型（recursive model）X1Y2Y1无环图X1Y2Y1有环图一个有向图是由节点集及连接一对有序节点的边集组成的。一条开始和结束都在同一个变量处的有向路是一个圈，若一个有向图没有圈，则是非循环的。在这种情况下，称这种图为一个有向非循环图或DAGS。父节点（parents）：结果变量的直接原因子节点（child/daughter）：原因变量的直接结果祖节点（

3、ancestor）：与某变量间有直接路径的所有变量后裔节点（descendent）：从某变量出发的直接路径上的所有变量所有的父节点都是祖节点所有的子节点都是后裔节点X1X1X3X4X5变量的Markov链有向图X1Y2Y5Y3Y4Y1有分支和扰动的树形图对于一个DAG，总可以将所有节点排序，使得每个节点Xj的父节点都排在该节点之前DAG描述的概率分布为：(,)(,)121211nP x xxP xx xxnjjj(= ()(|(|fffff超重，吸烟，心脏病，咳嗽）超重）吸烟心脏病超重，吸烟）咳嗽吸烟）超重超重心脏病吸烟咳嗽(,)()121P xx xxP xPAjjjj令PAj表示节点Xj的

4、父节点的集合，一个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）马尔科夫决策方法XY ZA path is said to be d-sep

5、arated (or blocked) by a set of nodes Z if and only ifp contains a chain im j or a fork im j such that the middle node m is in set Z, orp 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 in Z如果一个路径不是有向分离的，称为有向连接的（d-connected

6、）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、果后，这两个原因因素变得相互独立了XYZXXYZYZW1、当Y不是一个相遇时，X和Z是有向连通的，但是它们在给定Y下是有向分离的。2、若X和Z在Y处相遇，则X和Z是有向分离的，但是它们在给定Y下是有向连通的。3、具有后裔节点的相遇与一般的相遇具有相同的结果。因此，在上面最后一个图中，X和Z是有向分离的，但是它们在给定W下是有向连通的。外星人 手表迟到得知你朋友已经迟到一定会增加她被绑架的可能性。但是当得知你忘记把你的手表设定好时，就会降低你朋友被绑架的可能性。因此，外星人和手表在给定迟到的条件下是相互依赖的。马尔科夫决策是一种风险型决策。主要研究对象是一个运行系统的状态和状态的转移。目的是根据

8、某些变量的现在状态及其变化趋向，来预测它在未来某一特定期间可能出现的状态，从而提供某种决策的依据。基本方法是用转移概率矩阵进行预测和决策。设 表示概率值， 表示 步转移概率矩阵，则有:矩阵各行概率表示状态 经过k步转移到状态后的概率。矩阵各行元素之和为1，即ijP( )kPk21111( )21.kknkkknkkmnmPPPPPPPiAjA11nijjP根据上表建立得失的转移概率矩阵：横行表示各公司失去客户到其他公司的概率。纵列表示各公司从其他公司得到客户的概率。160202020020020035450155005005002520255300300300上例显示8月1日各公司的市场占有率

9、为0.22、0.49、0.29 。预计9月1日各个公司的市场占有率的方法是将前一期的市场占有率乘以转移概率矩阵。具体如下： 若要预测k期的市场占有率，可用本期的占有率乘上转移概率矩阵的k次方。0.80.10.10.220.490.290.070.90.030.0830.0670.85只要转移概率矩阵不变，不管市场占有率如何改变，最后总会达到稳定状态，这时市场占有率不再改变，称为最后占有率。设ABC公司市场占有率分别稳定在X1,X2,X3. 因此有解得： 1231230.80.10.10.070.90.030.0830.0670.85xxxxxx10.27320.45430.273xxx假设A公司为提高市场占有率有2个方案：（1）与B公司竞争，从流失到B公司的客户中争回5%，转移概率矩阵求得最后占有率为0.850.050.10.070.90.030.0830.0670.851230.3360.3670.297xxx（2）与C公司竞争，从流失到C公司的客户中争回5%，转移概率矩阵如下：求得最后占有率为若两个方案费用相同，则A公司应该选择第一方案。如费用不同，则要比较净盈利进行决策。0.850.10.050