周志華-機(jī)器學(xué)習(xí)-西瓜書-全書16章-ch13課件

周志華-機(jī)器學(xué)習(xí)-西瓜書-全書16章--ch13課件第十三章：半監(jiān)督學(xué)習(xí)第十三章：半監(jiān)督學(xué)習(xí)背景（半監(jiān)督學(xué)習(xí)）隔壁老王品瓜師吃背景（半監(jiān)督學(xué)習(xí)）隔壁老王品瓜師吃背景（半監(jiān)督學(xué)習(xí)）品瓜師吃模型有標(biāo)記樣本無標(biāo)記樣本直推學(xué)習(xí)（純）半監(jiān)督學(xué)習(xí)待測數(shù)據(jù)背景（半監(jiān)督學(xué)習(xí)）品瓜師吃模型有標(biāo)記樣本無標(biāo)記樣本直推學(xué)習(xí)（背景（主動學(xué)習(xí)）品瓜師吃背景（主動學(xué)習(xí)）品瓜師吃背景（主動學(xué)習(xí)）品瓜師吃主動學(xué)習(xí)待測數(shù)據(jù)模型有標(biāo)記樣本無標(biāo)記樣本標(biāo)注者背景（主動學(xué)習(xí)）品瓜師吃主動學(xué)習(xí)待測數(shù)據(jù)模型有標(biāo)記樣本無標(biāo)記未標(biāo)記樣本的效用未標(biāo)記樣本的效用未標(biāo)記樣本的假設(shè)要利用未標(biāo)記樣本，必然要做一些將未標(biāo)記樣本所揭示的數(shù)據(jù)分布信息與類別標(biāo)記相聯(lián)系的假設(shè)，其中有兩種常見的假設(shè)。聚類假設(shè)（clusteringassumption）：

假設(shè)數(shù)據(jù)存在簇結(jié)構(gòu)，同一簇的樣本屬于同一類別。流形假設(shè)（manifoldassumption）：

假設(shè)數(shù)據(jù)分布在一個流形結(jié)構(gòu)上，鄰近的樣本具有相似的輸出值。流形假設(shè)可看做聚類假設(shè)的推廣未標(biāo)記樣本的假設(shè)流形假設(shè)可看做聚類假設(shè)的推廣大綱未標(biāo)記樣本生成式方法半監(jiān)督SVM圖半監(jiān)督學(xué)習(xí)基于分歧的方法半監(jiān)督聚類大綱未標(biāo)記樣本生成式方法假設(shè)樣本由這個假設(shè)意味著混合成分高斯混合模型生成,且每個類別對應(yīng)一個高斯混合成分：

其中,

生成式方法假設(shè)樣本由這個假設(shè)意味著混合成分高斯混合模型生成生成式方法由最大化后驗概率可知：生成式方法由最大化后驗概率可知：生成式方法假設(shè)樣本獨立同分布，且由同一個高斯混合模型生成，則對數(shù)似然函數(shù)是：生成式方法假設(shè)樣本獨立同分布，且由同一個高斯混合模型生成，則生成式方法高斯混合的參數(shù)估計可以采用EM算法求解，迭代更新式如下：E步：根據(jù)當(dāng)前模型參數(shù)計算未標(biāo)記樣本屬于各高斯混合成分的概率。生成式方法高斯混合的參數(shù)估計可以采用EM算法求解，迭代更新式生成式方法M步：基于更新模型參數(shù)生成式方法M步：基于更新模型參數(shù)生成式方法將上述過程中的高斯混合模型換成混合專家模型，樸素貝葉斯模型等即可推導(dǎo)出其他的生成式半監(jiān)督學(xué)習(xí)算法。此類方法簡單、易于實現(xiàn),在有標(biāo)記數(shù)據(jù)極少的情形下往往比其他方法性能更好。然而,此類方法有一個關(guān)鍵:模型假設(shè)必須準(zhǔn)確,即假設(shè)的生成式模型必須與真實數(shù)據(jù)分布吻合;否則利用未標(biāo)記數(shù)據(jù)反而會顯著降低泛化性能。生成式方法將上述過程中的高斯混合模型換成混合專家模型，樸素貝大綱未標(biāo)記樣本生成式方法半監(jiān)督SVM圖半監(jiān)督學(xué)習(xí)基于分歧的方法半監(jiān)督聚類大綱未標(biāo)記樣本半監(jiān)督SVM半監(jiān)督SVM半監(jiān)督SVM半監(jiān)督支持向量機(jī)中最著名的是TSVM(TransductiveSupportVectorMachine)半監(jiān)督SVM半監(jiān)督支持向量機(jī)中最著名的是TSVM(Trans半監(jiān)督SVMTSVM采用局部搜索來迭代地尋找近似解.無標(biāo)記樣本有標(biāo)記樣本SVM0偽標(biāo)記SVM1訓(xùn)練訓(xùn)練訓(xùn)練標(biāo)注半監(jiān)督SVMTSVM采用局部搜索來迭代地尋找近似解.無標(biāo)記樣半監(jiān)督SVMSVM1無標(biāo)記樣本搜索指派可能出錯的樣本交換樣本標(biāo)記有標(biāo)記樣本訓(xùn)練訓(xùn)練SVM2半監(jiān)督SVMSVM1無標(biāo)記樣本搜索指派可能出錯的樣本交換樣本半監(jiān)督SVM未標(biāo)記樣本的偽標(biāo)記不準(zhǔn)確半監(jiān)督SVM未標(biāo)記樣本的偽標(biāo)記不準(zhǔn)確半監(jiān)督SVM未標(biāo)記樣本進(jìn)行標(biāo)記指派及調(diào)整的過程中,有可能出現(xiàn)類別不平衡問題,即某類的樣本遠(yuǎn)多于另一類。為了減輕類別不平衡性所造成的不利影響,可對算法稍加改進(jìn):將優(yōu)化目標(biāo)中的項拆分為與

兩項,并在初始化時令：半監(jiān)督SVM未標(biāo)記樣本進(jìn)行標(biāo)記指派及調(diào)整的過程中,有可能出半監(jiān)督SVM顯然,搜尋標(biāo)記指派可能出錯的每一對未標(biāo)記樣本進(jìn)行調(diào)整,仍是一個涉及巨大計算開銷的大規(guī)模優(yōu)化問題。因此,半監(jiān)督SVM研究的一個重點是如何設(shè)計出高效的優(yōu)化求解策略。例如基于圖核(graphkernel)函數(shù)梯度下降的LaplacianSVM[ChapelleandZien,2005]、基于標(biāo)記均值估計的meanS3VM[Lietal.,2009]等.半監(jiān)督SVM顯然,搜尋標(biāo)記指派可能出錯的每一對未標(biāo)記樣本進(jìn)大綱未標(biāo)記樣本生成式方法半監(jiān)督SVM圖半監(jiān)督學(xué)習(xí)基于分歧的方法半監(jiān)督聚類大綱未標(biāo)記樣本圖半監(jiān)督學(xué)習(xí)給定一個數(shù)據(jù)集,我們可將其映射為一個圖,數(shù)據(jù)集中每個樣本對應(yīng)于圖中一個結(jié)點,若兩個樣本之間的相似度很高(或相關(guān)性很強),則對應(yīng)的結(jié)點之間存在一條邊,邊的“強度”(strength)正比于樣本之間的相似度(或相關(guān)性)。我們可將有標(biāo)記樣本所對應(yīng)的結(jié)點想象為染過色,而未標(biāo)記樣本所對應(yīng)的結(jié)點則尚未染色.于是,半監(jiān)督學(xué)習(xí)就對應(yīng)于“顏色”在圖上擴(kuò)散或傳播的過程。由于一個圖對應(yīng)了一個矩陣,這就使得我們能基于矩陣運算來進(jìn)行半監(jiān)督學(xué)習(xí)算法的推導(dǎo)與分析。圖半監(jiān)督學(xué)習(xí)給定一個數(shù)據(jù)集,我們可將其映射為一個圖,數(shù)據(jù)圖半監(jiān)督學(xué)習(xí)我們先基于構(gòu)建一個圖，其中結(jié)點集邊集E可表示為一個親和矩陣(affinitymatrix),?；诟咚购瘮?shù)定義為:圖半監(jiān)督學(xué)習(xí)我們先基于構(gòu)建一個圖圖半監(jiān)督學(xué)習(xí)假定從圖將學(xué)得一個實值函數(shù)。直觀上講相似的樣本應(yīng)具有相似的標(biāo)記,即得到最優(yōu)結(jié)果于是可定義關(guān)于f的“能量函數(shù)”(energyfunction)[Zhuetal.,2003]:

圖半監(jiān)督學(xué)習(xí)假定從圖將學(xué)得一個實值函圖半監(jiān)督學(xué)習(xí)采用分塊矩陣表示方式:由可得:圖半監(jiān)督學(xué)習(xí)采用分塊矩陣表示方式:圖半監(jiān)督學(xué)習(xí)圖半監(jiān)督學(xué)習(xí)圖半監(jiān)督學(xué)習(xí)上面描述的是一個針對二分類問題的“單步式”標(biāo)記傳播(labelpropagation)方法,下面我們來看一個適用于多分類問題的“迭代式”標(biāo)記傳播方法[Zhouetal.,2004].仍基于構(gòu)建一個圖其中結(jié)點集定義一個的非負(fù)標(biāo)記矩陣，其第i行元素為示例

的標(biāo)記向量,相應(yīng)的分類規(guī)則為:將F初始化為：圖半監(jiān)督學(xué)習(xí)上面描述的是一個針對二分類問題的“單步式”標(biāo)記傳圖半監(jiān)督學(xué)習(xí)基于W構(gòu)造一個標(biāo)記傳播矩陣，其中,于是有迭代計算式:基于迭代至收斂可得:圖半監(jiān)督學(xué)習(xí)基于W構(gòu)造一個標(biāo)記傳播矩陣圖半監(jiān)督學(xué)習(xí)事實上,算法對應(yīng)于正則化框架[Zhouetal.,2004]:當(dāng)時,最優(yōu)解恰為迭代算法的收斂解。圖半監(jiān)督學(xué)習(xí)事實上,算法對應(yīng)于正則化框架[Zhouet圖半監(jiān)督學(xué)習(xí)圖半監(jiān)督學(xué)習(xí)圖半監(jiān)督學(xué)習(xí)圖半監(jiān)督學(xué)習(xí)方法在概念上相當(dāng)清晰,且易于通過對所涉矩陣運算的分析來探索算法性質(zhì)。但此類算法的缺陷也相當(dāng)明顯.首先是在存儲開銷高。另一方面,由于構(gòu)圖過程僅能考慮訓(xùn)練樣本集,難以判知新樣本在圖中的位置,因此,在接收到新樣本時,或是將其加入原數(shù)據(jù)集對圖進(jìn)行重構(gòu)并重新進(jìn)行標(biāo)記傳播,或是需引入額外的預(yù)測機(jī)制。圖半監(jiān)督學(xué)習(xí)圖半監(jiān)督學(xué)習(xí)方法在概念上相當(dāng)清晰,且易于通過對大綱未標(biāo)記樣本生成式方法半監(jiān)督SVM圖半監(jiān)督學(xué)習(xí)基于分歧的方法半監(jiān)督聚類大綱未標(biāo)記樣本基于分歧的方法基于分歧的方法(disagreement-basedmethods)使用多學(xué)習(xí)器,而學(xué)disagreement亦稱diversity習(xí)器之間的“分歧”(disagreement)對未標(biāo)記數(shù)據(jù)的利用至關(guān)重要。協(xié)同訓(xùn)練(co-training)[BlumandMitchell,1998]是基于分歧的方法的重要代表,它最初是針對“多視圖”(multi-view)數(shù)據(jù)設(shè)計的,因此也被看作“多視圖學(xué)習(xí)”(multi-viewlearning)的代表.基于分歧的方法基于分歧的方法(disagreement-ba基于分歧的方法網(wǎng)頁分類任務(wù)中的雙視圖圖片視圖文字視圖基于分歧的方法網(wǎng)頁分類任務(wù)中的雙視圖圖片視圖文字視圖基于分歧的方法協(xié)同訓(xùn)練正是很好地利用了多視圖的“相容互補性”.假設(shè)數(shù)據(jù)擁有兩個“充分”(sufficient)且“條件獨立”視圖。視圖1視圖2模型1模型2最確信樣本最確信樣本基于分歧的方法協(xié)同訓(xùn)練正是很好地利用了多視圖的“相容互補性”基于分歧的方法基于分歧的方法基于分歧的方法協(xié)同訓(xùn)練過程雖簡單,但令人驚訝的是,理論證明顯示出,若兩個視圖充分且條件獨立,則可利用未標(biāo)記樣本通過協(xié)同訓(xùn)練將弱分類器的泛化性能提升到任意高[BlumandMitchell,1998].不過,視圖的條件獨立性在現(xiàn)實任務(wù)中通常很難滿足,不會是條件獨立的因此性能提升幅度不會那么大,但研究表明,即使在更弱的條件下,協(xié)同訓(xùn)練仍可有效地提升弱分類器的性能[周志華,2013].基于分歧的方法協(xié)同訓(xùn)練過程雖簡單,但令人驚訝的是,理論證基于分歧的方法協(xié)同訓(xùn)練算法本身是為多視圖數(shù)據(jù)而設(shè)計的,性集合的常見數(shù)據(jù)但此后出現(xiàn)了一些能在單視圖數(shù)據(jù)上使用的變體算法。

它們或是使用不同的學(xué)習(xí)算法[GoldmanandZhou,2000]、或使用不同的數(shù)據(jù)采樣[ZhouandLi,2005b]、甚至使用不同的參數(shù)設(shè)置[ZhouandLi,2005a]來產(chǎn)生不同的學(xué)習(xí)器,也能有效地利用未標(biāo)記數(shù)據(jù)來提升性能。后續(xù)理論研究發(fā)現(xiàn),此類算法事實上無需數(shù)據(jù)擁有多視圖,僅需弱學(xué)習(xí)器之間具有顯著的分歧(或差異),即可通過相互提供偽標(biāo)記樣本的方式來提高泛化性能[周志華,2013]?；诜制绲姆椒▍f(xié)同訓(xùn)練算法本身是為多視圖數(shù)據(jù)而設(shè)計的,性集合基于分歧的方法基于分歧的方法只需采用合適的基學(xué)習(xí)器,就較少受到模型假設(shè)、損失函數(shù)非凸性和數(shù)據(jù)規(guī)模問題的影響,學(xué)習(xí)方法簡單有效、理論基礎(chǔ)相對堅實、適用范圍較為廣泛。為了使用此類方法,需能生成具有顯著分歧、性能尚可的多個學(xué)習(xí)器,但當(dāng)有標(biāo)記樣本很少、尤其是數(shù)據(jù)不具有多視圖時,要做到這一點并不容易?；诜制绲姆椒ɑ诜制绲姆椒ㄖ恍璨捎煤线m的基學(xué)習(xí)器,就較少大綱未標(biāo)記樣本生成式方法半監(jiān)督SVM圖半監(jiān)督學(xué)習(xí)基于分歧的方法半監(jiān)督聚類大綱未標(biāo)記樣本半監(jiān)督聚類聚類是一種典型的無監(jiān)督學(xué)習(xí)任務(wù),然而在現(xiàn)實聚類任務(wù)中我們往往能獲得一些額外的監(jiān)督信息,于是可通過“半監(jiān)督聚類”(semi-supervisedclustering)來利用監(jiān)督信息以獲得更好的聚類效果.聚類任務(wù)中獲得的監(jiān)督信息大致有兩種類型：第一種類型是“必連”(must-link)與“勿連”(cannot-link)約束，前者是指樣本必屬于同一個簇,后者則是指樣本必不屬于同一個簇；第二種類型的監(jiān)督信息則是少量的有標(biāo)記樣本.半監(jiān)督聚類聚類是一種典型的無監(jiān)督學(xué)習(xí)任務(wù),然而在現(xiàn)實聚類任半監(jiān)督聚類約束k均值(Constrainedk-means)算法[Wagstaffetal.,2001]是利用第一類監(jiān)督信息的代表。該算法是k均值算法的擴(kuò)展,它在聚類過程中要確保“必連”關(guān)系集合與“勿連”關(guān)系集合中的約束得以滿足,否則將返回錯誤提示。半監(jiān)督聚類約束k均值(Constrainedk-means半監(jiān)督聚類不沖突，選擇最近的簇沖突，嘗試次近的簇半監(jiān)督聚類不沖突，選擇最近的簇沖突，嘗試次近的簇半監(jiān)督聚類半監(jiān)督聚類半監(jiān)督聚類第二種監(jiān)督信息是少量有標(biāo)記樣本。即假設(shè)少量有標(biāo)記樣本屬于k個聚類簇。這樣的監(jiān)督信息利用起來很容易:直接將它們作為“種子”,用它們初始化k均值算法的k個聚類中心,并且在聚類簇迭代更新過程中不改變種子樣本的簇隸屬關(guān)系.這樣就得到了約束種子k均值(ConstrainedSeedk-means)算法[Basuetal.,2002]。半監(jiān)督聚類第二種監(jiān)督信息是少量有標(biāo)記樣本。即假設(shè)少量有標(biāo)記樣半監(jiān)督聚類半監(jiān)督聚類半監(jiān)督聚類半監(jiān)督聚類閱讀材料半監(jiān)督學(xué)習(xí)的研究一般認(rèn)為始于[ShahshahaniandLandgrebe,1994],該領(lǐng)域在上世紀(jì)末、本世紀(jì)初蓬勃發(fā)展.國際機(jī)器學(xué)習(xí)大會(ICML)從2008年開始評選“十年最佳論文”,在短短6年中,半監(jiān)督學(xué)習(xí)四大范型(paradim)中基于分歧的方法、半監(jiān)督SVM、圖半監(jiān)督學(xué)習(xí)的代表性工作先后于2008年[BlumandMitchell,1998]、2009年[Joachims,1999]、2013年[Zhuetal.,2003]獲獎.半監(jiān)督學(xué)習(xí)在利用未標(biāo)記樣本后并非必然提升泛化性能,在有些情形下甚至?xí)?dǎo)致性能下降.對生成式方法,其成因被認(rèn)為是模型假設(shè)不準(zhǔn)確[CozmanandCohen,2002],因此需依賴充分可靠的領(lǐng)域知識來設(shè)計模型.對半監(jiān)督SVM,其成因被認(rèn)為是訓(xùn)練數(shù)據(jù)中存在多個“低密度劃分”,而學(xué)習(xí)算法有可能做出不利的選擇;S4VM[LiandZhou,2015]通過優(yōu)化最壞情形性能來綜“安全”指利用未標(biāo)記數(shù)合利用多個低密度劃分,提升了此類技術(shù)的安全性.據(jù)之后,確保泛化性能至少不差于僅利用有標(biāo)記數(shù)據(jù)更一般的“安全”(safe)半監(jiān)督學(xué)習(xí)仍是一個未決問題.閱讀材料半監(jiān)督學(xué)習(xí)的研究一般認(rèn)為始于[Shahshahani閱讀材料本章主要介紹了半監(jiān)督分類和聚類,但半監(jiān)督學(xué)習(xí)已普遍用于各類機(jī)器學(xué)習(xí)任務(wù),例如在半監(jiān)督回歸[ZhouandLi,2005a]、降維[Zhangetal.,2007]等方面都有相關(guān)研究.更多關(guān)于半監(jiān)督學(xué)習(xí)的內(nèi)容可參見[Chapelleetal.,2006b,Zhu,2006],[周志華,2013,ZhouandLi,2010]則是關(guān)于基于分歧的方法的專門介紹.[Settles,2009]是一個關(guān)于主動學(xué)習(xí)的介紹.閱讀材料本章主要介紹了半監(jiān)督分類和聚類,但半監(jiān)督學(xué)習(xí)已普遍此課件下載可自行編輯修改，供參考！感謝您的支持，我們努力做得更好！此課件下載可自行編輯修改，供參考！周志華-機(jī)器學(xué)習(xí)-西瓜書-全書16章--ch13課件第十三章：半監(jiān)督學(xué)習(xí)第十三章：半監(jiān)督學(xué)習(xí)背景（半監(jiān)督學(xué)習(xí)）隔壁老王品瓜師吃背景（半監(jiān)督學(xué)習(xí)）隔壁老王品瓜師吃背景（半監(jiān)督學(xué)習(xí)）品瓜師吃模型有標(biāo)記樣本無標(biāo)記樣本直推學(xué)習(xí)（純）半監(jiān)督學(xué)習(xí)待測數(shù)據(jù)背景（半監(jiān)督學(xué)習(xí)）品瓜師吃模型有標(biāo)記樣本無標(biāo)記樣本直推學(xué)習(xí)（背景（主動學(xué)習(xí)）品瓜師吃背景（主動學(xué)習(xí)）品瓜師吃背景（主動學(xué)習(xí)）品瓜師吃主動學(xué)習(xí)待測數(shù)據(jù)模型有標(biāo)記樣本無標(biāo)記樣本標(biāo)注者背景（主動學(xué)習(xí)）品瓜師吃主動學(xué)習(xí)待測數(shù)據(jù)模型有標(biāo)記樣本無標(biāo)記未標(biāo)記樣本的效用未標(biāo)記樣本的效用未標(biāo)記樣本的假設(shè)要利用未標(biāo)記樣本，必然要做一些將未標(biāo)記樣本所揭示的數(shù)據(jù)分布信息與類別標(biāo)記相聯(lián)系的假設(shè)，其中有兩種常見的假設(shè)。聚類假設(shè)（clusteringassumption）：

假設(shè)數(shù)據(jù)存在簇結(jié)構(gòu)，同一簇的樣本屬于同一類別。流形假設(shè)（manifoldassumption）：

假設(shè)數(shù)據(jù)分布在一個流形結(jié)構(gòu)上，鄰近的樣本具有相似的輸出值。流形假設(shè)可看做聚類假設(shè)的推廣未標(biāo)記樣本的假設(shè)流形假設(shè)可看做聚類假設(shè)的推廣大綱未標(biāo)記樣本生成式方法半監(jiān)督SVM圖半監(jiān)督學(xué)習(xí)基于分歧的方法半監(jiān)督聚類大綱未標(biāo)記樣本生成式方法假設(shè)樣本由這個假設(shè)意味著混合成分高斯混合模型生成,且每個類別對應(yīng)一個高斯混合成分：

其中,

生成式方法假設(shè)樣本由這個假設(shè)意味著混合成分高斯混合模型生成生成式方法由最大化后驗概率可知：生成式方法由最大化后驗概率可知：生成式方法假設(shè)樣本獨立同分布，且由同一個高斯混合模型生成，則對數(shù)似然函數(shù)是：生成式方法假設(shè)樣本獨立同分布，且由同一個高斯混合模型生成，則生成式方法高斯混合的參數(shù)估計可以采用EM算法求解，迭代更新式如下：E步：根據(jù)當(dāng)前模型參數(shù)計算未標(biāo)記樣本屬于各高斯混合成分的概率。生成式方法高斯混合的參數(shù)估計可以采用EM算法求解，迭代更新式生成式方法M步：基于更新模型參數(shù)生成式方法M步：基于更新模型參數(shù)生成式方法將上述過程中的高斯混合模型換成混合專家模型，樸素貝葉斯模型等即可推導(dǎo)出其他的生成式半監(jiān)督學(xué)習(xí)算法。此類方法簡單、易于實現(xiàn),在有標(biāo)記數(shù)據(jù)極少的情形下往往比其他方法性能更好。然而,此類方法有一個關(guān)鍵:模型假設(shè)必須準(zhǔn)確,即假設(shè)的生成式模型必須與真實數(shù)據(jù)分布吻合;否則利用未標(biāo)記數(shù)據(jù)反而會顯著降低泛化性能。生成式方法將上述過程中的高斯混合模型換成混合專家模型，樸素貝大綱未標(biāo)記樣本生成式方法半監(jiān)督SVM圖半監(jiān)督學(xué)習(xí)基于分歧的方法半監(jiān)督聚類大綱未標(biāo)記樣本半監(jiān)督SVM半監(jiān)督SVM半監(jiān)督SVM半監(jiān)督支持向量機(jī)中最著名的是TSVM(TransductiveSupportVectorMachine)半監(jiān)督SVM半監(jiān)督支持向量機(jī)中最著名的是TSVM(Trans半監(jiān)督SVMTSVM采用局部搜索來迭代地尋找近似解.無標(biāo)記樣本有標(biāo)記樣本SVM0偽標(biāo)記SVM1訓(xùn)練訓(xùn)練訓(xùn)練標(biāo)注半監(jiān)督SVMTSVM采用局部搜索來迭代地尋找近似解.無標(biāo)記樣半監(jiān)督SVMSVM1無標(biāo)記樣本搜索指派可能出錯的樣本交換樣本標(biāo)記有標(biāo)記樣本訓(xùn)練訓(xùn)練SVM2半監(jiān)督SVMSVM1無標(biāo)記樣本搜索指派可能出錯的樣本交換樣本半監(jiān)督SVM未標(biāo)記樣本的偽標(biāo)記不準(zhǔn)確半監(jiān)督SVM未標(biāo)記樣本的偽標(biāo)記不準(zhǔn)確半監(jiān)督SVM未標(biāo)記樣本進(jìn)行標(biāo)記指派及調(diào)整的過程中,有可能出現(xiàn)類別不平衡問題,即某類的樣本遠(yuǎn)多于另一類。為了減輕類別不平衡性所造成的不利影響,可對算法稍加改進(jìn):將優(yōu)化目標(biāo)中的項拆分為與

兩項,并在初始化時令：半監(jiān)督SVM未標(biāo)記樣本進(jìn)行標(biāo)記指派及調(diào)整的過程中,有可能出半監(jiān)督SVM顯然,搜尋標(biāo)記指派可能出錯的每一對未標(biāo)記樣本進(jìn)行調(diào)整,仍是一個涉及巨大計算開銷的大規(guī)模優(yōu)化問題。因此,半監(jiān)督SVM研究的一個重點是如何設(shè)計出高效的優(yōu)化求解策略。例如基于圖核(graphkernel)函數(shù)梯度下降的LaplacianSVM[ChapelleandZien,2005]、基于標(biāo)記均值估計的meanS3VM[Lietal.,2009]等.半監(jiān)督SVM顯然,搜尋標(biāo)記指派可能出錯的每一對未標(biāo)記樣本進(jìn)大綱未標(biāo)記樣本生成式方法半監(jiān)督SVM圖半監(jiān)督學(xué)習(xí)基于分歧的方法半監(jiān)督聚類大綱未標(biāo)記樣本圖半監(jiān)督學(xué)習(xí)給定一個數(shù)據(jù)集,我們可將其映射為一個圖,數(shù)據(jù)集中每個樣本對應(yīng)于圖中一個結(jié)點,若兩個樣本之間的相似度很高(或相關(guān)性很強),則對應(yīng)的結(jié)點之間存在一條邊,邊的“強度”(strength)正比于樣本之間的相似度(或相關(guān)性)。我們可將有標(biāo)記樣本所對應(yīng)的結(jié)點想象為染過色,而未標(biāo)記樣本所對應(yīng)的結(jié)點則尚未染色.于是,半監(jiān)督學(xué)習(xí)就對應(yīng)于“顏色”在圖上擴(kuò)散或傳播的過程。由于一個圖對應(yīng)了一個矩陣,這就使得我們能基于矩陣運算來進(jìn)行半監(jiān)督學(xué)習(xí)算法的推導(dǎo)與分析。圖半監(jiān)督學(xué)習(xí)給定一個數(shù)據(jù)集,我們可將其映射為一個圖,數(shù)據(jù)圖半監(jiān)督學(xué)習(xí)我們先基于構(gòu)建一個圖，其中結(jié)點集邊集E可表示為一個親和矩陣(affinitymatrix),?；诟咚购瘮?shù)定義為:圖半監(jiān)督學(xué)習(xí)我們先基于構(gòu)建一個圖圖半監(jiān)督學(xué)習(xí)假定從圖將學(xué)得一個實值函數(shù)。直觀上講相似的樣本應(yīng)具有相似的標(biāo)記,即得到最優(yōu)結(jié)果于是可定義關(guān)于f的“能量函數(shù)”(energyfunction)[Zhuetal.,2003]:

圖半監(jiān)督學(xué)習(xí)假定從圖將學(xué)得一個實值函圖半監(jiān)督學(xué)習(xí)采用分塊矩陣表示方式:由可得:圖半監(jiān)督學(xué)習(xí)采用分塊矩陣表示方式:圖半監(jiān)督學(xué)習(xí)圖半監(jiān)督學(xué)習(xí)圖半監(jiān)督學(xué)習(xí)上面描述的是一個針對二分類問題的“單步式”標(biāo)記傳播(labelpropagation)方法,下面我們來看一個適用于多分類問題的“迭代式”標(biāo)記傳播方法[Zhouetal.,2004].仍基于構(gòu)建一個圖其中結(jié)點集定義一個的非負(fù)標(biāo)記矩陣，其第i行元素為示例

的標(biāo)記向量,相應(yīng)的分類規(guī)則為:將F初始化為：圖半監(jiān)督學(xué)習(xí)上面描述的是一個針對二分類問題的“單步式”標(biāo)記傳圖半監(jiān)督學(xué)習(xí)基于W構(gòu)造一個標(biāo)記傳播矩陣，其中,于是有迭代計算式:基于迭代至收斂可得:圖半監(jiān)督學(xué)習(xí)基于W構(gòu)造一個標(biāo)記傳播矩陣圖半監(jiān)督學(xué)習(xí)事實上,算法對應(yīng)于正則化框架[Zhouetal.,2004]:當(dāng)時,最優(yōu)解恰為迭代算法的收斂解。圖半監(jiān)督學(xué)習(xí)事實上,算法對應(yīng)于正則化框架[Zhouet圖半監(jiān)督學(xué)習(xí)圖半監(jiān)督學(xué)習(xí)圖半監(jiān)督學(xué)習(xí)圖半監(jiān)督學(xué)習(xí)方法在概念上相當(dāng)清晰,且易于通過對所涉矩陣運算的分析來探索算法性質(zhì)。但此類算法的缺陷也相當(dāng)明顯.首先是在存儲開銷高。另一方面,由于構(gòu)圖過程僅能考慮訓(xùn)練樣本集,難以判知新樣本在圖中的位置,因此,在接收到新樣本時,或是將其加入原數(shù)據(jù)集對圖進(jìn)行重構(gòu)并重新進(jìn)行標(biāo)記傳播,或是需引入額外的預(yù)測機(jī)制。圖半監(jiān)督學(xué)習(xí)圖半監(jiān)督學(xué)習(xí)方法在概念上相當(dāng)清晰,且易于通過對大綱未標(biāo)記樣本生成式方法半監(jiān)督SVM圖半監(jiān)督學(xué)習(xí)基于分歧的方法半監(jiān)督聚類大綱未標(biāo)記樣本基于分歧的方法基于分歧的方法(disagreement-basedmethods)使用多學(xué)習(xí)器,而學(xué)disagreement亦稱diversity習(xí)器之間的“分歧”(disagreement)對未標(biāo)記數(shù)據(jù)的利用至關(guān)重要。協(xié)同訓(xùn)練(co-training)[BlumandMitchell,1998]是基于分歧的方法的重要代表,它最初是針對“多視圖”(multi-view)數(shù)據(jù)設(shè)計的,因此也被看作“多視圖學(xué)習(xí)”(multi-viewlearning)的代表.基于分歧的方法基于分歧的方法(disagreement-ba基于分歧的方法網(wǎng)頁分類任務(wù)中的雙視圖圖片視圖文字視圖基于分歧的方法網(wǎng)頁分類任務(wù)中的雙視圖圖片視圖文字視圖基于分歧的方法協(xié)同訓(xùn)練正是很好地利用了多視圖的“相容互補性”.假設(shè)數(shù)據(jù)擁有兩個“充分”(sufficient)且“條件獨立”視圖。視圖1視圖2模型1模型2最確信樣本最確信樣本基于分歧的方法協(xié)同訓(xùn)練正是很好地利用了多視圖的“相容互補性”基于分歧的方法基于分歧的方法基于分歧的方法協(xié)同訓(xùn)練過程雖簡單,但令人驚訝的是,理論證明顯示出,若兩個視圖充分且條件獨立,則可利用未標(biāo)記樣本通過協(xié)同訓(xùn)練將弱分類器的泛化性能提升到任意高[BlumandMitchell,1998].不過,視圖的條件獨立性在現(xiàn)實任務(wù)中通常很難滿足,不會是條件獨立的因此性能提升幅度不會那么大,但研究表明,即使在更弱的條件下,協(xié)同訓(xùn)練仍可有效地提升弱分類器的性能[周志華,2013].基于分歧的方法協(xié)同訓(xùn)練過程雖簡單,但令人驚訝的是,理論證基于分歧的方法協(xié)同訓(xùn)練算法本身是為多視圖數(shù)據(jù)而設(shè)計的,性集合的常見數(shù)據(jù)但此后出現(xiàn)了一些能在單視圖數(shù)據(jù)上使用的變體算法。

它們或是使用不同的學(xué)習(xí)算法[GoldmanandZhou,2000]、或使用不同的數(shù)據(jù)采樣[ZhouandLi,2005b]、甚至使用不同的參數(shù)設(shè)置[ZhouandLi,2005a]來產(chǎn)生不同的學(xué)習(xí)器,也能有效地利用未標(biāo)記數(shù)據(jù)來提升性能。后續(xù)理論研究發(fā)現(xiàn),此類算法事實上無需數(shù)據(jù)擁有多視圖,僅需弱學(xué)習(xí)器之間具有顯著的分歧(或差異),即可通過相互提供偽標(biāo)記樣本的方式來提高泛化性能[周志華,2013]?；诜制绲姆椒▍f(xié)同訓(xùn)練算法本身是為多視圖數(shù)據(jù)而設(shè)計的,性集合基于分歧的方法基于分歧的方法只需采用合適的基學(xué)習(xí)器,就較少受到模型假設(shè)、損失函數(shù)非凸性和數(shù)據(jù)規(guī)模問題的影響,學(xué)習(xí)方法簡單有效、理論基礎(chǔ)相對堅實、適用范圍較為廣泛。為了使用此類方法,需能生成具有顯著分歧、性能尚可的多個學(xué)習(xí)器,但當(dāng)有標(biāo)記樣本很少、尤其是數(shù)據(jù)不具有多視圖時,要做到這一點并不容易。基于分歧的方法基于分歧的方法只需采用合適的基學(xué)習(xí)器,就較少大綱未標(biāo)記樣本生成式方法半監(jiān)督SVM圖半監(jiān)督學(xué)習(xí)基于分歧的方法半監(jiān)督聚類大綱未標(biāo)記樣本半監(jiān)督聚類聚類是一種典型的無監(jiān)督學(xué)習(xí)任務(wù),然而在現(xiàn)實聚類任務(wù)中我們往往能獲得一些額外的監(jiān)督信息,于是可通過“半監(jiān)督聚類”(semi-supervisedclustering)來利用監(jiān)督信息以獲得更好的聚類效果.聚類任務(wù)中獲得的監(jiān)督信息大致有兩種類型：第一種類型是“必連”(must-link)與“勿連”(cannot-link)約束，前者是指樣本必屬于同一個簇,后者則是指樣本必不屬于同一個簇；第二種類型的監(jiān)督信息則是少量的有標(biāo)記樣本.半監(jiān)督聚類聚類是一種典型的無監(jiān)督學(xué)習(xí)任務(wù),然而在現(xiàn)實聚類任半監(jiān)督聚類約束k均值(Constrainedk-means)算法[Wagstaffetal.,2001]是利用第一類監(jiān)督信息的代表。該算法是k均值算法的擴(kuò)展,它在聚類過程中要確保“必連”關(guān)系集合與“勿連”關(guān)系集合中的約束得以滿足,否則