文本信息處理預(yù)備知識(shí)

1、文本信息處理,章成志Department of Information Management, School of Economics and Management,Nanjing University of Science and Technology E-Mail: zhangchz@istic.ac.cn Sina weibo: @章成志

2、 Blog: http://blog.sciencenet.cn/u/timy,2,預(yù)備知識(shí),預(yù)備知識(shí),概率統(tǒng)計(jì)基礎(chǔ)信息論基礎(chǔ)集合論基礎(chǔ)線性代數(shù)基礎(chǔ)實(shí)驗(yàn)數(shù)據(jù)性能評(píng)價(jià)編程工具,3,——宗成慶. 統(tǒng)計(jì)自然語(yǔ)言處理. 北京：清華大學(xué)出版社,2008.——?jiǎng)⑷? 計(jì)算語(yǔ)言學(xué)課件,概率統(tǒng)計(jì)基礎(chǔ),?樣本空間?事件、隨機(jī)變量?概率?條件概率?聯(lián)合概率?獨(dú)立事件?貝葉斯原理?期望與方差?概率分布?協(xié)方差

3、、相關(guān)系數(shù)?參數(shù)估計(jì)?極大似然估計(jì)?隨機(jī)過程?馬爾科夫過程,4,概率統(tǒng)計(jì)基礎(chǔ),概率(Probability),5,概率是從隨機(jī)實(shí)驗(yàn)中的事件到實(shí)數(shù)域的函數(shù)，用以表示事件發(fā)生的可能性。如果用P(A) 作為事件A的概率，?是實(shí)驗(yàn)的樣本空間，則概率函數(shù)必須滿足如下公理：公理1（非負(fù)性）： P(A) ? 0公理2（規(guī)范性）： P(?) = 1公理3（可列可加性）：如果對(duì)任意的 i和 j ( i ≠ j

4、)，事件 Ai和 Aj不相交( Ai∩Aj＝Φ)，則有：,概率統(tǒng)計(jì)基礎(chǔ),最大似然估計(jì)(Maximization Likelihood Estimation),6,概率統(tǒng)計(jì)基礎(chǔ),7,概率統(tǒng)計(jì)基礎(chǔ),條件概率(Conditional Probability),8,概率統(tǒng)計(jì)基礎(chǔ),全概率公式,9,概率統(tǒng)計(jì)基礎(chǔ),10,

5、概率統(tǒng)計(jì)基礎(chǔ),貝葉斯法則(Bayes’ Theorem),11,概率統(tǒng)計(jì)基礎(chǔ),貝葉斯決策理論(Bayesian Decision Theory),12,概率統(tǒng)計(jì)基礎(chǔ),例子 假設(shè)某一種特殊的句法結(jié)構(gòu)很少出現(xiàn)，平均大約每100,000個(gè)句子中才可能出現(xiàn)一次。我們開發(fā)了一個(gè)程序來判斷某個(gè)句子中是否存在這種特殊的句法結(jié)構(gòu)。如果句子中確實(shí)含有該特殊句法結(jié)構(gòu)時(shí)，程序判斷結(jié)果為“存在”的概率為0.95。如果句子中實(shí)際上不存在該句法

6、結(jié)構(gòu)時(shí)，程序錯(cuò)誤地判斷為“存在”的概率為0.005。那么，這個(gè)程序測(cè)得句子含有該特殊句法結(jié)構(gòu)的結(jié)論是正確的概率有多大？,13,概率統(tǒng)計(jì)基礎(chǔ),假設(shè)G 表示事件“句子確實(shí)存在該特殊句法結(jié)構(gòu)”，T 表示事件“程序判斷的結(jié)論是存在該特殊句法結(jié)構(gòu)”。那么，我們有：,14,求：P(G|T)= ?,概率統(tǒng)計(jì)基礎(chǔ),二項(xiàng)式分布(Binomial Distribution),15,概率統(tǒng)計(jì)基礎(chǔ),二項(xiàng)式分布(Binomial Distribution),16

7、,概率統(tǒng)計(jì)基礎(chǔ),二項(xiàng)式分布(Binomial Distribution),17,在自然語(yǔ)言處理中，常以句子為處理單位。一般地，我們假設(shè)一個(gè)語(yǔ)句獨(dú)立于它前面的其它語(yǔ)句，句子的概率分布近似地認(rèn)為符合二項(xiàng)式分布。,概率統(tǒng)計(jì)基礎(chǔ),期望(Expectation),18,概率統(tǒng)計(jì)基礎(chǔ),方差(Variance),19,N元語(yǔ)法模型,20,N元語(yǔ)法模型,21,信息論基礎(chǔ),?信息量?互信息?熵?聯(lián)合熵、條件熵?交叉熵?困惑度、混亂度Perple

8、xity?噪聲信道模型,22,信息論基礎(chǔ),熵(Entropy),23,香農(nóng)(Claude Elwood Shannon)于1940年獲得MIT 數(shù)學(xué)博士學(xué)位和電子工程碩士學(xué)位后，于1941年加入了貝爾實(shí)驗(yàn)室數(shù)學(xué)部，并在那里工作了15年。1948年6月和10月，由貝爾實(shí)驗(yàn)室出版的《貝爾系統(tǒng)技術(shù)》雜志連載了香農(nóng)博士的文章《通訊的數(shù)學(xué)原理》，該文奠定了香農(nóng)信息論的基礎(chǔ)。 熵是信息論中重要的基本概念。,信息論基礎(chǔ),熵(entropy),2

9、4,信息論基礎(chǔ),熵(entropy),25,熵又稱為自信息（self-information），表示信源 X 每發(fā)一個(gè)符號(hào)(不論發(fā)什么符號(hào))所提供的平均信息量。熵也可以被視為描述一個(gè)隨機(jī)變量的不確定性的數(shù)量。一個(gè)隨機(jī)變量的熵越大，它的不確定性越大。那么，正確估計(jì)其值的可能性就越小。越不確定的隨機(jī)變量越需要大的信息量用以確定其值。,信息論基礎(chǔ),例子,26,計(jì)算下列兩種情況下英文（26個(gè)字母和空格，共27個(gè)字符）信息源的熵: (1)假設(shè)2

10、7個(gè)字符等概率出現(xiàn)；(2)假設(shè)英文字母的概率分布如下：,信息論基礎(chǔ),解：,27,說明：考慮了英文字母和空格實(shí)際出現(xiàn)的概率后，英文信源的平均不確定性，比把字母和空格看作等概率出現(xiàn)時(shí)英文信源的平均不確定性要小。,信息論基礎(chǔ),詞熵、字母熵、漢字熵,28,馮志偉計(jì)算出：–漢字的熵為9.65比特–法語(yǔ)一個(gè)字母的熵為3.98比特–意大利語(yǔ)一個(gè)字母的熵為4.00比特–西班牙語(yǔ)一個(gè)字母的熵為4.01比特–英語(yǔ)一個(gè)字母的熵為4.03比特–

11、德語(yǔ)一個(gè)字母的熵為4.12比特–俄語(yǔ)一個(gè)字母的熵為4.35比特,信息論基礎(chǔ),29,1970年代末期馮志偉首先開展了對(duì)漢字信息熵的研究，經(jīng)過幾年的語(yǔ)料收集和手工統(tǒng)計(jì)，在當(dāng)時(shí)艱苦的條件下測(cè)定了漢字的信息熵為9.65比特(bit)。1980年代末期，劉源等測(cè)定了漢字的信息熵為9.71 比特，而漢語(yǔ)詞的熵為11.46比特。漢語(yǔ)詞匯平均長(zhǎng)度約為2.5個(gè)漢字。,信息論基礎(chǔ),30,信息論基礎(chǔ),31,聯(lián)合熵(Joint Entropy),信息論

12、基礎(chǔ),32,條件熵(Conditional Entropy),信息論基礎(chǔ),33,信息論基礎(chǔ),34,例： 假設(shè)(X, Y)服從如下聯(lián)合分布：,請(qǐng)計(jì)算H(X)、H(Y) 、H(X|Y)、H(Y|X) 和H(X, Y)各是多少？,信息論基礎(chǔ),35,信息論基礎(chǔ),36,信息論基礎(chǔ),37,信息論基礎(chǔ),38,信息論基礎(chǔ),39,相對(duì)熵(Relative Entropy, 或Kullback-Leibler divergence, KL 距離),

13、兩個(gè)概率分布p(x) 和q(x) 的相對(duì)熵定義為：,(18),信息論基礎(chǔ),40,對(duì)熵常被用以衡量?jī)蓚€(gè)隨機(jī)分布的差距。當(dāng)兩個(gè)隨機(jī)分布相同時(shí)，其相對(duì)熵為0。當(dāng)兩個(gè)隨機(jī)分布的差別增加時(shí)，其相對(duì)熵也增加。,信息論基礎(chǔ),交叉熵(Cross Entropy),41,(19),信息論基礎(chǔ),困惑度(Perplexity),42,(20),信息論基礎(chǔ),互信息(Mutual Information),43,如果(X, Y) ~ p(x, y)，X, Y之間

14、的互信息 I(X; Y)定義為： I (X; Y) = H(X) – H(X | Y) (21),(22),信息論基礎(chǔ),44,信息論基礎(chǔ),應(yīng)用：中文分詞問題,45,利用互信息值估計(jì)兩個(gè)漢字結(jié)合的強(qiáng)度：,互信息值越大，表示兩個(gè)漢字之間的結(jié)合越緊密，越可能成詞。反之，斷開的可能性越大。,信息論基礎(chǔ),46,信息論基礎(chǔ),47,信息論基礎(chǔ),48,噪聲信道模型(Noisy Channel Mod

15、el),在信號(hào)傳輸?shù)倪^程中都要進(jìn)行雙重性處理：一方面要通過壓縮消除所有的冗余，另一方面又要通過增加一定的可控冗余以保障輸入信號(hào)經(jīng)過噪聲信道后可以很好的恢復(fù)原狀。信息編碼時(shí)要盡量占用少量的空間，但又必須保持足夠的冗余以便能夠檢測(cè)和校驗(yàn)錯(cuò)誤。接收到的信號(hào)需要被解碼使其盡量恢復(fù)到原始的輸入信號(hào)。噪聲信道模型的目標(biāo)就是優(yōu)化噪聲信道中信號(hào)傳輸?shù)耐掏铝亢蜏?zhǔn)確率，其基本假設(shè)是一個(gè)信道的輸出以一定的概率依賴于輸入。,信息論基礎(chǔ),49,信息論基礎(chǔ),5

16、0,信息論基礎(chǔ),51,(23),信息論基礎(chǔ),52,(24),信息論基礎(chǔ),53,信息論基礎(chǔ),54,(25),信息論基礎(chǔ),55,信息論基礎(chǔ),56,集合論基礎(chǔ),57,集合論基礎(chǔ),58,線性代數(shù)基礎(chǔ),59,? 向量空間模型,線性代數(shù)基礎(chǔ),60,向量的內(nèi)積,61,向量的長(zhǎng)度,62,⑵ 向量長(zhǎng)度的性質(zhì),向量的單位化,63,實(shí)驗(yàn)數(shù)據(jù),64,?訓(xùn)練集Training Set – 用來獲得模型參數(shù)?測(cè)試集Test Set –從訓(xùn)練集以

17、外獨(dú)立采樣 –反映系統(tǒng)面對(duì)真實(shí)世界的處理能力?封閉測(cè)試與開放測(cè)試?交叉驗(yàn)證Cross-Validation –將數(shù)據(jù)集分為k個(gè)子集 –用k-1個(gè)子集作訓(xùn)練集，1個(gè)子集作測(cè)試集，然后k 次交叉驗(yàn)證?公開測(cè)評(píng)數(shù)據(jù)集 -LDC, Chinese-LDC,性能評(píng)價(jià),65,性能評(píng)價(jià),66,編程工具,編程語(yǔ)言：Python, java, C++編程工具：NLTK,67,什么是Python?,6

18、8,Python的特點(diǎn),歷史短（不到10年），但應(yīng)用廣泛 –大范圍應(yīng)用，尤其在AI和Web領(lǐng)域非常容易學(xué)習(xí) –很多學(xué)校用把Python作為入門語(yǔ)言編程方便 –相比C、C++、Java代碼短得多容易閱讀與維護(hù) –類似于自然語(yǔ)言和數(shù)學(xué)公式的語(yǔ)法,69,“Hello World!”,70,NLTK工具,NLTK：Natural Language ToolkitNLTK是用Python實(shí)現(xiàn)的一套自然語(yǔ)言