最大熵模型

最大熵模型

0.引言

這部分內(nèi)容主要是從七月在線的課程上學(xué)習(xí)到的屑宠,算是自己的學(xué)習(xí)筆記攘滩。
在介紹最大熵模型和EM算法之前首先要明確幾個(gè)熵的概念,然后再來研究什么是最大熵尸红,什么是最大熵模型纳账,什么是EM算法逛薇。一開始比較心急,直接去看EM算法疏虫,到頭來發(fā)現(xiàn)一臉懵逼永罚,還是要回來從基礎(chǔ)學(xué)起。萬丈高樓莫非平地起卧秘!本篇筆記主要介紹熵呢袱、聯(lián)合熵、條件熵翅敌、互信息羞福、相對(duì)熵(KL散度)和交叉熵。這里先給出個(gè)Venn圖蚯涮,后面會(huì)用到治专,圖片來自百度,侵權(quán)刪遭顶。


.1531022543542.png

信息增益在決策樹中介紹张峰,最大熵模型之后再來更。

1.各種熵的定義

1.1信息量

為了解釋熵棒旗,首先要引入“信息量”這個(gè)詞喘批。直觀上理解,信息量可以度量一個(gè)事件包含的信息铣揉。先給出公式饶深,然后結(jié)合例子來理解。
信息量的定義:
h(x_{i})=-log_{2}p(x_{i})=log_{2}\frac{1}{p(x_{i})}
例子:比如有兩個(gè)事件逛拱,狗咬了人與人咬了狗粥喜,那很明顯狗咬人這件事情概率大,人咬了狗這件事情概率小橘券,所以可以通過公式來分析。log是一個(gè)單調(diào)遞增的凹函數(shù),因此公式中p(x_{i})越大則信息量h(x_{i})越信越ⅰ锋华;p(x_{i})越小則信息量h(x_{i})越大。例子中箭窜,狗咬人的信息量就很小毯焕,人咬狗的信息量就很大』怯#總而言之信息量與概率成反比纳猫,概率越低則信息量越大,概率越大信息量則越小竹捉。

1.2熵——由信息量引出

有了信息量的基礎(chǔ)芜辕,就可以用來解釋熵是什么東西。簡(jiǎn)單的一句話來解釋就是 “熵是信息量的期望”块差,先給出公式:
熵的定義:
H(X)=-\sum_{i=1}^{n}p(x_{i})log_{2}p(x_{i})=\sum_{i=1}^{n}p(x_{i})\frac{1}{p(x_{i})}
可以看到侵续,事件的概率乘上這個(gè)時(shí)間的信息量再求和,那就是期望的定義憨闰。熵能夠反映事件的不確定性状蜗,不確定性與熵成正比關(guān)系。

1.3聯(lián)合熵

聯(lián)合熵實(shí)際上是表示兩個(gè)變量或者多個(gè)變量熵的并集鹉动。給出公式:
多變量X=\{x_1,x_2,...,x_n\}聯(lián)合熵的定義:
H(x_1,x_2,...,x_n)=-\sum_{i=1}^{n}\sum_{j=1}^{n}...\sum_{k=1}^{n}p(x_{1i},x_{2j},...,x_{nk})log_{2}p(x_{1i},x_{2j},...,x_{nk})

性質(zhì)1:H(x_1,x_2,...,x_n)\geqslant max\big[H(x_1),H(x_2)...,H(x_n)\big]
性質(zhì)2:H(x_1,x_2,...,x_n)\leqslant H(x_1)+H(x_2)+...+H(x_n)

1.4條件熵

條件熵可以從引言部分中給出的Venn圖中可以直觀地理解轧坎,由于個(gè)人能力有限,無法用通俗的語(yǔ)言來解釋泽示。還是用公式來描述其含義比較準(zhǔn)確缸血。
條件熵的定義:
H(Y|X)=-\sum_{i=1}^{n}\sum_{j=1}^{n}p(x_i,y_j)log\frac{p(x_i)}{p(x_i,y_j)}
推導(dǎo)一波:
\begin{aligned} H(Y|X) &=-\sum_{i=1}^{n}\sum_{j=1}^{n}p(x_i)p(y_j|x_i)logp(y_j|x_i)\\ &=-\sum_{i=1}^{n}\sum_{j=1}^{n}p(x_i,y_j)logp(y_j|x_i) \\ &=-\sum_{i=1}^{n}\sum_{j=1}^{n}p(x_i,y_j)log\frac{p(x_i)}{p(x_i,y_j)} \\ \end{aligned}
條件熵的兩種含義:
H(X|Y)=H(X,Y)-H(Y)
H(X|Y)=H(X,Y)-I(X,Y)
第一種含義是說從聯(lián)合熵H(X,Y)中減去熵H(Y)第二中含義是說熵H(Y)減去互信息I(X,Y). 其中,互信息就是指兩個(gè)熵的交集边琉,接下來馬上介紹互信息属百。

1.5互信息

互信息的含義可以通過引言部分的Venn圖理解一下,實(shí)際上就是兩個(gè)熵的交集变姨。給出公式:
互信息的定義:
I(X,Y)=-\sum_{i=1}^{n}\sum_{j=1}^{n}p(x_i,y_j)log\frac{p(x_i,y_j)}{p(x_i)p(y_j)}
特點(diǎn):互信息常用于機(jī)器學(xué)習(xí)中的特征選擇和特征關(guān)聯(lián)性分析族扰。互信息刻畫了兩個(gè)變量之間的非線性相關(guān)性定欧,而概率論中的相關(guān)性\rho=\frac{cov(X,Y)}{\sqrt{var(X)}\sqrt{var(Y)}}用來刻畫線性相關(guān)性

1.6相對(duì)熵(KL散度)

KL散度是什么渔呵?是用來做什么的?

KL散度用來刻畫兩個(gè)分布之間的差異性砍鸠,可參考MLPR一書中對(duì)貝葉斯的描述扩氢。有很多類似的度量?jī)蓚€(gè)分布P和Q的方法,如KL(P||Q),\ Wase(P,Q),\ MMD,\ kernel\ hilbert\ distance(P||Q),這里只是mark一下爷辱,目前我還沒有逐一去研究過录豺,這里僅討論KL散度朦肘。

為什么要用KL散度比較兩個(gè)分布之間的差異性?

為什么需要用KL散度來比較兩個(gè)分布之間的差異性呢双饥?在這個(gè)問題之前還有問題媒抠,什么是兩個(gè)分布?怎么就來了兩個(gè)分布咏花?答案是實(shí)際的應(yīng)用問題引出的趴生。機(jī)器學(xué)習(xí)中有時(shí)候需要比較兩個(gè)樣本集的差異,按照經(jīng)驗(yàn)比較差異那就可以用一些范數(shù)距離來求解昏翰,如用一階范數(shù)\sum||x_i-y_i||或者二階范數(shù)\sum||x_i-y_i||^2直接來計(jì)算不久OK了嗎苍匆?當(dāng)然,用范數(shù)來做有一定的道理棚菊,也是可以的浸踩,但是有一個(gè)先決條件——“兩個(gè)數(shù)據(jù)集中的樣本能夠逐一對(duì)應(yīng)”。如果不滿足這個(gè)先決條件窍株,那么用范數(shù)來度量差異性就是不合理的民轴。實(shí)際的應(yīng)用中,很難保證兩個(gè)樣本集中的樣本能夠一一對(duì)應(yīng)球订,因此用范數(shù)距離比較差異的方法就不可行了后裸。那么就換一種思路,我用兩個(gè)樣本集的分布來比較差異性冒滩,這樣就回答了“兩個(gè)分布怎么來的”這個(gè)問題微驶。

再回答標(biāo)題中的問題,為什么需要用KL散度來比較兩個(gè)分布之間的差異性呢开睡?答案就很簡(jiǎn)單了因苹,KL散度只是很多種比較分布差異性的一種,我們這里討論熵的時(shí)候就用到了相對(duì)熵篇恒,那就是KL散度扶檐。條條大路通羅馬,KL散度只是其中一種方法胁艰。

相對(duì)熵的推導(dǎo)

假設(shè)有兩個(gè)分布P和Q款筑,我們需要求他們的相對(duì)熵,那么用公式可以表示為
相對(duì)熵的定義:
KL(P||Q)=D(P||Q)=\sum_{i=1}^{n}p(x_i)log\frac{p(x_i)}{q(x_i)}
性質(zhì)1:D(P||Q)\neq D(Q||P)
性質(zhì)2:隨著D(P||Q)的增大腾么,P和Q兩個(gè)分布的差異會(huì)非常明顯
推導(dǎo)一波:D(P||Q)=\sum_{i=1}^{n}p(x_i)log\frac{p(x_i)}{q(x_i)}為了方便進(jìn)一步的推導(dǎo)奈梳,我們令y_i=\frac{q(x_i)}{p(x_i)}, 則\frac{1}{y_i}=\frac{p(x_i)}{q(x_i)}; 令f(y_i)=log(y_i)則有
D(P||Q)=\sum_{i=1}^{n}p(x_i)log\frac{1}{y_i}=-\sum_{i=1}^{n}p(x_i)logy_i
由于log函數(shù)是一個(gè)凹函數(shù),因此根據(jù)凹函數(shù)的詹森不等式E[f(x)]\leqslant f[EX]解虱,可以對(duì)進(jìn)一步推導(dǎo):
\begin{aligned}-D(P||Q)\sum_{i=1}^{n}p(x_i)logy_i &\leqslant log\sum_{i=1}^{n}p(x_i)y_i\\ &=log\sum_{i=1}^{n}p(x_i)\frac{q(x_i)}{p(x_i)}\\ &=log\sum_{i=1}^{n}q(x_i)\\ &=log1\\&=0\\ \end{aligned}
其中\sum_{i=1}^{n}q(x_i)=1攘须。通過推導(dǎo)可以發(fā)現(xiàn)
D(P||Q)\geqslant 0
證畢!

1.7交叉熵

交叉熵可以用來計(jì)算學(xué)習(xí)模型分布與訓(xùn)練分布之間的差異殴泰,交叉熵廣泛用于邏輯回歸的Sigmoid和Softmax函數(shù)中作為損失函數(shù)使用于宙。(這句話引自https://www.cnblogs.com/kyrieng/p/8694705.html浮驳,感謝大佬的解讀)給出公式:
交叉熵的定義
CH(P,Q)=-\sum_{i=1}^{n}p(x_i)logq(x_i)
實(shí)際上交叉熵還可以這樣理解:
\begin{aligned}CH(P,Q) &=-\sum_{i=1}^{n}p(x_i)logp(x_i)+\sum_{i=1}^{n}p(x_i)logp(x_i)-\sum_{i=1}^{n}p(x_i)logq(x_i)\\ &=-\sum_{i=1}^{n}p(x_i)logp(x_i)+\sum_{i=1}^{n}p(x_i)log\frac{p(x_i)}{q(x_i)}\\ &=H(X)+D(P||Q)\\\end{aligned}
因此,交叉熵可以看做是熵加上KL散度.

1.8信息增益

決策樹中介紹(還未更)

1.9最大熵

在介紹最大熵之前限煞,首先來明確一下事件概率的經(jīng)驗(yàn)值和理論值

事件概率的經(jīng)驗(yàn)值與理論值

經(jīng)驗(yàn)值:
假設(shè)有這樣一個(gè)數(shù)據(jù)集T={(x_,y_1),...(x_n,y_n)}抹恳,我們用\hat{p}(x_i,y_i)來表示從包含n個(gè)樣本的數(shù)據(jù)集中樣本(x_i,y_i)所占的比例。這個(gè)\hat{p}(x_i,y_i)就是我們的經(jīng)驗(yàn)值署驻,實(shí)際上也就是我們從數(shù)據(jù)中訓(xùn)練得到的值。
\hat{p}(x_i,y_i)=\frac{num(x_i,y_i)}{n}
理論值:理論上這個(gè)事件的概率應(yīng)該如何表示呢健霹?實(shí)際上這個(gè)問題在很早以前就學(xué)過了旺上。就是拋硬幣的例子,例如拋100次出現(xiàn)30次正面糖埋,拋1000次出現(xiàn)400次正面宣吱,拋10000次出現(xiàn)4800次正面....拋n\to\infty次的時(shí)候出現(xiàn)\frac{n}{2}次正面。因此瞳别,最后逼近極限的\frac{n}{2}就是拋硬幣例子中概率的理論值征候。在考慮我們的數(shù)據(jù)集T={(x_,y_1),...(x_n,y_n)},在這個(gè)例子中事件(x_i,y_i)的理論概率值就是數(shù)據(jù)集T中的樣本無窮多的時(shí)候\hat{p}(x_i,y_i)\approx p(x_i,y_i).用公式來描述就是:p(x_i,y_i)=\lim_{n\to\infty}\hat{p}(x_i,y_i)

最大熵原則

通過前面幾節(jié)對(duì)熵的介紹祟敛,可以知道熵表示事件的不確定性疤坝,熵越大則不確定性越大。如果有A,B,C三件事情馆铁,通過已有數(shù)據(jù)測(cè)量發(fā)現(xiàn)他們發(fā)生的概率都是三分之一跑揉。那么問題來了,現(xiàn)在又發(fā)生了一個(gè)事件埠巨,請(qǐng)問到底是是A历谍,B,C其中的哪件事情辣垒?要回答這個(gè)問題就先來看看最大熵原則是怎么說的
最大熵原則是這樣一句話:承認(rèn)已知數(shù)據(jù)望侈,對(duì)未知數(shù)據(jù)無偏見。
通過這句話勋桶,我們?cè)诶又兴姓J(rèn)的就是“A,B,C三件事情脱衙,通過已有數(shù)據(jù)測(cè)量發(fā)現(xiàn)他們發(fā)生的概率都是三分之一”,對(duì)未知數(shù)據(jù)無偏見意思就是哥遮,再來一個(gè)事件我們主觀地認(rèn)為它可能會(huì)是哪個(gè)事件岂丘。

最大熵如何應(yīng)用

通過上面的例子可能會(huì)有兩個(gè)問題,最大熵到底有什么用眠饮?如何應(yīng)用最大熵奥帘?那么下面的例子來解釋這兩個(gè)問題。
插播一條李航《統(tǒng)計(jì)學(xué)習(xí)方法》中對(duì)最大熵原理是這樣講的“最大熵原理認(rèn)為仪召,學(xué)習(xí)概率模型時(shí)寨蹋,在所有可能的概率模型中松蒜,熵最大的模型是最好的模型”
先回憶條件熵:H(Y|X)=-\sum_{i=1}^{n}\sum_{j=1}^{n}p(x_i,y_j)log(p(y_j|x_i))最大熵怎么用呢?我們可以用最大熵來確定事件的概率已旧,然后通過概率來確定事件的歸屬類別秸苗。通俗地將就是可以通過對(duì)數(shù)據(jù)進(jìn)行分析后進(jìn)行參數(shù)估計(jì)。
用上面的條件熵可以有:
p^{*}(y|x)=argmax\{H(y|x)\}這個(gè)式子的意思就是:求解p^{*}(y|x)运褪,使得熵H(y|x)最大惊楼。實(shí)際上,這個(gè)式子就引出了最大熵模型的目標(biāo)秸讹。再定義一個(gè)特征函數(shù)就構(gòu)成了最大熵問題的清單檀咙。特征函數(shù)是什么呢?可以理解為數(shù)據(jù)的特征對(duì)估計(jì)結(jié)果的映射關(guān)系璃诀。接下來給出最大熵問題的清單:
\begin{cases} H(y|x)=-\sum_x\sum_y p(x,y)logp(y|x)\\ p^{*}(y|x)=argmax\{H(y|x)\}\\ f_i(x,y)= \begin{cases} 1, &x=x_0,y=y_0\\ 0,&other\ values\\ \end{cases}\\ \end{cases}
st.\begin{cases}\sum_{y}p(y|x)=1\\E(f_i)=\hat{E}(f_i)\end{cases}
接下來弧可,有目標(biāo)函數(shù),有約束劣欢,那就可以用拉格朗日朗日乘子法求解棕诵。可以看到凿将,這里又引入了一個(gè)經(jīng)驗(yàn)值\hat{E}(f_i)校套,它和理想值E(f_i)相等是一個(gè)約束條件。用公式來描述:\hat{E}(f_i)=\sum_{i=1}^{n}\sum_{j=1}^{n}\hat{p}(x_i,y_j)f_i(x_i,y_j)=\sum_{i=1}^{n}\sum_{j=1}^{n}\hat{p}(x)p(y|x)f_i(x_i,y_j)
E(f_i)=\sum_{i=1}^{n}\sum_{j=1}^{n}p(x_i,y_j)f_i(x_i,y_j)=\sum_{i=1}^{n}\sum_{j=1}^{n}p(x)p(y|x)f_i(x_i,y_j)
開始構(gòu)造拉格朗日函數(shù):\begin{aligned}L(p(y|x),\lambda) &=H(y|x)+\sum_{i=1}^{m}\lambda_i[E(f_i)-\hat{E}(f_i)]+\lambda_0(\sum_{j=1}^{n}p(y_j|x)-1)\\ & =\sum_{x}\sum_{y}p(y|x)p(x)log\frac{1}{p(y|x)}+\sum_{i=1}^{m}\lambda_i\sum_x\sum_yf_i(x,y)[p(x,y)-\hat{p}(x,y)]+\lambda_0\big[\sum_{j=1}^{n}p(y_j|x)-1\big]\\ &=\sum_{x}\sum_{y}p(y|x)p(x)log\frac{1}{p(y|x)}+\sum_{i=1}^{m}\lambda_i\sum_x\sum_yf_i(x,y)[\hat{p}(x)p(y|x)-p(x,y)]+\lambda_0\big[\sum_{j=1}^{n}p(y_j|x)-1\big]\\ \end{aligned}
對(duì)p(y|x)求偏導(dǎo):
\frac{\partial L}{\partial p(y|x)}=p(x)\big[log\frac{1}{p(y|x)}-1\big]+\sum_{i=1}\lambda_i\hat{p}(x)f_i(x,y)
\frac{\partial L}{\partial p(y|x)}=0則可以推導(dǎo)得到:
p^{*}(y|x)=e^{\sum_{i=1}^{n}\lambda_if_i(x,y)-\frac{\lambda_0}{\hat{p}(x)}-1}=e^{\sum_{i=1}^{n}\lambda_if_i(x,y)}e^{-\frac{\lambda_0}{\hat{p}(x)}-1}
\frac{1}{z}=e^{-\frac{\lambda_0}{\hat{p}(x)}-1}則有:
p^{*}(y|x)=\frac{1}{z}e^{\sum_{i=1}^{n}\lambda_if_i(x,y)}
這樣丸相,我們就得到了最終所要估計(jì)的概率p^{*}(y|x).

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末搔确,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子灭忠,更是在濱河造成了極大的恐慌膳算,老刑警劉巖,帶你破解...
    沈念sama閱讀 216,372評(píng)論 6 498
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件弛作,死亡現(xiàn)場(chǎng)離奇詭異涕蜂,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)映琳,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,368評(píng)論 3 392
  • 文/潘曉璐 我一進(jìn)店門机隙,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人萨西,你說我怎么就攤上這事有鹿。” “怎么了谎脯?”我有些...
    開封第一講書人閱讀 162,415評(píng)論 0 353
  • 文/不壞的土叔 我叫張陵葱跋,是天一觀的道長(zhǎng)。 經(jīng)常有香客問我,道長(zhǎng)娱俺,這世上最難降的妖魔是什么稍味? 我笑而不...
    開封第一講書人閱讀 58,157評(píng)論 1 292
  • 正文 為了忘掉前任,我火速辦了婚禮荠卷,結(jié)果婚禮上模庐,老公的妹妹穿的比我還像新娘。我一直安慰自己油宜,他們只是感情好掂碱,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,171評(píng)論 6 388
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著慎冤,像睡著了一般顶吮。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上粪薛,一...
    開封第一講書人閱讀 51,125評(píng)論 1 297
  • 那天,我揣著相機(jī)與錄音搏恤,去河邊找鬼违寿。 笑死,一個(gè)胖子當(dāng)著我的面吹牛熟空,可吹牛的內(nèi)容都是我干的藤巢。 我是一名探鬼主播,決...
    沈念sama閱讀 40,028評(píng)論 3 417
  • 文/蒼蘭香墨 我猛地睜開眼息罗,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼掂咒!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起迈喉,我...
    開封第一講書人閱讀 38,887評(píng)論 0 274
  • 序言:老撾萬榮一對(duì)情侶失蹤绍刮,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后挨摸,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體孩革,經(jīng)...
    沈念sama閱讀 45,310評(píng)論 1 310
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,533評(píng)論 2 332
  • 正文 我和宋清朗相戀三年得运,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了膝蜈。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 39,690評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡熔掺,死狀恐怖饱搏,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情置逻,我是刑警寧澤推沸,帶...
    沈念sama閱讀 35,411評(píng)論 5 343
  • 正文 年R本政府宣布,位于F島的核電站,受9級(jí)特大地震影響坤学,放射性物質(zhì)發(fā)生泄漏疯坤。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,004評(píng)論 3 325
  • 文/蒙蒙 一深浮、第九天 我趴在偏房一處隱蔽的房頂上張望压怠。 院中可真熱鬧,春花似錦飞苇、人聲如沸菌瘫。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,659評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)雨让。三九已至,卻和暖如春忿等,著一層夾襖步出監(jiān)牢的瞬間栖忠,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,812評(píng)論 1 268
  • 我被黑心中介騙來泰國(guó)打工贸街, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留庵寞,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 47,693評(píng)論 2 368
  • 正文 我出身青樓薛匪,卻偏偏與公主長(zhǎng)得像捐川,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子逸尖,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,577評(píng)論 2 353