數(shù)據(jù)驅(qū)動(dòng)的圖推斷算法研究.pdf

1、機(jī)器學(xué)習(xí)是近二十多年來發(fā)展起來的一門新興學(xué)科，在當(dāng)今的人工智能領(lǐng)域占有著舉足輕重的地位。其研究目的是設(shè)計(jì)計(jì)算機(jī)算法從已有的數(shù)據(jù)中總結(jié)、提取出一定的普適規(guī)律，以便對未來的數(shù)據(jù)進(jìn)行處理和分析。機(jī)器學(xué)習(xí)是計(jì)算機(jī)科學(xué)、統(tǒng)計(jì)學(xué)、認(rèn)知科學(xué)等多個(gè)領(lǐng)域的交叉學(xué)科，并且在公共安全、國防建設(shè)、生物醫(yī)學(xué)等方面獲得了廣泛的應(yīng)用。
　　作為機(jī)器學(xué)習(xí)的一種重要方法，圖推斷是指基于一個(gè)帶權(quán)圖，算法能夠給未標(biāo)記樣本直接分配明確的標(biāo)簽，而不是基于已有的已標(biāo)記樣本建

2、立一個(gè)普適的決策函數(shù)。另外，由于在很多情況下先驗(yàn)知識比較難獲得，因此本文主要研究如何直接根據(jù)已有數(shù)據(jù)設(shè)計(jì)不依賴于先驗(yàn)知識的數(shù)據(jù)驅(qū)動(dòng)的圖推斷算法。具體地，本文提出了一系列的迭代或者非迭代的圖推斷算法，介紹如下：
　　在第二章中，提出了一種非迭代算法——“基于變形拉普拉斯矩陣的標(biāo)簽預(yù)測”（Label Prediction via Deformed Graph Laplacian，LPDGL）。現(xiàn)有的算法多采用傳統(tǒng)的拉普拉斯矩陣去實(shí)現(xiàn)成

3、對樣本間標(biāo)簽的光滑性，與之不同的是通過在LPDGL中引入變形拉普拉斯矩陣，算法不僅獲得了現(xiàn)有的成對樣本光滑項(xiàng)，而且還導(dǎo)出了一種全新的局部光滑項(xiàng)。這個(gè)局部光滑項(xiàng)通過使用樣本的“度”來檢測其標(biāo)簽的不確定性，然后給度大的樣本施加置信的標(biāo)簽，而給度小的不確定樣本分配較弱的標(biāo)簽，進(jìn)而使設(shè)計(jì)的算法能夠產(chǎn)生比現(xiàn)有典型算法更魯棒的推斷結(jié)果。盡管LPDGL最初被設(shè)計(jì)用來做圖推斷，但它經(jīng)過簡單的擴(kuò)展后同樣可以處理圖歸納問題。
　　在第三章中，設(shè)計(jì)了一

4、種迭代的標(biāo)簽傳播算法用于圖推斷，即“基于菲克定律的標(biāo)簽傳播”（Fick’s Law Assisted Propagation，F(xiàn)LAP）。具體來說，F(xiàn)LAP把標(biāo)簽在圖上的傳播視為實(shí)際流體在一個(gè)平面上的擴(kuò)散，進(jìn)而根據(jù)著名的菲克流體定律設(shè)計(jì)了一種新的標(biāo)簽傳播算法?，F(xiàn)有的機(jī)器學(xué)習(xí)算法多基于一些啟發(fā)式的準(zhǔn)則，而FLAP則通過一種更“自然”的方式實(shí)施標(biāo)簽傳播，即一個(gè)樣本什么時(shí)候需要傳播多少標(biāo)簽，這些標(biāo)簽需要向哪里傳播，都是根據(jù)物理定律自然地決定的

5、。因此，F(xiàn)LAP不僅可以產(chǎn)生更準(zhǔn)確的傳播結(jié)果，而且比現(xiàn)有的迭代算法需要更少的計(jì)算時(shí)間。
　　在第四章中，提出了一種新的標(biāo)簽傳播框架——“導(dǎo)學(xué)與導(dǎo)教”（Teaching-to-Learn and Learning-to-Teach，TLLT）。在這個(gè)框架里，本文引入“老師”（即一種指導(dǎo)機(jī)器學(xué)習(xí)的導(dǎo)學(xué)算法）去指導(dǎo)標(biāo)簽傳播?，F(xiàn)有的傳播方法都是平等地看待所有未標(biāo)記樣本，而 TLLT認(rèn)為不同的樣本具有不同的分類難度，而且它們的傳播需要遵循由

6、易到難的順序。這樣做的好處在于之前學(xué)習(xí)的簡單樣本可以降低后續(xù)學(xué)習(xí)復(fù)雜樣本的難度，進(jìn)而有利于對這些難的樣本實(shí)施正確的分類。在每一次傳播的過程中，老師要給“學(xué)生”（即標(biāo)簽傳播算法）指定當(dāng)前最簡單的樣本。當(dāng)學(xué)生“學(xué)完”這些簡單的樣本后，老師會(huì)從學(xué)生那里獲取學(xué)習(xí)反饋以制定合適的下一輪待學(xué)習(xí)樣本。正是由于這種交互式的教與學(xué)的過程，所有未標(biāo)記樣本都按照精心制定的合理順序被傳播，因而所設(shè)計(jì)的方法可以獲得比其它方法更好的性能。
　　在第五章中，本