半監(jiān)督學(xué)習(xí)中的協(xié)同訓(xùn)練算法

1、半監(jiān)督學(xué)習(xí)中的協(xié)同訓(xùn)練風(fēng)范周志華南京大學(xué)計(jì)算機(jī)軟件新技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，南京2100931. 引言在傳統(tǒng)的監(jiān)督學(xué)習(xí)中，學(xué)習(xí)器通過(guò)對(duì)大量有標(biāo)記的(labeled )訓(xùn)練例進(jìn)行學(xué)習(xí)，從而建立模型用于預(yù)測(cè)未見(jiàn)示例的標(biāo)記。這里的“標(biāo)記”(label )是指示例所對(duì)應(yīng)的輸出，在分類(lèi)問(wèn)題中標(biāo)記就是示例的類(lèi)別，而在回歸問(wèn)題中標(biāo)記就是示例所對(duì)應(yīng)的實(shí)值輸出。隨著數(shù)據(jù)收集和存儲(chǔ)技術(shù)的飛速發(fā) 展，收集大量未標(biāo)記的(un labeled )示例已相當(dāng)容易，而獲取大量有標(biāo)記的示例則相對(duì)較為困難， 因?yàn)楂@得這些標(biāo)記可能需要耗費(fèi)大量的人力物力。例如在計(jì)算機(jī)輔助醫(yī)學(xué)圖像分析中，可以從醫(yī)院 獲得大量的醫(yī)學(xué)圖像作為訓(xùn)練例，但如果

2、要求醫(yī)學(xué)專(zhuān)家把這些圖像中的病灶都標(biāo)識(shí)出來(lái)，則往往是 不現(xiàn)實(shí)的。事實(shí)上，在真實(shí)世界問(wèn)題中通常存在大量的未標(biāo)記示例，但有標(biāo)記示例則比較少，尤其 是在一些在線應(yīng)用中這一問(wèn)題更加突出。例如，在進(jìn)行Web網(wǎng)頁(yè)推薦時(shí)，需要用戶(hù)標(biāo)記出哪些網(wǎng)頁(yè)是他感興趣的，很少會(huì)有用戶(hù)愿意花大量的時(shí)間來(lái)提供標(biāo)記，因此有標(biāo)記的網(wǎng)頁(yè)示例比較少，但Web上存在著無(wú)數(shù)的網(wǎng)頁(yè)，它們都可作為未標(biāo)記示例來(lái)使用。顯然，如果只使用少量的有標(biāo)記示例，那么利用它們所訓(xùn)練出的學(xué)習(xí)系統(tǒng)往往很難具有強(qiáng)泛化 能力；另一方面，如果僅使用少量“昂貴的”有標(biāo)記示例而不利用大量“廉價(jià)的”未標(biāo)記示例，則 是對(duì)數(shù)據(jù)資源的極大的浪費(fèi)。因此，在有標(biāo)記示例較少時(shí)，如何利用

3、大量的未標(biāo)記示例來(lái)改善學(xué)習(xí) 性能已成為當(dāng)前機(jī)器學(xué)習(xí)研究中最受關(guān)注的問(wèn)題之一。目前，利用未標(biāo)記示例的主流學(xué)習(xí)技術(shù)主要有三大類(lèi)Zhou06，即半監(jiān)督學(xué)習(xí)(semi-supervisedlearning )、直推學(xué)習(xí)(transductive learning )和主動(dòng)學(xué)習(xí)(active learning )。這三類(lèi)技術(shù)都是試圖利用大量的未標(biāo)記示例來(lái)輔助對(duì)少量有標(biāo)記示例的學(xué)習(xí)，但它們的基本思想?yún)s有顯著的不同。在半監(jiān)督學(xué)習(xí)ChapelleSZ06Zhu06中，學(xué)習(xí)器試圖自行利用未標(biāo)記示例，即整個(gè)學(xué)習(xí)過(guò)程不需人工干預(yù)，僅基于學(xué)習(xí)器自身對(duì)未標(biāo)記示例進(jìn)行利用。直推學(xué)習(xí)Vapnik98Joachims99與半

4、監(jiān)督學(xué)習(xí)的相似之處是它也是由學(xué)習(xí)器自行利用未標(biāo)記示例，但不同的是，直推學(xué)習(xí)假定未標(biāo)記示例就是測(cè)試?yán)磳W(xué) 習(xí)的目的就是在這些未標(biāo)記示例上取得最佳泛化能力。換句話(huà)說(shuō)，半監(jiān)督學(xué)習(xí)考慮的是一個(gè)“開(kāi)放 世界”，即在進(jìn)行學(xué)習(xí)時(shí)并不知道要預(yù)測(cè)的示例是什么，而直推學(xué)習(xí)考慮的則是一個(gè)“封閉世界”，在學(xué)習(xí)時(shí)已經(jīng)知道了需要預(yù)測(cè)哪些示例。實(shí)際上，直推學(xué)習(xí)這一思路直接來(lái)源于統(tǒng)計(jì)學(xué)習(xí)理論*本文得到國(guó)家自然科學(xué)基金(60635030)和全國(guó)優(yōu)秀博士學(xué)位論文作者專(zhuān)項(xiàng)基金(200343)資助Vapnik98，并被一些學(xué)者認(rèn)為是統(tǒng)計(jì)學(xué)習(xí)理論對(duì)機(jī)器學(xué)習(xí)思想的最重要的貢獻(xiàn)有人認(rèn)為統(tǒng)計(jì)學(xué)習(xí)理論的最重要貢獻(xiàn)是支持向量機(jī)，但實(shí)際上，支持

5、向量機(jī)只是對(duì)結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則的一個(gè)實(shí)現(xiàn),在處理非線性時(shí)用到了核技巧(kernel trick )。結(jié)構(gòu)風(fēng)險(xiǎn)最小化的思想在機(jī)器學(xué)習(xí)中早已有之，只是以往的研究沒(méi)有 適時(shí)地總結(jié)成一套完整的框架；至于核技巧，則在機(jī)器學(xué)習(xí)和模式識(shí)別領(lǐng)域早就在使用了。而直推學(xué)習(xí)則是和經(jīng)典 的歸納學(xué)習(xí)很不相同的一個(gè)思路。其出發(fā)點(diǎn)是不要通過(guò)解一個(gè)困難的問(wèn)題來(lái)解決一個(gè)相對(duì)簡(jiǎn)單的問(wèn)題。V. Vapnik認(rèn)為，經(jīng)典的歸納學(xué)習(xí)假設(shè)期望學(xué)得一個(gè)在整個(gè)示例分布上具有低錯(cuò)誤率的決策函數(shù)，這實(shí)際上把問(wèn)題復(fù)雜化了，因?yàn)樵诤芏嗲闆r下， 人們并不關(guān)心決策函數(shù)在整個(gè)示例分布上性能怎么樣，而只是期望在給定的要預(yù)測(cè)的示例上達(dá)到最 好的性能。后者比前者

6、簡(jiǎn)單，因此，在學(xué)習(xí)過(guò)程中可以顯式地考慮測(cè)試?yán)龔亩菀椎剡_(dá)到目的。這一思想在機(jī)器學(xué)習(xí)界目前仍有爭(zhēng)議，但直推學(xué)習(xí)作為一種重要的利用未標(biāo)記示例的技術(shù)，則已經(jīng)受到了眾多學(xué)者的關(guān)注。主動(dòng)學(xué)習(xí)SeungOS92LewisG94AbeM98和前面兩類(lèi)技術(shù)不同，它假設(shè)學(xué) 習(xí)器對(duì)環(huán)境有一定的控制能力，可以“主動(dòng)地”向?qū)W習(xí)器之外的某個(gè)“神諭”(oracle)這里的“神諭”可以是人，也可以是能夠?yàn)槭纠峁┱鎸?shí)標(biāo)記的其他過(guò)程。進(jìn)行查詢(xún)來(lái)獲得訓(xùn)練例的標(biāo)記。因此，在主動(dòng)學(xué)習(xí)中，學(xué)習(xí)器自行挑選出一些未標(biāo)記示例并通過(guò)神諭查詢(xún)獲得 這些示例的標(biāo)記，然后再將這些有標(biāo)記示例作為訓(xùn)練例來(lái)進(jìn)行常規(guī)的監(jiān)督學(xué)習(xí)，而其技術(shù)難點(diǎn)則在 于如何

7、使用盡可能少的查詢(xún)來(lái)獲得強(qiáng)泛化能力。對(duì)比半監(jiān)督學(xué)習(xí)、直推學(xué)習(xí)和主動(dòng)學(xué)習(xí)可以看出， 后者在利用未標(biāo)記示例的過(guò)程中需要與外界進(jìn)行交互，而前兩者則完全依靠學(xué)習(xí)器自身，正因?yàn)榇?，也有一些研究者將直推學(xué)習(xí)作為一種半監(jiān)督學(xué)習(xí)技術(shù)來(lái)進(jìn)行研究。本章的主旨是介紹半監(jiān)督學(xué)習(xí)中的協(xié)同訓(xùn)練(co-training )這一風(fēng)范(paradigm)，因此，對(duì)直推學(xué)習(xí)和主動(dòng)學(xué)習(xí)不再做更多的介紹，僅在第2節(jié)對(duì)半監(jiān)督學(xué)習(xí)的概況做一簡(jiǎn)要描述。第3至5節(jié)將從學(xué)習(xí)算法、理論分析、實(shí)際應(yīng)用等三個(gè)方面來(lái)介紹協(xié)同訓(xùn)練的研究進(jìn)展，第6節(jié)則列出幾個(gè)可能值得進(jìn)一步研究的問(wèn)題。2. 半監(jiān)督學(xué)習(xí)一般認(rèn)為，半監(jiān)督學(xué)習(xí)的研究始于B. Shahshaha

8、ni和D. Landgrebe的工作ShahshahaniL94，但未標(biāo)記示例的價(jià)值實(shí)際上早在上世紀(jì)80年代末就已經(jīng)被一些研究者意識(shí)到了Lippman89。D.J.Miller和H.S. Uyar MillerU97認(rèn)為，半監(jiān)督學(xué)習(xí)的研究起步相對(duì)較晚，可能是因?yàn)樵诋?dāng)時(shí)的主流機(jī) 器學(xué)習(xí)技術(shù)(例如前饋神經(jīng)網(wǎng)絡(luò))中考慮未標(biāo)記示例相對(duì)比較困難。隨著統(tǒng)計(jì)學(xué)習(xí)技術(shù)的不斷發(fā)展，以及利用未標(biāo)記示例這一需求的日漸強(qiáng)烈，半監(jiān)督學(xué)習(xí)才在近年來(lái)逐漸成為一個(gè)研究熱點(diǎn)。半監(jiān)督學(xué)習(xí)的基本設(shè)置是給定一個(gè)來(lái)自某未知分布的有標(biāo)記示例集L=( x1, y1), (x2, y2),X |L|,yL|)以及一個(gè)未標(biāo)記示例集 U = *

9、' X2 , "X ui',期望學(xué)得函數(shù)f: Xt丫可以準(zhǔn)確地對(duì)示例x預(yù)測(cè)其 標(biāo)記y。這里Xi,為 X均為d維向量，比 Y為示例Xj的標(biāo)記，|L|和|U|分別為L(zhǎng)和U的大小，即它們所包含的示例數(shù)。在介紹具體的半監(jiān)督學(xué)習(xí)技術(shù)之前，有必要先探討一下為什么可以利用未標(biāo)記示例來(lái)改善學(xué)習(xí)性能。關(guān)于這個(gè)問(wèn)題，有不少研究者給出了解釋。例如，D.J. Miller和H.S. Uyar MillerU97 從數(shù)據(jù)分布估計(jì)的角度給出了一個(gè)直觀的分析。他們假設(shè)所有數(shù)據(jù)服從于某個(gè)由L個(gè)高斯分布混合而成的分布，即Lf (x1 9)= "a f (x 町(1)l = 1其中"

10、ta=1為混合系數(shù)，e= Bi為參數(shù)。這樣，標(biāo)記就可視為一個(gè)由選定的混合成分mi和特征向量Xi以概率P(G | Xi, mi)決定的隨機(jī)變量。于是，根據(jù)最大后驗(yàn)概率假設(shè)，最優(yōu)分類(lèi)由式2給出：h(x) = argmax"P(G = k m = j,Xi )P(m = j xj(2)aj f ( 9j )其中 P(m = j 為)='L 。"ai f (xi B)l=1這樣，學(xué)習(xí)目標(biāo)就變成了利用訓(xùn)練例來(lái)估計(jì)P(ci = k | mj = j, Xi)和P(mi = j | x)。這兩項(xiàng)中的第一項(xiàng)與類(lèi)別標(biāo)記有關(guān)，而第二項(xiàng)并不依賴(lài)于示例的標(biāo)記，因此，如果有大量的未標(biāo)記示例可

11、用，則意味 著能夠用于估計(jì)第二項(xiàng)的示例數(shù)顯著增多，這會(huì)使得第二項(xiàng)的估計(jì)變得更加準(zhǔn)確，從而導(dǎo)致式2更加準(zhǔn)確，也就是說(shuō)，分類(lèi)器的泛化能力得以提高。此后，T. Zhang和F. J. Oles ZhangOOO進(jìn)一步分析了未標(biāo)記示例在半監(jiān)督學(xué)習(xí)中的價(jià)值，并指出如果一個(gè)參數(shù)化模型如果能夠分解成P(x, y | B) = P(y| x, B) P(x | B的形式，那么未標(biāo)記示例的價(jià)值就體現(xiàn)在它們能夠幫助更好地估計(jì)模型參數(shù)從而導(dǎo)致 模型性能的提高。實(shí)際上，只要能夠合理建立未標(biāo)記示例分布和學(xué)習(xí)目標(biāo)之間的聯(lián)系，就可以利用未標(biāo)記示例來(lái)輔助提高學(xué)習(xí)性能。在Shahshaha niL94MillerU97中，這一

12、聯(lián)系是通過(guò)對(duì)生成式模型(gen erativemodel)參數(shù)的估計(jì)來(lái)體現(xiàn)的，但在更一般的情況下就需要在某些假設(shè)的基礎(chǔ)上來(lái)建立未標(biāo)記示例和目標(biāo)之間的聯(lián)系。目前，在半監(jiān)督學(xué)習(xí)中有兩個(gè)常用的基本假設(shè)，即聚類(lèi)假設(shè)(cluster assumption)禾口流形假設(shè)(manifold assumption )聚類(lèi)假設(shè)是指處在相同聚類(lèi)(cluster)中的示例有較大的可能擁有相同的標(biāo)記。根據(jù)該假設(shè)，決 策邊界就應(yīng)該盡量通過(guò)數(shù)據(jù)較為稀疏的地方，從而避免把稠密的聚類(lèi)中的數(shù)據(jù)點(diǎn)分到?jīng)Q策邊界兩側(cè)。在這一假設(shè)下，大量未標(biāo)記示例的作用就是幫助探明示例空間中數(shù)據(jù)分布的稠密和稀疏區(qū)域，從而 指導(dǎo)學(xué)習(xí)算法對(duì)利用有標(biāo)記示例

13、學(xué)習(xí)到的決策邊界進(jìn)行調(diào)整，使其盡量通過(guò)數(shù)據(jù)分布的稀疏區(qū)域。聚類(lèi)假設(shè)簡(jiǎn)單、直觀，常以不同的方式直接用于各種半監(jiān)督學(xué)習(xí)算法的設(shè)計(jì)中。例如，T. JoachimsJoachims99提出了 TSVM算法這實(shí)際上是一個(gè)直推算法。,在訓(xùn)練過(guò)程中，該算法不斷修改SVM的劃分超平面并交換超平面兩側(cè)某些未標(biāo)記示例的可能標(biāo)記，使得SVM在所有訓(xùn)練數(shù)據(jù)（包括有標(biāo)記和未標(biāo)記示例）上最大化間隔（margin），從而得到一個(gè)既通過(guò)數(shù)據(jù)相對(duì)稀疏的區(qū)域又盡可能正確劃分有標(biāo)記示例的超平面；N. D. Lawrenee 和 M. I. Jordan LawrenceJ05 通過(guò)修改高斯過(guò)程（Gaussian process）中

14、的噪音模型來(lái) 進(jìn)行半監(jiān)督學(xué)習(xí)，他們?cè)谡?、反兩?lèi)之間引入了“零類(lèi)”，并強(qiáng)制要求所有的未標(biāo)記示例都不能被分為零類(lèi)，從而迫使學(xué)習(xí)到的分類(lèi)邊界避開(kāi)數(shù)據(jù)稠密區(qū)域；Y. Gran dvalet和Y. Ben gio Gra ndvaletB05通過(guò)使用最小化熵作為正則化項(xiàng)來(lái)進(jìn)行半監(jiān)督學(xué)習(xí)，由于熵僅與模型在未標(biāo)記示例上的輸出有關(guān)，因 此，最小化熵的直接結(jié)果就是降低模型的不確定性，迫使決策邊界通過(guò)數(shù)據(jù)稀疏區(qū)域。流形假設(shè)是指處于一個(gè)很小的局部鄰域內(nèi)的示例具有相似的性質(zhì)，因此，其標(biāo)記也應(yīng)該相似。這一假設(shè)反映了決策函數(shù)的局部平滑性。和聚類(lèi)假設(shè)著眼整體特性不同，流形假設(shè)主要考慮模型的 局部特性。在該假設(shè)下，大量未標(biāo)記

15、示例的作用就是讓數(shù)據(jù)空間變得更加稠密，從而有助于更加準(zhǔn) 確地刻畫(huà)局部區(qū)域的特性，使得決策函數(shù)能夠更好地進(jìn)行數(shù)據(jù)擬合。流形假設(shè)也可以容易地直接用于半監(jiān)督學(xué)習(xí)算法的設(shè)計(jì)中。例如，J. Zhu等人ZhuGL03使用高斯隨機(jī)場(chǎng)以及諧波函數(shù)來(lái)進(jìn)行半監(jiān)督學(xué)習(xí)，他們首先基于訓(xùn)練例建立一個(gè)圖，圖中每個(gè)結(jié)點(diǎn)就是 一個(gè)（有標(biāo)記或未標(biāo)記）示例，然后求解根據(jù)流形假設(shè)定義的能量函數(shù)的最優(yōu)值，從而獲得對(duì)未標(biāo) 記示例的最優(yōu)標(biāo)記；D. Zhou等人ZhouBLWS04 在根據(jù)示例相似性建立圖之后，讓示例的標(biāo)記信息不斷向圖中的鄰近示例傳播，直到達(dá)到全局穩(wěn)定狀態(tài)。值得注意的是，一般情形下，流形假設(shè)和聚類(lèi)假設(shè)是一致的。由于聚類(lèi)通常

16、比較稠密，滿(mǎn)足流 形假設(shè)的模型能夠在數(shù)據(jù)稠密的聚類(lèi)中得出相似的輸出。然而，由于流形假設(shè)強(qiáng)調(diào)的是相似示例具 有相似的輸出而不是完全相同的標(biāo)記，因此流行假設(shè)比聚類(lèi)假設(shè)更為一般，這使其在聚類(lèi)假設(shè)難以 成立的半監(jiān)督回歸中仍然有效 ZhouL05bZhouL07。根據(jù)半監(jiān)督學(xué)習(xí)算法的工作方式，可以大致將現(xiàn)有的很多半監(jiān)督學(xué)習(xí)算法分為三大類(lèi)。第一類(lèi) 算法以生成式模型為分類(lèi)器，將未標(biāo)記示例屬于每個(gè)類(lèi)別的概率視為一組缺失參數(shù)，然后采用EM算法來(lái)進(jìn)行標(biāo)記估計(jì)和模型參數(shù)估計(jì)，其代表包括Shahshaha niL94MillerU97 NigamMTMOO 等。此類(lèi)算法可以看成是在少量有標(biāo)記示例周?chē)M(jìn)行聚類(lèi)，是早期直

17、接采用聚類(lèi)假設(shè)的做法。第二類(lèi)算 法是基于 圖正則化框架的半監(jiān)督學(xué)習(xí)算法，其代表包括BlumC01ZhuGL03Belki nN 04 ZhouBLWS04Belk in NS05等。此類(lèi)算法直接或間接地利用了流形假設(shè)，它們通常先根據(jù)訓(xùn)練例及 某種相似度度量建立一個(gè)圖，圖中結(jié)點(diǎn)對(duì)應(yīng)了（有標(biāo)記或未標(biāo)記）示例，邊為示例間的相似度，然 后，定義所需優(yōu)化的目標(biāo)函數(shù)并使用決策函數(shù)在圖上的光滑性作為正則化項(xiàng)來(lái)求取最優(yōu)模型參數(shù)。第三類(lèi)算法是協(xié)同訓(xùn)練（co-training ）算法。此類(lèi)算法隱含地利用了聚類(lèi)假設(shè)或流形假設(shè)，它們使用 兩個(gè)或多個(gè)學(xué)習(xí)器，在學(xué)習(xí)過(guò)程中，這些學(xué)習(xí)器挑選若干個(gè)置信度高的未標(biāo)記示例進(jìn)行相互

18、標(biāo)記， 從而使得模型得以更新。在A. Blum和T. Mitchell BlumM98提出最早的協(xié)同訓(xùn)練算法后，很多研究者對(duì)其進(jìn)行了研究并取得了很多進(jìn)展，使得協(xié)同訓(xùn)練成為半監(jiān)督學(xué)習(xí)中最重要的風(fēng)范（paradigm）之一，而不再只是一個(gè)算法。本章接下來(lái)的幾節(jié)就將對(duì)協(xié)同訓(xùn)練進(jìn)行進(jìn)一步的介紹。3. 協(xié)同訓(xùn)練算法最初的協(xié)同訓(xùn)練算法（或稱(chēng)為標(biāo)準(zhǔn)協(xié)同訓(xùn)練算法）是 A. Blum和T. Mitchell BlumM98 在1998 年提出的。他們假設(shè)數(shù)據(jù)集有兩個(gè)充分冗余（sufficient and redundant）的視圖（view），即兩個(gè)滿(mǎn)足下述條件的屬性集：第一，每個(gè)屬性集都足以描述該問(wèn)題，也就是

19、說(shuō)，如果訓(xùn)練例足夠，在每個(gè)屬 性集上都足以學(xué)得一個(gè)強(qiáng)學(xué)習(xí)器；第二，在給定標(biāo)記時(shí)，每個(gè)屬性集都條件獨(dú)立于另一個(gè)屬性集。A. Blum和T. Mitchell認(rèn)為，充分冗余視圖這一要求在不少任務(wù)中是可滿(mǎn)足的。例如，在一些網(wǎng)頁(yè)分 類(lèi)問(wèn)題上，既可以根據(jù)網(wǎng)頁(yè)本身包含的信息來(lái)對(duì)網(wǎng)頁(yè)進(jìn)行正確分類(lèi)，也可以利用鏈接到該網(wǎng)頁(yè)的超 鏈接所包含的信息來(lái)進(jìn)行正確分類(lèi)，這樣的網(wǎng)頁(yè)數(shù)據(jù)就有兩個(gè)充分冗余視圖，刻畫(huà)網(wǎng)頁(yè)本身包含的 信息的屬性集構(gòu)成第一個(gè)視圖，而刻畫(huà)超鏈接所包含的信息的屬性集構(gòu)成第二個(gè)視圖。A. Blum和T.Mitchell的算法在兩個(gè)視圖上利用有標(biāo)記示例分別訓(xùn)練出一個(gè)分類(lèi)器，然后，在協(xié)同訓(xùn)練過(guò)程中，每 個(gè)分類(lèi)

20、器從未標(biāo)記示例中挑選出若干標(biāo)記置信度（即對(duì)示例賦予正確標(biāo)記的置信度）較高的示例進(jìn) 行標(biāo)記，并把標(biāo)記后的示例加入另一個(gè)分類(lèi)器的有標(biāo)記訓(xùn)練集中，以便對(duì)方利用這些新標(biāo)記的示例 進(jìn)行更新。協(xié)同訓(xùn)練過(guò)程不斷迭代進(jìn)行，直到達(dá)到某個(gè)停止條件。該算法如圖1所示，其中XX2分別指示例X在第1視圖和第2視圖上對(duì)應(yīng)的示例。A. Blum和T. Mitchell BlumM98 對(duì)圖1的算法進(jìn)行了分析，證明了在充分冗余視圖這一條件成立時(shí)，圖1算法可以有效地通過(guò)利用未標(biāo)記示例提升學(xué)習(xí)器的性能，實(shí)驗(yàn)也驗(yàn)證了該算法具有較好的性能。Input: the labeled training set Lthe unlabeled

21、training set UProcess:Create a pool U' of examples by choosing u examples at random from ULoop for k iterations:Use L to train a classifier h1 that considers only the X1 portion of xUse L to train a classifier h2 that considers only the x2 portion of xAllow h1 to label p positive and n negative

22、examples from U' Allow h2 to label p positive and n negative examples from U' Add th ese self-labeled examples to LRandomly choose 2p+2n examples from U to replenish U'圖1標(biāo)準(zhǔn)協(xié)同訓(xùn)練算法BlumM98然而，在真實(shí)問(wèn)題中充分冗余視圖這一要求往往很難得到滿(mǎn)足。實(shí)際上，即使對(duì)A. Blum和T.Mitchell所舉的網(wǎng)頁(yè)分類(lèi)的例子來(lái)說(shuō)也是這樣，因?yàn)椤熬W(wǎng)頁(yè)本身的信息”這一視圖與“超鏈接上的信息”這一視圖很難滿(mǎn)足

23、條件獨(dú)立性。K. Nigam和R. Ghani NigamG對(duì)協(xié)同訓(xùn)練算法在不具有充分冗余視圖的問(wèn)題上的性能進(jìn)行了實(shí)驗(yàn)研究，其結(jié)果表明，在屬性集充分大時(shí)，可以隨機(jī)把屬性集劃 分成兩個(gè)視圖，在此基礎(chǔ)上進(jìn)行協(xié)同訓(xùn)練也可能取得較好的效果。遺憾的是，大多數(shù)的問(wèn)題并不具 有“充分大”的屬性集，而且隨機(jī)劃分視圖這一策略并非總能奏效，因此，一些研究者開(kāi)始試圖設(shè) 計(jì)不需要充分冗余視圖的協(xié)同訓(xùn)練算法。S. Goldman和Y. Zhou GoldmanZOO提出了一種不需要充分冗余視圖的協(xié)同訓(xùn)練算法。他們使用不同的決策樹(shù)算法，從同一個(gè)屬性集上訓(xùn)練出兩個(gè)不同的分類(lèi)器，每個(gè)分類(lèi)器都可以把示例空間 劃分為若干個(gè)等價(jià)類(lèi)

24、。在協(xié)同訓(xùn)練過(guò)程中，每個(gè)分類(lèi)器通過(guò)統(tǒng)計(jì)技術(shù)來(lái)估計(jì)標(biāo)記置信度，并且把標(biāo) 記置信度最高的示例進(jìn)行標(biāo)記后提交給另一個(gè)分類(lèi)器作為有標(biāo)記訓(xùn)練例，以便對(duì)方進(jìn)行更新。該過(guò) 程反復(fù)進(jìn)行，直到達(dá)到某個(gè)停止條件。在預(yù)測(cè)階段，該算法先估計(jì)兩個(gè)分類(lèi)器對(duì)未見(jiàn)示例的標(biāo)記置 信度，然后選擇置信度高的分類(lèi)器進(jìn)行預(yù)測(cè)。S. Goldman和Y. Zhou將該算法建立在 A. Angluin和P. Laird An glui nL88的噪音學(xué)習(xí)理論的基礎(chǔ)上，并通過(guò)實(shí)驗(yàn)對(duì)算法性能進(jìn)行了驗(yàn)證。此后，他們ZhouG04又對(duì)該算法進(jìn)行了擴(kuò)展，使其能夠使用多個(gè)不同種類(lèi)的分類(lèi)器。雖然S. Goldman和Y. Zhou的算法GoldmanZ

25、OO不再要求問(wèn)題本身具有充分冗余視圖，但他們引入了對(duì)分類(lèi)器種類(lèi)的限制。此外，他們?yōu)榱斯烙?jì)標(biāo)記置信度，在挑選未標(biāo)記示例進(jìn)行標(biāo)記的過(guò) 程中以及選擇分類(lèi)器對(duì)未見(jiàn)示例進(jìn)行預(yù)測(cè)的過(guò)程中頻繁地使用10倍交叉驗(yàn)證，時(shí)間開(kāi)銷(xiāo)很大。同時(shí)，在少量有標(biāo)記數(shù)據(jù)上進(jìn)行10倍交叉驗(yàn)證經(jīng)常難以得到對(duì)置信度的穩(wěn)定估計(jì)。為了進(jìn)一步放松協(xié)同訓(xùn)練的約束條件，Z.-H. Zhou和M. Li ZhouL05a 提出了一種既不要求充分冗余視圖、也不要求使用不同類(lèi)型分類(lèi)器的tri-training算法。該算法的一個(gè)顯著特點(diǎn)是使用了三個(gè)分類(lèi)器，不僅可以簡(jiǎn)便地處理標(biāo)記置信度估計(jì)問(wèn)題以及對(duì)未見(jiàn)示例的預(yù)測(cè)問(wèn)題，還可以利用集成 學(xué)習(xí)(ensemb

26、le learning) Dietterich00 來(lái)提高泛化能力。該算法首先對(duì)有標(biāo)記示例集進(jìn)行可重復(fù)取樣(bootstrap sampling )以獲得三個(gè)有標(biāo)記訓(xùn)練集，然后從每個(gè)訓(xùn)練集產(chǎn)生一個(gè)分類(lèi)器。在協(xié)同訓(xùn) 練過(guò)程中，各分類(lèi)器所獲得的新標(biāo)記示例都由其余兩個(gè)分類(lèi)器協(xié)作提供，具體來(lái)說(shuō)，如果兩個(gè)分類(lèi)對(duì)同一個(gè)未標(biāo)記示例的預(yù)測(cè)相同，則該示例就被認(rèn)為具有較高的標(biāo)記置信度，并在標(biāo)記后被加入 第三個(gè)分類(lèi)器的有標(biāo)記訓(xùn)練集。在對(duì)未見(jiàn)示例進(jìn)行預(yù)測(cè)時(shí)，tri-training算法不再象以往算法那樣挑選一個(gè)分類(lèi)器來(lái)使用，而是使用集成學(xué)習(xí)中經(jīng)常用到的投票法來(lái)將三個(gè)分類(lèi)器組成一個(gè)集成來(lái)實(shí)現(xiàn)對(duì) 未見(jiàn)示例的預(yù)測(cè)。與以往協(xié)

27、同訓(xùn)練算法需要顯式地對(duì)標(biāo)記置信度進(jìn)行估計(jì)不同，tri-training算法通過(guò)判斷三個(gè)分類(lèi)器的預(yù)測(cè)一致性來(lái)隱式地對(duì)不同未標(biāo)記示例的標(biāo)記置信度進(jìn)行比較，這一做法使得該算法不需要頻 繁地使用耗時(shí)的統(tǒng)計(jì)測(cè)試技術(shù)。但與顯式估計(jì)標(biāo)記置信度相比，這一隱式處理往往不夠準(zhǔn)確，特別 是如果初始分類(lèi)器比較弱，未標(biāo)記示例可能被錯(cuò)誤標(biāo)記，從而給第三個(gè)分類(lèi)器的訓(xùn)練引入噪音。乙-H.Zhou和M. Li ZhouL05a基于噪音學(xué)習(xí)理論 AngluinL88推導(dǎo)出了能以較高概率確保這一做法有 效的條件，直觀地說(shuō)，如果大多數(shù)未標(biāo)記示例的標(biāo)記是準(zhǔn)確的，那么引入的噪音所帶來(lái)的負(fù)面影響 可以被使用大量未標(biāo)記示例所帶來(lái)的好處抵消。

28、為了進(jìn)一步降低噪音影響，有必要使用一些更可靠的誤差估計(jì)技術(shù)，但這會(huì)在一定程度上增大算法的開(kāi)銷(xiāo)。此后，M. Li和 乙-H. Zhou LiZ07 對(duì)tri-training進(jìn)行了擴(kuò)展，提出了可以更好發(fā)揮集成學(xué)習(xí)作用的Co-Forest算法。Tri-training算法最近被D. Mavroeidis 等人MavroeidisCPCV06用來(lái)參加歐洲機(jī)器學(xué)習(xí)/數(shù)據(jù)挖掘競(jìng)賽ECML/PKDD2006 Discovery Challenge并獲得了較好的名次。以往的半監(jiān)督學(xué)習(xí)研究幾乎都是關(guān)注分類(lèi)問(wèn)題 半監(jiān)督聚類(lèi)已有不少研究，但由于聚類(lèi)本身是一種非監(jiān)督學(xué)習(xí)技術(shù)， 因此半監(jiān)督聚類(lèi)的岀發(fā)點(diǎn)與半監(jiān)督分類(lèi)、

29、回歸 等期望利用大量未標(biāo)記示例來(lái)輔助對(duì)少量有標(biāo)記示例的學(xué)習(xí)很不相同，而且其所利用的額外信息也并非未標(biāo)記示例， 而是有標(biāo)記示例、示例相似性約束等，所以，本章未對(duì)半監(jiān)督聚類(lèi)進(jìn)行討論。，雖然在監(jiān)督學(xué)習(xí)中回歸問(wèn)題的重要性不亞于分 類(lèi)問(wèn)題，半監(jiān)督回歸卻一直缺乏研究。如第二節(jié)所述，在半監(jiān)督回歸中由于示例的標(biāo)記是實(shí)值輸出， 因此聚類(lèi)假設(shè)不再成立，但半監(jiān)督學(xué)習(xí)的流形假設(shè)仍然是成立的，而且因?yàn)榛貧w輸出通常具有平滑 性，所以流形假設(shè)在回歸問(wèn)題中可能比在分類(lèi)問(wèn)題中更加有效。因此，如Zhu Zhu06所述，一些基于流形假設(shè)的半監(jiān)督學(xué)習(xí)技術(shù)，例如圖正則化算法，在理論上是可以推廣到半監(jiān)督回歸中去的。但 實(shí)際上，此類(lèi)技術(shù)由

30、于要先建立圖再進(jìn)行標(biāo)記傳播，因此若直接推廣則只能進(jìn)行直推回歸，要進(jìn)行 半監(jiān)督回歸還需要做一些其他處理。乙-H. Zhou和M. Li ZhouL05b 最早使用協(xié)同訓(xùn)練技術(shù)進(jìn)行半監(jiān)督回歸。在回歸問(wèn)題中，由于示例的屬性是連續(xù)的實(shí)數(shù)值，這就使得以往協(xié)同訓(xùn)練算法中所使用的標(biāo)記置信度估計(jì)技術(shù)難以直接使 用。為此，他們提出了一個(gè)選擇標(biāo)記置信度最高的未標(biāo)記示例的準(zhǔn)則一一標(biāo)記置信度最高的未標(biāo)記 示例是在標(biāo)記后與學(xué)習(xí)器的有標(biāo)記訓(xùn)練集最一致的示例。更嚴(yán)格的表述是，令h表示當(dāng)前學(xué)習(xí)器學(xué)得的模型，L表示有標(biāo)記示例集，xu U表示一個(gè)未標(biāo)記示例，h'表示把h標(biāo)記過(guò)的示例(Xu , h(xu)加入訓(xùn) 練集后重新

31、訓(xùn)練得到的學(xué)習(xí)器，則標(biāo)記置信度最高的未標(biāo)記示例是在U中最大化式3的示例。1 2 1 2Au =刀(Vi - h (xi)-刀(Vi - h (xi)I L I Xi LI L I Xi L實(shí)際上，式3也可以用于半監(jiān)督分類(lèi)?；谑?, Z.-H. Zhou和M. Li ZhouL05b 提出了 COREG算法，該算法不要求充分冗余視圖，而是通過(guò)使用同一學(xué)習(xí)器的不同參數(shù)設(shè)置來(lái)生成兩個(gè)初始學(xué)習(xí) 器。具體來(lái)說(shuō)，他們使用了基于不同階Minkowski距離的兩個(gè)k近鄰回歸模型作為學(xué)習(xí)器，在協(xié)同訓(xùn)練過(guò)程中，兩個(gè)學(xué)習(xí)器根據(jù)式3挑選未標(biāo)記示例進(jìn)行標(biāo)記供對(duì)方進(jìn)行更新。最后的回歸預(yù)測(cè)通過(guò)對(duì)兩個(gè)k近鄰回歸模型預(yù)測(cè)值的

32、平均來(lái)完成。此后，他們ZhouL07又將COREG推廣到使用不同距離度量、不同近鄰個(gè)數(shù)以及其他回歸模型的情況。最近，U. Brefeld 等人BrefeldGSW06 把基于協(xié)同訓(xùn)練的半監(jiān)督回歸思想移植到正則化框架 下，通過(guò)最小化不同視圖下回歸模型對(duì)未標(biāo)記示例的預(yù)測(cè)差異來(lái)改善各視圖的回歸模型，也取得了 很好的效果。4. 協(xié)同訓(xùn)練理論分析在提出標(biāo)準(zhǔn)協(xié)同訓(xùn)練算法時(shí)，A. Blum和T. Mitchell BlumM98就對(duì)該技術(shù)能夠奏效的原因進(jìn)行了探討。令Xi和X2分別表示X的兩個(gè)視圖，則一個(gè)示例就可以表示為(X1, X2)，其中X1是x在Xi視圖中的 特征向量，X2則是其在X2視圖中的特征向量。

33、假設(shè)f是在示例空間X中的目標(biāo)函數(shù)，若x的標(biāo)記為l則應(yīng) 有f(x) = fi(xi) = f2(X2)= l。因此，A. Blum 和T. Mitchell 定義了所謂的"相容性”(compatibility)，即對(duì)X上的某個(gè)分布D, Ci和C2分別是定義在Xi和X2上的概念類(lèi)，如果D對(duì)滿(mǎn)足fi(x)斗2(X2)的示例(xi, X2) 指派零概率，則稱(chēng)目標(biāo)函數(shù) f= (fi, Ci XC2與D “相容”?；谙嗳菪愿拍?，A. Blum和T. Mitchell揭示了協(xié)同訓(xùn)練設(shè)置下的一個(gè)有趣的現(xiàn)象即使 0和C2是復(fù)雜度很高(VC-維很高)的大概念類(lèi)，與分布D相容的目標(biāo)概念集相對(duì)來(lái)說(shuō)仍然可能

34、會(huì)小得多、 簡(jiǎn)單得多。這樣，就有可能利用未標(biāo)記示例來(lái)輔助探查哪些目標(biāo)概念是相容的，而該信息有助于減 少學(xué)習(xí)算法所需的有標(biāo)記示例數(shù)。他們借助于圖2來(lái)直觀地展示這一現(xiàn)象。圖中二部圖左邊的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)了 Xi中的一個(gè)特征向量，右邊的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)了 X2中的一個(gè)特征向量，當(dāng)且僅當(dāng)示例(Xi, X2) 在分布D下以非零概率存在時(shí)，結(jié)點(diǎn) Xi和X2之間才存在邊，這些邊在圖中已經(jīng)用線條標(biāo)示出來(lái)，其中 用實(shí)邊標(biāo)示的邊對(duì)應(yīng)了已經(jīng)觀察到的未標(biāo)記示例。在這一表示下，C中與D相容的概念就對(duì)應(yīng)了在圖中連通成分之間沒(méi)有交叉線的劃分。顯然，屬于同一連通成分的示例必然屬于同樣的類(lèi)別，而未標(biāo) 記示例可以幫助學(xué)習(xí)算法了解圖中的連

35、通性(實(shí)際上也就是了解分布D),因此，通過(guò)利用未標(biāo)記示例，學(xué)習(xí)算法可以使用較少的有標(biāo)記示例達(dá)到原來(lái)需要更多的有標(biāo)記示例才能達(dá)到的效果。圖2 示例分布的二部圖表示 BlumM98進(jìn)一步，A. Blum和T. Mitchell BlumM98證明了一個(gè)定理：如果 C2在有分類(lèi)噪音時(shí)是 PAC可學(xué)習(xí)的，并且兩個(gè)視圖具有條件獨(dú)立性，那么給定一個(gè)初始的弱有效(weakly-useful )學(xué)習(xí)器h(xi)，協(xié)同訓(xùn)練算法只需使用未標(biāo)記示例就可以學(xué)得(Ci, C2)。這是一個(gè)非常強(qiáng)的結(jié)論，它意味著只要兩個(gè)視別數(shù)；如果學(xué)習(xí)器h無(wú)法判斷x的類(lèi)別，則表示為h(x)=上令|h|表示對(duì)h的復(fù)雜度的一個(gè)度量。Dasgu

36、pta 等人推導(dǎo)出這樣的結(jié)論： 在S上至少以1- 3的概率，對(duì)任何一對(duì) 九和山2來(lái)說(shuō)只要對(duì)所有的1<i wk都有Y(h1, h2, 3/2) >0 以及 b(h1, h2, 3/2) w(k -1)/k，就有(0) <(P(h1 mJ- £(|hj, 3/2)maxbj (0,0, 3/2)errork- 1 + k(P(h1=±)+ 伽,3/2)其中£(k, » =kln2 + ln2/ 39#1b (hi, h2, 3)=(P(h Mi h2 二 i,h mJ) + q (h1,h2, 3)(In 2)(闖 + 帆|)Y (h1,h

37、2, 3) '丿.2k+ l n 3i,hiY (hn h2, 5) = P (h! = i h?二 i,h P(h 為 h?二 i, h mJ)- 2 q (h“ h?, 3)值得注意的是，A. Blum和T. Mitchell的工作以及Dasgupta等人的工作都假定兩個(gè)視圖間的條 件獨(dú)立性假設(shè)成立，但如本章第三節(jié)所述，實(shí)際上該假設(shè)通常是不成立的。這就使得A. Blum和T.Mitchell的分析結(jié)論以及Dasgupta等人所推出的協(xié)同訓(xùn)練誤差上界實(shí)際上都只能是理想情況，未必 能夠適用于實(shí)際情況。M.-F. Balcan等人BalcanBY05 進(jìn)行了進(jìn)一步的研究，發(fā)現(xiàn)對(duì)協(xié)同訓(xùn)練技

38、術(shù)來(lái)說(shuō)，如果在每個(gè) 視圖上有合適的強(qiáng)學(xué)習(xí)器，則兩個(gè)視圖的條件獨(dú)立性假設(shè)甚至連弱獨(dú)立性假設(shè)Ab ney02都不是必需的，只要數(shù)據(jù)分布滿(mǎn)足比上述假設(shè)弱得多的“擴(kuò)張性”(expa nsion)假設(shè)，迭代式的協(xié)同訓(xùn)練算法就可以奏效?！皵U(kuò)張性”是如下定義的：令乂+表示X中的正區(qū)域，D+表示D在X+上的分布；對(duì)S1? X1和S2 ? X2,令S (i = 1,2)表示示例(X1, x2)有Xi Si；令P(S1 AS2)表示對(duì)S1和S2都確信的概率，P(S1 ® S2) 表示對(duì)S1和S2中至少一個(gè)確信的概率；令 Hi n Xi+表示h n Xi+ : h Hi ，其中Hi (i = 1,2)是假

39、設(shè)類(lèi)。若式5對(duì)任何S1? X1 +和S2? X2 +都成立，貝U稱(chēng)。+是&擴(kuò)張的(qexpa ndi ng )；若式5對(duì)任何0 ? H1 n X1 +和S2? H2 nX2 +都成立，則稱(chēng)D+對(duì)假設(shè)類(lèi)H1 XH2來(lái)說(shuō)是q擴(kuò)張的。P(S1 S2) >cmin (P(S1 AS2),P(S1 AS?)直觀地說(shuō)，在滿(mǎn)足擴(kuò)張性的數(shù)據(jù)分布上，對(duì)一個(gè)與視圖j (j =1,2)上的模型所對(duì)應(yīng)的較小的確信集(con fide nee set) Sj來(lái)說(shuō)，可以利用S所導(dǎo)出的另一個(gè)視圖3-j上的條件分布對(duì)該視圖上的正例進(jìn)行采樣，如果利用采樣所得的示例學(xué)得一個(gè)誤差小于的模型，那么在視圖3-j上的示例出

40、現(xiàn)在該模型所對(duì)應(yīng)的確信集S3-j中的概率將大于出現(xiàn)在 Sj中的概率。值得注意的是，實(shí)際使用的協(xié)同訓(xùn)練算法(例如第三節(jié)中描述的算法)實(shí)際上都是迭代式協(xié)同訓(xùn)練算法，而通常在每個(gè)視圖上使用的都是強(qiáng)學(xué)習(xí)器5，因此，M.-F. Balcan等人的工作在一定程度上解釋了為什么兩個(gè)視圖的條件獨(dú)立性雖然通常不成立，但協(xié)同訓(xùn)練算法仍能取得好的效果。最近，W. Wang和Z.-H. Zhou WangZ07又做了進(jìn)一步的分析。一方面，他們證明了只要兩個(gè)學(xué) 習(xí)器有較大的差異，就可以通過(guò)協(xié)同訓(xùn)練來(lái)利用未標(biāo)記示例提高學(xué)習(xí)性能。這不僅解釋了為什么在 兩個(gè)視圖的條件獨(dú)立性不成立時(shí)協(xié)同訓(xùn)練算法可以有好的效果，還解釋了那些根本

41、不利用兩個(gè)視圖 的算法，例如GoldmanZ00ZhouL05b等奏效的原因。另一方面，從以往的理論分析來(lái)看，使用協(xié) 同訓(xùn)練總可以使得泛化能力提高，甚至可以將弱學(xué)習(xí)器提升到任意精度；然而，在實(shí)際使用協(xié)同訓(xùn) 練時(shí)往往出現(xiàn)這樣的情況，即在若干輪協(xié)同訓(xùn)練之后如果再繼續(xù)進(jìn)行下去，不僅不能改善學(xué)習(xí)結(jié)果,有時(shí)甚至?xí)?dǎo)致性能下降。W. Wang和Z.-H. Zhou WangZ07對(duì)此問(wèn)題也給出了理論解釋。5. 協(xié)同訓(xùn)練的應(yīng)用自然語(yǔ)言處理是協(xié)同訓(xùn)練技術(shù)應(yīng)用得最為廣泛的一個(gè)領(lǐng)域。實(shí)際上，該領(lǐng)域的研究者在協(xié)同訓(xùn) 練技術(shù)出現(xiàn)之前就已經(jīng)意識(shí)到可以利用問(wèn)題本身具有的不同屬性集來(lái)建立模型。例如，D. YarowskyY

42、arowsky95在研究詞義消歧時(shí)，通過(guò)同時(shí)使用詞的局部上下文以及詞在文檔其他部分出現(xiàn)時(shí)的含 義這兩部分信息， 有效減少了對(duì)人工標(biāo)注數(shù)據(jù)的需求量；E. Riloff和R. Jones RiloffJ99在對(duì)名詞短語(yǔ)進(jìn)行地理位置分類(lèi)時(shí)，同時(shí)考慮了名詞短語(yǔ)本身及其出現(xiàn)的上下文；M. Colli ns 和Y. Sin gerCollinsS99進(jìn)行名實(shí)體識(shí)別時(shí)，也同時(shí)使用了名實(shí)體的拼寫(xiě)信息及名實(shí)體出現(xiàn)的上下文信息。A. Blum和T. Mitchell提出標(biāo)準(zhǔn)協(xié)同訓(xùn)練算法后，協(xié)同訓(xùn)練技術(shù)很快就在自然語(yǔ)言處理領(lǐng)域受到了重視。D. Pierce和C. Cardie PierceC01將協(xié)同訓(xùn)練算法用于名

43、詞短語(yǔ)識(shí)別，他們把當(dāng)前詞及在文檔中出現(xiàn)在該詞前的k個(gè)詞作為一個(gè)視圖，把該詞及出現(xiàn)在其后的另外k個(gè)詞作為另外一個(gè)視圖，然后在兩個(gè)視圖上利用協(xié)同訓(xùn)練算法進(jìn)行訓(xùn)練。為了適應(yīng)多類(lèi)分類(lèi)問(wèn)題，他們還對(duì)標(biāo)準(zhǔn)協(xié)同訓(xùn)練算 法進(jìn)行了改進(jìn)。他們的研究結(jié)果表明，在使用協(xié)同訓(xùn)練技術(shù)利用未標(biāo)記示例后，識(shí)別錯(cuò)誤率比僅使 用有標(biāo)記示例時(shí)下降了36%o A Sarkar Sarkar01將句法分析器分解為兩個(gè)相關(guān)模型，其中一個(gè)負(fù)責(zé)基于上下文挑選出合適的分析樹(shù)(parsing tree),另一個(gè)則負(fù)責(zé)計(jì)算分析樹(shù)間的關(guān)系并且給出最優(yōu)的分析結(jié)果。在學(xué)習(xí)過(guò)程中，兩個(gè)模型通過(guò)利用未標(biāo)記示例進(jìn)行協(xié)同訓(xùn)練，每個(gè)模型都利用對(duì)方提供 的信息來(lái)幫

44、助自己排除部分句法分析中的不確定因素。其結(jié)果表明，通過(guò)協(xié)同訓(xùn)練學(xué)得的句法分析 器在精度(precision)和召回率(recall)方面都有顯著提高。 M. Steedman等人SteedmanOSCHH03 也提出了一種基于協(xié)同訓(xùn)練的統(tǒng)計(jì)句法分析方法，與A. Sarkar的方法不同，他們使用了兩個(gè)不同的但功能完整的統(tǒng)計(jì)句法分析器進(jìn)行協(xié)同訓(xùn)練。在訓(xùn)練過(guò)程中，每個(gè)分析器根據(jù)自己對(duì)未分析句子的雖然A. Blum和T. Mitchell BlumT98的理論結(jié)果表明弱學(xué)習(xí)器就夠用了，但他們?cè)趯?shí)驗(yàn)中仍然使用了強(qiáng)學(xué)習(xí)器。 一般來(lái)說(shuō)，在理論分析時(shí)為了便于討論算法的能力通常使用弱學(xué)習(xí)器；而在實(shí)際使用時(shí)為了得

45、到更好的性能通常使 用強(qiáng)學(xué)習(xí)器。分析結(jié)果利用某個(gè)函數(shù)進(jìn)行打分，作為對(duì)該句子分析的置信度，然后把得分最高的若干個(gè)示例提交 給對(duì)方使用。他們的研究結(jié)果也證實(shí)，使用協(xié)同訓(xùn)練技術(shù)可以顯著提高句法分析器的性能。 R. Hwa 等人 HwaOSS03 提出了一種基于協(xié)同訓(xùn)練的主動(dòng)半監(jiān)督句法分析方法，在學(xué)習(xí)過(guò)程中，一個(gè)學(xué)習(xí) 器挑選并標(biāo)記自己最確定的示例給另一個(gè)學(xué)習(xí)器，而另一個(gè)學(xué)習(xí)器則挑選自己最不確定的示例請(qǐng)用 戶(hù)標(biāo)記后再提交給該學(xué)習(xí)器用于模型更新。他們的研究結(jié)果表明該方法可以減少大約一半的人工標(biāo) 記量。協(xié)同訓(xùn)練技術(shù)的另一個(gè)重要應(yīng)用領(lǐng)域是基于內(nèi)容的圖像檢索(CBIR )。CBIR要求檢索系統(tǒng)能夠根據(jù)用戶(hù)提供的

46、查詢(xún)圖像自動(dòng)地從圖像庫(kù)中檢索出相似圖像。在檢索過(guò)程中通常會(huì)利用相關(guān)反饋(releva nee feedback)來(lái)提高性能。具體來(lái)說(shuō)，系統(tǒng)將檢索結(jié)果提供給用戶(hù)后，如果用戶(hù)不滿(mǎn)意，就 可以從中選擇一些圖像并標(biāo)示出其是否是期望的圖像，然后系統(tǒng)根據(jù)這些信息再重新進(jìn)行檢索。該 過(guò)程可能會(huì)反復(fù)進(jìn)行多輪，直到用戶(hù)滿(mǎn)意或喪失信心為止。值得注意的是，在CBIR 過(guò)程中，即使將用戶(hù)在相關(guān)反饋過(guò)程中提供的信息考慮進(jìn)來(lái)，有標(biāo)記圖像的數(shù)目仍然是比較少的，因?yàn)楹苌儆杏?戶(hù)會(huì)愿意花大量的時(shí)間來(lái)提供反饋；但圖像庫(kù)中卻通常存在大量的圖像，這些圖像都是未標(biāo)記的， 因?yàn)樵诓樵?xún)之前無(wú)法事先判斷它們是否與查詢(xún)相關(guān)。 顯然， CBIR

47、 任務(wù)是典型的有標(biāo)記示例很少、 未 標(biāo)記示例非常多的任務(wù)。 因此， 基于內(nèi)容的圖像檢索是利用未標(biāo)記示例的學(xué)習(xí)技術(shù)的很好的試驗(yàn)場(chǎng)， 另一方面，通過(guò)引入這些學(xué)習(xí)技術(shù)可能有助于突破 CBIR 的技術(shù)瓶頸 Zhou06 。Zhou等人ZhouCJ04ZhouCD06 將協(xié)同訓(xùn)練引入 CBIR，提出了基于協(xié)同訓(xùn)練的主動(dòng)半監(jiān)督 相關(guān)反饋方法。他們?cè)诿恳惠喯嚓P(guān)反饋后，利用現(xiàn)有的有標(biāo)記示例訓(xùn)練兩個(gè)基于距離度量的簡(jiǎn)單學(xué) 習(xí)器，然后兩個(gè)學(xué)習(xí)器分別對(duì)圖像庫(kù)中的圖像進(jìn)行預(yù)測(cè)從而產(chǎn)生兩個(gè)排序，排在最前面的是置信度 最高的相關(guān)圖像，排在最后面的是置信度最高的不相關(guān)圖像，而排在中間的則是置信度比較低的圖 像?；谶@兩個(gè)排序

48、， 兩個(gè)學(xué)習(xí)器分別將自己最確定的相關(guān)圖像和最確定的不相關(guān)圖像傳遞給對(duì)方， 然后兩個(gè)學(xué)習(xí)器利用這些新的有標(biāo)記圖像進(jìn)行更新。更新后的學(xué)習(xí)器再對(duì)圖像庫(kù)中的圖像進(jìn)行預(yù)測(cè) 從而產(chǎn)生兩個(gè)排序，通過(guò)結(jié)合這兩個(gè)排序就得到一個(gè)總排序。基于總排序，系統(tǒng)把排在最前面的若 干幅圖像作為檢索結(jié)果反饋給用戶(hù)，而把排在中間的若干幅圖像放入反饋池(feedback pool )中，供用戶(hù)在進(jìn)行下一輪相關(guān)反饋時(shí)進(jìn)行標(biāo)示。在 COREL 圖像庫(kù)上的實(shí)驗(yàn)表明，該技術(shù)通過(guò)在協(xié)同訓(xùn)練 設(shè)置下結(jié)合半監(jiān)督學(xué)習(xí)和主動(dòng)學(xué)習(xí)，可以有效地利用圖像庫(kù)中的圖像來(lái)提高檢索性能。6. 結(jié)束語(yǔ)從上世紀(jì) 90 年代末標(biāo)準(zhǔn)協(xié)同訓(xùn)練算法被提出開(kāi)始， 很多研究者對(duì)

49、協(xié)同訓(xùn)練技術(shù)進(jìn)行了研究， 不 僅提出了很多學(xué)習(xí)方式不同、限制條件強(qiáng)弱各異的算法，對(duì)協(xié)同訓(xùn)練的理論分析和應(yīng)用研究也取得 了不少進(jìn)展，使得協(xié)同訓(xùn)練成為半監(jiān)督學(xué)習(xí)中最重要的風(fēng)范之一。但至少在目前，針對(duì)協(xié)同訓(xùn)練風(fēng)范仍然存在很多值得進(jìn)一步研究的問(wèn)題：由于協(xié)同訓(xùn)練是一種半監(jiān)督學(xué)習(xí)技術(shù)，因此半監(jiān)督學(xué)習(xí)領(lǐng)域存在的主要問(wèn)題在協(xié)同訓(xùn)練風(fēng)范中 都存在。例如，在通過(guò)半監(jiān)督學(xué)習(xí)利用未標(biāo)記示例后，有時(shí)不僅不能提高泛化能力，反而會(huì)使得性 能下降。一般認(rèn)為，在模型假設(shè)不符合真實(shí)情況CohenCSCH04CozmanC02或者未標(biāo)記示例的分布與有標(biāo)記示例的分布有較大差異TianYXS04時(shí)，進(jìn)行半監(jiān)督學(xué)習(xí)有可能導(dǎo)致性能下降。另

50、一方面，隨著訓(xùn)練不斷進(jìn)行，自動(dòng)標(biāo)記的示例中的噪音會(huì)不斷積累，其負(fù)作用會(huì)越來(lái)越大。禾U用數(shù)據(jù)審 計(jì)(data editing)技術(shù)來(lái)發(fā)現(xiàn)和處理這些噪音數(shù)據(jù)，也許是一條可能的途徑，M. Li和Z.-H. Zhou LiZ04對(duì)此進(jìn)行了初步的嘗試?？偟膩?lái)說(shuō)，找到未標(biāo)記示例導(dǎo)致性能下降的真正原因，有助于更好地發(fā)揮 半監(jiān)督學(xué)習(xí)技術(shù)的效用。目前雖然有了很多協(xié)同訓(xùn)練算法，但這些算法都有自身的弱點(diǎn)。如何設(shè)計(jì)出更強(qiáng)有力的協(xié)同訓(xùn) 練算法，一直是該領(lǐng)域的重要研究?jī)?nèi)容。現(xiàn)有對(duì)協(xié)同訓(xùn)練的理論分析雖然揭示了協(xié)同訓(xùn)練的一些內(nèi) 在機(jī)理，但是很多分析都建立在一些較強(qiáng)的假設(shè)條件上?，F(xiàn)在已經(jīng)知道，在這些較強(qiáng)的假設(shè)條件不 滿(mǎn)足的情況

51、下，協(xié)同訓(xùn)練技術(shù)仍然能夠取得較好的效果。因此，在更一般、更接近真實(shí)情況的條件 下對(duì)協(xié)同訓(xùn)練進(jìn)行理論分析，是一個(gè)需要努力的方向。將協(xié)同訓(xùn)練技術(shù)投入到更多的應(yīng)用中去，基 于協(xié)同訓(xùn)練技術(shù)研制出實(shí)用系統(tǒng)，也是該領(lǐng)域重要的研究?jī)?nèi)容。值得注意的是，A. Blum和T. Mitchell BlumM98利用數(shù)據(jù)不同視圖的思想受到了機(jī)器學(xué)習(xí)界的很大重視，為"多視圖學(xué)習(xí)”(multi-view learning )這一新的研究領(lǐng)域奠定了基礎(chǔ)，這也使得協(xié)同訓(xùn)練風(fēng)范的影響超越了半監(jiān)督學(xué)習(xí)領(lǐng)域。例如，I. Muslea等人MusleaMK00MusleaMK02 將協(xié)同訓(xùn)練的思想引入主動(dòng)學(xué)習(xí)，他們?cè)趦蓚€(gè)視圖

52、上分別建立分類(lèi)器，然后選擇兩個(gè)分類(lèi)器預(yù)測(cè)差異最大 的示例進(jìn)行查詢(xún)。對(duì)多視圖學(xué)習(xí)的算法、理論、應(yīng)用進(jìn)行研究，是今后的重要研究?jī)?nèi)容。到目前為止，對(duì)協(xié)同訓(xùn)練的研究主要是在機(jī)器學(xué)習(xí)算法這一層面開(kāi)展的雖然本章談到了學(xué)習(xí)算法、理論分析、實(shí)際應(yīng)用等方面，但其實(shí)機(jī)器學(xué)習(xí)的核心研究?jī)?nèi)容就是“算法”。這里的“算法”是廣義的，不僅包含了學(xué)習(xí)算法本身，還包含了對(duì)算法性質(zhì)的理論分析或?qū)λ惴ㄔO(shè)計(jì)的理論討論，以及對(duì)算法 的應(yīng)用等。實(shí)際上，計(jì)算機(jī)科學(xué)大多數(shù)領(lǐng)域的核心研究?jī)?nèi)容都是“算法”。,但筆者認(rèn)為，協(xié)同訓(xùn)練除了在機(jī)器學(xué)習(xí)算法方面具有重要性，深入研究協(xié)同訓(xùn)練機(jī)制對(duì)理解和模仿人類(lèi)的學(xué)習(xí)行為也有 重要的意義。例如，人類(lèi)在對(duì)外界事

53、物進(jìn)行學(xué)習(xí)時(shí)，不同感官對(duì)同一事物的感知能力通常是不同的， 但在學(xué)習(xí)之后，不同感官對(duì)此類(lèi)事物的感知能力往往都會(huì)得到提高。如果把同一事物在不同感官上 的反映看作同一示例在不同視圖下的特征向量，則學(xué)習(xí)之后感知能力的提高有可能是因?yàn)椴煌晥D 下的學(xué)習(xí)器互相提供了信息。再如，人類(lèi)在集體環(huán)境下進(jìn)行學(xué)習(xí)時(shí)，如果把每個(gè)人看作一個(gè)學(xué)習(xí)器， 則即使對(duì)同樣的事物，不同的人學(xué)得的結(jié)果也可能是顯著不同的，而人們可以通過(guò)互相學(xué)習(xí)來(lái)提高 自己的能力，這恰恰與協(xié)同訓(xùn)練非常相似。筆者認(rèn)為，通過(guò)借鑒人類(lèi)學(xué)習(xí)行為，有可能產(chǎn)生更強(qiáng)有 力的協(xié)同訓(xùn)練技術(shù)，而機(jī)器學(xué)習(xí)中對(duì)協(xié)同訓(xùn)練技術(shù)的研究，也許能夠?yàn)檎J(rèn)知科學(xué)中對(duì)學(xué)習(xí)的研究提 供啟示和實(shí)驗(yàn)

54、手段。AbeM98 N. Abe, H. Mamitsuka. Query learning strategies using boosting and bagging. In: Proceedings of the 15th International Conference on Machine Learning (ICML , Madison', W98I,) 1998, 1-9.Abney02 S. Abney. Bootstrapping. In: Proceedings of the 40th Annual Meeting of the Association for Com

55、putational Linguistics (ACL , Ph'ila0d2e)lphia, PA, 2002, 360-367.AngluinL88 D. Angluin, P. Laird. Learning from noisy examples. Machine Learning, 1988, 2(4): 343-370. BalcanBY05 M.-F. Balcan, A. Blum, K. Yang. Co-training and expansion: Towards bridging theory and practice. In: L. K. Saul, Y .

56、Weiss, L. Bottou, eds. Advances in Neural Information Processing Systems 17, Cambridge, MA: MIT Press, 2005, 89-96.BelkinN04 M. Belkin, P. Niyogi. Semi-supervised learning on Riemannian manifolds. Machine Learning, 2004, 56(1-3): 209-239.BelkinNS05 M. Belkin, P. Niyogi, V . Sindwani. On manifold reg

57、ularization. In: Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics (AISTATS, Savannah Hotel,'B0a5rb)ados,2005, 17-24.BlumC01 A. Blum, S. Chawla. Learning from labeled and unlabeled data using graph mincuts. In:Proceedings of the 18th International Conference on Machine Learning (ICML , San Franci'sco0,1)CA, 2001, 19-26.BlumM98 A. Blum, T. Mitchell. Combining labeled and unlabeled data with co-training. In: Proceedings of the 11th Annual Conference on Computational Learning Theory (COLT , Wis