雖然HMM可以達到很高的精確度，但是我們發現它需要大量的體系結構創新來處理未知的單詞、後退、後綴等等。如果我們能夠以一種乾淨的方式將任意的特性直接添加到模型中，這將會容易得多，但是這對於生成模型(如HMMs)來說很難。幸運的是，我們已經看到了這樣做的模型:邏輯回歸模型!但logistic回歸不是一個序列模型;它為單個觀察分配一個類。然而，我們可以將邏輯回歸轉化為一個判別序列模型，只需對連續的單詞運行它，使用分配給前一個單詞的類作為下一個單詞分類的一個特徵。當我們以這種方式應用邏輯回歸時，它被稱為最大熵馬爾可夫模型或MEMM5

設單詞序列為 W = w_{1}^n ，標籤序列 T = t_{1}^n 。在隱馬爾可夫模型中，為了計算使P(T|W)最大化的最佳標記序列，我們依賴於貝葉斯規則和概率P(W|T):

相比之下，在MEMM中，我們直接計算後驗 P(T|W) ，訓練它區分可能的標籤序列:

考慮只標記一個單詞。一個多項式邏輯回歸分類器可以用與隱馬爾可夫模型不同的方法計算單概率 P(t_i | w_{i},t_{i-1}) 。圖8.12通過箭頭的方向直觀地顯示了差異;HMMs計算似然(觀察詞以標記為條件)，而MEMMs計算後驗(標記以觀察詞為條件)。

Figure 8.12 一個示意圖視圖的HMM(頂部)和MEMM(底部)表示的概率計算的正確序列標籤為後一句話。隱馬爾可夫模型計算給定隱藏狀態下觀察結果的可能性，而基於先前狀態和當前觀察結果的隱馬爾可夫模型計算每個狀態的後驗

MEMM中的特徵

當然，我們不會只在 w_i 和 t_i 上建立MEMMs。使用判別序列模型的原因是它更容易包含許多特性。圖8.13顯示了這些附加特性的圖形直觀。

基本的MEMM詞性標記器以觀察詞本身、相鄰詞、以前的標記以及各種組合為條件，使用的特徵模板如下:

特徵模板用於自動填充訓練和測試集中每個實例的特徵集。因此，我們的示例Janet/NNP will/MD back/VB the/DT bill/NN，當 w_i 為詞back時，將生成以下特徵:

此外，還需要處理未知單詞的特性，表示單詞的拼寫或形狀的屬性:

針對 w_i 可有如下情況：

  1. w_i包含特定前綴
  2. w_i包含特定後綴
  3. w_i包含數字
  4. w_i包含一個大寫字母
  5. w_i包含一個字元
  6. w_i全是大寫字母
  7. w_i 的單詞形狀
  8. w_i 的短單詞形狀
  9. w_i 是大寫，有數字和破折號
  10. w_i 是大寫字母，Co.， Inc.等在3個字以內

單詞的形狀特徵用於表示單詞的抽象字母圖案，方法是將小寫字母映射為「x」，將大寫字母映射到「X」，將數字映射到「d」，並保留標點符號。 因此，例如I.M.F將映射到X.X.X. 和DC10-30將映射到XXdd-dd。 還使用第二類較短的字形特徵。 在這些特徵中，連續的字元類型被刪除，因此DC10-30將被映射到Xd-d，但是I.M.F仍將映射到X.X.X. 例如，well-dressed將生成以下非零值特徵值：

已知單詞的特徵，如式8.33中的模板，對訓練集中出現的每個單詞進行計算。未知單詞的特徵也可以對訓練中的所有單詞進行計算，或者只對頻率低於某個閾值的訓練單詞進行計算。已知單詞模板和單詞簽名特性的結果是一組非常大的特徵。通常使用特徵截斷，如果訓練集中的特徵數小於5，則會拋出這些特徵。

解碼和訓練MEMMs

然後，結合輸入單詞 w_i 的這些特徵，計算出最有可能的標籤序列， w_i 附近l長度窗口以內的單詞 w_{l-l}^{i+l} 系列(左邊的l個單詞和右邊的l個單詞)，和當前單詞 w_i 前k個標籤 t_{i-k}^{i-1} 如下(使用θ來代替權重而不是w,以避免和單詞w弄混)：

我們應該如何解碼才能找到這個最優的標籤序列T ?將logistic回歸轉化為序列模型最簡單的方法是構建一個局部分類器，從左到右對每個單詞進行分類，對句子中的第一個單詞進行硬分類，然後對第二個單詞進行硬決策，以此類推。這被稱為貪心解碼演算法，因為我們貪婪地為每個單詞選擇最好的標籤，如圖8.14所示。

在貪心解碼中，我們只是在每個令牌上運行分類器，從左到右，每次都要做出一個艱難的決定，哪個是最好的標記。

貪心演算法的問題在於，在進入下一個單詞之前，對每個單詞做出艱難的決定，分類器不能使用來自未來決定的證據。雖然貪心演算法非常快，偶爾也有足夠的精度來使用，但一般來說，硬決策會導致性能下降太多，我們不使用它。相反，我們使用維特比演算法解碼MEMM，就像使用HMM一樣，找到對整個句子最優的詞性標記序列。

例如，假設我們的MEMM只以前面的標記 t_{i-1} 和觀察到的單詞 w_i 為條件。具體來說，這涉及到用 p(t_i | t_{i-1},w_i) 的適當值填充 N imes T 數組,並在繼續執行時維護反向指針，與HMM Viterbi一樣，當表被填滿時，我們只需按照最後一列中的最大值返回指針來檢索所需的標籤集。Viterbi的hmm風格應用程序的必要更改只與我們如何填充每個單元格有關。由式8.20可知，維特比方程的遞推步驟計算狀態j的時間t的維特比值為:

HMM的實現：

MEMM只需要對後一個公式稍加修改，將a和b的先驗概率和似然概率替換為直接後驗概率：

MEMMs中的學習依賴於我們提出的用於邏輯回歸的監督學習演算法。在給定一系列觀測值、特徵函數和相應隱藏狀態的情況下，利用梯度下降法訓練權值，使訓練語料庫的對數似然值達到最大。

所介紹的MEMM和HMM模型的一個問題是，它們完全是從左到右運行的。雖然Viterbi演算法仍然允許當前的決策受到未來決策的間接影響，但是如果一個關於詞wi的決策可以直接使用關於未來標記 t_{i+1} 和 t_{i+2} 的信息，那麼它將更有幫助

實現雙向性的一種方法是切換到一個更強大的模型，稱為條件隨機場(CRF)。CRF是一個無向的圖形模型，這意味著它不會在每個時間步長計算每個標記的概率。相反，CRF在每個時間步長上計算一個小圈子上的對數線性函數，這是一組相關特性。與MEMM不同的是，這些可能在將來的時間步驟中包含單詞的輸出特性。最佳序列的概率同樣由維特比演算法計算。因為CRF對所有標籤序列的概率進行標準化，而不是對單個時間t的所有標籤進行標準化，所以訓練需要計算所有可能標籤的和，這使得CRF訓練非常慢。


推薦閱讀：
相关文章