圖上的傳播學(xué)習(xí)研究及應(yīng)用.pdf

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

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

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

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

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

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

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