圖上的傳播學習研究及應用.pdf

1、目前,半監(jiān)督機器學習方法不但在理論方面得到了深入地研究,而且在實踐中已獲得了廣泛地應用。半監(jiān)督學習的基本出發(fā)點是同時利用已標號和未標號樣本進行學習,主要目的是借助隱含于未標號樣本中的結構信息來提高學習性能。由于數(shù)據(jù)的結構信息通?？梢杂靡粋€圖來表達,所以以圖表達為中心的半監(jiān)督學習方法成為了當前的研究主流之一。圖上的傳播學習正是基于圖表達的一類典型半監(jiān)督學習方法,其主要思想是:圖結點上的標號信息可以通過圖路徑從已標記(樣本)結點傳播到未標記

2、(樣本)結點,而連接兩結點的圖路徑數(shù)量和路徑長度可作為它們之間的一種相似度測量。最近,圖上的傳播學習方法已經(jīng)成功滲透到分類、聚類、排序和降維等諸多研究領域。
　　 然而,無論是在理論方面還是應用方面,圖傳播方法仍存在一些關鍵問題有待于解決。例如,(1)當需要傳播的對象是樣本間的成對約束而不是樣本的類別標號時,該如何進行約束傳播?(2)當沒有任何監(jiān)督信息可以利用時,該如何來發(fā)掘和改造圖傳播方法?(3)圖傳播方法是否能作為一種數(shù)據(jù)預

3、處理手段而不僅僅是作為一種特定的分類方法?(4)當傳播圖很大時,是否能在部分圖而不是全局圖上進行傳播?針對以上這些問題,本文對圖傳播方法進行了深入的研究,并得到了如下四個方面的研究成果:
　　 1.把約束傳播問題歸結為一個核矩陣學習問題,并由此提出了核傳播的概念。現(xiàn)有的標號傳播算法不能對樣本間的成對約束進行傳播,為此,我們把該問題轉化成一個核矩陣傳播問題。核矩陣傳播的主要思路是,首先通過求解一個小規(guī)模半定規(guī)劃問題把用戶提供的成對

4、約束信息編碼到一個小尺寸的“種子核”矩陣內(nèi),然后利用核傳播公式把該種子核矩陣傳播成為整個樣本集上的全核矩陣。特別地,在某種意義下,標號傳播方法能被解釋為核傳播方法的一個特例。相比于現(xiàn)有的同類型方法,我們的核傳播方法在實驗中表現(xiàn)出了更好的綜合性能。
　　 2.提出了基于流形收縮的無監(jiān)督數(shù)據(jù)預處理方法。傳統(tǒng)的標號傳播方法在無監(jiān)督情形下將失效,為此我們提出了一種名為流形收縮的無監(jiān)督數(shù)據(jù)預處理方法。一方面,流形收縮方法能夠被直觀地解釋成

5、為樣本點在圖上的一個隨機行走(Random walks)過程；另一方面,流形收縮方法相當于對原樣本集進行了一個收縮映射,而且可以把此映射作為一種數(shù)據(jù)預處理手段。此外,作為一種新的無監(jiān)督數(shù)據(jù)預處理技術,流形收縮方法不但能方便且自然地與核技巧、降維方法等相互結合,而且能從理論上保證更好的分類泛化能力。
　　 3.提出了基于模式移動的半監(jiān)督數(shù)據(jù)預處理方法。在部分樣本類別標號已知的情況下,傳統(tǒng)的標號傳播方法通常被作為一種特定的分類器來使

6、用,這限制了在傳播中進一步使用其它分類器的能力。為了能夠把圖傳播方法的優(yōu)勢方便地結合到普通的監(jiān)督型分類器中,我們提出了半監(jiān)督模式移動的概念,同時把它作為一種新的半監(jiān)督數(shù)據(jù)預處理手段。此外,我們還進一步提出了一種利用采樣技術進行算法加速的方案,并由此自然地解決了模式移動算法中的外樣本(Out-of-Sample)推廣問題。實驗結果表明,相比于一些半監(jiān)督降維方法,我們提出的半監(jiān)督模式移動方法具有一定的優(yōu)勢。
　　 4.提出了一種基于

7、子圖正則化的半監(jiān)督圖像檢索方法?；诜答伒膱D像檢索問題雖然可以作為一個普通的在線分類問題來對待,但它自身還具有小樣本性、類不平衡性和實時性要求等特點。Lu等人[1]提出的基于全圖正則化的支持向量機分類算法在應用到圖像檢索方面時沒有考慮到類不平衡性和實時性等問題,為此,我們提出了一種基于查詢子圖(而非全圖)正則化的半監(jiān)督圖像檢索算法,稱為偏拉普拉斯支持向量機(BLap SVM,Biased Laplacian Support Vector