用于分類問題
最大熵模型用于分類問題,其基本假設是:在滿足限制條件的情況下,條件熵最大的模型就是最好的模型。正如一個著名的投資理念“雞蛋不要放在一個籃子裡”。
目标函數是條件熵,我們希望它最大,即條件機率的期望最大。
已知資訊成為目标函數的限制,是客觀存在的,必須得到滿足。其它不作任何假設,越随機越合理。有多少個特征函數,就有多少個限制,再加上條件機率之和為
1
1。
認識條件熵
條件熵是熵的期望,它度量了我們的
Y
Y
Y 在知道了
X
X
X 以後的不确定性,條件熵定義的最原始形式是:
H
(
Y
∣
X
)
=
∑
x
∈
X
p
x
H(Y|X)=\sum_{x\in X} p(x)H(Y|X=x)
H(Y∣X)=x∈X∑p(x)H(Y∣X=x)
或者寫成:
i
=
n
x
i
H(Y|X)=\sum_{i=1}^{n} p(x_i)H(Y|X=x_i)
H(Y∣X)=i=1∑np(xi)H(Y∣X=xi)
條件熵表示在已知随機變量
X 的條件下,
Y 的條件機率分布的熵對随機變量
X 的數學期望。熵是數學期望(資訊量的數學期望),條件熵也是數學期望,是數學期望的數學期望,有點拗口,不妨把定義多看幾遍,就清楚了。
這裡又假設随機變量
Y 有
m
m
m 個取值,将
H
(
∣
=
i
)
H(Y|X=x_i)
H(Y∣X=xi) 用定義式
−
j
m
y
j
log
H(Y|X=x_i) = - \sum_{j=1}^{m} p(y_j|X=x_i)\log p(y_j|X=x_i)
H(Y∣X=xi)=−j=1∑mp(yj∣X=xi)logp(yj∣X=xi)
代入上式,得
KaTeX parse error: No such environment: eqnarray at position 8: \begin{̲e̲q̲n̲a̲r̲r̲a̲y̲}̲ H(Y|X) &=& \su…
即
H(Y|X)=\sum_{i=1}^{n} p(x_i)H(Y|X=x_i) =-\sum_{i=1}^{n}p(x_i) \sum_{j=1}^{m} p(y_j|x_i) \log p(y_j|x_i)
H(Y∣X)=i=1∑np(xi)H(Y∣X=xi)=−i=1∑np(xi)j=1∑mp(yj∣xi)logp(yj∣xi)
條件熵即按一個新的變量的每個值對原變量進行分類,比如《統計學習方法》中将是否同意貸款按照申請人是否有自己的房子分為兩類。然後在每一個小類裡面,都計算熵,然後每一個熵乘以各個類别的機率,然後求和(權重求和)。我們用另一個變量對原變量分類後,原變量的不确定性就會減小了,因為新增了
Y 的資訊,不确定程度減少了多少就是資訊的增益。
經驗條件熵如何計算:
D
A
H(D|A)
H(D∣A)。
KaTeX parse error: No such environment: equation at position 8: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲}̲\begin{split} H…
決策樹中條件熵和最大熵原理中的條件熵
決策樹中特征選擇,希望條件熵越小越好,這樣資訊增益就大,此時我們是在選最佳特征,是在已知特征中找最能把類标厘清楚的特征。
在最大熵原理中,我們希望選擇的模型“越平均越好”,選擇的是機率模型,即在未知的機率模型中,選擇一個除了滿足已知資訊以外,不做任何其它假設的機率模型,我們希望條件熵最大。
了解特征函數
輸入
x
x
x 和輸出
y
y
y 之間的關系,使用特征函數
f
,
f(x, y)
f(x,y) 來表示,可以想象
x 取某個值的時候,
y 就有一個值與之對應,它描述的是輸入變量和輸出變量的關系,用特征函數來刻畫:
f
,
y
{
,
x
與
y
滿
足
某
一
事
實
否
則
f(x,y)=\begin{cases} 1, & x 與 y 滿足某一事實 \\ 0, & 否則 \\ \end{cases}
f(x,y)={1,0,x與y滿足某一事實否則
特征函數是把自變量和因變量的關系都考慮進去的函數。可以在皮果提的文章:最大熵學習筆記(三)最大熵模型 中找到具體的例子,了解特征函數的定義。
還可以參考這篇知乎問答:如何了解最大熵模型裡面的特征?。
公式推導
1、計算兩個經驗分布,所謂經驗分布,就是從訓練資料集中統計出來的頻率值。隻要是經驗分布,我們在表示機率的時候,都在上面加上“一彎”進行差別。從訓練資料集可以得到:
(1)聯合分布
P
P(Y|X)
P(Y∣X) 的經驗分布:
P
~
v
(
,
Y
y
)
N
\widetilde P(X=x,Y=y) = \frac{v(X=x,Y=y)}{N}
P
(X=x,Y=y)=Nv(X=x,Y=y)
(2)邊緣分布
P(X)
P(X) 的經驗分布:
\widetilde P(X=x) = \frac{v(X=x)}{N}
(X=x)=Nv(X=x)
其中 $v(X=x,Y=y) $ 表示訓練樣本中
(x,y)
(x,y) 出現的頻數;
v
v(X=x)
v(X=x) 表示訓練資料集中輸入
x 出現的頻數,
N
N
N 表示訓練樣本容量。
2、通過這兩個經驗分布,建立與特征函數和目标函數的等式,形成限制條件。因為
P(x,y)
P(x,y) 未知,但是可以用
P
~
\widetilde P(x,y)
P
(x,y) 代替,而
P(y|x)
P(y∣x) 為所求,又有
P(x,y)=P(x)P(y|x)
P(x,y)=P(x)P(y∣x),
P(x)
P(x) 也未知,但是可以用
\widetilde P(x)
(x) 代替,于是就有:
(1)特征函數
f(x,y)
f(x,y) 關于經驗分布(訓練資料集的分布)$\widetilde P(X,Y) $ 的期望值:
E
P
~
E_{\widetilde P}(f) = \sum_{x,y}\widetilde P(x,y)f(x,y)
EP
(f)=x,y∑P
(x,y)f(x,y)
(2)特征函數
f(x,y) 關于模型
P(Y∣X) 與經驗分布 $\widetilde P(X) $ 的期望值:
E_{P}(f) =\sum_{x,y} \widetilde P(x)P(y|x)f(x,y)
EP(f)=x,y∑P
(x)P(y∣x)f(x,y)
如果模型能夠擷取從訓練資料集中的資訊,那麼就可以假設這兩個期望值相等。
E_{P}(f) = E_{\widetilde P}(f)
EP(f)=EP
(f)
即:
\sum_{x,y} \widetilde P(x)P(y|x)f(x,y) = \sum_{x,y}\widetilde P(x,y)f(x,y)
x,y∑P
(x)P(y∣x)f(x,y)=x,y∑P
上面的兩個等式作為條件機率的最大熵的限制條件。如果有
n
n
n 個特征函數,那麼就有
n 個限制條件。
于是最大熵模型就可以表示成:
1、目标函數:條件熵,最優化的方向是使其最大。
2、限制條件:
(1)有多少個特征函數,就有多少個限制條件。
(2)條件機率之和為 1。
3、有限制的最大化問題可以使用拉格朗日乘子法。
引入拉格朗日乘子,寫出拉格朗日函數。接下來的步驟和 SVM 是一樣的。
利用拉格朗日對偶性,求解對偶問題。即:原始問題是 $ \min_p \max_w$ 的,對偶問題是
max
w
min
\max_w \min_p
maxwminp 的。
最大熵模型的學習可以歸結為對偶函數的極大化問題。對偶函數的極大化等價于最大熵模型的極大似然估計。
總結:
\sum_{x,y}\widetilde P(x,y)f(x,y) = \sum_{x,y}P(x,y)f(x,y)
(x,y)f(x,y)=x,y∑P(x,y)f(x,y)
左邊
E_{\widetilde P}(f) = \sum_{x,y}\widetilde P(x,y)f(x,y)
(x,y)f(x,y) 表示特征函數
f(x,y)
f(x,y) 在訓練資料集上關于經驗分布
\widetilde P(x,y)
(x,y) 的數學期望;
右邊
E_{P}(f) =\sum_{x,y}P(x,y)f(x,y)
EP(f)=x,y∑P(x,y)f(x,y) 表示特征函數
f(x,y) 在模型上關于理論分布
P(x,y)
P(x,y) 的數學期望。
下面是我的手寫筆記:
最大熵模型的優點
最大熵模型在分類方法裡算是比較優的模型,但是由于它的限制函數的數目一般來說會随着樣本量的增大而增大,導緻樣本量很大的時候,對偶函數優化求解的疊代過程非常慢,scikit-learn 甚至都沒有最大熵模型對應的類庫。但是了解它仍然很有意義,尤其是它和很多分類方法都有千絲萬縷的聯系。
最大熵模型的優點有:
1、最大熵統計模型獲得的是所有滿足限制條件的模型中條件熵極大的模型,作為經典的分類模型時準确率較高;
2、可以靈活地設定限制條件,通過限制條件的多少可以調節模型對未知資料的适應度和對已知資料的拟合程度。
最大熵模型的缺點
由于限制函數數量和樣本數目有關系,導緻疊代過程計算量巨大,實際應用比較難。
參考資料
[1] 李航. 統計學習方法(第 2 版)第 6 章“最大熵模型”. 北京:清華大學出版社,2019.
[2] 吳軍. 數學之美(第 20 章“不要把雞蛋放到一個籃子裡”). 北京:人民郵電出版社,2012.
[3]皮果提的系列文章:
最大熵學習筆記(零)目錄和引言
最大熵學習筆記(一)預備知識
最大熵學習筆記(二)最大熵原理
最大熵學習筆記(三)最大熵模型
最大熵學習筆記(四)模型求解
最大熵學習筆記(五)最優化算法
最大熵學習筆記(六)優缺點分析
以下為草稿,我自己留着備用,讀者可以忽略,歡迎大家批評指正。
函數
−
y = x - 1
y=x−1 與
l
y = ln(x)
y=ln(x) 的圖像:
1、溫暖的蛋殼:最大熵模型
位址:http://47.96.227.134/index.php/2018/06/17/maxentropy/
說明:這篇文章指出了:最大熵模型是一種很抽象的描述,在不同的場景和業務中我們可能需要定義不同的特征函數求出對應的權重值,來解決不同的問題。
2、碼農場:邏輯斯谛回歸與最大熵模型
位址:http://www.hankcs.com/ml/the-logistic-regression-and-the-maximum-entropy-model.html
3、統計學習方法|最大熵原理剖析及實作
位址:https://www.pkudodo.com/2018/12/05/1-7/
4、白馬負金羁:最大熵模型(MaxEnt):萬法歸宗(上)
最大熵模型(MaxEnt):萬法歸宗(下)
5、李航·統計學習方法筆記·第6章 logistic regression與最大熵模型(2)·最大熵模型
6、馬同學:如何了解拉格朗日乘子法?
7、自然語言處理之一:最大熵模型
javascript:void(0)
8、李航統計學習-最大熵模型之我的了解
9、最大熵原理
10、最大熵與邏輯回歸的等價性
12、統計學習-邏輯回歸(LR)和最大熵模型
13、機器學習——最大熵原理
14、最大熵模型與GIS ,IIS算法
15、機器學習筆記(二十)——求解最大熵模型
在機器學習中,
P
P 往往用來表示樣本的真實分布,比如
[
]
[1,0,0]
[1,0,0] 表示目前樣本屬于第一類。
Q
Q
Q 用來表示模型所預測的分布,比如
0.7
0.2
0.1
[0.7,0.2,0.1]
[0.7,0.2,0.1]。即
P 表示真實類别的獨熱編碼,
Q 表示預測的機率分布。
16、機器學習筆記(十九)——最大熵原理和模型定義
17、一步一步了解最大熵模型