最大熵模型簡(jiǎn)介課件

GenerativeModelvs.DiscriminativeModelGenerativeModel(GM):P(Y|X)=P(X|Y)P(Y)/P(X)，通過(guò)求解P(X|Y)和P(Y)來(lái)求解P(Y|X)DiscriminativeModel(DM):對(duì)P(Y|X)直接建模GMDMGaussiansMixturesofGaussiansHMMNa?veBayesBayesianNetworkMRF(馬爾科夫隨機(jī)場(chǎng))LogisticRegressionSVMskNNMaxEnt(最大熵模型)MEMM(最大熵馬爾科夫模型)CRF(條件隨機(jī)場(chǎng)模型)VotedPerceptronNeuralNetwork綱要最大熵原理最大熵模型定義最大熵模型中的一些算法最大熵模型的應(yīng)用總結(jié)思考題綱要最大熵原理最大熵模型定義最大熵模型中的一些算法最大熵模型的應(yīng)用總結(jié)思考題最大熵原理(MaximumEntropyPrinciple)信息熵：熵的概念最先在1864年首先由克勞修斯提出，

1948年美國(guó)電器工程師香農(nóng)(Shannon,C.E)在《通信的數(shù)學(xué)理論》中，把“熵”用來(lái)表示一個(gè)隨機(jī)事件的“不確定性”或信息量的量度。隨機(jī)事件的不確定性信息量概率分布消除熵(Entropy)一個(gè)離散隨機(jī)變量X，其概率分布函數(shù)為p(x)，則X的熵定義為：由于H只與p(x)有關(guān)，所以有時(shí)也寫成H(p)通常對(duì)數(shù)以2為底，H代表了X的信息量，也可以認(rèn)為是對(duì)X進(jìn)行二進(jìn)制編碼所需要的平均編碼長(zhǎng)度性質(zhì)：X只取某個(gè)確定值的時(shí)左邊等號(hào)成立X為均勻分布時(shí)右邊等號(hào)成立

聯(lián)合熵、條件熵、互信息隨機(jī)變量X、Y的聯(lián)合分布是p(x,y)，它們的聯(lián)合熵(JointEntropy)為條件熵(ConditionalEntropy)互信息(MutualInformation)有人稱紅色方框內(nèi)式子為互信息I(x,y)或者點(diǎn)互信息，將I(X,Y)稱為平均互信息。一個(gè)是對(duì)變量的具體值求值，一個(gè)是對(duì)隨機(jī)變量求值，請(qǐng)注意區(qū)分一個(gè)例子一個(gè)6面的骰子，各面的點(diǎn)數(shù)分別為1,2,…,6，令X表示拋出后朝上的點(diǎn)數(shù)。分布一p1：p(X=1)=p(X=2)=…=p(X=6)=1/6分布二p2：p(X=1)=p(X=2)=1/4,p(X=3)=p(X=4)=p(X=5)=p(X=6)=1/8分布三p3:只有已知條件p(X=1)+p(X=2)=0.6H(p1)=1/6*log6*6=log6≈2.58H(p2)=2*1/4*log4+4*1/8*log8=2.5p1vsp2:分布一具有更大的熵(信息量)，即具有更大的不確定性。p3*=argmax(H(p3)),此時(shí)p(X=1)=p(X=2)=0.3,p(X=3)=p(X=4)=p(X=5)=p(X=6)=0.1最大熵原理最大熵原理：1957年由E.T.Jaynes

提出。主要思想：

在只掌握關(guān)于未知分布的部分知識(shí)時(shí)，應(yīng)該選取符合這些知識(shí)但熵值最大的概率分布。原理的實(shí)質(zhì)：

前提：已知部分知識(shí)關(guān)于未知分布最合理的推斷＝符合已知知識(shí)最不確定或最隨機(jī)的推斷。 這是我們可以作出的唯一不偏不倚的選擇，任何其它的選擇都意味著我們?cè)黾恿似渌募s束和假設(shè)，這些約束和假設(shè)根據(jù)我們掌握的信息無(wú)法作出。一些現(xiàn)象熱力學(xué)：熱學(xué)中一個(gè)重要的基本現(xiàn)象是趨向平衡態(tài)，這是一個(gè)不可逆過(guò)程，即朝熵增加的方向轉(zhuǎn)變。社會(huì)學(xué)：共產(chǎn)主義經(jīng)濟(jì)學(xué)：消除壟斷哲學(xué)：中庸家庭：婆家、娘家……最大熵原理一個(gè)正確的概率分布p應(yīng)該滿足下面兩個(gè)條件：（1）服從樣本數(shù)據(jù)中的已知統(tǒng)計(jì)證據(jù)。（2）使熵最大化。 其中，，P表示所有可能的概率分布。最大熵原理特征：用來(lái)表示從樣本中獲得的統(tǒng)計(jì)證據(jù)。也就是使得熵最大的概率分布p必須受到特征的限制。通常為一個(gè)二值函數(shù)。例如：在詞性標(biāo)注中，可定義特征如下：

綱要最大熵原理最大熵模型定義最大熵模型中的一些算法最大熵模型的應(yīng)用總結(jié)思考題最大熵模型(MaximumEntropyModel)假設(shè)有一個(gè)樣本集合，我們給出k個(gè)特征，特征j對(duì)p的制約可以表示為,

表示在概率分布為p時(shí)特征的期望。表示特征的樣本期望值。最大熵模型無(wú)任何先驗(yàn)知識(shí)：存在先驗(yàn)知識(shí)：(求滿足一組條件的最優(yōu)解問(wèn)題)最大熵模型例如：給定一個(gè)詞假定已知存在四種詞性：名詞、動(dòng)詞、介詞、指代詞如果該詞在語(yǔ)料庫(kù)中出現(xiàn)過(guò)，并且屬于名詞的概率為70%，則判斷該詞屬于名詞的概率為0.7，屬于其他三種詞性的概率均為0.1如果該詞沒(méi)有在語(yǔ)料庫(kù)中出現(xiàn)，則屬于四種詞性的概率為0.25在符合已知情況的前提下，使未知事件的概率分布盡可能均勻最大熵模型－條件分布假設(shè)有一個(gè)樣本集合，表示一個(gè)上下文，表示對(duì)應(yīng)的結(jié)果。假設(shè)我們給出k個(gè)特征，對(duì)每個(gè)特征給出條件限制：期望概率值等于經(jīng)驗(yàn)概率值其中：最大熵模型－條件分布

是模型參數(shù)，可以看成是特征函數(shù)的權(quán)重。帶約束非線性規(guī)劃問(wèn)題:拉格朗日乘子算法模型訓(xùn)練：即求的值。綱要最大熵原理最大熵模型定義最大熵模型中的一些算法最大熵模型的應(yīng)用總結(jié)思考題最大熵模型中的一些算法GIS(GeneralizedIterativeScaling)算法、IIS(ImprovedIterativeScaling)算法或者QuasiNewton算法

參數(shù)估計(jì)算法：用來(lái)得到具有最大熵分布的參數(shù)的值。FI算法(特征引入算法，F(xiàn)eatureInduction)

解決如何選擇特征的問(wèn)題：通常采用一個(gè)逐步增加特征的辦法進(jìn)行，每一次要增加哪個(gè)特征取決于樣本數(shù)據(jù)。AlgorithmsGeneralizedIterativeScaling(GIS):(DarrochandRatcliff,1972)ImprovedIterativeScaling(IIS):(DellaPietraetal.,1995)GIS:setupRequirementsforrunningGIS:Obeyformofmodelandconstraints:Anadditionalconstraint:LetAddanewfeaturefk+1:GISalgorithmComputedj,j=1,…,k+1Initialize(anyvalues,e.g.,0)RepeatuntilconvergeForeachjCompute

UpdatewhereApproximationforcalculatingfeatureexpectationPropertiesofGISL(p(n+1))>=L(p(n))Thesequenceisguaranteedtoconvergetop*.Theconvergecanbeveryslow.TherunningtimeofeachiterationisO(NPA):N:thetrainingsetsizeP:thenumberofclassesA:theaveragenumberoffeaturesthatareactiveforagivenevent(a,b).IISalgorithmComputedj,j=1,…,k+1andInitialize(anyvalues,e.g.,0)RepeatuntilconvergeForeachjLetbethesolutionto

UpdateCalculatingIfThenGISisthesameasIISElsemustbecalculatednumerically.FI算法—特征引入特征選取的衡量標(biāo)準(zhǔn)：信息增益一個(gè)特征對(duì)所處理問(wèn)題帶來(lái)的信息越多，越適合引入到模型中。首先形式化一個(gè)特征空間，所有可能的特征都為候補(bǔ)特征。然后從候補(bǔ)特征集合中選取對(duì)模型最為有用的特征集合。FI算法(續(xù))輸入：候補(bǔ)特征集合F，經(jīng)驗(yàn)分布輸出：模型選用的特征集合S，結(jié)合這些特征的模型Ps初始化：特征集合S為空，它所對(duì)應(yīng)的模型Ps均勻分布，n＝0對(duì)于候補(bǔ)特征集合F中的每一個(gè)特征f，計(jì)算該特征加入模型后為模型帶來(lái)的增益值Gf。選擇具有最大增益值的G(S,f)的特征fn。把特征fn加入到集合S中，S=(f1,f2,…fn);重新調(diào)整參數(shù)值，使用GIS算法計(jì)算模型Ps.n=n+1,返回步驟2。FI算法(續(xù))計(jì)算增益量：Kullback-Leibler(KL)距離(也叫相對(duì)熵)兩個(gè)概率p、q的KL距離：基本思想：距離越小，分布越接近。FI算法(續(xù))引入第i個(gè)特征fi后的增益值：選擇的特征：綱要最大熵原理最大熵模型定義最大熵模型中的一些算法最大熵模型的應(yīng)用總結(jié)思考題最大熵模型的應(yīng)用—詞性標(biāo)注任務(wù)：根據(jù)上下文，求詞的詞性利用最大熵模型求特征定義：即為語(yǔ)料庫(kù)中詞性為DET的that出現(xiàn)次數(shù)除以語(yǔ)料庫(kù)中總詞數(shù)綱要最大熵原理最大熵模型定義最大熵模型中的一些算法最大熵模型的應(yīng)用總結(jié)思考題總結(jié)最大熵模型用途：進(jìn)行概率估計(jì)。

在已知條件下，如何選擇一個(gè)合適的分布來(lái)預(yù)測(cè)事件。優(yōu)點(diǎn)：只需集中精力選擇特征，不需考慮如何使用這些特征。特征選擇靈活，容易更換。各個(gè)特征之間可以毫不相關(guān)。便于從多個(gè)角度來(lái)描述問(wèn)題。無(wú)需做獨(dú)立性假設(shè)。綱要最大熵原理最大熵模型定義最大熵模型中的一些算法最大熵模型的應(yīng)用總結(jié)思考題思考如何利用最大熵模型來(lái)進(jìn)行中文文本分類？參看：李榮陸等，使用最大熵模型進(jìn)行中文文本分類，計(jì)算機(jī)研究與發(fā)展，2005，42(1):94-101參考文獻(xiàn)Amaximumentropyapproachtonaturallanguageprocessing(AdamBerger)ABriefMaxEntTutorial(AdamBerger)Learningtoparsenaturallanguagewithmaximumentropymo