马尔可夫链

随机过程

概率论的研究对象是静态的随机现象，而随机过程的研究对象是随时间演变的随机现象（天气随着时间的变化）。在随机过程中，随机现象在某时刻的取值用表示，所有可能的状态组成状态集合。

马尔可夫性质

当且仅当某时刻的状态只取决于上一个时刻的状态时，一个随机过程被称为具有马尔可夫性质。更系统地，当前状态是未来的充分统计量，而不会受到过去状态的影响。但是这并不代表和历史完全没有关系，实际上当前状态也受到了上一状态的影响，正是通过这种链式关系将历史信息的影响传递到了现在。显然，这一性质可以大大简化计算。

数学表达如下：

马尔可夫过程

又叫马尔可夫链，即满足马尔可夫性质的随机过程，通常用一个有限状态集合和一个状态转移矩阵来表示。直观地，马尔可夫链可以看作一个有向图，其中每条边的权值表示从发出状态到接受状态之间的转移概率，所以状态转移矩阵其实可以说是邻接矩阵。

静态分布

马尔可夫链在长时间运行后达到的一种稳定状态的概率分布。直观地，假设静态分布为 ，意味着经过足够长的时间后，系统状态的分布不再变化且每个状态出现的概率为。

为什么

假设状态转移矩阵为， 表示状态到且恰好经过步的概率

随着步数的增加，初始状态的影响越来越小，最终整个系统的行为只由转移该来本身决定。所以转移矩阵在经过多次幂运算后逐渐趋于稳定，如下式子所示。每一行都是正态分布，所以无论起点如何（处于矩阵的那一行），在经过足够长的时间后（)，落到所有状态的概率都是固定的（每一列的取值都相等）。

前提条件

当然，静态分布并不是在所有情况下都成立，需要满足以下条件

  • 可约性，所有状态必须是互相到达的
  • 无周期性，不会被卡在循环内

也就是说，满足静态分布性质的马尔可夫链所构成的图是一个无环的强连通图。

用于文本生成任务

上面提到的状态可以表示为文本中的词，根据马尔可夫性质，仅通过当前词来预测下一个词。

一种比较简单的想法为，在大量样本数据上学习到各个词语之间的转移概率，从给定起始词出发进行随机漫步从而达到生成文本的效果。虽然生成的文本大多数是无意义的，但是大多数都是语法正确的。因为语法成分具有很强的前后依赖关系，比如形容词后大多是名词，名词后大多是动词等。

隐马尔可夫模型

介绍

HMM 是一种可用于标注任务的机器学习模型，描述由隐藏的马尔可夫链随机生成观测序列的过程，属于生成模型。

HMM 包含 隐藏的即不可观测的序列 和 可观测序列，隐藏序列具有 马尔可夫性质，即当前状态仅有上一状态决定。其中，可观测序列仅由当前的隐藏状态决定，模型的目标是通过可观测序列找到最有可能的隐藏状态序列。实际上，刚才的的描述已经了包含了 HMM 的两个关键假设，即 马尔可夫假设和观测独立性假设。

模型描述

包含隐藏状态集合，观测状态集合，初始概率，转移概率和发射概率。初始概率即为稳态分布，发射概率即为从隐藏状态到观测状态的概率。

序列标注

解释性

在标注任务中，可观测序列就是文本，隐藏状态序列就是所求的标签。我们有充分理由认为，当前词的词性或者槽仅有前一个词的词性或者槽标签决定，也就是说马尔可夫假设是有说服力的。在语料库中，我们也可以学习到各词性或者槽标签出现最多的词是哪些，所以发射概率是可求的。

  • 转移概率：描述了”上一个标签是什么，接下来可能是什么标签”
  • 发射概率：描述了“这个标签下，出现这个观测值的可能性”
具体应用

  • 首先，从语料库中学习到不同词性或者槽标签的之间的转移概率，再通过这个概率求出稳态分布

  • 其次，统计各个词性或者槽标签下出现某词的概率即发射概率

有了这三个概率后，就可以根据给定的 观测值即输入序列 得到 隐藏状态序列即标签序列，假设为可观测序列，为隐藏状态序列，对问题进行概率建模，再利用贝叶斯定理进行展开。

维特比算法

本质是一种动态规划算法，将全局问题分解为最优子问题，并且子问题的最优解能够推导出全局问题的最优解。在 HMM 中，维特比算法遵循了这个思想：每一个时刻的最优状态序列是基于前一个时刻的最优状态序列推导出来的。

参数说明：

  • 为初始概率

  • 到的转移概率

  • 表示生成观测值的发射概率

状态定义：

  • 时间时到达的最大概率
  • 记录上一时刻的状态，用于回溯找出路径

状态转移矩阵：

路径回溯：

最大熵马尔可夫模型

背景

HMM 的缺陷

在 HMM 中提到，HMM 解决的任务的需要满足 马尔可夫假设 和 观测独立性建设。在序列标注任务中，马尔可夫假设是很有说服力的，即当前标签仅跟标签仅跟上一个标签有关，不需要更早的标签。

但是观测独立性假设意味着，观测值只依赖于当前隐藏状态，虽然有一定的可解释性，但过于简单并不能自由地利用上下文信息。在实际情况中，往往需要更多的特征。HMM并不能很好的利用丰富特征

最大熵原理

最大熵思想是一种在已知信息下进行建模时尽量少做无谓假设的原则。核心观点是：在所有满足已知约束条件的概率分布中，选取熵最大的分布。

在序列建模上的应用：对于多种复杂特征，我们并不知道哪些特征能够更好的辅助预测当前词性，所以做出最无偏的估计，最大化不确定性，保留最大的可能性空间，最大程度上避免引入不必要的假设。

数学形式

熵定义为： 最大熵建模的目标是在满足某些约束的前提下，最大化分布的熵。

求最值的方法：

已知目标函数和约束条件，可以通过构造拉格朗日函数的方法来求极值。

设目标函数为，约束条件为，构造拉格朗日函数为：

分别对求偏导建立方程组，通过消去求解

模型结构

MEMM的基本思想是：在当前状态下，使用最大熵模型计算下一个状态的条件概率。

给定观测序列，预测标签序列为，条件概率可以建模为： 其中，为特征函数，为特征权重，是归一化因子

评价

HMM vs MEMM
  • 在HMM中，我们直接对整个序列建模联合概率，有从状态到观测的生成过程，属于生成式模型。
  • 在MEMM中，是对每一步的条件概率的建模，并使用最大熵模型预测，属于判别式模型。
优点

灵活加入任意特征，通过最大化不确定性来避免主观假设，还降低过拟合风险。这是MEMM相对于HMM的巨大优势，它可以把当前观测的各种特征（比如词本身、词根、词缀、大小写、是不是数字、前后词是什么等）都作为线索，帮助预测当前词性。HMM则很难利用这么多交叉重叠的特征。

标注偏见

标注偏见问题的本质是：转移概率是在每个当前状态下局部归一化的，模型只能在当前状态下对下一状态做局部最优决策，无法评估整个路径的最优性。虽然 MEMM 相比 HMM 引入了更多特征，提高了对观测数据的建模能力，但在结构上仍然采用局部归一化策略，导致容易偏向那些“出口较少”的状态（即容易集中概率的路径），从而忽略全局更优的路径选择。