概率图模型 ---- 表示 学习 清华大学自动化系张长水 zcs@mail.tsinghua.edu.cn 2011,11,6 1
概率图模型 结合图论和概率论 研究对象之间概率关系的一种工具 与统计学 系统工程 信息论 模式识别 机器学习 人工智能和统计力学中的研究关系密切 2
概率图模型 有向图 贝叶斯网络 (Baesian network) 信念网络 (Belief network) 无向图 马尔可夫随机场 (Markov random field) 3
随机事件的条件独立 如果有 P( AB, C) PA ( CPB ) ( C) 则称在给定事件 C 的条件下, 两个事件和 B 条件独立 这其中假定 PC ( ) 0 可以写成 : A B C 等价形式 : PABC (, ) PAC ( ) PABC (,, ) PACPBC (, ) (, )/ PC ( ) A 4
随机变量的条件独立 p ( abc, ; ) p ( ac ; ) p ( bc ; ) AB C A C B C 5
随机变量的条件独立 6
随机变量的条件独立 7
随机变量的条件独立 B C A 1 A 2 8
图论 A S G ( V, E) T L B 顶点或节点 (node) 边 (edge 或 arc) E X 无向图 (nondirected graph) 有向图 (directed graph) 子图 D 9
图论 Y G ( V, E) A S 孤立节点 相邻节点 T L B 起始节点 终止节点或末节点 E 父节点祖先节点 X D 直接后继节点 10
图论 路径 (path,chain) 起始节点 T L 终止节点路径的长度 E 环或圈, 或回路 (circuit, ccle) 连通的 A X S D B 11
图论 A S 有向无环图 (Directed Acclic Graph, DAG) T L B T E E X D X 12
图论 割集 (separation) 13
图论 在有向图中, 下面两个叙述是等价的 : 1) 图是无环的 2) 图中所有节点都可以按照一个方向排序 14
随机变量的图表示 E X X1 X2 X k (,,, ) V {1, 2,, k} (, i j) 15
条件独立图 V {1, 2, 3, 4} 1 2 4 3 16
条件独立图 直观上 : 割集与条件独立有关系? 17
条件独立图 V {1, 2,, k} V1, V2 1 2 4 3 18
条件独立图 V 3 V {1, 2,, k} V, 3 i j 1 2 4 3 19
条件独立图 V 3 V 3 V {1, 2,, k} V1, V2 1 2 4 3 20
条件独立图 1 2 3 1 2 3 4 1 2 3 4 1 2 4 3 21
有向独立图 只考虑有向无环图 之所以这样, 是因为通常情况下, 没有适当的联合概率适合一个有向有环图 22
有向独立图 在实际应用中, 节点的先后顺序可以表示事件的因果关系, 或表示与时间相关的过去 现在和将来 给定一个节点的顺序下, V( j) {1,2,, j} 表示节点的过去和现在 X j 23
有向独立图 例 : 由下面的随机变量之间的条件独立性所描述的马尔可夫链 :,, 可以得到下面的图 : 1 2 3 4 24
有向独立图 (, i j) X X1 X2 X k (,,, ) E V {1, 2,, k} V( j) {1,2,, j} 25
有向独立图 有向图表示了变量之间的因果关系 有向图中割集和条件独立的关系? 1 2 3 4 26
有向独立图 例 : 由下面的随机变量之间的条件独立性所描述的马尔可夫链 :,, 可以得到下面的图 : 1 2 3 4 27
有向独立图 1 2 3 4 把上面的条件独立关系转换成无向独立图为则独立条件就变成为,,, 这种方法总是正确的吗? 边缘独立不意味着条件独立 28
有向独立图 如果一个图中不存在下面的子图, 称该图满足 Wermuth 条件 也称该图是 perfect 图, 即 : 一个有向无环图中每一个节点的所有父节点构成了一个完全子图 29
有向独立图 一个图 G的 Moral graph G m 是一个这样一个无向图, 它包含图 G 的所有节点和边, 并加入了一些边使得不满足 Wermuth 条件的子图不存在 可以通过把图 G 中每个节点的所有父节点相连接, 同时去掉边的箭头而得到 G m 去掉 V 结构 30
有向独立图 例 : 下面是一个有向无环图和它的正则图 2 3 1 4 2 3 1 4 定理 : 有向独立图具有其对应的正则图的马尔可夫性质 31
概率分布 p 与条件独立图 G 收集满足条件独立假设的所有断言 (X i X j Z), 构成一个集合, 称为关于 P 的 I-map, 记为 I(P) 对图 G, 独立断言集合 I(G) 如果 I(G)I(P), 则称 :G 是一个对独立集合 I(P) 的 I-map, 32
概率分布 p 与条件独立图 G 最小 map: 令 G 是一个对 I(P) 的最小 I-map, 如果它是一个对 I(P) 的 I-map, 且从 G 上移除任何一个单边, 它将不再是 I-map D,I,S,G,L L,S,G,I,D L,D,S,I,G 33
A S 举例 T L B E X D 呼吸困难 ( Dspnoea) 的原因可能来自于肺结核 (Tuberculosis) 肺癌 (Lung caner) 或支气管炎 (Bronchitis) 中的一种或几种, 或者其它原因 最近如果去过 A 地的话, 将会增加患肺结核的几率 而吸烟 (Smoking) 是导致肺癌和支气管炎的一个危险因素 无论是否呼吸困难,X 光 (X-ra) 检查的结果将无法区分肺结核和肺癌 34
因子分析 假设 X 的先验分布为,Y 的条件分布为, 这个模型就称作因子分析 通常假设, 这个模型的意义在于用低维特征的线性组合来表示一个高维向量 35
GMM I X 假设 I 的先验分布为 : PI ( i) wi,x 的条件分布为 : px ( x Ii) Nx ( ; i, i ) 边缘概率 px ( x) px ( x IPI ) ( ) wnx ( ;, ) I 这是一个混合高斯模型 i i i 用一组高斯模型来表示一个复杂的分布 i 36
Probabilistic Latent Semantic Analsis D: Documents Z: topics W: words D d z w N LDA: Latent Dirichlet Allocation Dnamic LDA 37
其他模型 PCA ICA Mixture of Experts Conditional Random Field, CRF 38
小结 条件独立性 V 结构 2 3 4 2 3 4 1 1 39
概率图模型的参数学习 假设概率图模型的结构已知 目的 : 通过观察数据来学习模型的参数, 也就是概率分布函数的参数 A B D I X C 40
完整数据时最大似然参数学习 在有向概率网络中, 已知由 N 个独立同分布的观测组成的集合 d { x 1,, x N } 其中 x n ( x n, 则似然函数可以表 1,, x n d ) 示为 : 41
完整数据时最大似然参数学习 无向图中的概率分布 A 联合分布是对子图势能的平均 B D 1 P( X,..., X n) f ( X1,..., X Z 1 n f ( X1,..., X n ) i ( Di ) ) P 称为 Gibbs 分布 势能函数 C Z X,..., X 1 1 X n f ( X,..., ) ( D ) n 1 X n X,..., i i Z 称为划分函数 42
完整数据时最大似然参数学习 最大化对数似然函数进行参数估计 n L( ) log p( d ) log p( x ) N d n1 i1 L( ) L( ) n1 n n log px ( pax ( ), ) d i1 i i N i i i n n Li( i) log p( xi pa( xi ), i) n 1 2 3 4 43
完整数据情况下的最大似然参 数学习 44
samples = 50 The maximum likelihood estimates of the parameters: F F : 1.0000 0.0000 T F : 0.2000 0.8000 F T : 0.2273 0.7727 T T : 0.0000 1.0000 F F : 1.0000 0.0000 T F : 0.1000 0.9000 F T : 0.1000 0.9000 T T : 0.0100 0.9900 parameters learned for node 4 the learned parameters are fairl close to the "true" ones 45
贝叶斯参数学习 把参数看成一个随机变量 确定随机变量的先验分布 计算参数估计的后验, 或平均 46
缺失数据时最大似然参数学习 With hidden variables, the log likelihood : L ( ) log p( x ) log p( x, ) x denotes the setting of the observed variables, the setting of the hidden variables. GMM plsa D d z w N I X 47
缺失数据时最大似然参数学习 Maximizing the log likelihood directl is often difficult because the log of the sum can potentiall couple all of the parameters of the model. An distribution q() over the hidden variables defines a lower bound on L: L( ) q( )log p( x, ) q( )log q( ) F( q, ) 48
49 缺失数据时最大似然参数学习 ), ( ) ( )log ( ), ( )log ( ) ( ), ( )log ( ) ( ), ( ) ( log ), ( log ) ( q F q q x p q q x p q q x p q x p L The inequalit is known as Jensen s inequalit
The EM Algorithm The Expectation-Maximization algorithm alternates between maximizing F with respect to q and, respectivel, holding the other fixed. E step: M step: q [ k1] [ k1] argmaxf( q q argmaxf( q [ k] [ k1], [ k], ) [ k] ) 50
51 The maximum in the E step is obtained b setting: ), ( ) ( ] [ 1] [ k k x p q ) ( ) ( log ) ( ) log, ( ), ( ) ( ), ( ) log, ( ) ( ), ( ) log ( ), ( L x p x p x p x p x p x p x p q x p q q F The EM Algorithm ) ( ), ( L q F
The EM Algorithm The maximum in the M step is obtained b maximizing the first term of F( q, ) M step : [ k 1] arg max p ( x, [ k ])log p(, x ) F( q, ) q( )log p( x, ) q( )log q( ) 52
Example: 53
Number of samples = 50. Randoml hide half the values generated from the water sprinkler example. samples2 = samples; hide = rand(n, nsamples) > 0.5; [I,J]=find(hide); for k=1:length(i) end samples2{i(k), J(k)} = []; 54
after 10 iterations of EM 0.6616 0.3384 0.6510 0.3490 0.8751 0.1249 0.8366 0.1634 0.0197 0.9803 0.8276 0.1724 0.0546 0.9454 0.5452 0.4548 0.1658 0.8342 55
概率图模型的结构学习 假设概率图模型的结构未知 目的 : 通过观察数据来学习概率网络的结构和参数, 也就是确定各个节点之间的连接关系以及由此决定的概率密度函数的参数 A A B E B E C D C D 56
学习贝叶斯网络的策略 对一个由变量集合构成的图结构, 有两个极端情况 ( 平凡 ): 所有变量不相连接 A 学习 : 部分相连 A A 所有变量两两相连 A B E 加边 B E B E 删边 B E C D C D 目标 : (1) 根据给定数据集发现变量之间的关系, 知识发现 ; (2) 密度估计, 其本质是泛化 核心 : 从数据集发现变量之间的独立关系 困难 : (1) 噪音, 没有绝对独立,(2) 稀疏解答 C D C D
贝叶斯网络的结构学习 基于搜索评价的方法 给出一个评价准则 : 一组数据和一个网络结构是否吻合 寻找该评价准则最好的结构 58
贝叶斯网络的结构学习 存在几种评价贝叶斯网络的准则函数 贝叶斯评价方法 n qi ri ( ri 1)! ScoreBDe( B, D) P( B, D) P( B) Nijk! ( N r 1)! i1 j1 ij i k1 最小描述长度 (minimum description length) 准则方法 基于熵的评价方法等 59
马尔科夫网络的似然函数 1 MN 已知, 并表示为 : P ( X 1,..., X n) i( D i) Z i 其中 是表示变量关系的势函数, 这里的 D i Z i( D i) 表示 i 涉及的变量观测 ( 在 MN 上的完全子图 ) X 1,..., X n i 将 写成权值和特征函数的形式 : i (D i )= i f i (D i ) 似然函数为 : k 1 L (, D ) P( X 1,..., X n : ) exp i fi( D i) Z ( ) i 1 取对数 k M l( : D ) ln L( : D ) i f i( [ m ]) M ln Z ( ) i1 m 1 注意 : 在特征函数中, 表示第 m 个样本中与 f 有关变量的数值, 这恰恰反映了 MN 的结构 方括号内是 M 个样本
似然函数性质 k M l( : D ) ln L( : D ) i fi( [ m ]) M ln Z ( ) i1 m 1 关键是 ln Z() ln Z ( ) ln exp i fi( ) i 关于参数 的最大似然没有解析形式采用优化方法
MN 参数估计算法 对数似然函数 i 1 M i k M l( : D ) i f i ( [ m ]) M ln Z ( ) i 1 m 1 为了计算最大似然, 对 求导, 并令其为 0 M 1 1 l( : D ) fi ( [ m ]) ln Z 0 M M m 1 右边第 1 项是对所有样本的平均 ( 经验 ), 第 2 项是对参数 的平均 ( 期望 ) 1 M l( : D ) E [ f ] E f 0 M m1 D i i 算法一般采用梯度法, 计算代价高 f ( [ m]) E [ f ] i D i i ln i Z E f 如果 是最大似然参数,iff 对所有 i,e D [f i ()]=E [f i ] i
小结 假设 : 给定结构且样本是完整 ( 所有变量被赋值 ) 的 任务 : 学习参数, 参数估计 方法 :(1) 最大似然估计, (2)Baes 预测 假设 : 结构未知, 但是, 样本完整 任务 : 学习结构和参数 考虑一个可能结构的假设空间, 结构选择变为优化问题 假设 : 样本不完整, 或某些变量未知 任务 : 发现非显现表现的变量, 知识发现 对 BN: 工具 : 最大似然和 Baes 估计 特点 : 从局部到整体的学习 困难 : 鲁棒性, 泛化 对 MN: 工具 : 最大似然, Baes 估计, 迭代优化 特点 : 鲁棒性, 泛化 困难 : 整体的划分函数和推断
谢谢 64