3. 模型求解

使用\( Lagrange \)将模型转换为无约束优化问题, 设乘子\( w = \{w_0,w_1,\cdots,w_n \} \)。定义\( Lagrange \)函数：

\[ \begin{align}
L(P, w) &= -H(P) + w_0 \left[ 1 – \sum_y p(y|x) \right] + \sum_{i=1} w_i \left[ E_{\tilde{P}}(f_i) – E_P(f_i) \right] \\
&= \sum_{x, y} \tilde{p}(x) p(y|x) \log p(y|x) + w_0 \left[ 1 – \sum_y p(y|x) \right] \\ & \quad + \sum_{i=1} w_i \left[ \sum_{x,y} \tilde{p}(x,y) f_i(x,y) – \sum_{x,y} \tilde{p}(x) p(y|x) f_i(x, y) \right]
\end{align} \]

原始问题和对偶问题分别为：

\[ \min_P \max_w L(P, w) \quad ; \quad \max_w \min_P L(P, w) \]

因\( Lagrange \)函数\( L(P, w) \)是P的凸函数, 因此求解对偶问题等价求解原始问题。

定义对偶函数：

\[ \Psi(w) = \min_P L(P, w) = L(P_w, w) \]

其解为：

\[ P_w = \arg\min_P L(P, w) = P_w(Y|X) \]

也就是说，在\( w \)不变时求得最小值参数。计算\( P_w(Y|X) \)的导数，并让其为0即可。
\[ \begin{align}
\frac{\partial L(P,w)}{\partial p(y|x)} &= \sum_{x,y} \tilde{p}(x) \left( \log p(y|x) + 1 \right) – \sum_y w_0 – \sum_{x,y} \left[ \tilde{p}(x) \sum_{i=1} w_i f_i(x, y) \right] \\
&= \sum_{x,y} \tilde{p}(x) \left( \log p(y|x) + 1 \right) – \sum_x \tilde{p}(x) \sum_y w_0 – \sum_{x,y} \left[ \tilde{p}(x) \sum_{i=1} w_i f_i(x, y) \right] \\
& \quad \text{use:} \sum_x \tilde{p}(x) = 1; \\
&= \sum_{x,y} \tilde{p}(x) \left[ \log p(y|x) + 1 – w_0 – \sum_{i=1} w_i f_i(x,y) \right]
\end{align} \]

令其为0,且已知\( \tilde{p}(x) > 0 \)：
\[ \begin{align}
\log p(y|x) &= \sum_{i=1} w_i f_i(x,y) – (1 – w_0) \\
p(y|x) &= \exp{\left[ \sum_{i=1} w_i f_i(x,y) – (1 – w_0) \right]} \\
&= \frac{\exp \left[ \sum_{i=1} w_i f_i(x,y) \right] }{ \exp( 1-w_0 ) } \\
\text{because:} & \quad \sum_y p(y|x) = 1 \\
p(y|x) &= \frac{\exp \left[ \sum_{i=1} w_i f_i(x,y) \right] }{ Z_w(x) } \\
&= \frac{\exp \left[ \sum_{i=1} w_i f_i(x,y) \right] }{ \sum_y \exp \left[ \sum_{i=1} w_i f_i(x,y) \right] }
\end{align} \]

\( Z_w(x) \)为规范化因子，求得\( P_w \)后，得到最大熵模型，其中\( w_{i=1,2,\cdots,n} \)可以被理解为每个特征的权重，注意在这里\( w_0 \)被规范化因子给消除掉了. 而学习最大熵模型只需要调整权重的大小，极大化对偶函数\( \max_w \Psi(w) \)即可.

4. 极大似然估计

上面已推导出最大熵模型，并已知极大化其对偶函数为模型学习结果。接下来证明对偶函数极大化估计等价于最大熵模型的极大似然估计。

条件概率分布的对数似然函数为：

\[ L_\tilde{P}(P_w) = \log \prod_{x,y}p(y|x)^{\tilde{p}(x,y)} = \sum_{x,y} \tilde{p}(x,y) \log p(y|x) \]

在这里使用指数表示似然，解释如下：
设分布\( p(x_1,x_2,\cdots,x_n) \)的似然函数为，(\( Count \)是计数函数)。
\[ P(x_1,x_2,\cdots,x_n) = \prod_x P(X=x)^{Count(X=x)} \]
需要的是求相对大小，并不在意绝对值。左右同时用总样本数\( N \)开方。
\[ \sqrt[N]{p(x_1,x_2,\cdots,x_n)} = \prod_x P(X=x)^{\frac{Count(X=x)}{N}} = \prod_x p(x) ^{p(x)} \]

\[ \begin{align}
L_\tilde{P}(P_w) &= \sum_{x,y} \tilde{p}(x,y) \log p(y|x) \\
&= \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} w_i f_i(x,y) – \sum_{x,y} \tilde{p}(x,y) \log Z_w(x) \\
\text{because:} & \quad \sum_y p(x,y) = p(x) \\
&= \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} w_i f_i(x,y) – \sum_{x} \tilde{p}(x) \log Z_w(x)
\end{align} \]

对耦函数\( \Psi(w) \)的极大化估计为（在函数解模型\( P_w \)推导中参数\( w_0 \)已被规范化因子证明约掉，因此不再考虑。）。

\[ \begin{align}
\Psi(w) &= L(P_w, w) \\
&= \sum_{x, y} \tilde{p}(x) p_w(y|x) \log p_w(y|x) \\
& \quad + \sum_{i=1} w_i \left[ \sum_{x,y} \tilde{p}(x,y) f_i(x,y) – \sum_{x,y} \tilde{p}(x) p_w(y|x) f_i(x, y) \right] \\
&= \sum_{x,y} \tilde{p}(x) p_w(y|x) \log p_w(y|x) \\
& \quad + \left[ \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} w_i f_i(x,y) – \sum_{x,y} \tilde{p}(x)p_w(y|x) \sum_{i=1} w_i f_i(x,y) \right] \\
&= \sum_{x,y} \tilde{p}(x) p_w(y|x) \left[ \sum_{i=1} w_i f_i(x,y) – \log Z_w(x) \right] \\
& \quad + \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} w_i f_i(x,y) – \sum_{x,y} \tilde{p}(x) p_W(y|x) \sum_{i=1} w_i f_i(x,y) \\
&= \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} w_i f_i (x,y) – \sum_{x,y} \tilde{p}(x) p_w(y|x) \log Z_w(x) \\
& \text{because:} \sum_y p_w(y|x) = 1 \\
&= \sum_{x,y} \tilde{p}(x,y) \sum_{i=1} w_i f_i (x,y) – \sum_{x} \tilde{p}(x) \log Z_w(x)
\end{align} \]

以上证明求解对偶函数极大化和求解模型对数极大似然是相同的，因此最大熵模型的学习使用这两个方法都可行。

五、参考资料
[1] https://en.wikipedia.org/wiki/Maximum-entropy_Markov_model
[2] McCallum, Andrew; Freitag, Dayne; Pereira, Fernando (2000)
[3] Ethem Alpaydın: Introduction to Machine Learning Third Edition 15 Hidden Markov Models
[4] Daphne Koller, Nir Friedman; Probabilistic Graphical Models – Principles and Techniques
[5] 李航; 统计学习方法
[6] peghoty; http://blog.csdn.net/itplus/article/details/26550369