搜索
第11章概率图模型王泉中国科学院大学网络空间安全学院2016年11月目录•11.1概述•11.2有向图模型：贝叶斯网络•11.3无向图模型：马尔可夫随机场•11.4学习与推断•11.5隐马尔可夫模型•11.6条件随机场•11.7话题模型•11.8本章小结概率图模型•概率图模型(probabilisticgraphicalmodel)是用图结构来表达随机变量依赖关系的概率模型–节点：一个或一组随机变量–边：随机变量之间的概率依赖关系𝑃𝐸=1𝑃𝐸=012⁄12⁄𝐸𝑃𝐵=红𝑃𝐵=黑112⁄12⁄001𝑃𝑋𝑖𝑌𝑃𝑌信封问题朴素贝叶斯两类图模型•有向图模型，也称贝叶斯网络(Bayesiannetwork)–以有向边表示变量间的“因果”关系(causality)•无向图模型，也称马尔可夫随机场(Markovrandomfield)–以无向边表示变量间的简单相关(correlation)有向图模型无向图模型贝叶斯网络•图结构：有向无环图(DAG)•联合概率分布分解形式–𝐱≔𝑥1,𝑥2,⋯,𝑥𝑛；𝐱𝜋𝑖为𝑥𝑖所有父节点所构成的集合𝑃𝐱=�𝑃𝑥𝑖𝐱𝜋𝑖𝑛𝑖=1𝑃𝑥1,𝑥2,𝑥3,𝑥4,𝑥5,𝑥6=𝑃𝑥1𝑃𝑥2𝑥1𝑃𝑥3𝑥1𝑃𝑥4𝑥2𝑃𝑥5𝑥2,𝑥3𝑃𝑥6𝑥2,𝑥5条件独立性•D-分离准则(D-separationcriterion)：判断贝叶斯网络节点之间的条件独立性tail-to-tail𝑨⊥𝑩|𝑪head-to-tailhead-to-head𝑨⊥𝑩|𝑪𝑨⊥𝑩|𝑪或其任意后代条件独立性•给定节点集合𝐴,𝐵,𝐶，若𝐴中节点到𝐵中节点的所有无向路径都是阻塞的(blocked)，则称𝐴和𝐵被𝐶D-分离(D-separated)，即𝐴和𝐵关于𝐶条件独立•若一条无向路径包含节点𝑥满足以下条件之一，则称其是阻塞的–𝑥是tail-to-tail或head-to-tail节点，并且𝑥包含在𝐶中–𝑥是head-to-head节点，并且𝑥及𝑥的任意后代均不包含在𝐶中贝叶斯网络的全局马尔可夫性(globalMarkovproperty)马尔可夫随机场•图结构：无向图•联合概率分布分解形式–𝐱≔𝑥1,𝑥2,⋯,𝑥𝑛；𝒞为团集合；𝐱𝐶为团𝐶∈𝒞对应的变量集合–𝜓𝐶为定义在团𝐶上的非负势函数；𝑍是规范化因子𝑃𝐱=1𝑍�𝜓𝐶𝐱𝐶𝐶∈𝒞𝑃𝑥1,𝑥2,𝑥3,𝑥4,𝑥5,𝑥6=1𝑍𝜓12𝑥1,𝑥2𝜓13𝑥1,𝑥3𝜓24𝑥2,𝑥4𝜓35𝑥3,𝑥5𝜓256𝑥2,𝑥5,𝑥6条件独立性•给定节点集合𝐴,𝐵,𝐶，若从𝐴中的节点到𝐵中的节点必须经过𝐶中的节点，则称𝐴和𝐵被𝐶分离，即𝐴和𝐵关于𝐶条件独立马尔可夫随机场的全局马尔可夫性(globalMarkovproperty)𝑨⊥𝑩|𝑪𝑨⊥𝑩|𝑪目录•11.1概述•11.2有向图模型：贝叶斯网络•11.3无向图模型：马尔可夫随机场•11.4学习与推断•11.5隐马尔可夫模型•11.6条件随机场•11.7话题模型•11.8本章小结基本定义•推断(inference)：已知联合概率分布𝑃𝑥1,⋯,𝑥𝑛，估计𝑃𝐱𝑄𝐱𝐸，其中𝐱𝑄∪𝐱𝐸⊆𝑥1,⋯,𝑥𝑛–𝐱𝑄问题变量(query)；𝐱𝑬证据变量(evidence)–已知模型，在给定证据的条件下回答问题𝑃𝑅=1𝑃𝑅=00.20.8𝑅𝑃𝑆=1𝑃𝑆=010.010.9900.40.6𝑆𝑅𝑃𝐺=1𝑃𝐺=0110.990.01100.90.1010.80.2000.01.0𝑃𝑆=1𝐺=1=?𝑃𝑅=1𝐺=1=?基本定义•学习(learning)：从观测数据𝐱1,⋯,𝐱𝑚中学习联合概率分布𝑃𝑥1,⋯,𝑥𝑛–寻找最符合观测数据的概率图模型𝑃𝑅=1𝑃𝑅=00.20.8𝑅𝑃𝑆=1𝑃𝑆=010.010.9900.40.6𝑆𝑅𝑃𝐺=1𝑃𝐺=0110.990.01100.90.1010.80.2000.01.0𝐺,𝑆,𝑅=1,1,0𝐺,𝑆,𝑅=1,1,1⋮𝐺,𝑆,𝑅=1,0,1𝐺,𝑆,𝑅=0,0,0基本定义•学习(learning)：从观测数据𝐱1,⋯,𝐱𝑚中学习联合概率分布𝑃𝑥1,⋯,𝑥𝑛–寻找最符合观测数据的概率图模型𝑃𝑅=1𝑃𝑅=00.20.8𝑅𝑃𝑆=1𝑃𝑆=010.010.9900.40.6𝑆𝑅𝑃𝐺=1𝑃𝐺=0110.990.01100.90.1010.80.2000.01.0𝐺,𝑆,𝑅=1,1,0𝐺,𝑆,𝑅=1,1,1⋮𝐺,𝑆,𝑅=1,0,1𝐺,𝑆,𝑅=0,0,0参数学习(parameterlearning)基本定义•学习(learning)：从观测数据𝐱1,⋯,𝐱𝑚中学习联合概率分布𝑃𝑥1,⋯,𝑥𝑛–寻找最符合观测数据的概率图模型𝑃𝑅=1𝑃𝑅=00.20.8𝑅𝑃𝑆=1𝑃𝑆=010.010.9900.40.6𝑆𝑅𝑃𝐺=1𝑃𝐺=0110.990.01100.90.1010.80.2000.01.0𝐺,𝑆,𝑅=1,1,0𝐺,𝑆,𝑅=1,1,1⋮𝐺,𝑆,𝑅=1,0,1𝐺,𝑆,𝑅=0,0,0参数学习(parameterlearning)结构学习(structurelearning)推断•已知联合概率分布𝑃𝑥1,⋯,𝑥𝑛，估计–𝐱𝑄问题变量；𝐱𝑬证据变量；𝐱𝑄∪𝐱𝐸=𝑥1,⋯,𝑥𝑛𝑃𝐱𝑄𝐱𝐸=𝑃𝐱𝑄,𝐱𝐸𝑃𝐱𝐸=𝑃𝐱𝑄,𝐱𝐸∑𝑃𝐱𝑄,𝐱𝐸𝐱𝑄观测图片𝑦𝑖原始图片𝑥𝑖𝑦�=argmax𝑃𝑦𝐱朴素贝叶斯𝐱�=argmax𝑃𝐱𝐲图像去噪推断•已知联合概率分布𝑃𝑥1,⋯,𝑥𝑛，估计–𝐱𝑄问题变量；𝐱𝑬证据变量；𝐱𝑄∪𝐱𝐸=𝑥1,⋯,𝑥𝑛–枚举：𝑘个变量，每个变量𝑟个取值，复杂度𝑟𝑘𝑃𝐱𝑄𝐱𝐸=𝑃𝐱𝑄,𝐱𝐸𝑃𝐱𝐸=𝑃𝐱𝑄,𝐱𝐸∑𝑃𝐱𝑄,𝐱𝐸𝐱𝑄推断•已知联合概率分布𝑃𝑥1,⋯,𝑥𝑛，估计–𝐱𝑄问题变量；𝐱𝑬证据变量；𝐱𝑄∪𝐱𝐸=𝑥1,⋯,𝑥𝑛–推断问题的关键：如何高效地计算边际分布𝑃𝐱𝐸=∑𝑃𝐱𝑄,𝐱𝐸𝐱𝑄𝑃𝐱𝑄𝐱𝐸=𝑃𝐱𝑄,𝐱𝐸𝑃𝐱𝐸=𝑃𝐱𝑄,𝐱𝐸∑𝑃𝐱𝑄,𝐱𝐸𝐱𝑄推断方法•精确推断：计算𝑃𝐱𝐸或𝑃𝐱𝑄𝐱𝐸的精确值–变量消去(variableelimination)–信念传播(beliefpropagation)•近似推断：在较低的时间复杂度下获得原问题的近似解–前向采样(forwardsampling)–吉布斯采样(Gibbssampling)变量消去•动机：利用图模型的紧凑概率分布形式来削减计算量–有向图–推断𝑃𝑥5=����𝑃𝑥1,𝑥2,𝑥3,𝑥4,𝑥5𝑥1𝑥2𝑥3𝑥4=����𝑃𝑥1𝑃𝑥2𝑥1𝑃𝑥3𝑥2𝑃𝑥4𝑥3𝑃𝑥5𝑥3𝑥1𝑥2𝑥3𝑥4变量消去•动机：利用图模型的紧凑概率分布形式来削减计算量–有向图–推断𝑃𝑥5=����𝑃𝑥1,𝑥2,𝑥3,𝑥4,𝑥5𝑥1𝑥2𝑥3𝑥4=����𝑃𝑥1𝑃𝑥2𝑥1𝑃𝑥3𝑥2𝑃𝑥4𝑥3𝑃𝑥5𝑥3𝑥1𝑥2𝑥3𝑥4变量消去•动机：利用图模型的紧凑概率分布形式来削减计算量–有向图𝑃𝑥5=����𝑃𝑥1𝑃𝑥2𝑥1𝑃𝑥3𝑥2𝑃𝑥4𝑥3𝑃𝑥5𝑥3𝑥1𝑥2𝑥3𝑥4=���𝑃𝑥3𝑥2𝑃𝑥4𝑥3𝑃𝑥5𝑥3�𝑃𝑥1𝑃𝑥2𝑥1𝑥1𝑥2𝑥3𝑥4=���𝑃𝑥3𝑥2𝑃𝑥4𝑥3𝑃𝑥5𝑥3𝑚12𝑥2𝑥2𝑥3𝑥4变量消去•动机：利用图模型的紧凑概率分布形式来削减计算量–有向图𝑃𝑥5=����𝑃𝑥1𝑃𝑥2𝑥1𝑃𝑥3𝑥2𝑃𝑥4𝑥3𝑃𝑥5𝑥3𝑥1𝑥2𝑥3𝑥4=���𝑃𝑥3𝑥2𝑃𝑥4𝑥3𝑃𝑥5𝑥3�𝑃𝑥1𝑃𝑥2𝑥1𝑥1𝑥2𝑥3𝑥4=���𝑃𝑥3𝑥2𝑃𝑥4𝑥3𝑃𝑥5𝑥3𝑚12𝑥2𝑥2𝑥3𝑥4变量消去•动机：利用图模型的紧凑概率分布形式来削减计算量–有向图𝑃𝑥5=����𝑃𝑥1𝑃𝑥2𝑥1𝑃𝑥3𝑥2𝑃𝑥4𝑥3𝑃𝑥5𝑥3𝑥1𝑥2𝑥3𝑥4=���𝑃𝑥3𝑥2𝑃𝑥4𝑥3𝑃𝑥5𝑥3�𝑃𝑥1𝑃𝑥2𝑥1𝑥1𝑥2𝑥3𝑥4=���𝑃𝑥3𝑥2𝑃𝑥4𝑥3𝑃𝑥5𝑥3𝑚12𝑥2𝑥2𝑥3𝑥4变量消去•动机：利用图模型的紧凑概率分布形式来削减计算量–有向图𝑃𝑥5=���𝑃𝑥3𝑥2𝑃𝑥4𝑥3𝑃𝑥5𝑥3𝑚12𝑥2𝑥2𝑥3𝑥4=��𝑃𝑥4𝑥3𝑃𝑥5𝑥3�𝑃𝑥3𝑥2𝑚12𝑥2𝑥2𝑥3𝑥4=��𝑃𝑥4𝑥3𝑃𝑥5𝑥3𝑚23𝑥3𝑥3𝑥4变量消去•动机：利用图模型的紧凑概率分布形式来削减计算量–有向图𝑃𝑥5=���𝑃𝑥3𝑥2𝑃𝑥4𝑥3𝑃𝑥5𝑥3𝑚12𝑥2𝑥2𝑥3𝑥4=��𝑃𝑥4𝑥3𝑃𝑥5𝑥3�𝑃𝑥3𝑥2𝑚12𝑥2𝑥2𝑥3𝑥4=��𝑃𝑥4𝑥3𝑃𝑥5𝑥3𝑚23𝑥3𝑥3𝑥4变量消去•动机：利用图模型的紧凑概率分布形式来削减计算量–有向图𝑃𝑥5=���𝑃𝑥3𝑥2𝑃𝑥4𝑥3𝑃𝑥5𝑥3𝑚12𝑥2𝑥2𝑥3𝑥4=��𝑃𝑥4𝑥3𝑃𝑥5𝑥3�𝑃𝑥3𝑥2𝑚12𝑥2𝑥2𝑥3𝑥4=��𝑃𝑥4𝑥3𝑃𝑥5𝑥3𝑚23𝑥3𝑥3𝑥4变量消去•动机：利用图模型的紧凑概率分布形式来削减计算量–有向图𝑃𝑥5=��𝑃𝑥4𝑥3𝑃𝑥5𝑥3𝑚23𝑥3𝑥3𝑥4=�𝑃𝑥5𝑥3𝑚23𝑥3�𝑃𝑥4𝑥3𝑥4𝑥3=�𝑃𝑥5𝑥3𝑚23𝑥3𝑚43𝑥3𝑥3变量消去•动机：利用图模型的紧凑概率分布形式来削减计算量–有向图𝑃𝑥5=��𝑃𝑥4𝑥3𝑃𝑥5𝑥3𝑚23𝑥3𝑥3𝑥4=�𝑃𝑥5𝑥3𝑚23𝑥3�𝑃𝑥4𝑥3𝑥4𝑥3=�𝑃𝑥5𝑥3𝑚23𝑥3𝑚43𝑥3𝑥3变量消去•动机：利用图模型的紧凑概率分布形式来削减计算量–有向图𝑃𝑥5=��𝑃𝑥4𝑥3𝑃𝑥5𝑥3𝑚23𝑥3𝑥3𝑥4=�𝑃𝑥5𝑥3𝑚23𝑥3�𝑃𝑥4𝑥3𝑥4𝑥3=�𝑃𝑥5𝑥3𝑚23𝑥3𝑚43𝑥3𝑥3变量消去•动机：利用图模型的紧凑概率分布形式来削减计算量–有向图𝑃𝑥5=��𝑃𝑥4𝑥3𝑃𝑥5𝑥3𝑚23𝑥3𝑥3𝑥4=�𝑃𝑥5𝑥3𝑚23𝑥3�𝑃𝑥4𝑥3𝑥4𝑥3=�𝑃𝑥5𝑥3𝑚23𝑥3𝑚43𝑥3𝑥3=𝑚35𝑥5变量消去•动机：利用图模型的紧凑概率分布形式来削减计算量–有向图𝑃𝑥5=��𝑃𝑥4𝑥3𝑃𝑥5𝑥3𝑚23𝑥3𝑥3𝑥4=�𝑃𝑥5𝑥3𝑚23𝑥3�𝑃𝑥4𝑥3𝑥4𝑥3=�𝑃𝑥5𝑥3𝑚23𝑥3𝑚43𝑥3𝑥3=𝑚35𝑥5变量消去•动机：利用图模型的紧凑概率分布形式来