文本信息處理預備知識

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,預備知識,預備知識,概率統(tǒng)計基礎(chǔ)信息論基礎(chǔ)集合論基礎(chǔ)線性代數(shù)基礎(chǔ)實驗數(shù)據(jù)性能評價編程工具,3,——宗成慶. 統(tǒng)計自然語言處理. 北京：清華大學出版社,2008.——劉群. 計算語言學課件,概率統(tǒng)計基礎(chǔ),?樣本空間?事件、隨機變量?概率?條件概率?聯(lián)合概率?獨立事件?貝葉斯原理?期望與方差?概率分布?協(xié)方差

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

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

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

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

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

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

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

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

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

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

13、兩個概率分布p(x) 和q(x) 的相對熵定義為：,(18),信息論基礎(chǔ),40,對熵常被用以衡量兩個隨機分布的差距。當兩個隨機分布相同時，其相對熵為0。當兩個隨機分布的差別增加時，其相對熵也增加。,信息論基礎(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,利用互信息值估計兩個漢字結(jié)合的強度：,互信息值越大，表示兩個漢字之間的結(jié)合越緊密，越可能成詞。反之，斷開的可能性越大。,信息論基礎(chǔ),46,信息論基礎(chǔ),47,信息論基礎(chǔ),48,噪聲信道模型(Noisy Channel Mod

15、el),在信號傳輸?shù)倪^程中都要進行雙重性處理：一方面要通過壓縮消除所有的冗余，另一方面又要通過增加一定的可控冗余以保障輸入信號經(jīng)過噪聲信道后可以很好的恢復原狀。信息編碼時要盡量占用少量的空間，但又必須保持足夠的冗余以便能夠檢測和校驗錯誤。接收到的信號需要被解碼使其盡量恢復到原始的輸入信號。噪聲信道模型的目標就是優(yōu)化噪聲信道中信號傳輸?shù)耐掏铝亢蜏蚀_率，其基本假設(shè)是一個信道的輸出以一定的概率依賴于輸入。,信息論基礎(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,向量的長度,62,⑵ 向量長度的性質(zhì),向量的單位化,63,實驗數(shù)據(jù),64,?訓練集Training Set – 用來獲得模型參數(shù)?測試集Test Set –從訓練集以

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

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