1.2 半監督學習方法

在當前的技術條件下，可以很容易地收集到大量無標記的樣本，而有標記的樣本獲取則仍然十分困難，這是因為對樣本進行標記往往需要消耗大量的人力和物力^［4］。以遙感圖像的分類問題為例，圖像對應的地物類別必須通過實地考察才可以確定，而遙感圖像常覆蓋著廣大的區域，造成實地考察難度大、耗時長的問題，因此可用的標記樣本量常無法滿足需求。基于數量有限的有標記樣本訓練得到的分類器往往泛化能力較低；而大量未標記樣本無法得到有效的利用，則造成數據資源的巨大浪費。半監督學習就是一種可以合理利用大量未標記樣本作為有限的有標記樣本的補充，對分類器性能進行優化的機器學習方法。本節將首先介紹半監督學習的思想起源，然后給出無標記樣本提高學習性能的基本假設，最后對幾種主流的半監督學習方法進行簡要介紹。

1.2.1 半監督學習概述

一般認為，Shahshahani和Landgrebe^［24］在1994年的研究工作是半監督學習的開始。但由于在當時的主流機器學習方法（如神經網絡）中考慮未標記樣本相對比較困難，因此未得到較大關注。近些年來，隨著統計學習理論的不斷發展、機器學習理論在實際問題中的廣泛應用以及利用未標記樣本這一需求的日漸強烈，半監督學習逐漸成為機器學習研究領域的一個熱點，并獲得了長足的發展。

半監督學習的思想起源于自訓練（Self-training）方法，自訓練算法又被稱為自學習（Self-teaching）算法或Bootstrapping方法，是目前在半監督學習中普遍使用的一種方法。在自訓練方法中，首先用少量的有標記數據訓練出一個初始的分類器，然后用該分類器對無標記數據進行預測。之后將置信度較高的無標記樣本連同預測出的類別標記一同加入到原來的訓練集中。再用新的訓練集重新訓練這個分類器，如此循環下去，直到達到終止條件。由上述學習過程可以看出，該方法能夠利用無標記樣本對訓練樣本集進行擴充，需要注意的一點是，如果在自訓練過程中出現分類錯誤，則這些錯誤不但很難被糾正，而且會向下一輪的訓練傳播，反而使錯誤不斷增強，因此如何選擇置信度高的無標記樣本至關重要。有些算法通過事先設定閾值的方式避免錯誤增強問題，若預測置信度低于設定的閾值，則不對相應的未標記樣本做進一步的學習。自訓練方法通常難以進行理論分析，但仍有一些專家學者嘗試對其收斂性進行分析。

在一定的前提條件下，采用無標記的樣本可以提高分類器的性能。Miller和Uyar^［25］通過理論推導，證明如果目標和未標記樣本分布之間能夠建立相互聯系，利用未標記樣本訓練分類器就能夠達到提高分類性能的效果。通常，未標記樣本和目標間的聯系需以某些假設為基礎。聚類假設（Cluster Assumption）和流形假設（Manifold Assumption）是目前在半監督學習中使用最廣泛的兩個基本假設。

1）聚類假設是指相同聚類（Cluster）中的樣本具有相同標記的概率更高。因此，分類器的決策邊界就應盡可能避開各聚類中的數據稠密區域以免將聚類分割到決策邊界兩側。根據聚類假設，未標記樣本用來作為分析樣本空間中數據分布的依據，根據未標記樣本數據的分布特點，來調整通過標記樣本學習得到的決策邊界，使決策邊界盡可能通過樣本空間中數據分布稀疏的區域^［4］。聚類假設簡單且直觀，因此得到了較廣泛的應用^{［26，27］}。例如，Joachims等^［28］提出一種直推式支持向量機，在訓練時，通過不斷調整支持向量機的決策超平面并標記超平面兩側部分未標記樣本，使得分類器在全體樣本組成的訓練集上取得最大分類間隔，得到的分類超平面能避開數據稠密區域并對有標記樣本進行正確劃分；Lawrence等^［29］通過對高斯過程（Gaussian Process）中的噪聲模型進行修改來實現半監督學習，該方法在正、反兩類之外引入“零類”，禁止任一未標記樣本被歸入零類，以保證訓練得到的決策面遠離數據稠密區域；Grandvalet等^［30］引入信息熵作為正則化項來實現半監督學習，由于熵的最小化僅和模型在未標記樣本上的輸出相關，因此，最小化熵就是降低模型的不確定性，從而迫使決策面從數據稀疏的區域通過。

2）流形假設則認為數據空間中的鄰近樣本應具有相似性，即這些樣本的標記應該是大體一致的。具體來說，在高維空間中一個很小的局部鄰域內的數據點在低維投影空間中應該是相近的，其標記也應該相似。這種相似性可理解為決策函數的局部平滑特性。相對而言，聚類假設注重整體特性，流形假設則著眼于局部特性。在流形假設下，大量存在的未標記樣本使得數據空間更加稠密，因此對局域特性的刻畫更加精細，相應的決策函數對數據的擬合也有更好的效果^［31］。在實際中，可直接應用流形假設。例如，Zhu等^［32］基于高斯隨機場（Gaussian Random Field）和諧波函數實現半監督學習，先是根據訓練樣本集建立一個圖，圖中各個節點都表示一個（有標記或未標記）樣本，接著由流形假設構造能量函數并求其最優解，以確定未標記樣本對應的最優類別標記；Zhou等^［33］基于流形假設根據樣本間的相似性建立圖模型，并使有標記樣本節點上的信息（類標）向鄰近節點不斷傳播，直到實現圖的全局穩定。

可以證明聚類假設和流形假設在本質上是一致的^［4］。事實上，聚類通常是比較稠密的區域，因此根據流形假設得到的模型輸出在同一聚類中也是相似的。兩者的差別在于，由于流形假設要求相似樣本具有相似輸出而非完全相同的標記，因此流形假設較聚類假設更為一般化，在一些半監督回歸問題中聚類假設難以滿足，而流形假設則更易實現^［4］。

1.2.2 半監督學習方法簡介

半監督學習涵蓋的范圍非常廣泛，如果根據所選取的不同模型來分類，則半監督學習方法可大致分為生成式模型（Generative Models）、協同訓練（Co-training）、最大化分離（Maximizing Separation）和基于圖的方法（Graph-based Methods）4種。其中，生成式模型將未標記樣本屬于各類別的概率作為缺失參數，使用期望最大化（Expectation Maximization，EM）算法對標記參數和模型參數進行估計，利用大量未標記樣本幫助建立高斯混合模型的各個成分。為避免一個分類器的分類錯誤傳遞到后續過程中，并累積而導致分類器的訓練結果持續惡化，協同訓練假設樣本集具有兩個完備且冗余的視圖（特征子集），利用這兩個視圖分別訓練出對應的分類器。在協同訓練階段，兩個分類器各自在未標記樣本中對一些置信度較高的樣本進行標記，并將標記后的樣本補充到對方的標記訓練集中，然后重新訓練，當沒有更多合適的未標記樣本加入時迭代停止。當所使用的基分類器在初始分類效果上存在差異時，即便使用單個視圖協同訓練也同樣有效。最大化分離方法要求數據分布滿足聚類假設并存在較低的概率密度分布區域，通過加入約束項使得分類的超平面避開數據稠密的樣本區域。而基于圖的方法以流形假設理論為依據，通常利用訓練樣本集中標記樣本和無標記樣本間的相似度來構建圖，通過流形正則化方法求解相應的決策函數。下面將對這4種主要的半監督學習方法進行更為詳細的介紹。

（1）生成式模型半監督學習方法^［34］

生成式模型是最早的半監督學習方法之一。該方法完全基于數據的概率分布進行建模，其基本思想是對于給定樣本特征的完全數據概率建模，通常以生成式模型為分類器，將未標記樣本屬于各類別的概率看作缺失參數，然后利用最大似然算法對標記和模型參數進行估計。常用于半監督學習的生成式模型有高斯混合模型、多項式混合模型、Markov隱式模型等。此類方法也可以看成是以少量已知標記的樣本為中心進行聚類，因而屬于基于聚類假設的方法。

在半監督問題中，常將未標記樣本隸屬于各個類別的概率看作一組缺失參數，在此基礎上采用期望最大化算法^［35］對標記和模型參數進行估計，從而利用未標記樣本實現提升分類器分類性能的目標。期望最大化算法對模型的參數估計通常是利用最大似然準則來實現。假設數據集X={x₁，x₂，…，x_N}中的全部分量都是基于特定分布p（x_i|θ）的獨立同分布采樣獲得的，則數據集的似然函數可表示為

式中：θ為樣本分布的參數向量；N為樣本個數；L（·）為似然函數。

最大似然準則就是要尋找滿足以下條件的模型參數：

為簡化計算，常利用對數似然函數lg（L（θ|X））來實現求解和優化。

在數據缺失情況下，期望最大化算法是進行模型參數估計的一種有效手段^［35-37］。用Z=（X，Y）表示包含已觀測數據集X以及未測數據集Y的數據全集，則集合Z與集合X分別被稱為完全數據集和不完全數據集。

根據上述定義可以得到以下關系式，即

定義L（θ|Z）=L（θ|X，Y）=p（X，Y|θ）為完全數據似然函數，則式（1.1）中的L（θ|X）就表示不完全數據似然函數。不妨將完全數據似然函數L（θ|X，Y）視為數據集Y的函數^［38］，即

式中：f（Y|X，θ）為未測數據集Y在給定已觀測數據集X和參數向量θ的條件下的邊緣分布函數。

以上述定義為基礎，可概括期望最大化算法處理未測數據的過程如下：

1）期望步，計算以下完全數據對數似然函數，即

式中：θ^t-1為t-1時刻參數的估計值；Ω為缺失變量y的取值范圍。

2）最大化步，求使式（1.5）中的期望值Q（θ，θ^t-1）最大化的t時刻的參數估計值，即

通過對上述期望步和最大化步的迭代執行，就可搜尋到參數θ的局部最優解^［39］。

此外，通過聚類算法消除影響半監督學習效果的奇異點，并在期望最大化算法的初值設置中引入優化，可顯著提高半監督學習對數據結構挖掘的精確度^［40］。將半監督學習的誤差估計與未標記樣本的學習同時進行，而將誤差估計值也作為調整分類器參數的依據，得到一種擴展型期望最大化半監督學習方法^［41］。通過引入廣義貝葉斯理論，采用期望最大化算法對混合模型的參數進行調整，提出另一種改進的半監督混合模型方法^［42］。Constantinopoulos等^［43］提出的概率徑向基函數神經網絡，在每次迭代過程中都基于期望最大化算法進行半監督學習，可達到比監督型神經網絡更理想的學習效果。

（2）協同訓練半監督學習方法

協同訓練（Co-training）是另外一種流行的半監督學習方法。協同訓練隱含地利用聚類假設或流形假設。通常使用兩個或多個分類器，在學習過程中，這些分類器挑選若干個置信度高的未標記樣本進行相互標記，從而使得模型得以更新。協同訓練已運用到文本分類、英語基本名詞及短語識別、情感分類、共指消解等研究上，而且取得了不錯的效果，甚至超過了傳統的有監督學習方法。協同訓練方法最大的優點是不用人工干涉，即可從未標注的數據中自動學習到知識。

協同訓練算法（或稱標準協同訓練算法）^［44］假設數據集具有兩個充分且冗余（Sufficient and Redundant）的視圖（View），即兩個滿足充分和冗余條件的屬性集。首先，每個屬性集都足以單獨描述該問題，在訓練量足夠的前提下，每個屬性集上都足以建立起一個強的分類器；其次，對于給定標記，兩個屬性集滿足條件獨立假設。在此基礎上，協同訓練算法的基本思想是：基于標記樣本的兩個不同視圖（View）分別訓練得到一個分類器，在之后的協同訓練過程中，一個分類器從未標記樣本中選出一些標記置信度較高的樣本并進行標記，再把標記后的樣本作為標記樣本加入另一個分類器的訓練集中，而獲得新樣本的分類器則利用這些新標記進行重新訓練。協同訓練過程不斷重復進行，直到最后達到某個停止條件。

在協同訓練中，當視圖的充分冗余性條件成立時，分類器的性能可以通過標準協同訓練算法得到顯著提升^［45］。然而在很多實際應用中，充分冗余視圖的條件可能很難達到。為解決該問題，需要設計不需要充分冗余視圖條件支持的協同訓練方法。其中一種不需要充分冗余視圖的協同算法^［46］是：利用不同的決策樹算法，基于同一個屬性集訓練得到兩個不同的分類器，這兩個分類器都能將樣本空間劃分為若干個等價類。在之后的協同訓練過程中，這兩個分類器通過統計方法來估計標記的置信度，并且選取置信度最高的樣本標記提供給另一個分類器作為有標記訓練例，更新對應分類器。這一過程反復進行，直到最后達到停止條件。在測試階段，該算法首先對兩分類器為未標記樣本所做標記的置信度進行估計，然后選取置信度較高的分類器進行預測。該算法的性能已通過試驗進行驗證，且經過擴展后可使用多個不同種類的分類器。但該算法的計算時間消耗較大，且魯棒性不高。

另一方面，有理論證明^［47］：只要兩個分類器具有明顯的差異，就能通過協同訓練來有效利用未標記樣本以提高學習性能。這說明當兩個視圖的條件獨立性不成立時，采用具有明顯差異的兩個分類器的協同訓練算法仍能取得較好的效果。

三重訓練方法也是一種不需要充分冗余視圖條件支持的協同訓練方法^{［48，49］}，該方法既不需滿足充分冗余性條件，也不需使用具有差異性的分類器，因此進一步放松了協同訓練的約束條件。三重訓練方法使用3個分類器，使標記置信度更易估計，未標記樣本的類別也更容易預測，而集成學習（Ensemble Learning）^［50］的引入則能進一步提高算法的泛化性。三重訓練方法首先對有標記樣本集進行可重復采樣（Bootstrap Sampling）從而得到3個有標記的訓練集，然后基于每個訓練集分別生成一個分類器。在之后的協同訓練過程中，各分類器所用到的新標記樣本都是通過其余兩個分類器協作提供。具體做法是，當兩個分類器對同一個未標記樣本的預測相同時，認為該樣本的標記具有較高的置信度，將該樣本加入第三個分類器的訓練集。預測過程中，采用投票的方式綜合3個分類器的預測結果，來判斷未標記樣本的類別。集成學習的優勢通過不同分類器的整合得以發揮。三重訓練方法區別于以往協同訓練算法的一個關鍵是，它根據3個分類器預測結果的一致性來隱式地比較不同未標記樣本的標記置信度，從而避免統計測試技術的頻繁使用，較大程度降低了運算量。然而與直接估計標記置信度的方法相比，這種隱式比較常常表現得不夠準確，特別是對于分類器初始準確性較低的情況，如果未標記樣本被錯誤標記，就可能給第三個分類器的訓練引入噪聲。針對這一問題，根據噪聲學習理論^［51］可推導出以較高概率保證隱式處理方法效果的條件，即如果大部分未標記樣本的標記是準確的，少量噪聲所造成的干擾就會被大量未標記樣本所包含的有效信息所抵消^［48］。如果要進一步減輕噪聲的影響，就需要采用一些更可靠的誤差估計技術，然而這是以增加算法運算量和存儲空間占用率為代價的。在三重訓練算法的基礎上，進一步擴展得到的Co-forest算法^［52］，更好地發揮了集成學習的作用。

（3）最大化分離半監督學習方法

最大化分離半監督學習方法（也稱最大間隔分割半監督學習方法）是一種利用聚類假設中的低密度分割思想的半監督學習算法。在該算法中，未標記數據起到探索數據分布的稠密和稀疏區域的作用，并使決策邊界出現于低密度數據區，保證不同類別的數據用最大的間隔（Maximum Margin）分割開來。基于支持向量機（Support Vector Machine，SVM）、高斯過程（Gaussian Process，GP）^［53］、信息正則化^［54］及最小化熵^［55］的半監督學習均屬于最大化分離半監督學習方法。直推式支持向量機（Transductive Support Vector Machine，TSVM）^［27］是最早提出的也是最具代表性的一種最大化分離半監督學習方法，以下以直推式支持向量機為例對最大化分離半監督學習方法進行詳細介紹。

在監督學習方法中，支持向量機只利用已標記樣本在數據空間中構造一個最優超平面，使得兩類樣本具有最大分類間隔，而在半監督學習中，樣本集中既有已標記樣本又有未標記樣本，因而數據間隔難以得到確切的描述，這就需要對問題進行適當的松弛，一般是通過施加一個弱約束條件來實現。直推式支持向量機在構造最優分類超平面時將未標記樣本也考慮進來，使得原始的標記樣本和未標記樣本均以最大的間隔被分離，同時最優分類邊界在對原始未標記樣本分類時應具有最小泛化誤差。

由于有效利用了隱含在未標記樣本中的分布特性信息，直推式支持向量機的分類效果比單純基于標記樣本的傳統支持向量機分類效果有了顯著提高，然而直推式支持向量機本身仍然有需改進的地方。對于二分類問題，樣本類別標記有正標記和負標記兩種，直推式支持向量機在執行前要求人工設定未標記樣本中的具有正標記的樣本個數K，而在實際過程中很難準確給出K值的估計。在直推式支持向量機中K值的估算通常采用一種簡單的方法實現，即由正標記樣本在標記樣本中所占比例來對K值進行估計。這種做法在標記樣本集規模較小的條件下很可能導致較大的估計誤差，而當K的估計值與真實的正標記樣本個數相差較大時，分類器性能將迅速下降。從另一個角度來說，由于有標記樣本通常是經人工處理和選取的，而不是隨機采樣獲得的，因此根據其標記分布來估計整個樣本集中正負標記的大致比例是不合理的。即使隨機選取得到有標記樣本，由于直推式向量機能用到的有標記樣本集規模往往較小，據其對樣本全集分布的估計也常常是不準確的。對K值的錯誤估計，將導致直推式支持向量機產生一個無法正確反映樣本分布特性的分類器。直推式支持向量機的實用價值在很大程度上被這一缺陷所限制。在基本直推式支持向量機基礎上，漸進直推式支持向量機（Progressive Transduetive SVM，PTSVM）^［56］有效解決了K值難以估計的問題。漸進直推式支持向量機在進行訓練之前，并不估計未標記樣本的分布特性，而是在訓練過程中，每次選擇1～2個可能對后續訓練過程造成較大影響的未標記樣本，標以當前條件下最可能的類標，并將其歸入到有標記樣本集，再重新進行下一輪的訓練。一般情況下，新樣本的加入會影響到新一輪的訓練過程，并使當前分割平面發生些許偏移。在每一次訓練中，可能會發現先前的部分標記是不合適的，這時則需要取消這些不合適的標記，將其恢復為未標記的狀態。

直推式支持向量機作為一種最大化分離半監督學習方法，受到國內外研究學者越來越多的關注，成為半監督學習的一個代表性方法。Bruzzone等^［57］將二值分類的直推式支持向量機推廣到多值分類問題，并將直推式支持向量機成功應用于復雜遙感圖像的地物分類問題。Zhang等^［58］提出一種最小二乘直推式支持向量機，即對傳統直推式支持向量機的目標函數由非凸函數向凸函數轉換，以簡化直推式支持向量機的求解過程，同時帶來性能上的提升。Li等^［59］以直推式支持向量機為基礎提出一種迭代式半監督支持向量機，通過特征重提取，成功解決了對未標記樣本的學習過程中的誤差累積問題。Adankon等^［60］結合遺傳算法來求解直推式支持向量機使用的非凸目標函數的優化問題，進一步提升了直推式支持向量機的分類精度。此外，一些學者嘗試在直推式支持向量機中引入包括半正定規劃（Semi-definite Programming）、局部組合搜索（Local Combinatorial Search）、梯度下降（Gradient Descent）、延拓技術（Continuation Techniques）、凸凹過程（Convex-concave Procedures）、確定性退火技術（Deterministic Annealing）以及不可微分方法（Non-differentiable Methods）在內的多種優化技術來提升半監督學習的性能^［61-63］。

（4）基于圖的半監督學習方法

基于圖的半監督學習方法直接或間接地利用流形假設，在學習過程中首先基于訓練樣本的特定相似度度量建立圖，圖中各節點對應（有標記或是未標記）樣本，節點間的連接表示樣本間的相似度，之后定義模型的優化目標函數，并根據圖的平滑性，添加相應的正則化項得到決策函數，通過最小化決策函數計算模型參數的最優值。

基于圖模型的半監督學習方法中較有代表性的方法有Mincut方法^［64］、Tikhonov正則化方法^［65］、馬爾可夫隨機漫步法（Markov Random Walk）^［66］、圖-核方法（Graph Kernels）^{［67，68］}和流形方法（Manifold Method）^［69］等。其中流形方法在近年來受到較為廣泛的關注。流形方法認為，分類邊界在子流形上可以比在原空間中更為容易識別，基于此設想，流形方法把處于高維空間的樣本映射到低維流形上以達到簡化分類的目的。流形學習方法是一種非參數方法，即對流形的參數不需要進行先驗假設。目前基于流形的半監督學習方法主要包括譜映射（Spectral Projection）方法^［70］、基于局部和全局一致性（Local and Global Consistency）的方法^［71］、基于高斯域和調和函數（Gaussian Fields and Harmonic Functions）的方法^［72］以及黎曼流形最小誤差映射（Riemannian Manifolds and Mapping for Minimum Error Sum）方法^［73］等。這些基于流形的半監督學習方法在低維映射過程中，都會事先設定一個能量函數來確認低維空間比原空間具有更加突出的類別分界線。基于流形的半監督學習方法所采用的能量函數，可以統一表示為

式中：t為樣本在低維流形上的坐標值（或者是樣本的類別標記）；E（t）為t坐標值上的能量函數；w_ij為圖模型中各個樣本點間連接的權值；i和j為第i個和第j個樣本；N為樣本個數。

以極小化E（t）為優化目標，該映射過程的含義是，在原樣本空間內距離較近的樣本點投影到低維流形上也應該相互接近，即應趨于相同的類標。近年來，基于圖模型的半監督學習方法得到了越來越多相關學者的關注。Camps-Valls等^［67］通過流形半監督學習從高光譜遙感圖像中發掘出了未標記樣本的類別特征信息，并且成功地克服了高光譜遙感圖像分類中存在的不適定問題。Kulis等^［74］結合核聚類算法與圖模型，利用基于圖的半監督分類方法實現了對向量數據和圖形數據的同時處理。構建合理的圖模型權值矩陣是基于圖的半監督學習方法的關鍵，針對這一關鍵問題Yang等^［75］提出一種子空間半監督學習框架，該框架使得圖模型的權值矩陣的求解更容易，這種框架方法已成功應用于降維問題中。Zhong等^［76］提出的基于圖模型的半監督學習方法，將若干圖模型整合為統一框架，很好地解決了半監督特征選擇中存在的未標記樣本利用效率低的問題。Rohban等^［77］提出一種新的方法來對半監督圖模型中邊權值進行更新，該方法能有效降低個別強勢節點對相鄰節點的不良影響，并實現半監督圖模型的整體性能的優化。Wang等^［78］指出大部分基于圖的半監督學習方法僅以距離作為樣本點之間相似性的唯一判斷標準的做法會導致嚴重的分類誤差，在基于圖的半監督分類方法中引入近鄰相似性測量（Neighborhood Similarity Measure）技術，該技術使得半監督學習方法在充分考慮到樣本間距離相似性的同時，考慮局部分布的差異性，從而能有效提高基于圖模型的半監督學習方法的分類精度。