MIT自然語言處理第五講：最大熵和對數(shù)線性模型（第一部分）

自然語言處理：最大熵和對數(shù)線性模型
Natural Language Processing: Maximum Entropy and Log-linear Models?
作者：Regina Barzilay（MIT,EECS Department, October 1, 2004)
譯者：我愛自然語言處理（www.52nlp.cn?，2009年4月25日）

上一講主要內(nèi)容回顧（Last time）：
* 基于轉(zhuǎn)換的標(biāo)注器（Transformation-based tagger）
* 基于隱馬爾科夫模型的標(biāo)注器（HMM-based tagger）

遺留的內(nèi)容（Leftovers）:?
a) 詞性分布（POS distribution）
　i. 在Brown語料庫中按歧義程度排列的詞型數(shù)目（The number of word types in Brown corpus by degree of ambiguity）：
　　無歧義（Unambiguous）只有1個標(biāo)記： 35,340
　　　　歧義（Ambiguous） 有2-7個標(biāo)記： 4,100
　　　　　　　　　　　　　　　　2個標(biāo)記：3,764
　　　　　　　　　　　　　　　　3個標(biāo)記：264
　　　　　　　　　　　　　　　　4個標(biāo)記：61
　　　　　　　　　　　　　　　　5個標(biāo)記：12
　　　　　　　　　　　　　　　　6個標(biāo)記：2
　　　　　　　　　　　　　　　　7個標(biāo)記：1
b) 無監(jiān)督的TBL（Unsupervised TBL）
　i. 初始化（Initialization）：允許的詞性列表（a list of allowable part of speech tags）
　ii. 轉(zhuǎn)換（Transformations）： 在上下文C中將一個單詞的標(biāo)記從χ變?yōu)閅 (Change the tag of a word from χ to Y in context C, where γ ∈ χ).
　　例子（Example）: “From NN VBP to VBP if previous tag is NNS”
　iii. 評分標(biāo)準(zhǔn)(Scoring criterion):
　　

這一講主要內(nèi)容（Today）：
* 最大熵模型(Maximum entropy models)
* 與對數(shù)線性模型的聯(lián)系(Connection to log-linear models)
* 優(yōu)化方法(Optimization methods)

一般問題描述(The General Problem)：
a) 給定輸入域χ（We have some input domain χ）；
b) 給定標(biāo)記集γ（We have some label set γ）；
c) 目標(biāo)（Goal）：對于任何x ∈ χ 及 y ∈γ學(xué)習(xí)一個條件概率P(y|x) （learn a conditional probability P(y|x)for any x ∈ χ and y ∈ γ ）。

一、 詞性標(biāo)注（POS tagging）：
a) 例子：Our/PRP$ enemies/NNS are/VBP innovative/JJ and/CC resourceful/JJ ,/, and/CC so/RB are/VB we/PRP ?/?.
　i. 輸入域（Input domain）：χ是可能的“歷史”（χ is the set of possible histories）；
　ii. 標(biāo)記集（Label set）：γ是所有可能的標(biāo)注標(biāo)記（γ is the set of all possible tags）；
　iii. 目標(biāo)（Goal）：學(xué)習(xí)一個條件概率P(tag|history)（learn a conditional probability P(tag|history)）。
b) 表現(xiàn)形式（Representation）：
　i. “歷史”是一個4元組(t1,t2,w[1:n],i) （History is a 4-tuples (t1,t2,w[1:n],i)；
　ii. t1,t2是前兩個標(biāo)記（t1,t2 are the previous two tags）
　iii. w[1:n]是輸入句子中的n個單詞（w[1:n]are the n words in the input sentence）
　iv. i 是將要被標(biāo)注的單詞的位置索引（i is the index of the word being tagged）
　χ是所有可能的“歷史”集合（χis the set of all possible histories）

未完待續(xù)：第二部分

附：課程及課件pdf下載MIT英文網(wǎng)頁地址：
　　　http://people.csail.mit.edu/regina/6881/

MIT自然語言處理第五講：最大熵和對數(shù)線性模型（第二部分）

自然語言處理：最大熵和對數(shù)線性模型
Natural Language Processing: Maximum Entropy and Log-linear Models?
作者：Regina Barzilay（MIT,EECS Department, October 1, 2004)
譯者：我愛自然語言處理（www.52nlp.cn?，2009年4月29日）

一、 詞性標(biāo)注（POS tagging）：
c) 特征向量表示（Feature Vector Representation）
　i. 一個特征就是一個函數(shù)f（A feature is a function f ）：

　ii. 我們有m個特征fk，k = 1…m（We have m features fk for k =1…m）
d) 詞性表示（POS Representation）
　i. 對于所有的單純/標(biāo)記對的單詞/標(biāo)記特征，（Word/tag features for all word/tag pairs）：

ii. 對于所有特定長度的前綴/后綴的拼寫特征（Spelling features for all prefixes/suffixes of certain length）：

iii. 上下文特征（Contextual features）：

iv. 對于一個給定的“歷史”x ∈ X ，每一個γ中的標(biāo)記都被映射到一個不同的特征向量（For a given history x ∈ X, each label in γ is mapped to a different feature vector）：

v. 目標(biāo)（Goal）：學(xué)習(xí)一個條件概率P(tag|history)（learn a conditional probability P(tag|history)

二、 最大熵（Maximum Entropy）：
a) 例子（Motivating Example）：
　i. 給定約束條件：p(x, 0)+p(y, 0)=0.6，a ∈{x, y}且b ∈0, 1，估計概率分布p(a, b)（Estimate probability distribution p(a, b), given the constraint: p(x, 0) + p(y, 0) =0.6, where a ∈{x, y}and b ∈0, 1））：
　　　　　　　
　ii. 滿足約束條件的一種分布（One Way To Satisfy Constraints）：
　　　　　　　
　iii. 滿足約束條件的另一種分布（Another Way To Satisfy Constraints）：
　　　　　　　
b) 最大熵模型(Maximum Entropy Modeling)
　i. 給定一個訓(xùn)練樣本集，我們希望尋找一個分布符合如下兩個條件(Given a set of training examples, we wish to find a distribution which)：
　　1. 滿足已知的約束條件（satisfies the input constraints）
　　2. 最大化其不確定性（maximizes the uncertainty）
　ii. 補充：
　　最大熵原理是在1957 年由E.T.Jaynes 提出的，其主要思想是，在只掌握關(guān)于未知分布的部分知識時，應(yīng)該選取符合這些知識但熵值最大的概率分布。因為在這種情況下，符合已知知識的概率分布可能不止一個。我們知道，熵定義的實際上是一個隨機變量的不確定性，熵最大的時侯，說明隨機變量最不確定，換句話說，也就是隨機變量最隨機，對其行為做準(zhǔn)確預(yù)測最困難。從這個意義上講，那么最大熵原理的實質(zhì)就是，在已知部分知識的前提下，關(guān)于未知分布最合理的推斷就是符合已知知識最不確定或最隨機的推斷，這是我們可以作出的唯一不偏不倚的選擇，任何其它的選擇都意味著我們增加了其它的約束和假設(shè)，這些約束和假設(shè)根據(jù)我們掌握的信息無法做出。（這一段轉(zhuǎn)自北大常寶寶老師的《自然語言處理的最大熵模型》）

未完待續(xù):第三部分

附：課程及課件pdf下載MIT英文網(wǎng)頁地址：
　　　http://people.csail.mit.edu/regina/6881/

MIT自然語言處理第五講：最大熵和對數(shù)線性模型（第三部分）

自然語言處理：最大熵和對數(shù)線性模型
Natural Language Processing: Maximum Entropy and Log-linear Models?
作者：Regina Barzilay（MIT,EECS Department, October 1, 2004)
譯者：我愛自然語言處理（www.52nlp.cn?，2009年5月5日）

二、 最大熵（Maximum Entropy）：
b) 最大熵模型(Maximum Entropy Modeling)
　iii. 約束條件（Constraint）：
　　每個特征的觀察樣本期望值與特征模型期望值相一致（observed expectation of each feature has to be the same as the model’s expectation of the feature）：
　　
　iv. 最大熵原理(Principle of Maximum Entropy)：
　　將已知事實作為制約條件，求得可使熵最大化的概率分布作為正確的概率分布：
　　　　　
　v. 補充：
　　自然語言處理中很多問題都可以歸結(jié)為統(tǒng)計分類問題，很多機器學(xué)習(xí)方法在這里都能找到應(yīng)用，在自然語言處理中，統(tǒng)計分類表現(xiàn)在要估計類a 和某上下文b 共現(xiàn)的概率P(a,b) ，不同的問題，類a 和上下文b 的內(nèi)容和含義也不相同。在詞性標(biāo)注中是類的含義是詞性標(biāo)注集中的詞類標(biāo)記，而上下文指的是當(dāng)前被處理的詞前面一個詞及詞類，后面一個詞及詞類或前后若干個詞和詞類。通常上下文有時是詞，有時是詞類標(biāo)記，有時是歷史決策等等。大規(guī)模語料庫中通常包含a 和b 的共現(xiàn)信息，但b 在語料庫中的出現(xiàn)常常是稀疏的，要對所有可能的(a,b)計算出可靠的P(a,b) ，語料庫規(guī)模往往總是不夠的。問題是要發(fā)現(xiàn)一個方法，利用這個方法在數(shù)據(jù)稀疏的條件下可靠的估計P(a,b) 。不同的方法可能采用不同的估計方法。
　　最大熵模型的優(yōu)點是：在建模時，試驗者只需要集中精力選擇特征，而不需要花費精力考慮如何使用這些特征。而且可以很靈活地選擇特征，使用各種不同類型的特征，特征容易更換。利用最大熵建模，一般也不需要做在其它方法建模中常常使用的獨立性假設(shè)，參數(shù)平滑可以通過特征選擇的方式加以考慮，無需專門使用常規(guī)平滑算法單獨考慮，當(dāng)然也不排除使用經(jīng)典平滑算法進行平滑。每個特征對概率分布的貢獻則由參數(shù)α決定，該參數(shù)可以通過一定的算法迭代訓(xùn)練得到。
（注：以上兩段轉(zhuǎn)自北大常寶寶老師的《自然語言處理的最大熵模型》）

三、 最大熵模型詳述
a) 概要（Outline）
　i. 我們將首先證明（We will first show that）滿足上述條件的概率分布p*具有如下的形式：
　　　　　
　其中pi是一個歸一化常數(shù)，α是模型參數(shù)（where?pi?is a normalization constant and the α’s are the model parameters）
　ii. 然后我們將考慮搜尋α的參數(shù)估計過程（Then, we will consider an estimation procedure for finding the α’s）
b) 數(shù)學(xué)符號表示（Notations）
　i. χ是可能的“歷史”集（χis the set of possible histories）
　ii. γ是所有可能的標(biāo)記集（γ is the set of all possible tags）
　iii. S是事件訓(xùn)練樣本集（S finite training sample of events）
　iv. p’(x)是S中x的觀察概率（p’(x)observed probability of x in S）
　v. p(x)是x的模型概率（p(x) the model’s probability of x）
　vi. 其它符號公式定義如下：
　　　　

未完待續(xù):第四部分

附：課程及課件pdf下載MIT英文網(wǎng)頁地址：
　　　http://people.csail.mit.edu/regina/6881/

MIT自然語言處理第五講：最大熵和對數(shù)線性模型（第四部分）

自然語言處理：最大熵和對數(shù)線性模型
Natural Language Processing: Maximum Entropy and Log-linear Models?
作者：Regina Barzilay（MIT,EECS Department, October 1, 2004)
譯者：我愛自然語言處理（www.52nlp.cn?，2009年5月9日）

三、 最大熵模型詳述
c) 相對熵（Kullback-Liebler距離）（Relative Entropy (Kullback-Liebler Distance)）
　i. 定義（Definition）：兩個概率分布p和q的相對熵D由下式給出（The relative entropy D between two probability distributions p and q is given by）
　　　　　　
　ii. 引理1（Lemma 1）：對于任意兩個概率分布p和q，D(p, q)≥0 且 D(p, q)=0 當(dāng)且僅當(dāng)p=q（For any two probability distributions p and q, D(p, q)≥ 0, and D(p, q)=0 if and only if p =q）
　iii. 引理2（畢達哥拉斯性質(zhì)）（Lemma 2 (Pythagorean Property)）：若p∈P，q∈Q，p*∈P∩Q，則D(p, q) = D(p, p*) + D(p*, q) （If p ∈P and q ∈ Q, and p*∈P∩Q, then D(p, q) = D(p, p*) + D(p*, q)）
　注：證明請參看MIT NLP 的lec5.pdf英文講稿；
d) 最大熵解（The Maximum Entropy Solution）
　i. 定理1(Theorem 1)：若p*∈P∩Q，則p* =?argmax_{p in P}H(p)?,且p*唯一(If p?∈P ∩Q then p* =?argmax_{p in P}H(p). Furthermore, p* is unique)
注：證明請參看min nlp原講稿，主要運用引理1和引理2得出。
e) 最大似然解（The Maximum Likelihood Solution）
　i. 定理2(Theorem 2)：若p*∈P∩Q，則p* =?argmax_{q in Q}L(q)?,且p*唯一(If p?∈P ∩Q then p* =?argmax_{q in Q}L(q). Furthermore, p* is unique)
注：證明請參看min nlp原講稿，主要運用引理1和引理2得出。
f) 對偶定理（Duality Theorem）
　i. 存在一個唯一分布p*(There is a unique distribution p*）
　　1. p*∈ P ∩ Q
　　2. p* =?argmax_{p in P}H(p)?(最大熵解（Max-ent solution）)
　　3. p* =?argmax_{q in Q}L(q)?(最大似然解（Max-likelihood solution）)
　ii. 結(jié)論（Implications）：
　　1. 最大熵解可以寫成對數(shù)線性形式（The maximum entropy solution can be written in log-linear form）
　　2. 求出最大似然解同樣給出了最大熵解（Finding the maximum-likelihood solution also gives the maximum entropy solution）

未完待續(xù)…

附：課程及課件pdf下載MIT英文網(wǎng)頁地址：
　　　http://people.csail.mit.edu/regina/6881/

MIT自然語言處理第五講：最大熵和對數(shù)線性模型（第五部分）

自然語言處理：最大熵和對數(shù)線性模型
Natural Language Processing: Maximum Entropy and Log-linear Models?
作者：Regina Barzilay（MIT,EECS Department, October 1, 2004)
譯者：我愛自然語言處理（www.52nlp.cn?，2009年5月14日）

三、 最大熵模型詳述
g) GIS算法（Generative Iterative Scaling）
　i. 背景：
　　最原始的最大熵模型的訓(xùn)練方法是一種稱為通用迭代算法GIS (generalized iterative scaling) 的迭代算法。GIS 的原理并不復(fù)雜，大致可以概括為以下幾個步驟：
　　1. 假定第零次迭代的初始模型為等概率的均勻分布。
　　2. 用第 N 次迭代的模型來估算每種信息特征在訓(xùn)練數(shù)據(jù)中的分布，如果超過了實際的，就把相應(yīng)的模型參數(shù)變小；否則，將它們變大。
　　3. 重復(fù)步驟 2 直到收斂。
　　GIS 最早是由 Darroch 和 Ratcliff 在七十年代提出的。但是，這兩人沒有能對這種算法的物理含義進行很好地解釋。后來是由數(shù)學(xué)家希薩（Csiszar) 解釋清楚的，因此，人們在談到這個算法時，總是同時引用 Darroch 和Ratcliff 以及希薩的兩篇論文。GIS 算法每次迭代的時間都很長，需要迭代很多次才能收斂，而且不太穩(wěn)定，即使在 64 位計算機上都會出現(xiàn)溢出。因此，在實際應(yīng)用中很少有人真正使用 GIS。大家只是通過它來了解最大熵模型的算法。
　　八十年代，很有天才的孿生兄弟的達拉皮垂(Della Pietra)在 IBM 對 GIS 算法進行了兩方面的改進，提出了改進迭代算法 IIS（improved iterative scaling）。這使得最大熵模型的訓(xùn)練時間縮短了一到兩個數(shù)量級。這樣最大熵模型才有可能變得實用。即使如此，在當(dāng)時也只有 IBM 有條件是用最大熵模型。（以上摘自Google吳軍《數(shù)學(xué)之美系列16》）
　ii. 目標(biāo)（Goal）：尋找遵循如下約束條件的此種形式pi prod{j=1}{k}{{alpha_j}^{f_j}(x)}的分布（Find distribution of the form?pi prod{j=1}{k}{{alpha_j}^{f_j}(x)}that obeys the following constraints）：
　　　　　　　　　　E_p f_j = E_{p prime}{f_j}?
　iii. GIS約束條件（GIS constraints）：
　　　1、
　　其中C是一個常數(shù)（where C is a constant (add correctional feature)）
　　　2、　
　iv. 定理（Theorem）：下面的過程將收斂到p*∈P∩Q（The following procedure will converge to p*∈P∩Q）：
　　　　　
　　　
　v. 計算量（Computation）
　　　
　　其中S={(a1,b1),…,(aN,bN)}是訓(xùn)練樣本（where S is a training sample）
　　　
　　因為有太多可能的(a,b)，為了減少計算量，因而采用下面的公式近似計算：
　　　
　　時間復(fù)雜度（Running time）：O(NPA)
　　其中N訓(xùn)練集規(guī)模，P是預(yù)期數(shù)，A是對于給定事件(a,b)活躍特征的平均數(shù)（where N is the training set size, P is the number of predictions, and A is the average number of features that are active for a given event (a,b)）

四、 最大熵分類器（ME classifiers）
a) 可以處理很多特征（Can handle lots of features）
b) 存在數(shù)據(jù)稀疏問題（Sparsity is an issue）
　i. 應(yīng)用平滑算法和特征選擇方法解決（apply smoothing and feature selection）
c) 特征交互（Feature interaction）？
　i. 最大熵分類器并沒有假設(shè)特征是獨立的（ME classifiers do not assume feature independence）
　ii. 然而，它們也沒有明顯的模型特征交互（However, they do not explicitly model feature interaction）

五、 總結(jié)（Summary）
　a) 條件概率建模與對數(shù)線性模型（Modeling conditional probabilities with log-linear models）
　b) 對數(shù)線性模型的最大熵性質(zhì)（Maximum-entropy properties of log-linear models）
　c) 通過迭代縮放進行優(yōu)化（Optimization via iterative scaling）

一些實現(xiàn)的最大熵工具（Some implementations）：
　　http://nlp.stanford.edu/downloads/classifier.shtml
　　http://maxent.sourceforge.net

第五講結(jié)束！

附：課程及課件pdf下載MIT英文網(wǎng)頁地址：
　　　http://people.csail.mit.edu/regina/6881/

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的MIT自然语言处理第五讲：最大熵和对数线性模型的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。