笔记(总结)-从马尔可夫模型到条件随机场-2

本篇紧接上篇笔记(总结)-从马尔可夫模型到条件随机场-1，讲述最大熵模型（Maximum Entropy Model），和最大熵马尔可夫模型（Maximum Entropy Markov Model）。

最大熵模型

定义与理解

先来简单介绍下熵的概念，看看为什么要“最大熵”建模。

熵用来度量随机变量的不确定性。即熵越大，不确定性越大。

举个例子，给定一个骰子，问抛出去后最终每个面朝上的概率是多少？一般人都会回答“等概率”。为什么这么回答？因为对这个“一无所知的“骰子，假定每个面等概率朝上是最安全的（我们不能主观假设骰子被动过手脚）。从投资角度看，这种假定是风险最小的。从熵的角度看，这是保留了最大的不确定性，也就是让熵最大化。再举例，给定一个骰子，已知4点朝上的概率是 $1 / 3$ ，那么每个面朝上的概率是多少？相应回答为4点为 $1 / 3$ ，其余各点等概率都为 $2 / 15$ 。也就是说已知条件必须满足，然后再进行最大不确定性条件下的回答。这种基于直觉的回答正是运用了最大熵的原理。

此时，对最大熵有了直观的认识。在已知若干约束条件下建模时，我们应该在满足约束条件的基础上，不作其它任何的假设，然后选择熵最大的建模方式。在上述例子中就是满足约束后，使得其它情况满足均匀分布，达到最大熵。这和常说的“不要把鸡蛋放在一个篮子里”的道理是一样的。

特征函数与约束定义

将最大熵问题应用于分类，就得到的是最大熵模型。给定样本集，目标是利用最大熵原理选择最好的分类模型，即对于给定输入 $x$ ，输出概率 $p (y | x)$ 。根据最大熵原理，我们首先要满足已知的约束。那这些约束如何来提取呢？采用的方法是从样本集中提取一些特征，要求这些特征在样本集上的关于经验分布 $\bar{p} (x, y)$ 的期望和特征在模型中关于 $p (x, y)$ 的期望相等。这样，每个特征就对应了一个约束。

特征的抽取在机器学习中是个永恒的话题，我们在此只给出最简单的二值定义方式：

f (x, y) = {\begin{cases} 1, 若 x, y 满 足 某 种 条 件 \\ 0, 否 则 \end{cases}

这个条件可以是某种规则，也可以是一个复杂的计算公式。将特征函数作用在样本集上，就得到了所有的取值情况。

接下来定义经验分布：

\bar{p} (x, y) = \frac{c o u n t (x, y)}{N}, \bar{p} (x) = \frac{c o u n t (x)}{N}

其中， $c o u n t$ 表示在样本集中出现次数。

按照上述期望的方式定义约束如下：

\begin{aligned} E_{\bar{p}} (f) = \sum_{x, y} \bar{p} (x, y) f (x, y), \\ E_{p} (f) = \sum_{x, y} p (x, y) f (x, y) \end{aligned}

其中， $E_{\bar{p}} (f)$ 表示 $f$ 在样本集上关于 $\bar{p} (x, y)$ 的数学期望， $E_{p} (f)$ 表示 $f$ 在模型中关于 $p (x, y)$ 的数学期望。但是 $p (x, y)$ 我们是不知道的，而建模的目标是生成 $p (y | x)$ ，因此我们利用条件概率的反变换 $p (x, y) = p (x) p (y | x)$ ，但是 $p (x)$ 我们也是不知道的，只能利用 $\bar{p} (x)$ 进行近似了。于是我们得到约束条件为：

E_{\bar{p}} (f) = E_{p} (f)

即：

\sum_{x, y} \bar{p} (x, y) f (x, y) = \sum_{x, y} \bar{p} (x) p (y | x) f (x, y)

最大熵引入

特征函数和约束条件定义完毕，接下来定义熵。由于目标是得到条件概率分布，因此使用条件熵：

H (Y | X) = - \sum_{x, y} p (x, y) \log p (y | x)

与 $E_{p} (f)$ 中 $p (x, y)$ 展开方式相同，我们使用近似替代，于是得到：

H (Y | X) = - \sum_{x, y} \bar{p} (x) p (y | x) \log p (y | x)

于是我们的建模目标为：

max_{p} H (Y | X) = - \sum_{x, y} \bar{p} (x) p (y | x) \log p (y | x) \begin{aligned} s . t . & \sum_{y} p (y | x) = 1 \\ E_{\bar{p}} (f) = E_{p} (f), \forall f \end{aligned}

第一个限制条件是为了让 $p (y | x)$ 是一个合法的条件概率分布，第二个限制条件是以特征函数定义的最大熵约束条件。下面我们简述下如何求解最大熵模型。

最大熵模型求解

改写建模目标为：

min_{p} - H (Y | X) = \sum_{x, y} \bar{p} (x) p (y | x) \log p (y | x)

这么做是为了构造对偶问题。下述建模过程都基于对偶问题展开，可以对比本人总结的SVM笔记，建模过程是类似的。首先构造拉格朗日（lagrange）函数如下：

L (p, λ) = - H (Y | X) + λ_{0} (1 - \sum_{y} p (y | x)) + \sum_{i = 1}^{n} λ_{i} (E_{\bar{p}} (f_{i}) - E_{p} (f_{i}))

根据对偶性，最大熵问题等价于：

min_{p} max_{λ} L (p, λ)

该问题称为原问题，构造对偶问题如下：

max_{λ} min_{p} L (p, λ)

由于 $H (Y | X)$ 是关于 $p (y | x)$ 的凸函数，原问题和对偶问题等价，解对偶问题就相当于解原问题，也即解最大熵问题。先解内层的极小问题 $min_{p} L (p, λ)$ ，注意内层极小问题是关于 $p$ 的函数，令：

\frac{\partial L (p, λ)}{\partial p (y | x)} = 0

得到：

\log p (y | x) + 1 - λ_{0} - \sum_{i = 1}^{n} λ_{i} f_{i} (x, y) = 0

解得：

p (y | x) = e^{λ_{0} - 1} \cdot e^{\sum_{i = 1}^{n} λ_{i} f_{i} (x, y)}

代入约束条件 $\sum_{y} p (y | x) = 1$ ，可得：

p_{λ} = \frac{1}{Z_{λ (x)}} e^{\sum_{i = 1}^{n} λ_{i} f_{i} (x, y)} w h e r e Z_{λ} (x) = \sum_{y} e^{\sum_{i = 1}^{n} λ_{i} f_{i} (x, y)}

这边是我们的最大熵模型。此时上式已经不含有 $λ_{0}$ ， $λ_{i}, i = 1, 2, . . ., n$ 为参数，分别对应特征 $f_{i}$ 的权重。 $λ_{i}$ 越大，特征 $f_{i}$ 越重要。只需要解出参数 $λ$ 即可。

内层极小问题解完后，得到了 $p_{λ}$ ，开始解外层极大问题，注意外层问题以 $λ$ 为变量：

max_{λ} min_{p} L (p, λ) ⟶ max_{λ} ψ (λ)

将 $p (λ)$ 结果代入，化简得到：

ψ (λ) = \sum_{i = 1}^{n} λ_{i} E_{\bar{p}} (f) - \sum_{x} \bar{p} (x) \log Z_{λ} (x)

此时目标变为求解：

λ^{*} = \arg max_{λ} ψ (λ)

上式没有显式的解析解，由于 $ψ λ$ 是凸函数，借助于数值方法可以保证求得全局最优解。采用通用迭代尺度法（Generalized Iterative Scaling，GIS）和改进的迭代尺度法（Improved Iterative Scaling，IIS），这两个算法是为最大熵模型量身定制的。由于我们主要关注的是最大熵模型，这里就不再对数值优化算法的过程进行展开。当我们最终得到 $λ$ 参数时，得到最终的最大熵模型：

p_{λ} = \frac{1}{Z_{λ} (x)} e^{\sum_{i = 1}^{n} λ_{i} f_{i} (x, y)} 其 中 Z_{λ} (x) = \sum_{y} e^{\sum_{i = 1}^{n} λ_{i} f_{i} (x, y)} 称 为 归 一 化 因 子

小结

最大熵问题可以把众多复杂因素综合到一个模型中，使用者只需要集中精力选择特征即可，模型会利用约束来综合使用特征。但最大熵模型的计算量太大，且涉及到数值解法，程序实现效果决定了模型的使用情况。最大熵模型总体而言是很优雅的，将熵的概念引入到分类问题中，并使用对偶思想进行转换求解。最终得出的模型结果与接下来要讲的条件随机场也是很像的。即使是在当下出镜率并不高，学习最大熵模型也能提高对各部分知识的理解，个人觉得还是很有必要的。

可以看到最大熵模型最开始就是在基于条件概率 $p (y | x)$ 建模，来得到分类的概率。因此最大熵模型属于判别式模型。最大熵模型在特征函数的设计部分，只考虑了 $f (x, y)$ 中 $x, y$ 应该满足何种条件，与HMM一样，输出之间也是独立的。为了解决这个问题，我们引入最大熵马尔可夫模型（Maximum Entropy Markov Model）。

最大熵马尔可夫模型

MEMM与HMM的关联

回忆下HMM，其中包含两部分概率，状态转移概率矩阵 $P (q_{t} = S_{j} | q_{t - 1} = S_{i}) = a_{i j}$ ，状态产生输出的概率分布 $P (o_{t} = v_{k} | q_{t} = S_{j}) = b_{j} (k)$ 。MEMM进行了如下改进，用 $P (q_{t} | q_{t - 1}, o_{t})$ 来代替HMM中的两部分概率，该公式表示根据前一隐状态和当前观测值来预测当前的隐状态。整体建模思路为 $P (Q | O, λ) = \prod_{t = 1}^{T} P (q_{t} | q_{t - 1}, o_{t})$ ，从这可以看到一开始就基于条件概率建模，目标是给定可观测输出情况下计算隐状态序列的概率，所以MEMM是判别式模型，这一点和HMM不同，和最大熵模型相同。

MEMM和MEM的关联

$P (q_{t} | q_{t - 1}, o_{t})$ 是通过最大熵分类器建模，即：

P (q_{t} | q_{t - 1}, o_{t}) = \frac{1}{Z (o_{t}, q_{t - 1})} e^{\sum_{i = 1}^{n} λ_{i} f_{i} (o_{t}, q_{t})}

和MEM公式对比可以看到，归一化部分的参数是不一样的，这一点不细展开了。MEM在建立模型之后，给定样本直接根据公式给出分类标签的概率，而MEMM是有状态的（这一点取自HMM），最大熵只是建模了相邻状态的变化，即给定了前一状态的具体值和当前的输出时，给出当前状态的概率分布。将每一步的最大熵合并后，我们最终的建模公式是：

P (Q | O, λ) = \prod_{t = 1}^{T} \frac{1}{Z (o_{t}, q_{t - 1})} e^{\sum_{i = 1}^{n} λ_{i} f_{i} (o_{t}, q_{t})}

MEM是无状态的，特征函数基于样本建模。而MEMM是有状态的，特征函数在定义时，可以考虑前后状态与观测值。之前讲HMM的弊端时我们说到，输出独立性假设是建模时就自带的缺陷，这使得HMM无法考量输出之间的依赖关系，而这在自然语言处理中是十分普遍的。比如说词性标注过程中，标签（隐状态）不仅和当前的词（可观测输出）有关，还可能和上下文的标签有关（这部分我们后面细说）。MEMM现在基于状态转移来定义特征函数，可以解决输出独立性的问题。

求解与标注偏置

由于MEMM的建模目标是 $P (Q | O, λ)$ ，对应的就是HMM中的解码问题，于是采用Viterbi算法进行求解。这里我们对比下两个模型的Viterbi递推式：

\begin{aligned} (HMM) & δ_{t + 1} (q) = max_{q^{^{'}}} [δ_{t} (q^{^{'}}) P (q | q^{^{'}})] P (o_{t + 1} | q) \\ (MEMM) & δ_{t + 1} (q) = max_{q^{^{'}}} [δ_{t} (q^{^{'}})] P (q | q^{^{'}}, o_{t + 1}) \end{aligned}

其中， $δ_{t + 1} (q)$ 表示以 $q$ 为路径终点的所有状态转移路径的概率最大值。HMM是利用联合概率展开来建模，没有什么漏洞。而MEMM的后一部分 $P (q | q^{^{'}}, o_{t + 1})$ 是以最大熵建模，进行了归一化，这就带来了问题。考虑下图：

根据上图，计算路径如下：

\begin{aligned} P (1, 1, 1, 1) = 0.4 \times 0.45 \times 0.5 = 0.09 \\ P (2, 2, 2, 2) = 0.2 \times 0.3 \times 0.3 = 0.01 \\ P (1, 2, 1, 2) = 0.6 \times 0.2 \times 0.5 = 0.06 \\ P (1, 1, 2, 2) = 0.4 \times 0.55 \times 0.3 = 0.066 \end{aligned}

最大概率路径是1->1->1->1。但从概率转移图上看，状态1倾向于转移到状态2，状态2倾向于留在状态2。这是由于 $P (q | q^{^{'}}, o_{t + 1})$ 这部分进行了局部归一化，导致当前状态倾向于转移到拥有更少转移状态的状态。以上图为例，比较路径A：1->1->1->1和路径B：1->1->2->2两条路径，在第二次状态转移时不同。路径B选择了当前概率更大的0.55，但是转移到状态2后，由于状态2可以转移的状态很多，导致最终第三次状态转移时2->2的概率只有0.3，换言之，概率被其它转移到其它状态的路径给分流了。反观路径A，只能转移到两个状态，分流的概率也是较少的。因此在MEMM中，概率最大的路径节点中更容易出现转移状态少的状态，这使得某些状态（隐状态即为标注）出现的次数较多，即存在标注偏置问题。

小结

MEMM基于HMM的状态转移思想，引入了最大熵建模转移过程。HMM限定了观测和状态、相邻状态之间的依赖，而MEMM基于状态转移而定义的特征函数能够解决输出独立性的问题，可以表示前后多个状态、观测之间的复杂依赖。但缺点在于最大熵建模状态转移时，进行了概率局部归一化，使得转移状态较多的状态会发生概率分流，从而使得状态转移路径中出现更多的转移状态少的状态节点，即标注偏置问题。为了解决这个问题，我们引入条件随机场，参见下篇。