3. 使用 EM 的半監(jiān)督文本分類

數(shù)十年以來,統(tǒng)計學(xué)家提倡使用標(biāo)記數(shù)據(jù)和未標(biāo)記數(shù)據(jù)的組合,通過迭代期望最大化(EM)技術(shù)估計生成模型的參數(shù)來訓(xùn)練分類器。本章探討了這種方法在應(yīng)用于文本分類領(lǐng)域時的有效性。本文用一組詞模型來表示文本文檔等缀,這導(dǎo)致了一個基于多項式混合的生成分類模型。這個模型非常簡單地表示了書面文本的復(fù)雜性娇昙。本章闡述并說明了生成模型下文本分類半監(jiān)督學(xué)習(xí)的三個要點尺迂。首先,盡管文本域的表示形式過于簡單,但在生成模型概率和分類精度之間枪狂,有些文本域具有很高的正相關(guān)危喉。在這些領(lǐng)域中,簡單地將em應(yīng)用于NaiveBayes文本模型效果很好州疾。其次辜限,一些文本域沒有這種相關(guān)性。在這里严蓖,我們可以采用一個更具表現(xiàn)力和適當(dāng)?shù)纳赡P捅〉眨_實具有正相關(guān)性。在這些領(lǐng)域中颗胡,半監(jiān)督學(xué)習(xí)再次提高了分類的準(zhǔn)確性毫深。最后,EM還存在局部極大值問題毒姨,特別是在文本分類等高維領(lǐng)域哑蔫。我們證明了確定性退火是EM的一個變種,它可以克服局部極大值問題弧呐,在生成模型適當(dāng)?shù)那闆r下進一步提高分類精度闸迷。

3.1?簡介

從標(biāo)記數(shù)據(jù)和未標(biāo)記數(shù)據(jù)的組合中學(xué)習(xí)分類器是統(tǒng)計學(xué)界的一個老觀點。至少早在1968年俘枫,就有人建議通過測試所有可能的類分配腥沽,將有標(biāo)記和無標(biāo)記的數(shù)據(jù)結(jié)合起來,以建立具有最大似然性的分類器(Hartley和Rao鸠蚪,1968年)今阳。Day(1969)的開創(chuàng)性論文提出了一種迭代的EM-like方法,僅從未標(biāo)記的數(shù)據(jù)中獲得已知協(xié)方差的兩個正態(tài)的混合參數(shù)茅信。類似的迭代算法盾舌,用于從有標(biāo)記和無標(biāo)記的數(shù)據(jù)中構(gòu)建最大似然分類器,隨后使用顯式生成模型蘸鲸,主要用于正態(tài)分布的混合分布(McLachlan矿筝,1975;Titterington棚贾,1976)。

Dempster等人(1977)提出了 EM 框架的理論榆综,將先前提出的用于缺失數(shù)據(jù)的似然最大化的迭代技術(shù)的許多共性集合起來并形式化妙痹。它適用于根據(jù)標(biāo)記和未標(biāo)記數(shù)據(jù)(Murray和Titterington,1978年)估計混合模型的最大似然(或最大后驗)參數(shù)鼻疮,然后將其用于分類(Little怯伊,1977年),立即得到了承認(rèn)判沟。此后耿芹,繼續(xù)使用和研究這種方法(McLachlan和Ganesaligam崭篡,1982年;Ganesaligam吧秕,1989年琉闪;Shahshahani和Landgrebe,1994年)砸彬。最近颠毙,利用混合模型的似然最大化將標(biāo)記和未標(biāo)記的數(shù)據(jù)組合起來進行分類,已經(jīng)向機器學(xué)習(xí)社區(qū)發(fā)展了起來(Miller和Uyar砂碉,1996年蛀蜜;Nigam等人,1998年增蹭;Baluja滴某,1999年)。

期望最大化的理論基礎(chǔ)表明滋迈,當(dāng)模型類生成足夠多的未標(biāo)記數(shù)據(jù)時霎奢,可以找到比僅使用標(biāo)記數(shù)據(jù)更可能的模型。如果分類任務(wù)是預(yù)測生成模型的潛在變量杀怠,那么有足夠的數(shù)據(jù)椰憋,一個更可能的模型也將導(dǎo)致更準(zhǔn)確的分類器。

這種方法基于生成模型是正確的假設(shè)赔退。當(dāng)分類任務(wù)是對人類編寫的文本進行分類時(我們在這里考慮)橙依,真正的生成模型是不可能參數(shù)化的,而實踐者傾向于使用非常簡單的表示硕旗。例如窗骑,常用的樸素貝葉斯分類器將每個編寫的文檔表示為一個單詞包,丟棄所有單詞排序信息漆枚。這個分類器的生成模型斷言文檔是通過從類條件多項式中抽取來創(chuàng)建的创译。由于這是對創(chuàng)作過程的一種極端簡化,因此有必要問一下墙基,這種生成式的半監(jiān)督學(xué)習(xí)建模方法在文本分類領(lǐng)域是否合適或有益软族。

這一章論證了當(dāng)選擇的生成模型概率與分類精度有很好的相關(guān)性,并且可以避免次優(yōu)局部極大值時残制,生成方法適用于半監(jiān)督文本分類立砸。在某些情況下,盡管樸素的貝葉斯生成模型很簡單初茶,但它還是足夠的颗祝。我們發(fā)現(xiàn)模型概率與分類精度密切相關(guān),期望最大化技術(shù)產(chǎn)生的分類器具有未標(biāo)記的數(shù)據(jù),比單獨使用標(biāo)記數(shù)據(jù)構(gòu)建的分類器更精確螺戳。在其他情況下搁宾,樸素貝葉斯生成模型與分類準(zhǔn)確度沒有很好的相關(guān)性。通過采用更具表現(xiàn)力的生成模型倔幼,恢復(fù)了模型的準(zhǔn)確性和概率相關(guān)性盖腿,再次得到了良好的結(jié)果。

EM的一個缺陷是它只保證在模型概率空間中發(fā)現(xiàn)局部極大值而不是全局極大值凤藏。在像文本分類這樣的領(lǐng)域中奸忽,由于參數(shù)數(shù)量非常多,這種效果可能非常顯著揖庄。研究表明栗菜,當(dāng)模型概率和分類之間存在良好的相關(guān)性時,采用確定性退火(一種交替的模型估計過程)可以發(fā)現(xiàn)更可能的蹄梢,從而更準(zhǔn)確的分類器疙筹。

非生成方法也被用于半監(jiān)督文本分類。Joachims(1999)使用轉(zhuǎn)導(dǎo)支持向量機為多個文本分類任務(wù)構(gòu)建識別分類器禁炒。Blum和Mitchell(1998)使用聯(lián)合培訓(xùn)設(shè)置為網(wǎng)頁構(gòu)建Naive Bayes分類器而咆,使用錨文本和頁面本身作為有關(guān)實例的兩個不同信息源。Zelikovitz和Hirsh(2000)使用未標(biāo)記的數(shù)據(jù)作為背景知識來增強最近鄰分類器幕袱。他們不直接將測試示例與其最近的標(biāo)記示例進行匹配暴备,而是通過測量與一組未標(biāo)記示例的相似性,將測試示例與標(biāo)記示例進行匹配们豌。

本章內(nèi)容如下涯捻。第3.2節(jié)介紹了用于文本分類的生成模型,并說明了如何使用em執(zhí)行半監(jiān)督學(xué)習(xí)望迎。第3.3節(jié)給出了一個示例障癌,說明了這種方法在何處工作良好。第3.4節(jié)提出了一個更具表現(xiàn)力的生成模型辩尊,該模型在樸素的貝葉斯假設(shè)不充分時有效涛浙,并從需要它的領(lǐng)域獲得了實驗結(jié)果。第3.5節(jié)給出了確定性退火,并表明這發(fā)現(xiàn)了比EM發(fā)現(xiàn)的模型參數(shù)化更為可能的模型參數(shù)化,尤其是當(dāng)標(biāo)記數(shù)據(jù)稀疏時捐寥。

3.2?文本生成式模型

本節(jié)介紹了一個描述文本文檔的框架,并說明了如何使用該框架從標(biāo)記和未標(biāo)記的數(shù)據(jù)訓(xùn)練分類器我注。該框架定義了概率生成模型,并對生成過程進行了三個假設(shè):(1)數(shù)據(jù)是由混合模型生成的劳秋;(2)混合成分與類之間存在一一對應(yīng)關(guān)系;(3)混合成分是單個詞的多項式分布。這些是樸素貝葉斯分類器使用的假設(shè)玻淑,這是標(biāo)準(zhǔn)監(jiān)督文本分類的常用工具(Lewis嗽冒,1998;McCallum和Nigam补履,1998)添坊。

我們假設(shè)文檔是由多項式模型的混合生成的,其中每個混合分布組件對應(yīng)一個類箫锤。設(shè)有?M?個類別和一個大小為?|\chi|?的詞匯表贬蛙;每個文檔?x_i含有?|x_i|個單詞。如何使用此模型創(chuàng)建文檔谚攒?第一阳准,我們滾動有偏的M面骰子來確定文檔的類。然后馏臭,選取與所選類對應(yīng)的偏|\chi|邊骰子野蝇。我們將這個骰子滾動|x_i|次,計算每個單詞出現(xiàn)的次數(shù)括儒。這些字?jǐn)?shù)構(gòu)成生成的文檔绕沈。

形式上,每個文檔都是根據(jù)由混合模型參數(shù)定義的概率分布生成的帮寻,稱為θ乍狐。概率分布由一個由組件?c_j\in[M]混合分布組成。文檔固逗,x_i浅蚪,首先根據(jù)混合權(quán)重選擇一個混合組件——P(c_j|\theta),然后使用這個被選中的組件根據(jù)自身的參數(shù)依分布P(x_i|c_j;\theta)生成一個文檔抒蚜。因此掘鄙,看到文檔x_i的似然是所有混合分布成分的總概率之和:

P(x_i|\theta)=\sum_{j\in [M]}P(c_j|\theta)P(x_i|c_j;\theta)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(3.1)

每個文檔有一個類標(biāo)簽。我們假設(shè)混合模型組件和類之間是一對一的對應(yīng)關(guān)系嗡髓,因此使用c_j來表示jth混合物組件以及jth類操漠。一個文檔?x_i對應(yīng)的類標(biāo)簽寫為?y_i。如果文檔?x_i是由混合組件c_j生成的我們就說?y_i=c_j饿这。

一個文檔浊伙,x_i,是一個詞匯數(shù)量的向量长捧。我們將x_{it}寫為文檔x_i中出現(xiàn)的單詞w_t的次數(shù)嚣鄙。當(dāng)一個文件由一個特定的混合成分生成時,文件長度串结,|x_i|=\sum\nolimits_{t=1}^{|\chi|}x_{it}哑子,首先是獨立于組件選擇的舅列。然后,利用所選混合組分的多項式分布卧蜓,生成指定長度的文檔帐要。

由此我們可以展開(3.1)中的第二項,并根據(jù)文檔的組成特征(文檔長度和文檔中的單詞)表示給定混合成分的文檔的概率弥奸。

P(x_i|c_j;\theta)\propto P(|x_i|)\prod_{w_t=\chi} P(w_t|c_j;\theta)^{x_{it}}? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(3.2)

這個公式嵌入了標(biāo)準(zhǔn)樸素貝葉斯假設(shè):文檔中的詞匯在給定類標(biāo)簽時是條件獨立于同一文檔中的其他詞匯的榨惠。

因此,單個混合成分的參數(shù)定義了詞的多項式分布盛霎,即?詞概率的集合赠橙,每一個寫為?\theta_{w_t|c_j},因此?\theta_{w_t|c_j}\equiv P(w_t|c_j;\theta)愤炸,這兒?t\in[|\chi|]\sum\nolimits_t P(w_t|c_j:\theta)=1期揪。因為我們假設(shè)對于所有類,文檔長度都是相同分布的摇幻,所以不需要為分類參數(shù)化文檔長度横侦。模型的其他參數(shù)只有混合權(quán)重(類概率),\theta_{cj}\equiv P(c_j|\theta)绰姻,其指示了選擇不同混合成分的概率枉侧。?因此,模型參數(shù)θ的完整集合定義了一組多項式和類概率:\theta = \{\theta_{w_t|c_j}:w_t\in [M];\theta_{c_j}:c_j\in [M]  \}狂芋。

總結(jié)下榨馁,通過結(jié)合方程 3.1 、3.2?給出的的全生成模型帜矾,賦值概率P(x_i|\theta)生成文檔x_i如下:

P(x_i|\theta)\propto P(|x_i|)\sum_{j\in[M]}P(c_j|\theta)\prod_{w_t=\chi} P(w_t|c_j;\theta)^{x_{it}}? ? ? ? ? ?(3.3)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 這兒次數(shù)集x_{it}是生成模型中參數(shù)向量\theta的充分統(tǒng)計翼虫。

3.2.1?基于生成模型的監(jiān)督文本分類

從一組標(biāo)記文檔中學(xué)習(xí)樸素貝葉斯文本分類器包括估計生成模型的參數(shù)。對參數(shù)\theta的估計記為?\hat \theta屡萤。樸素貝葉斯使用最大后驗(MAP)估計珍剑,即找到?argmax_{\theta}P(\theta|X,Y)。這是考慮到訓(xùn)練數(shù)據(jù)的證據(jù)和一個先驗值的最可能的\theta?值死陆。

我們的先驗分布是由Dirichlet分布的乘積形成的招拙,每類多項式一個,總類概率一個措译。Dirichlet是多項式分布中常用的共軛先驗分布别凤。Dirichlet?分布如下:? ? ? ??

P(\theta_{w_t|c_j}|\alpha) \propto \prod_{w_t\in \chi}P(w_t|c_j)^{\alpha_t -1}? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(3.4)

這兒?\alpha_t限制大于 0。我們設(shè)置所有?\alpha_t = 2?领虹,這對應(yīng)一個偏好均勻分布的先驗规哪。這與拉普拉斯和 M-估計 平滑相同。Stolcke和Omohundro對Dirichlet分布作了很好的介紹塌衰。由數(shù)據(jù)和先驗值最大化得到的參數(shù)估計公式是我們熟悉的經(jīng)驗計數(shù)平滑比诉稍。詞概率估計值?\hat\theta_{w_t|c_j}為:

\hat\theta_{w_t|c_j}\equiv P(w_t|c_j;\hat\theta)=\frac{1+\sum\nolimits_{x_i\in \chi}\delta_{ij}x_{it }}{|\chi|+\sum\nolimits_{s=1}^{|\chi|}\sum\nolimits_{x_i\in \chi}\delta_{ij}x_{is}  } ? ? ? ? ? ? ? (3.5)

這兒?\delta_{ij}由類標(biāo)簽給出:1?當(dāng)?y_i=c_j蝠嘉,0?其他。類概率杯巨,即\theta_{c_j}是晨,以同樣的方式估計,并且還涉及一個平滑計數(shù)比:

\hat\theta_{c_j}\equiv P(c_j|\hat \theta)=\frac{1+\sum\nolimits_{i=1}^{|\chi|}\delta_{ij} }{M + |X|} ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (3.6)

這些計數(shù)比公式的推導(dǎo)直接來自于最大后驗參數(shù)估計舔箭。求P(\theta|X,Y)最大化的θ是通過首先用貝葉斯規(guī)則將這個表達式分成兩個項來完成的:P(\theta|X,Y) \propto P(X,Y|\theta)P(\theta)。第一個術(shù)語是根據(jù)所有文檔類型的乘積計算的(從等式 3.1)蚊逢。第二項层扶,參數(shù)上的先驗分布,為?Dirichlets?分布的乘積烙荷。通過求解log(P(\theta|X,Y)的偏導(dǎo)數(shù)系統(tǒng)镜会,使用拉格朗日乘數(shù)來滿足一個類中的詞概率必須和為1的約束,從而使整個表達式最大化终抽。這個最大化產(chǎn)生上面看到的計數(shù)比率戳表。

根據(jù)標(biāo)注的訓(xùn)練文檔計算出的這些參數(shù)的估計值,可以將生成模型反轉(zhuǎn)昼伴,并計算特定混合成分生成給定文檔以執(zhí)行分類的概率匾旭。這源于貝葉斯規(guī)則的應(yīng)用:

P(y_i=c_j|x_i;\hat\theta)=\frac{P(c_j|\hat\theta)P(x_i|c_j;\hat\theta)}{P(x_i|\hat\theta)} =\frac{P(c_j|\hat\theta)\prod_{w_t\in \chi}P(w_t|cj;\hat\theta)^{x_{it}}}{\sum\nolimits_{k=1}^M P(c_k|\hat\theta)\prod_{w_t\in \chi}P(w_t|c_k;\hat\theta)^{x_{it}}} (3.7)

如果任務(wù)是將一個測試文檔分為單個類,然后是后驗概率最高的類圃郊,argmax_jP(y_i=c_j|x_i;\hat\theta)价涝,被選中。

3.2.2?基于?EM?的半監(jiān)督文本分類

在帶有標(biāo)記和未標(biāo)記數(shù)據(jù)的半監(jiān)督設(shè)置中持舆,我們?nèi)匀幌M业阶畲蠛篁瀰?shù)估計色瘩,如上面的監(jiān)督設(shè)置中所示。因為沒有標(biāo)簽的數(shù)據(jù)沒有標(biāo)簽逸寓,所以前一節(jié)中的閉式公式不適用居兆。然而,利用EM 技術(shù)竹伸,我們可以找到生成模型的局部最大后驗參數(shù)估計泥栖。

將EM技術(shù)應(yīng)用于帶有樸素貝葉斯的標(biāo)記和未標(biāo)記數(shù)據(jù)的情況,可以得到一個簡單而吸引人的算法佩伤。首先聊倔,一個樸素的貝葉斯分類器是以標(biāo)準(zhǔn)的監(jiān)督方式從有限的標(biāo)記訓(xùn)練數(shù)據(jù)中構(gòu)建的。然后生巡,我們用樸素貝葉斯模型對未標(biāo)記的數(shù)據(jù)進行分類耙蔑,注意到不是最可能的類,而是與每個類相關(guān)的概率孤荣。這意味著甸陌,根據(jù)這些估計的類概率须揣,未標(biāo)記的文檔被視為幾個部分文檔。我們迭代這個過程钱豁,對未標(biāo)記的數(shù)據(jù)進行分類耻卡,并重建樸素的貝葉斯模型,直到它收斂到一個穩(wěn)定的分類器和數(shù)據(jù)的標(biāo)簽集牲尺。這在算法3.1中進行了總結(jié):

算法 3.1?文本分類器半監(jiān)督學(xué)習(xí)的基本EM算法

\cdot?輸入:標(biāo)記文檔集?X_l和未標(biāo)記文檔集?X_u

\cdot?僅從標(biāo)記文檔集卵酪,X_l,構(gòu)造一個初始化樸素貝葉斯分類器谤碳,\hat\theta溃卡。使用最大后驗參數(shù)估計去找到\hat\theta = argmax_{\theta}P(X_l|\theta)P(\theta)?(見等式 3.5?和 3.6)

\cdot?通過l(\theta|X,Y)的變化測量(標(biāo)記和未標(biāo)記數(shù)據(jù)的對數(shù)概率,以及先驗)蜒简,在分類器參數(shù)改善時循環(huán)(見等式 3.8):

? ??????\cdot?(E?步)使用當(dāng)前分類器瘸羡,\hat \theta,估計每個未標(biāo)記文檔的組件成員身份搓茬,即犹赖,每個混合組? ?分(和類)生成每個文檔的概率,P(c_j|x_i;\hat\theta)(見等式 3.7)

? ??????\cdot?(M?步)根據(jù)每個文檔的估計組件成員關(guān)系卷仑,重新估計分類器峻村,\hat\theta。使用最大后驗(MAP)參數(shù)估計找到?\hat\theta=argmax_{\theta}P(X,Y|\theta)P(\theta)(見等式 3.5?及 3.6)

\cdot?輸出:分類器 锡凝,\hat\theta雀哨,其輸入未標(biāo)記的文檔并預(yù)測類標(biāo)簽。

更正式地說私爷,學(xué)習(xí)分類器的方法是計算\theta的最大后驗估計雾棺,即argmax_{\theta}P(\theta)P(X,Y|\theta),這相當(dāng)于最大化相同函數(shù)的對數(shù)衬浑“坪疲考慮最大化的第二項,所有可觀測數(shù)據(jù)的概率工秩。單個未標(biāo)記文檔的概率是所有類的總概率之和尸饺,如?等式 3.1?中所示。對于標(biāo)記的數(shù)據(jù)助币,生成組件已經(jīng)由標(biāo)簽y_i給出浪听,我們不需要引用與類對應(yīng)的所有混合組件——只需要引用與類對應(yīng)的。使用X_u表示未標(biāo)記的示例眉菱,X_l表示給出標(biāo)簽的示例迹栓,完整數(shù)據(jù)的預(yù)期對數(shù)概率為

l(\theta|X,Y)=log(P(\theta)) + \sum_{x_i \in X_u} log\sum_{j\in [M]} P(c_j|\theta)P(x_i|c_j;\theta) + \sum_{x_i \in X_l} log(P(y_i=c_j|\theta)P(x_i|y_i=c_j;\theta))? (3.8)

(為了方便我們刪除了常數(shù)項)注意,這個方程包含了未標(biāo)記數(shù)據(jù)的和的對數(shù)俭缓,這使得偏導(dǎo)數(shù)的最大化難以計算克伊。EM 的形式化(Dempster 等人酥郭,1977)提供了一種迭代爬山方法,用于在參數(shù)空間中找到模型概率的局部最大值愿吹。算法的E步估計了給定模型參數(shù)最新迭代的缺失值(即未標(biāo)記類信息)的期望值不从。M步驟使用先前計算的缺失值的期望值最大化模型參數(shù)的可能性,就好像它們是真實值一樣犁跪。

實際上椿息,E 步驟對應(yīng)于使用等式3.7對每個未標(biāo)記文檔進行分類。M步對應(yīng)于使用公式 3.5 坷衍、3.6與P(c_j|x_i;\hat\theta)的當(dāng)前估計值 計算參數(shù)撵颊,\hat\theta,的新的最大后驗(MAP)估計惫叛。

本質(zhì)上,所有參數(shù)的初始化都會導(dǎo)致一些局部極大值與?EM逞刷。許多?EM 的實例化都是從隨機選擇一個起始模型參數(shù)化開始的嘉涌。在我們的例子中,由于我們不僅有未標(biāo)記的數(shù)據(jù)夸浅,而且還有一些標(biāo)記的數(shù)據(jù)仑最,所以我們可以對起點進行更為選擇性的選擇。我們的迭代過程是用一個啟動的 M 步驟初始化的帆喇,在這個步驟中警医,只使用標(biāo)記的文檔來估計分類器參數(shù)\hat\theta,如等式3.5坯钦、3.6中所示预皇。然后,循環(huán)從一個E步驟開始婉刀,該步驟使用這個分類器首次概率地標(biāo)記未標(biāo)記的文檔吟温。

該算法迭代,直到收斂到一個點突颊,其中\hat\theta不會隨迭代改變鲁豪。從算法上講,我們通過觀察參數(shù)的對數(shù)概率(公式3.8)低于閾值的變化來確定收斂性律秃,該變化是 EM 爬坡的表面高度爬橡。

3.2.3?討論

這種方法的理由取決于第3.2節(jié)中所述的假設(shè),即數(shù)據(jù)由混合模型生成棒动,并且混合物成分和類別之間存在一一對應(yīng)關(guān)系糙申。如果生成建模假設(shè)是正確的,那么最大化模型概率將是訓(xùn)練分類器的一個很好的標(biāo)準(zhǔn)船惨。在這種情況下郭宝,當(dāng)訓(xùn)練實例數(shù)接近無窮大時辞槐,貝葉斯最優(yōu)分類器對應(yīng)于模型的最大后驗參數(shù)估計。當(dāng)這些假設(shè)不能像真實文本數(shù)據(jù)中那樣確定時粘室,未標(biāo)記數(shù)據(jù)的收益就不那么清楚了榄檬。僅使用標(biāo)記數(shù)據(jù),樸素貝葉斯分類器就可以很好地對文本文檔進行分類(Lewis和Ringuette衔统,1994鹿榜;Craven等人,2000锦爵;Yang和Pedersen舱殿,1997;Joachims险掀,1997沪袭;McCallum等人,1998)樟氢。這一觀察部分解釋為分類估計僅僅是函數(shù)估計的符號(二進制分類)的函數(shù)(Domingos和Pazzani冈绊,1997;Friedman埠啃,1997)死宣。錯誤的單詞獨立性假設(shè)加劇了樸素貝葉斯產(chǎn)生極端(幾乎為0或1)類概率估計的傾向。然而碴开,即使這些估計是不適當(dāng)?shù)臉O端毅该,分類精度也可能相當(dāng)高。

半監(jiān)督學(xué)習(xí)比監(jiān)督學(xué)習(xí)更依賴于模型假設(shè)的正確性潦牛。下一節(jié)將從經(jīng)驗上說明眶掌,這種方法確實可以顯著提高文檔分類器的準(zhǔn)確性,特別是在只有幾個標(biāo)記的文檔的情況下巴碗。

圖片3.1 20個新聞組數(shù)據(jù)集的分類準(zhǔn)確度畏线,包括10000個未標(biāo)記文檔和10000個未標(biāo)記文檔。使用少量的訓(xùn)練數(shù)據(jù)良价,使用 EM 可以生成更精確的分類器寝殴。隨著訓(xùn)練數(shù)據(jù)的大量標(biāo)記,無需使用未標(biāo)記的數(shù)據(jù)就可以得到準(zhǔn)確的參數(shù)估計明垢,兩種方法的分類精度開始收斂蚣常。

3.3?基于基礎(chǔ)?EM?算法的實驗結(jié)果

在本節(jié)中,我們證明了具有標(biāo)記和未標(biāo)記數(shù)據(jù)的半監(jiān)督學(xué)習(xí)提供的文本分類器比僅使用標(biāo)記數(shù)據(jù)的監(jiān)督學(xué)習(xí)提供的文本分類器更準(zhǔn)確痊银。這是一個有趣的結(jié)果抵蚊,因為多項式生成模型的混合是真實創(chuàng)作過程的巨大簡化。然而,我們證明贞绳,對于某些領(lǐng)域谷醉,模型概率的優(yōu)化準(zhǔn)則與分類精度密切相關(guān)。

本節(jié)中的實驗使用了著名的20個新聞組文本分類數(shù)據(jù)集(Mitchell冈闭,1997)俱尼,它由大約20000篇均勻分布在20個新聞組中的 Usenet 文章組成。任務(wù)是將文章分類到發(fā)布它的新聞組中萎攒。對于預(yù)處理遇八,將刪除停止詞,并對每個文檔的字?jǐn)?shù)進行縮放耍休,以使每個文檔具有恒定的長度刃永,并可能具有分?jǐn)?shù)字?jǐn)?shù)。由于數(shù)據(jù)具有時間戳羊精,因此從每個新聞組的最后20%的文章中形成一個測試集斯够。通過從剩余的樣本中隨機選擇10000件樣本,形成一個未標(biāo)記的集合喧锦。標(biāo)記的訓(xùn)練集是通過將剩余的文檔劃分為不重疊的集而形成的读规。我們根據(jù)集合的大小創(chuàng)建最多10個訓(xùn)練集,因為數(shù)據(jù)是可用的裸违。當(dāng)后驗?zāi)P透怕时粓蟾娌@示在圖上時,一些加性和乘性常數(shù)被丟棄本昏,但相對值保持不變供汛。

圖3.1顯示了將 EM 與未標(biāo)記數(shù)據(jù)一起使用對該數(shù)據(jù)集的影響∮磕拢縱軸表示測試集上分類器的平均準(zhǔn)確率怔昨,橫軸表示對數(shù)刻度上標(biāo)記的訓(xùn)練數(shù)據(jù)量。我們改變標(biāo)記的訓(xùn)練數(shù)據(jù)的數(shù)量宿稀,并將傳統(tǒng)的樸素貝葉斯(無未標(biāo)記文檔)的分類準(zhǔn)確度與一個能夠訪問10000個未標(biāo)記文檔的em學(xué)習(xí)者進行比較趁舀。

圖3.2? 散點圖顯示了后驗?zāi)P透怕逝c用標(biāo)記和未標(biāo)記數(shù)據(jù)訓(xùn)練的模型精度之間的相關(guān)性。強相關(guān)性意味著模型概率是20個新聞組數(shù)據(jù)集的一個很好的優(yōu)化標(biāo)準(zhǔn)祝沸。

EM 的表現(xiàn)明顯優(yōu)于傳統(tǒng)的樸素貝葉斯矮烹。例如,有300個標(biāo)記的文檔(每類15個文檔)罩锐,樸素貝葉斯的精確度達到52%奉狈,而 EM 的精確度達到66%。這意味著分類誤差減少了 30%涩惑。注意仁期,即使只有很少的標(biāo)記文檔,EM 也有很好的表現(xiàn);只有20個文檔(每個類只有一個標(biāo)記文檔)跛蛋,樸素貝葉斯獲得20%熬的,EM? 35%。正如所料赊级,當(dāng)有大量的標(biāo)記數(shù)據(jù)押框,而樸素的貝葉斯學(xué)習(xí)曲線接近平穩(wěn)時,擁有未標(biāo)記的數(shù)據(jù)幾乎沒有幫助此衅,因為已經(jīng)有足夠的標(biāo)記數(shù)據(jù)來準(zhǔn)確估計分類器參數(shù)强戴。使用5500份標(biāo)記文檔(每類275份),分類精度從76%提高到78%挡鞍。這些結(jié)果均具有統(tǒng)計學(xué)意義(P<0.05)骑歹。

EM 如何找到更準(zhǔn)確的分類器?它是通過優(yōu)化后驗?zāi)P透怕蕘韺崿F(xiàn)的墨微,而不是直接對分類精度進行優(yōu)化道媚。如果我們的生成模型是完美的,那么我們期望模型的概率和準(zhǔn)確性是相關(guān)的翘县,并且 EM 是有用的最域。但我們知道,我們的簡單生成模型并不能捕獲文本中包含的許多屬性锈麸。我們的20個新聞組的結(jié)果表明镀脂,我們不需要一個完美的模型來幫助 EM 進行文本分類。如果模型的概率和準(zhǔn)確性是相關(guān)的忘伞,生成模型就足以代表文本分類的目的薄翅,從而使 EM 能夠間接地優(yōu)化準(zhǔn)確性。

為了更明確地說明這一點氓奈,讓我們再次看看20個新聞組的實驗翘魄,并根據(jù)經(jīng)驗測量這種相關(guān)性。圖3.2顯示了散點圖中每個點的相關(guān)性舀奶,它們是圖3.1中標(biāo)記的和未標(biāo)記的分割之一暑竟。此處標(biāo)記的數(shù)據(jù)僅用于設(shè)置EM初始化,在迭代期間不使用育勺。我們將分類性能作為測試數(shù)據(jù)的準(zhǔn)確度但荤,并給出后驗?zāi)P透怕省?/p>

對于該數(shù)據(jù)集,分類精度和模型概率具有較好的對應(yīng)性涧至。準(zhǔn)確度與模型概率的相關(guān)系數(shù)為0.9798纱兑,確實是一個很強的相關(guān)性,我們可以將其作為事后驗證化借,證明該數(shù)據(jù)集可以通過生成模型方法使用未標(biāo)記的數(shù)據(jù)潜慎。模型概率的優(yōu)化準(zhǔn)則是適用于此的,因為它與精度是一致的。

3.4?使用更具表現(xiàn)力的生成模型

第3.2節(jié)中生成模型的第二個假設(shè)指出铐炫,混合模型中的類和組件之間存在一對一的對應(yīng)關(guān)系垒手。在某些文本領(lǐng)域,很明顯這樣的假設(shè)是危險的倒信】票幔考慮文本過濾的任務(wù),我們希望從很大的文檔池或文檔流中識別一個定義良好的小類文檔鳖悠。一個例子可能是一個系統(tǒng)榜掌,它監(jiān)視網(wǎng)絡(luò)管理員收到的電子郵件,以識別罕見的緊急情況乘综,這種情況需要在休假時給她打電話憎账。將非緊急郵件建模為僅具有一個多項式分布的負(fù)類將導(dǎo)致無表達力模型。否定類包含各種副標(biāo)題的電子郵件:個人電子郵件卡辰、非緊急請求琴许、垃圾郵件等绪撵。

更具表達力的模型是什么?與其用一個單一的混合成分來模擬大量的負(fù)面例子卓起,不如用多個成分來建模蛔六。這樣擎鸠,在最大化之后睦焕,每一個負(fù)成分都可以捕獲大量的例子红省。本節(jié)對文本數(shù)據(jù)采用了本例所建議的方法,并放寬了混合組件和類之間一對一對應(yīng)的假設(shè)晶疼。我們將其替換為限制性較小的假設(shè):混合組件和類之間的多對一對應(yīng)酒贬。這使我們能夠模擬類的副標(biāo)題結(jié)構(gòu)。

3.4.1?每類多個混合成分

新的生成模型必須考慮混合成分和類之間的多對一對應(yīng)關(guān)系冒晰。和舊模型一樣同衣,我們首先選擇一個帶有偏壓模具輥的類竟块。每個類都有幾個副標(biāo)題壶运;接下來我們將選擇其中一個副標(biāo)題,同樣使用有偏差的骰子浪秘。既然確定了副標(biāo)題蒋情,就生成了文檔中的單詞。我們首先選擇一個長度(獨立于副標(biāo)題和類)耸携,然后從副標(biāo)題的多項式分布中提取單詞棵癣。

與以前不同的是,現(xiàn)在每個未標(biāo)記的文檔都缺少兩個值——類和副標(biāo)題夺衍。即使對于標(biāo)記的數(shù)據(jù)狈谊,也缺少值;盡管類是已知的,但其副標(biāo)題不是河劝。由于我們無法訪問這些丟失的類和副標(biāo)題標(biāo)簽壁榕,因此必須使用諸如EM之類的技術(shù)來估計局部最大后驗(MAP)生成參數(shù)。如第3.2.2節(jié)所述赎瞎,EM 被例示為迭代算法牌里,該算法在估計缺失類和副標(biāo)題標(biāo)簽的值和使用估計標(biāo)簽計算最大后驗(MAP)參數(shù)之間交替進行。當(dāng) EM 收斂到高概率參數(shù)估計后务甥,生成模型可以通過使用貝葉斯規(guī)則來進行文本分類牡辽。

新的生成模型指定了混合組件和類之間的分離。現(xiàn)在敞临,c_j\in [N]只表示第j個混合物成分(副標(biāo)題)态辛,而不是用c_j
來表示這兩個成分。我們?yōu)閷⒌?a
類寫成t_a \in [M]哟绊,當(dāng)組件c_j屬于t_a類時因妙,q_{aj}=1,否則為0票髓。這表示混合組件和類之間預(yù)定的攀涵、確定性的、多對一的映射洽沟。我們分別用y_iz_i表示文檔的類標(biāo)簽和副標(biāo)題標(biāo)簽以故。因此,如果文獻x_i是由混合成分c_j生成的裆操,我們說z_i=c_j怒详,如果文檔屬于t_a類,那么我們稱y_i=t_a踪区。

如果我們的數(shù)據(jù)集知道所有的類和副標(biāo)題標(biāo)簽昆烁,那么為生成參數(shù)找到最大后驗(MAP)估計將是類似于第3.2.1節(jié)中的樸素貝葉斯的閉式方程的一個簡單應(yīng)用。單詞概率參數(shù)的公式與樸素貝葉斯的公式3.5相同缎岗。

\hat \theta_{w_t|c_j}\equiv P(w_t|c_j;\hat\theta) = \frac{1+\sum\nolimits_{x_i\in \chi}\delta_{ij}x_{it}}{|\chi|+\sum\nolimits_{s=1}^{|\chi|}\sum\nolimits_{x_i\in \chi}\delta_{ij}x_{is}  }? ? ? ? ? ? ? ? ? ? ? ? ? ? (3.9)

類概率類似于等式3.6静尼,但使用類的新符號而不是組件:

\hat\theta_{t_a}\equiv P(t_a|\hat\theta) = \frac{1 + \sum\nolimits_{i=1}^{|\chi|}\delta_{ia} }{M +|\chi|}? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (3.10)

副標(biāo)題的概率是相似的,除非它們是根據(jù)組件類中的其他文檔進行估計的:

\hat\theta_{c_j|t_a}\equiv P(c_j|t_a;\hat\theta) = \frac{1+\sum\nolimits_{i=1}^{|\chi|} \delta_{ij}\delta_{ia}}{\sum\nolimits_{j=1}^{N}q_{aj}+\sum\nolimits_{i=1}^{|\chi|}\delta_{ia}}? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (3.11)

在分類時传泊,我們必須估計未標(biāo)記文檔的類成員概率鼠渺。這是通過首先計算副標(biāo)題的成員資格,然后求和副標(biāo)題以獲得總體類概率來完成的眷细。副標(biāo)題成員的計算類似于幼稚貝葉斯的混合成分成員拦盹,只需對兩個先驗(類和副主題)而不是一個先驗進行小調(diào)整即可。

P(z_i=c_j|x_i;\theta)=\frac{\sum\nolimits_{a\in [M]}q_{aj}P(t_a|\hat\theta)P(c_j|t_a;\hat\theta)\prod_{w_t\in \chi}P(w_t|c_j;\hat\theta)^{x_it}}{\sum\nolimits_{r\in [N]}\sum\nolimits_{b\in [M]}q_{br}P(t_b|\hat\theta)P(c_r|t_b;\hat\theta)\prod_{w_t\in \chi}P(w_t|c_r;\hat\theta)^{x_{it}}}? (3.12)

整個類的成員關(guān)系是用類所有副標(biāo)題的概率和計算的:

P(y_i=t_a|x_i;\hat\theta)=\sum\nolimits_{j\in [N]}q_{aj}P(z_i=c_j|x_i;\hat\theta)? ? ? ? ? ? ? ? ? ? ? ? ?(3.13)

只有當(dāng)所有培訓(xùn)文件都有課堂和副標(biāo)題標(biāo)簽時溪椎,這些監(jiān)督學(xué)習(xí)方程才適用普舆。沒有這些恬口,我們使用EM。M 步沼侣,和基本em一樣楷兽,為多項式和先驗建立最大的后驗參數(shù)估計。這是用等式3.9华临、3.10和3.11完成的芯杀。使用前一個E步驟中估計的概率類和次主題成員身份。在E步驟中雅潭,對于未標(biāo)記的文檔揭厚,我們計算概率加權(quán)的副標(biāo)題和類成員身份(等式 3.12和3.13)。對于帶標(biāo)簽的文檔扶供,我們必須估計副標(biāo)題成員身份筛圆。但是我們從它給出的類標(biāo)簽中知道,許多子主題成員必須是零——那些屬于其他類的子主題椿浓。因此太援,我們計算未標(biāo)記數(shù)據(jù)的子主題成員身份,但將適當(dāng)?shù)某蓡T身份設(shè)置為零扳碍,并僅在屬于其類的主題上規(guī)范化非零的成員身份提岔。

如果我們得到一組類標(biāo)記的數(shù)據(jù)和一組未標(biāo)記的數(shù)據(jù),我們現(xiàn)在可以應(yīng)用 EM笋敞,如果每個類都有一些指定的副標(biāo)題數(shù)碱蒙。但是,這些信息通常不可用夯巷。因此赛惩,我們必須借助一些技術(shù)來選擇模型。常用的模型選擇方法有交叉驗證法趁餐、阿卡克信息準(zhǔn)則(AIC)喷兼、貝葉斯信息準(zhǔn)則(BIC)等。由于我們確實有有限數(shù)量的標(biāo)記文檔可用后雷,因此我們使用交叉驗證來選擇分類性能的副標(biāo)題數(shù)量季惯。

表 3.1?使用傳統(tǒng)樸素貝葉斯(NB1)的Reuters二元分類器的分類精度,使用標(biāo)記和未標(biāo)記數(shù)據(jù)的基本 EM(EM1)喷面,使用剛標(biāo)記數(shù)據(jù)的多個混合成分(NB*)星瘾,以及使用標(biāo)記和未標(biāo)記數(shù)據(jù)的多個混合成分EM (EM*)走孽。對于NB*和EM*惧辈,每個試驗的組分?jǐn)?shù)量是最佳選擇的,括號中顯示了負(fù)類試驗的組分中間數(shù)磕瓷。請注意盒齿,對于路透社來說念逞,多成分模型更自然,因為它的否定類包含許多主題边翁。每個類同時使用未標(biāo)記的數(shù)據(jù)和多個混合組件可以提高性能翎承,而不是單獨使用或使用樸素的貝葉斯。

表 3.1?

3.4.2?實驗結(jié)果

這里符匾,我們提供了經(jīng)驗證據(jù)叨咖,證明在生成建模方法中使用未標(biāo)記的數(shù)據(jù),有時需要更具表現(xiàn)力的生成模型啊胶。與原始生成模型相比甸各,分類精度與模型概率呈負(fù)相關(guān),在使用未標(biāo)記數(shù)據(jù)時分類精度較低焰坪。使用更具表達力的生成模型趣倾,可以獲得中等的正相關(guān),從而提高分類精度某饰。

路透社21578發(fā)行版1.0的數(shù)據(jù)集包括大約13000篇來自路透社通訊社的新聞文章儒恋,這些文章被標(biāo)記為90個主題類別。此數(shù)據(jù)集中的文檔具有多個類標(biāo)簽黔漂,并且傳統(tǒng)上使用二進制分類器評估每個類別诫尽。在其他幾項研究(Joachims,1998炬守;Liere和Tadepalli箱锐,1997)之后,我們?yōu)槭畟€人口最多的類中的每一個構(gòu)建了二進制分類器劳较,以確定主題驹止。我們使用了一個非索引字表,但不停止观蜗。每項 Reuters 試驗的詞匯大小都是通過優(yōu)化準(zhǔn)確度來選擇的臊恋,這是通過在標(biāo)記的訓(xùn)練集上留出一個交叉驗證來測量的。使用標(biāo)準(zhǔn)的Modapte列車/測試分割墓捻,這是時間敏感的抖仅。可供培訓(xùn)的9603份文件中有七千份未貼標(biāo)簽砖第。從其余部分中撤卢,我們隨機選擇最多10個不重疊的訓(xùn)練集,其中只有10個正標(biāo)記文檔和40個負(fù)標(biāo)記文檔梧兼。

表3.1中結(jié)果的前兩列重復(fù)了第3.3節(jié)中關(guān)于路透社數(shù)據(jù)集的基本em的實驗放吩。在這里我們看到,對于大多數(shù)類別羽杰,分類精度隨著引入未標(biāo)記的數(shù)據(jù)而降低渡紫〉酵疲考慮到標(biāo)記和未標(biāo)記數(shù)據(jù)的證據(jù),對于每個路透社類別惕澎,em都發(fā)現(xiàn)了一個更為可能的模型莉测。但是,這個更可能的模型常常對應(yīng)一個低精度的分類器唧喉,而不是我們所希望的捣卤。

圖3.3 顯示了Reuters ACQ 任務(wù)的模型概率和分類精度之間的關(guān)系的散點圖。在左邊八孝,只有一個負(fù)類的混合成分腌零,概率和準(zhǔn)確度成反比,這正是我們不想要的唆阿。在右側(cè)益涧,10個混合成分為負(fù),模型概率與分類精度之間存在中等正相關(guān)

圖3.3中 的第一個圖提供了對未標(biāo)記數(shù)據(jù)為什么會受到損傷的理解驯鳖。每類有一個混合成分闲询,分類精度和模型概率之間的相關(guān)性非常強(r=-0.9906),但方向不對浅辙!概率較高的模型分類精度明顯較低扭弧。通過對EM發(fā)現(xiàn)的解決方案的分析,我們發(fā)現(xiàn)最可能的數(shù)據(jù)聚類有一個部分包含了大多數(shù)負(fù)面文檔记舆,第二個部分包含了大部分正面文檔鸽捻,但負(fù)面文檔明顯更多。因此泽腮,類與高概率模型不分離御蒲。

此數(shù)據(jù)集中的文檔通常具有多個類標(biāo)簽。在基本的生成模型中诊赊,負(fù)類覆蓋了多達89個不同的類別厚满。因此,期望用單一的混合成分捕獲如此廣泛的文本基礎(chǔ)是不合理的碧磅。為此碘箍,我們放松了生成模型,用一個混合成分對正類進行建模鲸郊,用一個到四十個混合成分對負(fù)類進行建模丰榴,無論是否有未標(biāo)記的數(shù)據(jù)。

表3.1的后半部分顯示了使用每類多個混合物生成模型的結(jié)果秆撮。注意兩個不同的結(jié)果四濒。首先,對于單獨標(biāo)記的數(shù)據(jù)(nb*),分類精度比每個類的單個組件(nb1)高峻黍。第二,對于未標(biāo)記的數(shù)據(jù)拨匆,新的生成模型結(jié)果(em*)通常優(yōu)于其他結(jié)果姆涩。在路透社的所有試驗中,未標(biāo)記數(shù)據(jù)的增加具有統(tǒng)計學(xué)意義(p<0.05)惭每。

表3.2 當(dāng)通過交叉驗證(EM*CV)選擇組分?jǐn)?shù)量時骨饿,與最佳選擇(EM*)和簡單樸素貝葉斯(NB1)相比,使用多個混合物組分的性能台腥。注意交叉驗證通常選擇的組件太少宏赘。

表 3.2

對于十個混合組分,精度和模型概率之間的相關(guān)性是非常不同的黎侈。右圖3.3顯示了使用十個混合組分對負(fù)類進行建模時察署,精度與模型概率之間的相關(guān)性。在這里峻汉,模型概率與正確方向的分類精度之間存在中等相關(guān)性(r=0.5474)贴汪。對于這些解決方案,一個組件幾乎涵蓋了所有的正面文檔和一些(但不是很多)負(fù)面文檔休吠。其他十個部分通過剩余的負(fù)面文檔分發(fā)扳埂。由于分類精度和模型概率是相關(guān)的,因此該模型更能代表我們的分類任務(wù)的數(shù)據(jù)瘤礁。這使得通過生成模型方法可以有效地使用未標(biāo)記的數(shù)據(jù)阳懂。

一個顯而易見的問題是,如何在不訪問測試集標(biāo)簽的情況下自動選擇最佳數(shù)量的混合組分柜思。我們使用“留一法交叉驗證”岩调。與樸素貝葉斯(NB1)和最佳EM (EM*)相比,該技術(shù)(EM*CV)的結(jié)果如表3.2所示赡盘。請注意誊辉,交叉驗證并不能完美地選擇測試集上性能最佳的組件數(shù)量。結(jié)果一致地表明亡脑,通過交叉驗證選擇的組件數(shù)量比最佳組件數(shù)量少堕澄。

3.4.3?討論

模型的復(fù)雜性與數(shù)據(jù)的稀疏性之間存在著模型選擇過程中的張力,只要有大量的副標(biāo)題和文檔霉咨,就可以很好地對訓(xùn)練數(shù)據(jù)進行建模蛙紫,每個副標(biāo)題包含一個訓(xùn)練文檔。由于仍然存在大量的副標(biāo)題途戒,我們可以對現(xiàn)有數(shù)據(jù)進行精確的建模坑傅,但泛化性能較差。這是因為每一個多項式將有它的許多參數(shù)估計從少數(shù)文件喷斋,并將遭受稀疏的數(shù)據(jù)唁毒。副標(biāo)題很少蒜茴,就會出現(xiàn)相反的問題。我們將非常準(zhǔn)確地估計多項式浆西,但模型將受到過度限制粉私,不能代表真實的文檔分布。交叉驗證應(yīng)該有助于在這些緊張關(guān)系之間選擇一個很好的折衷方案近零,特別是在分類性能方面诺核。

注意,我們對每個類使用多個混合組件允許我們捕獲類級別上單詞之間的一些依賴關(guān)系久信。例如窖杀,考慮一個體育課,它包含關(guān)于曲棍球和棒球的文檔裙士。在這些文檔中入客,單詞 ice 和 puck 可能同時出現(xiàn),單詞 bat 和 base 可能同時出現(xiàn)腿椎。然而痊项,在體育課上,這些依賴性不能通過對單詞的一個多項式分布來捕獲酥诽。每個班級有多個混合成分鞍泉,一個多項式可以覆蓋曲棍球副標(biāo)題,另一個則覆蓋棒球副標(biāo)題肮帐。在曲棍球的副標(biāo)題中咖驮,“冰和冰球”這個詞的概率比全部類別的概率要高得多。這使得它們在曲棍球文件中的共存比在單一多項式假設(shè)下更為可能训枢。

3.5?克服局部最大值的挑戰(zhàn)

在參數(shù)空間的似然性與分類精度密切相關(guān)的情況下托修,我們的優(yōu)化得到了很好的分類器。然而恒界,當(dāng)?shù)氐母裱悦黠@阻礙了我們的進步睦刃。例如,我們在第3.3節(jié)中僅用幾個帶標(biāo)簽的示例發(fā)現(xiàn)的局部最大值比標(biāo)記數(shù)據(jù)充足時提供的分類精度低40多個百分點十酣。因此涩拙,考慮其他有助于彌合這一差距的方法是很重要的,尤其是在標(biāo)記數(shù)據(jù)稀疏的情況下耸采。

通常情況下兴泥,為了加快收斂速度,創(chuàng)建了EM的變體或替代品(McLachlan和Krishnan虾宇,1997)搓彻。然而,在文本分類領(lǐng)域,我們已經(jīng)看到收斂速度非承癖幔快怔接。因此,我們可以很容易地考慮以較慢收斂為代價來改進局部極大值情況的EM替代方案稀轨。確定性退火正是這種權(quán)衡扼脐。

3.5.1?確定性退火

確定性退火背后的直覺是,它開始于一個非常光滑的凸曲面上的最大化靶端,而這個曲面只與我們真正感興趣的概率曲面有著極遠的聯(lián)系谎势。最初我們可以找到這個簡單曲面的全局最大值凛膏。慢慢地杨名,我們改變表面,使之變得更粗糙猖毫,更接近真實的概率表面台谍。如果我們在曲面變得更復(fù)雜時遵循原始最大值,那么當(dāng)給定原始曲面時吁断,我們?nèi)匀挥幸粋€很可能的最大值趁蕊。通過這種方式,它避免了許多當(dāng)?shù)氐母裱宰幸郏駝t他們會被抓住掷伙。

我們在前幾節(jié)中應(yīng)用 EM 可以認(rèn)為是一個優(yōu)化問題,其中損失函數(shù)是似然函數(shù)的否定(等式3.8)又兵。EM 的迭代是參數(shù)空間中的爬山算法任柜,局部地將損失最小化。

考慮一組密切相關(guān)的損失函數(shù):? ? ??l(\theta|X,Y)=\sum_{x_i\in X_u}log\sum_{c_j\in [M]}[P(c_j|\theta)P(x_i|c_j;\theta)]^{\beta}+ \sum_{x_i\in X_l}log([P(y_i=c_j|\theta)P(x_i|y_i=c_j;\theta)]^{\beta})? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (3.14)

其中β在0和1之間變化沛厨。當(dāng)β=1時宙地,我們熟悉前面章節(jié)的概率曲面,與分類精度有很好的相關(guān)性逆皮,但具有許多有害的局部最大值宅粥。當(dāng)β接近于零時,參數(shù)空間中損失函數(shù)的表面值變成凸的电谣,只有一個全局最大值秽梅。但在這種極端情況下,所提供的數(shù)據(jù)對損失函數(shù)沒有影響剿牺,與分類精度的相關(guān)性較差风纠。零和一之間的值表示參數(shù)空間平滑度與數(shù)據(jù)提供的良好相關(guān)概率曲面相似性之間權(quán)衡的不同點。

這種見解是驅(qū)動所謂確定性退火方法的原因之一牢贸。(Rose等人竹观,1992年),首次用作在無監(jiān)督集群期間構(gòu)建層次結(jié)構(gòu)的方法。它還用于從未標(biāo)記的數(shù)據(jù)(Ueda和Nakano臭增,1995)估計高斯混合體的參數(shù)懂酱,并從未標(biāo)記的數(shù)據(jù)構(gòu)建文本層次(Hofmann和Puzicha,1998)誊抛。

對于β的固定值列牺,我們可以通過迭代以下步驟找到給定損失函數(shù)的局部最大值:

\cdot?E?步:計算類分派的預(yù)期值,\hat z_{ij}^{(k+1)}=E[y_i=c_j|x_i;\hat\theta ^k]=\frac{[P(c_j|\hat\theta ^k)P(x_i|c_j;\hat\theta ^k)]^{\beta}}{\sum_{c_r \in [M]}[P(c_r|\hat\theta ^k)P(x_i|c_r;\hat\theta ^k)]^{\beta}}? ? ? ? ?(3.15)

\cdot?M?步:使用預(yù)期的類分派找到最可能的模型拗窃,

\hat\theta^{k+1}=argmax_{\theta}P(\theta|X;Y;\hat z^{k+1})? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?(3.16)

M?步與3.2.2?節(jié)的是一樣的瞎领,而E步驟包括通過\beta的損失約束。

在形式上随夸,β是一個拉格朗日乘子九默,當(dāng)根據(jù)最大熵(或先驗分布的最小相對熵)的優(yōu)化準(zhǔn)則求解似然空間中的固定損失時。一個 \beta?接近于零對應(yīng)于為一個允許損失非常大的模型找到最大熵參數(shù)化宾毒。

考慮不同目標(biāo)損失對模型可能性(等式3.14)的影響驼修。當(dāng)目標(biāo)損失非常大時,\beta將非常接近于零诈铛;每個模型的概率將非常接近于其先驗概率乙各,因為數(shù)據(jù)的影響可以忽略不計。在\beta變?yōu)榱愕臉O限條件下幢竹,概率曲面將是凸的耳峦,具有一個全局最大值。對于較小的損失目標(biāo)焕毫,\beta將很小蹲坷,但不能忽略。在這里咬荷,數(shù)據(jù)的概率會有更大的影響冠句,不再有單一的全局最大值,而是幾個幸乒。當(dāng)β=1時懦底,我們有前面章節(jié)中我們熟悉的概率曲面,有許多局部極大值罕扎。

這些觀察結(jié)果表明了尋找低損耗模型的退火過程聚唐。如果我們將\beta初始化為非常小的,我們可以很容易地找到具有 EM 的全局最大后驗解腔召,因為曲面是凸的杆查。當(dāng)我們提高β值時,概率曲面會變得更加粗糙和復(fù)雜臀蛛,因為數(shù)據(jù)的可能性會對模型的概率產(chǎn)生更大的影響亲桦。雖然更復(fù)雜崖蜜,但如果我們稍微降低溫度(1/\beta),新的最大值將非常接近舊的最大值客峭。因此豫领,當(dāng)用em搜索最大值時,我們可以用舊的最大值對其進行初始化舔琅,并為新的概率曲面收斂到一個好的最大值等恐。這樣,我們可以逐步提高\beta备蚓,同時跟蹤一個很可能的解课蔬。最終,當(dāng)\beta變?yōu)?時郊尝,我們將有一個很好的生成模型假設(shè)的局部最大值二跋。因此,我們將從標(biāo)記和未標(biāo)記的數(shù)據(jù)中找到一個高概率的局部最大值虚循,然后我們可以使用它進行分類同欠。

請注意样傍,確定性退火的計算成本明顯高于 EM横缔。雖然每次迭代都采用相同的計算,但由于溫度降低非常緩慢衫哥,確定性退火的迭代次數(shù)更多茎刚。例如,在我們的實驗中撤逢,我們對確定性退火進行了390次迭代膛锭,對EM只進行了7次迭代。當(dāng)能夠提供額外的計算時蚊荣,這樣做的好處可能是分類器更加精確初狰。

3.5.2?實驗結(jié)果

在這一節(jié)中,我們從經(jīng)驗上看到互例,當(dāng)標(biāo)記的訓(xùn)練數(shù)據(jù)稀疏時奢入,確定性退火比EM找到更可能的參數(shù)和更準(zhǔn)確的分類器。

對于實驗結(jié)果媳叨,我們使用 News5 數(shù)據(jù)集腥光,它是20個新聞組的一個子集,其中包含五個容易混淆的comp.*類糊秆。我們?yōu)樗械膶嶒灤_定了一個單一的詞匯表武福,作為在整個標(biāo)記數(shù)據(jù)集上通過相互信息測量的前4000個單詞。為了運行這個確定性退火算法痘番,我們初始化\beta?為 0.02捉片,我通過乘以一個因子 1.01?增加?\beta?的值直到?\beta = 1平痰。我們幾乎沒有努力調(diào)整這些參數(shù)。因為每次我們增加?\beta?的概率表面變化很小伍纫,我們在每個溫度設(shè)置下只運行一次?EM 迭代觉增。每類600份隨機文件(共3000份)視為未貼標(biāo)簽。每個類固定數(shù)量的標(biāo)記示例也隨機選擇翻斟。其余文檔用作測試集逾礁。

圖 3.4?與 EM 相比,確定性退火的性能访惜。如果完全完成了類到組件的分配嘹履,那么確定性退火將比標(biāo)記數(shù)據(jù)稀疏時的 EM 更精確。雖然默認(rèn)的對應(yīng)關(guān)系很差债热,但是可以用少量的領(lǐng)域知識來糾正艇棕。

圖3.4比較了確定性退火與常規(guī)EM的分類精度。最初的結(jié)果表明赌厅,當(dāng)標(biāo)記數(shù)據(jù)豐富時注益,這兩種方法的性能基本相同,但當(dāng)標(biāo)記數(shù)據(jù)為稀疏墙杯。例如配并,每個類有兩個標(biāo)記的例子(總共十個),EM 給出58%的準(zhǔn)確度高镐,而確定性退火只給出51%溉旋。對混淆矩陣的深入研究表明,當(dāng)標(biāo)記數(shù)據(jù)稀疏時嫉髓,與確定性退火的類對組件不正確對應(yīng)存在顯著的不利影響观腊。這是因為,當(dāng)溫度非常高時算行,全局最大值將使每個多項式混合分量非常接近其先驗值梧油,并且標(biāo)記數(shù)據(jù)的影響最小。由于先驗是相同的州邢,所以每個混合成分基本上是相同的儡陨。隨著溫度的降低,混合成分變得更加明顯偷霉,當(dāng)沒有足夠的標(biāo)記數(shù)據(jù)將簇拉向正確的類時迄委,一個組件可以輕松地跟蹤與錯誤類關(guān)聯(lián)的聚類。

為了解決這個問題类少,我們在完成確定性退火之后叙身,根據(jù)每個標(biāo)記示例的分類,將類更改為集群對應(yīng)關(guān)系硫狞。圖3.4顯示了通過經(jīng)驗選擇的對應(yīng)關(guān)系獲得的精度信轿,以及通過完全對應(yīng)關(guān)系獲得的最佳精度晃痴。我們發(fā)現(xiàn),通過經(jīng)驗設(shè)置對應(yīng)關(guān)系财忽,確定性退火只會略微提高精度倘核,在得到51%之前,通過改變對應(yīng)關(guān)系即彪,我們將其提高到55%紧唱,在58%時仍不優(yōu)于 EM。然而隶校,如果我們能夠執(zhí)行完美的類對應(yīng)漏益,確定性退火的精度將是67%,遠遠高于 EM深胳。

圖3.5? 比較EM和確定性退火模型概率和精度的散點圖绰疤。結(jié)果表明,確定性退火是成功的舞终,因為它找到了概率顯著較高的模型轻庆。

為了驗證確定性退火的更高精度來自于尋找更可能的模型,圖3.5顯示了確定性退火(具有最優(yōu)類分配)和 EM 的模型概率與精度的散點圖敛劝。兩個值得注意的結(jié)果非常突出余爆。第一個問題是,確實確定性退火發(fā)現(xiàn)了更可能的模型攘蔽,即使有少量的標(biāo)記數(shù)據(jù)龙屉。這說明了確定性退火的額外準(zhǔn)確性呐粘。第二個值得注意的是满俗,通過確定性退火發(fā)現(xiàn)的模型仍然沿著相同的概率精度相關(guān)線。這進一步證明了模型的概率和準(zhǔn)確性與此數(shù)據(jù)集有很強的相關(guān)性作岖,并且相關(guān)性不僅僅是電磁干擾的產(chǎn)物唆垃。

3.5.3?討論

實驗結(jié)果表明,如果解決了類與組件之間的對應(yīng)關(guān)系痘儡,確定性退火確實可以幫助分類辕万。確定性退火成功地避免了陷入局部極大值的不足,而是找到了更可能的模型沉删。由于這些高概率模型與高精度分類器相關(guān)渐尿,因此確定性退火可以很好地利用未標(biāo)記的數(shù)據(jù)進行文本分類。

當(dāng)只有有限的標(biāo)記數(shù)據(jù)時矾瑰,類對應(yīng)問題最為嚴(yán)重砖茸。這是因為在標(biāo)簽較少的例子中,小的干擾更可能導(dǎo)致通信誤入歧途殴穴。然而凉夯,只要有一點人類的知識货葬,班級通信問題通常可以解決瑣碎劲够。在除最大和最令人困惑的分類任務(wù)外的所有分類任務(wù)中震桶,根據(jù)最具指示性的單詞(如加權(quán)對數(shù)似然比)等度量標(biāo)準(zhǔn)來衡量),可以很容易地識別一個類征绎。例如蹲姐,表3.3 中顯示了按此度量設(shè)置的每類數(shù)據(jù)的前十個詞。僅從這十個詞來看人柿,任何一個擁有一點點領(lǐng)域知識的人都可以很好地為組件分配類淤堵。因此,在確定性退火完成之后顷扩,需要少量的人力來糾正類對應(yīng)關(guān)系并不是不合理的拐邪。這項工作可以定位在主動學(xué)習(xí)框架內(nèi)。因此隘截,當(dāng)標(biāo)記的訓(xùn)練數(shù)據(jù)最稀疏扎阶,并且培訓(xùn)師可以適當(dāng)投資將類標(biāo)簽映射到集群組件時,確定性退火將成功地找到比傳統(tǒng) EM 更可能和更準(zhǔn)確的模型婶芭。

即使這個有限的領(lǐng)域知識或人力資源不可用东臀,也應(yīng)該可以自動估計類的對應(yīng)關(guān)系∠可以對數(shù)據(jù)執(zhí)行?EM 和確定性退火惰赋。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市呵哨,隨后出現(xiàn)的幾起案子赁濒,更是在濱河造成了極大的恐慌,老刑警劉巖孟害,帶你破解...
    沈念sama閱讀 223,002評論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件拒炎,死亡現(xiàn)場離奇詭異,居然都是意外死亡挨务,警方通過查閱死者的電腦和手機击你,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評論 3 400
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來谎柄,“玉大人丁侄,你說我怎么就攤上這事〕祝” “怎么了鸿摇?”我有些...
    開封第一講書人閱讀 169,787評論 0 365
  • 文/不壞的土叔 我叫張陵,是天一觀的道長捍歪。 經(jīng)常有香客問我户辱,道長鸵钝,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,237評論 1 300
  • 正文 為了忘掉前任庐镐,我火速辦了婚禮恩商,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘必逆。我一直安慰自己怠堪,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 69,237評論 6 398
  • 文/花漫 我一把揭開白布名眉。 她就那樣靜靜地躺著粟矿,像睡著了一般。 火紅的嫁衣襯著肌膚如雪损拢。 梳的紋絲不亂的頭發(fā)上陌粹,一...
    開封第一講書人閱讀 52,821評論 1 314
  • 那天,我揣著相機與錄音福压,去河邊找鬼掏秩。 笑死,一個胖子當(dāng)著我的面吹牛荆姆,可吹牛的內(nèi)容都是我干的蒙幻。 我是一名探鬼主播,決...
    沈念sama閱讀 41,236評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼胆筒,長吁一口氣:“原來是場噩夢啊……” “哼邮破!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起仆救,我...
    開封第一講書人閱讀 40,196評論 0 277
  • 序言:老撾萬榮一對情侶失蹤抒和,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后派桩,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體构诚,經(jīng)...
    沈念sama閱讀 46,716評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,794評論 3 343
  • 正文 我和宋清朗相戀三年铆惑,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片送膳。...
    茶點故事閱讀 40,928評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡员魏,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出叠聋,到底是詐尸還是另有隱情撕阎,我是刑警寧澤,帶...
    沈念sama閱讀 36,583評論 5 351
  • 正文 年R本政府宣布碌补,位于F島的核電站虏束,受9級特大地震影響棉饶,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜镇匀,卻給世界環(huán)境...
    茶點故事閱讀 42,264評論 3 336
  • 文/蒙蒙 一照藻、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧汗侵,春花似錦幸缕、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,755評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至雪猪,卻和暖如春栏尚,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背只恨。 一陣腳步聲響...
    開封第一講書人閱讀 33,869評論 1 274
  • 我被黑心中介騙來泰國打工抵栈, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人坤次。 一個月前我還...
    沈念sama閱讀 49,378評論 3 379
  • 正文 我出身青樓古劲,卻偏偏與公主長得像,于是被迫代替她去往敵國和親缰猴。 傳聞我的和親對象是個殘疾皇子产艾,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,937評論 2 361