第11章++概率图模型(上)

第11章概率图模型王泉中国科学院大学网络空间安全学院2016年11月目录•11.1概述•11.2有向图模型：贝叶斯网络•11.3无向图模型：马尔可夫随机场•11.4学习与推断•11.5隐马尔可夫模型•11.6条件随机场•11.7话题模型目录•11.1概述•11.2有向图模型：贝叶斯网络•11.3无向图模型：马尔可夫随机场•11.4学习与推断•11.5隐马尔可夫模型•11.6条件随机场•11.7话题模型信封问题•桌上有两个信封，其中一个信封装有一个红球（100美元）和一个黑球，另外一个信封装有两个黑球•你随机选了一个信封并从中随机取出一个球，发现是黑球•这时你被告知可以有一次换信封重新取球的机会，你会选择换还是不换？信封问题•随机变量𝐸∈1,0,𝐵∈红,黑•𝑃𝐸=1=𝑃𝐸=0=12⁄•𝑃𝐵=红E=1=12⁄,𝑃𝐵=红E=0=0信封问题•随机变量𝐸∈1,0,𝐵∈红,黑•𝑃𝐸=1=𝑃𝐸=0=12⁄•𝑃𝐵=红E=1=12⁄,𝑃𝐵=红E=0=0•实际上我们考察：𝑃𝐸=1𝐵=黑≥12⁄?信封问题•随机变量𝐸∈1,0,𝐵∈红,黑•𝑃𝐸=1=𝑃𝐸=0=12⁄•𝑃𝐵=红E=1=12⁄,𝑃𝐵=红E=0=0•实际上我们考察：𝑃𝐸=1𝐵=黑≥12⁄?𝑃𝐸=1𝐵=黑=𝑃𝐵=黑𝐸=1𝑃𝐸=1𝑃𝐵=黑𝐸=1𝑃𝐸=1+𝑃𝐵=黑𝐸=0𝑃𝐸=0=13换!!信封问题•随机变量𝐸∈1,0,𝐵∈红,黑•𝑃𝐸=1=𝑃𝐸=0=12⁄•𝑃𝐵=红E=1=12⁄,𝑃𝐵=红E=0=0𝑃𝐸=1𝑃𝐸=012⁄12⁄𝐸𝑃𝐵=红𝑃𝐵=黑112⁄12⁄001西瓜分类问题•基于西瓜的相关属性预测他们是不是好瓜𝑋1≔色泽∈乌黑,青绿,浅白𝑋2≔根蒂∈蜷缩,稍蜷,硬挺𝑋3≔敲声∈沉闷,浊响,清脆𝑋4≔纹理∈清晰,稍糊,模糊𝑋5≔脐部∈凹陷,稍凹,平坦𝑋6≔触感∈硬滑,软粘𝑌≔好瓜∈是,否𝑃𝑌𝑋1,𝑋2,𝑋3,𝑋4,𝑋5,𝑋6𝑃(𝑌,𝑋1,𝑋2,𝑋3,𝑋4,𝑋5,𝑋6)西瓜分类问题•基于西瓜的相关属性预测他们是不是好瓜𝑋1≔色泽∈乌黑,青绿,浅白𝑋2≔根蒂∈蜷缩,稍蜷,硬挺𝑋3≔敲声∈沉闷,浊响,清脆𝑋4≔纹理∈清晰,稍糊,模糊𝑋5≔脐部∈凹陷,稍凹,平坦𝑋6≔触感∈硬滑,软粘𝑌≔好瓜∈是,否𝑃𝑌𝑋1,𝑋2,𝑋3,𝑋4,𝑋5,𝑋6𝑃(𝑌,𝑋1,𝑋2,𝑋3,𝑋4,𝑋5,𝑋6)无条件独立假设•𝟐×𝟑×𝟑×𝟑×𝟑×𝟑×𝟐=𝟗𝟗𝟐西瓜分类问题•基于西瓜的相关属性预测他们是不是好瓜𝑋1≔色泽∈乌黑,青绿,浅白𝑋2≔根蒂∈蜷缩,稍蜷,硬挺𝑋3≔敲声∈沉闷,浊响,清脆𝑋4≔纹理∈清晰,稍糊,模糊𝑋5≔脐部∈凹陷,稍凹,平坦𝑋6≔触感∈硬滑,软粘𝑌≔好瓜∈是,否𝑃𝑌𝑋1,𝑋2,𝑋3,𝑋4,𝑋5,𝑋6𝑃(𝑌,𝑋1,𝑋2,𝑋3,𝑋4,𝑋5,𝑋6)无条件独立假设•𝟐×𝟑×𝟑×𝟑×𝟑×𝟑×𝟐=𝟗𝟗𝟐朴素贝叶斯•𝑃𝑌𝑋1,⋯,𝑋6∝𝑃𝑌∏𝑃𝑋𝑖𝑌6𝑖=1•𝟐+𝟔+𝟔+𝟔+𝟔+𝟔+𝟒=𝟑𝟔西瓜分类问题•基于西瓜的相关属性预测他们是不是好瓜𝑋1≔色泽∈乌黑,青绿,浅白𝑋2≔根蒂∈蜷缩,稍蜷,硬挺𝑋3≔敲声∈沉闷,浊响,清脆𝑋4≔纹理∈清晰,稍糊,模糊𝑋5≔脐部∈凹陷,稍凹,平坦𝑋6≔触感∈硬滑,软粘𝑌≔好瓜∈是,否𝑃𝑌𝑋1,𝑋2,𝑋3,𝑋4,𝑋5,𝑋6𝑃(𝑌,𝑋1,𝑋2,𝑋3,𝑋4,𝑋5,𝑋6)𝑃𝑋𝑖𝑌𝑃𝑌概率图模型•概率图模型(probabilisticgraphicalmodel)是用图结构来表达随机变量依赖关系的概率模型–节点：一个或一组随机变量–边：随机变量之间的概率依赖关系𝑃𝐸=1𝑃𝐸=012⁄12⁄𝐸𝑃𝐵=红𝑃𝐵=黑112⁄12⁄001𝑃𝑋𝑖𝑌𝑃𝑌两类图模型•有向图模型，也称贝叶斯网络(Bayesiannetwork)–以有向边表示变量间的“因果”关系(causality)•无向图模型，也称马尔可夫随机场(MarkovRandomField)–以无向边表示变量间的简单相关(correlation)有向图模型无向图模型目录•11.1概述•11.2有向图模型：贝叶斯网络•11.3无向图模型：马尔可夫随机场•11.4学习与推断•11.5隐马尔可夫模型•11.6条件随机场•11.7话题模型贝叶斯网络•图结构：有向无环图(DAG)–节点：一个或一组随机变量–边：随机变量之间的单向、直接影响（疾病症状）YESNO贝叶斯网络•图结构：有向无环图(DAG)–节点：一个或一组随机变量–边：随机变量之间的单向、直接影响（疾病症状）•当前节点：𝑥3•父节点：𝑥1•子节点：𝑥5•后代节点：𝑥5,𝑥6•马尔可夫毯：𝑥1,𝑥2,𝑥5贝叶斯网络•联合概率分布分解形式–𝐱≔𝑥1,𝑥2,⋯,𝑥𝑛；𝐱𝜋𝑖为𝑥𝑖所有父节点所构成的集合𝑃𝐱=�𝑃𝑥𝑖𝐱𝜋𝑖𝑛𝑖=1𝑃𝑥1,𝑥2,𝑥3,𝑥4,𝑥5,𝑥6=𝑃𝑥1𝑃𝑥2𝑥1𝑃𝑥3𝑥1𝑃𝑥4𝑥2𝑃𝑥5𝑥2,𝑥3𝑃𝑥6𝑥2,𝑥5示例：草坪问题𝑃𝑅=1𝑃𝑅=00.20.8𝑅𝑃𝑆=1𝑃𝑆=010.010.9900.40.6𝑆𝑅𝑃𝐺=1𝑃𝐺=0110.990.01100.90.1010.80.2000.01.0𝑃𝐺=1,𝑆=1,𝑅=1=𝑃𝐺=1𝑆=1,𝑅=1𝑃𝑆=1𝑅=1𝑃𝑅=1=0.99×0.01×0.2=0.00198𝑃𝐺,𝑆,𝑅=𝑃𝐺𝑆,𝑅𝑃𝑆𝑅𝑃𝑅𝑃𝐺=1,𝑆=1,𝑅=0=𝑃𝐺=1𝑆=1,𝑅=0𝑃𝑆=1𝑅=0𝑃𝑅=0=0.9×0.4×0.8=0.288示例：草坪问题𝑃𝑅=1𝑃𝑅=00.20.8𝑅𝑃𝑆=1𝑃𝑆=010.010.9900.40.6𝑆𝑅𝑃𝐺=1𝑃𝐺=0110.990.01100.90.1010.80.2000.01.0𝑃𝐺,𝑆,𝑅=𝑃𝐺𝑆,𝑅𝑃𝑆𝑅𝑃𝑅𝑃𝑆=1𝐺=1=𝑃𝐺=1,𝑆=1𝑃𝐺=1=∑𝑃𝐺=1,𝑆=1,𝑅𝑅∈1,0∑𝑃𝐺=1,𝑆,𝑅𝑆,𝑅∈1,0=0.00198+0.2880.00198+0.288+0.1584+0.0≈0.6467𝑃𝑅=1𝐺=1=𝑃𝐺=1,𝑅=1𝑃𝐺=1=∑𝑃𝐺=1,𝑆,𝑅=1𝑆∈1,0∑𝑃𝐺=1,𝑆,𝑅𝑆,𝑅∈1,0=0.00198+0.15840.00198+0.288+0.1584+0.0≈0.3577示例：朴素贝叶斯•𝐱=𝑥1,𝑥2,⋯,𝑥𝑛特征向量；𝑦类别标签𝑃𝑦𝐱=𝑃𝐱,𝑦𝑃𝐱∝𝑃𝑦�𝑃𝑥𝑖𝑦𝑛𝑖=1普通变量关系图盘式记法条件独立性•D-分离准则(D-separationcriterion)：判断贝叶斯网络节点之间的条件独立性条件独立性•D-分离准则(D-separationcriterion)：判断贝叶斯网络节点之间的条件独立性tail-to-tail𝑨⊥𝑩|𝑪条件独立性•D-分离准则(D-separationcriterion)：判断贝叶斯网络节点之间的条件独立性tail-to-tail𝑨⊥𝑩|𝑪𝑃𝐴,𝐵𝐶=𝑃𝐴,𝐵,𝐶𝑃𝐶=𝑃𝐶𝑃𝐴𝐶𝑃𝐵𝐶𝑃𝐶=𝑃𝐴𝐶𝑃𝐵𝐶条件独立性•D-分离准则(D-separationcriterion)：判断贝叶斯网络节点之间的条件独立性tail-to-tail𝑨⊥𝑩|𝑪head-to-tail𝑨⊥𝑩|𝑪条件独立性•D-分离准则(D-separationcriterion)：判断贝叶斯网络节点之间的条件独立性tail-to-tail𝑨⊥𝑩|𝑪head-to-tail𝑨⊥𝑩|𝑪𝑃𝐴,𝐵𝐶=𝑃𝐴,𝐵,𝐶𝑃𝐶=𝑃𝐴𝑃𝐶𝐴𝑃𝐵𝐶𝑃𝐶=𝑃𝐴,𝐶𝑃𝐵𝐶𝑃𝐶=𝑃𝐴𝐶𝑃𝐵𝐶条件独立性•D-分离准则(D-separationcriterion)：判断贝叶斯网络节点之间的条件独立性tail-to-tail𝑨⊥𝑩|𝑪head-to-tailhead-to-head𝑨⊥𝑩|𝑪𝑨⊥𝑩|𝑪或其任意后代条件独立性•给定节点集合𝐴,𝐵,𝐶，若𝐴中节点到𝐵中节点的所有无向路径都是阻塞的(blocked)，则称𝐴和𝐵被𝐶D-分离(D-separated)，即𝐴和𝐵关于𝐶条件独立•若一条无向路径包含节点𝑥满足以下条件之一，则称其是阻塞的–𝑥是tail-to-tail或head-to-tail节点，并且𝑥包含在𝐶中–𝑥是head-to-head节点，并且𝑥及𝑥的任意后代均不包含在𝐶中条件独立性•𝐴和𝐵是否关于𝐶条件独立？𝐴和𝐵是否关于𝐹条件独立？条件独立性•𝐴和𝐵是否关于𝐶条件独立？𝐴和𝐵是否关于𝐹条件独立？条件独立性•𝐴和𝐵是否关于𝐶条件独立？𝐴和𝐵是否关于𝐹条件独立？𝑨⊥𝑩|𝑪条件独立性•𝐴和𝐵是否关于𝐶条件独立？𝐴和𝐵是否关于𝐹条件独立？𝑨⊥𝑩|𝑪条件独立性•𝐴和𝐵是否关于𝐶条件独立？𝐴和𝐵是否关于𝐹条件独立？𝑨⊥𝑩|𝑪𝑨⊥𝑩|𝑭条件独立性•给定节点集合𝐴,𝐵,𝐶，若𝐴中节点到𝐵中节点的所有无向路径都是阻塞的(blocked)，则称𝐴和𝐵被𝐶D-分离(D-separated)，即𝐴和𝐵关于𝐶条件独立•若一条无向路径包含节点𝑥满足以下条件之一，则称其是阻塞的–𝑥是tail-to-tail或head-to-tail节点，并且𝑥包含在𝐶中–𝑥是head-to-head节点，并且𝑥及𝑥的任意后代均不包含在𝐶中贝叶斯网络的全局马尔可夫性(globalMarkovproperty)条件独立性•给定某变量的父节点，则该变量条件独立于其他所有非其后代节点•给定某变量的马尔可夫毯(父节点、子节点、子节点的父节点)，则该变量条件独立于其他变量𝑥𝑣⊥𝑥𝑉\𝑣\DE𝑣|𝑥PA𝑣𝑥𝑣⊥𝑥𝑉\𝑣\MB𝑣|𝑥MB𝑣贝叶斯网络的局部马尔可夫性(localMarkovproperty)目录•11.1概述•11.2有向图模型：贝叶斯网络•11.3无向图模型：马尔可夫随机场•11.4学习与推断•11.5隐马尔可夫模型•11.6条件随机场•11.7话题模型马尔可夫随机场•图结构：无向图–节点：一个或一组随机变量–边：随机变量之间的相互依赖（非“因果”关系）马尔可夫随机场•图结构：无向图–节点：一个或一组随机变量–边：随机变量之间的相互依赖（非“因果”关系）团：对于图中节点的一个子集，若其中任意两节点间都有边相连，则称该节点子集为一个团(clique)极大团：若在一个团中加入另外任何一个节点都不再形成团，则称该团为极大团(maximalclique)马尔可夫随机场•图结构：无向图–节点：一个或一组随机变量–边：随机变量之间的相互依赖（非“因果”关系）极大团：𝑥1,𝑥2,𝑥1,𝑥3,𝑥2,𝑥4,𝑥3,𝑥5𝑥2,𝑥5,𝑥6马尔可夫随机场•联合概率分布分解形式–𝐱≔𝑥1,𝑥2,⋯,𝑥𝑛；𝒞为团集合；𝐱𝐶为团𝐶∈𝒞对应的变量集合–𝜓𝐶为定义在团𝐶上的非负势函数(potentialfunction)–𝑍=∑∏𝜓𝐶𝐱𝐶𝐶∈𝒞𝑥是规范化因子𝑃𝐱=