中文分词词性和序列标注之MEMM-3-最大熵模型求解
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