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

假設數據存在簇結構，同一簇的樣本屬于同一類別。流形假設（manifoldassumption）：

假設數據分布在一個流形結構上，鄰近的樣本具有相似的輸出值。流形假設可看做聚類假設的推廣未標記樣本的假設流形假設可看做聚類假設的推廣大綱未標記樣本生成式方法半監督SVM圖半監督學習基于分歧的方法半監督聚類大綱未標記樣本生成式方法假設樣本由這個假設意味著混合成分高斯混合模型生成,且每個類別對應一個高斯混合成分：

其中,

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

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

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

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

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

假設數據存在簇結構，同一簇的樣本屬于同一類別。流形假設（manifoldassumption）：

假設數據分布在一個流形結構上，鄰近的樣本具有相似的輸出值。流形假設可看做聚類假設的推廣未標記樣本的假設流形假設可看做聚類假設的推廣大綱未標記樣本生成式方法半監督SVM圖半監督學習基于分歧的方法半監督聚類大綱未標記樣本生成式方法假設樣本由這個假設意味著混合成分高斯混合模型生成,且每個類別對應一個高斯混合成分：

其中,

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

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

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

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

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