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

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

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

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

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

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

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