最大熵模型課件

最大熵模型

與

自然語言處理

MaxEntModel&NLP

laputaNLPGroup,AILab,TsinghuaUniv.TopicsNLP與隨機過程的關系（背景）最大熵模型的介紹（熵的定義、最大熵模型）最大熵模型的解決（非線性規(guī)劃、對偶問題、最大似然率）特征選取問題應用實例總結與啟發(fā)NLP與隨機過程NLP:已知一段文字：x1x2…xn（n個詞）標注詞性y1y2…yn標注過程：已知：x1x2…xn 求：y1已知：x1x2…xny1 求：y2已知：x1x2…xny1y2 求：y3已知：x1x2…xny1y2y3 求：y4…NLP與隨機過程yi可能有多種取值，yi被標注為a的概率有多少?隨機過程：一個隨機變量的序列。x1x2…xn p(y1=a|x1x2…xn)x1x2…xny1 p(y2=a|x1x2…xny1)x1x2…xny1y2 p(y3=a|x1x2…xny1y2)x1x2…xny1y2y3 p(y4=a|x1x2…xny1y2y3)…NLP與隨機過程x1x2…xn p(y1=a|x1x2…xn)x1x2…xny1 p(y2=a|x1x2…xny1)x1x2…xny1y2 p(y3=a|x1x2…xny1y2)x1x2…xny1y2y3 p(y4=a|x1x2…xny1y2y3)…問題：p(yi=a|x1x2…xny1y2…yi-1)怎么求?yi與x1x2…xny1y2…yi-1的關系?NLP與隨機過程問題：p(yi=a|x1x2…xny1y2…yi-1)怎么求?yi與x1x2…xny1y2…yi-1的關系?一個直觀的解決：問題again!(x1x2…xny1y2…yi-1)？What’sEntropy?AnExample：假設有5個硬幣：1,2,3,4,5，其中一個是假的，比其他的硬幣輕。有一個天平，天平每次能比較兩堆硬幣，得出的結果可能是以下三種之一：左邊比右邊輕右邊比左邊輕兩邊同樣重問：至少要使用天平多少次才能保證找到假硬幣?（某年小學生數(shù)學競賽題目:P）稱硬幣(cont.)答案：2次一種方法：Why最少2次?稱硬幣(cont.)Let:x是假硬幣的序號：Let:yi是第i次使用天平所得到的結果：用天平稱n次，獲得的結果是：y1y2…yny1y2…yn的所有可能組合數(shù)目是3n我們要通過y1y2…yn找出x。所以：每個y1y2…yn組合最多可能有一個對應的x取值。因為x取X中任意一個值的時候，我們都要能夠找出x，因此對于任意一個x的取值，至少要有一個y1y2…yn與之對應。根據鴿籠原理……稱硬幣(cont.)Let:x是假硬幣的序號：Let:Yi是第i次使用天平所得到的結果：用y1y2…yn表達x。即設計編碼：x->y1y2…ynX的“總不確定度”是：Y的“表達能力”是：至少要多少個Y才能準確表示X？稱硬幣(cont.)Why???為什么用log?“表達能力”與“不確定度”的關系？稱硬幣(cont.)為什么用log?假設一個Y的表達能力是H(Y)。顯然，H(Y)與Y的具體內容無關，只與|Y|有關。兩個Y(就是：y1y2)的表達能力是多少?y1可以表達三種情況，y2可以表達三種情況。兩個并列，一共有：3*3=9種情況（乘法原理）。因此：稱硬幣(cont.)“表達能力”與“不確定度”的關系？都表達了一個變量所能變化的程度。在這個變量是用來表示別的變量的時候，這個程度是表達能力。在這個變量是被表示變量的時候，這個程度是不確定度。而這個可變化程度，就是一個變量的熵（Entropy）。顯然：熵與變量本身含義無關，僅與變量的可能取值范圍有關。稱硬幣-Version.2假設有5個硬幣：1,2,3,…5，其中一個是假的，比其他的硬幣輕。已知第一個硬幣是假硬幣的概率是三分之一；第二個硬幣是假硬幣的概率也是三分之一，其他硬幣是假硬幣的概率都是九分之一。有一個天平，天平每次能比較兩堆硬幣，得出的結果可能是以下三種之一：左邊比右邊輕右邊比左邊輕兩邊同樣重假設使用天平n次找到假硬幣。問n的期望值至少是多少？（不再是小學生問題:P）稱硬幣-Version.2因為第一個、第二個硬幣是假硬幣的概率是三分之一，比其他硬幣的概率大，我們首先“懷疑”這兩個。第一次可以把這兩個做比較。成功的概率是三分之二。失敗的概率是三分之一。如果失敗了，第二次稱剩下的三個。所以，期望值是：稱硬幣-Version.2《數(shù)據結構》：Huffman編碼問題。稱硬幣-Version.2《數(shù)據結構》：Huffman編碼問題。稱硬幣-Version.2《數(shù)據結構》：Huffman編碼問題。用反證法可以證明，這個是最小值。（假設第一個和第二個硬幣中有一個要稱兩次的話……）稱硬幣-Version.2《數(shù)據結構》：Huffman編碼問題。稱硬幣-Version.3,4,…∞更廣泛地：如果一個隨機變量x的可能取值為X={x1,x2,…,xk}。要用n位y:y1y2…yn表示（每位y有c種取值）n的期望值至少為：一般地，我們令c為2（二進制表示），于是，X的信息量為：What’sEntropy?定義:X的具體內容跟信息量無關，我們只關心概率分布，于是H(X)可以寫成：熵的性質第一個等號在X為確定值的時候成立（沒有變化的可能）第二個等號在X均勻分布的時候成立。熵的性質證明：熵的性質證明：詳細證明略。求條件極值就可以證明了（求偏導數(shù)，條件是：所有的概率之和為1）結論：均勻分布的時候，熵最大ConditionalEntropy有兩個變量：x,y。它們不是獨立的。已知y，x的不確定度又是多少呢?ConditionalEntropyConditionReducesEntropy(C.R.E.)知識（Y）減少不確定性（X）證明（略）。用文氏圖說明：已知與未知的關系對待已知事物和未知事物的原則：承認已知事物（知識）；對未知事物不做任何假設，沒有任何偏見已知與未知的關系—例子已知：“學習”可能是動詞，也可能是名詞?？梢员粯藶橹髡Z、謂語、賓語、定語……令x1表示“學習”被標為名詞，x2表示“學習”被標為動詞。令y1表示“學習”被標為主語，y2表示被標為謂語，y3表示賓語，y4表示定語。得到下面的表示：如果僅僅知道這一點，根據無偏見原則，“學習”被標為名詞的概率與它被標為動詞的概率相等。已知與未知的關系—例子已知：“學習”可能是動詞，也可能是名詞?？梢员粯藶橹髡Z、謂語、賓語、定語……“學習”被標為定語的可能性很小，只有0.05除此之外，仍然堅持無偏見原則：我們引入這個新的知識：已知與未知的關系—例子已知：“學習”可能是動詞，也可能是名詞?？梢员粯藶橹髡Z、謂語、賓語、定語……“學習”被標為定語的可能性很小，只有0.05當“學習”被標作動詞的時候，它被標作謂語的概率為0.95除此之外，仍然堅持無偏見原則，我們盡量使概率分布平均。但問題是：什么是盡量平均的分布？引入這個新的知識：最大熵模型

MaximumEntropy概率平均分布〈=〉熵最大我們要一個x和y的分布，滿足：同時使H(Y|X)達到最大值最大熵模型

MaximumEntropy最大熵模型

MaximumEntropyWhatisConstraints?--模型要與已知知識吻合Whatisknown?--訓練數(shù)據集合一般模型：P={p|p是X上滿足條件的概率分布}特征(Feature)特征：(x,y)y:這個特征中需要確定的信息x:這個特征中的上下文信息注意一個標注可能在一種情況下是需要確定的信息，在另一種情況下是上下文信息：x1x2…xn p(y1=a|x1x2…xn)x1x2…xny1 p(y2=a|x1x2…xny1)樣本(Sample)關于某個特征(x,y)的樣本--特征所描述的語法現(xiàn)象在標準集合里的分布：(xi,yi)pairsyi是y的一個實例xi是yi的上下文(x1,y1)(x2,y2)(x3,y3)…… 特征與樣本已知：“學習”可能是動詞，也可能是名詞?？梢员粯藶橹髡Z、謂語、賓語、定語……“學習”被標為定語的可能性很小，只有0.05特征：當“學習”被標作動詞的時候，它被標作謂語的概率為0.95x是什么?y是什么?樣本是什么?特征與樣本已知：“學習”可能是動詞，也可能是名詞。可以被標為主語、謂語、賓語、定語……特征：“學習”被標為定語的可能性很小，只有0.05當“學習”被標作動詞的時候，它被標作謂語的概率為0.95x是什么?y是什么?樣本是什么?特征與樣本特征函數(shù)：對于一個特征(x0,y0)，定義特征函數(shù)：特征函數(shù)期望值：對于一個特征(x0,y0)，在樣本中的期望值是：是(x,y)在樣本中出現(xiàn)的概率條件（Constraints）條件：對每一個特征(x,y)，模型所建立的條件概率分布要與訓練樣本表現(xiàn)出來的分布相同。假設樣本的分布是（已知）：特征f在模型中的期望值：最大熵模型

MaximumEntropyNLP模型：P={p|p是y|x的概率分布并且滿足下面的條件}對訓練樣本，對任意給定的特征fi：最大熵模型

MaximumEntropyNLP模型：定義條件熵模型目的定義特征函數(shù)約束條件（1）（2）該條件約束優(yōu)化問題的Lagrange函數(shù)最大熵模型：最大熵模型的解決問題：已知若干條件，要求若干變量的值使到目標函數(shù)（熵）最大數(shù)學本質：最優(yōu)化問題（OptimizationProblem）條件：線性、等式目標函數(shù)：非線性非線性規(guī)劃（線性約束）(non-linearprogramming

withlinearconstraints)非線性規(guī)劃基本概念

NonlinearProgramming解決的思路：非線性規(guī)劃問題（帶約束）（拉格朗日法）->非線性規(guī)劃問題（不帶約束UnconstrainedProblem）（求偏導數(shù)法）->解決不帶約束求解問題（解方程）->求出原問題的解法非線性規(guī)劃基本概念

NonlinearProgrammingp:m維向量；H(p):關于p的非線性函數(shù)A:n*m常數(shù)矩陣；b:n維向量如何去掉約束？抽象問題：假設：A的行向量線性無關。確定了m維空間里面n個方向上（就是與Ap=b確定的m-n個方向“垂直”的n個方向）的取值。p只能在剩下的r=m-n個方向上面移動。非線性規(guī)劃基本概念

NonlinearProgramming假設Z是跟Ap=b垂直的方向量。Z:m*(m-n)常數(shù)矩陣)

就是p能夠自由活動的所有空間了。v:m-n維變量于是有：非線性規(guī)劃基本概念

NonlinearProgrammingp:m維向量；H(p):關于p的非線性函數(shù)A:n*m常數(shù)矩陣；b:n維向量如何去掉約束？抽象問題：Z:m*(m-n)常數(shù)矩陣v:m-n維變量極值條件Z:m*(m-n)常數(shù)矩陣v:m-n維變量極值條件：把分解成Z方向向量和A方向向量：極值條件Z:m*(m-n)常數(shù)矩陣v:m-n維變量極值條件p:m維向量；H(p):關于p的非線性函數(shù)A:n*m常數(shù)矩陣；b:n維向量令：假設：A的行向量線性無關。拉格朗日算子

LagrangeMultiplier一般地，對于k個限制條件的ConstrainedOptimization問題：拉格朗日函數(shù)為：其中引入的拉格朗日算子：拉格朗日算子

LagrangeMultiplier拉格朗日函數(shù)可能的最優(yōu)解（Exponential）最優(yōu)解的存在性一階導數(shù)為零，二階導數(shù)小于零，所得到的是最大值！最優(yōu)解形式（Exponential）最優(yōu)解（Exponential）最優(yōu)解（Exponential）能不能找到另一種逼近？比如……等價成求某個函數(shù)的最大/最小值？幾乎不可能有解析解（包含指數(shù)函數(shù)）近似解不代表接近駐點。對偶問題

Duality對偶問題的引入。Alice和Bob的游戲：有一個2*2的矩陣Ｃ。每次Alice挑一個數(shù)x(x=1或者2)，Bob也挑一個數(shù)y(y=1或者2)。兩人同時宣布所挑的數(shù)字。然后看Cx,y是多少，Bob要付AliceCx,y塊錢。（如果Cx,y是負數(shù)，Alice給Bob錢）。矩陣Ｃ如下：對偶問題Alicevs

Bob假設：Alice和Bob都是聰明而貪得無厭的人。而且他們都清楚對方也很聰明和很貪心。Alice的策略：找一個x，無論Bob怎么挑y，Cx,y要盡量大。Bob的策略：找一個y，無論Alice怎么挑x，Cx,y要盡量小。雙方都很聰明：雙方都對對方有“最壞打算”對偶問題Alicevs

BobAlice的選擇：x*=2Bob的選擇：y*=2Alicevs

BobVersion.2Alice的選擇：x*=1Bob的選擇：y*=2對偶問題Alicevs

BobVersion1:Alice的估計=結果=Bob的估計Version2:Alice的估計<結果=Bob的估計一般情況:Alice的估計<=結果<=Bob的估計定理：當存在馬鞍點（SaddlePoint）的時候，等號成立。并且結果=馬鞍點的值。馬鞍點：非線性規(guī)劃中的對偶問題拉格朗日函數(shù)：于是：因此，為了盡量大，p的選取必須保證考慮：對偶問題與拉格朗日函數(shù)：同時：等價于：而對偶問題與拉格朗日函數(shù)：梯度遞減法把p*代入L，得到：令：梯度遞減法求導，計算-L的梯度：梯度遞減法遞推公式：收斂問題……最大似然率

MaximumLikelihood最大似然率：找出與樣本的分布最接近的概率分布模型。簡單的例子。10次拋硬幣的結果是：畫畫字畫畫畫字字畫畫假設p是每次拋硬幣結果為“畫”的概率。則：得到這樣的實驗結果的概率是：最大似然率

MaximumLikelihood最大似然率：找出與樣本的分布最接近的概率分布模型。最優(yōu)解是：p=0.7似然率的一般定義：最大似然率

MaximumLikelihood似然率的一般定義：似然率的對數(shù)形式：最大似然率

MaximumLikelihood在NLP里面，要估計的是：似然率是：是常數(shù)，可以忽略最大似然率

MaximumLikelihood在NLP里面，要估計的是：似然率可以定義為：通過求值可以發(fā)現(xiàn)，如果p(y|x)的形式是最大熵模型的形式的話，最大熵模型與最大似然率模型一致。最大似然率為書寫方便，令：最大似然率最大似然率

MaximumLikelihood結論：最大熵的解（無偏見地對待不確定性）同時是最吻合樣本數(shù)據分布的解。進一步證明了最大熵模型的合理性。偶然？必然？“Itsohappensthat…”???熵：不確定度似然率：與知識的吻合度最大熵：對不確定度的無偏見分配最大似然率：對知識的無偏見理解知識＝不確定度的補集特征選取問題問題：所有知識可信嗎？所有知識都有用嗎？太多知識怎么辦？在NLP里面：上下文信息可以很多很多種，那些是有用呢？特征選取問題Remind:

“熵是描述不確定度的”“知識是不確定度的補集”－－不確定度越小，模型越準確。直觀的過程：什么特征都不限定：熵最大加一個特征：熵少一點（C.R.E.）加的特征越多，熵越少……特征選取算法目標：選擇最有用的Ｋ個特征（知識）“最”？－－全局的最優(yōu)解幾乎不可能可行的方法：逐步選擇最有用的信息。每一步用“貪心”原則：挑選“現(xiàn)在看來”最有用的那個特征?！坝杏?？”使到走這一步后熵減少最多算法步驟有效特征集合E={}//這個時候p均勻分布計算最大熵H(p*)。顯然：對以下步驟循環(huán)K次：對每個不在E里面的特征fi，把E+{fi}作為有效特征，計算最大熵Hi(pi*)；假設Hm(pm*)最小，則：E=E+{fm}。敏感度分析與特征提取

SensitivityHowtoworkoninsufficientdataset?最終結論應該是約束條件越確定（_p(x)越大），lambda越大。應用實例AdwaitRatnaparkhi’s“LearningtoParseNaturalLanguagewithMaximumEntropyModels”創(chuàng)新點：用MaxEnt模型輔助Shift-reduceParsing應用實例Parser的特點：三層ParserK-BFS搜索——每層只搜索最好的K個方案(derivations)“最好”：概率最大概率：最大熵模型得到的概率分布應用實例數(shù)據流：應用實例概率：最大熵模型得到的概率分布事先對每類Parsing都訓練一個最大熵模型。得到概率分布：pX*(a|c)。a是action，c是上下文。X可能是：TAG,CHUNK,BUILD/CHECK最優(yōu)解求法：GIS（GeneralIterativeScalingAlgorithm“一般梯度算法”？）特征選?。褐蝗〕霈F(xiàn)次數(shù)大于等于5的所有特征（比較簡單，但因此計算量也少多了）應用實例實驗結果：Upenn的Corpus作為訓練集合WallStreetJournal上的句子作為測試對象準確率：90%左右應用實例分析：三層Parser功不可沒（上層Parser看到的是下層Parser的所有信息—包括處理點之前和之后的信息）MaxEnt模型提供了比較準確的評價模型（不然三層Parser會比單層Parser引起更大的誤差累積，“失之毫厘謬以千里”）相關項目CMU:AdamBergerUPenn:AdwaitRatnaparkhiSourceForge:opennlp.

MAXENT……總結與啟發(fā)MaxEnt已經是比較成功的一個NLP模型，并獲得廣泛應用從信息論獲得啟發(fā)（1948-）：自然語言處理也是信息處理的一種。語法標注也可以看作一種編碼的過