Probabilistic Graphic Model

2020-03-01 160浏览

1.概率图模型 Probabilistic Graphical Model 51174500002 蔡璟辉 51174500009 储德明 51174500028 51174500034 金莹林喆 51174500051 吴旭东
2.目录 • 表示 • 贝叶斯网络 • 马尔可夫网储德明吴旭东 • 推断 • 精确推断 • 近似推断 • 学习金莹林喆蔡璟辉
3.概率图：概率论与图论的结合 • 处理机器学习中的不确定性和复杂性 • 图论提供直观的表示，便于进行分析，解释以及提出新模型 • 复杂系统由更小的部分和他们之间的概率关系组合而成，概率论确保了系统的一致性
4.基础知识 • 点为随机变量，边为概率依赖关系 • 阴影点为可观测变量，非阴影点为隐变量 • 盘 (plate) 里面为重复 • 有向图：贝叶斯网络，信念网络 • 无向图：马尔科夫网络 • 有向无向混合的链图
5.例子
6.条件独立 • 概率图表达条件独立 • 条件独立性让概率能够被分解，容易计算 • 条件独立约束了变量不能任意取值
7.概率图模型 • 一系列可观测变量和隐变量 • 概率图图模型是一些条件独立假图图图图图图图图图图图图束下的图图图图合概率分布图图图图 • 条件独立假设在图结构中表达 • 图结构在计算的过程更容易追溯和存储，容易被人理解，又能解决对应的概率模型
8.贝叶斯网络 • 贝叶斯网络是与一系列概率分布相关联的有向无环图 (Directed Acyclic Graph or DAG) • DAG 中无法从一个点出发回到这个点 • 给定一个点的父亲，它与它的祖先独立 • 依据点和父图图，构建图图图图合概率分布分解形式：图图图图图图图图图
9.贝叶斯网络例子
10.贝叶斯网络例子
11.D- 分离准则 • 判断两个变量 A,B 在 C 条件是是否独立 • 第三种被称为 V 型结构
12.条件独立性 • 给定点集 A,B,C 若 A 中节点到 B 中节点的所有路径都被阻塞，则 A,B 图于 C 独立 • 一条无向路径被阻塞，如存在点 x 图足如下条件： • x 与前后的边为非 V 型结构， x 属于 C • x 与前后的边为 V 型结构， x 及其后代中不存在点属于 C • 这样的路径被称为非有效迹，反之则称为有效迹 • 存在有效迹则两者不独立
13.
14.
15.
16.
17.
18.
19.
20.隐马尔科夫模型 • 时序概率模型，最简单的动态贝叶斯网络 • 根据图图叶斯网图图图图模型图图图得概率：图图图
21.贝叶斯网中的独立性可从两种截然不同的方式看待贝叶斯网： • 它提供了以因子分解的方式紧凑表示联合分布骨架的数据结构。 • 它是关于一个分布的一系列条件独立性假设的紧凑表示。在深层意义上，因子分解和独立性关系有什么样的联系呢？当已知一个分布 P 根据 G 因子分解时，是否可从图 G 中读出 P 蕴含的独立关系？
22.贝叶斯网语义
23.d- 分离 (d-Separation) 根据之前关于有效迹的讨论，这里引出 d- 分离的概念：这个集合也称为全局马尔可夫独立性集。
24.d- 分离 (d-Separation) 如果 P 根据 G 因子分解，给定 Z 图 X 与 Y 在 G 上是 d- 分离的，则 P 满足
25.图与分布 • 贝叶斯网的形式化语义是一系列独立性断言。同时另一方面，贝叶斯网是由条件概率分布 (CPDs) 做注图的图图图，图图个图图通图图图式法图图图图图叶斯网定图图图图图了一个图图联合分布。 • 接下来将证明这两个定义实际上是等价的：分布 P 满足与图 G 相图的条件图图图独立性，当且仅当 P 可以由图 G 相关的一系列条件概率分布表示。
26.独立图 (I-map) 首先定义与分布 P 相关的独立性的集合：现在可以将陈述“分布 P 满足于图 G 相关的条件独立性”简写为这种情况下，我们称 G 是 P 的一个独立图 (I-map) 。
27.独立图 (I-map) �1 �1 �2 X Y 和两个独立图，一个独立图 �2 X Y
28.等价性条件独立和因子分解的等价性： • 如果概率分布 P 可以按照某个图 G 因子分解，那么 G 就是 P 的一个独立图。 • 反之，如果 G 是概率分布 P 的一个独立图，那么 P 可以按照 G 来进行因子分解。
29.因子分解条件独立
30.条件独立因子分解
31.等价性条件独立和因子分解的等价性： • 如果概率分布 P 可以按照某个图 G 因子分解，那么 G 就是 P 的一个独立图。 • 反之，如果 G 是概率分布 P 的一个独立图，那么 P 可以按照 G 来进行因子分解。从条件独立和因子分解两个图点来看，我图图图图图图图得到了图图图图叶斯网的双重对偶视角：图图图 • 图 G 可以用来表示概率分布 P 。 • P 可以用来表达图 G 所展示的独立关系。
32.等价性当已知一个分布 P 根据 G 因子分解时候，是否可以从图中读出 P 图含的独立关系？确图图可以，但是不能保图图图图图图图图图图出分布中的所有独立性图图图图图图图图图图图系。（由独立图图图图图图图的定义图图图可知）图图
33.马尔可夫网
34.马尔可夫网 • 贝叶斯网 ——有向图模型 • • 节点：一个或一组随机变量边：随机变量之间的图向、直接影响 • 马尔可夫网——无向图模型 • • 节点：一个或一组随机变量边：随机变量之间的相互依赖（非“因果”关系）
35.例子对只满足
36.因子马尔可夫网中的交互影响是无向的，需要使用更加对称的参数化方法：
37.因子为了定义全局模型，有必要对这些交互影响进行组合。 Z 是一个归一化的常数。
38.吉布斯分布
39.如何理解因子能否尝试将因子理解为变量在其辖域上的边缘分布？ NO ！ A 、 B 上的边缘分布一个因子仅仅是影响联合分布的一个因素，而作为网图整体的图图图合分布需要将所有因子的影图图图图图图图图图图图图图考图图图去。
40.团位势参数化马尔可夫网的因子通常称为团位势。 • • 团：对于图中节点的一个子集，若其中任意两节点间都有边相连，则称该子集为一个团。极大团：若在一个团中加入另外任何节点都不再形成团，则称该团为极大团。
41.马尔可夫网中的独立性同图图叶斯网一图图图图图，图图图可夫网中的图图图图图图图构也可以看做是图图图图图图图图一系列独立性假图图图图图图图图的图图。概率影图沿着有效路径流“ 图。 ”图
42.分离基于有效路径的概念，可以在图中定义分离的概念：图图图图图图图图图
43.分离基于有效路径的概念，可以在图中定义分离的概念：
44.其他独立性
45.等价性图似图图图叶斯网，图图图图图图可夫网图图图图构所图图图含的独立性性图图图图图图图与一个分布在图图图图图图图上的分解之间也有着等价性的关系： • 如果分布 P 是在马尔可夫网 H 上因子分解的一个分布，那么 H 就是 P 的一个独立图。 • 反之，如果马尔可夫网 H 是正分布 P 的一个独立图，那么 P 可以按照 H 来进行因子分解。（ Hammersley-Clifford 定理）
46.贝叶斯网马尔可夫网 � ( � 4 ∨�1 , � 2 , � 3 ) φ
47.推断（ Inference ）
48.推断 (inference) • 假设图模型对应变量集分为和两个不相交的变量集 • 证据变量 (evidence); 为问题变量 (query) • 目标：计算边际概率或条件概率 • 联合概率由概率图模型得出 • 枚举： k 个变量，每个变量 r 个取值，复杂度 • 推断问题关键→高效计算边际分布
49.常见算法 • 因子乘积求和 • 变量消去 • 图上的信息传递 • 信念传播 • 团树算法 • 随机采样 • 马尔可夫链门特卡罗方法 (MCMC) • 其他采样方法
50.变量消去 (Variable Elimination) • 利用图模型所描述的条件独立性来削减计算量 • 最直观的精确推断算法，也是其他精确推断算法基础 C • 动态规划算法 • 目标，消去 C,D,I,G,H,S,L D • 推断 I G S L J H
51.变量消去 (Variable Elimination) • • Eliminate C • ⇒ • ⇒ • Eliminate D • ⇒ C D I G • ⇒ S L H J
52.变量消去 (Variable Elimination) •• Eliminate I • ⇒ C • ⇒ D I • Eliminate H G • ⇒ • ⇒ • Eliminate G • ⇒ • ⇒ • ⇒ S L J H
53.变量消去 (Variable Elimination) • 通过证据变量减少因子 • 获得变量集 Φ • 对每一个不是问题变量的变量 Z • 把 Z 从 Φ 消去 • 把剩下的因子都乘起来 • 重归一化得到分布
54.变量消去顺序 • C D I G SS L J H
55.找到变量消去顺序 • 使用启发式损失函数的贪心搜索 • 在每一点，消去消耗最小的节点 • 可能的损失函数 • 最少数目的邻居节点 • 添加最少的边 • 最小权重 • 添加最少权重的边（边的权重 =2 个节点的权重相乘）
56.聚类图 (Cluster Graph) 1:A,B A D B C A D B 2:B,C 4:A,D C 3:C,D
57.聚类图 • 在一个无向图中 • 节点是一个个聚，每个聚类类都是变量集的一个子集 • 连接和的边又被称为分离集， • 对于因子集 Φ 中的每个 ϕ 都分配给唯一的一个聚类 • 定义 1:A,B A D B 2:B,C 4:A,D C 3:C,D
58.聚类图 ϕ1 ( � , � , � ) , ϕ2 ( � , � ) , ϕ 3 ( � , � ) , ϕ 4 ( � , � ) , ϕ5 ( � , � ) , ϕ 6 ( � , � ) , ϕ7 ( � , � , � ) • 1:A,B,C C 2:B,C,D B B D 4:B,E B E 5:D,E 3:B,D,F D
59.聚类图 1:A,B,C B B B, C 2:B,C,D 4:B,E E D 5:D,E 3:B,D,F D
60.聚类图的性质 • Family preservation ：对于每个因子来说，它都被分配给一个且唯一一个聚类 C • Running intersection property ：对一对聚类和及来说，和间存在唯一的一条路径，它们间的所有聚类和分离集都包含 X C1 C3 X X X C2 X X C4 X C5 X X
61.聚类图的性质 1:A,B,C B, C C 2:B,C,D B B D 4:B,E B E 5:D,E 3:B,D,F D
62.Bethe 聚类图 • 每个因子分配给一个， • 对每个变量够造单独的聚类 • 如果，够造边 1:A,B,C 6： A 2:B,C,D 7： B 3:B,D,F 8： C 9： D 4:B,E 10 ： E 5:D,E 11 ： F
63.传递信息 1:A,B A 4:A,D D B 2:B,C �� → � ( � � , � ) = 3:C,D C ∑ � �− � � , � �� × ∏ �∈ (� � − { � }) �� →�
64.传递信息 • • i j 表示消息从传递到。表示被传递的消息。 • 通式的物理意义有以下三点： • 消息从 i 传递到 j ， i 会综合所有人给他说的信息（把所有的 δ 相乘） • 加上自己图图消息图图图合的认知（把图图图图图 δ 相乘的结果乘以消息之间的关系） • 3. 去除掉不需要图图的部分（把其他图图图图图量掉）图 • 以上循环一定次数后，达到某种稳定状态。
65.信念传播算法 • 把每个 ϕ 都分配图唯一的一个聚图图图图图图图 • 够造初始的因子 • 把所有消息都初始化为 1 • 循环 • 选择一条边来传递消息 • 计算
66.二次扫描 • 指定一个根图点，从所有叶图图图图图图图图点开始向根图图图图图图点图图图消息，直到根图图图图图节点收到所有接邻节点的消息 • 从根节点开始向叶节点传递消息，直到所有叶节点均收到消息
67.团树算法 • 在图上的信息图图图图图图 • 遵守聚类图的 family preservation 及 running intersection property �1→2 ( � )=∑ �1 � 1:A,B B �2→3 ( � ) =∑ �2 ×�1→2 �4→3 ( � )=∑ �4 � 2:B,C C � 3:C,D D 4:D,E
68.团树算法 �1→2 ( �) =∑ �1 �2→3 ( �,� )=∑ �2 ×�1→2 � �3→4 ( �,�) =∑ �3 ×�2→3 � � 1:C,D �3→2 ( �,� )=∑ �3 ×�4→3 D 2:G,I,D 5:H,G,J GI GJ �5→4 ( � , � ) =∑ �5 � � 3:G,S,I C D I G S GS 4:G,J,S,L L �4→3 ( �,� ) =∑ �4 ×�5→4 �,� J H
69.团树解决推断问题 • 在同一个团里的变量后验分布查询 • 包含这些变量的其它团的无关变量求和 • 引入新的证据变量 Z=z 后查询 X • X 和 Z 出现在同一个团中 • 把包含 X 和 Z 的团乘以指示函数 1(Z=z) • 加和无图图图量并重图图图图一化图 • X 和 Z 不出现在同一个团中 • 把包含 Z 变量的乘以指示函数团 1(Z=z) • 沿路径把消息图图播到包含图图图图图量 X 的团
70.团树算法与独立性 • 如果能观测到边上的变量，那么边两端的变量是独立的 C 1:C,D D D 2:G,I,D GI I G S L J H 5:H,G,J GJ 3:G,S,I GS 4:G,J,S,L � Φ ⊨ ( { � , � , � } ⊥ { � , � , � } { � , � })
71.变量消去与团树算法变量消去团树算法 • 每一步通过因子乘积生成一个因子 • 的一个因子被消去产生新的中间 • 来产生其他 • 对概率计算要从头开始 • 团的因子就是中间因子 • 是消息 • 一个取值的改变只影响一个方向来的信息，而另外一个方向传递来的信息不受影响
72.用变量消去生成团树 • 对每个在计算中使用的因子分配一个聚类 • 当生成的因子在中还被使用。则将聚类和用边连接起来
73.用变量消去生成团树 ••C:•G:•D:•S:•I:•L:C •H:G,I,D D C,D G, I D G,S,I G,S G,J,S,L G, H,G,J J J,S,L J,S,L J,L I G J,L S L J H
74.用变量消去生成团树 • 树状 • 在变量消去法中中间因子只被使用一次，且每个聚类传递一条消息给另一个聚类（每个聚类最多只有一个父节点） • Family preservation • 每一个初始因子 ϕ 都在变量消去环节被使用 • Running intersection property C1 C4 X C7X X C3 X X X C6 C2 C5
75.近似推断 • 采样算法 • 变分推断
76.采样算法 • 解决问题： • 关于一个概率分布函数期望： • 精确求出期望或许十分复杂
77.采样算法 • 解决问题： • 关于一个概率分布函数期望： • 精确求出期望或许十分复杂 • 解决方法： • 从概率分布独立抽取一图图图本其中图图 • 通过有限和计算 :
78.采样算法 • E.g.
79.采样算法 • E.g. � 0 � 1 � 1 � 0 �1
80.采样算法 • 性质 • 精度越高，结果越可靠，需要的采样次数越多 • 事件发生的概率很小，则需要很大的采样次数 • 随机变量数量增多，采样算法非常复杂
81.采样算法 • 性质 • 精度越高，结果越可靠，需要的采样次数越多 • 事件发生的概率很小，则需要很大的采样次数 • 随机变量数量增多，采样算法非常复杂 • 新的问题： • 如何在复图的概率分布中抽取相图图图图图图图图图图图独立的图图图图本？图
82.马尔科夫链蒙特卡洛方法 • 马尔科夫链 • 一种时域动态模型 • 不同的状态是随机变量所可能的取值 • 相邻状态之间是相关关系 • 目的 • 某些情况下，随机变量的分布无法用数学公式表达
83.马尔科夫链 • 具体介绍 • 表示随机变量在取值 • 如果每一个状态只取决于前一个状态，即 : • 马尔科夫链指一段时间内取值序列 (
84.转移 • 转移概率指一个时刻到下一个时刻，从状态概率：
85.转移 • 转移概率指一个时刻到下一个时刻，从状态概率： • E.g.
86.转移 • 转移概率指一个时刻到下一个时刻，从状态概率： • E.g. • 图在图图图刻图图概率，那么图图图
87.转移 • 转移概率指一个时刻到下一个时刻，从状态概率： • E.g. • 记在时刻为概率，那么 • E,g+…
88.转移 • 转移概率指一个时刻到下一个时刻，从状态概率： • E.g. • 记在时刻为概率，那么 • E,g 转移矩阵
89.马尔科夫链的平稳分布 • 平稳分布 • 收敛到平稳分布即 : 且: 其中转移概率矩阵 • 收敛之后每次转移都是样本
90.马尔科夫蒙特卡洛方法 (MCMC) • • 给定概率分布构造转移矩阵为马尔科夫链，使得马尔科夫链的平稳分布为 • 得到 • 如果马尔科夫过程在第步时已经达到平稳条件，那么就将一个样本选出
91.Metropolis Hastings 方法 • 细致平稳条件 • 对于一个马尔科夫过程，转移矩阵满足即随机变量转移到下个状态的概率和从该状态转移回来的概率相等
92.Metropolis Hastings 方法 • 细致平稳条件 • 对于一个马尔科夫过程，转移矩阵满足即随机变量转移到下个状态的概率和从该状态转移回来的概率相等 • 流程 • 用户给定先验概率从状态到状态概率 • 根据随机出有一个候选状态 • 计算出表示从状态接受的概率，其中
93.概率图上的马尔科夫链 • 马尔科夫链提供了一个通用框架 • 目标 • 从生成样本 • 做法 • 构造一条平稳分布的马尔科夫链
94.概率图上的马尔科夫链 • 定义马尔科夫链随机变量状态，满足 ξ • 这些状态为变量的值的子集
95.概率图上的马尔科夫链 • 定义马尔科夫链随机变量状态，满足 ξ • 这些状态为变量的值的子集 • 定义转移矩阵，使得平稳分布的期望是
96.概率图上的马尔科夫链 • 定义马尔科夫链随机变量状态，满足 ξ • 这些状态为变量的值的子集 • 定义转移矩阵，使得平稳分布的期望是 • 在图模型的情况下，每个状态都含有一些变量。 • 每次只图移状图图图图向量中的一图图图图图 • 定义多个转移矩阵 • 每步随机或者依次使用一个转移矩阵
97.概率图上的马尔科夫链 • 定义马尔科夫链随机变量状态，满足 ξ • 这些状态为变量的值的子集 • 定义转移矩阵，使得平稳分布的期望是 • 在图模型的情况下，每个状态都含有一些变量。 • 每次只转移状态向量中的一维 • 定义多个转移矩阵 • 每步随机或者依次使用一个转移矩阵 • 失去 • —— 依然符合马尔科夫链模型
98.吉布斯采样 • 分解状态空间 • 通过以下方法完成采样： • • • • 随机选取某变量根据变量，计算条件概率 ) 根据条件概率对，代替原值。循环上述操作
99.吉布斯采样 • 分解状态空间 • 通过以下方法完成采样： • • • • 随机选取某变量根据变量，计算条件概率 ) 根据条件概率对，代替原值。循环上述操作
100.生成样本 • 问题： • 构筑一条很长的马尔科夫链需要大量时间。
101.生成样本 • 问题： • 构筑一条很长的马尔科夫链需要大量时间。 • 观察： • 如果生成的，那么从的。
102.生成样本 • 问题： • 构筑一条很长的马尔科夫链需要大量时间。 • 观察： • 如果生成的，那么从的。 • 结论： • 有一条足够长的马尔科夫链，得到一个样本之后可以继续生成样本
103.生成样本 • 问题： • 构筑一条很长的马尔科夫链需要大量时间。 • 观察： • 如果生成的，那么从的。 • 结论： • 有一条足够长的马尔科夫链，得到一个样本之后可以继续生成样本 • 方法： • 我们用生成状态，然后将。
104.生成样本 • 新的问题： • 从相同轨迹生成的样本具有一定相关性； • 这些样本估计的方差远远低于从独立样本估计的方差。
105.生成样本 • 新的问题： • 从相同轨迹生成的样本具有一定相关性； • 这些样本估计的方差远远低于从独立样本估计的方差。 • 解决方法： • 将为样本后继续生成一段马尔科夫链，之后将样本。 • 将两个样本的相关性缩小的时间，与马尔科夫链达到平稳的时间有关。
106.变分推断 • 简单介绍： • 变分推断通过已知简单分布来逼近需推断的复杂分布。
107.变分推断 • 简单介绍： • 变分推断通过已知简单分布来逼近需推断的复杂分布。 •E.g:• 黄色的分布是需求的复杂分布 • 选用红色和绿色简单分布逼近 • 选用和的绿色分布来估计
108.平均场理论 • 平均场假设多变量可拆分为一系列相互独立的多变量且化为这些变量集的乘积：
109.平均场理论 • 平均场假设多变量可拆分为一系列相互独立的多变量且化为这些变量集的乘积： • 那么
110.平均场理论 • 平均场假设多变量可拆分为一系列相互独立的多变量且化为这些变量集的乘积： • 那么 • 如果我们只关心，固定去最大化 • 那么其中定义了 • 即
111.平均场理论 • 平均场假设多变量可拆分为一系列相互独立的多变量且化为这些变量集的乘积： • 那么 • 如果我们只关心，固定去最大化 • 那么其中定义了 • 即 • 当图图，。图 • 所以
112.步骤 • 图图图量图图图图行拆解 • 假设各变量子集服从何种分布 • 套用结论 • 结合 EM 算法可进行概率图模型的推断和参数估计。
113.近似算法对比 • • • • 变分推断效率高于采图算法图图采样算法比变分推断更精确变分推断推导过程相对复杂变分推断在拆解或子集分布假设不当时，效率低效果差
114.学习（ Learning ） 51174500002 蔡璟辉
115.基本定义根据实例（仅数据或数据与部分先验）来构建模型的任务叫做模型学习 1. 参数学习（ parameter estimation ） 2. 结构学习（ structure learning ）
116.学习任务
117.学习任务
118.学习任务
119.学习任务的目标 1. 在新的数据上进行准确的预测任务 2. 对概率图模型的知识挖掘
120.参数学习贝叶斯网络中的参数估计：求解问题的方法： 1. 极大似然估计（ MLE ） 2. 贝叶斯方法
121.极大似然估计图钉实例
122.极大似然估计一般情况：
123.贝叶斯网络中的极大似然估计
124.贝叶斯网络中的极大似然估计贝叶斯网络分解的似然函数
125.参数的极大似然估计对于 X_i 的局部似然函数为：
126.独立参数的极大似然估计问题约束单项最优全局最优
127.贝叶斯估计极大似然估计中，原理为 theta = argmax P(x theta) 贝叶斯估计中，原理为 theta = max p(theta x) 极大似然求解的最大的问题为无法对先验知识进行建模。
128.贝叶斯估计
129.先验 - 狄利克雷分布聚合性（ agglomerative property ）
130.先验 - 狄利克雷分布
131.贝叶斯估计
132.贝叶斯估计
133.马尔科夫网络中的参数估计似然函数：梯度：先验梯度增加项
134.贝叶斯网络结构学习 1. 基于约束的方法 2. 预计 Score 的方法 3. 贝叶斯模型均值方法
135.基于 Score 的方法 • 似然得分（ The Likelihood Score ） • BIC 得分（ Bayesian Information Criterion Score ） • 贝叶斯得分（ Bayesian Score ）
136.The Likelihood Score
137.似然得分的局限信息论解释：
138.贝叶斯得分
139.BIC 得分