半監(jiān)督學(xué)習(xí)綜述

1、1,半監(jiān)督學(xué)習(xí)綜述(Semi-supervisedLearning ),2,有監(jiān)督的學(xué)習(xí)：學(xué)習(xí)器通過對大量有標(biāo)記的訓(xùn)練例進(jìn)行學(xué)習(xí)，從而建立模型用于預(yù)測未見示例的標(biāo)記(label)。很難獲得大量的標(biāo)記樣本。 無監(jiān)督的學(xué)習(xí)：無訓(xùn)練樣本，僅根據(jù)測試樣本的在特征空間分布情況來進(jìn)行標(biāo)記，準(zhǔn)確性差。 半監(jiān)督的學(xué)習(xí)：有少量訓(xùn)練樣本，學(xué)習(xí)機(jī)以從訓(xùn)練樣本獲得的知識為基礎(chǔ)，結(jié)合測試樣本的分布情況逐步修正已有知識，并判斷測試樣本的類別。,機(jī)器學(xué)習(xí),4,半監(jiān)督學(xué)習(xí)的過程,5,傳統(tǒng)機(jī)器學(xué)習(xí)算法需要利用大量有標(biāo)記的樣本進(jìn)行學(xué)習(xí)。 隨著信息技術(shù)的飛速發(fā)展，收集大量未標(biāo)記的（unlabeled）樣本已相當(dāng)容易，而獲取大量有標(biāo)

2、記的示例則相對較為困難，因?yàn)楂@得這些標(biāo)記可能需要耗費(fèi)大量的人力物力。 如何利用大量的未標(biāo)記樣本來改善學(xué)習(xí)性能成為當(dāng)前機(jī)器學(xué)習(xí)研究中備受關(guān)注的問題。 優(yōu)點(diǎn)：半監(jiān)督學(xué)習(xí)（Semi-supervisedLearning）能夠充分利用大量的未標(biāo)記樣本來改善學(xué)習(xí)機(jī)的性能，是目前利用未標(biāo)記樣本進(jìn)行學(xué)習(xí)的主流技術(shù)。,半監(jiān)督學(xué)習(xí)背景,6,半監(jiān)督學(xué)習(xí)的發(fā)展歷程,未標(biāo)記示例的價(jià)值實(shí)際上早在上世紀(jì)80年代末就已經(jīng)被一些研究者意識到了。 R. P. Lippmann. Pattern classification using neural networks. IEEE Communications, 1989, 27

3、(11): 47-64 .,一般認(rèn)為，半監(jiān)督學(xué)習(xí)的研究始于B. Shahshahani和D. Landgrebe的工作，最早是在這篇文章當(dāng)中提到的。 B. Shahshahani, D. Landgrebe. The effect of unlabeled samples in reducing the small sample size problem and mitigating the hughes phenomenon. IEEE Transactions on Geoscience and Remote Sensing, 1994, 32(5): 1087-1095.,D.J. Mi

4、ller和H.S. Uyar 認(rèn)為，半監(jiān)督學(xué)習(xí)的研究起步相對較晚，可能是因?yàn)樵诋?dāng)時(shí)的主流機(jī)器學(xué)習(xí)技術(shù)（例如前饋神經(jīng)網(wǎng)絡(luò)）中考慮未標(biāo)記示例相對比較困難。隨著統(tǒng)計(jì)學(xué)習(xí)技術(shù)的不斷發(fā)展，以及利用未標(biāo)記示例這一需求的日漸強(qiáng)烈，半監(jiān)督學(xué)習(xí)才在近年來逐漸成為一個(gè)研究熱點(diǎn)。 D. J. Miller, H. S. Uyar. A mixture of experts classifier with learning based on both labelled and unlabelled data. In: M. Mozer, M. I. Jordan, T. Petsche, eds. Advances

5、in Neural Information Processing Systems 9, Cambridge, MA: MIT Press, 1997, 571-577,7,在進(jìn)行Web網(wǎng)頁推薦時(shí)，需要用戶標(biāo)記出哪些網(wǎng)頁是他感興趣的，很少會有用戶愿意花大量的時(shí)間來提供標(biāo)記，因此有標(biāo)記的網(wǎng)頁示例比較少，但Web上存在著無數(shù)的網(wǎng)頁，它們都可作為未標(biāo)記示例來使用。 這類問題直接來自于實(shí)際應(yīng)用：例如，大量醫(yī)學(xué)影像，醫(yī)生把每張片子上的每個(gè)病灶都標(biāo)出來再進(jìn)行學(xué)習(xí)，是不可能的，能否只標(biāo)一部分，并且還能利用未標(biāo)的部分？,半監(jiān)督學(xué)習(xí)的應(yīng)用領(lǐng)域,8,半監(jiān)督學(xué)習(xí)應(yīng)用實(shí)例,語音識別（Speech recognition

6、） 文本分類（Text categorization） 詞義解析（Parsing） 視頻監(jiān)控（Video surveillance） 蛋白質(zhì)結(jié)構(gòu)預(yù)測（Protein structure prediction）,9,半監(jiān)督學(xué)習(xí)的主要方法,最大期望（EM算法） 自訓(xùn)練（Self-training) 協(xié)同訓(xùn)練（Co-training) 轉(zhuǎn)導(dǎo)支持向量機(jī)（Transductive Support Vector Machines ） 基于圖的方法(graph-based methods),現(xiàn)狀與展望,10,1. 最大期望（EM算法）,背景 ：期望最大化（EM）方法和樸素貝葉斯方法有著共同的理論基礎(chǔ)。期望最

7、大化是一種基于循環(huán)過程的最大似然參數(shù)估計(jì)方法，用于解決帶缺失數(shù)據(jù)的參數(shù)估計(jì)問題。是最早的半監(jiān)督學(xué)習(xí)方法。 前提： 樣本數(shù)據(jù)分為標(biāo)記樣本和未標(biāo)記樣本，按照統(tǒng)計(jì)的觀點(diǎn)，對于每一個(gè)樣本的產(chǎn)生，其背后都有一個(gè)模型，即樣本生成模型（generative models）。樣本生成模型的參數(shù)先由標(biāo)記樣本確定，再通過標(biāo)記樣本和利用當(dāng)前模型判斷標(biāo)記的未標(biāo)記樣本共同調(diào)整。,11,1.1 EM算法的特點(diǎn),定義：具有隱狀態(tài)變量的分布中參數(shù)的最大似然估計(jì)。 適用：能夠產(chǎn)生很好的聚類數(shù)據(jù) 困難：如果把在參數(shù) 下的期望 為 。那么，在估計(jì)狀態(tài)變量X時(shí)，估值當(dāng)然應(yīng)該用條件期望然而這時(shí)就需要知道參數(shù) 的值；另一方面，為了知道

8、，又必須先知道X的估值（作為狀態(tài)已知樣本值）,12,1、設(shè)定初值 2、（E-步驟）對 ，令 3、（M-步驟）（修正的估計(jì)）取使之滿足： 其中E-步驟為取條件期望（expectation），而M-步驟為取最大（maximum）。這種交替的方法稱為EM方法。 優(yōu)點(diǎn)：算法構(gòu)思很簡單，并且在數(shù)學(xué)上有很嚴(yán)格的理論基礎(chǔ) 缺點(diǎn)：計(jì)算量過大，對生成模型的依賴較大。,1.2 EM算法的具體步驟（解決方法）,返回,Figure: If the model is wrong, higher likelihood may lead to lower classification accuracy. For examp

9、le, (a) is clearly not generated from two Gaussian. If we insist that each class is a single Gaussian, (b) will have higher probability than (c). But (b) has around 50% accuracy, while (c) is much better.,Figure: An example of unidentifiable models. Even if we known p(x) (top) is a mixture of two un

10、iform distributions, we cannot uniquely identify the two components. For instance, the mixtures on the second and third line give the same p(x), but they classify x = 0.5 differently.,15,2 自訓(xùn)練（Self-training）,定義：首先利用已標(biāo)記的樣本訓(xùn)練分類器，然后利用已有未標(biāo)記訓(xùn)練樣本建立的模型標(biāo)記，使用分類器選出置信度高的樣本加入訓(xùn)練集中重新訓(xùn)練，迭代這個(gè)過程，得到一個(gè)比較理想的分類器。 適用：用監(jiān)督

11、學(xué)習(xí)分類器時(shí)很復(fù)雜或者是很難修正 優(yōu)點(diǎn)：簡單 、容易實(shí)現(xiàn) 。 缺點(diǎn)：誤差也同時(shí)會自我迭代放大。,返回,16,3 協(xié)同訓(xùn)練（Co-training）,背景：最早是1998年由A.Blum和T.Mitchell在Combining labeled and unlabeled data with co-training. In: Proceedings of the 11th Annual Conference on Computational Learning Theory (COLT98), Wisconsin, MI, 1998, 92-100.提出來的，在當(dāng)時(shí)來說可謂是半監(jiān)督學(xué)習(xí)的核心主流算

12、法。 定義：假設(shè)特征能夠分成兩個(gè)集，這兩個(gè)數(shù)據(jù)集是獨(dú)立同分布的。每個(gè)子特征集能夠訓(xùn)練一個(gè)很好的分類器。每個(gè)分類器把未標(biāo)記的樣本分出來給另一個(gè)分類器，選擇出置信度高的新的為標(biāo)記樣本進(jìn)行標(biāo)記，重復(fù)上面的過程。 適用：特征能夠很好的分成兩類。 缺點(diǎn)：大多數(shù)的問題并不具有“充分大”的屬性集，而且隨機(jī)劃分視圖這一策略并非總能奏效，,Figure: Co-Training: Conditional independent assumption on feature split. With this assumption the high confident data points in x1 view,

13、represented by circled labels, will be randomly scattered in x2 view. This is advantageous if they are to be used to teach the classifier in x2 view.,18,3.1 協(xié)同訓(xùn)練的改進(jìn),S. Goldman和Y. Zhou提出了一種不需要充分冗余視圖的協(xié)同訓(xùn)練算法。他們用不同的決策樹算法，從同一個(gè)屬性集上訓(xùn)練出兩個(gè)不同的分類器，每個(gè)分類器都可以把示例空間劃分為若干個(gè)等價(jià)類。 他們 又對該算法進(jìn)行了擴(kuò)展，使其能夠使用多個(gè)不同種類的分類器。 tri-tra

14、ining算法：不僅可以簡便地處理標(biāo)記置信度估計(jì)問題以及對未見示例的預(yù)測問題，還可以利用集成學(xué)習(xí)（ensemble learning）來提高泛化能力,19,3.2 協(xié)同訓(xùn)練的應(yīng)用實(shí)例,D. Yarowsky 在研究詞義消歧時(shí)，通過同時(shí)使用詞的局部上下文以及詞在文檔其他部分出現(xiàn)時(shí)的含義這兩部分信息，有效減少了對人工標(biāo)注數(shù)據(jù)的需求量 E. Riloff和R. Jones 在對名詞短語進(jìn)行地理位置分類時(shí)，同時(shí)考慮了名詞短語本身及其出現(xiàn)的上下文。 M. Collins和Y. Singer 進(jìn)行名實(shí)體識別時(shí)，也同時(shí)使用了名實(shí)體的拼寫信息及名實(shí)體出現(xiàn)的上下文信息。,返回,20,背景：TSVM是為了改進(jìn)SV

15、M在文本分類中本已出色的表現(xiàn)而做的更一步改進(jìn).使用SVM 進(jìn)行文本分類一個(gè)問題是難于建造出那么多的標(biāo)記文檔，要么是可用的訓(xùn)練數(shù)據(jù)本身就少，或者是用人工方法把無標(biāo)記的文檔分類為有標(biāo)記的文檔所花費(fèi)的功夫無法承受。這樣就引出了TSVM。 定義：是標(biāo)準(zhǔn)SVM在半監(jiān)督學(xué)習(xí)當(dāng)中的拓展，是通過加入約束項(xiàng)使得未標(biāo)記數(shù)據(jù)落在Margin之外，即使得分類的超平面避開數(shù)據(jù)密度高的區(qū)域 。這里的未標(biāo)記樣本的特點(diǎn)就是使得決策面避開樣本的密集區(qū)。 優(yōu)點(diǎn)：考慮無標(biāo)簽樣本對分類器的影響，并且結(jié)合SVM算法實(shí)現(xiàn)的一種高效的分類算法。 適用：能夠用SVM的地方，自然想到用轉(zhuǎn)導(dǎo)支持向量機(jī)能夠獲得更好的效果 缺點(diǎn)：時(shí)間復(fù)雜度比較高，

16、需要預(yù)先設(shè)置正負(fù)比例等的不足。,4 轉(zhuǎn)導(dǎo)支持向量機(jī)（TSVM）,返回,21,5 基于圖的方法,定義：通過相似度度量將標(biāo)記和未標(biāo)記數(shù)據(jù)放在聯(lián)系起來的圖當(dāng)中。實(shí)際當(dāng)中，很多基于圖的方法就是基于圖估計(jì)一個(gè)函數(shù) 這個(gè)函數(shù)需滿足下面兩個(gè)前提假設(shè)。 對于已標(biāo)記樣本點(diǎn) ， 盡可能的接近標(biāo)記 ，表為在損失函數(shù)(loss function)的選擇。 在整個(gè)圖上函數(shù)要比較平緩，表現(xiàn)為正交器regularizer。 適用：具有相似特征的點(diǎn)往往被分在同一類當(dāng)中,22,特點(diǎn)：不同的基于圖的方法大體上都差不多，只不過是損失函數(shù)和正規(guī)則器的選擇不同而已，其關(guān)鍵是要構(gòu)建一個(gè)好的圖。 Blum and Chawla (2001

17、) pose semi-supervised learning as a graph mincut (also known as st-cut) problem. In the binary case, positive labels act as sources and negative labels act as sinks. The objective is to find a minimum set of edges whose removal blocks all flow from the sources to the sinks。 優(yōu)點(diǎn)：物理原理能夠很好的解釋。 缺點(diǎn)：目前對于圖的構(gòu)建研究還不是很深入。,5.1 基于圖的方法,一些隨機(jī)手寫字符數(shù)據(jù)集的樣本,A symmetrized Euclidean 2NN graph on some 1s and 2s. Label Propagation on this graph works well.,返回,25,半監(jiān)督學(xué)習(xí)的不足,通過半監(jiān)督學(xué)習(xí)利用未標(biāo)記示例后，有時(shí)不僅不能提高泛化能力，反而會使得性能下降。 在模型假設(shè)不符合真實(shí)情況