MIT自然语言处理第三讲:概率语言模型
生活随笔
收集整理的這篇文章主要介紹了
MIT自然语言处理第三讲:概率语言模型
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
一、 簡單介紹 a) 預(yù)測字符串概率 i. 那一個(gè)字符串更有可能或者更符合語法 1. Grill doctoral candidates. 2. Grill doctoral updates. (example from Lee 1997) ii. 向字符串賦予概率的方法被稱之為語言模型(Methods for assigning probabilities to strings are called Language Models.) b) 動(dòng)機(jī)(Motivation) i. 語音識別,拼寫檢查,光學(xué)字符識別和其他應(yīng)用領(lǐng)域(Speech recognition, spelling correction, optical character recognition and other applications) ii. 讓E作為物證(?不確定翻譯),我們需要決定字符串W是否是有E編碼而得到的消息(Let E be physical evidence, and we need to determine whether the string W is the message encoded by E) iii. 使用貝葉斯規(guī)則(Use Bayes Rule): P(W/E)={P_{LM}(W)P(E/W)}/{P(E)} 其中P_{LM}(W)是語言模型概率 iv. P_{LM}(W)提供了必要的消歧信息(P_{LM}(W)provides the information necessary for isambiguation (esp. when the physical evidence is not sufficient for disambiguation)) c) 如何計(jì)算(How to Compute it)? i. 樸素方法(Naive approach): 1. 使用最大似然估計(jì)——字符串在語料庫S中存在次數(shù)的值由語料庫規(guī)模歸一化: P_{MLE}(Grill~doctorate~candidates)={count(Grill~doctorate~candidates)}/delim{|}{S}{|} 2. 對于未知事件,最大似然估計(jì)P_{MLE}=0(For unseen events,?P_{MLa Sparseness) d) 兩個(gè)著名的句子(Two Famous Sentences)E}=0) ——數(shù)據(jù)稀疏問題比較“可怕”(Dreadful behavior in the presence of Dat i. “It is fair to assume that neither sentence“Colorless green ideas sleep fu riously” nor “Furiously sleep ideas green colorless” ... has ever occurred ... Hence, in any statistical model ... these sentences will be ruled out on identical grounds as equally “remote” from English. Yet (1), though nonsensical, is grammatical, while (2) is not.” [Chomsky 1957] ii. 注:這是喬姆斯基《句法結(jié)構(gòu)》第9頁上的:下面的兩句話從來沒有在一段英語談話中出現(xiàn)過,從統(tǒng)計(jì)角度看離英語同樣的“遙遠(yuǎn)”,但只有句1是合乎語法的: 1) Colorless green ideas sleep furiously. 2) Furiously sleep ideas sleep green colorless . “從來沒有在一段英語談話中出現(xiàn)過”、“從統(tǒng)計(jì)角度看離英語同樣的‘遙遠(yuǎn)’”要看從哪個(gè)角度去看了,如果拋開具體的詞匯、從形類角度看,恐怕句1的統(tǒng)計(jì)頻率要高于句2而且在英語中出現(xiàn)過。 二、語言模型構(gòu)造 a) 語言模型問題提出(The Language Modeling Problem) i. 始于一些詞匯集合(Start with some vocabulary): ν= {the, a, doctorate, candidate, Professors, grill, cook, ask, ...} ii. 得到一個(gè)與詞匯集合v關(guān)的訓(xùn)練樣本: Grill doctorate candidate. Cook Professors. Ask Professors. …... iii. 假設(shè)(Assumption):訓(xùn)練樣本是由一些隱藏的分布P刻畫的 iv. 目標(biāo)(Goal): 學(xué)習(xí)一個(gè)概率分布P prime盡可能的與P近似 sum{x in v}{}{P prime (x)}=1, P prime (x) >=0 P prime (candidates)=10^{-5} {P prime (ask~candidates)}=10^{-8} b) 獲得語言模型(Deriving Language Model) i. 向一組單詞序列w_{1}w_{2}...w_{n}賦予概率(Assign probability to a sequencew_{1}w_{2}...w_{n}?) ii. 應(yīng)用鏈?zhǔn)椒▌t(Apply chain rule): 1. P(w1w2...wn)= P(w1|S)?P(w2|S,w1)?P(w3|S,w1,w2)...P(E|S,w1,w2,...,wn) 2. 基于“歷史”的模型(History-based model): 我們從過去的事件中預(yù)測未來的事件 3. 我們需要考慮多大范圍的上下文? c) 馬爾科夫假設(shè)(Markov Assumption) i. 對于任意長度的單詞序列P(wi|w(i-n) ...w(i?1))是比較難預(yù)測的 ii. 馬爾科夫假設(shè)(Markov Assumption): 第i個(gè)單詞wi僅依賴于前n個(gè)單詞 iii. 三元語法模型(又稱二階馬爾科夫模型): 1. P(wi|START,w1,w2,...,w(i?1))=P(wi|w(i?1),w(i?2)) 2. P(w1w2...wn)= P(w1|S)?P(w2|S,w1)?P(w3|w1,w2)?...P(E|w(n?1),wn) d) 一種語言計(jì)算模型(A Computational Model of Language) i. 一種有用的概念和練習(xí)裝置:“拋硬幣”模型 1. 由隨機(jī)算法生成句子 ——生成器可以是許多“狀態(tài)”中的一個(gè) ——拋硬幣決定下一個(gè)狀態(tài) ——拋其他硬幣決定哪一個(gè)字母或單詞輸出 ii. 香農(nóng)(Shannon): “The states will correspond to the“residue of influence” from preceding letters” e) 基于單詞的逼近 注:以下是用莎士比亞作品訓(xùn)練后隨機(jī)生成的句子,可參考《自然語言處理綜論》 i. 一元語法逼近(這里MIT課件有誤,不是一階逼近(First-order approximation)) 1. To him swallowed confess hear both. which. OF save 2. on trail for are ay device and rote life have 3. Every enter now severally so, let 4. Hill he late speaks; or! a more to leg less first you 5. enter ii. 三元語法逼近(這里課件有誤,不是三階逼近(Third-order approximation)) 1. King Henry. What! I will go seek the traitor Gloucester. 2. Exeunt some of the watch. A great banquet serv’s in; 3. Will you tell me how I am? 4. It cannot be but so. 三、 語言模型的評估 a) 評估一個(gè)語言模型 i. 我們有n個(gè)測試單詞串: S_{1},S_{2},...,S_{n} ii. 考慮在我們模型之下這段單詞串的概率: prod{i=1}{n}{P(S_{i})} 或?qū)?shù)概率(or log probability): log{prod{i=1}{n}{P(S_{i})}}=sum{i=1}{n}{logP(S_{i})} iii. 困惑度(Perplexity): Perplexity = 2^{-x} 這里x = {1/W}sum{i=1}{n}{logP(S_{i})} W是測試數(shù)據(jù)里總的單詞數(shù)(W is the total number of words in the test data.) iv. 困惑度是一種有效的“分支因子”評測方法(Perplexity is a measure of effective “branching factor”) 1. 我們有一個(gè)規(guī)模為N的詞匯集v,模型預(yù)測(We have a vocabulary v of size N, and model predicts): P(w) = 1/N 對于v中所有的單詞(for all the words in v.) v. 困惑度是什么(What about Perplexity)? Perplexity = 2^{-x} 這里?x = log{1/N} 于是 Perplexity = N vi. 人類行為的評估(estimate of human performance (Shannon, 1951) 1. 香農(nóng)游戲(Shannon game)— 人們在一段文本中猜測下一個(gè)字母(humans guess next letter in text) 2. PP=142(1.3 bits/letter), uncased, open vocabulary vii. 三元語言模型的評估(estimate of trigram language model (Brown et al. 1992)) PP=790(1.75 bits/letter), cased, open vocabulary 四、 平滑算法 a) 最大似然估計(jì)(Maximum Likelihood Estimate) i. MLE使訓(xùn)練數(shù)據(jù)盡可能的“大”: P_{ML}(w_{i}/{w_{i-1},w_{i-2}}) = {Count(w_{i-2},w_{i-1},w_{i})}/{Count(w_{i-2},w_{i-1})} 1. 對于詞匯規(guī)模為N的語料庫,我們將要在模型中得到N^{3}的參數(shù)(For vocabulary of size N, we will have N3 parameters in the model) 2. 對于N=1000,我們將要估計(jì)1000^{3}=10^{9}個(gè)參數(shù)(For N =1, 000, we have to estimate1, 000^{3}=10^{9}?parameters) 3. 問題(Problem): 如何處理未登錄詞? ii. 數(shù)據(jù)稀疏問題(Sparsity) 1. 未知事件的總計(jì)概率構(gòu)成了測試數(shù)據(jù)的很大一部分 2. Brown et al (1992): 考慮一個(gè)3.5億詞的英語語料庫,14%的三元詞是未知的 iii. 注:關(guān)于MLE的簡要補(bǔ)充 1. 最大似然估計(jì)是一種統(tǒng)計(jì)方法,它用來求一個(gè)樣本集的相關(guān)概率密度函數(shù)的參數(shù)。這個(gè)方法最早是遺傳學(xué)家以及統(tǒng)計(jì)學(xué)家羅納德?費(fèi)雪爵士在1912年至1922年間開始使用的。 2. “似然”是對likelihood 的一種較為貼近文言文的翻譯,“似然”用現(xiàn)代的中文來說即“可能性”。故而,若稱之為“最大可能性估計(jì)”則更加通俗易懂。 3.MLE選擇的參數(shù)使訓(xùn)練語料具有最高的概率,它沒有浪費(fèi)任何概率在訓(xùn)練語料中沒有出現(xiàn)的事件中 4.但是MLE概率模型通常不適合做NLP的統(tǒng)計(jì)語言模型,會(huì)出現(xiàn)0概率,這是不允許的。 b) 如何估計(jì)未知元素的概率? i. 打折(Discounting) 1. Laplace 加1平滑(Laplace) 2. Good-Turing 打折法(Good-Turing) ii. 線性插值法(Linear Interpolation) iii. Katz回退(Katz Back-Off) c) 加一(Laplace)平滑 i. 最簡單的打折方法(Simplest discounting technique): {P(w_{i}/w_{i-1})} = {C(w_{i-1},w_{i})+1}/{C(w_{i-1})+V} 這里V是詞匯表的數(shù)目——語料庫的“型” 注:MIT課件這里似乎有誤,我已修改 ii. 貝葉斯估計(jì)假設(shè)事件發(fā)生前是一個(gè)均勻分布 iii. 問題(Problem): 對于未知事件占去的概率太多了 iv. 例子(Example): 假設(shè)V=10000(詞型),S=1000000(詞例)(Assume |ν| =10, 000, and S=1, 000, 000): P_{MLE}(ball/{kike~a}) = {{Count(kike~a~ball)}/{Count(kick~a)}} = 9/10 = 0.9 P_{+1}(ball/{kike~a}) = {{Count(kike~a~ball)+1}/{Count(kick~a)+V}} = {9+1}/{10+10000} = 9*10^{-4} v. Laplace的缺點(diǎn)(Weaknesses of Laplace) 1. 對于稀疏分布,Laplace法則賦予未知事件太多的概率空間 2. 在預(yù)測二元語法的實(shí)際概率時(shí)與其他平滑方法相比顯得非常差( 3. 使用加epsilon平滑更合理一些 五、 Good-Turing打折法(Good-Turing Discounting) a) 你在將來看到一個(gè)新詞的可能性有多大?用所看到的事件去估計(jì)未知事件的概率 i.?n_r——頻率為r的元素(n元語法)計(jì)數(shù)并且r>0 ii.?n_0——總詞匯規(guī)模減去觀察到的詞匯規(guī)模,既出現(xiàn)次數(shù)為0的n元語法 iii. 對于頻率為r的元素,修正計(jì)數(shù)為: r^* = (r+1)*{n_{r+1}/n_r} b) 關(guān)于Good-Turing打折法的補(bǔ)充說明: i. Good(1953)首先描述了Good-Turing算法,而這種算法的原創(chuàng)思想則來自Turing 。 ii. Good-Turing平滑的基本思想是:用觀察較高的N元語法數(shù)的方法來重新估計(jì)概率量的大小,并把它指派給那些具有零計(jì)數(shù)或較低計(jì)數(shù)的N元語法。 c) 直觀的Good-Turing打折法(Good-Turing Discounting: Intuition) i. 目的(Goal): 估計(jì)訓(xùn)練數(shù)據(jù)中計(jì)數(shù)為r的單詞在同樣規(guī)模測試集中的出現(xiàn)頻率(estimate how often word with r counts in training data occurs in test set of equal size)。 ii. 我們使用刪除估計(jì)(We use deleted estimation): 1. 每次刪除一個(gè)單詞(delete one word at a time) 2. 如果單詞“test”在所有的數(shù)據(jù)集中出現(xiàn)了r+1次(if “test” word occurs r +1 times in complete data set): ——它在訓(xùn)練集中出現(xiàn)了r 次(it occurs r times in “training” set) ——對計(jì)數(shù)為r的單詞加1(add one count to words with r counts) iii. r-count單詞“桶”中的總的計(jì)數(shù)為(total count placed to bucket for r-count words is): n_{r+1}*(r +1) iv. 平均計(jì)數(shù)為: (avg-count of r count words) = {n_{r+1}*(r+1)}/n_r? d) Good-Turing打折法續(xù)(Good-Turing Discounting (cont.)): i. 在Good-Turing中,分配給所有未知事件的總的概率等于n_1/N, 其中N是訓(xùn)練集的規(guī)模。它與分配給獨(dú)立事件的相對頻率公式相似。 ii. In Good-Turing, the total probability assigned to all the unobserved events is equal ton_1/N , where N is the size of the training set. It is the same as a relative frequency formula would assign to singleton events. e) 舉例(Example: Good-Turing) Training sample of 22,000,000 (Church&Gale’1991)) r N_r heldout r^* 0 74,671,100,000 0.00027 0.00027 1 2,018,046 0.448 0.446 2 449,721 1.25 1.26 3 188,933 2.24 2.24 4 105,668 3.23 3.24 5 68,379 4.21 4.22 6 48,190 5.23 5.19 f) 補(bǔ)充說明: i. 根據(jù)Zipf定律,對于小的r,?N_r比較大;對于大的r,N_r小,對于出現(xiàn)次數(shù)最多的n元組,r*=0! ii. 所以對于出現(xiàn)次數(shù)很多的n元組, GT估計(jì)不準(zhǔn),而MLE估計(jì)比較準(zhǔn),因此可以直接采用MLE. GT估計(jì)一般適用于出現(xiàn)次數(shù)為k(k<10)的n元組 iii. 如果這樣,考慮”劫富濟(jì)貧”,這里的”富”就變成了”中產(chǎn)”階級!呵呵,真正的富翁沾光了!(雖然富翁損一點(diǎn)也沒什么)連打折法也不敢欺富人!這就是“為富不仁”,“一毛不拔”的來歷。 六、 插值及回退 a) The Bias-Variance Trade-Off i. 未平滑的三元模型估計(jì)(Unsmoothed trigram estimate): P_ML({w_i}/{w_{i-2},w_{i-1}})={Count(w_{i-2}w_{i-1}w_{i})}/{Count(w_{i-2},w_{i-1})} ii. 未平滑的二元模型估計(jì)(Unsmoothed bigram estimate): P_ML({w_i}/{w_{i-1}})={Count(w_{i-1}w_{i})}/{Count(w_{i-1})} iii. 未平滑的一元模型估計(jì)(Unsmoothed unigram estimate): P_ML({w_i})={Count(w_{i})}/sum{j}{}{Count(w_{j})} iv. 這些不同的估計(jì)中哪個(gè)和“真實(shí)”的P({w_i}/{w_{i-2},w_{i-1}})概率最接近(How close are these different estimates to the “true” probability?P({w_i}/{w_{i-2},w_{i-1}}))? b) 插值(Interpolation) i. 一種解決三元模型數(shù)據(jù)稀疏問題的方法是在模型中混合使用受數(shù)據(jù)稀疏影響較小的二元模型和一元模型(One way of solving the sparseness in a trigram model is to mix that model with bigram and unigram models that suffer less from data sparseness)。 ii. 權(quán)值可以使用期望最大化算法(EM)或其它數(shù)值優(yōu)化技術(shù)設(shè)置(The weights can be set using the Expectation-Maximization Algorithm or another numerical optimization technique) iii. 線性插值(Linear Interpolation) hat{P}({w_i}/{w_{i-2},w_{i-1}})={lambda_1}*P_ML({w_i}/{w_{i-2},w_{i-1}}) +{lambda_2}*P_ML({w_i}/w_{i-1})+{lambda_3}*P_ML({w_i}) 這里{lambda_1}+{lambda_2}+{lambda_3}=1并且{lambda_i}>=0?對于所有的 i iv. 參數(shù)估計(jì)(Parameter Estimation) 1. 取出訓(xùn)練集的一部分作為“驗(yàn)證”數(shù)據(jù)(Hold out part of training set as “validation” data) 2. 定義Count_2(w_1,w_2,w_3)作為驗(yàn)證集中三元集?w_1,w_2,w_3?的出現(xiàn)次數(shù)(DefineCount_2(w_1,w_2,w_3)?to be the number of times the trigram?w_1,w_2,w_3?is seen in validation set) 3. 選擇{lambda_i}去最大化(Choose?{lambda_i}?to maximize): L({lambda_1},{lambda_2},{lambda_3})=sum{(w_1,w_2,w_3)in{upsilon}}{}{Count_2(w_1,w_2,w_3)}log{hat{P}}({w_3}/{w_2,w_1}) 這里{lambda_1}+{lambda_2}+{lambda_3}=1并且{lambda_i}>=0?對于所有的 i 注:關(guān)于參數(shù)估計(jì)的其他內(nèi)容,由于公式太多,這里略,請參考原始課件 c)Kats回退模型-兩元(Katz Back-Off Models (Bigrams)): i. 定義兩個(gè)集合(Define two sets): A(w_{i-1})=delim{lbrace}{w:Count(w_{i-1},w)>0}{rbrace} B(w_{i-1})=delim{lbrace}{w:Count(w_{i-1},w)=0}{rbrace} ii. 一種兩元模型(A bigram model): P_K({w_i}/w_{i-1})=delim{lbrace}{matrix{2}{2}{{{Count^{*}(w_{i-1},w)}/{Count(w_{i-1})}>0} {if{w_i}{in}{A(w_{i-1})}} {alpha(w_{i-1}){{P_ML(w_{i})}/sum{w{in}B(w_{i-1})}{}{P_ML(w)}} } {if{w_i}{in}{B(w_{i-1})}} }}{} {alpha(w_{i-1})=1-sum{w{in}A(w_{i-1})}{}{{Count^{*}(w_{i-1},w)}/{Count(w_{i-1})}}} iii. Count^*定義(Count^*definitions) 1. Kats對于Count(x)<5使用Good-Turing方法,對于Count(x)>=5令Count^*(x)=Count(x)(Katz uses Good-Turing method for Count(x)< 5, and?Count^*(x)=Count(x)for Count(x)>=5) 2. “Kneser-Ney”方法(“Kneser-Ney” method): Count^*(x)=Count(x)-D,其中?D={n_1}/{n_1+n_2} n_1是頻率為1的元素個(gè)數(shù)(n_1?is a number of elements with frequency 1) n_2是頻率為2的元素個(gè)數(shù)(n_2?is a number of elements with frequency 2) 七、 綜述 a) N元模型的弱點(diǎn)(Weaknesses of n-gram Models) i. 有何想法(Any ideas)? 短距離(Short-range) 中距離(Mid-range) 長距離(Long-range) b) 更精確的模型(More Refined Models) i. 基于類的模型(Class-based models) ii. 結(jié)構(gòu)化模型(Structural models) iii. 主題和長距離模型(Topical and long-range models) c) 總結(jié)(Summary) i. 從一個(gè)詞表開始(Start with a vocabulary) ii. 選擇一種模型(Select type of model) iii. 參數(shù)估計(jì)(Estimate Parameters) d) 工具包參考: i. CMU-Cambridge language modeling toolkit: http://mi.eng.cam.ac.uk/~prc14/toolkit.html ii.SRILM - The SRI Language Modeling Toolkit: http://www.speech.sri.com/projects/srilm/
轉(zhuǎn)載于:https://www.cnblogs.com/sccdcwc/p/6445143.html
《新程序員》:云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作,文字、視頻、音頻交互閱讀總結(jié)
以上是生活随笔為你收集整理的MIT自然语言处理第三讲:概率语言模型的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。

- 上一篇: 201521123029《Java程序设
- 下一篇: 浅谈XML