最大熵模型課件

最大熵模型

與

自然語言處理

MaxEntModel&NLP

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

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

MaximumEntropy最大熵模型

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

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

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

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

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

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

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

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

NonlinearProgrammingp:m維向量；H(p):關(guān)于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):關(guān)于p的非線性函數(shù)A:n*m常數(shù)矩陣；b:n維向量令：假設(shè)：A的行向量線性無關(guān)。拉格朗日算子

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

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

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是負(fù)數(shù)，Alice給Bob錢）。矩陣Ｃ如下：對偶問題Alicevs

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

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

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

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

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

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

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

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

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

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