Microsoft PowerPoint - 图模型-mla11.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - 图模型-mla11.pptx"

幕赖
5 years ago
Views:

1 概率图模型 ---- 表示学习清华大学自动化系张长水 2011,11,6 1

2 概率图模型结合图论和概率论研究对象之间概率关系的一种工具与统计学系统工程信息论模式识别机器学习人工智能和统计力学中的研究关系密切 2

3 概率图模型有向图贝叶斯网络 (Baesian network) 信念网络 (Belief network) 无向图马尔可夫随机场 (Markov random field) 3

4 随机事件的条件独立如果有 P( AB, C) PA ( CPB ) ( C) 则称在给定事件 C 的条件下, 两个事件和 B 条件独立这其中假定 PC ( ) 0 可以写成 : A B C 等价形式 : PABC (, ) PAC ( ) PABC (,, ) PACPBC (, ) (, )/ PC ( ) A 4

5 随机变量的条件独立 p ( abc, ; ) p ( ac ; ) p ( bc ; ) AB C A C B C 5

6 随机变量的条件独立 6

7 随机变量的条件独立 7

8 随机变量的条件独立 B C A 1 A 2 8

9 图论 A S G ( V, E) T L B 顶点或节点 (node) 边 (edge 或 arc) E X 无向图 (nondirected graph) 有向图 (directed graph) 子图 D 9

10 图论 Y G ( V, E) A S 孤立节点相邻节点 T L B 起始节点终止节点或末节点 E 父节点祖先节点 X D 直接后继节点 10

11 图论路径 (path,chain) 起始节点 T L 终止节点路径的长度 E 环或圈, 或回路 (circuit, ccle) 连通的 A X S D B 11

12 图论 A S 有向无环图 (Directed Acclic Graph, DAG) T L B T E E X D X 12

13 图论割集 (separation) 13

14 图论在有向图中, 下面两个叙述是等价的 : 1) 图是无环的 2) 图中所有节点都可以按照一个方向排序 14

15 随机变量的图表示 E X X1 X2 X k (,,, ) V {1, 2,, k} (, i j) 15

16 条件独立图 V {1, 2, 3, 4}

17 条件独立图直观上 : 割集与条件独立有关系? 17

18 条件独立图 V {1, 2,, k} V1, V

19 条件独立图 V 3 V {1, 2,, k} V, 3 i j

20 条件独立图 V 3 V 3 V {1, 2,, k} V1, V

21 条件独立图

22 有向独立图只考虑有向无环图之所以这样, 是因为通常情况下, 没有适当的联合概率适合一个有向有环图 22

23 有向独立图在实际应用中, 节点的先后顺序可以表示事件的因果关系, 或表示与时间相关的过去现在和将来给定一个节点的顺序下, V( j) {1,2,, j} 表示节点的过去和现在 X j 23

24 有向独立图例 : 由下面的随机变量之间的条件独立性所描述的马尔可夫链 :,, 可以得到下面的图 :

25 有向独立图 (, i j) X X1 X2 X k (,,, ) E V {1, 2,, k} V( j) {1,2,, j} 25

26 有向独立图有向图表示了变量之间的因果关系有向图中割集和条件独立的关系?

27 有向独立图例 : 由下面的随机变量之间的条件独立性所描述的马尔可夫链 :,, 可以得到下面的图 :

28 有向独立图把上面的条件独立关系转换成无向独立图为则独立条件就变成为,,, 这种方法总是正确的吗? 边缘独立不意味着条件独立 28

29 有向独立图如果一个图中不存在下面的子图, 称该图满足 Wermuth 条件也称该图是 perfect 图, 即 : 一个有向无环图中每一个节点的所有父节点构成了一个完全子图 29

30 有向独立图一个图 G的 Moral graph G m 是一个这样一个无向图, 它包含图 G 的所有节点和边, 并加入了一些边使得不满足 Wermuth 条件的子图不存在可以通过把图 G 中每个节点的所有父节点相连接, 同时去掉边的箭头而得到 G m 去掉 V 结构 30

31 有向独立图例 : 下面是一个有向无环图和它的正则图定理 : 有向独立图具有其对应的正则图的马尔可夫性质 31

32 概率分布 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

33 概率分布 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

34 A S 举例 T L B E X D 呼吸困难 ( Dspnoea) 的原因可能来自于肺结核 (Tuberculosis) 肺癌 (Lung caner) 或支气管炎 (Bronchitis) 中的一种或几种, 或者其它原因最近如果去过 A 地的话, 将会增加患肺结核的几率而吸烟 (Smoking) 是导致肺癌和支气管炎的一个危险因素无论是否呼吸困难,X 光 (X-ra) 检查的结果将无法区分肺结核和肺癌 34

35 因子分析假设 X 的先验分布为,Y 的条件分布为, 这个模型就称作因子分析通常假设, 这个模型的意义在于用低维特征的线性组合来表示一个高维向量 35

36 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

37 Probabilistic Latent Semantic Analsis D: Documents Z: topics W: words D d z w N LDA: Latent Dirichlet Allocation Dnamic LDA 37

38 其他模型 PCA ICA Mixture of Experts Conditional Random Field, CRF 38

39 小结条件独立性 V 结构

40 概率图模型的参数学习假设概率图模型的结构已知目的 : 通过观察数据来学习模型的参数, 也就是概率分布函数的参数 A B D I X C 40

41 完整数据时最大似然参数学习在有向概率网络中, 已知由 N 个独立同分布的观测组成的集合 d { x 1,, x N } 其中 x n ( x n, 则似然函数可以表 1,, x n d ) 示为 : 41

42 完整数据时最大似然参数学习无向图中的概率分布 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

43 完整数据时最大似然参数学习最大化对数似然函数进行参数估计 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

44 完整数据情况下的最大似然参数学习 44

45 samples = 50 The maximum likelihood estimates of the parameters: F F : T F : F T : T T : F F : T F : F T : T T : parameters learned for node 4 the learned parameters are fairl close to the "true" ones 45

46 贝叶斯参数学习把参数看成一个随机变量确定随机变量的先验分布计算参数估计的后验, 或平均 46

47 缺失数据时最大似然参数学习 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

48 缺失数据时最大似然参数学习 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 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

50 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 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

52 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

53 Example: 53

54 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

55 after 10 iterations of EM

56 概率图模型的结构学习假设概率图模型的结构未知目的 : 通过观察数据来学习概率网络的结构和参数, 也就是确定各个节点之间的连接关系以及由此决定的概率密度函数的参数 A A B E B E C D C D 56

57 学习贝叶斯网络的策略对一个由变量集合构成的图结构, 有两个极端情况 ( 平凡 ): 所有变量不相连接 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 贝叶斯网络的结构学习基于搜索评价的方法给出一个评价准则 : 一组数据和一个网络结构是否吻合寻找该评价准则最好的结构 58

59 贝叶斯网络的结构学习存在几种评价贝叶斯网络的准则函数贝叶斯评价方法 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

60 马尔科夫网络的似然函数 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 个样本

61 似然函数性质 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 关于参数的最大似然没有解析形式采用优化方法

62 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

63 小结假设 : 给定结构且样本是完整 ( 所有变量被赋值 ) 的任务 : 学习参数, 参数估计方法 :(1) 最大似然估计, (2)Baes 预测假设 : 结构未知, 但是, 样本完整任务 : 学习结构和参数考虑一个可能结构的假设空间, 结构选择变为优化问题假设 : 样本不完整, 或某些变量未知任务 : 发现非显现表现的变量, 知识发现对 BN: 工具 : 最大似然和 Baes 估计特点 : 从局部到整体的学习困难 : 鲁棒性, 泛化对 MN: 工具 : 最大似然, Baes 估计, 迭代优化特点 : 鲁棒性, 泛化困难 : 整体的划分函数和推断

64 谢谢 64

EM算法及其应用

EM算法及其应用 EM 算法原理及其应用罗维大纲基础知识 EM 算法应用举例 EM 算法及其证明 EM 算法的变种 2 EM 算法的名字由来 E 步 M 步 Expectation 期望 Maximization 最大化 EM(Expectation Maximization, 期望最大化 ) 算法 3 笼统的 EM 算法描述 Loop { E 步 : 求期望 (expectation) } M 步 : 求极大