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

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

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

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

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

6、們先基于 構建一個圖 ，其中結點集p 邊集E可表示為一個親和矩陣(affinity matrix),?；诟咚购瘮刀x為:p 假定從圖 將學得一個實值函數 。p 直觀上講相似的樣本應具有相似的標記,即得到最優結果于是可定義關于f的“能量函數”(energy function)Zhu et al., 2003: p 采用分塊矩陣表示方式:p 由 可得:p 上面描述的是一個針對二分類問題的“單步式”標記傳播(label propagation)方法, 下面我們來看一個適用于多分類問題的“迭代式”標記傳播方法Zhou et al., 2004.p 仍基于 構建一個圖 其中結點集p 定義一個 的非負標

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

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

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

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

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

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

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

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