研究生课程：机器学习-第9章 概率图模型

《机器学习》课程笔记：第9章 概率图模型

第9章 概率图模型

有向图模型：贝叶斯网络

图结构：有向无环图

结点：一个或一组随机变量

边：随机变量之间的单向、直接影响

联合概率分布分解形式：，其中， 为 所有父结点构成的集合

条件独立性 D-分离准则（D-separation criterion）：判断贝叶斯网络结点之间的条件独立性。

贝叶斯网络的全局马尔科夫性：给定结点集合A，B，C，若A到B中结点的所有无向路径都是被C阻塞的（blocked），则称A和B被C D-分离（D-separated），即A和B关于C条件独立。

若一条无向路径包含结点x满足以下条件之一，则称其是阻塞的：

• x 是tail-to-tail 或head-to-tail 结点，并且x包含在C中。
• x 是head-to-head 结点，并且x(及x 的任意后代均)不包含在C中。

贝叶斯网络的局部马尔科夫性：

• 给定某变量的父结点，则该变量条件独立于所有其他非其后代结点。
• 给定某变量的马尔可夫毯（父结点，子结点，子结点的父结点），则该变量条件独立于其他变量。

无向图模型：马尔可夫随机场

图结构：无向图

结点：一个或一组随机变量。

边：随机变量之间的相互依赖（非“因果关系”）。

团：对于图中的结点子集，若其中任意两个节点之间都有连边，则称该结点子集为一个团（clique）。

极大团：若在团中加入其他任意一个结点都不再形成团，则称该团为极大团（maximal clique）。

分解形式：

其中， 为团集合， 为团 对应的变量集合， 为定义在团 上的非负势函数，是归一化因子

条件独立性：

马尔可夫随机场的全局马尔科夫性：给定结点集合A，B，C，若从A中的结点到B中结点必须经过C中的结点，则称A和B被C分离，即A和B关于C条件独立。

局部马尔科夫性：给定某变量的马尔可夫毯（邻接变量），则该变量条件独立于其他变量。

成对马尔科夫性：给定其他所有变量，两个非相邻变量条件独立。 if

学习与推断

基本定义

推断：已知联合概率分布 ，估计 ，其中 是集合 的子集。 是问题变量， 是证据变量。

学习：从观测数据 中学习联合概率分布 ，寻找最符合观测数据的概率图模型。

推断：已知联合概率分布 ，估计，其中

枚举 : 假设 有 个变量，每个变量的取值个数的期望是 ，则时间复杂度为

推断的核心问题 : 如何高效地计算边际分布

推断方法

精确推断：计算或的精确值。

变量消去（variable elimination）

思路：利用图模型的紧凑概率分布形式来削减计算量。

优点：简单直观，代数上的消去对应图中结点的消去。

缺点：针对不同证据变量会造成大量冗余计算。

信念传播（belief propagation）

思路：将变量消去过程中产生的中间结果视为可复用的消息，避免重复计算。

消息传递仅在邻接变量之间发生，与边的方向性无关。

树结构：有向树=无向树

树结构上的消息传递：

消息计算公式：

边际分布：

二次扫描算法：

• 指定一个根结点，从所有叶结点开始向根节点传递消息，直到根结点收到所有邻接结点的消息。
• 从根结点开始向叶结点传递消息，直到所有叶结点均收到消息。

近似推断

近似推断：在较低的时间复杂度下获得原问题的近似解。通过采样一组服从特定分布的样本，来近似原始分布，适用范围更广，操作性更强。

前向采样（forward sampling）

思路：依据贝叶斯网络的（条件）概率直接采样。采样后，进行需要的概率统计。

缺点：对于小概率事件采样困难，可能经过很多次采样也无法获得足够多的样本

仅适用于贝叶斯网络，不适用于马尔可夫随机场。

吉布斯采样（Gibbs sampling）

思路：直接依照条件概率采样。

马尔可夫毯的性质：

优点：

• 直接从采样，解决小概率事件采样难的问题
• 同时适用于贝叶斯网络和马尔可夫随机场
• 简单易推导，时间复杂度低。

实例模型

隐马尔可夫模型

隐马尔可夫模型是关于时序的概率模型，是最简单的动态贝叶斯网络模型。

状态变量 表示第 时刻的系统状态，观测变量 表示第 时刻的观测值。

观测变量仅依赖于当前时刻的状态变量，当前状态仅依赖于前一时刻的状态。状态集合 ，观测值集合

联合概率：

状态转移矩阵，其中表示 时刻处于状态 的条件下， 时刻转移到状态 的概率

观测概率矩阵，其中表示 时刻处于状态 的条件下观测到 的概率

初始状态概率向量 ，其中表示系统初始状态为的概率。

生成过程：

给定 ，生成观测序列

1. 设置，并根据初始状态概率生成初始状态
2. 根据和观测概率矩阵B生成
3. 根据和状态转移矩阵A 生成
4. 若，则设置，并转到第（2）步；否则，停止。

三个基本问题

• 概率计算问题：给定模型和观测序列，计算在模型下观测到的概率。（评估模型与观测序列之间的匹配程度）
• 直接计算法：给定模型和观测序列，求使得最大的状态观测序列。（根据观测序列推测状态序列）
• 学习问题：给定观测序列，调整模型参数，使得该序列出现的概率最大。（训练模型使其更好地描述观测序列）

条件随机场

条件随机场(Conditional Random Field) 是给定随机变量的条件下，随机变量的马尔可夫随机场。是中的随机变量构成的无向图，图中每个变量在给定的条件下都满足马尔可夫性：

线性链条件随机场(linear-chain CRF)是随机变量为线性链时的条件随机场

是观测序列。 是标记序列（或称状态序列 )，在给定的条件下，的条件分布构成条件随机场。