Question

1. 设分类模型是一个条件概率分布 $ MathJax-Element-87 $ 为输入， $ MathJax-Element-88 $ 为输出。

   给定一个训练数据集 $ MathJax-Element-514 $ ，学习的目标是用最大熵原理选取最好的分类模型。

2.1 最大熵模型

1. 根据训练集 $ MathJax-Element-1005 $ ，可以得到联合分布 $ MathJax-Element-90 $ 的经验分布 $ MathJax-Element-99 $ 和 $ MathJax-Element-91 $ 的经验分布 $ MathJax-Element-109 $ ：

   $ \tilde P(X=\vec{\mathbf x},Y=y)=\frac{\upsilon(X=\vec{\mathbf x}, Y=y)}{N} ,\quad \vec{\mathbf x} \in\mathcal X,y\in \mathcal Y\\ \tilde P(X)=\frac{\upsilon(X=\vec{\mathbf x})}{N} ,\quad \vec{\mathbf x} \in\mathcal X $

   其中 $ MathJax-Element-165 $ 为样本数量， $ MathJax-Element-94 $ 为频数。

2. 用特征函数 $ MathJax-Element-107 $ 描述输入 $ MathJax-Element-96 $ 和输出 $ MathJax-Element-97 $ 之间的某个事实：

   $ f(\vec{\mathbf x},y)= \begin{cases} 1, & \text{if $\vec{\mathbf x},y$ statisfy the fact.} \\ 0, & \text{or else.} \end{cases} $

   • 特征函数是一个二值函数，但是理论上它也可以取任意值。

   • 特征函数 $ MathJax-Element-107 $ 关于经验分布 $ MathJax-Element-99 $ 的期望定义为 $ MathJax-Element-100 $ ： $ MathJax-Element-519 $ 。

     这个期望其实就是约束 $ MathJax-Element-113 $ 在训练集上的统计结果的均值（也就是约束 $ MathJax-Element-113 $ 出现的期望的估计量）。

     • 如果 $ MathJax-Element-113 $ 取值为二值0,1，则表示约束 $ MathJax-Element-113 $ 在训练集上出现的次数的均值。
     • 如果 $ MathJax-Element-113 $ 取值为任意值，则表示约束 $ MathJax-Element-113 $ 在训练集上累计的结果的均值。

   • 特征函数 $ MathJax-Element-107 $ 关于模型 $ MathJax-Element-121 $ 与经验分布 $ MathJax-Element-109 $ 的期望用 $ MathJax-Element-110 $ 表示：

     $ \mathbb E_{P}[f]=\sum_{\vec{\mathbf x},y}\tilde P(\vec{\mathbf x})P(y\mid \vec{\mathbf x})f(\vec{\mathbf x},y) $

     理论上 $ MathJax-Element-2317 $ ，这里使用 $ MathJax-Element-1706 $ 作为 $ MathJax-Element-1708 $ 的估计。

   • 可以假设这两个期望相等，即： $ MathJax-Element-111 $ 。

     • $ MathJax-Element-181 $ 在 $ MathJax-Element-2330 $ 时为 0，在 $ MathJax-Element-2333 $ 才有可能非 0 。因此 $ MathJax-Element-519 $ 仅仅在 $ MathJax-Element-2333 $ 上累加。
     • $ MathJax-Element-1706 $ 在 $ MathJax-Element-2342 $ 时为 0，在 $ MathJax-Element-2344 $ 才有可能非 0 。因此 $ MathJax-Element-543 $ 仅在 $ MathJax-Element-2352 $ 上累加。

3. 理论上，由于 $ MathJax-Element-581 $ ，看起来可以使用 $ MathJax-Element-114 $ 作为 $ MathJax-Element-153 $ 的一个估计。

   但是这个估计只考虑某个点 $ MathJax-Element-116 $ 上的估计，并未考虑任何约束。所以这里通过特征函数的两种期望相等来构建在数据集整体上的最优估计。

4. 最大熵模型：假设有 $ MathJax-Element-119 $ 个约束条件 $ MathJax-Element-124 $ ，满足所有约束条件的模型集合为： $ MathJax-Element-120 $ 。

   定义在条件概率分布 $ MathJax-Element-121 $ 上的条件熵为：

   $ H(P)=-\sum_{\vec{\mathbf x},y}\tilde P(\vec{\mathbf x})P(y\mid \vec{\mathbf x})\log P(y\mid \vec{\mathbf x}) $

   则模型集合 $ MathJax-Element-122 $ 中条件熵最大的模型称为最大熵模型。

2.2 词性标注约束案例

1. 在词性标注任务中，给定单词序列 $ MathJax-Element-743 $ ，需要给出每个单词对应的词性 $ MathJax-Element-748 $ 。如 ：{他们 吃 苹果} 对应的标注序列为 {代词 动词 名词} 。

   假设标注仅仅与当前单词有关，与前面、后面的单词无关，也无前面、后面的标注有关。即：标注 $ MathJax-Element-998 $ 由单词 $ MathJax-Element-1000 $ 唯一决定。

   则统计文本中所有单词及其词性，得到训练集 $ MathJax-Element-1035 $ ，其中 $ MathJax-Element-165 $ 为单词数量。

2. 假设没有任何约束，则每个单词取得任何词性的概率都是等可能的。现在发现：苹果 这个单词的词性标记结果中，大部分都是名词，因此可以定义特征函数：

   $ f(v,s)=\begin{cases} 1,& 当 v 为苹果, 且 s 为名词时\\ 0,& 其他情况 \end{cases} $

   统计满足特征函数的样本的个数 $ MathJax-Element-164 $ ，除以样本总数 $ MathJax-Element-165 $ 。则可以认为：当数据足够多时，这个商就是统计意义下的结果：

   $ \mathbb E_{\tilde P}[f(v,s)]=\sum_{v,s}\tilde P(v,s)f(v,s)=\frac {N_f}N $

   其中：

   • $ MathJax-Element-1049 $ ， $ MathJax-Element-935 $ 为二元对 $ MathJax-Element-937 $ 出现的次数。
   • 满足特征函数的样本出现总数为： $ MathJax-Element-2365 $ 。

3. 事实上对于任意单词 $ MathJax-Element-166 $ ，其中 $ MathJax-Element-1082 $ 为所有单词的词汇表， $ MathJax-Element-1115 $ 为词汇表大小； 以及对任意词性 $ MathJax-Element-168 $ ，其中 $ MathJax-Element-1111 $ 为词性集合（如名词、动词、形容词....)， $ MathJax-Element-1116 $ 为词性表大小。 可以任意选择搭配从而构造非常庞大的特征函数：

   $ f_{1,1}(v,s)=\begin{cases} 1,& v=\mathbf v_1,\text{and}\; s=\mathbf s_1\\ 0,& other \end{cases}\\ f_{1,2}(v,s)=\begin{cases} 1,& v=\mathbf v_1,\text{and}\; s=\mathbf s_2\\ 0,& other \end{cases}\\ \vdots\\ f_{i,j}(v,s)=\begin{cases} 1,& v=\mathbf v_i,\text{and}\; s=\mathbf s_j\\ 0,& other \end{cases}\\ \vdots\\ \mathbf v_i\in \mathbb V,\mathbf s_j \in \mathbb S $

   以及约束条件： $ MathJax-Element-1418 $ 。其中 $ MathJax-Element-1420 $ 为满足特征函数 $ MathJax-Element-1423 $ 的样本个数。

   • 如果 $ MathJax-Element-1420 $ 较大，则说明该约束指定的 单词,词性 搭配的可能性很高。
   • 如果 $ MathJax-Element-1420 $ 较小，则说明该约束指定的 单词,词性 搭配的可能性很低。
   • 如果 $ MathJax-Element-1420 $ 为 0，则说明该约束指定的 单词,词性 搭配几乎不可能出现。

4. 待求的模型为 $ MathJax-Element-1152 $ 。以矩阵的形式描述为：

   $ \mathbf P=\begin{bmatrix} P_{1,1}&P_{1,2}&\cdots&P_{1,S}\\ P_{2,1}&P_{2,2}&\cdots&P_{2,S}\\ \vdots&\vdots&\ddots&\vdots\\ P_{V,1}&P_{V,2}&\cdots&P_{V,S} \end{bmatrix},\quad P_{i,j}\ge 0,\quad \sum_{j=1}^S P_{i,j}=1,i=1,2,\cdots,V $

   其中 $ MathJax-Element-1300 $ ，即单词 $ MathJax-Element-1302 $ 的词性为 $ MathJax-Element-1304 $ 的概率。

   • 设单词 $ MathJax-Element-1302 $ 在 $ MathJax-Element-1005 $ 中出现的次数为 $ MathJax-Element-1383 $ ，则有： $ MathJax-Element-1409 $ 。则有：

     $ \mathbb E_{P}[f_{i,j}]=\sum_{v,s}\tilde P(v)P(s\mid v)f_{i,j}(v,s) =\frac {N_i}{N}\times P_{i,j} $

   • 考虑到 $ MathJax-Element-1574 $ ，则根据 $ MathJax-Element-1580 $ 有：

     $ P_{i,j}=\frac{N_{f_{i,j}}}{N_i} $

     • 其物理意义为：单词 $ MathJax-Element-1302 $ 的词性为 $ MathJax-Element-1304 $ 的概率 = 数据集 $ MathJax-Element-1005 $ 中单词 $ MathJax-Element-1302 $ 的词性为 $ MathJax-Element-1304 $ 出现的次数 / 数据集 $ MathJax-Element-1005 $ 中单词 $ MathJax-Element-1302 $ 出现的次数。

     • 由于 $ MathJax-Element-1895 $ ， $ MathJax-Element-1892 $ ，因此可以发现有：

       $ \frac{\tilde P(v=\mathbf v_i,s=\mathbf s_j) }{\tilde P(v=\mathbf v_i)} =\frac{N_{f_{i,j}}}{N_i}= P_{i,j}= P(s=\mathbf s_j\mid v=\mathbf v_i) $

       因此在这个特殊的情形下， $ MathJax-Element-1961 $ 是 $ MathJax-Element-1962 $ 的估计。

5. 事实上，真实的词性标注还需要考虑前后单词的词性的影响。比如：不可能出现连续的三个动词，也不可能出现连续的五个代词。

   当需要考虑前后文影响时，需要使用 HMM 模型 或者 CRF 模型。

2.3 模型求解

1. 对给定的训练数据集 $ MathJax-Element-514 $ ，以及特征函数 $ MathJax-Element-124 $ ，最大熵模型的学习等价于约束最优化问题：

   $ \max_{P\in \mathcal C} H(P)=-\sum_{\vec{\mathbf x},y}\tilde P(\vec{\mathbf x})P(y\mid \vec{\mathbf x})\log P(y\mid \vec{\mathbf x})\\ s.t.\mathbb E_P[f_i]=\mathbb E_{\tilde P}[f_i],i=1,2,\cdots,n\\ \sum_y P(y\mid \vec{\mathbf x})=1 $

2. 将其转化为最小化问题：

   $ \min_{P\in \mathcal C} -H(P)=\sum_{\vec{\mathbf x},y}\tilde P(\vec{\mathbf x})P(y\mid \vec{\mathbf x})\log P(y\mid \vec{\mathbf x})\\ s.t.\mathbb E_P[f_i]-\mathbb E_{\tilde P}[f_i]=0,i=1,2,\cdots,n\\ \sum_y P(y\mid \vec{\mathbf x})=1 $

   其中：

   • $ MathJax-Element-609 $ 是已知的。
   • $ MathJax-Element-611 $ 是未知的。

3. 将约束最优化的原始问题转换为无约束最优化的对偶问题，通过求解对偶问题来求解原始问题。

   引入拉格朗日乘子 $ MathJax-Element-127 $ ，定义拉格朗日函数 $ MathJax-Element-131 $ ：

   $ L(P,\mathbf{\vec w})=-H(P)+w_0(1-\sum_y P(y\mid \vec{\mathbf x}))+\sum_{i=1}^{n}w_i(\mathbb E_{\tilde P}[f_i]-E_P(f_i))\\ =\sum_{\vec{\mathbf x},y}\tilde P(\vec{\mathbf x})P(y\mid \vec{\mathbf x})\log P(y\mid \vec{\mathbf x})+w_0\left(1-\sum_y P(y\mid \vec{\mathbf x})\right)\\ +\sum_{i=1}^{n}w_i\left(\sum_{\vec{\mathbf x},y}\tilde P(\vec{\mathbf x},y)f_i(\vec{\mathbf x},y)-\sum_{\vec{\mathbf x},y}\tilde P(\vec{\mathbf x})P(y\mid \vec{\mathbf x})f_i(\vec{\mathbf x},y)\right) $
   • 最优化的原始问题是： $ MathJax-Element-623 $ ，对偶问题是 $ MathJax-Element-628 $ 。
   • 由于拉格朗日函数 $ MathJax-Element-131 $ 是凸函数，因此原始问题的解与对偶问题的解是等价的。
   • 求解对偶问题：先求解内部的极小化问题，之后求解对偶问题外部的极大化问题。

4. 先求解内部的极小化问题： $ MathJax-Element-656 $ 。

   它是一个 $ MathJax-Element-182 $ 的函数，将其记作： $ MathJax-Element-662 $ 。

   • 先用 $ MathJax-Element-131 $ 对 $ MathJax-Element-153 $ 求偏导数：

     $ \frac{\partial L(P,\vec{\mathbf w})}{\partial P(y\mid \vec{\mathbf x})}=\sum_{\vec{\mathbf x},y}\tilde P(\vec{\mathbf x})(\log P(y\mid \vec{\mathbf x})+1)-\sum_y w_0-\sum_{\vec{\mathbf x},y}\left(\tilde P(\vec{\mathbf x})\sum_{i=1}^{n}w_if_i(\vec{\mathbf x},y)\right)\\ =\sum_{\vec{\mathbf x},y} \tilde P(\vec{\mathbf x})\left(\log P(y\mid \vec{\mathbf x})+1-w_0-\sum_{i=1}^{n}w_i f_i(\vec{\mathbf x},y)\right) $

     令偏导数为 0 。在 $ MathJax-Element-133 $ 时，解得：

     $ P(y\mid \vec{\mathbf x})=\exp\left(\sum_{i=1}^{n}w_i f_i(\vec{\mathbf x},y)+w_0-1\right)=\frac{\exp\left(\sum_{i=1}^{n}w_i f_i(\vec{\mathbf x},y)\right)}{\exp(1-w_0)} $

   • 由于 $ MathJax-Element-134 $ ，则有： $ MathJax-Element-669 $ 。因此有：

     $ \exp(1-w_0)=\sum_y \exp\left(\sum_{i=1}^{n}w_i f_i(\vec{\mathbf x},y)\right) $

   • 定义 $ MathJax-Element-699 $ 为规范因子，则：

     $ P_\mathbf{\vec w}(y\mid \vec{\mathbf x})=\frac{1}{Z_\mathbf{\vec w}(\vec{\mathbf x})} \exp\left(\sum_{i=1}^{n}w_i f_i(\vec{\mathbf x},y)\right) $

     由该式表示的模型 $ MathJax-Element-138 $ 就是最大熵模型。

5. 再求解对偶问题外部的极大化问题： $ MathJax-Element-705 $ 。

   • 将其解记作 $ MathJax-Element-220 $ ，即： $ MathJax-Element-710 $ 。
   • 求得 $ MathJax-Element-220 $ 之后，用它来表示 $ MathJax-Element-138 $ ，得到 $ MathJax-Element-139 $ ，即得到最大熵模型。

6. 上述过程总结为：

   • 先求对偶问题的内部极小化，得到 $ MathJax-Element-157 $ 函数，以及极值点 $ MathJax-Element-204 $ 。
   • 再求 $ MathJax-Element-157 $ 函数的极大值，得到 $ MathJax-Element-220 $ 。
   • 最后将 $ MathJax-Element-220 $ 代入 $ MathJax-Element-204 $ 得到最终模型 $ MathJax-Element-146 $ 。

7. 可以证明： $ MathJax-Element-157 $ 函数的最大化，等价于最大熵模型的极大似然估计。

   证明如下：已知训练数据 $ MathJax-Element-1005 $ 中， $ MathJax-Element-195 $ 出现的频次为 $ MathJax-Element-2155 $ 。则条件概率分布 $ MathJax-Element-153 $ 的对数似然函数为：

   $ \log \prod_{\vec{\mathbf x},y} P(y\mid \vec{\mathbf x})^{k_{\vec{\mathbf x},y}}=\sum_{\vec{\mathbf x},y}k_{\vec{\mathbf x},y}\log P(y\mid \vec{\mathbf x}) $

   将对数似然函数除以常数 $ MathJax-Element-165 $ ，考虑到 $ MathJax-Element-2239 $ ，其中 $ MathJax-Element-181 $ 为经验概率分布。则 $ MathJax-Element-153 $ 的对数似然函数为：

   $ \sum_{\vec{\mathbf x},y}\tilde P(\vec{\mathbf x},y) \log P(y\mid \vec{\mathbf x}) $

   再利用 ：

   $ P_\mathbf{\vec w}(y\mid \vec{\mathbf x})=\frac{1}{Z_\mathbf{\vec w}(\vec{\mathbf x})} \exp\left(\sum_{i=1}^{n}w_i f_i(\vec{\mathbf x},y)\right) $

   代入，最后化简合并，最终发现它就是 $ MathJax-Element-157 $ 。

2.4 最大熵与逻辑回归

1. 设 $ MathJax-Element-1988 $ 为 $ MathJax-Element-119 $ 维变量，对于二类分类问题，定义 $ MathJax-Element-119 $ 个约束：

   $ f_i(\mathbf{\vec x},y)=\begin{cases} x_i,&y=1\\ 0,&y=0 \end{cases},\quad i=1,2,\cdots,n $

2. 根据最大熵的结论，有：

   $ Z_\mathbf{\vec w}(\vec{\mathbf x})=\sum_y \exp\left(\sum_{i=1}^{n}w_i f_i(\vec{\mathbf x},y)\right)=\exp\left(\sum_{i=1}^{n}w_i f_i(\vec{\mathbf x},y=0)\right)+\exp\left(\sum_{i=1}^{n}w_i f_i(\vec{\mathbf x},y=1)\right)\\ =1+\exp\left(\sum_{i=1}^{n}w_i x_i\right)=1+\exp(\mathbf{\vec w}\cdot \mathbf{\vec x}) $

   以及：

   $ P_\mathbf{\vec w}(y\mid \vec{\mathbf x})=\frac{1}{Z_\mathbf{\vec w}(\vec{\mathbf x})} \exp\left(\sum_{i=1}^{n}w_i f_i(\vec{\mathbf x},y)\right) =\frac{1}{1+\exp(\mathbf{\vec w}\cdot \mathbf{\vec x})} \exp\left(\sum_{i=1}^{n}w_i f_i(\vec{\mathbf x},y)\right) $

   • 当 $ MathJax-Element-2494 $ 时有：

     $ P_\mathbf{\vec w}(y=1\mid \vec{\mathbf x})=\frac{1}{1+\exp(\mathbf{\vec w}\cdot \mathbf{\vec x})} \exp\left(\sum_{i=1}^{n}w_i f_i(\vec{\mathbf x},y=1)\right)\\ =\frac{1}{1+\exp(\mathbf{\vec w}\cdot \mathbf{\vec x})} \exp\left(\sum_{i=1}^{n}w_i x_i\right) =\frac{\exp(\mathbf{\vec w}\cdot \mathbf{\vec x})}{1+\exp(\mathbf{\vec w}\cdot \mathbf{\vec x})} $

   • 当 $ MathJax-Element-2518 $ 时有：

     $ P_\mathbf{\vec w}(y=0\mid \vec{\mathbf x})=\frac{1}{1+\exp(\mathbf{\vec w}\cdot \mathbf{\vec x})} \exp\left(\sum_{i=1}^{n}w_i f_i(\vec{\mathbf x},y=0)\right) =\frac{1}{1+\exp(\mathbf{\vec w}\cdot \mathbf{\vec x})} $

   最终得到：

   $ \log \frac{P_\mathbf{\vec w}(y=1\mid \vec{\mathbf x})}{P_\mathbf{\vec w}(y=0\mid \vec{\mathbf x})}=\mathbf{\vec w}\cdot \mathbf{\vec x} $

   这就是逻辑回归模型。