北郵郭軍web搜索chapter5

1、Web 搜索搜索郭軍郭軍北京郵電大學(xué) 第第5 5章章 信息過(guò)濾信息過(guò)濾n基本方法基本方法n模型學(xué)習(xí)模型學(xué)習(xí)n垃圾郵件及垃圾短信過(guò)濾垃圾郵件及垃圾短信過(guò)濾n話(huà)題檢測(cè)與追蹤系統(tǒng)話(huà)題檢測(cè)與追蹤系統(tǒng)引言引言n信息過(guò)濾的本質(zhì)是“流環(huán)境”下的二元分類(lèi)u流環(huán)境：過(guò)濾系統(tǒng)處于信息持續(xù)新生的環(huán)境之中，新的數(shù)據(jù)源源不斷地流經(jīng)過(guò)濾系統(tǒng)u二元分類(lèi)：一類(lèi)是需要篩選出來(lái)的，一類(lèi)是系統(tǒng)不關(guān)心的 n以模式分類(lèi)模式分類(lèi)為技術(shù)核心，高效高精度地處理數(shù)據(jù)流IR被檢索的文檔相對(duì)穩(wěn)定 用戶(hù)查詢(xún)需求不同 IF信息資源動(dòng)態(tài)變化 用戶(hù)需求相對(duì)固定IF的研究重點(diǎn)n分類(lèi)器的選擇u針對(duì)特定的應(yīng)用環(huán)境選擇分類(lèi)器模型u目前研究較多的是樸素Bayes模

2、型、向量相似度(模板匹配)模型、SVM、k-NN等n分類(lèi)器的學(xué)習(xí)及優(yōu)化u生成式算法、區(qū)分式算法u計(jì)算效率，類(lèi)別模型的增量學(xué)習(xí)和自動(dòng)演進(jìn)，半監(jiān)督學(xué)習(xí)、特征降維技術(shù)基本方法基本方法n信息過(guò)濾系統(tǒng)中常用的分類(lèi)器uBayes分類(lèi)器u向量距離分類(lèi)器uk近鄰分類(lèi)器uSVMn系統(tǒng)性能評(píng)價(jià)Bayes分類(lèi)器分類(lèi)器nBayes分類(lèi)器將分類(lèi)問(wèn)題看作統(tǒng)計(jì)決策問(wèn)題，以最小錯(cuò)誤率為目標(biāo)進(jìn)行分類(lèi)u前提：事先獲得各個(gè)類(lèi)別的似然函數(shù)，決策時(shí)利用Bayes公式計(jì)算給定樣本特征值條件下各類(lèi)別的后驗(yàn)概率n設(shè)隨機(jī)變量xRd, 各類(lèi)別的似然函數(shù)為P(x|ci)，對(duì)于某確定樣本t, 根據(jù)Bayes公式：( ) ()()( )iiiP c

3、PcP cPttt分類(lèi)方法n計(jì)算得到各個(gè)P(ci|t)后，將樣本t分到類(lèi)別ck中，其中1argmax()jj mkP c t舉例：隨機(jī)選取100封郵件，進(jìn)行人工標(biāo)注，其中有30封垃圾郵件和70封非垃圾郵件，對(duì)于詞“培訓(xùn)”，垃圾郵件中有21封含有該詞，非垃圾郵件中有28封含有該詞，假定過(guò)濾系統(tǒng)只采用該詞判別是否為垃圾郵件，問(wèn)若一封新郵件含有該詞，則過(guò)濾系統(tǒng)認(rèn)為該郵件是否是垃圾郵件？對(duì)于多個(gè)詞，如何判別？似然比Rln二元分類(lèi)問(wèn)題可以根據(jù)似然比Rl來(lái)決定t的歸屬 對(duì)數(shù)似然比：假設(shè)x的各維數(shù)據(jù)之間相互獨(dú)立； 樸素Bayes分類(lèi)器 111222(| )( ) ( |)(| )() ( |)lP cP c

4、 PcRP cP c Pctttt111221( )(|)()(|)djjldjjP cP tcRP cP tc121211lnln( )ln()ln (|)ln (|)ddljjjjRP cP cP tcP tc向量距離分類(lèi)器向量距離分類(lèi)器n向量距離分類(lèi)器可以看作是Bayes分類(lèi)器的簡(jiǎn)化，它用各類(lèi)別數(shù)據(jù)的均值向量、方差向量、協(xié)方差矩陣等參數(shù)近似描述它們的分布特性，利用向量之間的各種距離進(jìn)行分類(lèi)，常用的距離尺度有:21()dgjijjDt1|dcjijjDt1()()TmiiiDtt221() /dsjijijjDtk近鄰分類(lèi)器近鄰分類(lèi)器n也稱(chēng)k-NN分類(lèi)器(k-Nearest Neighbo

5、r)n最大特點(diǎn)是不需要訓(xùn)練類(lèi)別模型，而是按某種合理的比例從各類(lèi)別中抽取樣本，用所有抽出的樣本構(gòu)成分類(lèi)器的總體特征樣本n對(duì)于一個(gè)給定的樣本t，首先按照某種距離測(cè)度找出與其最接近的k個(gè)樣本，然后根據(jù)這k個(gè)樣本所屬類(lèi)別進(jìn)行投票SVMnSVM是一種以結(jié)構(gòu)風(fēng)險(xiǎn)最小化為目標(biāo)的二元分類(lèi)器，在尋找最優(yōu)分類(lèi)超平面時(shí)不但要求將兩類(lèi)數(shù)據(jù)隔離，而且要求兩類(lèi)數(shù)據(jù)距超平面的平均距離最大n設(shè)線(xiàn)性可分?jǐn)?shù)據(jù)集為nD維空間中線(xiàn)性判別函數(shù)的一般形式為n分類(lèi)超平面方程為1(,)niiiyDxdRx1, 1y ( )gbxw x0bw x系統(tǒng)性能評(píng)價(jià)系統(tǒng)性能評(píng)價(jià)n評(píng)價(jià)指標(biāo)主要包括分類(lèi)器的精度和速度u速度取決于分類(lèi)器算法的復(fù)雜程度，在實(shí)

6、際應(yīng)用中與計(jì)算機(jī)的硬件性能關(guān)系很大u精度通過(guò)與人工標(biāo)注結(jié)果(ground truth)進(jìn)行比較來(lái)計(jì)算n對(duì)于二元分類(lèi)問(wèn)題，常用的精度指標(biāo)有u準(zhǔn)確率u召回率uF-measureubreak-even點(diǎn) 精度指標(biāo)標(biāo)注標(biāo)注為為L(zhǎng)類(lèi)類(lèi)標(biāo)注為標(biāo)注為非非L類(lèi)類(lèi)判別為判別為L(zhǎng)類(lèi)類(lèi)ab判別為非判別為非L類(lèi)類(lèi)cd分類(lèi)與標(biāo)注對(duì)應(yīng)關(guān)系的頻次分類(lèi)與標(biāo)注對(duì)應(yīng)關(guān)系的頻次 aPabaRaci) 準(zhǔn)確率準(zhǔn)確率(Precision)表示所有被分類(lèi)器分到類(lèi)L的數(shù)據(jù)中正確的所占的比例ii) 召回率召回率(Recall)表示所有實(shí)際屬于L的數(shù)據(jù)被分類(lèi)器分到L中的比例iii) 平衡點(diǎn)平衡點(diǎn)BEP(Break-even Point): P

7、和R值是互相影響的: P會(huì)隨著R的升高而降低，反之亦然。因此，為了更全面地反映分類(lèi)器的性能，一種做法是選取P和R相等時(shí)的值來(lái)表征系統(tǒng)性能，這個(gè)值叫BEPiv) F值值一種把準(zhǔn)確率和召回率綜合考慮的評(píng)價(jià)方法，定義如下：22(1) P RFPR12 P RFPR模型學(xué)習(xí)模型學(xué)習(xí)n生成式學(xué)習(xí)u典型應(yīng)用：利用EM算法對(duì)GMM的參數(shù)進(jìn)行估計(jì)u共同特征：每個(gè)類(lèi)模型只用本類(lèi)的樣本進(jìn)行估計(jì)，估計(jì)的準(zhǔn)則是使模型產(chǎn)生訓(xùn)練樣本的可能性最大(最大似然)u早期的模型學(xué)習(xí)主要采用生成式算法n區(qū)分式學(xué)習(xí)u典型應(yīng)用: SVM的學(xué)習(xí)u共同特征: 由需要相互區(qū)分的各類(lèi)樣本共同構(gòu)成一個(gè)模型，通過(guò)多類(lèi)樣本的“角力”形成不偏不依的分類(lèi)

8、面降維變換降維變換n需要進(jìn)行學(xué)習(xí)的降維變換是指變換核（基函數(shù)）隨被處理數(shù)據(jù)集變化以獲得最佳變換效果的變換(自適應(yīng)變換)u主成分分析PCA(Principal Component Analysis)u獨(dú)立成分分析ICA(Independent Component Analysis)u線(xiàn)性鑒別分析LDA(Linear Discriminative Analysis)u希爾伯特黃變換Hilbert-Huangu自適應(yīng)變換也存在生成式和區(qū)分式之分PCA dRxN1iixX11NxiiNx 11)NtxixixiN (x)(x 設(shè)隨機(jī)變量，存在一個(gè)樣本集，則其均值可估計(jì)如下：協(xié)方差矩陣可估計(jì)如下：xii

9、a1 ,.,dAaa()xtAyx 求解按降序排列的d個(gè)特征值和對(duì)應(yīng)的特征向量，并構(gòu)成矩陣稱(chēng)為x的PCA變換(也稱(chēng)K-L變換)，則式PCA的性質(zhì)的性質(zhì)yx tAAxyx1yd PCA變換后的變量y是零均值的隨機(jī)變量，其協(xié)方差矩陣為：由于A是列為的特征向量的正交矩陣，所以是對(duì)角陣且對(duì)角線(xiàn)元素為的特征值，即：由于y的非對(duì)角元素都是零，所以隨機(jī)變量y的各維之間是不相關(guān)的LDA nLDA的思想是找一個(gè)投影方向，使得投影后在低維空間里樣本的類(lèi)間散度較大，類(lèi)內(nèi)散度較小 x1x2xLDA的定義的定義(1/3)1cwiiSS()()itiiCSixxmxmdRx1()()ctbiiiinSmm mmm設(shè)Ci為

10、第i類(lèi)樣本的集合，共有c類(lèi)樣本，則樣本類(lèi)內(nèi)散度矩陣定義為：其中，mi為第i類(lèi)樣本的均值，樣本類(lèi)間散度矩陣定義為：其中為樣本集的總體均值向量LDA的定義的定義(2/3)t Wyx:將d維的隨機(jī)變量x變換到c-1維11()() ()()ySSiccttwiibiiiiCinymymmm mm SW S WSW S Wttwwbb定義在變換空間中樣本的類(lèi)內(nèi)和類(lèi)間散度矩陣：容易證明LDA的定義的定義(3/3)定義如下的準(zhǔn)則函數(shù)：()argmaxargmaxTbbTwwJoptWWSW S WWW S WS(1,2,)biiwiic 1S wS w， -1wbS S1S S WWwb 121 ,cdia

11、g 容易證明，使J(.)最大化的變換矩陣W的列向量由下列等式中的最大特征值對(duì)應(yīng)的特征向量組成：這是一個(gè)廣義特征值問(wèn)題，如果Sw是非奇異的，W的列向量就是由矩陣的特征向量組成其中LDA的奇異性的奇異性nLDA是信息過(guò)濾中數(shù)據(jù)降維的核心算法之一n在應(yīng)用中常遇到類(lèi)內(nèi)分散度矩陣Sw奇異的問(wèn)題u當(dāng)數(shù)據(jù)維數(shù)很高時(shí)，能夠獲得的樣本數(shù)常常相對(duì)不足，使得獨(dú)立的訓(xùn)練樣本數(shù)N小于數(shù)據(jù)維數(shù)d，而這將導(dǎo)致Sw為奇異矩陣u信息過(guò)濾所處理的文本、圖像、音頻等一般都是在高維數(shù)據(jù)空間中表達(dá)的u解決LDA奇異性問(wèn)題時(shí)，常先用某種生成式算法對(duì)數(shù)據(jù)進(jìn)行降維LDA奇異性的解決奇異性的解決n 主要方法: u正則化正則化LDAuPCA+L

12、DAuPCA+NULL空間空間uLDA/QRuLDA/GSVD 正則化正則化LDA（RLDA）n一種簡(jiǎn)單的解決Sw矩陣奇異的方法是利用正則化思想在Sw上加一個(gè)擾動(dòng)量，數(shù)學(xué)表達(dá)為其中 0，I為一個(gè)單位矩陣 這種方法的主要問(wèn)題在于擾動(dòng)量的選取有難度。如果擾動(dòng)量太小可能不足以解決奇異問(wèn)題，太大又會(huì)使Sw內(nèi)包含的判決信息丟失wwSSIPCA+LDAn首先用PCA對(duì)數(shù)據(jù)降維，使Sw成為非奇異矩陣，然后再進(jìn)行LDAn將生成式變換與區(qū)分式變換結(jié)合nPCA變換使數(shù)據(jù)中的信息被 “忠實(shí)地”保留，同時(shí)數(shù)據(jù)維數(shù)得到了壓縮，以便消除使Sw奇異的條件n難點(diǎn)：沒(méi)有明確的理論指導(dǎo)PCA降維的維數(shù)選擇u如果PCA維數(shù)太低，會(huì)

13、丟失過(guò)多的鑒別信息u如果維數(shù)太高，相對(duì)來(lái)說(shuō)訓(xùn)練樣本會(huì)仍顯不足，這樣即使能解決Sw的奇異問(wèn)題，也難免會(huì)出現(xiàn)過(guò)擬合的現(xiàn)象LDA/QRn對(duì)Hb進(jìn)行QR分解，得到一個(gè)正交矩陣Q和一個(gè)上三角矩陣R，然后在Q張成的低維子空間內(nèi)進(jìn)行鑒別分析n算法分兩步完成：bd rRQbrcRR, TTbbwwSQ S QSQ S Q, bwSS第一步，對(duì)Hb進(jìn)行QR分解，Hb = QR的正交列張成了Hb的秩空間是上三角矩陣第二步，在上運(yùn)用LDA然后定義:LDA/GSVD n通過(guò)廣義奇異值分解GSVD，用Hb和Hw代替Sb和Swn根據(jù)GSVD理論，正交矩陣YRc*c，ZRn*n，以及非奇異矩陣XRd*d滿(mǎn)足如下關(guān)系：因此有

14、, , TTbbTTwwY H X 0Z H X0IIDDOObwbwbwbw1(,)twbbrrrdiagD1(,)twbwrrrdiagD221iiTTbbww IX的列向量就是矩陣對(duì)Hb,Hw對(duì)應(yīng)的廣義奇異向量，并將其作為基于GSVD的鑒別特征子空間RDMnRDM的特點(diǎn)主要有兩方面u1）將LDA問(wèn)題轉(zhuǎn)化為同時(shí)對(duì)角化類(lèi)內(nèi)和類(lèi)間散度矩陣問(wèn)題u2）通過(guò)能量適應(yīng)準(zhǔn)則來(lái)近似估計(jì) 12, ,Twndiag SI0對(duì)類(lèi)內(nèi)散度矩陣Sw進(jìn)行對(duì)角化，得：在對(duì)角矩陣上加上一個(gè)小的擾動(dòng)量進(jìn)行正則化，即（）的選擇11*,()min( )miimnmiiJ mmE其中RDM將Sw的能量譜用作選擇的標(biāo)準(zhǔn)J(m)通過(guò)前

15、m個(gè)特征值在總能量譜中所占的比例來(lái)確定m的值半監(jiān)督學(xué)習(xí)半監(jiān)督學(xué)習(xí)n問(wèn)題：樣本不足 / 標(biāo)注樣本不足u找到有效的方法，使得只需手工標(biāo)注少數(shù)數(shù)據(jù)，就能較準(zhǔn)確地對(duì)全部數(shù)據(jù)進(jìn)行自動(dòng)標(biāo)注n三類(lèi)算法u在聚類(lèi)過(guò)程中利用已標(biāo)注的數(shù)據(jù)來(lái)引導(dǎo)聚類(lèi)u在對(duì)標(biāo)注樣本進(jìn)行學(xué)習(xí)之后，首先處理那些有較高置信度的未標(biāo)注樣本，然后迭代地把這些估計(jì)加入到標(biāo)注樣本集中u將數(shù)據(jù)看作圖上的結(jié)點(diǎn)，將數(shù)據(jù)間的(已知的)相似性看作結(jié)點(diǎn)間的初始邊長(zhǎng)(權(quán)重)，應(yīng)用圖的理論對(duì)數(shù)據(jù)進(jìn)行聚類(lèi)半監(jiān)督學(xué)習(xí)的形式定義半監(jiān)督學(xué)習(xí)的形式定義1,lxx1 CiRy1,ll uxx標(biāo)注樣本集合L =標(biāo)注樣本的類(lèi)別向量用yij = 1 and yiq = 0 (qj)

16、表示xi點(diǎn)屬于第j類(lèi)，C為類(lèi)別數(shù)用fi表示，fi是元素值為0或1的C維向量用Y表示已標(biāo)注樣本集的真實(shí)類(lèi)別矩陣用F表示數(shù)據(jù)集的類(lèi)別指示矩陣，其類(lèi)別指示向量設(shè)未標(biāo)注樣本集合U = 半監(jiān)督學(xué)習(xí):在已知數(shù)據(jù)集L、U和Y的情況下估計(jì)F基于圖的算法基于圖的算法n在圖中估計(jì)樣本的類(lèi)別函數(shù)f，使其滿(mǎn)足兩個(gè)條件：u1) 對(duì)于已標(biāo)注樣本，其真實(shí)類(lèi)別和通過(guò)f得到的結(jié)果越接近越好u2) 對(duì)于整個(gè)樣本集，f 足夠平滑n這兩個(gè)條件可以通過(guò)正則化方法得到滿(mǎn)足，即在求解的過(guò)程中用先驗(yàn)知識(shí)對(duì)求解過(guò)程加以約束，從而獲得有意義的解n類(lèi)別估計(jì)函數(shù) f 一般由兩項(xiàng)組成，一項(xiàng)是損失函數(shù)，用來(lái)評(píng)價(jià)條件1的滿(mǎn)足度；另一項(xiàng)是正則化，保證條件2

17、得到滿(mǎn)足基于隨機(jī)場(chǎng)的半監(jiān)督學(xué)習(xí)基于隨機(jī)場(chǎng)的半監(jiān)督學(xué)習(xí) n首先在圖上定義一個(gè)連續(xù)的隨機(jī)場(chǎng)，然后根據(jù)能量函數(shù)最小化時(shí)調(diào)和函數(shù)的特性獲得聚類(lèi)結(jié)果 2,1( ) ( )( )2iji jEwijfff()1( )EpeZffexp( )llZEdffYf基于相似點(diǎn)應(yīng)屬于相同類(lèi)別，得到二次能量函數(shù)：式中W=wij是圖的權(quán)值矩陣，代表結(jié)點(diǎn)間的相似性通過(guò)已標(biāo)注數(shù)據(jù)，可以獲得部分f(i)的取值即，如果xiL ，則f(i)由yi確定另，利用Gauss隨機(jī)場(chǎng)賦予f一個(gè)概率分布其中為常數(shù)，Z為配分函數(shù)Diiijjw DW2,1( ) ( )( )2Tiji jEwijfffff1( )TpeZfff令D為一個(gè)對(duì)角矩

18、陣,，表示點(diǎn)i的度, 則定義由此，能量函數(shù)可以改寫(xiě)為：Gauss隨機(jī)場(chǎng)可以改寫(xiě)為：的定義:組合Laplace矩陣基于基于Gauss隨機(jī)場(chǎng)的學(xué)習(xí)隨機(jī)場(chǎng)的學(xué)習(xí)(1/2) 1( )( ) Dijj iiiiwjffllluuluuWWWWW111()()uuuuuulluuulluuull fDWW ffIPP f上式中的含義與圖中的平滑概念是一致的 (f(i)取周?chē)c(diǎn)的均值)將權(quán)重矩陣W寫(xiě)成分4塊的分塊矩陣調(diào)和函數(shù)的解是在滿(mǎn)足fl = yl的條件下使 f = 0其中P為圖的轉(zhuǎn)移概率矩陣，P=D-1W在能量函數(shù)達(dá)到最小的條件下，未標(biāo)注樣本點(diǎn)滿(mǎn)足基于基于Gauss隨機(jī)場(chǎng)的學(xué)習(xí)隨機(jī)場(chǎng)的學(xué)習(xí)(2/2) 基

19、于局部一致和全局平滑的學(xué)習(xí)基于局部一致和全局平滑的學(xué)習(xí)222 ()()0 ijikjjkiijeifNNwotherwisexxxxxx2,11ijiji jiijjwffDD用一個(gè)加權(quán)圖來(lái)描述數(shù)據(jù)集，在滿(mǎn)足與標(biāo)注信息一致的條件下使樣本集的類(lèi)別平滑變化定義圖G = V,W，wij的計(jì)算方法如下根據(jù)相似度越大類(lèi)別越可能一致的原則，定義目標(biāo)函數(shù)是數(shù)據(jù)集中每個(gè)點(diǎn)與其近鄰點(diǎn)間的差異度，越小越好優(yōu)化目標(biāo)函數(shù)優(yōu)化目標(biāo)函數(shù)A Fb1,TTTTlA00yy11,TTTTTllnfFfff2,11min. .ijiji jiijjwstYDDA Fbff聚類(lèi)結(jié)果必須滿(mǎn)足已標(biāo)注的真實(shí)類(lèi)別信息將這些信息表示為等式：

20、A為Cn的系數(shù)矩陣，yi為已標(biāo)注樣本i的真實(shí)類(lèi)別向量(行向量)F為nC的類(lèi)別指示矩陣b是CC的對(duì)角矩陣，bjj等于標(biāo)注樣本中屬于第j類(lèi)的樣本個(gè)數(shù)最優(yōu)的類(lèi)別估計(jì)結(jié)果就是當(dāng)xiL時(shí)，fi =yi因此，半監(jiān)督學(xué)習(xí)問(wèn)題就轉(zhuǎn)化為了如下的最優(yōu)化問(wèn)題優(yōu)化問(wèn)題的求解優(yōu)化問(wèn)題的求解1122CID WDmin. .TtracestYF CFAFb令矩陣，上述優(yōu)化問(wèn)題可轉(zhuǎn)化為(, )()TLtraceFF CFAFb(, )0(, )0TLL FFCFAFAFb將F取0/1值的條件進(jìn)行松弛，使其取實(shí)數(shù)值將優(yōu)化問(wèn)題變?yōu)闃?biāo)準(zhǔn)的二次規(guī)劃問(wèn)題，定義Lagrange函數(shù)令可求得類(lèi)別指示向量F的最優(yōu)實(shí)數(shù)解為T(mén)FR b111()

21、TRACAAC其中演進(jìn)式學(xué)習(xí)演進(jìn)式學(xué)習(xí)n演進(jìn)式學(xué)習(xí)演進(jìn)式學(xué)習(xí)分類(lèi)模型隨著信息環(huán)境的變化而自動(dòng)演進(jìn)u隨機(jī)過(guò)程(而不是隨機(jī)變量)動(dòng)態(tài)描述數(shù)據(jù)分布，使分類(lèi)模型隨著分布的變化而自動(dòng)演進(jìn)u分類(lèi)模型永遠(yuǎn)是動(dòng)態(tài)的，系統(tǒng)通過(guò)應(yīng)用環(huán)境中的樣本對(duì)模型不斷進(jìn)行修正u不再試圖估計(jì)靜態(tài)的“總體分布”，而只考慮當(dāng)前時(shí)刻隨機(jī)變量的分布如何從上一時(shí)刻的分布演進(jìn)出來(lái)u演進(jìn)學(xué)習(xí)通過(guò)小樣本完成，因而可以提高學(xué)習(xí)效率演進(jìn)式學(xué)習(xí)的流程演進(jìn)式學(xué)習(xí)的流程n不斷地從應(yīng)用環(huán)境中獲取新樣本進(jìn)行模型的演進(jìn)u增加自動(dòng)采集新樣本、接收識(shí)別(分類(lèi))模塊的樣本反饋、以及演進(jìn)式模型學(xué)習(xí)和更新分類(lèi)模型等過(guò)程n類(lèi)別標(biāo)注樣本庫(kù)中存放從應(yīng)用環(huán)境中自動(dòng)采集的數(shù)據(jù)樣本

22、和分類(lèi)器識(shí)別后反饋的樣本，作為模型演進(jìn)的數(shù)據(jù)源模型的演進(jìn)方法模型的演進(jìn)方法u假設(shè)S(ti)是隨機(jī)過(guò)程X(t)在ti時(shí)刻的一個(gè)學(xué)習(xí)樣本集相鄰時(shí)刻學(xué)習(xí)樣本集的關(guān)系是: S(ti) = S(ti-1) E(ti) A(ti)即，S(ti)可以通過(guò)從S(ti-1) 中剔除樣本集E(ti)后添加樣本集A(ti)的方法獲得u模型演進(jìn)的關(guān)鍵問(wèn)題：u獲得A(ti)和E(ti)的方法u利用A(ti)和E(ti)對(duì)ti-1時(shí)刻的模型進(jìn)行演進(jìn)，獲得ti時(shí)刻的模型|A(ti)|和|E(ti)|的變化規(guī)律n在t0時(shí)刻用N0個(gè)樣本初始化，演進(jìn)初期|A(ti)| |E(ti)|n隨著系統(tǒng)的成熟，|A(ti)|和| E(t)

23、|逐步接近ntc是系統(tǒng)性能達(dá)到設(shè)計(jì)要求進(jìn)入常態(tài)的時(shí)刻，交換的訓(xùn)練樣本數(shù)為dnd的大小與演進(jìn)周期(ti - ti-1)成正比n在演進(jìn)周期(ti - ti-1)比較短的情況下，|A(ti)|和|E(ti)|都遠(yuǎn)小于|S(ti-1)|。q性能指標(biāo)影響因素：q系統(tǒng)進(jìn)入常態(tài)的時(shí)刻qdA(ti)和E(ti)的獲得nti時(shí)刻以隨機(jī)的方式從采集的樣本和反饋的識(shí)別樣本中選出一個(gè)集合N(ti)，從中選出|A(ti)|個(gè)識(shí)別得分最低的樣本組成A(ti)，在S(ti-1)中選出|E(ti)|個(gè)識(shí)別得分最低的樣本組成E(ti)n|S(ti)| = | S(ti-1)| + |A(ti)| - |E(ti)|n物理意義是

24、通過(guò)更換邊緣樣本來(lái)移動(dòng)學(xué)習(xí)樣本集的類(lèi)中心。 模型演進(jìn)模型演進(jìn) n對(duì)于生成式模型，采用ML準(zhǔn)則下的增量式EM算法n對(duì)于區(qū)分式模型；可采用基于自適應(yīng)特征分布變化的adaboost算法n需要注意的是，由于自動(dòng)采集和識(shí)別反饋的樣本的類(lèi)別標(biāo)注是有錯(cuò)誤率的，因此在沒(méi)有人工校對(duì)的情況下S(ti)是含噪的垃圾郵件及垃圾短信過(guò)濾垃圾郵件及垃圾短信過(guò)濾n 垃圾郵件垃圾郵件(spam)過(guò)濾系統(tǒng)過(guò)濾系統(tǒng)uTREC Spam評(píng)測(cè)的技術(shù)是基于內(nèi)容識(shí)別的，這不同于目前在市場(chǎng)上普遍應(yīng)用的技術(shù)，如黑白名單過(guò)濾、基于地址分析及跟蹤的啟發(fā)式過(guò)濾等u文本分類(lèi)器是TREC Spam技術(shù)的核心，統(tǒng)計(jì)學(xué)習(xí)算法是研究的重點(diǎn)過(guò)濾器的性能過(guò)濾器

25、的性能n兩個(gè)指標(biāo)：uHam錯(cuò)分百分比錯(cuò)分百分比hm%：被錯(cuò)分到Spam目錄中的ham占ham總數(shù)的百分比uSpam錯(cuò)分百分比錯(cuò)分百分比sm%：被錯(cuò)分到Ham目錄中的spam占spam總數(shù)的百分比n系統(tǒng)根據(jù)郵件為spam的可能性進(jìn)行過(guò)濾u若可能性大于閾值t，則將其投入spam目錄，否則投入ham目錄u提高t有利于降低hm%，但會(huì)升高sm%；反之，降低t有利于降低sm%，但會(huì)升高h(yuǎn)m%u給出每封郵件的score，可以通過(guò)改變t值獲得sm%相對(duì)hm%的函數(shù)關(guān)系，這種函數(shù)關(guān)系的圖形表示就是著名的ROC(Receiver Operating Characteristic)曲線(xiàn)Spam過(guò)濾器過(guò)濾器n最常見(jiàn)

26、的是SVM和樸素BayesnBrat 05創(chuàng)新性地將動(dòng)態(tài)數(shù)據(jù)壓縮中的局部匹配預(yù)測(cè)PPM(Prediction by Partial Matching)用于Spam過(guò)濾nPPM是一種自適應(yīng)概率編碼壓縮技術(shù)u每處理被壓縮數(shù)據(jù)的一個(gè)符號(hào)，PPM的概率模型P(x|context)都會(huì)隨之更新u每處理完一個(gè)符號(hào)，都會(huì)得到一個(gè)新的P(x|context)u系統(tǒng)根據(jù)P(x|context)獲得一個(gè)熵編碼方案u編碼方案隨著context的演變而自適應(yīng)調(diào)整PPMn通過(guò)訓(xùn)練數(shù)據(jù)獲得PPM的兩個(gè)概率模型P(x|context-spam)和P(x|context-ham)n與常見(jiàn)的方法的差別：uPPM假設(shè)信源產(chǎn)生符號(hào)

27、的過(guò)程符合k階Markov過(guò)程uPPM模型會(huì)隨著處理的進(jìn)行而自動(dòng)演進(jìn)，這恰好應(yīng)對(duì)了Spam特征的演進(jìn)性n在PPM中，通常約定用-1階模式指出系統(tǒng)的字符集A，并且假定所有字符以相同的概率1/|A|出現(xiàn)n未出現(xiàn)過(guò)的轉(zhuǎn)移模式用Esc表示例例:“abracadabra”的的2階階PPM模型模型 垃圾短信的過(guò)濾垃圾短信的過(guò)濾n短信的基本特點(diǎn)：u長(zhǎng)度短，最長(zhǎng)不能超過(guò)140個(gè)ASCII字符或70個(gè)漢字u不完整(省略、指代、簡(jiǎn)化等)、不規(guī)范(用詞另類(lèi)、語(yǔ)法隨意等) n短信分類(lèi)不統(tǒng)一u運(yùn)營(yíng)商：訂閱（由SP提供的）/ 手寫(xiě)（由手機(jī)用戶(hù)手工輸入的）u用戶(hù)：私人 / 廣告u安全部門(mén)：合法 / 非法 u發(fā)送形式：SPM

28、U / U U / U MUu發(fā)送內(nèi)容：普通短信 / 垃圾短信 / 異常短信 u細(xì)分類(lèi)：聊天短信、問(wèn)候短信、祝福短信、娛樂(lè)短信、新聞短信、理財(cái)短信 基于正則表達(dá)式的分類(lèi)基于正則表達(dá)式的分類(lèi)n正則表達(dá)式(Regular Expression) u由數(shù)學(xué)家Stephen Kleene于1956年提出 u在許多腳本語(yǔ)言中得到支持，如Perl、PHP、JavaScript， 已經(jīng)被國(guó)際組織ISO和Open Group標(biāo)準(zhǔn)化u正則表達(dá)式由模式修正符、元字符、子模式、量詞和斷言等元素組成，通過(guò)一系列模式對(duì)字符串進(jìn)行匹配u快速地分析大量的文本以找到特定的字符模式，提取、編輯、替換或刪除字符串基于統(tǒng)計(jì)的分類(lèi)基

29、于統(tǒng)計(jì)的分類(lèi)n特征抽取主要采用VSM和n-gram模型u構(gòu)造一個(gè)詞的集合來(lái)很好覆蓋短信中出現(xiàn)的詞匯u分詞u詞集合的選擇是短信特征抽取的關(guān)鍵u簡(jiǎn)便的方法是以字為單位進(jìn)行處理n基于單字特征的Bayes分類(lèi)器1212argmax(|,.,)argmax() (,.,|)MAPini Linii LHP Cw wwP C P w wwCargmax()(|)NBikii LkHP CP wCTDT系統(tǒng)系統(tǒng)nTopic: 特指在特定時(shí)間特定地點(diǎn)發(fā)生的事件，而非一般意義的事件類(lèi)u例：“汶川地震”VS“地震”n一個(gè)話(huà)題或事件，會(huì)有多個(gè)相關(guān)的報(bào)道(story)nTDT的任務(wù)u報(bào)道分割t將一個(gè)連續(xù)的文本流劃分為

30、一個(gè)個(gè)報(bào)道u事件檢測(cè)t回顧式檢測(cè) / 在線(xiàn)式檢測(cè)u事件跟蹤t將新產(chǎn)生的報(bào)道與系統(tǒng)已知的事件聯(lián)系起來(lái)t給定目標(biāo)事件的條件下判斷每個(gè)后續(xù)報(bào)道是否在討論這個(gè)目標(biāo)事件報(bào)道分割報(bào)道分割n算法的評(píng)價(jià)u一方面是直接評(píng)價(jià)其對(duì)報(bào)道邊界定位的準(zhǔn)確性u(píng)另一方面是間接評(píng)價(jià)其對(duì)事件追蹤的支持能力n基于HMM進(jìn)行報(bào)道分割u基于話(huà)題轉(zhuǎn)換的概率進(jìn)行分割n基于局部語(yǔ)境分析LCA進(jìn)行報(bào)道分割u將句子轉(zhuǎn)換為L(zhǎng)CA詞，對(duì)其索引后判斷報(bào)道邊界 n將視頻分割應(yīng)用于報(bào)道分割 基于LCA方法的關(guān)鍵要素n基于內(nèi)容的特征: 一對(duì)語(yǔ)言模型，用于幫助判斷話(huà)題是否大幅改變u在線(xiàn)自適應(yīng)語(yǔ)言模型 VS 離線(xiàn)靜態(tài)語(yǔ)言模型n表示局部語(yǔ)境的語(yǔ)言學(xué)和結(jié)構(gòu)特征的詞匯特征u使用各個(gè)詞的位置偏移量對(duì)詞的特征進(jìn)行編碼u以更精細(xì)的粒度對(duì)與分割邊界相關(guān)的詞進(jìn)行判斷 n增量式地選擇最佳的詞匯特征的學(xué)習(xí)算法，并將詞匯特征與語(yǔ)言模型相結(jié)合形成統(tǒng)一的統(tǒng)計(jì)模型u增量式地構(gòu)建一個(gè)越來(lái)越詳細(xì)的模型，對(duì)分割邊界設(shè)置的正確性進(jìn)行概率估計(jì)事件檢測(cè)事件檢測(cè)n在新聞流中標(biāo)識(shí)出新的或是以前沒(méi)有標(biāo)識(shí)的事件n本質(zhì)：無(wú)監(jiān)督的學(xué)習(xí)任務(wù)n模式：回顧式/