机器学习.周志华《14概率图模型》

目录

思维导图转载自&＃xff1a;https://blog.csdn.net/liuyan20062010/article/details/72842007

导入&＃xff1a;

机器学习的核心价值观&＃xff1a;根据一些已观察到的证据来推断未知。其中基于概率的模型将学习任务归结为计算变量的概率分布&＃xff1b;

生成式模型&＃xff1a;先对联合分布P(Y,R,O)进行建模&＃xff0c;从而再来求解后验概率&＃xff0c;例如&＃xff1a;贝叶斯分类器先对联合分布进行最大似然估计&＃xff0c;从而便可以计算类条件概率&＃xff1b;

判别式模型:直接对条件分布P(Y,R|O)进行建模。

推断&＃xff1a;利用已知变量推测未知变量&＃xff1b;即由联合分布P(Y,R,O)或条件分布P(Y,R|O)推出条件概率分布P(Y,O)

概率图模型&＃xff08;probabilisticgraphical model&＃xff09;是一类用图来表达变量相关关系的概率模型。概率图模型&＃xff0c;以图为表示工具&＃xff0c;如一个结点表示一个或一组随机变量&＃xff0c;结点之间的边表示变量间的概率相关关系&＃xff0c;即变量关系图。

根据边的性质不同&＃xff0c;概率图模型大致可分为两类&＃xff1a;

1&＃xff09;使用有向无环图表示变量间的依赖关系&＃xff0c;称为有向图模型或贝叶斯网&＃xff08;Bayesian network&＃xff09;&＃xff1b;

2&＃xff09;使用无向图表示变量间的相关关系&＃xff0c;称为无向图模型或马尔可夫网&＃xff08;Markov network&＃xff09;&＃xff1b;

这里上一个概率图模型的思维导图&＃xff1a;

隐马尔科夫模型

统计学习方法里面的解释&＃xff1a;http://www.cnblogs.com/QueenJulia/articles/8940010.html

隐马尔可夫模型&＃xff08;Hidden Markov Model&＃xff0c;HMM&＃xff09;是结构最简单的动态贝叶斯网&＃xff08;dynamic Bayesian network&＃xff09;&＃xff0c;是著名的有向图模型&＃xff0c;主要用于时序数据建模&＃xff0c;在语音识别、自然语言处理等领域有广泛应用。

1&＃xff09;HMM结构信息

HMM的变量可分为两组&＃xff1a;

• 第一组是状态变量{y₁,y₂,…,y_n}&＃xff0c;其中y_i∈Y表示第i时刻的系统状态&＃xff0c;通常假定状态变量是隐藏的、不可观测的&＃xff0c;因此状态变量也叫隐变量&＃xff08;hidden variable&＃xff09;&＃xff1b;
• 第二组是观测变量{x₁,x₂,…,x_n}&＃xff0c;其中x_i∈X表示第i时刻的观测值。

在HMM中&＃xff0c;系统通常在多个状态{ s₁,s₂,…,s_N }之间转换&＃xff0c;因此状态变量y_i的取值范围Y&＃xff08;状态空间&＃xff09;通常是有N个可能取值的离散空间。观测变量x_i可以是离散型也可以使连续型&＃xff0c;这里仅考虑离散型观测变量&＃xff0c;并假定其取值范围X为{ o₁,o₂,…,o_M}。

HMM图结构如下&＃xff1a;

图中箭头表示了变量间的依赖关系。在任一时刻&＃xff0c;观测变量的取值仅依赖于状态变量&＃xff0c;即x_t由y_t确定&＃xff1b;与其他状态变量及观测变量的取值无关。t时刻的状态y_t仅依赖于t-1时刻的状态y_t-1&＃xff0c;与其余n-2个状态无关。此为马尔科夫链&＃xff08;Markov chain&＃xff09;&＃xff0c;即&＃xff1a;系统下一时刻的状态仅由当前状态决定&＃xff0c;不依赖于以往的任何状态。基于这种依赖关系&＃xff0c;所有变量的联合概率分布为&＃xff1a;

确定隐马尔科夫模型&＃xff1a;

• 状态变量Y
• 观测变量X

• 状态转移概率A

• 输出观测概率B

• 初始状态概率π

产生观测序列过程&＃xff1a;

实际应用中关注的三个问题&＃xff1a;

马尔科夫随机场

统计学习方法中的解释&＃xff1a;http://www.cnblogs.com/QueenJulia/articles/8940012.html

马尔科夫随机场是典型的马尔科夫网&＃xff0c;无向图模型&＃xff1a;

势函数&＃xff08;因子&＃xff09;&＃xff1a;

定义在变量子集上的非负实函数&＃xff0c;主要用于定义概率分布函数或者说用定量刻画变脸记Xq中半年之间的相关关系&＃xff1b;且在所骗号的变量取值上有较大的函数值&＃xff1b;

团:

图中结点的一个子集中&＃xff0c;若其中任意两结点都有边连接&＃xff0c;则该结点子集为一个“团&＃xff1b;”

极大团&＃xff1a;

若在一个团中加入另外任何一个节点都不再构成团&＃xff0c;该团为“极大团”&＃xff1b;

联合概率&＃xff08;基于团定义&＃xff09;&＃xff1a;

联合概率&＃xff08;基于极大团定义&＃xff09;

注&＃xff1a;

若团Q不是极大团&＃xff0c;则必被一个极大团Q*所包含&＃xff1b;

分离集&＃xff1a;

得出&＃xff1a;

条件随机场CRF

定义&＃xff1a;

若G&＃61;表示结点与标记变量y中元素一一对应的无向图&＃xff0c;yv表示与结点v的标记变量&＃xff0c;n(v)表示结点v的邻接结点&＃xff0c;若图G的每个变量yv都满足马尔可夫性&＃xff0c;则&＃xff08;y&＃xff0c;x&＃xff09;构成一个条件随机场。

马尔可夫性&＃xff1a;

链式条件随机场chain-structured CRF:

条件概率

转移特征函数&＃xff1a;刻画相邻标记变量之间的相关关系以及观测序列对他们的影响&＃xff1b;

• 主要判定两个相邻的标注是否合理&＃xff0c;例如&＃xff1a;动词&＃43;动词显然语法不通&＃xff1b;

状态特征函数&＃xff1a;刻画观测序列对标记变量的影响&＃xff1b;

• 主要判定观测值与对应的标注是否合理&＃xff0c;例如&＃xff1a; ly结尾的词–>副词较合理。

学习与推断

边际化&＃xff1a;

概率图模型的推断方法大致分为两类&＃xff1a;

1. 精确推断方法&＃xff1a;变量消去、信念传播&＃xff1b;
2. 近似推断方法&＃xff1a;MCMC采样、变分推断&＃xff1b;

精确推断

精确推断的实质是一种动态规划算法&＃xff0c;他利用图模型所描述的条件独立性来削减计算目标概率值所需的计算量。

变量消去

&＃xff08;1&＃xff09;有向图模型&＃xff1a;

&＃xff08;2&＃xff09;对无向图同样适用&＃xff01;

缺点&＃xff1a;

• 若需要计算多个边际分布&＃xff0c;重复使用变量消去会造成大量的冗余计算。

信念传播

解决求解多个边际分布的重复计算问题&＃xff1a;将变量消去法中的求和操作看做一个消息传递的过程&＃xff1b;

信念传播算法步骤&＃xff1a;

信念传播算法图示&＃xff1a;

近似推断

两大类方法&＃xff1a;

• 采样&＃xff1a;采用随机化方法完成近似&＃xff1b;
• 确定性近似&＃xff1a;典型代表变分推断&＃xff1b;

采样

可以参考的博客&＃xff1a;https://www.cnblogs.com/ironstark/p/5229085.html

典型代表&＃xff1a;马尔科夫链蒙特卡罗MCMC

目的&＃xff1a;通过构造‘平稳分布为p的马尔科夫链’来产生样本&＃xff1b;

平稳分布&＃xff1a;假设平稳马尔科夫链T的状态转移概率为T&＃xff08;x&＃39;|x&＃xff09;&＃xff0c;t时刻状态的分布为P&＃xff08;x^t&＃xff09;,则若在某个时刻马尔科夫链满足平稳条件&＃xff1a;

则p&＃xff08;x&＃xff09;是该马尔科夫链的平稳分布

步骤&＃xff1a;

1. 构造马尔科夫链&＃xff1b;
2. 逼近&＃xff08;收敛&＃xff09;至平稳分布恰为带估计参数的后验分布&＃xff1b;
3. 用马尔科夫链产生符合该后验分布的样本&＃xff0c;并基于这些样本进行估计

重点&＃xff1a;马尔科夫链转移概率的构造

MH&＃xff08;MCMC代表&＃xff09;&＃xff1a;基于“拒绝采样”来逼近平稳分布p&＃xff1b;

MC算法特例&＃xff1a;吉布斯采样

变分推断

附变分推断的知乎讨论&＃xff1a;https://www.zhihu.com/question/41765860

目标&＃xff1a;通过使用已知简单分布来逼近需推断的复杂分布&＃xff0c;并通过限制及时发布的类型&＃xff0c;从而得到一种局部最优、但具有确定街的近似后验分布。

盘式记忆&＃xff1a;

(b)中所能观测到的变量x的联合分布的概率密度函数&＃xff1a;

对应的对数似然函数&＃xff1a;

推断和学习的任务&＃xff1a;

由观察到的变量x来估计隐变量z和分布参数变量Θ&＃xff0c;即求解P(z|x,Θ)

解决方法&＃xff1a;

EM算法

总结&＃xff1a;

1、如何拆解隐变量&＃xff1b;

2、假设各变量子集服从的分布&＃xff1b;

3、服从的最优分布&＃xff1b;

4、EM算法&＃xff1b;

话题模型

生产式有向图模型&＃xff0c;主要处理离散型数据&＃xff08;如文本集合&＃xff09;。

隐狄利克雷分配模型&＃xff08;Latent Dirichlet Allocation&＃xff0c;简称LDA&＃xff09;

基本概念&＃xff1a;词&＃xff08;word&＃xff09;、文档&＃xff08;document&＃xff09;、话题&＃xff08;topic&＃xff09;。

词&＃xff1a;最基本的离散单元&＃xff1b; 
文档&＃xff1a;待处理的数据对象&＃xff0c;由一组词组成&＃xff0c;词在文档中不计顺序&＃xff1b;&＃xff08;词袋bag-of-words&＃xff09; 
话题&＃xff1a;表示一个概念&＃xff0c;具体表现为一系列相关的词&＃xff0c;以及它们该概念下出现的概率。这组词具有较强的相关关系。

在现实任务中&＃xff0c;一般我们可以得出一个文档的词频分布&＃xff0c;但不知道该文档对应着哪些话题&＃xff0c;LDA话题模型正是为了解决这个问题。

具体来说&＃xff1a;LDA认为每篇文档包含多个话题&＃xff0c;且其中每一个词都对应着一个话题。因此可以假设文档是通过如下方式生成&＃xff1a;

这样一个文档中的所有词都可以认为是通过话题模型来生成的&＃xff0c;当已知一个文档的词频分布后&＃xff08;即一个N维向量&＃xff0c;N为词库大小&＃xff09;&＃xff0c;则可以认为&＃xff1a;每一个词频元素都对应着一个话题&＃xff0c;而话题对应的词频分布则影响着该词频元素的大小。

LDA变量关系&＃xff1a;

因此很容易写出LDA模型对应的联合概率函数&＃xff1a;

补充&＃xff1a;

从上图可以看出&＃xff0c;LDA的三个表示层被三种颜色表示出来&＃xff1a;

corpus-level&＃xff08;红色&＃xff09;&＃xff1a; α和β表示语料级别的参数&＃xff0c;也就是每个文档都一样&＃xff0c;因此生成过程只采样一次。 
document-level&＃xff08;橙色&＃xff09;&＃xff1a; θ是文档级别的变量&＃xff0c;每个文档对应一个θ。 
word-level&＃xff08;绿色&＃xff09;&＃xff1a; z和w都是单词级别变量&＃xff0c;z由θ生成&＃xff0c;w由z和β共同生成&＃xff0c;一个单词w对应一个主题z。

通过上面对LDA生成模型的讨论&＃xff0c;可以知道LDA模型主要是想从给定的输入语料中学习训练出两个控制参数α和β&＃xff0c;当学习出了这两个控制参数就确定了模型&＃xff0c;便可以用来生成文档。其中α和β分别对应以下各个信息&＃xff1a;

α&＃xff1a;分布p(θ)需要一个向量参数&＃xff0c;即Dirichlet分布的参数&＃xff0c;用于生成一个主题θ向量&＃xff1b; 
β&＃xff1a;各个主题对应的单词概率分布矩阵p(w|z)。

把w当做观察变量&＃xff0c;θ和z当做隐藏变量&＃xff0c;就可以通过EM算法学习出α和β&＃xff0c;求解过程中遇到后验概率p(θ,z|w)无法直接求解&＃xff0c;需要找一个似然函数下界来近似求解&＃xff0c;原作者使用基于分解&＃xff08;factorization&＃xff09;假设的变分法&＃xff08;varialtional inference&＃xff09;进行计算&＃xff0c;用到了EM算法。每次E-step输入α和β&＃xff0c;计算似然函数&＃xff0c;M-step最大化这个似然函数&＃xff0c;算出α和β&＃xff0c;不断迭代直到收敛。