最大熵模型

“熵”最初是熱力學中的一個概念，上世紀40年代，香農首先在信息論中引入了信息熵的概念。信息熵用來表示不確定度的度量，不確定度越大，熵值越大。極限情況，當一個隨機變量均勻分佈時，熵值最大；完全確定時，熵值為0

第一次系統提出最大熵的原理的一般認為是Jaynes，後來有人提出了相應的算法來估計對應的統計模型的參數。由於當時計算條件的限制，最大熵模型在人工智能和自然語言處理領域都沒有得到廣泛應用。上世紀90年代，IBM的研究員應用重新深入的研究了這個問題，系統地描述了條件最大熵的框架和實現算法，並在自然語言處理任務上取得了非常好的效果，引起了人們的重視。很快條件最大熵模型技術得到了廣泛的傳播，在自然語言處理的各個領域都取得了巨大的成功，在此基礎上的一些深入研究工作也不斷展開。最大熵模型已經成為近年來自然語言處理領域最成功的機器學習方法。

假設我們的分類任務或者預測任務的類別為y，而我們能夠依據的上下文信息記為x。我們希望在不同的給定的上下文x條件下，統計模型能夠給出判為不同類別y的概率值。因此，我們希望能夠建立一種區分性的條件概率模型（注意，我們這裏仍然用了的表示形式，但是此處的意義表示的是整個的概率分佈，也不再表示具體的實例）。我們用來表示所有這種條件概率模型的集合，而我們期望得到的模型就是中的一種。所謂的條件最大熵模型，就是在一定約束下條件熵最大的模型。

所謂的約束，也就是我們已知的信息，可以認為我們希望模型在這些信息上能和訓練數據匹配。而熵最大，則表明除約束外，我們不再做未知的假設。在條件最大熵模型中，約束是通過特徵的形式來體現的。這裏的特徵和語音識別等領域的特徵有所不同，它表示成和的函數的形式，表示了x的某種屬性和y的共現情況。特徵函數理論上可以取任何實數值（早期因為訓練算法的原因只能取正值），在自然語言處理領域一般表示為0-1的指示函數的形式，例如：

我們定義特徵函數f的經驗期望如下：

表示樣本在訓練語料中出現的經驗概率：

而特徵函數f的模型期望為：

最大熵模型的約束就是使得任意特徵的經驗期望和模型期望相等：

我們認為我們定義的特徵集合描述了訓練樣本的信息，而我們的模型在這些信息的層面上和訓練數據保持了一致。

我們將滿足這些約束的條件概率的中的一個子集定義為，而條件熵的定義為：

那我們需要得到的就是在中條件熵最大的模型p：

根據概率公式的定義，我們還有另外一個約束：

那麼和構成了一個約束最優化問題，可以用拉格朗日乘子法來計算：

可以解得模型p的形式為：

這就是條件最大熵模型的形式，而對應的

這裏的拉格朗日乘子相當於特徵的權重，為了以後討論的方便，換用表示：

如果已知模型是上式的形式，那麼在訓練數據上的log似然值為：

通過上式我們可以發現，通過最大似然求解最優權將和的結果是一樣的。也就是説在約束下的條件熵最大的模型也就是具有形式且使得在訓練數據上似然值最大的模型。

雖然使得最大的*是我們的最優權值解，但是式子卻沒有一個直接的數值解，但是幸運的是，具有凸函數的性質，因此我們想求得最優的,只需要使得：

而通過計算我們可以得到：

恰好就是上文所提的約束條件。在設定的權值參數下，似然值的梯度是容易計算的。因此權值參數估計的方法可以通過基於梯度的數值優化算法進行，比如共軛梯度（Conjugate Gradient, CG），擬牛頓方法（quasi-Newton）等等。目前最常用的是一種稱為L-BFGS的擬牛頓方法（limited memory BFGS），它在優化性能和速度上都表現良好，特別是相對於早期的以前基於迭代縮放的IIS（improved iterative scaling）、GIS（generalized iterative scaling）最大熵模型參數估計方法優勢明顯。

採用最大似然方法訓練出的最大熵模型能夠在訓練數據上表現良好，但是不一定在未知數據上具有好的推廣性。特別是出現在參數數量巨大而訓練數據又不是很充足的情況下。一種解決方案是設立一定數量的開發集，當在開發集上性能下降時停止訓練。但是這並不是一個很好的策略，因為可能暫時的下降之後還會上升。

另一種思路就是在優化目標上改變，可以增加關於參數的先驗知識，也被稱為一種“正則化”的策略。設定我們的參數集為w，訓練樣本集合為D，那麼根據貝葉斯公式有：

其中，成為給定D下參數w的後驗，成為w在D上的似然，稱為w的先驗。最大似然軌跡其實就是假設w的先驗為均勻分佈，直接最大化似然就可以了。

而我們可以通過假設一個先驗分佈，來防止有些權值被過訓練，一個常用的分佈就是高斯分佈。