搜索引擎開發(fā)實踐

第二十一講N元分詞方法主講人：羅剛

產(chǎn)品和服務(wù)概述N元分詞原理二元搭配詞典平滑算法作業(yè)講解：地名切分地址串全切分動態(tài)規(guī)劃求解概率最大的詞序列香農(nóng)游戲(ShannonGame)根據(jù)前面的(n-1)個詞預(yù)測下一個單詞可能是什么?“NBA______”

比賽？

球星？籃球？秀選？“直播NBA______”決賽？季后賽？轉(zhuǎn)移概率P(比賽|NBA)選擇n值詞匯量(V)=20,000n可能的組合數(shù)量2(bigrams)400,000,0003(trigrams)8,000,000,000,0004(4-grams)1.6x1017選擇n值可靠性(Reliability)和可區(qū)別性(Discrimination)成反比，需要折中 n越大，區(qū)別力越大；n越小，可靠性越高N取多大？ 理論上講，越大越好 經(jīng)驗值：二元或三元(trigram)二元模型如果簡化成一個詞的出現(xiàn)僅依賴于它前面出現(xiàn)的一個詞，那么就稱為二元模型(bigram)。即：P(S)=P(w1,w2,...,wn)=P(w1)P(w2|w1)P(w3|w1,w2)…P(wn|w1w2,...,wn-1)≈P(w1)P(w2|w1)P(w3|w2)…P(wn|wn-1)基本的計算方法：P(wi|wi-1)≈freq(wi-1,wi)/freq(wi-1)二元搭配詞典Freq(有,意見)=4P(意見|有)≈freq(wi-1,wi)/freq(有)=4/4000=0.001因為數(shù)據(jù)稀疏導(dǎo)致“意見,分歧”等其他的搭配都沒找到。P(S1)和P(S2)都將是0，無法通過比較計算結(jié)果找到更好的切分方案。這就是零概率問題。查找二元詞典可以采用Trie樹的形式來存放N元模型的參數(shù)。與詞典Trie樹的區(qū)別在于：詞典Trie樹上每個結(jié)點對應(yīng)一個漢字，而N元模型Trie樹的一個結(jié)點對應(yīng)一個詞。或者可以把搭配信息存放在詞典Trie樹的葉子節(jié)點上。每個詞有一個編號wId。publicclassBigramMap{publicint[]keys;//詞編號

publicint[]vals;//頻率}查找二元詞典大中學(xué)活心生心動生活wId:8wId->頻率5->3wId:5以存儲“大學(xué)生,生活”為例，“生活”的詞編號是8，大學(xué)生的詞編號是5。假設(shè)“大學(xué)生,生活”頻率是3在Trie樹上增加二元信息避免零概率：數(shù)據(jù)平滑(smoothing)p’(w)≈p(w),但p’(w)≠0對一些p(w)>0,生成p’(w)<p(w)分配概率D給所有概率為0的項目w:p’(w)>p(w)=0可能對于概率值較低的詞也作調(diào)整可能有些w:p’(w)=p(w)需要確保有許多數(shù)據(jù)平滑的方法加1平滑加Lambda平滑Witten-Bell平滑Good-Turing平滑加一平滑第13頁加一平滑xya11/322/29xyb00/311/29xyc00/311/29xyd22/333/29xye00/311/29…xyz00/311/29xy總數(shù)33/32929/2926個字母，每個都加1加一平滑xya100100/300101101/326xyb00/30011/326xyc00/30011/326xyd200200/300201201/326xye00/30011/326…xyz00/30011/326xy總數(shù)300300/300326326/326300個觀測事件，而不是3個，有了更好的數(shù)據(jù)后，平滑更少了加一平滑seetheabacus11/322/20003seetheabbot00/311/20003seetheabduct00/311/20003seetheabove22/333/20003seetheAbram00/311/20003…seethezygote00/311/20003Total33/32000320003/20003假設(shè)有20000個單詞類型，而不是26個字母“新事件”=零次事件(不會在訓(xùn)練集中出現(xiàn))。這里:19998個新事件，全部估計概率是19998/20003.因此加一平滑認為特別可能看到新事件，而不是在訓(xùn)練集已經(jīng)看到的單詞。僅僅因為有一個大詞典就如此認為：引入了20000個可能的事件。“想的太多，違背直覺而出錯了”？加Lambda平滑大的詞典使得新事件變得太有可能了。解決方法：不是加1到所有的頻率上，而是加

=0.01?這樣又可能給太小的可能性到新事件如何選擇最好的?也就是說，要平滑多少?例如，分出多少概率給新事件?依賴于新事件有多大可能出現(xiàn)可能依賴于文本的類型，訓(xùn)練語料集的大小…從數(shù)據(jù)中判斷要平滑多少。18術(shù)語:類型與

表征詞

類型(type)=不同的詞匯項詞

表征(token)=該類型在語料庫中的出現(xiàn)詞典是一個類型的列表(詞典中的每一項就是一個類型)語料庫是一個表征的列表(每個類型有許多表征)a100b0c0d200e0…z0Total30026個類型300個表征該類型的100個表征該類型的200個表征該類型的0個表征600.465-IntrotoNLP-J.Eisner19新事件有多大可能?a1500both180candy01donuts02every50與0farina00grapes01his380icecream07…20000類型300表征300表征0/3000/300哪個零是真的罕見?有任何理論上的好方法來選擇λ?600.465-IntrotoNLP-J.Eisner20新事件有多大可能?a1500both180candy01donuts02every50與0farina00grapes01his380icecream07…20000類型300表征300表征限定詞:封閉的類600.465-IntrotoNLP-J.Eisner21新事件有多大可能?a1500both180candy01donuts02every50與0farina00grapes01his380icecream07…20000類型300表征300表征(食品)名詞:開放的類新事件有多常見?N0*N1*N2*N3*N4*N5*N6*從語料庫中的計數(shù)(N1百萬表征)novelwords(在詞典中但是不出現(xiàn))singletons(出現(xiàn)1次)doubletons(出現(xiàn)2次)N2

=#doubletontypesN2*2=#doubletontokensrNr

=全部#type=T(紫色欄)r(Nr*r)=全部#token=N(全部欄)出現(xiàn)次數(shù)新事件有多常見?N0*N1*N2*N3*N4*N5*N6*1

*1

*abaringe,Babatinde,cabaret…aback,Babbitt,cabanas…Abbas,babel,Cabot…abdominal,Bach,cabana…aberrant,backlog,cabinets…abdomen,bachelor,Caesar…theEOSWitten-Bell平滑思想N0*N1*N2*N3*N4*N5*N6*新詞singletonsdoubletons如果T/N值大，說明過去已經(jīng)看到了很多新類型

，將來也會期望看到很多新類型想象按順序掃描語料庫每個類型的第一個表征是新的看見了T新類型(紫色)不平滑

平滑2/N2/(N+T)1/N1/(N+T)0/N(T/(N+T))/N0理解:當(dāng)看見訓(xùn)練集中的一個新的類型w時，++count(w);++count(新事件)

因此p(新事件)估計是T/(N+T)，然后除以指定的新類型數(shù)N0出現(xiàn)次數(shù)Good-Turing平滑思想N0*N1*N2*N3*N4*N5*N6*根據(jù)詞在訓(xùn)練數(shù)據(jù)中出現(xiàn)了多少次，把類別詞匯分成大類

(新事件,singleton,doubleton,…)

使用觀察到的類別r+1的全部概率

去估計類別r的全部概率不平滑

平滑(N3*3/N)/N2(N2*2/N)/N1(N1*1/N)/N0r/N=(Nr*r/N)/Nr(Nr+1*(r+1)/N)/Nr觀察.p(singleton)估計.p(novel)2%觀察.p(doubleton)估計.p(singleton)1.5%觀察.p(tripleton)估計.p(doubleton)1.2%2/N(N3*3/N)/N21/N(N2*2/N)/N10/N(N1*1/N)/N0出現(xiàn)概率通過留一個訓(xùn)練證明!藍色部分是訓(xùn)練集。黃色部分是留出來的一個表征。藍色部分加黃色部分做測試集。輪流拿出N個表征中的一個，訓(xùn)練集大小是N-1，拿出來的集合大小是1不是僅僅調(diào)整，可以調(diào)整多個值p(novel)=0.02=N1/N[=黃色部分拿出來的一個開發(fā)詞在藍色訓(xùn)練集里是新事件]p(singleton)=0.015=N2*2/N[=黃色部分拿出來的一個開發(fā)詞在藍色訓(xùn)練集里是singleton]p(doubleton)=0.012=N3*3/N[=黃色部分拿出來的一個開發(fā)詞在藍色訓(xùn)練集里是doubleton]

也就是p(novel)=在全部訓(xùn)練集里的singleton部分p(singleton)=在全部訓(xùn)練集里的doubleton部分，依次類推證明Good-Turing…觀察.p(singleton)估計.p(novel)2%觀察.p(doubleton)估計.p(singleton)1.5%觀察.p(tripleton)估計.p(doubleton)1.2%13245N-1N實驗次數(shù)27Witten-Bell平滑Witten-Bell構(gòu)想：如果已經(jīng)看到許多不同的事件，則新事件也是有可能的。(考慮類型/表征比率)Good-Turing構(gòu)想：如果已經(jīng)看到許多singleton，則新事件也是有可能的。28Good-Turing平滑構(gòu)想：可以通過singleton的比率判斷新事件的比率假設(shè)Nr=出現(xiàn)r次的詞類型數(shù)量例如，N0=沒看到的單詞數(shù)例如，N1=只出現(xiàn)1次的單詞數(shù)假設(shè)N=rNr=總的詞數(shù)樸素的估計：如果x有r個表征，則p(x)=?答案:r/N全部的樸素概率全部的有r個表征的詞類型?答案:Nrr/N這個全部概率的Good-Turing估計：定義成:Nr+1(r+1)/Np(x)的Good-Turing估計是多少?答案:(Nr+1(r+1)/N)/Nr

Good-Turing平滑主要思想：利用高頻n-gram的頻率調(diào)整低頻n-gram的頻率。估計次數(shù)r*：

問題：有1個n-gram出現(xiàn)了r=1000次，有0個n-gram出現(xiàn)了1001次，那么，解決方法：可以把概率最大的詞保持原概率不變，但仍然參與歸一化處理出現(xiàn)了r+1次的n-gram個數(shù)出現(xiàn)了r次的n-gram個數(shù)GoodTuring平滑的例子想象正在釣魚已經(jīng)釣到了10條鯉魚，3條鱈魚，2條金槍魚，1條鱒魚，1條三文魚，1條鰻魚。多大可能下一條是新的一種魚?3/18多大可能下一條是金槍魚?小于2/18簡單線性插值(SimpleLinearInterpolation)這里λ1

+λ2

+λ3

=1，而且對所有的i來說，λi≥0線性插值這個估計定義了分布：估計條件概率使用GoodTuring估計條件概率例如，估計三元連接條件概率：根據(jù)平滑公式計算舉例P(S1)=P(有)*P’(意見|有)*P’(分歧|意見) =P(有)*(0.3P(意見)+0.7P(意見|有))*(0.3P(分歧)+0.7P(分歧|意見)) =0.0180*(0.3*0.001+0.7*0.001)*(0.3*0.0001) =5.4*10-9P(S2)=P(有意)*P’(見)*P’(分歧) =P(有意)*(0.3P(見)+0.7P(見|有意))*(0.3P(分歧)+0.7P(分歧|見)) =0.0005*(0.3*0.0002)*(0.3*0.0001) =9*10-13P(S1)>P(S2)動態(tài)規(guī)劃求解二元模型到Nodei為止的最大概率稱為Nodei的概率。如果Wj的結(jié)束節(jié)點是Nodei，就稱Wj為Nodei的前驅(qū)詞這里的prev2(Nodei)就是節(jié)點i的二級前驅(qū)詞序列，記做Wj,Wk。比如上面的例子中，“意見”和“見”都是節(jié)點3的1級前驅(qū)詞，候選詞“有”就是節(jié)點3的2級前驅(qū)詞。StartNode(wj)是wj的開始節(jié)點，也是節(jié)點i的2級前驅(qū)節(jié)點。因此切分的最大概率max(P(S))就是P(Nodem)也就是P(節(jié)點m的最佳2級前驅(qū)節(jié)點)*P(節(jié)點m的2級最佳前驅(qū)詞序列)求解二元模型實現(xiàn)//計算節(jié)點i的最佳前驅(qū)節(jié)點voidgetBestPrev(AdjListg,inti){ Iterator<CnToken>it1=g.getPrev(i);//得到一級前驅(qū)詞集合

doublemaxProb=Double.NEGATIVE_INFINITY; intmaxPrev1=-1; intmaxPrev2=-1;

while(it1.hasNext())