全部笔记的汇总贴：统计学习方法读书笔记汇总贴

逻辑斯谛回归 (logistic regression ）是统计学习中的经典分类方法。最大熵是概率模型学习的一个准则，将其推广到分类问题得到最大熵模型（maximum entropy model) 。逻辑斯谛回归模型与最大熵模型都属于对数线性模型。

一、逻辑斯谛回归模型

设 X X X是连续随机变量， X X X服从逻辑斯谛分布是指 X X X具有下列分布函数和密度函数： F ( x ) = P ( X ≤ x ) = 1 1 + e − ( x − μ ) γ f ( x ) = F ′ ( x ) = e − ( x − μ ) γ γ ( 1 + e − ( x − μ ) γ ) 2 F(x)=P(X\le x)=\frac1{1+e^{-\frac{(x-\mu)}\gamma}}\\f(x)=F'(x)=\frac{e^{-\frac{(x-\mu)}\gamma}}{\gamma(1+e^{-\frac{(x-\mu)}\gamma})^2} F(x)=P(X≤x)=1+e−γ(x−μ)​1​f(x)=F′(x)=γ(1+e−γ(x−μ)​)2e−γ(x−μ)​​其中， μ \mu μ为位置参数， γ > 0 \gamma>0 γ>0为形状参数。

分布函数 F ( x ) F(x) F(x)属于逻辑斯蒂函数，图形是一条 S S S形曲线，该曲线以 ( μ , 1 2 ) (\mu,\frac12) (μ,21​)为中心对称，即满足 F ( − x + μ ) − 1 2 = − F ( x + μ ) + 1 2 F(-x+\mu)-\frac12=-F(x+\mu)+\frac12 F(−x+μ)−21​=−F(x+μ)+21​曲线在中心附近增长速度较快，在两端增长速度较慢。形状参数 γ \gamma γ的值越小，曲线在中心附近增长得越快。

二项逻辑斯谛回归模型（binomial logistic regression model）是一种分类模型，由条件概率分布 P ( Y ∣ X ) P(Y|X) P(Y∣X) 表示，形式为参数化的逻辑斯蒂分布。条件概率分布为： P ( Y = 1 ∣ x ) = exp ⁡ ( w ⋅ x ) 1 + exp ⁡ ( w ⋅ x ) P ( Y = 0 ∣ x ) = 1 1 + exp ⁡ ( w ⋅ x ) P(Y=1|x)=\frac{\exp(w\cdot x)}{1+\exp(w\cdot x)}\\P(Y=0|x)=\frac1{1+\exp(w\cdot x)} P(Y=1∣x)=1+exp(w⋅x)exp(w⋅x)​P(Y=0∣x)=1+exp(w⋅x)1​

一个事件的几率（odds）是指该事件发生的概率与该事件不发生的概率的比值。一个事件的几率（odds）是指该事件发生的概率与该事件不发生的概率的比值。逻辑斯蒂回归的对数几率为 log ⁡ P ( Y = 1 ∣ x ) 1 − P ( Y = 1 ∣ x ) = w ⋅ x \log \frac{P(Y=1|x)}{1-P(Y=1|x)}=w\cdot x log1−P(Y=1∣x)P(Y=1∣x)​=w⋅x这就是说，在逻辑斯谛回归模型中，输出 Y = 1 Y=1 Y=1的对数几率是输入 x x x的线性函数。或者说，输出 Y = 1 Y= 1 Y=1的对数几率是由输入 x x x的线性函数表示的模型，即逻辑斯谛回归模型。

多项逻辑斯蒂回归模型 P ( Y = k ∣ x ) = exp ⁡ ( w k ⋅ x ) 1 + ∑ k = 1 K − 1 exp ⁡ ( w k ⋅ x ) P ( Y = K ∣ x ) = 1 1 + ∑ k = 1 K − 1 exp ⁡ ( w k ⋅ x ) P(Y=k|x)=\frac{\exp(w_k\cdot x)}{1+\sum_{k=1}^{K-1}\exp(w_k\cdot x)}\\P(Y=K|x)=\frac1{1+\sum_{k=1}^{K-1}\exp(w_k\cdot x)} P(Y=k∣x)=1+∑k=1K−1​exp(wk​⋅x)exp(wk​⋅x)​P(Y=K∣x)=1+∑k=1K−1​exp(wk​⋅x)1​

二、最大熵模型

最大熵模型（maximum entropy model) 由最大熵原理推导实现，最大熵原理是概率模型学习的一个准则。最大熵原理认为，学习概率模型时，在所有可能的概率模型（分布）中，熵最大的模型是最好的模型。

H ( P ) = − ∑ x P ( x ) log ⁡ P ( x ) 0 ≤ H ( P ) ≤ log ⁡ ∣ X ∣ H(P)=-\sum_xP(x)\log P(x)\\0\le H(P)\le \log|X| H(P)=−x∑​P(x)logP(x)0≤H(P)≤log∣X∣其中， ∣ X ∣ |X| ∣X∣是 X X X的取值个数，当且仅当 X X X是均匀分布时右边等号成立，也就是说，当 X X X服从均匀分布时，熵最大。

直观的可以把它看作等可能事件，具体的解析解求法可以用有约束的拉格朗日法。

三、模型学习的最优化算法

常用的方法有改进的迭代尺度法、梯度下降法、牛顿法或拟牛顿法。牛顿法或拟牛顿法一般收敛速度更快，但约束过多。

这里讲解一个书上提到的迭代尺度法（IIS）。可以看看这篇文献，讲的很详细：The Improved Iterative Scaling Algorithm

已知最大熵模型为： P w ( y ∣ x ) = 1 Z w ( x ) exp ⁡ ( ∑ i = 1 n w i f i ( x , y ) ) ( 1 ) P_w(y|x)=\frac1{Z_w(x)}\exp\Big(\sum_{i=1}^nw_if_i(x,y)\Big)\;\;\;\;\;\;(1) Pw​(y∣x)=Zw​(x)1​exp(i=1∑n​wi​fi​(x,y))(1)

其中， Z w ( x ) = ∑ y exp ⁡ ( ∑ i = 1 n w i f i ( x , y ) ) （ 规 范 化 因 子 ） ( 2 ) Z_w(x)=\sum_y\exp\Big(\sum_{i=1}^nw_if_i(x,y)\Big)（规范化因子）\;\;\;\;\;(2) Zw​(x)=y∑​exp(i=1∑n​wi​fi​(x,y))（规范化因子）(2)

对数似然函数为 L p ^ ( w ) = ∑ x , y P ^ ( x , y ) ∑ i = 1 n w i f i ( x , y ) − ∑ x P ^ ( x ) log ⁡ Z w ( x ) ( 3 ) L_{\hat p}(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)\;\;\;\;(3) Lp^​​(w)=x,y∑​P^(x,y)i=1∑n​wi​fi​(x,y)−x∑​P^(x)logZw​(x)(3)

给定联合经验分布函数 p ^ ( x , y ) \hat p(x,y) p^​(x,y)，根据条件模型 p w ( y ∣ x ) p_w(y|x) pw​(y∣x)，其对数似然函数为 L p ^ ( w ) = ∑ x , y p ^ ( x , y ) log ⁡ p w ( y ∣ x ) ( 4 ) L_{\hat p}(w)=\sum_{x,y}\hat p(x,y)\log p_w(y|x)\;\;\;\;\;\;(4) Lp^​​(w)=x,y∑​p^​(x,y)logpw​(y∣x)(4)

由(1)、(2)式可得 L p ^ ( w ) = ∑ x , y P ^ ( x , y ) ∑ i = 1 n w i f i ( x , y ) − ∑ x , y P ^ ( x , y ) log ⁡ Z w ( x ) ( 5 ) L_{\hat 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)\;\;\;\;\;\;(5) Lp^​​(w)=x,y∑​P^(x,y)i=1∑n​wi​fi​(x,y)−x,y∑​P^(x,y)logZw​(x)(5)

对比(3)和(5)，可得 ∑ x P ^ ( x ) = ∑ x , y P ^ ( x , y ) \sum_x\hat P(x)=\sum_{x,y}\hat P(x,y) ∑x​P^(x)=∑x,y​P^(x,y)

将(2)代入(3)得 L p ^ ( w ) = ∑ x , y P ^ ( x , y ) ∑ i = 1 n w i f i ( x , y ) − ∑ x P ^ ( x ) log ⁡ ∑ y exp ⁡ ( ∑ i = 1 n w i f i ( x , y ) ) L_{\hat p}(w)=\sum_{x,y}\hat P(x,y)\sum_{i=1}^nw_if_i(x,y)-\sum_x\hat P(x)\log \sum_y\exp\Big(\sum_{i=1}^nw_if_i(x,y)\Big) Lp^​​(w)=x,y∑​P^(x,y)i=1∑n​wi​fi​(x,y)−x∑​P^(x)logy∑​exp(i=1∑n​wi​fi​(x,y))

对 w i w_i wi​求偏导 ∂ L p ^ ( w ) ∂ w i = ∑ x , y P ^ ( x , y ) f i ( x , y ) − ∑ x , y p ^ ( x ) p w ( y ∣ x ) f i ( x , y ) \frac{\partial L_{\hat p}(w)}{\partial w_i}=\sum_{x,y}\hat P(x,y)f_i(x,y)-\sum_{x,y}\hat p(x)p_w(y|x)f_i(x,y) ∂wi​∂Lp^​​(w)​=x,y∑​P^(x,y)fi​(x,y)−x,y∑​p^​(x)pw​(y∣x)fi​(x,y)

令导数等于0得 ∑ x , y P ^ ( x , y ) f i ( x , y ) = ∑ x , y p ^ ( x ) p w ( y ∣ x ) f i ( x , y ) \sum_{x,y}\hat P(x,y)f_i(x,y)=\sum_{x,y}\hat p(x)p_w(y|x)f_i(x,y) x,y∑​P^(x,y)fi​(x,y)=x,y∑​p^​(x)pw​(y∣x)fi​(x,y)

即经验分布 p ^ ( x , y ) \hat p(x,y) p^​(x,y)的期望于经验分布 p ^ ( x ) \hat p(x) p^​(x)的值相等是一个很自然的条件。

IIS 的想法是：假设最大熵模型当前的参数向量是 w = ( w 1 , w 2 ， ⋯ ， w n ) T w = (w_1 ,w_2，\cdots，w_n)^T w=(w1​,w2​，⋯，wn​)T，我们希望找到一个新的参数向量 w + δ = ( w 1 + δ 1 , w 2 + δ 2 ， ⋯ ， w n + δ n ) T w+\delta = (w_1+\delta_1 ,w_2+\delta_2，\cdots，w_n+\delta_n)^T w+δ=(w1​+δ1​,w2​+δ2​，⋯，wn​+δn​)T，使得模型的对数似然函数值增大。如果能有这样一种参数向量更新的方法 τ : w → w + δ \tau :w\rightarrow w+\delta τ:w→w+δ，那么就可以重复使用这一方法，直至找到对数似然函数的最大值。

根据(4)得 L p ^ ( w + δ ) − L p ^ ( w ) = ∑ x , y p ^ ( x , y ) log ⁡ p w + δ ( y ∣ x ) − ∑ x , y p ^ ( x , y ) log ⁡ p w ( y ∣ x ) = ∑ x , y P ^ ( x , y ) ∑ i = 1 n ( w i + δ − w i ) f i ( x , y ) − ∑ x P ^ ( x ) log ⁡ Z w + δ ( x ) + ∑ x P ^ ( x ) log ⁡ Z w ( x ) = ∑ x , y P ^ ( x , y ) ∑ i = 1 n ( w i + δ − w i ) f i ( x , y ) − ∑ x P ^ ( x ) log ⁡ Z w + δ ( x ) Z w ( x ) L_{\hat p}(w+\delta)-L_{\hat p}(w)=\sum_{x,y}\hat p(x,y)\log p_{w+\delta}(y|x)-\sum_{x,y}\hat p(x,y)\log p_w(y|x)\\=\sum_{x,y}\hat P(x,y)\sum_{i=1}^n(w_i+\delta-w_i)f_i(x,y)-\sum_{x}\hat P(x)\log Z_{w+\delta}(x)+\sum_{x}\hat P(x)\log Z_w(x)\\=\sum_{x,y}\hat P(x,y)\sum_{i=1}^n(w_i+\delta-w_i)f_i(x,y)-{\color{blue}\sum_{x}\hat P(x)\log \frac{Z_{w+\delta}(x)}{ Z_w(x)}} Lp^​​(w+δ)−Lp^​​(w)=x,y∑​p^​(x,y)logpw+δ​(y∣x)−x,y∑​p^​(x,y)logpw​(y∣x)=x,y∑​P^(x,y)i=1∑n​(wi​+δ−wi​)fi​(x,y)−x∑​P^(x)logZw+δ​(x)+x∑​P^(x)logZw​(x)=x,y∑​P^(x,y)i=1∑n​(wi​+δ−wi​)fi​(x,y)−x∑​P^(x)logZw​(x)Zw+δ​(x)​

利用不等式 − log ⁡ a ≥ 1 − a ( a > 0 ) -\log a\ge1-a(a>0) −loga≥1−a(a>0)

所以 L p ^ ( w + δ ) − L p ^ ( w ) ≥ ∑ x , y P ^ ( x , y ) ∑ i = 1 n δ f i ( x , y ) + ∑ x P ^ ( x ) − ∑ x P ^ ( x ) Z w + δ ( x ) Z w ( x ) ( 又 ∑ x P ^ ( x ) = 1 ) = ∑ x , y P ^ ( x , y ) ∑ i = 1 n δ f i ( x , y ) + 1 − ∑ x P ^ ( x ) Z w + δ ( x ) Z w ( x ) L_{\hat p}(w+\delta)-L_{\hat p}(w)\ge\sum_{x,y}\hat P(x,y)\sum_{i=1}^n\delta f_i(x,y)+{\color{blue}\sum_{x}\hat P(x)-\sum_{x}\hat P(x) \frac{Z_{w+\delta}(x)}{ Z_w(x)}}\;\;\;\;\;\;(又\sum_{x}\hat P(x) =1)\\=\sum_{x,y}\hat P(x,y)\sum_{i=1}^n\delta f_i(x,y)+{\color{blue}1-\sum_{x}\hat P(x) \frac{Z_{w+\delta}(x)}{ Z_w(x)}} Lp^​​(w+δ)−Lp^​​(w)≥x,y∑​P^(x,y)i=1∑n​δfi​(x,y)+x∑​P^(x)−x∑​P^(x)Zw​(x)Zw+δ​(x)​(又x∑​P^(x)=1)=x,y∑​P^(x,y)i=1∑n​δfi​(x,y)+1−x∑​P^(x)Zw​(x)Zw+δ​(x)​

又因为 Z w + δ ( x ) Z w ( x ) = 1 Z w ( x ) ⋅ ∑ y exp ⁡ ( ∑ i = 1 n ( w i + δ i ) f i ( x , y ) ) = 1 Z w ( x ) ⋅ ∑ y exp ⁡ ( ∑ i = 1 n w i f i ( x , y ) + ∑ i = 1 n δ i f i ( x , y ) ) = ∑ y 1 Z w ( x ) ⋅ exp ⁡ ( ∑ i = 1 n w i f i ( x , y ) ) exp ⁡ ( ∑ i = 1 n δ i f i ( x , y ) ) = ∑ y p w ( y ∣ x ) exp ⁡ ( ∑ i = 1 n δ i f i ( x , y ) ) \frac{Z_{w+\delta}(x)}{ Z_w(x)}=\frac1{ Z_w(x)}\cdot \sum_y\exp\Big(\sum_{i=1}^n(w_i+\delta_i)f_i(x,y)\Big)\\=\frac1{ Z_w(x)}\cdot \sum_y\exp\Big(\sum_{i=1}^nw_if_i(x,y)+\sum_{i=1}^n\delta_if_i(x,y)\Big)\\=\sum_y\frac1{ Z_w(x)}\cdot \exp\Big(\sum_{i=1}^nw_if_i(x,y)\Big)\exp\Big(\sum_{i=1}^n\delta_if_i(x,y)\Big)\\=\sum_yp_w(y|x)\exp\Big(\sum_{i=1}^n\delta_if_i(x,y)\Big) Zw​(x)Zw+δ​(x)​=Zw​(x)1​⋅y∑​exp(i=1∑n​(wi​+δi​)fi​(x,y))=Zw​(x)1​⋅y∑​exp(i=1∑n​wi​fi​(x,y)+i=1∑n​δi​fi​(x,y))=y∑​Zw​(x)1​⋅exp(i=1∑n​wi​fi​(x,y))exp(i=1∑n​δi​fi​(x,y))=y∑​pw​(y∣x)exp(i=1∑n​δi​fi​(x,y))

即 L p ^ ( w + δ ) − L p ^ ( w ) ≥ ∑ x , y P ^ ( x , y ) ∑ i = 1 n δ f i ( x , y ) + 1 − ∑ x P ^ ( x ) ∑ y p w ( y ∣ x ) exp ⁡ ( ∑ i = 1 n δ i f i ( x , y ) ) L_{\hat p}(w+\delta)-L_{\hat p}(w)\ge \sum_{x,y}\hat P(x,y)\sum_{i=1}^n\delta f_i(x,y)+1-\sum_{x}\hat P(x) \sum_yp_w(y|x)\exp\Big(\sum_{i=1}^n\delta_if_i(x,y)\Big) Lp^​​(w+δ)−Lp^​​(w)≥x,y∑​P^(x,y)i=1∑n​δfi​(x,y)+1−x∑​P^(x)y∑​pw​(y∣x)exp(i=1∑n​δi​fi​(x,y))

将右端记作 A ( δ ∣ w ) A(\delta|w) A(δ∣w)

所以 L p ^ ( w + δ ) − L p ^ ( w ) ≥ A ( δ ∣ w ) L_{\hat p}(w+\delta)-L_{\hat p}(w)\ge A(\delta|w) Lp^​​(w+δ)−Lp^​​(w)≥A(δ∣w)即 A ( δ ∣ w ) A(\delta|w) A(δ∣w)是对数似然函数改变量的一个下界。

如果能找到适当的 δ \delta δ使下界 A ( δ ∣ w ) A(\delta|w) A(δ∣w)提高，那么对数似然函数也会提高。但是 A ( δ ∣ w ) A(\delta|w) A(δ∣w)是一个 n n n维向量，不易于同时优化。IIS试图每次优化其中一个 δ i \delta_i δi​，而固定其他变量 δ j , i ≠ j \delta_j,i\ne j δj​,i​=j。我们引入新的量 f # ( x , y ) = ∑ i f i ( x , y ) f^\#(x,y)=\sum_if_i(x,y) f#(x,y)=i∑​fi​(x,y)因为 f i ( x , y ) f_i(x,y) fi​(x,y)是一个二值函数， f # ( x , y ) f^\#(x,y) f#(x,y)表示特征 ( x , y ) (x,y) (x,y)出现的次数。所以我们重写 A ( δ ∣ w ) A(\delta|w) A(δ∣w)得到 A ( δ ∣ w ) = ∑ x , y P ^ ( x , y ) ∑ i = 1 n δ f i ( x , y ) + 1 − ∑ x P ^ ( x ) ∑ y p w ( y ∣ x ) exp ⁡ ( f # ( x , y ) ∑ i = 1 n δ i f i ( x , y ) f # ( x , y ) ) ( 6 ) A(\delta|w)=\sum_{x,y}\hat P(x,y)\sum_{i=1}^n\delta f_i(x,y)+1-\sum_{x}\hat P(x) \sum_yp_w(y|x)\exp\Big({\color{blue}f^\#(x,y)}\sum_{i=1}^n\frac{\delta_if_i(x,y)}{\color{blue}f^\#(x,y)}\Big)\;\;\;\;\;(6) A(δ∣w)=x,y∑​P^(x,y)i=1∑n​δfi​(x,y)+1−x∑​P^(x)y∑​pw​(y∣x)exp(f#(x,y)i=1∑n​f#(x,y)δi​fi​(x,y)​)(6)

利用指数函数的凸函数性质以及对任意 i i i有 f i ( x , y ) f # ( x , y ) ≥ 0 \frac{f_i(x,y)}{f^\#(x,y)}\ge 0 f#(x,y)fi​(x,y)​≥0且 ∑ i = 1 n f i ( x , y ) f # ( x , y ) = 1 \sum_{i=1}^n\frac{f_i(x,y)}{f^\#(x,y)}=1%+ ∑i=1n​f#(x,y)fi​(x,y)​=1这一事实，根据Jensen不等式，得到 exp ⁡ ( ∑ i = 1 n f i ( x , y ) f # ( x , y ) δ i f # ( x , y ) ) ≤ ∑ i = 1 n f i ( x , y ) f # ( x , y ) exp ⁡ ( δ i f # ( x , y ) ) \exp\Big(\sum_{i=1}^n\frac{f_i(x,y)}{f^\#(x,y)}\delta_i f^\#(x,y)\Big)\le \sum_{i=1}^n\frac{f_i(x,y)}{f^\#(x,y)}\exp\Big(\delta_i f^\#(x,y)\Big) exp(i=1∑n​f#(x,y)fi​(x,y)​δi​f#(x,y))≤i=1∑n​f#(x,y)fi​(x,y)​exp(δi​f#(x,y))

令 p ( x ) = f i ( x , y ) f # ( x , y ) , q ( x ) = δ i f # ( x , y ) p(x)=\frac{f_i(x,y)}{f^\#(x,y)},q(x)=\delta_i f^\#(x,y) p(x)=f#(x,y)fi​(x,y)​,q(x)=δi​f#(x,y)，重写(6)得到 A ( δ ∣ w ) ≥ ∑ x , y P ^ ( x , y ) ∑ i = 1 n δ f i ( x , y ) + 1 − ∑ x P ^ ( x ) ∑ y p w ( y ∣ x ) ∑ i = 1 n f i ( x , y ) f # ( x , y ) exp ⁡ ( δ i f # ( x , y ) ) A(\delta|w)\ge \sum_{x,y}\hat P(x,y)\sum_{i=1}^n\delta f_i(x,y)+1-\sum_{x}\hat P(x) \sum_yp_w(y|x) \sum_{i=1}^n\frac{f_i(x,y)}{f^\#(x,y)}\exp\Big(\delta_i f^\#(x,y)\Big) A(δ∣w)≥x,y∑​P^(x,y)i=1∑n​δfi​(x,y)+1−x∑​P^(x)y∑​pw​(y∣x)i=1∑n​f#(x,y)fi​(x,y)​exp(δi​f#(x,y))

不等式右边记为 B ( δ ∣ w ) = ∑ x , y P ^ ( x , y ) ∑ i = 1 n δ f i ( x , y ) + 1 − ∑ x P ^ ( x ) ∑ y p w ( y ∣ x ) ∑ i = 1 n f i ( x , y ) f # ( x , y ) exp ⁡ ( δ i f # ( x , y ) ) B(\delta|w)= \sum_{x,y}\hat P(x,y)\sum_{i=1}^n\delta f_i(x,y)+1-\sum_{x}\hat P(x) \sum_yp_w(y|x) \sum_{i=1}^n\frac{f_i(x,y)}{f^\#(x,y)}\exp\Big(\delta_i f^\#(x,y)\Big) B(δ∣w)=x,y∑​P^(x,y)i=1∑n​δfi​(x,y)+1−x∑​P^(x)y∑​pw​(y∣x)i=1∑n​f#(x,y)fi​(x,y)​exp(δi​f#(x,y))

所以 L p ^ ( w + δ ) − L p ^ ( w ) ≥ B ( δ ∣ w ) L_{\hat p}(w+\delta)-L_{\hat p}(w)\ge B(\delta|w) Lp^​​(w+δ)−Lp^​​(w)≥B(δ∣w)

对于新的下界 B ( δ ∣ w ) B(\delta|w) B(δ∣w)，对 δ i \delta_i δi​求偏导得 ∂ B ( δ ∣ w ) ∂ δ i = ∑ x , y P ^ ( x , y ) f i ( x , y ) − ∑ x P ^ ( x ) ∑ y p w ( y ∣ x ) ∑ i = 1 n f i ( x , y ) exp ⁡ ( δ i f # ( x , y ) ) \frac{\partial B(\delta|w)}{\partial\delta_i}=\sum_{x,y}\hat P(x,y) f_i(x,y)-\sum_{x}\hat P(x) \sum_yp_w(y|x) \sum_{i=1}^n{f_i(x,y)}\exp\Big(\delta_i f^\#(x,y)\Big) ∂δi​∂B(δ∣w)​=x,y∑​P^(x,y)fi​(x,y)−x∑​P^(x)y∑​pw​(y∣x)i=1∑n​fi​(x,y)exp(δi​f#(x,y))令导数为0，得 ∑ x , y P ^ ( x , y ) f i ( x , y ) = ∑ x P ^ ( x ) ∑ y p w ( y ∣ x ) ∑ i = 1 n f i ( x , y ) exp ⁡ ( δ i f # ( x , y ) ) \sum_{x,y}\hat P(x,y) f_i(x,y)=\sum_{x}\hat P(x) \sum_yp_w(y|x) \sum_{i=1}^n{f_i(x,y)}\exp\Big(\delta_i f^\#(x,y)\Big) x,y∑​P^(x,y)fi​(x,y)=x∑​P^(x)y∑​pw​(y∣x)i=1∑n​fi​(x,y)exp(δi​f#(x,y))

∑ x , y P ^ ( x ) p w ( y ∣ x ) ∑ i = 1 n f i ( x , y ) exp ⁡ ( δ i f # ( x , y ) ) = E p ^ ( f i ) ( 7 ) \sum_{x,y}\hat P(x) p_w(y|x) \sum_{i=1}^n{f_i(x,y)}\exp\Big(\delta_i f^\#(x,y)\Big)=E_{\hat p}(f_i)\;\;\;\;\;\;\;\;\;\;(7) x,y∑​P^(x)pw​(y∣x)i=1∑n​fi​(x,y)exp(δi​f#(x,y))=Ep^​​(fi​)(7)

依次对 δ i \delta_i δi​求解方程(7)从而求出 δ \delta δ。

改进的迭代尺度算法

输入：特征函数 f 1 , f 2 , ⋯ , f n ; f_1,f_2,\cdots,f_n; f1​,f2​,⋯,fn​;对于经验分布函数 P ^ ( X , Y ) \hat P(X,Y) P^(X,Y)，模型 P w ( y ∣ x ) P_w(y|x) Pw​(y∣x)

输出：最优参数值 w i ∗ w_i^* wi∗​；最优模型 P w ∗ P_{w^*} Pw∗​。

对所有 i ∈ { 1 , 2 , ⋯ , n } i\in\{1,2,\cdots,n\} i∈{1,2,⋯,n}，取初值 w i = 0 w_i=0 wi​=0。对每一 i ∈ { 1 , 2 , ⋯ , n } i\in\{1,2,\cdots,n\} i∈{1,2,⋯,n}

(1)令 δ i \delta_i δi​是方程 ∑ x , y P ^ ( x ) p w ( y ∣ x ) ∑ i = 1 n f i ( x , y ) exp ⁡ ( δ i f # ( x , y ) ) = E p ^ ( f i ) \sum_{x,y}\hat P(x) p_w(y|x) \sum_{i=1}^n{f_i(x,y)}\exp\Big(\delta_i f^\#(x,y)\Big)=E_{\hat p}(f_i) x,y∑​P^(x)pw​(y∣x)i=1∑n​fi​(x,y)exp(δi​f#(x,y))=Ep^​​(fi​)的解，这里 f # ( x , y ) = ∑ i f i ( x , y ) f^\#(x,y)=\sum_if_i(x,y) f#(x,y)=i∑​fi​(x,y)

(2)更新 w i w_i wi​值： w i → w i + δ i w_i\rightarrow w_i+\delta_i wi​→wi​+δi​

如果不是所有的 w i w_i wi​都收敛，重复2。

这一算法的关键是(1)，即求解方程(7)中的 δ i \delta_i δi​，如果 f # ( x , y ) f^\#(x,y) f#(x,y)是常数，即对任何 x , y x,y x,y有 f # ( x , y ) = M f^\#(x,y)=M f#(x,y)=M那么 δ i \delta_i δi​可以显示地表示成 δ i = 1 M log ⁡ E p ^ ( f i ) E p ( f i ) \delta_i=\frac1M\log\frac{E_{\hat p}(f_i)}{E_p(f_i)} δi​=M1​logEp​(fi​)Ep^​​(fi​)​如果 f # ( x , y ) f^\#(x,y) f#(x,y)不是常数，那么必须通过数值计算求 δ i \delta_i δi​。简单有效地方法是牛顿法，以 g ( δ i ) = 0 g(\delta_i)=0 g(δi​)=0表示方程（7），牛顿法通过迭代求得 δ i ∗ \delta_i^* δi∗​，使得 g ( δ i ∗ ) = 0 g(\delta^*_i)=0 g(δi∗​)=0迭代公式是 δ i ( k + 1 ) = δ i ( k ) − g ( δ i ( k ) ) g ′ ( δ i ( k ) ) \delta_i^{(k+1)}=\delta_i^{(k)}-\frac{g(\delta_i^{(k)})}{g'(\delta_i^{(k)})} δi(k+1)​=δi(k)​−g′(δi(k)​)g(δi(k)​)​

只要适当的选取初始值 δ i ( 0 ) \delta_i^{(0)} δi(0)​，由于 δ i \delta_i δi​的方程（7）有单根，因此牛顿法恒收敛，而且收敛的速度很快。

另一种方法是拟牛顿法，可以查看附录B

下一章传送门：统计学习方法读书笔记（七）-支持向量机