結(jié)合Logistic回歸構(gòu)建最大熵馬爾科夫模型

判定模型 vs 生成模型

上一篇博文中，我討論了樸素貝葉斯模型，以及它與隱馬爾可夫模型之間的聯(lián)系。它們都屬于生成模型，但本文要講的 Logistic 回歸模型是一個判定模型，全文以討論這種差異開始。

通常，機(jī)器學(xué)習(xí)分類器通過從所有可能的 y_i 中選擇有最大的 P(y | x) 的那個，來決定將哪個輸出標(biāo)簽 y 分配給輸入 x。

樸素貝葉斯分類器通過應(yīng)用貝葉斯定理間接估計 p(y | x)，然后計算類的條件分布/概率 P(x | y) 和先驗概率 P(y)。

這種間接性使得樸素貝葉斯成為一種生成模型，一種通過訓(xùn)練從類 y 生成數(shù)據(jù) x 的模型。p(x | y) 的意義是給定一個類 y，然后預(yù)測對應(yīng)的輸入 x 中包含哪些特征。相比之下，判定模型通過直接判定類別 y 的不同可能值來計算 p(y | x)，而不是計算概率。Logistic 回歸分類器正是這種分類器。

Logistic 回歸

Logistic 回歸是用于分類的一種監(jiān)督學(xué)習(xí)算法，它的本質(zhì)是線性回歸。

當(dāng)用于解決 NLP 任務(wù)時，它通過從輸入文本中提取特征并線性組合它們來估計 p(y | x)，即，將每個特征乘以一個權(quán)重，然后將它們相加，然后將指數(shù)函數(shù)應(yīng)用于該線性組合：

其中 f_i 是一個特征，w_i 是與該特征相關(guān)的權(quán)重。對于權(quán)重和特征點積進(jìn)行的 exp（即，指數(shù)函數(shù)）確保所有值都是正值，并且需要除以分母 Z 以得到（所有概率值的總和為 1）有效概率。

提取到的是二值特征，即只取值 0 和 1，通常稱為指標(biāo)函數(shù)。其中每一個特征都是通過輸入 x 和類 y 的函數(shù)來計算的。每個指標(biāo)函數(shù)表示為 f_i(y , x)，對于類 y 的特征 i，給定觀測值 x：

訓(xùn)練

我們想通過訓(xùn)練 logistic 回歸來獲得每一個特征的理想權(quán)重（使訓(xùn)練樣本和屬于的類擬合得最好的權(quán)重）。

Logistic 回歸用條件極大似然估計進(jìn)行訓(xùn)練。這意味著我們將選擇參數(shù) w，使對給定輸入值 x 在訓(xùn)練數(shù)據(jù)中 y 標(biāo)簽的概率最大化：

需要最大化的目標(biāo)函數(shù)是：

通過用前面展示的擴(kuò)展形式替換，并應(yīng)用對數(shù)除法規(guī)則，得到以下形式：

通?？梢赃\用隨機(jī)梯度下降法、L-BFGS 或共軛梯度法來求此函數(shù)的最大值，即找到最優(yōu)權(quán)重。

分類

在分類任務(wù)中，logistic 回歸通過計算給定觀察的屬于每個可能類別的概率，然后選擇產(chǎn)生最大概率的類別。

最大熵馬爾可夫模型

最大熵馬爾可夫模型（Maximum Entropy Markov Model，MEMM）的思想是利用 HMM 框架預(yù)測給定輸入序列的序列標(biāo)簽，同時結(jié)合多項 Logistic 回歸（又名最大熵，其給出了可以從輸入序列中提取特征的類型和數(shù)量上的自由度）。

HMM 基于兩種概率：

在現(xiàn)實問題中，我們要預(yù)測一個給定詞/輸入的標(biāo)簽/狀態(tài)。但是，由于貝葉斯定理（即生成方法），在 HMM 中不可能進(jìn)行編碼，而模型估計的是產(chǎn)生某個確定單詞的狀態(tài)的概率。

MEMM 因包含豐富的輸入特征而備受推崇：

也可以用一個判定方法來解決預(yù)測問題：

（左）傳統(tǒng) HMM 的依賴關(guān)系圖。（右）最大熵馬爾可夫模型的依賴關(guān)系圖（選自 A. McCallum et al. 2000）。

在最大熵馬爾可夫模型中，轉(zhuǎn)換函數(shù)和輸入函數(shù)（即上一篇博客的 HMM 矩陣 A 和 B）被單個函數(shù)代替：

給定前一個狀態(tài) s_t-1 和當(dāng)前的輸入值 o_t，得到當(dāng)前狀態(tài)的概率 s_t。下圖展示了計算狀態(tài)/標(biāo)簽/標(biāo)記轉(zhuǎn)換的不同之處。

HMM 和 MEMM 之間狀態(tài)轉(zhuǎn)換估計的對比。（選自「Speech and Language Processing」，Daniel Jurafsky & James H. Martin）

與當(dāng)前輸入僅依賴于當(dāng)前狀態(tài)的 HMM 相比，MEMM 中的當(dāng)前輸入也可以取決于之前的狀態(tài)。HMM 模型對于每個轉(zhuǎn)換和輸入都有確定的概率估計，而 MEMM 給出每個隱藏狀態(tài)的一個概率估計，這是給定前一個標(biāo)記和輸入值情況下的下一個標(biāo)記的概率。

在 MEMM 而不是轉(zhuǎn)換和觀測矩陣中，只有一個轉(zhuǎn)換概率矩陣。該矩陣將訓(xùn)練數(shù)據(jù)中先前狀態(tài) S_t-1 和當(dāng)前輸入 O_t 對的所有組合封裝到當(dāng)前狀態(tài) S_t。

令 N 為獨特狀態(tài)的個數(shù)，M 為獨特單詞的個數(shù)，矩陣的形狀為：

(N?M)?N

特征函數(shù)

MEMM 可以對輸入值的任何有用特征進(jìn)行條件化。在 HMM 中這是不可能的，因為 HMM 是基于概率的，因此需要計算每個輸入特征的概率。使用狀態(tài)-輸入轉(zhuǎn)換函數(shù)，而不是像 HMM 那樣的獨立的轉(zhuǎn)換和輸入函數(shù)，使我們能夠?qū)斎氲亩鄠€非獨立特征進(jìn)行建模。

這是通過多項 logistic 回歸來實現(xiàn)的，給定先前標(biāo)記（即，s’），輸入詞（即，o）和任意其它特征（即，fi(x,y’)）來估計每個局部標(biāo)記的概率：

其中 w_i 是與每個特征 f_i(x,y) 相關(guān)聯(lián)的需要學(xué)習(xí)的權(quán)重，Z 是使矩陣在每行上總和為 1 的歸一化因子。

考慮整個觀測序列的特征函數(shù)。（選自「Speech and Language Processing」，Daniel Jurafsky & James H. Martin）

訓(xùn)練與解碼

最初發(fā)表于 2000 年的 MEMM 論文使用廣義迭代縮放（GIS）算法來擬合多項 logistic 回歸，即根據(jù)訓(xùn)練數(shù)據(jù)找到完美的權(quán)重。該算法在很大程度上被基于梯度的方法（如 L-BFGS）所超越。

使用與 HMM 中相同的 Viterbi 算法進(jìn)行解碼，盡管不是那么適合估計狀態(tài)轉(zhuǎn)換的新方法。

MEMM 的重要結(jié)論

軟件包

生成海報

免責(zé)聲明：本網(wǎng)站內(nèi)容主要來自原創(chuàng)、合作伙伴供稿和第三方自媒體作者投稿，凡在本網(wǎng)站出現(xiàn)的信息，均僅供參考。本網(wǎng)站將盡力確保所提供信息的準(zhǔn)確性及可靠性，但不保證有關(guān)資料的準(zhǔn)確性及可靠性，讀者在使用前請進(jìn)一步核實，并對任何自主決定的行為負(fù)責(zé)。本網(wǎng)站對有關(guān)資料所引致的錯誤、不確或遺漏，概不負(fù)任何法律責(zé)任。任何單位或個人認(rèn)為本網(wǎng)站中的網(wǎng)頁或鏈接內(nèi)容可能涉嫌侵犯其知識產(chǎn)權(quán)或存在不實內(nèi)容時，應(yīng)及時向本網(wǎng)站提出書面權(quán)利通知或不實情況說明，并提供身份證明、權(quán)屬證明及詳細(xì)侵權(quán)或不實情況證明。本網(wǎng)站在收到上述法律文件后，將會依法盡快聯(lián)系相關(guān)文章源頭核實，溝通刪除相關(guān)內(nèi)容或斷開相關(guān)鏈接。