自然語言處理中的最大熵方法

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

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

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

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

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

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

建立統(tǒng)計(jì)模型

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

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

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

P(S1)=0.25P(S2)=0.25P(S3)=0.25P(S4)=0.25H(p)=-4X(0.25log20.25)=2熵值最大，最合理第二十八頁，共三十八頁，2022年，8月28日確定“打”的語義先驗(yàn)知識(shí):取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日不存在沒有約束的自由他了那個(gè)壞人打=S1他打了二兩酒打=S2他喜歡打籃球打=S3他喜歡打電話打=S4他用手機(jī)打我打=S1他酒后打人打=S1一些人在打球打=S3第三十頁，共三十八頁，2022年，8月28日知識(shí)的獲取統(tǒng)計(jì)這些先驗(yàn)知識(shí)（約束）(人，S1)(狗，S1)(醬油，S2)(酒，S2)(籃球，S3)(冰球，S3)(電話，S4)(手機(jī)，S4)(手機(jī)，S1)(酒，S1)(人，S3)第三十一頁，共三十八頁，2022年，8月28日知識(shí)的形式化表示在這些約束下，計(jì)算P(打=Si)，并滿足模型的熵最大引入特征函數(shù)

1ify=S3andx=籃球

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

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