条件最大熵模型及其推导过程——统计建模技术之二

/ NLP / 没有评论 / 393浏览

条件最大熵

如果对不了解,请查看熵(Entropy)与信息量详细介绍——统计机器学习核心概念 如果对最大熵模型不了解,请查看最大熵模型 Maximum Entropy——统计建模技术之一

场景描述

对于词性标注,一个词语,可能有多种标记
比如“把”,可以是介词,动词,量词, 名词
对于每一种词性,并不知道占多大比例,也就是 P(介词) = ?
但一定满足约束条件:$\sum p=1$

对于上述词性标注的例子,“把”的词性是一个集合 Y ={介词,动词,量词,名词}
统计建模后一定会输出一个 $y \in Y$, y 表示建模后得到的“把”的词性
输出 y 的过程中,可能受上下文信息的影响,我们把这个语境因素定义为 x, x 形成的集合为 X

X 表示句子出现在“把”周围的所有词汇

模型构建

我们需要构建一个模型,该模型的任务是在给定上下文 x 的情况下,输出 y 的概率 $p(y|x)$

此时优化的目标是分布的条件熵

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

由于 $p(x,y)$ 未知,条件熵可做如下近似

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

特征的观察值期望依然和最大熵模型一样

$$E_{\tilde{p}}f = \sum_{x \in X, y \in Y}\tilde{p}(x,y)f(x,y), \qquad \tilde{p}(x,y) = \frac{c(x,y)}{N}$$

特征的模型期望可如下近似计算

$$E_{p}f = \sum_{x \in X,y \in Y} p(x,y)f(x,y) \approx \sum_{x \in X,y \in Y}\tilde{p}(x)p(y|x)f(x,y)$$

这仍是一个约束最优化问题

约束条件

最大熵约束

$$p^* = \underset{p \in P}{\mathrm{argmax}} H(p), \qquad H(p) = -\sum_{x \in X,y \in Y}\tilde{p}(x)p(y|x) \log p(y|x)$$

特征的模型期望应该与特征的观察期望值一致 $E_{p}f_{j} = E_{\tilde{p}}f_{j}, \quad 1 \leq j \leq k$, 即:

$$E_{p}f = \sum_{x \in X,y \in Y}\tilde{p}(x)p(y|x)f(x,y) = \sum_{x \in X, y \in Y}\tilde{p}(x,y)f(x,y) = E_{\tilde{p}}f$$

概率和为1

$$\sum_{y}p(y|x) = 1$$

约束最优化

运用拉格朗日乘数法,构建拉格朗日函数

$$ L(p, \wedge, \alpha) = H(p) + \sum_{j}\lambda_{j}(E_{p}f_{j}-E_{\tilde{p}f_{j}}) + \alpha(\sum_{y \in Y}p(y|x)-1), \quad \wedge = (\lambda_{1}, \lambda_{2}, ..., \lambda_{k}) $$

展开为

$$\begin{aligned} L(p, \wedge, \alpha) &= -\sum_{x \in X,y \in Y}\tilde{p}(x)p(y|x) \log p(y|x) \\
&+ \sum_{j}\lambda_{j}(\sum_{x \in X,y \in Y}\tilde{p}(x)p(y|x)f_{j}(x,y) - \sum_{x \in X, y \in Y}\tilde{p}(x,y)f_{j}(x,y)) \\
&+ \alpha(\sum_{y \in Y}p(y|x)-1), \quad \wedge = (\lambda_{1}, \lambda_{2}, ..., \lambda_{k}) \end{aligned}$$

公式推导

两边对 $p(y|x)$ 求偏导

$$\begin{aligned} \frac{\partial L}{\partial p(y|x)} &= -\tilde{p}(x) \left [ \log p(y|x) + \frac{p(y|x)}{p(y|x)} \right ] + \sum_{j}\lambda_{j} \tilde{p}(x)f_{j}(x,y) + \alpha \\ &= -\tilde{p}(x)(\log p(y|x) + 1) + \sum_{j}\lambda_{j} \tilde{p}(x)f_{j}(x,y) + \alpha \end{aligned}$$

令该等式等于 0,求解 $p(y|x)$:

$$-\tilde{p}(x)(\log p(y|x) + 1) + \sum_{j}\lambda_{j} \tilde{p}(x)f_{j}(x,y) + \alpha = 0$$

$$\tilde{p}(x)(\log p(y|x) + 1) = \sum_{j}\lambda_{j} \tilde{p}(x)f_{j}(x,y) + \alpha$$

$$\log p(y|x) + 1 = \sum_{j}\lambda_{j}f_{j}(x,y) + \frac{\alpha}{\tilde{p}(x)}$$

$$\log p(y|x) = \sum_{j}\lambda_{j}f_{j}(x,y) + \frac{\alpha}{\tilde{p}(x)} - 1$$

$$p(y|x) = \exp(\sum_{j}\lambda_{j}f_{j}(x,y))\exp(\frac{\alpha}{\tilde{p}(x)} - 1) \tag{1}$$

由约束条件 $\sum_{y}p(y|x) = 1$ 得

$$\sum_{y} \exp(\sum_{j}\lambda_{j}f_{j}(x,y))\exp(\frac{\alpha}{\tilde{p}(x)} - 1) = 1$$

$$\exp(\frac{\alpha}{\tilde{p}(x)} - 1) = \frac{1}{\sum_{y} \exp(\sum_{j}\lambda_{j}f_{j}(x,y))}$$

将该结果带入到 (1) 式得

$$p(y|x) = \exp(\sum_{j}\lambda_{j}f_{j}(x,y))\frac{1}{\sum_{y} \exp(\sum_{j}\lambda_{j}f_{j}(x,y))}$$

得到条件最大熵分布的一般形式

$$p^*(y|x) = \frac{1}{Z(x)} \exp(\sum_{j}\lambda_{j}f_{j}(x,y))$$

$Z(x)$ 是归一常数

$$Z(x)=\sum_{y}\exp(\sum_{j}\lambda_{j}f_{j}(x,y))$$