傳統的機器學習技術分為兩類,一類是無監督學習,一類是監督學習。
無監督學習隻利用未标記的樣本集,而監督學習則隻利用标記的樣本集進行學習。
但在很多實際問題中,隻有少量的帶有标記的資料,因為對資料進行标記的代價有時很高,比如在生物學中,對某種蛋白質的結構分析或者功能鑒定,可能會花上生物學家很多年的工作,而大量的未标記的資料卻很容易得到。
這就促使能同時利用标記樣本和未标記樣本的半監督學習技術迅速發展起來。
半監督學習理論簡述:
半監督學習有兩個樣本集,一個有标記,一個沒有标記.分别記作
Lable={(xi,yi)},Unlabled={(xi)}.并且數量上,L<<U.
1. 單獨使用有标記樣本,我們能夠生成有監督分類算法
2. 單獨使用無标記樣本,我們能夠生成無監督聚類算法
3. 兩者都使用,我們希望在1中加入無标記樣本,增強有監督分類的效果;同樣的,我們希望在2中加入有标記樣本,增強無監督聚類的效果.
一般而言,半監督學習側重于在有監督的分類算法中加入無标記樣本來實作半監督分類.也就是在1中加入無标記樣本,增強分類效果.
半監督學習的動力,motivation
某人讨論的時候,總是教導我們的詞,motivation.一下午四五遍地強調寫論文要有motivation.下面說說半監督學習的motivation.
1. 有标記樣本難以擷取.
需要專門的人員,特别的裝置,額外的開銷等等.
2. 無标記的樣本相對而言是很廉價的.
3. 還有一點就是機器學習的光輝前景.
半監督學習與直推式學習的差別:
這個網上也有論述.主要就是半監督學習是歸納式的,生成的模型可用做更廣泛的樣本;而直推式學習僅僅為了目前無标記樣本的分類.
簡單的說,前者使用無标記樣本,為了以後其他樣本更好的分類.
後者隻是為了分類好這些有限的無标記樣本.
下面幾個圖來生動形象地诠釋半監督的好處:
上圖中,隻有兩個标記樣本,X,O,剩下綠點是無标記的樣本.通過無标記樣本的加入,原來的分類界限從0移到了0.5處,更好地拟合了樣本的現實分布.
半監督學習算法分類:
1. self-training(自訓練算法)
2. generative models生成模型
3. SVMs半監督支援向量機
4. graph-basedmethods圖論方法
5. multiview learing多視角算法
6. 其他方法
接着簡單介紹上述的幾個算法
self-training算法:
還是兩個樣本集合:Labled={(xi,yi)};Unlabled= {xj}.
執行如下算法
Repeat:
1. 用L生成分類政策F;
2. 用F分類U,計算誤差
3. 選取U的子集u,即誤差小的,加入标記.L=L+u;
重複上述步驟,直到U為空集.
上面的算法中,L通過不斷在U中,選擇表現良好的樣本加入,并且不斷更新子集的算法F,最後得到一個最有的F.
Self-training的一個具體執行個體:最近鄰算法
記d(x1,x2)為兩個樣本的歐式距離,執行如下算法:
2. 選擇x = argmin d(x, x0). 其中x∈U,min x0∈L.也就是選擇離标記樣本最近的無标記樣本.
2. 用F給x定一個類别F(x).
3. 把(x,F(x))加入L中
上面算法中,也就是定義了self-training的”誤差最小”,也就是用歐式距離來定義”表現最好的無标記樣本”,再用F給個标記,加入L中,并且也動态更新F.
下面是這種算法的效果圖:
上圖從兩個點出發,不斷加入最近鄰點,不斷更新F.
上面的算法表現良好,當然更多的是表現不好.如下:
生成模型
生成算法來源于假設,比如我們假設原樣本滿足高斯分布,然後用最大釋然的機率思想來拟合一個高斯分布,也就是常用的高斯混合模型(GMM).
簡單介紹下高斯混合模型:
假設如下的樣本分布:
我們假設他們滿足高斯分布.
高斯分布的參數有: θ = {w1, w2, µ1, µ2, Σ1, Σ2}
利用最大釋然的思想,最大化如下機率:
p(x, y|θ) = p(y|θ)p(x|y, θ).
得到如下的假設分布:
順便貼一個介紹高斯混合模型日志:
javascript:void(0)
接着是我們的半監督生成算法:
樣本分布如下:
算法過後,得到如下分布:
對比這兩個圖,說明下高斯混合模型與半監督生成模型的差別:
這兩種方法的釋然函數不同,前者最大化标記樣本出現機率,後者加入了無标記樣本出現機率.
算法的具體實作,請參見E-M算法.
這樣生成的算法也有許多不良表現,如下:
假設原始的分布式這樣的:
通過GMM,它變成了這樣:
幾個需要注意的地方:
1. 高斯混合的局部收斂性
2. 減少無标記樣本的權值
半監督SVM,圖算法模型,流行模型等.
SVM的理論不再贅述,就是一個最優超平面:
偷一張很牛逼的SVM圖:
這些内容涵蓋比較廣泛,一篇日志裝不下.有興趣地可以進一步了解.
最後是小結
上兩張圖:
基于生成式模型的半監督學習方法
該類方法通常是把未标記樣本屬于每個類别的機率看成一組缺失參數,然後采用EM (expectation-maximization) 算法對生成式模型的參數進行極大似然估計。不同方法的差別在于選擇了不同的生成式模型作為基分類器,例如混合高斯(mixture
of Gaussians)[3]、混合專家 (mixture
of experts)[1]、樸素貝葉斯(na ve
Bayes)[4]。雖然基于生成式模型的半監督學習方法簡單、直覺,并且在訓練樣本,特别是有标記樣本極少時能夠取得比判别式模型更好的性能,但是當模型假設與資料分布不一緻時,使用大量的未标記資料來估計模型參數反而會降低學得模型的泛化能力[5]。由于尋找合适的生成式模型來為資料模組化需要大量領域知識,這使得基于生成式模型的半監督學習在實際問題中的應用有限。
基于低密度劃分的半監督學習方法
該類方法要求決策邊界盡量通過資料較為稀疏區域,以免把聚類中稠密的資料點分到決策邊界兩側。基于該思想,Joachims[6]提出了TSVM算法(如圖2所示,其中實線為TSVM的分類邊界、虛線為不考慮未标記資料的SVM分類邊界)。在訓練過程中,TSVM算法首先利用有标記的資料訓練一個SVM并估計未标記資料的标記,然後基于最大化間隔準則,疊代式地交換分類邊界兩側樣本的标記,使得間隔最大化,并以此更新目前預測模型,進而實作在盡量正确分類有标記資料的同時,将決策邊界“推”向資料分布相對稀疏的區域。然而,TSVM的損失函數非凸,學習過程會是以陷入局部極小點,進而影響泛化能力。為此,多種TSVM的變體方法被提出,以緩解非凸損失函數對優化過程造成的影響,典型方法包括确定性退火[7]、CCCP直接優化[8]等。此外,低密度劃分思想還被用于TSVM以外的半監督學習方法的設計,例如通過使用熵對半監督學習進行正則化,迫使學習到的分類邊界避開資料稠密區域[9]。
圖 2 TSVM算法示意圖[6]
基于圖的半監督學習方法
該類方法利用有标記和未标記資料建構資料圖,并且基于圖上的鄰接關系将标記從有标記的資料點向未标記資料點傳播(如圖3所示,其中淺灰色和黑色結點分别為不同類别的有标記樣本、空心結點為未标記樣本)。根據标記傳播方式可将基于圖的半監督學習方法分為兩大類,一類方法通過定義滿足某種性質的标記傳播方式來實作顯式标記傳播,例如基于高斯随機場與諧函數的标記傳播[10]、基于全局和局部一緻性的标記傳播[11]等;另一類方法則是通過定義在圖上的正則化項實作隐式标記傳播,例如通過定義流形正則化項,強制預測函數對圖中的近鄰給出相似輸出,進而将标記從有标記樣本隐式地傳播至未标記樣本[12]。事實上,标記傳播方法對學習性能的影響遠比不上資料圖建構方法對學習性能的影響大。如果資料圖的性質與資料内在規律相背離,無論采用何種标記傳播方法,都難以獲得滿意的學習結果。然而,要建構反映資料内在關系的資料圖,往往需要依賴大量領域知識。所幸,在某些情況下,仍可根據資料性質進行處理,以獲得魯棒性更高的資料圖,例如當資料圖不滿足度量性時,可以根據圖譜将非度量圖分解成多個度量圖,分别進行标記傳播,進而可克服非度量圖對标記傳播造成的負面影響[13]。基于圖的半監督學習方法有良好的數學基礎,但是,由于學習算法的時間複雜度大都為O(n3) ,故難以滿足對大規模未标記資料進行半監督學習的應用需求。
圖 3 标記傳播示意圖
協同訓練(co-training)的半監督算法