极大似然估计

上篇文章介绍了最大熵模型以及采用拉格朗日乘子法求解对偶问题，其模型的解如下，

\begin{equation} P_{w}(y|x) = \frac 1 {Z_{w}(x)} \exp {\left( \sum\limits_{i=1}^n w_{i} f_{i}(x,y) \right)} \end{equation}

\begin{equation} Z_{w}(x,y) = \sum\limits_{y} \exp {\left( \sum\limits_{i=1}^n w_{i} f_{i}(x,y) \right)} \end{equation}

然后代入拉格朗日函数得到对偶函数$\Psi(w)$，

\begin{equation} \Psi(w) = L(P_{w},w) \end{equation}

于是对w求$\Psi(w)$的极大，解得 w 代入 (1)和(2)得到 $P_{w}(y|x)$。

本篇我们介绍最大熵模型的极大似然估计，并证明它与上述对偶函数的极大化是等价的。

首先计算$\Psi(w)$，先给出拉格朗日函数

\begin{aligned} L(P,w)  & \equiv -H(P)+w_{0}(1- \sum_{y}P(y|x))+ \sum_{i=1}^n w_{i}(E_{\tilde P}(f_i)-E_{P}(f_i))  \\ & = {\sum_{x,y} \tilde{P} (x)P(y|x)logP(y|x)+w_{0}(1- \sum_{y}P(y|x)) + \sum\limits_{i=1}^n w_{i}(\sum_{x,y} \tilde{P}(x,y)f_{i}(x,y)-\sum_{x,y} \tilde{P}(x)P(y|x)f_{i}(x,y))} \end{aligned}

于是

$$ \Psi(w)  =  \sum\limits_{x,y} \tilde{P}(x)P_{w}(y|x)logP_{w}(y|x)  + w_{0}(1-\sum_{y}P(y|x))  + \sum\limits_{i=1}^n w_{i}(\sum\limits_{x,y} \tilde{P}(x,y)f_{i}(x,y)-\sum\limits_{x,y} \tilde{P}(x)P_{w}(y|x)f_{i}(x,y)) $$

注意到有如下等式（具体参考上一篇文章）

$$\sum\limits_{y}P(y|x)=\frac{\sum\limits_{y}\exp{\left(\sum\limits_{i=1}^n w_{i} f_{i}(x,y) \right)}} {\exp(1-w_0)}=1$$

化简$\Psi(w)$的表达式，

\begin{equation} \begin{aligned} \Psi(w) & = \sum\limits_{x,y} \tilde{P}(x)P_{w}(y|x)logP_{w}(y|x)  + \sum\limits_{i=1}^n w_{i}(\sum\limits_{x,y} \tilde{P}(x,y)f_{i}(x,y)-\sum\limits_{x,y} \tilde{P}(x)P_{w}(y|x)f_{i}(x,y)) \\ & = \sum_{x,y}\tilde{P}(x,y)\sum_{i=1}^nw_{i}f_{i}(x,y) +\sum_{x,y}\tilde{P}(x)P_{w}(y|x)\left(logP_{w}(y|x) - \sum_{i=1}^nw_{i}f_{i}(x,y)\right) \\ & = \sum_{x,y}\tilde{P}(x,y)\sum_{i=1}^nw_{i}f_{i}(x,y)-\sum_{x,y}\tilde{P}(x)P_{w}(y|x)logZ_{w}(x) \\ & = \sum_{x,y}\tilde{P}(x,y)\sum_{i=1}^nw_{i}f_{i}(x,y)-\sum_{x}\tilde{P}(x) \log Z_{w}(x) \end{aligned} \end{equation}

其中$Z_{w}(x)$由(2)给出，这就是对偶函数的最终形式。

再看条件概率分布P(Y|X)的对数似然函数，给定训练数据集T，条件概率分布P(Y|X)的对数似然函数为

\begin{equation} L(P) = \log\prod_{x,y}P(y|x)^{\tilde{P}(x,y)} = \sum_{x,y}\tilde{P}(x,y) \log P(y|x) \end{equation}

上式以指数形式引入$\tilde{P}(x,y)$似乎不那么容易理解，这里举个例子类比一下，假设X1,X2,...,Xn~Bernoulli(p)，概率密度函数为

$$f(x;p)=p^{x}(1-p)^{1-x}$$

其中x=0,1，未知参数p表示x=1的概率，于是似然函数为，

$$\cal {L}_{n}(p) = \prod_{i=1}^n f(X_i;p) = \prod_{i=1}^n p^{X_i}(1-p)^{1-X_i} = p^{S}(1-p)^{n-S}$$

观察上式这个似然函数，发现本质是如下形式，

$$\cal {L}_{n}(p) = \prod_{i=1}^n p_{i}^{S_i}$$

其中$p_i$是$X_i$的概率，$S_i$是训练集中$X_i$出现次数，这两者的构成一个指数形式的项对应于$X_i$，然后将X所有取值对应的这些项连乘。

类比这里条件概率P(Y|X)的的似然函数，指数的底P(y|x)就是(x,y)构成的条件概率，将指数$\tilde{P}(x,y)$乘以训练数据集大小N这个常数，就是数据(x,y)出现的次数，于是(5)式就是(X,Y)的所有取值(x,y)构成的指数项连乘。

好了，既然理解了对数似然函数的构成，下面再对其进行求解，已知$P_{w}(y|x)$的解由(1)式给出，代入(5)式为，

\begin{equation} \begin{aligned} L(\tilde{P})  & = \sum_{x,y} \tilde{P}(x,y) \log P(y|x) \\ & = \sum_{x,y} \tilde{P}(x,y) \sum_{i=1}^n w_{i}f_{i}(x,y) - \sum_{x,y} \tilde{P}(x,y) \log Z_{w}(x) \\ & = \sum_{x,y} \tilde{P}(x,y) \sum_{i=1}^n w_{i}f_{i}(x,y) - \sum_{x} \tilde{P}(x) \log Z_{w}(x) \end{aligned} \end{equation}

发现与(4)式相同，也就是说，对偶函数等价于对数似然函数。

最大熵模型（二）