最大熵

一、熵

物理學概念

宏觀上：熱力學定律——體系的熵變等于可逆過程吸收或耗散的熱量除以它的絕對溫度（克

勞修斯，1865）

微觀上：熵是大量微觀粒子的位置和速度的分布概率的函數(shù)，是描述系統(tǒng)中大量微觀粒子的

無序性的宏觀參數(shù)（波爾茲曼，1872）

結(jié)論：熵是描述事物無序性的參數(shù)，熵越大則無序。

二、熵在自然界的變化規(guī)律——熵增原理

一個孤立系統(tǒng)的熵，自發(fā)性地趨于極大，隨著熵的增加，有序狀態(tài)逐步變?yōu)榛煦鐮顟B(tài)，不可

能自發(fā)地產(chǎn)生新的有序結(jié)構(gòu)。

當熵處于最小值,即能量集中程度最高、有效能量處于最大值時,那么整個系統(tǒng)也處于最有

序的狀態(tài),相反為最無序狀態(tài)。

熵增原理預(yù)示著自然界越變越無序

三、信息熵

（1）和熵的聯(lián)系——熵是描述客觀事物無序性的參數(shù)。香農(nóng)認為信息是人們對事物了解的

不確定性的消除或減少，他把不確定的程度稱為信息熵（香農(nóng)，1948）。

隨機事件的信息熵：設(shè)隨機變量ξ，它有A1，A2，A3，A4，……，An共n種可能的結(jié)局，

每個結(jié)局出現(xiàn)的概率分別為p1，p2，p3，p4，……，pn，則其不確定程度，即信息熵為

（2）信息熵是數(shù)學方法和語言文字學的結(jié)合。一個系統(tǒng)的熵就是它的無組織程度的度量。

熵越大，事件越不確定。熵等于0，事件是確定的。

舉例：拋硬幣，

p（head）=0.5，p（tail）=0.5

H（p）=-0.5log

2

（0.5）+（-0.5log2（0.5））=1

說明：熵值最大，正反面的概率相等，事件最不確定。

四、最大熵理論

在無外力作用下，事物總是朝著最混亂的方向發(fā)展。事物是約束和自由的統(tǒng)一體。事物總是

在約束下爭取最大的自由權(quán)，這其實也是自然界的根本原則。在已知條件下，熵最大的事物，

最可能接近它的真實狀態(tài)。

五、基于最大熵的統(tǒng)計建模：建模理論

以最大熵理論為基礎(chǔ)的統(tǒng)計建模。

為什么可以基于最大熵建模？

Jaynes證明：對隨機事件的所有相容的預(yù)測中，熵最大的預(yù)測出現(xiàn)的概率占絕對優(yōu)勢。

Tribus證明，正態(tài)分布、伽馬分布、指數(shù)分布等，都是最大熵原理的特殊情況。

結(jié)論：最大熵統(tǒng)計建模是以最大熵理論為基礎(chǔ)的方法，即從符合條件的分布中選擇熵最大的

分布作為最優(yōu)秀的分布。

最大熵統(tǒng)計模型需要解決的問題：

（1）特征空間的確定——問題域

（2）特征選擇——尋找約束條件

（3）建立統(tǒng)計模型——基于最大熵理論建立熵最大的模型

六、基于最大熵的統(tǒng)計模型：數(shù)學描述

（1）問題描述：設(shè)最終輸出值構(gòu)成的語言學類別有限集為Y，對于每個y∈Y，其生成均受

上下文信息x的影響和約束。已知與y有關(guān)的所有上下文信息組成的集合為X，則模型的目

標是：給定上下文x∈X，計算輸出為y∈Y的條件概率p（y|x）。

（2）訓練樣例

例子：我們的任務(wù)是為詞“打”的詞性標注過程建立模型，標注模型為p，每個可能的詞性為

p（t）。

“打”的可能詞性：{動詞，量詞，介詞}。

由此，模型p的第一個約束：p（動詞）+p（量詞）+（介詞）=1

在訓練最大熵模型時，任務(wù)選連系統(tǒng)通過數(shù)據(jù)轉(zhuǎn)換程序或者模式識別中通常所說的特征抽取

器，把真實世界的，原始訓練數(shù)據(jù)通過特定的方法或者算法轉(zhuǎn)化為多特征或?qū)傩员硎镜挠柧?/p>

樣例。

條件最大熵方法是一種有監(jiān)督的機器學習方法，所以每個訓練樣例由一個實例x以及他的目

標概念類y組成。

七、基于最大熵的統(tǒng)計建模：數(shù)學推導

（1）模型輸入：從人工標注的訓練數(shù)據(jù)中抽取的訓練樣本集T={（x1，y1），（x2，y2），...，

（xn，yn）}，（xi，yi）表示在語料庫中出現(xiàn)yi時其上下文信息為xi。

（2）從訓練樣例中得到經(jīng)驗概率分布：其中Count（x，y）是語料中出現(xiàn)的次數(shù)，N為總

詞數(shù)。則

（3）特征f是指x與y之間存在的某種特定的關(guān)系，用二值函數(shù)表示：

（4）特征的經(jīng)驗概率期望值是所有滿足特征要求的經(jīng)驗概率之和，即：

引入1個特征：

(5)特征的期望概率是特征在所學習的隨機事件中的真實分布為：

其中，是指x出現(xiàn)的情況下，y的經(jīng)驗概率。是指x出現(xiàn)的情況下，y的

真實概率。

（6）特征的經(jīng)驗概率與期望概率應(yīng)該一致，即：

即：

上面的式子即成為約束等式。

(7)設(shè)存在k個特征f

i

（i=1,2，...，k），多個約束等式構(gòu)成的集合叫做約束集，可表示為：

（8）最大熵模型，是滿足約束條件的所有模型中熵最大的模型，即：

其中p為滿足約束集C條件下的某一統(tǒng)計模型。argmax表示尋找具有最大評分的參量。

（9）于是我們可以把這個最大熵模型表示為：在滿足約束條件中選擇熵最大的那個。

這是一個有約束的優(yōu)化問題

我們可以用拉格朗日乘數(shù)法來解決這個優(yōu)化問題。

具體步驟如下：

為每一個特征f

i

引入一個參數(shù)λ

i

（稱為拉格朗日算子），另外由于p（y|x）是條件概率，所

以有，所以也要為每個實例x引入一個參數(shù)k（x）。那么拉格朗日函數(shù)

可定義為：

然后對它求導，就可以求出最大時。

（10）特征f

i

的權(quán)重用相對應(yīng)的參數(shù)λ

i

表示，則滿足最大熵條件p（y|x）用指數(shù)形式表示為：

其中：稱為歸一化因子。

（11）此時，最大值

（12）稱為歸一化因子，它的引入是為了保證的概率。

（13）這樣我們就把一個有約束的優(yōu)化問題轉(zhuǎn)化為一個沒有約束優(yōu)化的問題。

八、最大熵模型的求解

許多自然語言處理問題都可以歸結(jié)為分類問題，其任務(wù)是估計目標概念類y在實例或上下文

或條件x的概率，即

p（y|x）。

最大熵模型有兩個基本的任務(wù)：特征選擇和模型選擇。

特征選擇：選擇一個能表達隨機過程的統(tǒng)計特征的特征集合。

模型選擇：即模型估計或者參數(shù)估計，就是為每個入選的特征估計權(quán)重λ。九、基于最大熵

的統(tǒng)計建模：參數(shù)估計Input：特征函數(shù)集合{f}，特征經(jīng)驗分布。

Output：最優(yōu)參數(shù)值集合{λ}，最優(yōu)模型。

GIS算法、IIS算法、SCGIS算法

十、基于最大熵的統(tǒng)計建模：特征選擇

在所有的特征中選擇最有代表性的特征，構(gòu)造約束集合。

數(shù)據(jù)稀疏的問題。

特征選擇的步驟：特征模板—>候選特征->選擇特征

特征選擇的方法：（1）增量式特征選擇算法，基本算法和近似算法。（2）基于頻數(shù)閾值的

特征選擇算法。

十一、最大熵模型的優(yōu)缺點

優(yōu)點：

（1）建模時，試驗者只需集中精力選擇特征，而不需要花費精力考慮如何使用這些特征。

（2）特征選擇靈活，且不需要額外的獨立假定或者內(nèi)在約束。

（3）模型應(yīng)用在不同領(lǐng)域時的可移植性強。

（4）可結(jié)合更豐富的信息。

缺點：

（1）時空開銷大

（2）數(shù)據(jù)稀疏問題嚴重

（3）對語料庫的依賴性較強

十二、最大熵模型的應(yīng)用

詞性標注、短語識別、指代消解、語法分析、機器翻譯、文本分類、問題回答、語言模型......