1. 最大熵原理

最大熵模型（Maximum Entropy Model)是通過(guò)最大熵原理推導(dǎo)實(shí)現(xiàn),那什么是最大熵原理？

熵是隨機(jī)變量不確定性大的度量，不確定性越大，熵值越大；若隨機(jī)變量變?yōu)槎ㄖ?，即某個(gè)值發(fā)生的概率為1，而其它事件都為0，此時(shí)熵值為0，均勻分布是熵值最大的分布，也即“最不確定的分布”。

假設(shè)離散隨機(jī)變量 $X$ 的概率分布是 $P(X)$ ,則其熵為:

$H(P)=-\sum_{x}p(x)logp(x) \tag{1}$

熵滿(mǎn)足如下條件:

$0 \leq H(P) \leq log|X|$
其中, $|X|$ 表示 $X$ 的取值，當(dāng) $X$ 的分布是均勻分布時(shí)，滿(mǎn)足左邊等號(hào)，當(dāng) $X$ 是確定事件時(shí)，滿(mǎn)足左邊的等號(hào)。

從上面可知，最大熵原理認(rèn)為該求解的概率模型滿(mǎn)足如下條件:

滿(mǎn)足事先已約束的條件；
然后在滿(mǎn)足這些條件的模型中選擇熵最大的模型，即讓不確定的信息等可能的發(fā)生；

2. 最大熵模型

將最大熵原理應(yīng)用到分類(lèi)問(wèn)題中即得到最大熵模型。假設(shè)分類(lèi)模型的一個(gè)條件概率分布 $P(Y|X)$ , $X\in\chi\subseteq R^n$ 表示輸入， $X\in\gamma$ 表示輸出。這個(gè)模型表示給定的輸入 $X$ ,以條件概率 $P(Y|X)$ 輸出 $Y$ 。

給定一個(gè)訓(xùn)練數(shù)據(jù)集

$T=\{(x_1, y_1), (x_2,y_2)...(x_N, y_N)\}$

學(xué)習(xí)的目標(biāo)是用最大熵原理選擇最好的模型。

對(duì)于給定訓(xùn)練數(shù)據(jù)集，我們可以確定聯(lián)合分布 $P(X, Y)$ 的經(jīng)驗(yàn)分布 $\tilde P(X,Y)$ 和邊緣分布 $P(X)$ 的經(jīng)驗(yàn)分布 $\tilde P(X)$ ,即：

$\tilde P(X=x, Y=x) = \frac{v(X=x, Y=y)}{N} \\ \tilde P(X=x) = \frac{X(X=x)}{N} \tag{2}$

其中， $v(X=x, Y=y)$ 表示訓(xùn)練數(shù)據(jù)中樣本 $(x, y)$ 出現(xiàn)的頻數(shù)， $V(X=x)$ 表示訓(xùn)練數(shù)據(jù)集中 $x$ 出現(xiàn)的頻數(shù)。 $N$ 表示訓(xùn)練樣本的總?cè)萘俊?/p>

特征函數(shù) $f(x, y)$ 表示輸入 $x$ 和輸出 $y$ 之間的某個(gè)約束。其定義為:

$f(x,y)=\begin{cases} 1,\quad x和y滿(mǎn)足約束\\ 0, \quad x和y不滿(mǎn)足約束 \end{cases} \tag{3}$

特征函數(shù) $f(x,y)$ 關(guān)于經(jīng)驗(yàn)分布 $\tilde P(X, Y)$ 的期望值為:

$E_{\tilde p}(f) = \sum_{x, y} \tilde P(x,y)f(x, y) \tag{4}$

特征函數(shù) $f(x,y)$ 關(guān)于模型 $P(Y|X)$ 和經(jīng)驗(yàn)分布 $\tilde P(X)$ 的期望值為:

$E_{p}(f) = \sum_{x, y} \tilde P(x)P(y|x)f(x, y) \tag{5}$

因?yàn)闄C(jī)器學(xué)習(xí)的目的就是從數(shù)據(jù)集中學(xué)得數(shù)據(jù)中包含的某種內(nèi)在信息，因此我們可以假設(shè)公式4和公式5相等，即

$E_{\tilde p}(f) = E_{p}(f) \\ \sum_{x, y} \tilde P(x,y)f(x, y) = \sum_{x, y} \tilde P(x)P(y|x)f(x, y) \tag{6}$

公式6就作為模型的約束條件，如果有 n 個(gè)特征函數(shù)，則就有 n 個(gè)約束條件。

最大熵模型 假設(shè)滿(mǎn)足所有約束條件的模型集合為

$C=\{P|E_{\tilde p}(f_i) = E_{p}(f_i), i=1,2...n\}$

定義在條件概率分布 $P(Y|X)$ 上的條件熵為:

$H(P) = - \sum_{x,y}\tilde P(x)P(y|x)logP(y|x) \tag{7}$

則模型集合 $C$ 條件熵最大的模型成為最大熵模型

補(bǔ)充

條件概率的熵的公式為
$H(y|x)=-\sum_{x,y}p(x,y)logp(y|x) \tag{8}$

因此最大熵模型如公式7所示。

總之，最大熵模型就是在滿(mǎn)足約束的模型集合中選擇條件概率分布 $P(Y|X)$ 最大的模型。

3. 最大熵模型的學(xué)習(xí)

通過(guò)上述上述的描述，最大熵模型可以形式化為約束最優(yōu)化問(wèn)題，即

$\max_{P \in C} H(P) = -\sum_{x,y}\tilde P(x)P(y|x)\log P(y|x) \\ s.t. \quad E_{\tilde p}(f_i) = E_{p}(f_i), \quad i=1, 2...,n \\ \quad \sum_yP(y|x) = 1 \tag{9}$

按照優(yōu)化習(xí)慣，通常將最大值優(yōu)化轉(zhuǎn)換為最小值優(yōu)化。即
$\max_{P \in C} -H(P) = \sum_{x,y}\tilde P(x)P(y|x)\log P(y|x) \\ s.t. \quad E_{\tilde p}(f_i) = E_{p}(f_i), \quad i=1, 2...,n \\ \quad \sum_yP(y|x) = 1 \tag{10}$

公式10所得出的解就是最大熵模型學(xué)習(xí)的模型。

解決上述約束最優(yōu)化問(wèn)題，我們通過(guò)拉格朗日對(duì)偶性來(lái)進(jìn)行解決。

首先我們引入拉格朗日乘子 $w_0, w_1,w_2...w_n$ ,定義拉格朗日函數(shù) $L(p, w)$ 為
$\begin{aligned} L(P, w) &=-H(P) + w_0(1-\sum_yP(y|x))+\sum_{i=1}^{n}w_i(E_{\tilde p}(f_i) - E_{p}(f_i)) \\ &=\sum_{x,y}\tilde P(x)P(y|x)\log P(y|x) + w_0(1-\sum_yP(y|x)) \\ &+\sum_{i=1}^{n}w_i(\sum_{x,y}\tilde P(x,y)f(x, y) - \sum_{x, y} \tilde P(x)P(y|x)f(x, y)) \end{aligned} \tag{11}$

因此，最優(yōu)化問(wèn)題的原始問(wèn)題為
$\min_{P\in C} \max_{w} L(P,w) \tag{12}$
對(duì)偶問(wèn)題

$\max_{w} \min_{P\in C} L(P,w) \tag{13}$

我們稱(chēng)公式10、11和12為原始問(wèn)題，公式13為原始問(wèn)題的對(duì)偶問(wèn)題，且原始問(wèn)題的解與對(duì)偶問(wèn)題的解是等價(jià)的，因此，公式11的解就是我們求解的模型。

我們首先求解對(duì)偶問(wèn)題公式13內(nèi)部的極小化問(wèn)題 $\min_{P\in C} L(P,w)$ ,該函數(shù)是關(guān)于 $w$ 的函數(shù)，我們將其記作:

$\psi (w) = \min_{P\in C} L(P,w) = L(P_w, w) \tag{14}$

$\psi (w)$ 稱(chēng)為對(duì)偶函數(shù)，同時(shí)其解記為:

$P_w = \arg \min_{p}L(P,w) = P_w(y|x) \tag{15}$

我們可以利用偏導(dǎo)數(shù)來(lái)求解公式15，即

$\begin{aligned} \frac{\partial L(P,w)}{\partial P(y|x)} &= \sum_{x,y}(\tilde P(x) \log P(y|x) + \tilde{P}(x)) -\sum_{y}w_o+\sum_{i=1}^{n}w_i(-\sum_{x,y}\tilde{P}(x)f_{i}(x,y)) \\ &= \sum_{x,y}\tilde{P}(x)(\log P(y|x) + 1) - \sum_{y}w_0-\sum_{x,y}{\tilde{P}(x)\sum_{i=1}^nw_if_i(x,y)} \\ &=\sum_{x,y}\tilde{P}(x)(\log P(y|x) + 1) - \sum_x \tilde{P}(x)\sum_{y}w_0-\sum_{x,y}{\tilde{P}(x)\sum_{i=1}^nw_if_i(x,y)} \\ &= \sum_{x,y}\tilde{P}(x)(\log P(y|x) + 1-w_0-\sum_{i=1}^nw_if_i(x,y)) \end{aligned} \tag{16}$

由于 $L(P,w)$ 是凸函數(shù)，我們我可令上式偏導(dǎo)數(shù)為0，在 $\tilde P(x)>0$ 的情況下，即可求出 $P(y|x)$ , 即：
$\begin{aligned} P(y|x) &=\exp(\sum_{i=1}^{n}w_if_i(x,y)+w_0-1)\\ &=\frac{\exp{\sum_{i=1}^{n}w_if_i(x,y)}}{\exp(1-w_0)} \end{aligned} \tag{17}$

由于在概率論中， $\sum_{y}P(y|x)=1$ ,因此需對(duì)公式17進(jìn)行歸一化，又 $\exp(1-w_0)$ 為常數(shù),因此：

$P_w(y|x)=\frac{1}{Z_w(x)}\exp(\sum_{i=1}^{n}w_if_i(x,y)) \tag{18}$

其中

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

公式18、19表示的模型就是最大熵模型 $P_w=p_w(y|x)$ .然后求解對(duì)偶函數(shù)的極大化問(wèn)題
$\max_{w} \psi (w) \tag{20}$

求得 $w^*$ ,得到最終模型。

4 極大似然估計(jì)

通過(guò)上面一小節(jié)的計(jì)算，我們已經(jīng)求出最大熵模型，但是此時(shí)該模型還是一個(gè)關(guān)于 $w$ 的函數(shù)，我們?nèi)绾吻蟪? $w$ 來(lái)求得最終的模型呢。

我們先來(lái)描述對(duì)數(shù)似然函數(shù)，通過(guò)前面一章的邏輯回歸模型中的最大似然估計(jì)，我們可知對(duì)數(shù)似然函數(shù)和熵在值上互為相反數(shù)，又通過(guò)公式8得知條件概率的熵形式，因此我們可以得知，條件概率分布 $P(Y|X)$ 的對(duì)數(shù)似然函數(shù)

$L_{\tilde P}(P_w) = \sum_{x,y}\tilde{P}(x,y)\log P(y|x) \tag{21}$

我們?cè)贈(zèng)_似然函數(shù)的定義方面證明上述公司的正確性。

在給定數(shù)據(jù)集 $\{(x_1,y_1),(x_2,y_2)...(x_n,y_n)\}$ ,我們可求得當(dāng)前模型的似然函數(shù)為:

$L(\theta)=\prod_{i=1}^n P(x_i, \theta) \tag{22}$

我們假設(shè) $X_i$ 在訓(xùn)練集中出現(xiàn)了 $C(x_i)$ ,因此公式22可以轉(zhuǎn)化為:

$L(\theta)=\prod_{i=1}^k P(x_i, \theta)^{C(x_i)} \tag{23}$

$k$ 表示訓(xùn)練數(shù)據(jù)集中總共有 k 種不同的輸入特征，我們對(duì)上市求其 $\frac{1}{n}$ 次方，得：

$L(\theta)^{\frac{1}{n}}=\prod_{i=1}^k P(x_i, \theta)^{\frac{C(x_i)}{n}} \tag{24}$

對(duì)公式24求對(duì)數(shù)的:

$\begin{aligned} \log L(\theta)^{\frac{1}{n}} &=\log \prod_{i=1}^k P(x_i, \theta)^{\frac{C(x_i)}{n}} \\ &= \sum_{i=1}^k \frac{C(x_i)}{n} \log P(x_i, \theta)\\ \end{aligned} \tag{25}$

因此對(duì)于 $\log L(\theta)^{\frac{1}{n}}$ 和 $\log L(\theta)$ 是等價(jià)的，

因此對(duì)于條件概率分布 $P(Y|X)$ 的對(duì)數(shù)似然函數(shù)

$L_{\tilde P}(P_w) = \sum_{x,y}\tilde{P}(x,y)\log P(y|x) \tag{26}$

對(duì)于公式21-26的推導(dǎo)，不具有嚴(yán)格的樹(shù)學(xué)理論，只是為了理解下面公式27做鋪墊。

一直訓(xùn)練數(shù)據(jù)的經(jīng)驗(yàn)概率分布 $\tilde P(X,Y),$ 條件概率分布 $P(Y|X)$ 的對(duì)數(shù)似然函數(shù)表示為

$\begin{aligned} L_{\tilde P}(P_w) &=\log \prod_{xy}P(y|x)^{\tilde P(x,y)} = \sum_{x,y}\tilde{P}(x,y)\log P(y|x) \end{aligned} \tag{27}$

將公式18和19帶入公式27可得:
$\begin{aligned} L_{\tilde P}(P_w) &=\sum_{x,y}\tilde{P}(x,y)(\sum_{i=1}^{n}w_if_i(x,y)-\log Z_w(x) \\ &=\sum_{x,y}\tilde{P}(x,y)\sum_{i=1}^{n}w_if_i(x,y)-\sum_{x,y}\tilde{P}(x,y)\log Z_w(x) \\ &=\sum_{x,y}\tilde{P}(x,y)\sum_{i=1}^{n}w_if_i(x,y)-\sum_{x}\tilde {P}(x)\log Z_w(x) \end{aligned} \tag{28}$

公式28就是極大似然函數(shù)。上式最后兩步最后一項(xiàng)的轉(zhuǎn)化是因?yàn)? $Z_w(x)$ 是關(guān)于 x 的函數(shù)，所以可以對(duì) $\tilde{P}(x,y)$ 對(duì) $x$ 進(jìn)行累加得到 $\tilde {P}(x)$ .

我們?cè)倏纯磳?duì)偶函數(shù) $\psi (w)$ ,我們將 $P_w(y|x)$ 帶入公式11得:

$\begin{aligned} \psi (w) =& \sum_{x,y}\tilde P(x)P_w(y|x)\log P_w(y|x) + w_0(1-\sum_yP(y|x)) \\ &+\sum_{i=1}^{n}w_i(\sum_{x,y}\tilde P(x,y)f(x, y) - \sum_{x, y} \tilde P(x)P_w(y|x)f(x, y)) \\ =&\sum_{x,y}\tilde P(x)P_w(y|x)\log P_w(y|x) \\ &+\sum_{i=1}^{n}w_i(\sum_{x,y}\tilde P(x,y)f(x, y) - \sum_{x, y} \tilde P(x)P_w(y|x)f(x, y)) \\ =& \sum_{x,y}\tilde P(x,y)\sum_{i=1}^{n}w_if(x, y)+\sum_{x,y}\tilde{P}(x)P_w(y|x)(\log P_w(y|x)-\sum_{i=1}^{n}w_if_i{(x,y)}) \\ =& \sum_{x,y}\tilde P(x,y)\sum_{i=1}^{n}w_if(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}^{n}w_if(x, y)-\sum_{x,y}\tilde{P}(x)\log Z_w(x) \end{aligned} \tag{29}$

公式29第三步到第四步用到下面公式進(jìn)行推導(dǎo):

$P_w(y|x)=\frac{1}{Z_w(x)}\exp(\sum_{i=1}^{n}w_if_i(x,y)) \Rightarrow \log P_w(y|x)=\sum_{i=1}^{n}w_if_i(x,y)-\log Z_w(x)$

倒數(shù)第二步到最后一步的推導(dǎo)用到了 $\sum_{y}P(y|x)=1$ .

比較公式公式28和公式29，可得:

$\psi (w) = L_{\tilde P}(P_w)$

因此，可以證明，最大熵模型學(xué)習(xí)中的對(duì)偶函數(shù)極大化等價(jià)于最大熵模型的極大似然估計(jì)。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

最大熵模型

最大熵模型

1. 最大熵原理

2. 最大熵模型

3. 最大熵模型的學(xué)習(xí)

4 極大似然估計(jì)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

最大熵模型

1. 最大熵原理

2. 最大熵模型

3. 最大熵模型的學(xué)習(xí)

4 極大似然估計(jì)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av