# 一、信息量

一个事件的信息量就是这个事件发生的概率的负对数

$$y=-logP(x)$$



# 二、信息熵

信息熵其实是信息量的期望

$$H(x)=-\sum_xP(x)logP(x)$$

# 三、熵/联合熵/条件熵/互信息

熵度量了事物的不确定性，越不确定的事物，它的熵就越大。具体的，随机变量X的熵的表达式如下：

$$H(X) = -\sum\limits_{i=1}^{n}p_i logp_i$$

其中n代表X的n种不同的离散取值。而$𝑝_𝑖$代表了X取值为i的概率，log为以2或者e为底的对数。

熟悉了一个变量X的熵，很容易推广到多个个变量的联合熵，这里给出两个变量X和Y的联合熵表达式：

$$H(X,Y) = -\sum\limits_{x_i \in X}\sum\limits_{y_i \in Y}p(x_i,y_i)logp(x_i,y_i)$$

有了联合熵，又可以得到条件熵的表达式H(Y|X)，条件熵类似于条件概率,它度量了我们的Y在知道X以后剩下的不确定性。表达式如下：

$$H(Y \mid X)=\sum_{i=1}^{n} p\left(x_{i}\right) H\left(Y \mid X=x_{i}\right)=-\sum_{i=1}^{n} p\left(x_{i}\right) \sum_{j=1}^{m} p\left(y_{j} \mid x_{i}\right) \log p\left(y_{j} \mid x_{i}\right)$$

用下面这个图很容易明白他们的关系。左边的椭圆代表H(X),右边的椭圆代表H(Y),中间重合的部分就是我们的互信息或者信息增益I(X,Y)<font color="red">【代表X和Y的关联程度，可以参考“新词提取”那部分讲解的互信息】</font>, 左边的椭圆去掉重合部分就是H(X|Y),右边的椭圆去掉重合部分就是H(Y|X)。两个椭圆的并就是H(X,Y)。

$$I(X;Y)=\sum_{x,y}P(x,y)log\frac{P(x,y)}{P(x)P(y)}=E_{P(x,y)}log\frac{P(x,y)}{P(x)P(y)}$$



# 四、最大熵模型

最大熵原理是统计学习的一般原理,将它应用到分类就得到了最大熵模型

假设分类模型是一个条件概率分布P(Y|X),X表示输入,Y表示输出。这个模型表示的是对于给定的输入X,以条件概率P(Y|X)输出Y。
给定一个训练数据集T,我们的目标就是利用最大熵原理选择最好的分类模型。

$$T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots\left(x_{N}, y_{N}\right)\right\}$$

按照最大熵原理,我们应该优先保证模型满足已知的所有约束。那么如何得到这些约束呢?
思路是:从训练数据T中抽取若干特征,然后要求这些特征在T上关于经验分布的期望与它们在模型中关于p(x,y)的数学期望相等,这样,一个特征就对应一个约束。

**特征函数**

假设我们需要判断”打“字是动词还是量词，已知的训练数据有

$$
\begin{align}
(x_1,y_1) &= (一打火柴，量词) \\
(x_2,y_2) &= (三打啤酒，量词) \\
(x_3,y_3) &= (五打塑料袋，量词) \\
(x_4,y_4) &= (打电话，动词) \\
(x_5,y_5) &= (打篮球，动词) \\
\end{align}
$$

通过观察，我们发现，“打”前面为数字时，“打”是量词，“打”后面为名词时，“打”是
动词，这就是从训练数据中提取的两个特征，可分别用特征函数表示为

$$f_1(x,y)=
\begin{cases} 
1, 若”打“字前面是数字；\\
0, 否则；
\end{cases}
$$

$$f_2(x,y)=
\begin{cases} 
1, 若”打“字后面是名词；\\
0, 否则；
\end{cases}
$$

定义了两个特征函数后，对于训练数据，我们便有：

$$f_{1}\left(x_{1}, y_{1}\right)=f_{1}\left(x_{2}, y_{2}\right)=f_{1}\left(x_{3}, y_{3}\right)=1 ; f_{1}\left(x_{4}, y_{4}\right)=f_{1}\left(x_{5}, y_{5}\right)=0 ; \cdots$$

$$f_{2}\left(x_{1}, y_{1}\right)=f_{2}\left(x_{2}, y_{2}\right)=f_{2}\left(x_{3}, y_{3}\right)=0 ; f_{2}\left(x_{4}, y_{4}\right)=f_{2}\left(x_{5}, y_{5}\right)=1 ; \cdots$$

**经验分布**

经验分布是指通过训练数据T上进行统计得到的分布。我们需要考察两个经验分布,分别是x,y的联合经验分布以及x的分布。其定义如下:

$$\tilde{p}(x, y)=\frac{\operatorname{count}(x, y)}{N}, \quad \tilde{p}(x)=\frac{\operatorname{count}(x)}{N}$$

count(x,y)表示(x,y)在数据T中出现的次数,count(x)表示x在数据T中出现的次数。

**约束条件**

对于任意的特征函数f，记$E_{\tilde{p}}(f)$表示f在训练数据T上关于$\tilde{p}(x,y)$的数学
期望。$E_p(f)$表示f在模型上关于p(x,y)的数学期望。按照期望的定义,有:

$$E_{\tilde{p}}(f)=\sum_{x, y} \tilde{p}(x, y) f(x, y)$$

$$E_{p}(f)=\sum_{x, y} p(x, y) f(x, y)$$

我们需要注意的是第二个公式中p(x,y)是未知的。并且我们建模的
目标是求出p(y|x)，因此我们利用贝叶斯定理得到p(x,y)=p(x)p(y|x)。
此时，p(x)也还是未知,我们可以使用经验分布$\tilde{p}(x)$对p(x)进行近似。

$$E_{p}(f)=\sum_{x, y} \tilde{p}(x) p(y \mid x) f(x, y)$$


对于概率分布p(y|x),我们希望特征f的期望应该和从训练数据中得到的特征期望是一样的。因此,可以提出约束:

$$E_{p}(f)=E_{\tilde{p}}(f)$$

$$\sum_{x, y} \tilde{p}(x) p(y \mid x) f(x, y)=\sum_{x, y} \tilde{p}(x, y) f(x, y)$$

假设从训练数据中抽取了n个特征,相应的便有n个特征函数以及n个约束条件，$\mathcal{C}_{i}$表示第i个约束条件。

$$\mathcal{C}_{i}: E_{p}\left(f_{i}\right)=E_{\tilde{p}}\left(f_{i}\right)\ i=1,2, \cdots, n$$

**最大熵模型**

- 模型函数
定义最大熵模型为条件概率分布𝑃(𝑌|𝑋)上的条件熵：

$$H(P) = -\sum\limits_{x,y}\tilde{P}(x)P(y|x)logP(y|x)$$

- 目标

我们的目标是得到使𝐻(𝑃)最大的时候对应的𝑃(𝑦|𝑥),这里可以对𝐻(𝑃)加了个负号求极小值，这样做的目的是为了使−𝐻(𝑃)为凸函数，方便使用凸优化的方法来求极值【或者说给定数据集T,我们的目标就是根据最大熵原理选择一个最优的分类器。】。


- 损失函数

最大熵模型的函数𝐻(𝑃)。它的损失函数−𝐻(𝑃)定义为:

$$\underbrace{ min }_{P} -H(P) = \sum\limits_{x,y}\tilde{P}(x)P(y|x)logP(y|x)$$

约束条件为：

$$E_{\tilde{P}}(f_i) - E_{P}(f_i) = 0 (i=1,2,...M)$$

$$\sum\limits_yP(y|x) = 1\sum\limits_yP(y|x) = 1$$

由于它是一个凸函数，同时对应的约束条件为仿射函数，根据凸优化理论，这个优化问题可以用拉格朗日函数将其转化为无约束优化函数，此时损失函数对应的拉格朗日函数𝐿(𝑃,𝑤)定义为：

$$L(P,w) \equiv -H(P) + w_0(1 - \sum\limits_yP(y|x)) + \sum\limits_{i=1}^{M}w_i(E_{\tilde{P}}(f_i) - E_{P}(f_i))$$

其中$𝑤_𝑖(𝑖=1,2,...𝑚)$为拉格朗日乘子。如果大家也学习过支持向量机，就会发现这里用到的凸优化理论是一样的，接着用到了拉格朗日对偶也一样。

我们的拉格朗日函数，即为凸优化的原始问题：

$$\underbrace{ min }_{P} \underbrace{ max }_{w}L(P, w)$$

其对应的拉格朗日对偶问题为：

$$\underbrace{ max}_{w} \underbrace{ min }_{P}L(P, w)$$

由于原始问题满足凸优化理论中的KKT条件，因此原始问题的解和对偶问题的解是一致的。这样我们的损失函数的优化变成了拉格朗日对偶问题的优化。

求解对偶问题的第一步就是求$\underbrace{ min }_{P}L(P, w)$, 这可以通过求导得到。这样得到的$\underbrace{ min }_{P}L(P, w)$是关于w的函数。记为：

$$\psi(w) = \underbrace{ min }_{P}L(P, w) = L(P_w, w)$$

$\psi(w)$即为对偶函数，将其解记为：

$$P_w = arg \underbrace{ min }_{P}L(P, w) = P_w(y|x)$$

具体的是求$𝐿(𝑃,𝑤)$关于$𝑃(𝑦|𝑥)$的偏导数:

$$
\begin{align}
\frac{\partial L(P, w)}{\partial P(y|x)} &= \sum\limits_{x,y}\tilde{P}(x)(logP(y|x) +1) -  \sum\limits_yw_0 - \sum\limits_{x,y}(\tilde{P}(x)\sum\limits_{i=1}^{M}w_if_i(x,y))\\
&= \sum\limits_{x,y}\tilde{P}(x)(logP(y|x) +1- w_0 -\sum\limits_{i=1}^{M}w_if_i(x,y))
\end{align}
$$

令偏导数为0，可以解出$𝑃(𝑦|𝑥)$关于𝑤的表达式如下：

$$P(y|x) = exp(\sum\limits_{i=1}^{M}w_if_i(x,y) +w_0 -1) = \frac{exp(\sum\limits_{i=1}^{M}w_if_i(x,y))}{exp(1-w_0)}$$

由于$\sum_𝑦𝑃(𝑦|𝑥)=1$，可以得到$𝑃_𝑤(𝑦|𝑥)$的表达式如下：

$$
\begin{align}
&\sum_yP_w(y|x)=\frac{\sum_yexp(\sum\limits_{i=1}^{M}w_if_i(x,y))}{exp(1-w_0)} = 1\\
&\frac{P(y|x)}{1}=\frac{\frac{exp(\sum\limits_{i=1}^{M}w_if_i(x,y))}{exp(1-w_0)}}{1}=\frac{exp(\sum\limits_{i=1}^{M}w_if_i(x,y))}{exp(1-w_0)} \times \frac{exp(1-w_0)}{\sum_yexp(\sum\limits_{i=1}^{M}w_if_i(x,y))}=\frac{exp(\sum\limits_{i=1}^{M}w_if_i(x,y))}{\sum_yexp(\sum\limits_{i=1}^{M}w_if_i(x,y))}\\
&P_w(y|x) = \frac{1}{Z_w(x)}exp(\sum\limits_{i=1}^{M}w_if_i(x,y))
\end{align}
$$

其中，$𝑍_𝑤(𝑥)$为规范化因子，定义为：

$$Z_w(x) = \sum\limits_yexp(\sum\limits_{i=1}^{M}w_if_i(x,y))$$

<font color="red">这样我们就得出了𝑃(𝑦|𝑥)和𝑤的关系，从而可以把对偶函数𝜓(𝑤)里面的所有的𝑃(𝑦|𝑥)替换成用𝑤表示，这样对偶函数𝜓(𝑤)就是全部用𝑤表示了。接着我们对𝜓(𝑤)求极大化，就可以得到极大化时对应的w向量的取值，带入𝑃(𝑦|𝑥)和𝑤的关系式， 从而得到𝑃(𝑦|𝑥)的最终结果，依据𝑃(𝑦|𝑥)最终结果，来取概率最大的y作为类别。

**注意：**
    

</font>

对𝜓(𝑤)求极大化，由于它是连续可导的，所以优化方法有很多种，比如梯度下降法，牛顿法，拟牛顿法都可以。对于最大熵模型还有一种专用的优化方法，叫做改进的迭代尺度法(improved iterative scaling, IIS)。

IIS使用的方法是找到𝜓(𝑤+𝛿)−𝜓(𝑤)的一个下界𝐵(𝑤|𝛿)，通过对𝐵(𝑤|𝛿)极小化来得到对应的𝛿的值，进而来迭代求解𝑤。对于𝐵(𝑤|𝛿)，它的极小化是通过对𝛿求偏导数而得到的。

　由于IIS一般只用于最大熵模型，适用范围不广泛，这里就不详述算法过程了，感兴趣的朋友可以直接参考IIS的论文<a src="http://www.researchgate.net/publication/229027688_The_improved_iterative_scaling_algorithm_A_gentle_introduction">The improved iterative scaling algorithm: A gentle introduction。</a>

# 五、小结

最大熵模型在分类方法里算是比较优的模型，但是由于它的约束函数的数目一般来说会随着样本量的增大而增大，导致样本量很大的时候，对偶函数优化求解的迭代过程非常慢，scikit-learn甚至都没有最大熵模型对应的类库。但是理解它仍然很有意义，尤其是它和很多分类方法都有千丝万缕的联系。　

惯例，我们总结下最大熵模型作为分类方法的优缺点：

最大熵模型的优点有：

- 最大熵统计模型获得的是所有满足约束条件的模型中信息熵极大的模型,作为经典的分类模型时准确率较高。

- 可以灵活地设置约束条件，通过约束条件的多少可以调节模型对未知数据的适应度和对已知数据的拟合程度

最大熵模型的缺点有：

- 由于约束函数数量和样本数目有关系，导致迭代过程计算量巨大，实际应用比较难。



# 六、最大熵马尔科夫模型（MEMM）



MEMM正因为是判别模型，所以不废话，我上来就直接为了确定边界而去建模，比如说序列求概率（分类）问题，我直接考虑找出函数分类边界。这一点跟HMM的思维方式发生了很大的变化，如果不对这一点有意识，那么很难理解为什么MEMM、CRF要这么做。

HMM中，观测节点$O_i$依赖隐藏状态节点$i_i$,也就意味着我的观测节点只依赖当前时刻的隐藏状态。但在更多的实际场景下，观测序列是需要很多的特征来刻画的，比如说，我在做NER时，我的标注$i_i$不仅跟当前状态$O_i$相关，而且还跟前后标注$O_j(j\neq i)$相关，比如字母大小写、词性等等。

为此，提出来的MEMM模型就是能够直接允许“定义特征”，直接学习条件概率，即

$$P\left(i_{i} \mid i_{i-1}, o_{i}\right)(i=1, \cdots, n)$$

$$P(I \mid O)=\prod_{t=1}^{n} P\left(i_{i} \mid i_{i-1}, o_{i}\right), i=1, \cdots, n$$

并且，$P\left(i \mid i^{\prime}, o\right)$这个概率通过最大熵分类器建模（取名MEMM的原因）:

$$P\left(i \mid i^{\prime}, o\right)=\frac{1}{Z\left(o, i^{\prime}\right)} \exp \left(\sum_{a} \lambda_{a} f_{a}(o, i)\right)$$

重点来了，这是ME的内容，也是理解MEMM的关键：$Z\left(o, i^{\prime}\right)$这部分是归一化；$f_{a}(o, i)$是特征函数，具体点，这个函数是需要去定义的；$\lambda$是特征函数的权重，这是个未知参数，需要从训练阶段学习而得。

所以，MEMM的建模公式为：

$$P(I \mid O)=\prod_{t=1}^{n} \frac{\exp \left(\sum_{a} \lambda_{a} f_{a}(o, i)\right)}{Z\left(o, i_{i-1}\right)}, i=1, \cdots, n$$

是的，公式这部分之所以长成这样，是由ME模型决定的。

请务必注意，理解判别模型和定义特征两部分含义，这已经涉及到CRF的雏形了。

MEMM需要两点注意：

1. 与HMM的$O_i$依赖$i_i$不一样，MEMM当前隐藏状态$i_i$应该是依赖当前时刻的观测节点$O_i$和上一时刻的隐藏节点$i_{i-1}$

2. 需要注意，之所以图的箭头这么画，是由MEMM的公式决定的，而公式是creator定义出来的。

MEMM模型的工作流程也包括了学习训练问题、序列标注问题、序列求概率问题。




# 七、最大熵模型理解



# 八、最大熵模型的最大似然函数解释





```python

```

0d1ff53dae5e20182d274ba313e0d0a727c5fefb
ipynb
Jupyter Notebook
algorithm/mem_and_memm/mem_and_memm.ipynb
v-smwang/AI-NLP-Tutorial
3dbfdc7e19a025e00febab97f4948da8a3710f34
Apache-2.0
algorithm/mem_and_memm/mem_and_memm.ipynb
v-smwang/AI-NLP-Tutorial
3dbfdc7e19a025e00febab97f4948da8a3710f34
Apache-2.0
algorithm/mem_and_memm/mem_and_memm.ipynb
v-smwang/AI-NLP-Tutorial
3dbfdc7e19a025e00febab97f4948da8a3710f34
Apache-2.0
Qwen/Qwen-72B
1. YES
2. YES