1半監督學習

(Semi-supervised

Learning)2有監督的學習：學習器通過對大量有標記的訓練例進行學習，從而建立模型用于預測未見示例的標記(label)。很難獲得大量的標記樣本。無監督的學習：無訓練樣本，僅根據測試樣本的在特征空間分布情況來進行標記，準確性差。半監督的學習：有少量訓練樣本，學習機以從訓練樣本獲得的知識為基礎，結合測試樣本的分布情況逐步修正已有知識，并判斷測試樣本的類別。機器學習4半監督學習的過程5傳統機器學習算法需要利用大量有標記的樣本進行學習。隨著信息技術的飛速發展，收集大量未標記的（unlabeled）樣本已相當容易，而獲取大量有標記的示例則相對較為困難，因為獲得這些標記可能需要耗費大量的人力物力。如何利用大量的未標記樣本來改善學習性能成為當前機器學習研究中備受關注的問題。

優點：半監督學習（Semi-supervised

Learning）能夠充分利用大量的未標記樣本來改善學習機的性能，是目前利用未標記樣本進行學習的主流技術。半監督學習背景6半監督學習的發展歷程未標記示例的價值實際上早在上世紀80年代末就已經被一些研究者意識到了。R.P.Lippmann.Patternclassificationusingneuralnetworks.IEEECommunications,1989,27(11):47-64.

一般認為，半監督學習的研究始于B.Shahshahani和D.Landgrebe的工作，最早是在這篇文章當中提到的。

B.Shahshahani,D.Landgrebe.Theeffectofunlabeledsamplesinreducingthesmallsamplesizeproblemandmitigatingthehughesphenomenon.IEEETransactionsonGeoscienceandRemoteSensing,1994,32(5):1087-1095.

D.J.Miller和H.S.Uyar

認為，半監督學習的研究起步相對較晚，可能是因為在當時的主流機器學習技術（例如前饋神經網絡）中考慮未標記示例相對比較困難。隨著統計學習技術的不斷發展，以及利用未標記示例這一需求的日漸強烈，半監督學習才在近年來逐漸成為一個研究熱點。D.J.Miller,H.S.Uyar.Amixtureofexpertsclassifierwithlearningbasedonbothlabelledandunlabelleddata.In:M.Mozer,M.I.Jordan,T.Petsche,eds.AdvancesinNeuralInformationProcessingSystems9,Cambridge,MA:MITPress,1997,571-5777在進行Web網頁推薦時，需要用戶標記出哪些網頁是他感興趣的，很少會有用戶愿意花大量的時間來提供標記，因此有標記的網頁示例比較少，但Web上存在著無數的網頁，它們都可作為未標記示例來使用。這類問題直接來自于實際應用：例如，大量醫學影像，醫生把每張片子上的每個病灶都標出來再進行學習，是不可能的，能否只標一部分，并且還能利用未標的部分？半監督學習的應用領域8半監督學習應用實例語音識別（Speechrecognition）文本分類（Textcategorization）詞義解析（Parsing）視頻監控（Videosurveillance）蛋白質結構預測（Proteinstructureprediction）9半監督學習的主要方法最大期望（EM算法）自訓練（Self-training)協同訓練（Co-training)轉導支持向量機（TransductiveSupportVectorMachines）基于圖的方法(graph-basedmethods)

現狀與展望101.最大期望（EM算法）背景：期望最大化（EM）方法和樸素貝葉斯方法有著共同的理論基礎。期望最大化是一種基于循環過程的最大似然參數估計方法，用于解決帶缺失數據的參數估計問題。是最早的半監督學習方法。前提：

樣本數據分為標記樣本和未標記樣本，按照統計的觀點，對于每一個樣本的產生，其背后都有一個模型，即樣本生成模型（generativemodels）。樣本生成模型的參數先由標記樣本確定，再通過標記樣本和利用當前模型判斷標記的未標記樣本共同調整。111.1EM算法的特點定義：具有隱狀態變量的分布中參數的最大似然估計。適用：能夠產生很好的聚類數據困難：如果把在參數下的期望為。那么，在估計狀態變量X時，估值當然應該用條件期望然而這時就需要知道參數的值；另一方面，為了知道，又必須先知道X的估值（作為狀態已知樣本值）121、設定初值2、（E-步驟）對，令3、（M-步驟）（修正的估計）取使之滿足：其中E-步驟為取條件期望（expectation），而M-步驟為取最大（maximum）。這種交替的方法稱為EM方法。優點：算法構思很簡單，并且在數學上有很嚴格的理論基礎缺點：計算量過大，對生成模型的依賴較大。1.2EM算法的具體步驟（解決方法）返回Figure:Ifthemodeliswrong,higherlikelihoodmayleadtolowerclassificationaccuracy.Forexample,(a)isclearlynotgeneratedfromtwoGaussian.IfweinsistthateachclassisasingleGaussian,(b)willhavehigherprobabilitythan(c).But(b)hasaround50%accuracy,while(c)ismuchbetter.Figure:Anexampleofunidentifiablemodels.Evenifweknownp(x)(top)isamixtureoftwouniformdistributions,wecannotuniquelyidentifythetwocomponents.Forinstance,themixturesonthesecondandthirdlinegivethesamep(x),buttheyclassifyx=0.5differently.152自訓練（Self-training）定義：首先利用已標記的樣本訓練分類器，然后利用已有未標記訓練樣本建立的模型標記，使用分類器選出置信度高的樣本加入訓練集中重新訓練，迭代這個過程，得到一個比較理想的分類器。適用：用監督學習分類器時很復雜或者是很難修正優點：簡單、容易實現。缺點：誤差也同時會自我迭代放大。返回163協同訓練（Co-training）背景：最早是1998年由A.Blum和T.Mitchell在Combininglabeledandunlabeleddatawithco-training.In:Proceedingsofthe11thAnnualConferenceonComputationalLearningTheory(COLT’98),Wisconsin,MI,1998,92-100.提出來的，在當時來說可謂是半監督學習的核心主流算法。

定義：假設特征能夠分成兩個集，這兩個數據集是獨立同分布的。每個子特征集能夠訓練一個很好的分類器。每個分類器把未標記的樣本分出來給另一個分類器，選擇出置信度高的新的為標記樣本進行標記，重復上面的過程。適用：特征能夠很好的分成兩類。缺點：大多數的問題并不具有“充分大”的屬性集，而且隨機劃分視圖這一策略并非總能奏效，Figure:Co-Training:Conditionalindependentassumptiononfeaturesplit.Withthisassumptionthehighconfidentdatapointsinx1view,representedbycircledlabels,willberandomlyscatteredinx2view.Thisisadvantageousiftheyaretobeusedtoteachtheclassifierinx2view.183.1協同訓練的改進S.Goldman和Y.Zhou提出了一種不需要充分冗余視圖的協同訓練算法。他們用不同的決策樹算法，從同一個屬性集上訓練出兩個不同的分類器，每個分類器都可以把示例空間劃分為若干個等價類。他們

又對該算法進行了擴展，使其能夠使用多個不同種類的分類器。tri-training算法：不僅可以簡便地處理標記置信度估計問題以及對未見示例的預測問題，還可以利用集成學習（ensemblelearning）來提高泛化能力193.2協同訓練的應用實例D.Yarowsky

在研究詞義消歧時，通過同時使用詞的局部上下文以及詞在文檔其他部分出現時的含義這兩部分信息，有效減少了對人工標注數據的需求量E.Riloff和R.Jones

在對名詞短語進行地理位置分類時，同時考慮了名詞短語本身及其出現的上下文。M.Collins和Y.Singer

進行名實體識別時，也同時使用了名實體的拼寫信息及名實體出現的上下文信息。返回20背景：TSVM是為了改進SVM在文本分類中本已出色的表現而做的更一步改進.使用SVM進行文本分類一個問題是難于建造出那么多的標記文檔，要么是可用的訓練數據本身就少，或者是用人工方法把無標記的文檔分類為有標記的文檔所花費的功夫無法承受。這樣就引出了TSVM。定義：是標準SVM在半監督學習當中的拓展，是通過加入約束項使得未標記數據落在Margin之外，即使得分類的超平面避開數據密度高的區域。這里的未標記樣本的特點就是使得決策面避開樣本的密集區。優點：考慮無標簽樣本對分類器的影響，并且結合SVM算法實現的一種高效的分類算法。適用：能夠用SVM的地方，自然想到用轉導支持向量機能夠獲得更好的效果缺點：時間復雜度比較高，需要預先設置正負比例等的不足。4轉導支持向量機（TSVM）返回215基于圖的方法定義：通過相似度度量將標記和未標記數據放在聯系起來的圖當中。實際當中，很多基于圖的方法就是基于圖估計一個函數這個函數需滿足下面兩個前提假設。對于已標記樣本點，盡可能的接近標記，表為在損失函數(lossfunction)的選擇。在整個圖上函數要比較平緩，表現為正交器regularizer。適用：具有相似特征的點往往被分在同一類當中22特點：不同的基于圖的方法大體上都差不多，只不過是損失函數和正規則器的選擇不同而已，其關鍵是要構建一個好的圖。

BlumandChawla(2001)posesemi-supervisedlearningasagraphmincut(alsoknownasst-cut)problem.Inthebinarycase,positivelabelsactassourcesandnegativelabelsactassinks.Theobjectiveistofindaminimumsetofedgeswhoseremovalblocksallflowfromthesourcestoth