自然語言處理中的最大熵方法第一頁，共三十八頁，2022年，8月28日綱要熵理論的發(fā)展信息熵最大熵理論最大熵理論的應用第二頁，共三十八頁，2022年，8月28日什么是熵什么是熵？沒有什么問題在科學史的進程中曾被更為頻繁地討論過普里高津熵定律是自然界一切定律中的最高定律里夫金&霍華德第三頁，共三十八頁，2022年，8月28日熵的提出德國物理學家克勞修斯（RudolphJ.Eclausius）于1865提出熵的概念其經(jīng)典意義定義為：

R表示可逆過程，即體系的熵變等于可逆過程吸收或耗散的熱量除以它的絕對溫度。第四頁，共三十八頁，2022年，8月28日熵原理的形象比喻一滴墨水滴入一杯清水中，墨水擴散后均勻地分布在清水中比喻熱力體系的自發(fā)過程總是趨于溫度均勻分布，

反之不行。第五頁，共三十八頁，2022年，8月28日微觀世界中熵的含義熱力學定律都是對物質宏觀性質進行考察得到的經(jīng)驗定律宏觀物體是大量微觀粒子構成的1872年，波爾茲曼（L．Boltzmann）指出熵是大量微觀粒子的位置和速度的分布概率的函數(shù)，是描述系統(tǒng)中大量微觀粒子的無序性的宏觀參數(shù)熵值高意味著無序性強!第六頁，共三十八頁，2022年，8月28日熵增原理一個孤立系統(tǒng)的熵，自發(fā)性地趨于極大，隨著熵的增加，有序狀態(tài)逐步變?yōu)榛煦鐮顟B(tài)，不可能自發(fā)地產(chǎn)生新的有序結構。當熵處于最小值,即能量集中程度最高、有效能量處于最大值時,那么整個系統(tǒng)也處于最有序的狀態(tài),相反為最無序狀態(tài)。熵增原理預示著自然界越變越無序第七頁，共三十八頁，2022年，8月28日熵的普遍性熵概念的泛化

熵理論是存在問題的，需要發(fā)展和完善第八頁，共三十八頁，2022年，8月28日熵與信息1948年電氣工程師香農(nóng)(Shannon)創(chuàng)立了信息論，將信息量與熵聯(lián)系起來。他用非常簡潔的數(shù)學公式定義了信息時代的基本概念：熵

H(p)=-p(x)logp(x)單位：bits第九頁，共三十八頁，2022年，8月28日通信中的熵表示“是”和“否”1=是0=否表示“是”、“否”和“可能是”11=是 00=否10(01)=可能是一條消息的熵就是編碼這條消息所需二進制位即比特的個數(shù)。第十頁，共三十八頁，2022年，8月28日隨機事件的熵熵定量的描述事件的不確定性設隨機變量，它有A1，A2，…，An共n個可能的結局，每個結局出現(xiàn)的機率分別為p1,p2，...，pn，則的不確定程度，即信息熵為:

熵越大，越不確定熵等于0，事件是確定的第十一頁，共三十八頁，2022年，8月28日例子拋硬幣擲色子（32個面）不公平的硬幣第十二頁，共三十八頁，2022年，8月28日熵的圖形第十三頁，共三十八頁，2022年，8月28日信息熵的意義信息熵概念為測試信息的多少找到了一個統(tǒng)一的科學定量計量方法，是信息論的基礎。信息熵將數(shù)學方法和語言學相結合第十四頁，共三十八頁，2022年，8月28日最大熵理論熵增原理在無外力作用下，事物總是朝著最混亂的方向發(fā)展事物是約束和自由的統(tǒng)一體事物總是在約束下爭取最大的自由權，這其實也是自然界的根本原則。在已知條件下，熵最大的事物，最可能接近它的真實狀態(tài)第十五頁，共三十八頁，2022年，8月28日最大熵原則下點的分布對一隨機過程，如果沒有任何觀測量，既沒有任何約束，則解為均勻分布第十六頁，共三十八頁，2022年，8月28日最大熵原則下點的分布第十七頁，共三十八頁，2022年，8月28日最大熵原則下點的分布第十八頁，共三十八頁，2022年，8月28日最大熵原則下點的分布第十九頁，共三十八頁，2022年，8月28日選擇最好的模型研究某個隨機事件，根據(jù)已知信息，預測其未來行為。當無法獲得隨機事件的真實分布時，構造統(tǒng)計模型對隨機事件進行模擬。滿足已知信息要求的模型可能有多個。第二十頁，共三十八頁，2022年，8月28日基于最大熵原理選擇模型選擇熵最大的模型Jaynes證明：對隨機事件的所有相容的預測中，熵最大的預測出現(xiàn)的概率占絕對優(yōu)勢Tribus證明，正態(tài)分布、伽瑪分布、指數(shù)分布等，都是最大熵原理的特殊情況第二十一頁，共三十八頁，2022年，8月28日基于最大熵的統(tǒng)計建模特征空間的確定特征選擇

建立統(tǒng)計模型

基于最大熵的統(tǒng)計建模即發(fā)現(xiàn)滿足已知條件的熵最大的模型第二十二頁，共三十八頁，2022年，8月28日基于最大熵的統(tǒng)計建模已有特征f1(x,y),f2(x,y)…,fn(x,y)特征的經(jīng)驗概率：特征的期望概率：如果樣本足夠多，可信度高的特征的經(jīng)驗概率與真實概率一致的由訓練樣本習得的模型,對可信度高的特征的估計應滿足約束等式:第二十三頁，共三十八頁，2022年，8月28日基于最大熵的統(tǒng)計建模事件的熵計算模型的最大熵得其中第二十四頁，共三十八頁，2022年，8月28日最大熵模型求解

參數(shù)估計GIS算法(GeneralizedIterativescaling)DarrochandRatcliff,1972IIS算法(ImprovedIterativeScaling)DellaPietra1995Input:特征函數(shù)特征分布Output:最優(yōu)參數(shù)值最優(yōu)模型第二十五頁，共三十八頁，2022年，8月28日IIS算法1Startwithforall2DoforeachaLetbethesolutiontobUpdatethevalueof3Gotostep2ifnotallhaveconverged第二十六頁，共三十八頁，2022年，8月28日詞義消歧的例子詞義消歧確定多義詞在一個句子中所表達的詞義“打”的語義：S1,S2,S3,S4S1打人S2打醬油S3打球S4打電話他打完籃球后給我打了個電話

??第二十七頁，共三十八頁，2022年，8月28日確定“打”的語義沒有任何先驗知識概率分布：

P(S1)=0.25P(S2)=0.25P(S3)=0.25P(S4)=0.25H(p)=-4X(0.25log20.25)=2熵值最大，最合理第二十八頁，共三十八頁，2022年，8月28日確定“打”的語義先驗知識:取S1或S3的概率：0.6取S2或S4的概率：0.4概率分布：

P(S1)=0.3P(S2)=0.2P(S3)=0.3P(S4)=0.2H(p)=-2X(0.2log20.2)-2X(0.3log20.3)符合約束的分布中，該分布熵值最大，最合理第二十九頁，共三十八頁，2022年，8月28日不存在沒有約束的自由他了那個壞人打=S1他打了二兩酒打=S2他喜歡打籃球打=S3他喜歡打電話打=S4他用手機打我打=S1他酒后打人打=S1一些人在打球打=S3第三十頁，共三十八頁，2022年，8月28日知識的獲取統(tǒng)計這些先驗知識（約束）(人，S1)(狗，S1)(醬油，S2)(酒，S2)(籃球，S3)(冰球，S3)(電話，S4)(手機，S4)(手機，S1)(酒，S1)(人，S3)第三十一頁，共三十八頁，2022年，8月28日知識的形式化表示在這些約束下，計算P(打=Si)，并滿足模型的熵最大引入特征函數(shù)

1ify=S3andx=籃球

0otherwise第三十二頁，共三十八頁，2022年，8月28日模型的建立特征選擇在所有的特征中，選擇最有代表性的特征，構造約束集合參數(shù)估計應用IIS算法，計算出每個特征對應的參數(shù)值第三十三頁，共三十八頁，2022年，8月28日特征選擇(1)最簡單的方法： 選擇出現(xiàn)次數(shù)大于n的特征Forexample:(AdwaitRatnaparkhi1999)Discardfeaturesthatoccurlessthan5times

代價最小第三十四頁，共三十八頁，2022年，8月28日特征選擇(2)原子特征算法(BasicFeatureSelection)1特征集合S=02任取一特征加入集合中3調用IIS，確定4在該約束集合下，計算熵的增量5選擇使熵值增加最大的特征加到S中6調用IIS，計算在此特征集下的7執(zhí)行2第三十五頁，共三十八頁，2022年，8月28日特征選擇（3）近似增益算法(ApproximateGains)已有特征對應參數(shù)增加特征對應的參數(shù)則增加的特征只影響當前參數(shù)，不變模型的形式:第三十六頁，共三十八頁，2022年，8月28日ReferenceA.BergerS.D.PietraV.D.PietraAmaximumentropyapproachtonaturallanguageprocessingComputationallinguistics1996,V22(1):39-71S.D.Pietra,V.D.PietraandJ.LaffertyInducingfeaturesofrandomfieldsIEEETransact