最大熵模型求解
$\mathbb S1^o$拉格朗日乘子法与拉格朗日对偶性
使用拉格朗日乘子法：
$L(P,w)=-H(P)+w_0(1-\sum_yP(y|x))+\sum_{i=1}^nw_i(\mathbb E_{\hat P}(f_i)-\mathbb E_{P}(f_i))$
$=\sum_{x,y}\hat P(x)P(y|x)\log P(y|x)+w_0(1-\sum_yP(y|x))$
$+\sum_{i=1}^nw_i(\sum_{x,y}\hat P(x,y)f_i(x,y)-\sum_{x,y} \hat P(x)P(y|x)f_i(x,y))$
难以求极值，转化为广义拉格朗日极大极小问题，于是我们需要优化：
由于拉格朗日函数$L(P,w)$是$P$的凸函数，满足KKT条件，于是该优化问题等价于其对偶问题：
（更多阅读拉格朗日乘子和对偶性专题）
$\mathbb S2^o$内部求仅含$x$变量的0导数
先解决内部的极小化问题。
由于$L(P,w)$是凸函数，那对其直接求0导数即可
记$\Phi(w)=\min_{P∈\mathbb C}L(P,w)=L(P_w,w)$，$\Phi(w)$称为对偶函数
则对偶函数的解$P_w=\arg\min_{P∈\mathbb C}L(P,w)=P_w(y|x)$ ，即：求使得$L(P,w)$最小的$P(y|x)$
于是使用0导数法： （易错。见HMM中求和函数求导）
$\frac{\partial L(P,w)}{\partial P(y|x)}=\hat P(x)\log P(y|x)+\hat P(x)-w_0-\hat P(x)\sum_{i=1}^nw_if_i(x,y)=0$
为了利用更多分布信息，左右两边同时求$\sum_{x,y}$（就可以给$w_0$项再凑一个$\hat P(x)$来消去所有的$\hat P(x)$）
$\therefore \sum_{x,y}\hat P(x)\log P(y|x)+\sum_{x,y}\hat P(x)-\sum_{x,y}w_0-\sum_{x,y}\hat P(x)\sum_{i=1}^nw_if_i(x,y)=0$
由于$\sum_{x,y}\hat P(x)=1且w_0与x,y不相关$，$\therefore \sum_{x,y}w_0=w_0\sum_{x,y}=w_0\sum_{x,y}\hat P(x)$
$\therefore \sum_{x,y}\hat P(x)(\log P(y|x)+1-w_0-\sum_{i=1}^nw_if_i(x,y))=0$
又经验分布$\hat P(x)>0$，那么该乘式必然右边部分$=0$
$\therefore \log P(y|x)+1-w_0-\sum_{i=1}^nw_if_i(x,y)=0$
$\therefore P(y|x)=e^{\sum_{i=1}^nw_if_i(x,y)+w_0-1}=\frac{e^{\sum_{i=1}^nw_if_i(x,y)}}{e^{1-w_0}}$
$\because \sum_{y}P(y|x)=1$，所以为了归一化$P(y|x)$，引入归一化因子
$\therefore P_w(y|x)=\frac{1}{Z_w(x)}e^{\sum_{i=1}^nw_if_i(x,y)}$，$Z_w(x)=\sum_y e^{\sum_{i=1}^nw_if_i(x,y)}$
（注意$Z_w(x)$式子中$y$被边缘化了，所以$Z_w(x)$只与$x$有关）
其中$Z_w$称为规范化因子，$f_i(x,y)$是特征函数，$w_i$是特征的权值。
$P_w=P_w(y|x)$就是最大熵模型，$w$是最大熵模型中的参数向量
$\mathbb S3^o$外部恰好等价于求极大似然估计
于是我们下一步要求的就是对偶问题外部极大化问题：
（发现这个式子就可以用最优化算法来求了）
对偶函数的极大化等价于最大熵模型的极大似然估计：$\Phi(w)=L_{\hat P}(P_w)$
证明：将$\mathbb S2^o$中求出来的$P_w(y|x)$表达式代入$\mathbb S2^o$中的$L(P,w)$，即为对偶函数，恰好等于$P_w(y|x)$的似然函数$L_{\hat P}(P_w)$（见$\mathbb S4^o$中）。
也就是说，我们对上面已经求得的内部最小化一般形式MEM：$P_w$，求出$w$使得$MLE_{P_w}$最大即可，也是MEM学习过程
可以将MEM表示为更一般的形式【重要】：
$x∈\mathbb R^n$为输入，$y∈\{1,2,\cdots,K\}$为输出，$w∈\mathbb R^n$为权值向量，$f_i(x,y),i=1,2,\cdots,n$为任意实值的特征函数
【MEM的学习目标就转为学$w$】
形象化地举例：
假如我们知道昨天天气是雨$x_1$，今天天气是雷暴$x_2$，那么想要预测明天天气$y$，就可以给出：
$P(y|x_1,x_2,subject)=\frac{e^{w_1(x_1,x_2,y)+w_2(subject,y)}}{Z(x_1,x_2,subject)}$
这里$f_1(x_1,x_2,y),f_2(subject,y)$即为特征函数，即是约束条件，比如可以设定$f_1(x_1,x_2,y)=$三天都是坏天气（自己定义什么是坏天气）不同时发生，等等。$w_1,w_2$即为权重
确定参数$w$的过程就是训练模型的过程
于是我们开始求MLE表达式：
先求出$P_w$的对数似然估计函数：
$L_{\hat P}(P_w)=\log\prod_{i=1}^nP(y_i|x_i)=P(y_1|x_1)P(y_2|x_2)\cdots P(y_n|x_n)$
将相同的样本乘在一起。【注意这里构造MLE表达式】对相同的一组$x,y$，那么有$t$组指数就会为$t$，也就相当于乘了$t$次，这样对所有相同的$x,y$，都可以表示为$P(y|x)^{||(x,y)||_0}$，则对所有不同和相同的$x,y$，最终表示成了：$L_{\hat P}(P_w)=\log\prod_{x,y}P(y|x)^{||(x,y)||_0}$
极大化这个$L_{\hat P}(P_w)$也等同于极大化（指数部分分母除以$N$）：$L_{\hat P}(P_w)=\log\prod_{x,y}P(y|x)^{\hat P(x,y)}$
于是MLE可以表示为【重要】：
$\therefore L_{\hat P}(P_w)=\sum_{x,y}\hat P(x,y)\sum_{i=1}^nw_if_i(x,y)-\sum_{x,y}\hat P(x,y)\log Z_w(x)$
$=\sum_{x,y}\hat P(x,y)\sum_{i=1}^nw_if_i(x)-\sum_{x}\log Z_w(x)\sum_y\hat P(x,y)$ （拆离只含$x$变量的$Z_w(x)$）
$=\sum_{x,y}\hat P(x,y)\sum_{i=1}^nw_if_i(x)-\sum_{x}\hat P(x)\log Z_w(x)$ （$y$被边缘化）
（注意这里MLE的化简！）
最终形式：
$\mathbb S4^o$求解外部的极大似然估计
MEM的学习目标就转为学$w$后，我们就求解其$MLE_w$即可
IIS，梯度下降，牛顿法或拟牛顿法都可以求解，可以看前面的文章
IIS：
展开似然函数表达形式：$L(w)=\sum_{x,y}\hat P(x,y)\sum_{i=1}^nw_if_i(x,y)-\sum_x\hat P(x)\log Z_w(x)$为目标函数
求$\arg\max_wL(w)$
牛顿法：
展开似然函数表达形式：$L_1(w)=\sum_x\hat P(x)\log \sum_y e^{\sum_{i=1}^nw_if_i(x,y)}-\sum_{x,y}\hat P(x,y)\sum_{i=1}^nw_if_i(x,y)$为目标函数
求$\arg\min_wL_1(w)$
梯度下降法：
略
后记
回顾理解复合函数期望：$\mathbb E_{g(x)}f(x)=\int_x g(x)f(x)$
若$f(x)$理解为关于$x$的概率分布，那么$g(x)$可以理解为$x$的权重
为什么要用对数的似然？——对数函数将乘法变为和
拉格朗日对偶性见专题
拉个朗日对偶性求解的外部$\max_{w}$为什么不用零导数法？因为将内部求出的表达式代入回去之后发现无法分离出独立变量的子式，无法用零导法来求
