统计学习方法笔记07

李航. 统计学习方法[M]. 清华大学出版社, 2012.

6.2 最大熵模型

最大熵原理：学习概率模型时，在所有可能（即满足所有约束条件的）的概率模型（分布）中，熵最大的模型是最好的模型。

离散随机变量 $X$ 的概率分布是 $P(X)$ ，其熵满足不等式

$0 \; \leq \; H(P)=-\sum_{x} P(x)\log{P(x)} \; \leq \; \log |X|$

式中 $|X|$ 是 $X$ 的取值的个数，当且仅当 $X$ 的分布是均匀分布时右边等号成立，即熵最大。

用特征函数(feature function) $f(x,y)$ 描述输入 $x$ 和输出 $y$ 之间的某一个事实。其定义是

$f(x,y) = \begin{cases}1, &\text{x和y满足某一事实} \\0, &\text{否则}\end{cases}$

于是，特征函数 $f(x,y)$ 关于经验分布 $\widetilde{P}(X,Y)$ 的期望值

$E_{\widetilde{P}}(f) = \sum_{x,y} \widetilde{P}(x,y) f(x,y)$

特征函数 $f(x,y)$ 关于模型 $P(Y|X)$ 和经验分布 $\widetilde{P}(X)$ 的期望值

$E_{P}(f) = \sum_{x,y} \widetilde{P}(x) P(y|x) f(x,y)$

如果模型能够获取训练数据中的信息，那么就可以假设这两个期望值相等 $E_{\widetilde{P}}(f)=E_{P}(f)$ 。加入有 $n$ 个特征函数 $f_i(x,y),i=1,2,\dots,n$ ，那么就有 $n$ 个约束条件。

最大熵模型

假设满足所有约束条件的模型集合为 $\mathcal{C} = \{P\in\mathcal{P}|E_{\widetilde{P}}(f)=E_{P}(f), i=1,2,\dots,n\}$ ，定义在条件概率分布 $P(Y|X)$ 上的条件熵为

$H(P)=-\sum_{x,y} \widetilde{P}(x)P(y|x)\log{P(y|x)}$

则模型集合 $\mathcal{C}$ 中条件熵最大的模型称为最大熵模型。式中对数为自然对数。

最大熵模型的学习（书P98-102，配合附录C中的对偶问题求解）

原问题求解 $\min_{P\in\mathcal{C}} -H(P)$ ，引入拉格朗日乘子(目的是消除约束)后求解 $\min_{P\in\mathcal{C}} \max_{\omega} L(P,\omega)$ ，利用对偶问题及其凸性质求解 $\max_{\omega} \min_{P\in\mathcal{C}} L(P,\omega)$ ，即先对 $P$ 求偏导置0，后对 $\omega$ 求偏导置0。

最大熵模型学习中对偶问题极大化等价于最大熵模型的极大似然估计。最大熵模型为

$P_{\omega}(y|x) = \dfrac{1}{Z_{\omega}(x)} \exp{\left( \sum_{i=1}^n \omega_i f_i(x,y) \right)}$

$Z_{\omega}(x) = \sum_{y} \exp{\left( \sum_{i=1}^n \omega_i f_i(x,y) \right)}$

对数似然函数为

$L(\omega)=\sum_{x,y}\widetilde{P}(x,y)\sum_{i=1}^n \omega_i f_i(x,y) - \sum_{x} \widetilde{P}(x)\log{Z_{\omega}(x)}$

6.3 模型学习的最优化算法

逻辑斯谛回归模型、最大熵模型学习归结为以似然函数为目标函数的最优化问题，通常通过迭代算法求解。

改进的迭代尺度法(improved iterative scaling,IIS)是一种最大熵模型学习的最优化算法。目标是通过极大似然估计学习模型参数，即求对数似然函数的极大值 $\hat{\omega}$ 。

IIS的想法是：假设最大熵模型当前的参数向量是 $\omega=(\omega_1,\omega_2,\dots,\omega_n)^T$ ，我们希望找到一个新的参数向量 $\omega+\delta=(\omega_1+\delta_1,\omega_2+\delta_2,\dots,\omega_n+\delta_n)^T$ ，使得模型的对数似然函数值增大。

改进的迭代尺度法(improved iterative scaling, IIS)

输入：特征函数 $f_1,f_2,\dots,f_n$ ；经验分布 $\widetilde{P}(X,Y)$ ，模型 $P_{\omega}(y|x)$

输出：最优参数值 $\omega_i^{*}$ ；最优模型 $P_{\omega^*}$

(1) 对所有 $i\in\{1,2,\dots,n\}$ ，取初值 $\omega_i=0$ 。

(2) 对每一个 $i\in\{1,2,\dots,n\}$ ，令 $\delta_i$ 是方程

$\sum_{x,y}\widetilde{P}(x)P(y|x)f_i(x,y) \exp{(\delta_i f^{\#}(x,y))}=E_{\widetilde{P}}(f_i)$

的解，其中 $f^{\#}(x,y)=\sum_{i=1}^n f_i(x,y)$ 。更新 $\omega_i$ 的值： $\omega_i\leftarrow\omega_i+\delta_i$ 。

    * 如果$$f^{\#}(x,y)=M$$是常数，那么$$\delta_i$$可以显式地表示为$$\delta_i = \dfrac{1}{M}\log{\dfrac{E_{\widetilde{P}}(f_i)}{E_{P}(f_i)}}$$
    * 如果不是常数，需要用牛顿法迭代公式$$\delta_i^{(k+1)} = \delta_i^{(k)} - \dfrac{g(\delta_i^{(k)})}{g(\delta_i^{(k)})}$$求$$\delta_i^*$$使$$g(\delta_i^*)=0$$

(3) 如果不是所有 $\omega_i$ 都收敛，重复步骤(2)

最大熵模型学习的BFGS算法

输入：特征函数 $f_1,f_2,\dots,f_n$ ；经验分布 $\widetilde{P}(X,Y)$ ，目标函数 $f(\omega)$ ，梯度 $g(\omega)=\nabla f(\omega)$ ，精度要求 $\varepsilon$ ；

输出：最优参数值 $\omega^{*}$ ；最优模型 $P_{\omega^*}(y|x)$ 。

(1) 选定初始点 $\omega^{(0)}$ ，取 $B_0$ 为正定对称矩阵，置 $k=0$

(2) 计算 $g_k=g(\omega^{(k)})$ 。若 $||g_k||<\varepsilon$ ，则停止计算，得到 $\omega^*=\omega^{(k)}$ ；否则转(3)

(3) 由 $B_k p_k=-g_k$ 求出 $p_k$

(4) 一维搜索：求 $\lambda_k$ 使得 $f(\omega^{(k)}+\lambda_k p_k) = \min_{\lambda>0} f(\omega^{(k)}+\lambda p_k)$

(5) 置 $\omega^{(k+1)}=\omega^{(k)}+\lambda_k p_k$

(6) 计算 $g_{k+1}=g(\omega^{(k+1)})$ ，若 $||g_{k+1}||<\varepsilon$ ，则停止计算，得 $\omega^*=\omega^{(k+1)}$ ；否则按下式求出 $B_{k+1}$ ： $B_{k+1}=B_k+\dfrac{y_ky_k^T}{y_k^T\delta_k} - \dfrac{B_k \delta_k \delta_k^T B_k}{\delta_k^T B_k \delta_k}$ 。其中 $y_k=g_{k+1}-g_k$ ， $\delta_k=\omega^{(k+1)}-\omega^{(k)}$

(7) 置 $k=k+1$ ，转(3)

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 202,529评论 5赞 475
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,015评论 2赞 379
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 149,409评论 0赞 335
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,385评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,387评论 5赞 364
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,466评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,880评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,528评论 0赞 256
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,727评论 1赞 295
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,528评论 2赞 319
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,602评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,302评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,873评论 3赞 306
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,890评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,132评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,777评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,310评论 2赞 342

统计学习方法笔记07

6.2 最大熵模型

6.3 模型学习的最优化算法

推荐阅读更多精彩内容