熵（entropy）和困惑度（perplexity）是用于評估N元語法系統(tǒng)的最普通的計量方法。熵是信息量的度量，在自然語言處理、語音識別和計算語言學(xué)中，熵都是非常有價值的。熵可以用來度量一個特定語法中的信息量是多少，度量給定語法和給定語言的匹配程度有多高，預(yù)測一個給定的N元語法中的下一個單詞是什么。如果有給定的兩個語法和一個語料庫，我們可以使用熵來估計哪個語法與語料庫匹配得更好。我們也可以使用熵來比較兩個語音識別任務(wù)的困難程度，還可以使用它來測量一個給定的概率語法與人類語法的匹配程度。

熵的計算要求我們在所要預(yù)測的范圍內(nèi)（單詞、字母和詞類，我們稱為x的集合）建立一個隨機變量X，并且要有一個特定的概率函數(shù)，稱為p(x)，那么這個隨機變量X的熵為：

從原則上說，對數(shù)可以使用任何底數(shù)。在此我們在所有計算中采用的底數(shù)都是2，因此，熵的就用比特（bit）來度量，因為計算比特時是以2為底數(shù)的。

對于計算機科學(xué)家來說，定義熵的最直觀方法，就是把熵想像成對某一判斷進行信息編碼的比特數(shù)的下界，或者把熵想像成在最優(yōu)編碼中信息量的大小。

Cover and Thomas(1991)提出了如下的例子。假定我們想給Yonkers賽馬場的賽馬下賭注，但是Yonker賽馬場距離我們太遠(yuǎn)，我們只好給賽馬場登記賭注的人發(fā)一個短的消息，告訴他我們給哪匹馬下賭注。假定有八匹馬參加比賽。

給這個消息編碼的一種方法是用二進制代碼來表示馬的號碼；這樣，號碼為1的馬的二進制代碼是001，號碼為2的馬的二進制代碼是010，號碼為3的馬的二進制代碼是011，依次類推，號碼為8的馬的二進制代碼是000。如果我們用一天的時間來下賭注，每匹馬用比特來編碼，每次比賽我們要發(fā)出3比特的信息。

我們能不能把這件事做得好一點呢？我們可以根據(jù)賭注的實際分布來傳送消息，假定每匹馬的先驗概率如下：

圖1

計算這些馬的隨機變量X的熵，我們就可以知道其比特數(shù)的下界，具體計算如下：

每次比賽平均為2比特的代碼可以這樣來編碼：用最短的代碼來表示我們估計概率最大的馬，估計概率越小的馬，其代碼越長。例如，我們可以用0來給估計概率最大的馬編碼，按照估計概率從大到小的排列，其余的馬的代碼分別為：10，110，1110，111100，111101，111110和111111。