1 隐马尔可夫模型

机器学习的主要任务是根据一些已观察到的证据来对感兴趣的未知变量进行估计和推测。概率模型提供了描述框架，将学习任务归结于计算变量的概率分布。

推断：在概率模型中，利用已知变量推测未知变量的分布，核心是如何基于可观测变量推测出未知变量的条件分布。假定所关心的变量集合为Y，可观测变量集合为O，其他变量的集合为R。

概率图模型是一类用图来表达变量相关关系的概率模型，图中用一个结点表示一个或一组随机变量，结点之间的边表示变量间的概率相关关系。概率图模型大致分为两类：

• 有向图模型或贝叶斯模型：使用有向无环图表示变量间的依赖关系。
• 无向图模型或马尔可夫图：使用无向图表示变量间的相关关系。

隐马尔可夫模型（HMM）是结构最简单的动态贝叶斯网，是一种著名的有向图模型。图结构如下图：

隐马尔可夫模型中的变量分为两组：
一组是状态变量 { y 1 , y 2 , . . . , y n } \{y_1,y_2,...,y_n\} {y1​,y2​,...,yn​}，通常假定状态变量是隐藏的，不可被观测的，因此状态变量亦称隐变量。
一组是观测变量 { x 1 , x 2 , . . . , x n } \{x_1,x_2,...,x_n\} {x1​,x2​,...,xn​}，其中$x_i\in X$表示第i时刻的观测值，可以是离散型也可以是连续型。
上图中的箭头表示了变量间的依赖关系，任一时刻，观测变量的取值仅依赖于状态变量，由马尔可夫链表示。

系统下一时刻的状态仅由当前状态决定，不依赖于以往的任何状态. 基于这种依赖关系，所有变量的联合概率分布为
$$P(x_1,y_1,\dots ,x_n,y_n)=P(y_1)P(x_1\mid y_1)\prod _{i=2}^{n}P(y_i\mid y_{i-1})P(x_i\mid y_i).$$
欲确定一个隐马尔可夫模型还需以下三组参数

• 状态转移概率：模型在各个状态间转换的概率，通常记为矩阵$\mathbf{A}=$
  $[a_{ij}{]}_{N\times N}$,其中
  $$a_{ij}=P(y_{t+1}=s_j\mid y_t=s_i),1⩽i,j⩽N,$$
  表示在任意时刻$t$,若状态为$s_i$,则在下一时刻状态为$s_j$的概率
• 输出观测概率：模型根据当前状态获得各个观测值的概率，通常记为矩阵
  $\mathbf{B}=[b_{ij}{]}_{N\times M}$,其中
  $b_{ij}=P(x_t=o_j\mid y_t=s_i)$ , $1⩽i⩽N$ $,1⩽j⩽M$
  表示在任意时刻$t$,若状态为 $s_i$, 则观测值 $o_j$ 被获取的概率
• 初始状态概率：模型在初始时刻各状态出现的概率，通常记为$\pi =({\pi }_1,{\pi }_2,\dots ,{\pi }_N)$,·其中
  $${\pi }_i=P(y_1=s_i),1⩽i⩽N$$
  表示模型的初始状态为$s_i$的概率。

给定隐马尔可夫模型$\lambda$，按如下过程产生观测序列

1. 设置t=1，根据初始状态概率$\pi$选择初始状态$y_1$
2. 根据状态$y_1$和输出观测概率B选择观测变量取值$x_t$
3. 根据状态$y_t$和状态转移矩阵A转移模型状态，确定$y_{t+1}$
4. 若t<n，设置t=t+1，并且转到第2步，否则停止

隐马尔可夫模型有三个基本问题：
1.如何评估模型与观测序列之间的匹配程度？
2.如何根据观测序列推断出隐藏的模型状态？
3.如何训练模型使其能最好地描述观测数据？

2 马尔可夫随机场

马尔可夫随机场是典型的马尔可夫网（无向图模型），每个结点表示一个或一组变量，结点之间的边表示两个变量之间的依赖关系。马尔可夫随机场有一组势函数（因子），这是定义在变量子集上的非负实函数，用于定义概率分布函数。

下图是一个简单的马尔可夫随机场，
团：图中结点的一个子集，若其中任意两结点间都有边连接，称该结点子集为一个团。
极大团：一个团中加入另外任何一个结点都不再形成团。

所有团构成的集合为C，联合概率P(x)定义为
$P(x)=\frac{1}{Z}\prod {\psi }_Q(x_Q)$

其中${\psi }_Q$为与团Q对应的势函数，用于对团Q中的变量关系进行建模，$Z={\sum }_x\prod {\psi }_Q(x_Q)$为规范化因子，来确保$P(x)$是被正确定义的概率。

马尔可夫随机场借助分离来得到条件独立性，若结点集A中的结点到B中的结点都必须经过结点集C中的结点，则称结点集A和B被结点集C分离。

对马尔可夫随机场，有

• 全局马尔可夫性：给定两个变量子集的分离集，则称两个变量子集条件独立。
• 局部马尔可夫性：给定某变量的邻接变量，则该变量条件独立于其他变量。
• 成对马尔可夫性：给定所有其他变量，两个非邻接变量条件独立。

势函数的作用是定量刻画变量集中变量自建的相关关系，应该是非负函数，且在所偏好的变量取值上有较大函数值。为了满足非负性，指数函数常被用于定义势函数，即${\psi }_Q(x_Q)=e^{-H_Q(x_Q)}$

$H_Q({\mathbf{x}}_Q)$是一个定义在变量 ${\mathbf{x}}_Q$上的实值函数,常见形式为${H}_Q({\mathbf{x}}_Q)={\sum }_{u,v\in Q,u\ne v}{\alpha }_{uv}{x}_u{x}_v+{\sum }_{v\in Q}{\beta }_v{x}_v$,

3 条件随机场

条件随机场是一种判别式无向图模型，判别式模型是对条件分布进行建模。

条件随机场试图对多个变量在给定观测值后的条件概率进行建模。具体来说，若令 x = { x 1 , x 2 , … , x n } \mathbf{x}=\{x_1,x_2,\ldots,x_n\} x={x1​,x2​,…,xn​}为观测序列 , y = { y 1 , y 2 , … , y n } ,\mathbf{y}=\{y_1,y_2,\ldots,y_n\} ,y={y1​,y2​,…,yn​}为与之相应的标记序列，则条件随机场的目标是构建条件概率模型$P(\mathbf{y}\mid\mathbf{x}).

最常用的是如下图的链式条件随机场：

条件随机场使用势函数和图结构上的团来定义条件概率$P(y|x)$，
在条件随机场中,通过选用指数势函数并引入特征函数, 条件概率被定义为$P(\mathbf{y}\mid \mathbf{x})=\frac{1}{Z}\exp \left({\sum }_j{\sum }_{i=1}^{n-1}{\lambda }_j{t}_j(y_{i+1},y_i,\mathbf{x},i)+{\sum }_k{\sum }_{i=1}^n{\mu }_k{s}_k(y_i,\mathbf{x},i)\right)$ ,
$t_j$是定义在观测序列的两个相邻标记位置上的转移特征函数，用于刻画相邻标记变量之间的相关关系以及观测序列对他们的影响，$s_k$是定义在观测序列的标记位置i上的状态特征函数，用于刻画观测序列对标记变量的影响。
条件随机场处理的是条件概率，马尔可夫随机场处理的是来拟合概率。

4 学习与推断

基于概率图模型定义的联合概率分布，能对目标变量的边际分布或以某些可观测变量为条件分布进行推断。

边际分布：对无关变量求和或积分后得到的结果。
边际化：给定参数$\Theta$求解某个变量x的分布，变成对联合分布中其他无关变量进行积分的过程。

推断问题的关键是如何高效计算边际分布，即
$P({\mathbf{x}}_E)={\sum }_{{\mathbf{x}}_F}P({\mathbf{x}}_E,{\mathbf{x}}_F)$

推断方法大致分为两类：
第一类是精确推断方法，希望能计算出目标变量的边际分布或条件分布的精确值。
第二类是近似推断方法，希望在较低的时间复杂度获得原问题的近似解。

4.1 变量消去

精确推断实质是一类动态规范算法，利用图模型所描述的条件独立性来削减计算目标概率值所需的计算量。

通过利用乘法对加法的分配律，变量消去法把多个变量的积的求和问题，转化为对部分变量交替进行求积与求和的问题，简化了计算。

缺点：若需计算多个边际分布，重复使用变量消去法将会造成大量的冗余计算。

4.2 信念传播

该算法将变量消去法中的求和操作看作一个消息传递过程，较好地解决了求解多个边际分布时的重复计算问题。变量消去法通过求和操作$$m_{ij}(x_j)=\sum _{x_i}\psi (x_i,x_j)\prod _{k\in n(i)\setminus j}{m}_{ki}(x_i)$$
消去变量$x_i$,其中$n(i)$表示结点$x_i$的邻接结点.

该算法中，一个结点仅在接收到来自其他所有结点的消息后才能向另一个结点发送消息，且结点的边际分布正比于它所接收的消息的乘积，即
$$P(x_i)\propto \prod _{k\in n(i)}{m}_{ki}(x_i).$$

当图结构没有环，信念传播算法经过两个步骤可完成所有消息传递，从而计算所有变量上的边际分布：
1.指定一个根结点,从所有叶结点开始向根结点传递消息,直到根结点收到所有邻接结点的消息。
2.从根结点开始向叶结点传递消息,直到所有叶结点均收到消息。

5 近似推断

近似推断大致分为两大类：
第一类是采样，通过使用随机化方法完成近似。
第二类是使用确定性近似完成近似推断，典型代表为变分推断。

5.1 MCMC采样

采样法是基于概率分布来计算期望，可能进一步基于这些期望做出决策。假定目标是计算函数$f(x)$在概率密度函数$p(x)$下的期望
${\mathbb{E}}_p[f]=\int f(x)p(x)dx$

则可根据$p(x)$抽取一组样本 { x 1 , x 2 , … , x N } \{x_1,x_2,\ldots,x_N\} {x1​,x2​,…,xN​},然后计算$f(x)$在这些样本上的均值

$\hat{f}=\frac{1}{N}{\sum }_{i=1}^{N}f(x_i)$ ,

以此来近似目标期望$\mathbb{E}[f]$。

对概率图模型，问题的关键是如何高效地基于图模型所描述的概率分布来获取样本。最常用的采样技术是马尔科夫链蒙特卡洛。

给定连续变量$x\in X$的概率密度函数$p(x)$,
$x$在区间$A$中的概率可计算为
$$P(A)={\int }_{A}p(x)dx.$$
若有函数$f:X\mapsto \mathbb{R}$,则可计算$f(x)$的期望
$$p(f)={\mathbb{E}}_p\left[f(X)\right]={\int }_{x}f(x)p(x)dx.$$

MCMC方法的关键在于通过构造平稳分布为p的马尔可夫链来产生样本：若马尔可夫链运行时间足够常，则此时产出的样本x近似服从于分布p。
判断马尔可夫链到达平稳状态，MCMC方法先设法构造一条马尔科夫链，使其收敛至平稳分布恰为待估计参数的后验分布，然后通过这条马尔可夫链来产生符合后验分布的样本，并基于这些样本来进行估计。
吉布斯采样被视为MH算法的特例，使用马尔科夫链获取样本，通过循环执行以下步骤完成采样：
1.随机或以某个次序选取某变量$x_i$
2.根据X中除$x_i$外的变量的现有取值，计算条件概率$p(x_i|X)$
3.根据$p(x_i|X)$对变量$x_i$采样，用采样值代替原值

5.2 变分推断

通过使用已知简单分布来逼近需推断的复杂分布，通过限制近似分布的类型，从而得到一种局部最优，但具有确定解的近似后验分布。

盘式记法如下图：
相互独立的，由相同机制生成的多个变量放在一个方框内，在方框中标出类似变量重复出现的个数N。

所有能观察到的变量x的联合分布的概率密度函数是
$$p(\mathbf{x}\mid \Theta )=\prod _{i=1}^N\sum _{\mathbf{z}}p(x_i,\mathbf{z}\mid \Theta )$$

所对应的对数似然函数为 ln ⁡ p ( x ∣ Θ ) = ∑ i = 1 N ln ⁡ { ∑ z p ( x i , z ∣ Θ ) } \\\ln p(\mathbf{x}\mid\Theta)=\sum_{i=1}^{N}\ln\left\{\sum_{\mathbf{z}}p(x_{i},\mathbf{z}\mid\Theta)\right\} lnp(x∣Θ)=∑i=1N​ln{∑z​p(xi​,z∣Θ)}

概率模型的参数估计通常以最大化对数似然函数为手段。使用变分法，最重要的是考虑如何对隐变量进行拆解，以及假设各变量子集服从何种分布，若隐变量的拆解或变量子集的分布假设不当，会导致变分法效率低，效果差。

6 话题模型

话题模型是一族生成式有向图模型，用于处理离散型数据。隐狄利克雷分配模型是话题模型的典型代表。

以下介绍几个概念：

• 词：待处理数据的基本离散单元。
• 文档：待处理的数据对象，由一组词组成，这些词在文档中不计顺序。
• 话题：表示一个概念，具体表述为一系列相关的词，以及它们在该概念下出现的概率。

现实任务中可通过统计文档中出现的词来获得词频向量，LDA从生成式模型的角度来看待文档和话题。具体步骤如下：

• 1.根据参数为$\alpha$的狄利克雷分布随机采样一个话题分布${\Theta }_t;$

• 2.按如下步骤生成文档中的$N$个词
  (a)根据${\Theta }_t$进行话题指派，得到文档 $t$ 中词 $n$ 的话题 $z_{t,n}$。
  (b) 根据指派的话题所对应的词频分布${\beta }_k$随机采样生成词。

LDA模型对应的概率分布为：
$\begin{array}{rlr}& p(\mathbf{W},\mathbf{z},\beta ,\Theta \mid \mathbf{\alpha },\mathbf{\eta })=& \\ & \prod _{t=1}^{T}p({\Theta }_t\mid \mathbf{\alpha })\prod _{i=1}^{K}p({\mathbf{\beta }}_k\mid \mathbf{\eta })\left(\prod _{n=1}^{N}P(w_{t,n}\mid z_{t,n},{\mathbf{\beta }}_k)P(z_{t,n}\mid {\Theta }_t)\right),& \\ & & \\ & p({\Theta }_t\mid \alpha )=\frac{\Gamma ({\sum }_k{\alpha }_k)}{{\prod }_k\Gamma ({\alpha }_k)}\prod _k{\Theta }_{t,k}^{{\alpha }_k-1},& \text{2}\end{array}$

给定训练数据 W = { w 1 , w 2 , … , w T } \mathbf{W}=\{\boldsymbol{w}_1,\boldsymbol{w}_2,\ldots,\boldsymbol{w}_T\} W={w1​,w2​,…,wT​}, LDA 的模型参数可通过极大似然
法估计，即寻找$\alpha$和$\eta$以最大化对数似然

$$LL(\mathbf{\alpha },\mathbf{\eta })=\sum _{t=1}^T\ln p({\mathbf{w}}_t\mid \mathbf{\alpha },\mathbf{\eta }).$$

若模型已知，即参数$\alpha$和$\eta$已确定，则根据词频$w_{t,n}$来推断文档集所对应
的话题结构(即推断 ${\Theta }_t,{\beta }_k$ 和 $z_t,n)$可通过求解
$$p(\mathbf{z},\mathbf{\beta },\Theta \mid \mathbf{W},\mathbf{\alpha },\mathbf{\eta })=\frac{p(\mathbf{W},\mathbf{z},\mathbf{\beta },\Theta \mid \mathbf{\alpha },\mathbf{\eta })}{p(\mathbf{W}\mid \mathbf{\alpha },\mathbf{\eta })}.$$

实践中常采用吉布斯采样或变分法进行近似推断。