邏輯斯諦回歸（邏輯回歸）模型，是統(tǒng)計學習中的經(jīng)典分類方法穆咐。最大熵是概率模型學習的一個準則颤诀，推廣到分類問題得到最大熵模型。邏輯斯諦回歸和最大熵模型都屬于對數(shù)線性模型对湃。

邏輯斯諦回歸模型

邏輯斯諦分布的定義

設 $X$ 是連續(xù)隨機變量崖叫， $X$ 服從邏輯斯諦分布是指 $X$ 具有下列分布函數(shù)和概率密度函數(shù)：
$F(x)=P(X\leq x)=\frac1{1+e^{-(x-\mu)/\gamma}}\tag1$

$f(x)=F'(x)=\frac1{\gamma(1+e^{-(x-\mu)/\gamma})^2}\tag2$

式中， $\mu$ 是位置參數(shù)拍柒， $\gamma\gt0$ 為形狀參數(shù)心傀。

分布函數(shù)和密度函數(shù)如下圖所示

F(x)

f(x)

分布函數(shù)是一條S形的曲線，以點 $(\mu,\frac12)$ 中心對稱拆讯。密度函數(shù)根據(jù) $x=\mu$ 左右對稱脂男，形狀參數(shù)的值越小，在中心附近增長越快种呐。另外宰翅，根據(jù)sigmoid函數(shù)定義
$\mathrm{sigmod}(x)=\frac1{1+e^{-x}}$
概率密度函數(shù)也可以寫成
$f(x)=\mathrm{sigmoid}\bigg((x-\mu)/\mu\bigg)$

二項邏輯斯諦回歸模型

二項邏輯斯諦回歸模型是一種分類模型，由條件概率分布 $P(Y|X)$ 表示爽室， $Y$ 通常取實值0或1汁讼。二項邏輯斯諦回歸模型是如下的條件概率分布：
$P(Y=1|x)=\frac{\exp(w\cdot x+b)}{1+\exp(w\cdot x+b)}\tag3$

$P(Y=0|x)=\frac1{1+\exp(w\cdot x+b)}\tag4$

這里， $x\in\textbf R^n$ 是輸入阔墩， $Y= \{0,1\}$ 是輸出嘿架， $w\in\textbf R^n$ 和 $b\in\textbf R$ 是參數(shù)， $w$ 稱為權值向量啸箫， $b$ 稱為偏置耸彪， $w\cdot x$ 為 $w$ 和 $x$ 的內(nèi)積。

有時為了方便忘苛，將權值向量和輸入向量進行擴充蝉娜，仍記做 $w$ 和 $x$ 唱较， $w=(w^{(1)},w^{(2)},\cdots,w^{(n)},b)^T$ ， $x=(x^{(1)},x^{(2)},\cdots,x^{(n)},1)^T$ 召川，這時绊汹，邏輯斯諦回歸模型概率分布如下：
$P(Y=1|x)=\frac{\exp(w\cdot x)}{1+\exp(w\cdot x)}\tag5$

$P(Y=0|x)=\frac1{1+\exp(w\cdot x)}\tag6$

如果根據(jù) $\mathrm{softmax}$ 函數(shù)的定義
$\mathrm{softmax}(x_1,x_2)=(\frac{e^{x_1}}{\sum_{i=1}^2e^{x_i}},\frac{e^{x_2}}{\sum_{i=1}^2e^{x_i}})$
該條件概率分布還可以寫成
$P(Y=0|x),P(Y=1|x)=\mathrm{softmax}(0,w\cdot x)$
一個事件發(fā)生的幾率，定義為發(fā)生的概率 $p$ 和不發(fā)生概率 $1-p$ 的比值 $\frac p{1-p}$ 扮宠。則該事件的對數(shù)幾率或logit函數(shù)為：
$\mathrm{logit}(p)=\log\frac p{1-p}$
在邏輯斯諦回歸模型中
$\mathrm{logit}(p)=\log\frac p{1-p}=\log\frac{P(Y=1|x)}{1-P(Y=1|x)}=\log\frac{\exp(w\cdot x)}{1}=w\cdot x$
即邏輯斯諦回歸模型中，輸出 $Y=1$ 的對數(shù)幾率是線性函數(shù)狐榔。反之坛增，也就可以用一個線性函數(shù)轉(zhuǎn)化成邏輯斯諦回歸 $Y=1$ 發(fā)生的概率，即：
$P(Y=1|x)=\frac{\exp(w\cdot x)}{1+\exp(w\cdot x)}\tag5$

二項邏輯斯諦回歸模型的參數(shù)估計

邏輯斯諦回歸模型學習時薄腻，對于給定的訓練數(shù)據(jù)集 $T= \{(x_1,y_1),(x_2,y_x),\cdots,(x_n,y_n)\}$ 收捣，其中， $x_i\in\textbf R^n$ 庵楷， $y_i\in \{0,1\}$ 罢艾，可以用極大似然估計法估計模型參數(shù)，從而得到邏輯斯諦回歸模型尽纽。

設
$P(Y=1|x)=\pi(x)$

$P(Y=1|x)=1-\pi(x)$

則似然函數(shù)為
$\prod_{i=1}^N\bigg[[\pi(x_i)]^{y_i}[1-\pi(x_i)]^{1-y_i}\bigg]$
對數(shù)似然函數(shù)為
$L(w)=\sum_{i=1}^N\bigg[y_i(w\cdot x_i)-\log(1+\exp(w\cdot x_i))\bigg]$
對 $L(w)$ 求極大值咐蚯，得到 $w$ 的估計值。

求極值可以求 $\frac{\partial L(w)}{\partial w}=0$ 的解析解弄贿，但有時解析解不太容易求解春锋，所以也可以使用梯度下降或牛頓法這些迭代方法得到近似解。

多項邏輯斯諦回歸

多分類的多項邏輯斯諦回歸模型差凹，假設隨機變量 $Y$ 的取值集合是 $\{1,2,\cdots,K\}$ 期奔，其概率分布為：
$P(Y=k|x)=\frac{\exp(w_k\cdot x)}{1+\sum_{k=1}^{K-1}(w_k\cdot x)},\ \ k=1,2,\cdots,K-1$

$P(Y=K|x)=\frac1{1+\sum_{k=1}^{K-1}(w_k\cdot x)}$

這里， $x\in\textbf R^{n+1}$ 危尿， $w_k\in\textbf R^{n+1}$ 呐萌。即 $K$ 分類的多項邏輯斯諦回歸，需要估計 $K-1$ 個參數(shù)向量 $w_k$ 谊娇。此外肺孤，概率分布也可以看做
$P(Y=1|x),P(Y=2|x),\cdots,P(Y=K|x)=\mathrm{softmax}(w_1\cdot x,w_2\cdot x,\cdots,0)$

最大熵模型

最大熵原理是概率模型學習的一個準則。最大熵原理認為邮绿，學習概率模型時渠旁，在所有可能的概率模型中，熵最大的模型是最好的模型船逮。首先定義熵顾腊。

最大熵原理

假設離散隨機變量 $X$ 的概率分布是 $P(X)$ ，則其熵是
$H(P)=-\sum_xP(x)\log P(x)$
熵滿足下列不等式：
$0\leq H(P)\leq\log|X|$
式中挖胃， $|X|$ 是 $X$ 的取值個數(shù)杂靶，當且僅當 $X$ 的分布是均勻分布時右邊的等號成立梆惯。也就是說，當 $X$ 服從均勻分布時吗垮，熵最大垛吗。在決策樹時，熵也作為特征選擇的一個依據(jù)烁登，熵代表了 $X$ 的不確定性怯屉，在0-1分布中有下圖：

可以看出隨機變量 $X$ 在均勻分布時饵沧，熵最大锨络。最大熵原理的思想就是給予隨機變量 $X$ 的每個取值相同的概率，前提是滿足已知的約束狼牺。例如：

假設隨機變量 $X$ 有5個取值 $\{A,B,C,D,E\}$ 羡儿，并且已知 $P(A)+P(B)=\frac3{10}$ ，要求各個取值的概率是钥。根據(jù)最大熵原理掠归， $P(A)=P(B)=\frac3{20}$ ， $P(C)=P(D)=P(E)=\frac7{30}$ 悄泥。

最大熵模型的定義

最大熵原理是選擇模型的思想虏冻，將其應用到分類模型就叫做最大熵模型。

假設分類模型是一個條件概率分布 $P(Y|X)$ 码泞， $X\in\mathcal X\subseteq\textbf R^n$ 表示輸入兄旬， $Y\in\mathcal Y$ 表示輸出， $\mathcal X$ 和 $\mathcal Y$ 分別是輸入和輸出的集合余寥。這個模型表示的是對于給定的輸入 $X$ 领铐，以條件概率 $P(Y|X)$ 輸出 $Y$ 。

給定一個訓練數(shù)據(jù)集
$T= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$
學習的目標是用最大熵原理選擇最好的分類模型宋舷。

首先定義聯(lián)合分布 $P(X,Y)$ 的經(jīng)驗分布 $\tilde P(X,Y)$ 绪撵，邊緣概率 $P(X)$ 的經(jīng)驗分布 $\tilde P(X)$ 和特征函數(shù) $f(x,y)$
$\tilde P(X=x,Y=y)=\frac{v(X=x,Y=y)}N$

$\tilde P(X=x)=\frac{v(X=x)}N$

其中， $v(X=x,Y=y)$ 表示訓練數(shù)據(jù)中樣本 $(x,y)$ 出現(xiàn)的頻數(shù)祝蝠， $v(X=x)$ 表示訓練數(shù)據(jù)中輸入 $x$ 出現(xiàn)的頻數(shù)音诈， $N$ 表示訓練樣本容量。

特征函數(shù) $f(x,y)$ 描述輸入 $x$ 和輸出 $y$ 之間的某一個事實
$f(x,y)= \begin{cases} 1,&x與y滿足某一事實\\ 0,&否則 \end{cases}$
如果模型能夠獲取訓練數(shù)據(jù)中的信息绎狭，那么就可以假設下面兩個期望相等
$E_{P(X,Y)}(f(x,y))=E_{\tilde P(X,Y)}(f(x,y))$
即
$\sum_{x,y}[P(x,y)f(x,y)]=\sum_{x,y}[\tilde P(x,y)f(x,y)]$
上式中用 $P(x,y)$ 用 $\tilde P(x)P(y|x)$ 表示细溅，就變成了
$\sum_{x,y}[\tilde P(x)P(y|x)f(x,y)]=\sum_{x,y}[\tilde P(x,y)f(x,y)]\tag6$
對于 $n$ 個特征就應該有 $n$ 個上述公式(6)的約束成立，也就是最大熵模型應滿足的 $n$ 個事實儡嘶，在此約束下喇聊，選擇熵最大的分類模型。下面定義最大熵模型：

假設滿足所有約束條件的模型集合為
$\mathcal C= \{P\in\mathcal P|E_P(f_i)=E_{\tilde P}(f_i),\ \ i=1,2,\cdots,n\}\tag7$
定義在條件概率分布 $P(Y|X)$ 上的條件熵為
$H(P(Y|X))=-\sum_{x,y}[\tilde P(x)P(y|x)\log P(y|x)]\tag8$
則模型集合 $\mathcal C$ 中條件熵 $H(P(Y|X))$ 最大的模型稱為最大熵模型蹦狂。式中對數(shù)為自然對數(shù)誓篱。條件熵 $H(P(Y|X))$ 表示在已知 $X$ 的情況下 $Y$ 的不確定性朋贬。

最大熵模型的學習

最大熵模型可以描述為下列約束最優(yōu)化問題：
$\max_{P\in\mathcal C}\ \ H(P)=-\sum_{x,y}[\tilde P(x)P(y|x)\log P(y|x)]\tag9$

$\mathrm{s.t.}\ \ E_P(f_i)=E_{\tilde P}(f_i),\ \ i=1,2,\cdots,n\tag{10}$

$\sum_yP(y|x)=1\tag{11}$

對目標函數(shù)取相反數(shù)，轉(zhuǎn)化成極小化問題
$\min_{P\in\mathcal C}\ \ -H(P)=\sum_{x,y}[\tilde P(x)P(y|x)\log P(y|x)]\tag{12}$

$\mathrm{s.t.}\ \ E_P(f_i)=E_{\tilde P}(f_i),\ \ i=1,2,\cdots,n\tag{13}$

$\sum_yP(y|x)=1\tag{14}$

定義拉格朗日函數(shù)
$\begin{align} L(P,w)&=-H(P)+w_0\bigg(1-\sum_yP(y|x)\bigg)+\sum_{i=1}^n[w_i(E_{\tilde P}(f_i)-E_{\tilde P}(f_i))]\\ &=\sum_{x,y}[\tilde P(x)P(y|x)\log P(y|x)]+w_0\bigg(1-\sum_yP(y|x)\bigg)+\sum_{i=1}^nw_i\bigg(\sum_{x,y}[\tilde P(x,y)f_i(x,y)]-\sum_{x,y}[\tilde P(x)P(y|x)f_i(x,y)]\bigg) \end{align}$
最優(yōu)化的原始就變成了
$\min_{P\in\mathcal C}\max_wL(P,w)$
根據(jù)拉格朗日對偶性窜骄，對偶問題是
$\max_w\min_{P\in\mathcal C}L(P,w)$
可以通過求解對偶問題來求解原始問題锦募，首先求解內(nèi)部極小化問題
$\Psi(w)=\min_{P\in\mathcal C}L(P,w)=L(P_w,w)$
此時可以先把 $w$ 看做常量，其解寫作
$P_w=\arg\min_{P\in\mathcal C}L(P,w)=P_w(y|x)$
要求極小化邻遏，就要求 $L(P,w)$ 對 $P(y|x)$ 的偏導數(shù)糠亩，并使其等于0
$\frac{\partial L(P,w)}{\partial P(y|x)}=\sum_{x,y}\tilde P(x)\bigg(\log P(y|x)+1-w_0-\sum_{i=1}^nw_if_i(x,y)\bigg)=0$
由于 $\tilde P(x)\gt0$ ，所以
$\log P(y|x)+1-w_0-\sum_{i=1}^nw_if_i(x,y)=0$
解得
$P(y|x)=\frac{\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)}{\exp(1-w_0)}$
由于 $\sum_yP(y|x)=1$ 准验，解得
$P_w(y|x)=\frac1{Z_w(x)}\exp\bigg(w_if_i(x,y)\bigg)\tag{15}$
其中
$Z_w(x)=\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)\tag{16}$
$Z_w(x)$ 稱為規(guī)范化因子削解； $f_i(x,y)$ 是特征函數(shù)； $w_i$ 是特征的權值沟娱，由式(15)-(16)表示的模型是 $P_w=P_w(y|x)$ 就是最大熵模型。這里 $w$ 是最大熵模型中的參數(shù)向量腕柜。之后把 $P_w(y|x)$ 代入 $L(P,w)$ 求解對偶問題外部的極大化問題济似，得到模型參數(shù)
$\max_w\Psi(w)=\max_wL(P_w,w)$
其解記為 $w^*$ ，即
$w^*=\arg\max_w\Psi(w)=\arg\max_wP(P_w,w)$
這里可以用最優(yōu)化算法求解 $w^*$ 盏缤，例如梯度下降砰蠢，牛頓法，擬牛頓法唉铜。就得到了最大熵模型 $P_{w^*}(y|x)$ 台舱。

最大熵模型和多項邏輯斯諦回歸

觀察最大熵模型中公式(15)-(16)
$P_w(y|x)=\frac1{Z_w(x)}\exp\bigg(w_if_i(x,y)\bigg)$

$Z_w(x)=\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)$

和多項邏輯斯諦回歸的公式
$P(Y=k|x)=\frac{\exp(w_k\cdot x)}{1+\sum_{k=1}^{K-1}(w_k\cdot x)},\ \ k=1,2,\cdots,K-1$

$P(Y=K|x)=\frac1{1+\sum_{k=1}^{K-1}(w_k\cdot x)}$

可以看出兩者是非常近似的。在多項邏輯斯諦回歸中潭流，對輸入 $x$ 通過權值 $w_k$ 進行了加權求和竞惋，得到第 $k$ 個分類的未規(guī)范化的概率，隨后通過 $\mathrm{softmax}$ 函數(shù)進行了歸一化灰嫉，使其符合概率分布拆宛。而在最大熵模型中，多了一個通過約束的特征函數(shù) $f_i(x,y)$ 對輸入 $x$ 進行特征提取的過程讼撒，然后對特征向量進行加權求和浑厚，得到未規(guī)范化的概率，隨后通過 $\mathrm{softmax}$ 函數(shù)進行了歸一化根盒，使其符合概率分布钳幅，模型的參數(shù) $w_i$ 通過最大熵原理習得。此外炎滞，最大熵模型和多項邏輯斯諦回歸都是對數(shù)線性模型敢艰。

極大似然估計

下面證明求解對偶問題極大化等價于對最大熵模型進行極大似然估計，即求解 $w^*=\arg\max_w\Psi(w)$ 等價于求解條件概率 $P(Y|X)$ 的對數(shù)似然函數(shù)的極大化厂榛。

已知訓練數(shù)據(jù)的經(jīng)驗概率分布 $\tilde P(X,Y)$ 盖矫，條件概率分布 $P(Y|X)$ 的對數(shù)似然函數(shù)表示為
$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)]$
將公式(15)-(16)代入
$\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)\log\frac1{Z_w(x)}\exp(\sum_{i=1}^nw_if_i(x,y)]\\ &=\sum_{x,y}\tilde P(x,y)\sum_{i=1}^nw_if_i(x,y)-\sum_{x,y}\log Z_w(x)\\ &=\sum_{x,y}\tilde P(x,y)\sum_{i=1}^nw_if_i(x)-\sum_{x}\log Z_w(x)\tag{17} \end{align}$
在看對偶函數(shù)
$\Psi(w)=L(P_w,w)=\sum_{x,y}[\tilde P(x)P_w(y|x)\log P_w(y|x)]+w_0\bigg(1-\sum_yP_w(y|x)\bigg)+\\\sum_{i=1}^nw_i\bigg[\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)]\bigg]$
由于 $\sum_yP_w(y|x)=1$ 丽惭，所以
$\begin{align} \Psi(w)&=\sum_{x,y}[\tilde P(x)P_w(y|x)\log P_w(y|x)]+\sum_{i=1}^n\bigg(\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)]\bigg)\\ &=\sum_{x,y}\tilde P(x,y)\sum_{i=1}^nw_if_i(x,y)+\sum_{x,y}\tilde P(x)P_w(y|x)\bigg(\log P_w(y|x)-\sum_{i=1}^nw_if_i(x,y)\bigg)\\ &=\sum_{x,y}\tilde P(x,y)\sum_{i=1}^nw_if_i(x,y)-\sum_{x,y}\tilde P(x)P_w(y|x)\log Z_w(x)\\ &=\sum_{x,y}\tilde P(x,y)\sum_{i=1}^nw_if_i(x)-\sum_{x}\log Z_w(x) \end{align}$
所以
$\Psi(w)=L_{\tilde P}(P_w)$
即求解對偶問題極大化等價于對最大熵模型進行極大似然估計。

所以得到最大熵模型的等價的形式
$P_w(y|x)=\frac1{Z_w(x)}\exp\bigg(w_if_i(x,y)\bigg)$
其中
$Z_w(x)=\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)$
這里辈双， $x\in\textbf R^n$ 為輸入责掏， $y\in \{1,2,\cdots,K\}$ 為輸出， $w\in\textbf R^n$ 為權值向量湃望， $f_i(x,y),\ \ i=1,2,\cdots,n$ 為任意實值特征函數(shù)换衬。

最大熵模型學習的最優(yōu)化算法

求解最大熵模型，需要求解對偶問題的解 $w^*=\arg\max_w\Psi(w)$ 证芭。直接求解析解一般是比較困難的瞳浦，但是可以通過迭代算法，例如改進的迭代尺度法（IIS）废士，梯度下降法叫潦，牛頓法或擬牛頓法得到近似解。下面介紹IIS法和擬牛頓法官硝。

改進的迭代尺度法（IIS）的推導

由公式(17)可知需要最大化模型的對數(shù)似然函數(shù)
$L(w)=\sum_{x,y}\tilde P(x,y)\sum_{i=1}^nw_if_i(x)-\sum_{x}\tilde P(x)\log Z_w(x)$
對于要求解的參數(shù)向量 $w=(w_1,w_2,\cdots,w_n)$ 矗蕊，IIS的想法就是找到一個 $\delta=(\delta_1,\delta_2,\cdots,\delta_n)^T$ 使得更新后的參數(shù)向量 $w+\delta=(w_1+\delta_1,w_2+\delta_2,\cdots,w_n+\delta_n)$ 滿足
$L(w+\delta)-L(w)\gt0$
那么就可以通過不斷的迭代，使得似然函數(shù)逐漸增大氢架，達到極大似然估計的效果傻咖，計算
$L(w+\delta)-L(w)=\sum_{x,y}\tilde P(x,y)\sum_{i=1}^n\delta_if_i(x,y)-\sum_x\tilde P(x)\log\frac{Z_{w+\delta}(x)}{Z_w(x)}$
利用不等式 $-\log\alpha\geq1-\alpha$ ，即
$-\log\frac{Z_{w+\delta}(x)}{Z_w(x)}\geq1-\frac{Z_{w+\delta}(x)}{Z_w(x)}$
得到似然函數(shù)增量的下界
$L(w+\delta)-L(w)\geq\sum_{x,y}\tilde P(x,y)\sum_{i=1}^n\delta_if_i(x,y)+1-\sum_x\tilde P(x)\sum_yP_w(y|x)\exp\sum_{i=1}^n\delta_if_i(x,y)\tag{18}$
將右端記為
$A(\delta|x)=\sum_{x,y}\tilde P(x,y)\sum_{i=1}^n\delta_if_i(x,y)+1-\sum_x\tilde P(x)\sum_yP_w(y|x)\exp\sum_{i=1}^n\delta_if_i(x,y)$
于是有
$L(w+\delta)-L(w)\geq A(\delta|x)$
如果能找到合適的 $\delta$ 使得 $A(\delta|x)$ 提高岖研，那么對數(shù)似然函數(shù)也會提高卿操，但是 $A(\delta|x)$ 中包含了 $n$ 個變量 $\delta_i$ ，同時對其進行優(yōu)化是非常困難的孙援，所以IIS試圖每次只優(yōu)化一個變量 $\delta_i$ 害淤，固定其他變量 $\delta_j,j\neq i$ 。

為了達到這個目的拓售，IIS引入了一個量 $f^\#(x,y)$
$f^\#(x,y)=\sum_i^nf_i(x,y)$
這個量表示所有特征在 $(x,y)$ 出現(xiàn)的次數(shù)筝家。

所以，增量的下界可以改寫為
$A(\delta|x)=\sum_{x,y}\tilde P(x,y)\sum_{i=1}^n\delta_if_i(x,y)+1-\sum_x\tilde P(x)\sum_yP_w(y|x)\exp\bigg(f^\#(x,y)\sum_{i=1}^n\frac{\delta_if_i(x,y)}{f^\#(x,y)}\bigg)\tag{19}$
利用指數(shù)函數(shù)的凸性以及對任意 $i$ 邻辉，有 $\frac{f_i(x,y)}{f^\#(x,y)}\geq0$ 溪王，且 $\sum_i^n\frac{f_i(x,y)}{f^\#(x,y)}=1$ ，根據(jù)Jesen不等式得到
$\exp\bigg(f^\#(x,y)\sum_{i=1}^n\frac{\delta_if_i(x,y)}{f^\#(x,y)}\bigg)\leq\sum_{i=1}^n\frac{f_i(x,y)}{f^\#(x,y)}\exp(\delta_if^\#(x,y))$
所以
$A(\delta|w)\geq\sum_{x,y}\tilde P(x,y)\sum_{i=1}^n\delta_if_i(x,y)+1-\sum_x\tilde P(x)\sum_yP_w(y|x)\sum_{i=1}^n\frac{f_i(x,y)}{f^\#(x,y)}\exp(\delta_if^\#(x,y))$
記右端
$B(\delta|w)=\sum_{x,y}\tilde P(x,y)\sum_{i=1}^n\delta_if_i(x,y)+1-\sum_x\tilde P(x)\sum_yP_w(y|x)\sum_{i=1}^n\frac{f_i(x,y)}{f^\#(x,y)}\exp(\delta_if^\#(x,y))\tag{20}$
$B(\delta|w)$ 是對數(shù)似然函數(shù)增量的一個新的下界值骇。求 $B(\delta|w)$ 對 $\delta_i$ 的偏導
$\frac{\partial B(\delta|w)}{\partial\delta_i}=\sum_{x,y}\tilde P(x,y)f_i(x,y)-\sum_x\tilde P(x)\sum_yP_w(y|x)f_i(x,y)\exp(\delta_if^\#(x,y))=0\tag{21}$
上面的方程中除了 $\delta_i$ 沒有其他變量莹菱，所以可以對 $\delta_i$ 進行優(yōu)化，然后以同樣的方式依次對其他 $\delta_j$ 進行優(yōu)化吱瘩。

改進的迭代尺度法（IIS）的描述

輸入：特征函數(shù) $f_1,f_2,\cdots,f_n$ 道伟；經(jīng)驗分布 $\tilde P(X,Y)$ ，模型 $P_w(y|x)$

輸出：最優(yōu)參數(shù)值 $w_i^*$ ；最優(yōu)模型 $P_{w^*}$ 蜜徽。

（1）對所有 $i\in \{1,2,\cdots,n\}$ 祝懂，取初值 $w_i=0$

（2）對每一 $i\in \{1,2,\cdots,n\}$ ：

求解方程(21)
$\sum_{x,y}\tilde P(x,y)f_i(x,y)-\sum_x\tilde P(x)\sum_yP_w(y|x)f_i(x,y)\exp(\delta_if^\#(x,y))=0$
其中
$f^\#(x,y)=\sum_i^nf_i(x,y)$

$P_w(y|x)=\frac1{Z_w(x)}\exp\bigg(w_if_i(x,y)\bigg)$

$Z_w(x)=\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)$

更新 $w_i$ 的值： $w_i\leftarrow w_i+\delta_i$

（3）如果不是所有 $w_i$ 都收斂，重復步(2)拘鞋。

在上述算法中砚蓬，如果 $f^\#(x,y)$ 是常數(shù)，且 $f^\#(x,y)=M$ （即所有特征在任意 $(x,y)$ 出現(xiàn)的次數(shù)都是 $M$ 次盆色， $f^\#(x,y)$ 與 $x,y$ 取值無關灰蛙， $f^\#(x,y)$ 可以提到求和 $\sum_{x,y}$ 的外面），根據(jù)方程(21)則 $\delta_i$ 可以直接計算
$\begin{align} \exp(\delta_if^\#(x,y))&=\frac{\sum_{x,y}\tilde P(x,y)f_i(x,y)}{\sum_x\tilde P(x)\sum_yP_w(y|x)f_i(x,y)}=\frac{\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)}=\frac{\sum_{x,y}\tilde P(x,y)f_i(x,y)}{\sum_{x,y}P(x,y)f_i(x,y)}=\frac{E_{\tilde P(X,Y)}(f_i)}{E_{P(X,Y)}(f_i)}\\ &=\frac{E_{\tilde P}(f_i)}{E_P(f_i)} \end{align}$
所以
$\delta_i=\frac1{f^\#(x,y)}\log\frac{E_{\tilde P}(f_i)}{E_P(f_i)}=\frac1M\log\frac{E_{\tilde P}(f_i)}{E_P(f_i)}$

如果 $f^\#(x,y)$ 不是常數(shù)隔躲，根據(jù)方程(21)
$\sum_{x,y}\tilde P(x,y)f_i(x,y)-\sum_x\tilde P(x)\sum_yP_w(y|x)f_i(x,y)\exp(\delta_if^\#(x,y))=0$
即
$E_{\tilde P}(f_i)-\sum_{x,y}\bigg(\tilde P(x)P_w(y|x)f_i(x,y)\exp(\delta_if^\#(x,y))\bigg)=0$
令左端等于 $g(\delta_i)$
$g(\delta_i)=E_{\tilde P}(f_i)-\sum_{x,y}\bigg(\tilde P(x)P_w(y|x)f_i(x,y)\exp(\delta_if^\#(x,y))\bigg)$
這時候就需要求解方程 $g(\delta_i)=0$ 的解摩梧。這是個一元方程，可以直接求解宣旱，也可以通過牛頓法迭代公式
$\delta_i^{(k+1)}=\delta_i^{(k)}-\frac{g(\delta_i^{(k)})}{g'(\delta_i^{(k)})}\tag{22}$
解方程仅父。

擬牛頓法

最大熵模型的學習還可以用擬牛頓法。

對于最大熵模型：
$P_w(y|x)=\frac{\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)}{Z(x)}=\frac{\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)}{\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)}$
目標是最大化對數(shù)似然函數(shù)：
$L(w)=\sum_{x,y}\tilde P(x,y)\sum_{i=1}^nw_if_i(x)-\sum_{x}\log\tilde P(x)\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)$
對其取相反數(shù)浑吟，得到擬牛頓法需要最小化的目標函數(shù)：
$\min_{w\in\textbf R^n}\ \ f(w)=\sum_{x}\log\tilde P(x)\sum_y\exp\bigg(\sum_{i=1}^nw_if_i(x,y)\bigg)-\sum_{x,y}\tilde P(x,y)\sum_{i=1}^nw_if_i(x)\tag{23}$
梯度
$\frac{\partial f(w)}{\partial w_i}=\sum_{x,y}\tilde P(x)P_w(y|x)f_i(x,y)-E_{\tilde P}(f_i)=E_{P}(f_i)-E_{\tilde P}(f_i),\ \ i=1,2,\cdots,n$

最大熵模型學習的BFGS算法

輸入：特征函數(shù) $f_1,f_2,\cdots,f_n$ 驾霜；經(jīng)驗分布 $\tilde P(x,y)$ ，目標函數(shù) $f(w)$ 买置，梯度 $g(w)=\nabla f(w)$ ，精度要求 $\varepsilon$ 强霎；

輸出：最優(yōu)參數(shù)值 $w^*$ 忿项；最優(yōu)模型 $P_{w^*}(y|x)$ 。

（1）選定初始點 $w^{(0)}$ 城舞，取 $B_0$ 為正定對稱矩陣轩触，置 $k=0$

（2）計算 $g_k=g(w^{(k)})$ 。若 $||g_k||\lt\varepsilon$ 家夺，則停止計算脱柱，得 $w^*=w^{(k)}$ ；否則轉(zhuǎn)(3)

（3）由 $B_kp_k=-g_k$ 求出 $p_k$

（4）一維搜索：求 $\lambda_k$ 使得
$f(w^{(k)}+\lambda_kp_k)=\min_{\lambda_k\geq0}f(w^{(k)}+\lambda p_k)$
（5）置 $w^{(k+1)}=w^{(k)}+\lambda_kp_k$

（6）計算 $g_{k+1}=g(w^{(k+1)})$ 拉馋，若 $||g_{k+1}||\leq\varepsilon$ 榨为，則停止計算，得 $w^*=w^{(k+1)}$ 煌茴；否則随闺，按下式求出 $B_{k+1}$ ：
$B_{k+1}=B_k+\frac{y_ky_k^T}{y_k^T\delta_k}-\frac{B_k\delta_k\delta_k^TB_k}{\delta_k^TB_k\delta_k}$
其中，
$y_k=g_{k+1}-g_k$