# [白话解析]用水浒传为例学习最大熵马尔科夫模型
## 0x00 摘要
本文将尽量使用易懂的方式，尽可能不涉及数学公式，而是从整体的思路上来看，运用感性直觉的思考来解释最大熵马尔可夫模型。并且从名著中找了个具体应用场景来帮助大家深入这个概念。
在机器学习过程中，会遇到很多晦涩的概念，相关数学公式很多，大家理解起来很有困难。遇到类似情况，我们应该多从直觉角度入手思考，用类别或者举例来**附会**，这样往往会有更好的效果。
我在讲解论述过程中给自己的要求是：在生活中或者名著中找一个例子，然后用自己的话语阐述出来。
## 0x01 背景
在前文[[白话解析\]以水浒传为例学习隐马尔可夫模型](https://www.cnblogs.com/rossiXYZ/p/12430955.html)中，我们用 "梁中书突围大名府为例" 讲解了隐马尔可夫模型，但是现实中情况可能更复杂，比如梁中书突围遇到了宋江，他再次选择从宋江处突围的可能性会变低，因为宋江身边肯定是梁山大部分好汉，突围难度太大。但是如果遇到史进，危险性就没有那么大了。
这种情况只用隐马尔科夫模型就很难解决，需要引入最大熵马尔可夫模型了。
最大熵马尔可夫模型（Maximum Entropy Markov Model，MEMM）的思想把HMM和最大熵结合起来，可以提取特征以泛化模型能力，结合上下文依赖，直接判别减少建模负担。下面就来详述。
### 1. 隐马尔科夫模型的缺点
HMM是一种生成模型，定义了联合概率分布，其中y和x分别表示观察序列和相对应的标注序列的随机变量。为了能够定义这种联合概率分布，生成模型需要枚举出所有可能的观察序列，这在实际运算过程中很困难的，因此我们需要将观察序列的元素看作是彼此孤立的个体，即假设每个元素彼此独立，任何时刻的观察结果只依赖于该时刻的状态。
目标函数和预測目标函数不匹配，HMM学到的是状态和观察序列的联合分布P(Y,X)，而预測问题中，我们须要的是条件概率P(Y|X)。HMM必须计算出所有的潜在可能路径的概率值大小（然后再挑概率值最大的那一个作为最终结果）
HMM仅仅依赖于每个状态和它相应的观察对象，但是对于某一个观测值，它可能并非由一个隐藏状态决定的，而是两个以上的隐藏状态综合作用而产生的，那么这时HMM就无能为力了。
HMM模型的这个假设前提是在比较小的数据集上是合适的，但实际上在大量真实的语料中观察序列更多的是一种多重交互特征形式表现，观察元素之间广泛存在长程相关性。在命名实体识别的任务中，由于实体本身结构所具有的复杂性，利用简单的特征函数往往无法涵盖所有的特性，这时HMM的假设前提使得它无法使用复杂特征（它无法使用多于一个标记的特征）。
### 2. 最大熵模型的特点
最大熵模型的优点：首先，最大熵统计模型获得的是所有满足约束条件的模型中信息熵极大的模型；其次，最大熵统计模型可以灵活地设置约束条件，通过约束条件的多少可以调节模型对未知数据的拟合程度；再次，他还能自然地解决了统计模型中参数平滑的问题。
最大熵模型的不足：首先，最大熵统计模型中二值化特征只是记录特征的出现是否，而文本分类需要知道特征的强度，因此，它在分类方法中不是最优的。其次，由于算法收敛的速度比较慢，所以导致最大熵模型它的计算代价比较大，时空开销大；再次，数据稀疏问题比较严重。
最大熵模型可以使用任意的复杂相关特征，在性能上最大熵分类器超过了bayes分类器。但是，作为一种分类器模型，这两种方法有一个共同的缺点：每个词都是单独进行分类的，标记之间的关系无法得到充分利用。具有马尔可夫链的HMM模型可以建立标记之间的马尔科夫关联性，这是最大熵模型所没有的。所以一个很自然的想法就是将两者的优势结合起来，这就得到了最大熵马尔可夫模型。
### 3. MEMM的引入
最大熵马尔可夫模型（Maximum Entropy Markov Model，MEMM）的思想是利用 HMM 框架预测给定输入序列的序列标签，同时结合多项 Logistic 回归（又名最大熵，其给出了可以从输入序列中提取特征的类型和数量上的自由度）。这个模型允许状态转移概率依赖于序列中彼此之间非独立的 特征上，从而将上下文信息引入到模型的学习和识别过程中，提高了识别的精确度，召回率也大大的提高，有实验证明，这个新的模型在序列标注任务上表现的比 HMM和无状态的最大熵模型要好得多。
- MEMM解决了HMM输出独立性假设的问题。因为HMM只限定在了观测与状态之间的依赖，而MEMM引入自定义特征函数，不仅可以表达观测之间的依赖，还可表示**当前观测与前后多个状态之间**的复杂依赖；（ 这个复杂依赖是通过特征函数来做到的，比如该单词的 “前面单词/后面单词” 分别是什么 ）
- MEMM考虑到相邻状态之间依赖关系。且考虑整个观察序列，因此MEMM的表达能力更强；
- MEMM不考虑P(X)，减轻了建模的负担。同一时候学到的是目标函数是和预測函数一致；
HMM是生成式模型，参数即为各种概率分布元参数，数据量足够可以用最大似然估计。
而MEMM是判别式模型。是用函数直接判别，学习边界，MEMM即通过特征函数来界定。**这里由于去掉了独立性假设，所以不能给出联合概率分布，只能求后验概率，所以是判别模型**。但同样，MEMM也有极大似然估计方法、梯度下降、牛顿迭代、拟牛顿下降、BFGS、L-BFGS等等。
## 0x02 最大熵模型
因为HMM我们已经在前文了解，所以本文重点是最大熵模型的介绍。
### 1. Logistic 回归
通常，机器学习分类器通过从所有可能的 y_i 中选择有最大的 P(y|x) 的那个，来决定将哪个输出标签 y 分配给输入 x。在分类任务中，logistic 回归通过计算给定观察的属于每个可能类别的概率，然后选择产生最大概率的类别。
Logistic 回归是用于分类的一种监督学习算法，它的本质是线性回归。Logistic 回归用条件极大似然估计进行训练。这意味着我们将选择参数 w，使对给定输入值 x 在训练数据中 y 标签的概率最大化。通常可以运用随机梯度下降法、L-BFGS 或共轭梯度法来求此函数的最大值，即找到最优权重。
最大熵模型属于log-linear model，在给定训练数据的条件下对模型进行极大似然估计或正则化极大似然估计。
### 2. 最大熵原理
最大熵原理(Principle of Maximum Entropy)：将已知事实作为制约条件，求得可使熵最大化的概率分布作为正确的概率分布。而在机器学习里，就是如果没有数据说明，就不要随便为模型加假设。
最大熵原理的实质就是，在已知部分知识的前提下，关于未知分布最合理的推断就是：符合已知知识后 “最不确定或最随机的推断” 是我们可以作出的唯一不偏不倚的选择，任何其它的选择都意味着我们增加了其它的约束和假设，这些约束和假设根据我们掌握的信息无法作出。
例如，投掷一个骰子，如果问"每个面朝上的概率分别是多少"，你会说是等概率，即各点出现的概率均为1/6。因为对这个"一无所知"的色子，什么都不确定，而假定它每一个朝上概率均等则是最合理的做法。从投资的角度来看，这是风险最小的做法，而从信息论的角度讲，就是保留了最大的不确定性，也就是说让熵达到最大。
实践经验和理论计算都告诉我们，在完全无约束状态下，均匀分布等价于熵最大（有约束的情况下，不一定是概率相等的均匀分布。 比如，给定均值和方差，熵最大的分布就变成了正态分布 ）。
### 3. 最大熵模型
最大熵模型(Maximum Entropy Modeling) : 如果你有数据，请通过你的数据建立先验信息（在这里叫做约束条件），剩下的未知部分，请让他们均匀分布，也就是让他们的熵最大。
因为我们如果要搭建一个最大熵模型来实现分类，那么我们定义模型 p(y|x)，这个模型应该是：在 "满足事先已约束" 的条件下的模型中选择熵最大的模型，即让不确定的信息等可能的发生。这样我们就得到了最终的分类模型。
即，给定一个训练样本集，我们希望寻找一个分布符合如下两个条件(Given a set of training examples, we wish to find a distribution which)：
- 满足已知的约束条件（satisfies the input constraints）
- 最大化其不确定性（maximizes the uncertainty）
### 4. 已知的约束条件
#### 上下文 & 特征函数
我们做分类问题，看到的数据往往是每个实例对应一个类别。 比如说词性标注中一个词对应一个标注。 为了下面讨论的方便，将类别称为Outcome，将每个实例的上下文环境叫做Context。 实例被称为Event，一个实例是Outcome与Context的二元组。
比如，一个多维的向量x，x的每个维度都是一个特征，可以认为 x 对应了一个 Context（特征的集合）。然后这条样本对应了一个label（Outcome）。
问题就是数据并不是乖乖地排列好，x的每个维度都已经取好值等着我们分类了，所以出现了这个东西：特征函数。我们使用特征函数来表示约束条件，即 特征函数也就是用来指示元素是否属于某一个子集。
比如记 w 是句子 s 的某个单词，w是有很多维度的，则用来表示这些维度的特征函数可以是：
- w在句首
- w在句尾
- w的前缀是xxx
- w的后缀是xxx
- w前面的单词是xxx
可以看出，这些特征函数针对这个单词 w 的判别结果，就构成了 w 的上下文 Context。比如: w不在句首，w在句尾.....
#### 特征函数
给定一个训练数据集
$$
T = \{ (x_1, y_1), (x_2, y_2) ... (x_N, y_N) \}
$$
为了表示数据，我们从数据中抽取了一系列的特征。一般说的“特征”都是指输入的特征，而最大熵模型中的“特征”指的是输入和输出共同的特征。每个特征与每个类别都能组成一个特征，应该用乘法原理计数。也就是说，我们可以将**X的每一维度特征下的每个取值与某个类别**配对，并**同样的用一个参数来描绘这个配对的紧密程度**。
可以这么理解：就是把普遍意义上的"输入的特征"拆分处理变成"输入和输出共同的特征"。
比如原来是：
$$
\{ X = 1 \} ==> \{ Y = Class_i \}
$$
现在是
$$
f(x,y) =
\begin{cases}
1 & \text{当x,y满足某一事实} \\[2ex]
0 & \text{当不满足该事实}
\end{cases}
$$
比如每个特征函数可以是从Context到0-1的二值函数。
$$
f(x,y) =
\begin{cases}
1 & \text{if $x$ = "is" and y = v} \\[2ex]
0 & \text{otherwise}
\end{cases}
$$
我们为每个
