有向图与条件独立性ppt课件

有向图与条件独立性,1,条件独立性,定义：,直观地讲，知道了Z，Y并没有提供关于x的额外信息,2,图的几个术语,图：点集合和边集合的二元组顶点/节点（vertex/node）变量边（edge）依存性无向边/有向边有向图（directedgraph）：所有的边都是有向边箭头：原因变量结果变量路径（path）：从节点Xi开始，中间不重复经过节点到节点Xj的连续连接的边集合，不管边的方向有向路径：路径上所有的边的方向都是朝向Xj有向环：从Xi到Xi的有向路径,3,有向图的类型,有向有环图（directedcyclicgraph）：有有向环的图也称为非递归模型（nonrecursivemodel）有向无环图（directedacyclicgraph，DAG）：没有有向环的图也称为递归模型（recursivemodel）,X1,Y2,Y1,无环图,X1,Y2,Y1,有环图,4,有向非循环图（DAGs）,一个有向图是由节点集及连接一对有序节点的边集组成的。一条开始和结束都在同一个变量处的有向路是一个圈，若一个有向图没有圈，则是非循环的。在这种情况下，称这种图为一个有向非循环图或DAGS。,5,DAG的几个术语,父节点（parents）：结果变量的直接原因子节点（child/daughter）：原因变量的直接结果祖节点（ancestor）：与某变量间有直接路径的所有变量后裔节点（descendent）：从某变量出发的直接路径上的所有变量,所有的父节点都是祖节点所有的子节点都是后裔节点,6,有向图示例,X1,X1,X3,X4,X5,变量的Markov链有向图,X1,Y2,Y5,Y3,Y4,Y1,有分支和扰动的树形图,7,DAG描述的概率分布,对于一个DAG，总可以将所有节点排序，使得每个节点Xj的父节点都排在该节点之前DAG描述的概率分布为：,8,DAG概率函数的例子,超重,心脏病,吸烟,咳嗽,9,Markov条件,令PAj表示节点Xj的父节点的集合，一个DAG描述的概率分布具有如下的条件独立假TheMarkovconditionimpliesthatvariableswillbeunconditionallydependentontheirparentsbutconditionallyindependentofallothernondescendentvariables,conditionalonparents.定理：令X、Y和Z为互不相交的节点集，则当且仅当X和Y被Z有向分离（d-separated）马尔科夫决策方法,10,有向分离准则（一）,Apathissaidtobed-separated(orblocked)byasetofnodesZifandonlyifpcontainsachainimjoraforkimjsuchthatthemiddlenodemisinsetZ,orpcontainsaninvertedfork(orcollider)imjsuchthatthemiddlenodemisnotinsetZandsuchthatnodescendentofmisinZ如果一个路径不是有向分离的，称为有向连接的（d-connected）AsetZofvariablescorrespondingtonodesintheDAGissaidtobed-separateasetofvariablesXfromYifandonlyifZblockseverypathfromanodeinXtoanodeinY.,可用来推断：起初相关的变量何时变得独立起初独立的变量如何变得相关,在给定原因条件下，其多个结果之间，如果没有因果关系的话，是相互独立的作为原因的多个因素，即使它们之间是相互独立的，但是给定结果后，这些原因可能变得相关了很难想象，两个原因相关，给定结果后，这两个原因因素变得相互独立了,11,有向分离准则（二）,X,Y,Z,X,X,Y,Z,Y,Z,W,1、当Y不是一个相遇时，X和Z是有向连通的，但是它们在给定Y下是有向分离的。2、若X和Z在Y处相遇，则X和Z是有向分离的，但是它们在给定Y下是有向连通的。3、具有后裔节点的相遇与一般的相遇具有相同的结果。因此，在上面最后一个图中，X和Z是有向分离的，但是它们在给定W下是有向连通的。,12,一个例子,外星人手表,迟到,得知你朋友已经迟到一定会增加她被绑架的可能性。但是当得知你忘记把你的手表设定好时，就会降低你朋友被绑架的可能性。因此，外星人和手表在给定迟到的条件下是相互依赖的。,13,马尔科夫决策方法,马尔科夫决策是一种风险型决策。主要研究对象是一个运行系统的状态和状态的转移。目的是根据某些变量的现在状态及其变化趋向，来预测它在未来某一特定期间可能出现的状态，从而提供某种决策的依据。基本方法是用转移概率矩阵进行预测和决策。,14,转移概率矩阵,设表示概率值，表示步转移概率矩阵，则有:矩阵各行概率表示状态经过k步转移到状态后的概率。矩阵各行元素之和为1，即,15,例子说明马尔科夫决策方法的步骤,16,（一）建立转移概率矩阵,根据上表建立得失的转移概率矩阵：横行表示各公司失去客户到其他公司的概率。纵列表示各公司从其他公司得到客户的概率。,17,（二）利用转移概率矩阵进行模拟预测,上例显示8月1日各公司的市场占有率为0.22、0.49、0.29。预计9月1日各个公司的市场占有率的方法是将前一期的市场占有率乘以转移概率矩阵。具体如下：若要预测k期的市场占有率，可用本期的占有率乘上转移概率矩阵的k次方。,18,（三）求转移概率矩阵的稳定状态,只要转移概率矩阵不变，不管市场占有率如何改变，最后总会达到稳定状态，这时市场占有率不再改变，称为最后占有率。设ABC公司市场占有率分别稳定在X1,X2,X3.因此有解得：,19,（四）应用转移概率矩阵进行决策,假设A公司为提高市场占有率有2个方案：（1）与B公司竞争，从流失到B公司的客户中争回5%，转移概率矩阵求得最后占有率为,20,（2）与C公司竞争，从流失到C公司的客户中争回5%，转移概率矩阵如下：求得最后占有率为若两个方案费用相同，则A公司应该选择第一方案。如费用不同