周志華 機(jī)器學(xué)習(xí) 西瓜書 全書16章ch13半監(jiān)督學(xué)習(xí)

1、隔壁老王隔壁老王品瓜師品瓜師吃品瓜師品瓜師吃模型有標(biāo)記樣本無(wú)標(biāo)記樣本直推學(xué)習(xí)直推學(xué)習(xí)（純）半監(jiān)督學(xué)習(xí)（純）半監(jiān)督學(xué)習(xí)待測(cè)數(shù)據(jù)品瓜師品瓜師吃品瓜師品瓜師吃主動(dòng)學(xué)主動(dòng)學(xué)習(xí)習(xí)待測(cè)數(shù)據(jù)模型有標(biāo)記樣本無(wú)標(biāo)記樣本標(biāo)注者p 要利用未標(biāo)記樣本，必然要做一些將未標(biāo)記樣本所揭示的數(shù)據(jù)分布信息與類別標(biāo)記相聯(lián)系的假設(shè)，其中有兩種常見(jiàn)的假設(shè)。l 聚類假設(shè)（clustering assumption）：假設(shè)數(shù)據(jù)存在簇結(jié)構(gòu)，同一簇的樣本屬于同一類別。l 流形假設(shè)（manifold assumption）：假設(shè)數(shù)據(jù)分布在一個(gè)流形結(jié)構(gòu)上，鄰近的樣本具有相似的輸出值。流形假設(shè)可看做聚類假設(shè)的推廣p 未標(biāo)記樣本p 生成式方法p 半

2、監(jiān)督SVMp 圖半監(jiān)督學(xué)習(xí)p 基于分歧的方法p 半監(jiān)督聚類p 假設(shè)樣本由這個(gè)假設(shè)意味著混合成分 高斯混合模型生成, 且每個(gè)類別對(duì)應(yīng)一個(gè)高斯混合成分： 其中, p 由最大化后驗(yàn)概率可知：p 假設(shè)樣本獨(dú)立同分布，且由同一個(gè)高斯混合模型生成，則對(duì)數(shù)似然函數(shù)是：p 高斯混合的參數(shù)估計(jì)可以采用EM算法求解，迭代更新式如下：l E步：根據(jù)當(dāng)前模型參數(shù)計(jì)算未標(biāo)記樣本屬于各高斯混合成分的概率。l M步：基于 更新模型參數(shù)p 將上述過(guò)程中的高斯混合模型換成混合專家模型，樸素貝葉斯模型等即可推導(dǎo)出其他的生成式半監(jiān)督學(xué)習(xí)算法。p 此類方法簡(jiǎn)單、易于實(shí)現(xiàn), 在有標(biāo)記數(shù)據(jù)極少的情形下往往比其他方法性能更好。p 然而,

3、此類方法有一個(gè)關(guān)鍵: 模型假設(shè)必須準(zhǔn)確, 即假設(shè)的生成式模型必須與真實(shí)數(shù)據(jù)分布吻合; 否則利用未標(biāo)記數(shù)據(jù)反而會(huì)顯著降低泛化性能。p 未標(biāo)記樣本p 生成式方法p 半監(jiān)督SVMp 圖半監(jiān)督學(xué)習(xí)p 基于分歧的方法p 半監(jiān)督聚類p 半監(jiān)督支持向量機(jī)中最著名的是TSVM(Transductive Support Vector Machine)p TSVM采用局部搜索來(lái)迭代地尋找近似解.無(wú)標(biāo)記樣本有標(biāo)記樣本SVMSVM0 0偽標(biāo)記偽標(biāo)記SVMSVM1 1訓(xùn)練訓(xùn)練訓(xùn)練訓(xùn)練訓(xùn)訓(xùn)練練標(biāo)注標(biāo)注SVMSVM1 1無(wú)標(biāo)記樣本搜索搜索指派可能出錯(cuò)的樣本交換樣本標(biāo)記交換樣本標(biāo)記有標(biāo)記樣本訓(xùn)練訓(xùn)練訓(xùn)練訓(xùn)練SVMSVM2 2

4、未標(biāo)記樣本的偽未標(biāo)記樣本的偽標(biāo)記不準(zhǔn)確標(biāo)記不準(zhǔn)確p 未標(biāo)記樣本進(jìn)行標(biāo)記指派及調(diào)整的過(guò)程中, 有可能出現(xiàn)類別不平衡問(wèn)題,即某類的樣本遠(yuǎn)多于另一類。p 為了減輕類別不平衡性所造成的不利影響, 可對(duì)算法稍加改進(jìn): 將優(yōu)化目標(biāo)中的 項(xiàng)拆分為 與 兩項(xiàng),并在初始化時(shí)令：p 顯然, 搜尋標(biāo)記指派可能出錯(cuò)的每一對(duì)未標(biāo)記樣本進(jìn)行調(diào)整, 仍是一個(gè)涉及巨大計(jì)算開(kāi)銷的大規(guī)模優(yōu)化問(wèn)題。p 因此, 半監(jiān)督SVM研究的一個(gè)重點(diǎn)是如何設(shè)計(jì)出高效的優(yōu)化求解策略。p 例如基于圖核(graph kernel)函數(shù)梯度下降的Laplacian SVMChapelle and Zien, 2005、基于標(biāo)記均值估計(jì)的meanS3VM

5、Li et al., 2009等.p 未標(biāo)記樣本p 生成式方法p 半監(jiān)督SVMp 圖半監(jiān)督學(xué)習(xí)p 基于分歧的方法p 半監(jiān)督聚類p 給定一個(gè)數(shù)據(jù)集, 我們可將其映射為一個(gè)圖, 數(shù)據(jù)集中每個(gè)樣本對(duì)應(yīng)于圖中一個(gè)結(jié)點(diǎn), 若兩個(gè)樣本之間的相似度很高(或相關(guān)性很強(qiáng)), 則對(duì)應(yīng)的結(jié)點(diǎn)之間存在一條邊, 邊的“強(qiáng)度”(strength)正比于樣本之間的相似度(或相關(guān)性)。p 我們可將有標(biāo)記樣本所對(duì)應(yīng)的結(jié)點(diǎn)想象為染過(guò)色, 而未標(biāo)記樣本所對(duì)應(yīng)的結(jié)點(diǎn)則尚未染色. 于是, 半監(jiān)督學(xué)習(xí)就對(duì)應(yīng)于“顏色”在圖上擴(kuò)散或傳播的過(guò)程。p 由于一個(gè)圖對(duì)應(yīng)了一個(gè)矩陣, 這就使得我們能基于矩陣運(yùn)算來(lái)進(jìn)行半監(jiān)督學(xué)習(xí)算法的推導(dǎo)與分析。p 我

6、們先基于 構(gòu)建一個(gè)圖 ，其中結(jié)點(diǎn)集p 邊集E可表示為一個(gè)親和矩陣(affinity matrix),常基于高斯函數(shù)定義為:p 假定從圖 將學(xué)得一個(gè)實(shí)值函數(shù) 。p 直觀上講相似的樣本應(yīng)具有相似的標(biāo)記,即得到最優(yōu)結(jié)果于是可定義關(guān)于f的“能量函數(shù)”(energy function)Zhu et al., 2003: p 采用分塊矩陣表示方式:p 由 可得:p 上面描述的是一個(gè)針對(duì)二分類問(wèn)題的“單步式”標(biāo)記傳播(label propagation)方法, 下面我們來(lái)看一個(gè)適用于多分類問(wèn)題的“迭代式”標(biāo)記傳播方法Zhou et al., 2004.p 仍基于 構(gòu)建一個(gè)圖 其中結(jié)點(diǎn)集p 定義一個(gè) 的非負(fù)標(biāo)

7、記矩陣 ，其第i行元素 為示例 的標(biāo)記向量, 相應(yīng)的分類規(guī)則為:p 將F初始化為：p 基于W構(gòu)造一個(gè)標(biāo)記傳播矩陣 ，其中 , 于是有迭代計(jì)算式:p 基于迭代至收斂可得:p 事實(shí)上, 算法對(duì)應(yīng)于正則化框架Zhou et al., 2004:p 當(dāng) 時(shí), 最優(yōu)解恰為迭代算法的收斂解 。p 圖半監(jiān)督學(xué)習(xí)方法在概念上相當(dāng)清晰, 且易于通過(guò)對(duì)所涉矩陣運(yùn)算的分析來(lái)探索算法性質(zhì)。p 但此類算法的缺陷也相當(dāng)明顯. 首先是在存儲(chǔ)開(kāi)銷高。p 另一方面, 由于構(gòu)圖過(guò)程僅能考慮訓(xùn)練樣本集, 難以判知新樣本在圖中的位置, 因此, 在接收到新樣本時(shí), 或是將其加入原數(shù)據(jù)集對(duì)圖進(jìn)行重構(gòu)并重新進(jìn)行標(biāo)記傳播, 或是需引入額外的

8、預(yù)測(cè)機(jī)制。p 未標(biāo)記樣本p 生成式方法p 半監(jiān)督SVMp 圖半監(jiān)督學(xué)習(xí)p 基于分歧的方法p 半監(jiān)督聚類p 基于分歧的方法(disagreement-based methods)使用多學(xué)習(xí)器, 而學(xué)disagreement亦稱diversity 習(xí)器之間的“分歧”(disagreement)對(duì)未標(biāo)記數(shù)據(jù)的利用至關(guān)重要。p 協(xié)同訓(xùn)練(co-training)Blum and Mitchell, 1998是基于分歧的方法的重要代表, 它最初是針對(duì)“多視圖”(multi-view)數(shù)據(jù)設(shè)計(jì)的, 因此也被看作“多視圖學(xué)習(xí)”(multi-view learning)的代表.網(wǎng)頁(yè)分類任務(wù)中的雙視圖圖片視圖文

9、字視圖p 協(xié)同訓(xùn)練正是很好地利用了多視圖的“相容互補(bǔ)性”. 假設(shè)數(shù)據(jù)擁有兩個(gè)“充分”(sufficient)且“條件獨(dú)立”視圖。視圖1視圖2模型模型1 1模型模型2 2最確信樣本最確信樣本最確信樣本最確信樣本p 協(xié)同訓(xùn)練過(guò)程雖簡(jiǎn)單, 但令人驚訝的是, 理論證明顯示出, 若兩個(gè)視圖充分且條件獨(dú)立, 則可利用未標(biāo)記樣本通過(guò)協(xié)同訓(xùn)練將弱分類器的泛化性能提升到任意高Blum and Mitchell, 1998.p 不過(guò), 視圖的條件獨(dú)立性在現(xiàn)實(shí)任務(wù)中通常很難滿足,不會(huì)是條件獨(dú)立的因此性能提升幅度不會(huì)那么大, 但研究表明, 即使在更弱的條件下,協(xié)同訓(xùn)練仍可有效地提升弱分類器的性能周志華, 2013.p

10、 協(xié)同訓(xùn)練算法本身是為多視圖數(shù)據(jù)而設(shè)計(jì)的,性集合的常見(jiàn)數(shù)據(jù)但此后出現(xiàn)了一些能在單視圖數(shù)據(jù)上使用的變體算法。p 它們或是使用不同的學(xué)習(xí)算法Goldman and Zhou,2000、或使用不同的數(shù)據(jù)采樣Zhou and Li, 2005b、甚至使用不同的參數(shù)設(shè)置Zhou and Li, 2005a來(lái)產(chǎn)生不同的學(xué)習(xí)器, 也能有效地利用未標(biāo)記數(shù)據(jù)來(lái)提升性能。p 后續(xù)理論研究發(fā)現(xiàn), 此類算法事實(shí)上無(wú)需數(shù)據(jù)擁有多視圖, 僅需弱學(xué)習(xí)器之間具有顯著的分歧(或差異), 即可通過(guò)相互提供偽標(biāo)記樣本的方式來(lái)提高泛化性能周志華, 2013。p 基于分歧的方法只需采用合適的基學(xué)習(xí)器, 就較少受到模型假設(shè)、損失函數(shù)非凸

11、性和數(shù)據(jù)規(guī)模問(wèn)題的影響, 學(xué)習(xí)方法簡(jiǎn)單有效、理論基礎(chǔ)相對(duì)堅(jiān)實(shí)、適用范圍較為廣泛。p 為了使用此類方法, 需能生成具有顯著分歧、性能尚可的多個(gè)學(xué)習(xí)器, 但當(dāng)有標(biāo)記樣本很少、尤其是數(shù)據(jù)不具有多視圖時(shí), 要做到這一點(diǎn)并不容易。p 未標(biāo)記樣本p 生成式方法p 半監(jiān)督SVMp 圖半監(jiān)督學(xué)習(xí)p 基于分歧的方法p 半監(jiān)督聚類p 聚類是一種典型的無(wú)監(jiān)督學(xué)習(xí)任務(wù), 然而在現(xiàn)實(shí)聚類任務(wù)中我們往往能獲得一些額外的監(jiān)督信息, 于是可通過(guò)“半監(jiān)督聚類”(semi-supervised clustering)來(lái)利用監(jiān)督信息以獲得更好的聚類效果.p 聚類任務(wù)中獲得的監(jiān)督信息大致有兩種類型：l 第一種類型是“ 必連”(mus

12、t-link)與“勿連”(cannot-link)約束，前者是指樣本必屬于同一個(gè)簇, 后者則是指樣本必不屬于同一個(gè)簇；l 第二種類型的監(jiān)督信息則是少量的有標(biāo)記樣本.p 約束k均值(Constrained k-means)算法Wagstaff et al., 2001是利用第一類監(jiān)督信息的代表。p 該算法是k均值算法的擴(kuò)展,它在聚類過(guò)程中要確?！氨剡B”關(guān)系集合與“勿連”關(guān)系集合中的約束得以滿足, 否則將返回錯(cuò)誤提示。不沖突，選擇最近的簇不沖突，選擇最近的簇沖突，嘗試次近的簇沖突，嘗試次近的簇p 第二種監(jiān)督信息是少量有標(biāo)記樣本。即假設(shè)少量有標(biāo)記樣本屬于k個(gè)聚類簇。p 這樣的監(jiān)督信息利用起來(lái)很容易:

13、 直接將它們作為“種子”, 用它們初始化k均值算法的k個(gè)聚類中心, 并且在聚類簇迭代更新過(guò)程中不改變種子樣本的簇隸屬關(guān)系. 這樣就得到了約束種子k均值(Constrained Seed k-means)算法Basu et al., 2002。p 半監(jiān)督學(xué)習(xí)的研究一般認(rèn)為始于Shahshahani and Landgrebe, 1994, 該領(lǐng)域在上世紀(jì)末、本世紀(jì)初蓬勃發(fā)展. 國(guó)際機(jī)器學(xué)習(xí)大會(huì)(ICML) 從2008年開(kāi)始評(píng)選“十年最佳論文”, 在短短6年中, 半監(jiān)督學(xué)習(xí)四大范型(paradim)中基于分歧的方法、半監(jiān)督SVM、圖半監(jiān)督學(xué)習(xí)的代表性工作先后于2008年Blumand Mitche

14、ll, 1998、2009年Joachims, 1999、2013年Zhu et al., 2003獲獎(jiǎng).p 半監(jiān)督學(xué)習(xí)在利用未標(biāo)記樣本后并非必然提升泛化性能, 在有些情形下甚至?xí)?dǎo)致性能下降. 對(duì)生成式方法, 其成因被認(rèn)為是模型假設(shè)不準(zhǔn)確Cozmanand Cohen, 2002, 因此需依賴充分可靠的領(lǐng)域知識(shí)來(lái)設(shè)計(jì)模型. 對(duì)半監(jiān)督SVM, 其成因被認(rèn)為是訓(xùn)練數(shù)據(jù)中存在多個(gè)“低密度劃分”, 而學(xué)習(xí)算法有可能做出不利的選擇; S4VM Li and Zhou, 2015 通過(guò)優(yōu)化最壞情形性能來(lái)綜“安全”指利用未標(biāo)記數(shù) 合利用多個(gè)低密度劃分, 提升了此類技術(shù)的安全性.據(jù)之后, 確保泛化性能至少不差于僅利用有標(biāo)記數(shù)據(jù)更一般的“安全”(safe)半監(jiān)督學(xué)習(xí)仍是一個(gè)未決問(wèn)題.p 本章主要介紹了半監(jiān)督分類和聚類, 但半監(jiān)督學(xué)習(xí)已普遍