概率图模型中的推断

概率图模型中的推断王泉中国科学院大学网络空间安全学院2016年11月目录•推断问题回顾•精确推断：信念传播–信念传播算法回顾–信念传播在HMM中的应用•近似推断：吉布斯采样–吉布斯采样算法回顾–吉布斯采样在LDA中的应用目录•推断问题回顾•精确推断：信念传播–信念传播算法回顾–信念传播在HMM中的应用•近似推断：吉布斯采样–吉布斯采样算法回顾–吉布斯采样在LDA中的应用推断•已知联合概率分布𝑃𝑥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.001𝑃𝐸=0.002𝑃𝐴𝐵,𝐸=0.95𝑃𝐴𝐵,¬𝐸=0.94𝑃𝐴¬𝐵,𝐸=0.29𝑃𝐴¬𝐵,¬𝐸=0.001𝑃𝐽𝐴=0.9𝑃𝐽¬𝐴=0.05𝑃𝑀𝐴=0.7𝑃𝑀¬𝐴=0.01𝑃𝐵=1𝐸=0,𝐽=1=?𝑃𝐱𝑄𝐱𝐸=𝑃𝐱𝑄,𝐱𝐸𝑃𝐱𝐸推断•已知联合概率分布𝑃𝑥1,⋯,𝑥𝑛，估计–𝐱𝑄问题变量；𝐱𝑬证据变量；𝐱𝑄∪𝐱𝐸=𝑥1,⋯,𝑥𝑛𝑃𝐱𝑄𝐱𝐸=𝑃𝐱𝑄,𝐱𝐸𝑃𝐱𝐸观测图片𝑦𝑖原始图片𝑥𝑖𝑦�=argmax𝑃𝑦𝐱朴素贝叶斯𝐱�=argmax𝑃𝐱𝐲图像去噪推断方法•精确推断：计算𝑃𝐱𝑄𝐱𝐸的精确值–变量消去(variableelimination)–信念传播(beliefpropagation)–计算复杂度随着极大团规模的增长呈指数增长，适用范围有限•近似推断：在较低的时间复杂度下获得原问题的近似解–前向采样(forwardsampling)–吉布斯采样(Gibbssampling)–通过采样一组服从特定分布的样本，来近似原始分布，适用范围更广，可操作性更强推断方法•精确推断：计算𝑃𝐱𝑄𝐱𝐸的精确值–变量消去(variableelimination)–信念传播(beliefpropagation)–计算复杂度随着极大团规模的增长呈指数增长，适用范围有限•近似推断：在较低的时间复杂度下获得原问题的近似解–前向采样(forwardsampling)–吉布斯采样(Gibbssampling)–通过采样一组服从特定分布的样本，来近似原始分布，适用范围更广，可操作性更强目录•推断问题回顾•精确推断：信念传播–信念传播算法回顾–信念传播在HMM中的应用•近似推断：吉布斯采样–吉布斯采样算法回顾–吉布斯采样在LDA中的应用精确推断•已知联合概率分布𝑃𝑥1,⋯,𝑥𝑛，计算–𝐱𝑄问题变量；𝐱𝑬证据变量；𝐱𝑄∪𝐱𝐸=𝑥1,⋯,𝑥𝑛–问题的关键：如何高效地计算边际分布𝑃𝐱𝐸=∑𝑃𝐱𝑄,𝐱𝐸𝐱𝑄𝑃𝐱𝑄𝐱𝐸=𝑃𝐱𝑄,𝐱𝐸𝑃𝐱𝐸=𝑃𝐱𝑄,𝐱𝐸∑𝑃𝐱𝑄,𝐱𝐸𝐱𝑄目录•推断问题回顾•精确推断：信念传播–信念传播算法回顾–信念传播在HMM中的应用•近似推断：吉布斯采样–吉布斯采样算法回顾–吉布斯采样在LDA中的应用•动机：将变量消去过程中产生的中间结果视为可复用的消息(message)，避免重复计算–消息传递仅在邻接变量之间发生–消息传递与边的方向性无关(树结构)–消息传递与证据变量的选取无关(可复用)信念传播•消息传递与边际分布–消息：信念传播𝑚𝑗𝑖𝑥𝑖=�𝜓𝑥𝑗𝜓𝑥𝑖,𝑥𝑗�𝑚𝑘𝑗𝑥𝑗𝑘∈𝑁𝑗\𝑖𝑥𝑗•消息传递与边际分布–消息：–边际分布：信念传播𝑚𝑗𝑖𝑥𝑖=�𝜓𝑥𝑗𝜓𝑥𝑖,𝑥𝑗�𝑚𝑘𝑗𝑥𝑗𝑘∈𝑁𝑗\𝑖𝑥𝑗𝑃𝑥𝑖∝𝜓𝑥𝑖�𝑚𝑘𝑖𝑥𝑖𝑘∈𝑁𝑖•二次扫描算法(two-passalgorithm)–指定一个根节点，从所有叶节点开始向根节点传递消息，直到根节点收到所有邻接节点的消息–从根节点开始向叶节点传递消息，直到所有叶节点均收到消息信念传播目录•推断问题回顾•精确推断：信念传播–信念传播算法回顾–信念传播在HMM中的应用•近似推断：吉布斯采样–吉布斯采样算法回顾–吉布斯采样在LDA中的应用•隐马尔可夫模型(hiddenMarkovmodel)是关于时序的概率模型，是最简单的动态贝叶斯网络–状态变量𝑦1,𝑦2,⋯,𝑦𝑛，𝑦𝑡∈𝒴表示第𝑡时刻的系统状态–观测变量𝑥1,𝑥2,⋯𝑥𝑛，𝑥𝑡∈𝒳表示第𝑡时刻的观测值–观测变量仅依赖于当前时刻的状态变量，即𝑥𝑡由𝑦𝑡确定–当前状态仅依赖于前一时刻的状态，即𝑦𝑡由𝑦𝑡−1确定–𝒴≔𝑠1,𝑠2,⋯,𝑠𝑁,𝒳≔𝑜1,𝑜2,⋯,𝑜𝑀HMM回顾•隐马尔可夫模型的三要素–状态转移概率矩阵𝐀=𝑎𝑖𝑗𝑁×𝑁•在时刻𝑡处于状态𝑠𝑖的条件下在下一时刻转移到状态𝑠𝑗的概率–观测概率矩阵𝐁=𝑏𝑖𝑗𝑁×𝑀•在时刻𝑡处于状态𝑠𝑖的条件下观测到𝑜𝑗的概率–初始状态概率向量𝝅=𝜋1,𝜋2,⋯,𝜋𝑁•系统的初始状态为𝑠𝑖的概率HMM回顾𝑎𝑖𝑗=𝑃𝑦𝑡+1=𝑠𝑗𝑦𝑡=𝑠𝑖,1≤𝑖,𝑗≤𝑁𝑏𝑖𝑗=𝑃𝑥𝑡=𝑜𝑗𝑦𝑡=𝑠𝑖,1≤𝑖≤𝑁,1≤𝑗≤𝑀𝜋𝑖=𝑃𝑦1=𝑠𝑖,1≤𝑖≤𝑁•有向树转化为无向树HMM中的信念传播初始状态概率：𝑃𝑦1状态转移概率：𝑃𝑦𝑡𝑦𝑡−1观测概率：𝑃𝑥𝑡𝑦𝑡𝜓𝑦1=𝑃𝑦1,𝜓𝑥1=1𝜓𝑦𝑡=𝜓𝑥𝑡=1,𝑡=2,⋯,𝑛𝜓𝑦𝑡−1,𝑦𝑡=𝑃𝑦𝑡𝑦𝑡−1𝜓𝑥𝑡,𝑦𝑡=𝑃𝑥𝑡𝑦𝑡•二次扫描算法HMM中的信念传播•第一次扫描：从左向右–从观测变量向相应状态变量传递的消息HMM中的信念传播𝑚𝑥𝑡→𝑦𝑡=�𝜓𝑥𝑡𝜓𝑥𝑡,𝑦𝑡𝑥𝑡∈𝒳=𝑃𝑥𝑡𝑦𝑡,𝑡=1,⋯,𝑛•第一次扫描：从左向右–从观测变量向相应状态变量传递的消息HMM中的信念传播𝑚𝑥𝑡→𝑦𝑡=�𝜓𝑥𝑡𝜓𝑥𝑡,𝑦𝑡𝑥𝑡∈𝒳=𝑃𝑥𝑡𝑦𝑡,𝑡=1,⋯,𝑛𝑚𝑥𝑡→𝑦𝑡𝑠𝑖=𝑃𝑥𝑡𝑦𝑡=𝑠𝑖=𝑏𝑖𝑥𝑡•第一次扫描：从左向右–从当前状态变量向下一状态变量传递的消息HMM中的信念传播𝑚𝑦1→𝑦2=�𝜓𝑦1𝜓𝑦1,𝑦2𝑚𝑥1→𝑦1𝑦1∈𝒴=�𝑃𝑦1𝑃𝑦2𝑦1𝑃𝑥1𝑦1𝑦1∈𝒴𝑚𝑦𝑡→𝑦𝑡+1=�𝜓𝑦𝑡𝜓𝑦𝑡,𝑦𝑡+1𝑚𝑦𝑡−1→𝑦𝑡𝑚𝑥𝑡→𝑦𝑡𝑦𝑡∈𝒴=�𝑚𝑦𝑡−1→𝑦𝑡𝑃𝑦𝑡+1𝑦𝑡𝑃𝑥𝑡𝑦𝑡𝑦𝑡∈𝒴𝑡=2,⋯,𝑛−1•第一次扫描：从左向右–从当前状态变量向下一状态变量传递的消息HMM中的信念传播𝑚𝑦1→𝑦2=�𝜓𝑦1𝜓𝑦1,𝑦2𝑚𝑥1→𝑦1𝑦1∈𝒴=�𝑃𝑦1𝑃𝑦2𝑦1𝑃𝑥1𝑦1𝑦1∈𝒴𝑚𝑦𝑡→𝑦𝑡+1=�𝜓𝑦𝑡𝜓𝑦𝑡,𝑦𝑡+1𝑚𝑦𝑡−1→𝑦𝑡𝑚𝑥𝑡→𝑦𝑡𝑦𝑡∈𝒴=�𝑚𝑦𝑡−1→𝑦𝑡𝑃𝑦𝑡+1𝑦𝑡𝑃𝑥𝑡𝑦𝑡𝑦𝑡∈𝒴𝑚𝑦0→𝑦1𝑡=2,⋯,𝑛−1•第一次扫描：从左向右–从当前状态变量向下一状态变量传递的消息HMM中的信念传播𝑚𝑦0→𝑦1=𝑃𝑦1,𝑚𝑦𝑡→𝑦𝑡+1=�𝑚𝑦𝑡−1→𝑦𝑡𝑃𝑦𝑡+1𝑦𝑡𝑃𝑥𝑡𝑦𝑡𝑦𝑡∈𝒴,𝑡=1,⋯,𝑛−1•第一次扫描：从左向右–从当前状态变量向下一状态变量传递的消息HMM中的信念传播𝑚𝑦0→𝑦1𝑠𝑖=𝑃𝑦1=𝑠𝑖=𝜋𝑖,𝑚𝑦𝑡→𝑦𝑡+1𝑠𝑖=�𝑚𝑦𝑡−1→𝑦𝑡𝑠𝑗𝑎𝑗𝑖𝑏𝑗𝑥𝑡𝑁𝑗=1𝑚𝑦0→𝑦1=𝑃𝑦1,𝑚𝑦𝑡→𝑦𝑡+1=�𝑚𝑦𝑡−1→𝑦𝑡𝑃𝑦𝑡+1𝑦𝑡𝑃𝑥𝑡𝑦𝑡𝑦𝑡∈𝒴,𝑡=1,⋯,𝑛−1•第二次扫描：从右向左–从当前状态变量向上一状态变量传递的消息HMM中的信念传播𝑚𝑦𝑛→𝑦𝑛−1=�𝜓𝑦𝑛𝜓𝑦𝑛−1,𝑦𝑛𝑚𝑥𝑛→𝑦𝑛𝑦𝑛∈𝒴=�𝑃𝑦𝑛𝑦𝑛−1𝑃𝑥𝑛𝑦𝑛𝑦𝑛∈𝒴𝑚𝑦𝑡→𝑦𝑡−1=�𝜓𝑦𝑡𝜓𝑦𝑡−1,𝑦𝑡𝑚𝑦𝑡+1→𝑦𝑡𝑚𝑥𝑡→𝑦𝑡𝑦𝑡∈𝒴=�𝑚𝑦𝑡+1→𝑦𝑡𝑃𝑦𝑡𝑦𝑡−1𝑃𝑥𝑡𝑦𝑡𝑦𝑡∈𝒴𝑡=𝑛−1,⋯,2•第二次扫描：从右向左–从当前状态变量向上一状态变量传递的消息HMM中的信念传播𝑚𝑦𝑛→𝑦𝑛−1=�𝜓𝑦𝑛𝜓𝑦𝑛−1,𝑦𝑛𝑚𝑥𝑛→𝑦𝑛𝑦𝑛∈𝒴=�𝑃𝑦𝑛𝑦𝑛−1𝑃𝑥𝑛𝑦𝑛𝑦𝑛∈𝒴×1𝑚𝑦𝑡→𝑦𝑡−1=�𝜓𝑦𝑡𝜓𝑦𝑡−1,𝑦𝑡𝑚𝑦𝑡+1→𝑦𝑡𝑚𝑥𝑡→𝑦𝑡𝑦𝑡∈𝒴=�𝑚𝑦𝑡+1→𝑦𝑡𝑃𝑦𝑡𝑦𝑡−1𝑃𝑥𝑡𝑦𝑡𝑦𝑡∈𝒴𝑡=𝑛−1,⋯,2𝑚𝑦𝑛+1→𝑦𝑛=1•第二次扫描：从右向左–从当前状态变量向上一状态变量传递的消息HMM中的信念传播𝑚𝑦𝑛+1→𝑦𝑛=1,𝑚𝑦𝑡→𝑦𝑡−1=�𝑚𝑦𝑡+1→𝑦𝑡𝑃𝑦𝑡𝑦𝑡−1𝑃𝑥𝑡𝑦𝑡𝑦𝑡∈𝒴,𝑡=𝑛,⋯,2•第二次扫描：从右向左–从当前状态变量向上一状态变量传递的消息HMM中的信念传播𝑚𝑦𝑛+1→𝑦𝑛=1,𝑚𝑦𝑡→𝑦𝑡−1=�𝑚𝑦𝑡+1→𝑦𝑡𝑃𝑦𝑡𝑦𝑡−1𝑃𝑥𝑡𝑦𝑡𝑦𝑡∈𝒴,𝑡=𝑛,⋯,2𝑚𝑦𝑛+1→𝑦𝑛𝑠𝑖=1,𝑚𝑦𝑡→𝑦𝑡−1𝑠𝑖=�𝑚𝑦𝑡+1→𝑦𝑡𝑠𝑗𝑎𝑖𝑗𝑏𝑗𝑥𝑡𝑁𝑗=1•第二次扫描：从右向左–从状态变量向当前观测变量传递的消息HMM中的信念传播𝑚𝑦𝑡→𝑥𝑡=�𝜓𝑦𝑡𝜓𝑥𝑡,𝑦𝑡𝑚𝑦𝑡−1→𝑦𝑡𝑚𝑦𝑡+1→𝑦𝑡𝑦𝑡∈𝒴=�𝑃𝑥𝑡𝑦𝑡𝑚𝑦𝑡−1→𝑦𝑡𝑚𝑦𝑡+1→𝑦𝑡𝑦𝑡∈𝒴•第二次扫描：从右向左–从状态变量向当前观测变量传递的消息HMM中的信念传播𝑚𝑦𝑡→𝑥𝑡𝑥𝑡=�𝑏𝑖𝑥𝑡𝑚𝑦𝑡−1→𝑦𝑡𝑠𝑖𝑚𝑦𝑡+1→𝑦𝑡𝑠𝑖𝑁𝑖=1𝑚𝑦𝑡→𝑥𝑡=�𝜓𝑦𝑡𝜓𝑥𝑡,𝑦𝑡𝑚𝑦𝑡−1→𝑦𝑡𝑚𝑦𝑡+1→𝑦𝑡𝑦𝑡∈𝒴=�𝑃𝑥𝑡𝑦𝑡𝑚𝑦𝑡−1→𝑦𝑡𝑚𝑦𝑡+1→𝑦𝑡𝑦𝑡∈𝒴•计算条件概率𝑃𝑦𝑡=𝑠𝑖𝑥1,⋯,𝑥𝑛HMM中的信念传播𝑃𝑥1,⋯,𝑥𝑛,𝑦𝑡=𝜓𝑦𝑡𝑚𝑥𝑡→𝑦𝑡𝑚𝑦𝑡−1→𝑦𝑡𝑚𝑦𝑡+1→𝑦𝑡=𝑃𝑥𝑡𝑦𝑡𝑚𝑦𝑡−1→𝑦𝑡𝑚𝑦𝑡+1→𝑦𝑡𝑃𝑦𝑡=𝑠𝑖𝑥1,⋯,𝑥𝑛=𝑃𝑥1,⋯,𝑥𝑛,𝑦𝑡=𝑠𝑖∑𝑃𝑥1,⋯,𝑥𝑛,𝑦𝑡=𝑠𝑖𝑁𝑖=1=𝑏𝑖𝑥𝑡𝑚𝑦𝑡−1→𝑦𝑡𝑠𝑖�