基于圖的半監督學習方法綜述

韓靈珊

摘 要 半監督學習是機器學習中結合監督學習和無監督聚類方法的一類學習方法。基于圖的半監督學習憑借其直觀性得到了半監督學習領域專家的青睞。本文對常用的半監督學習方法進行了介紹和闡述，介紹了基于圖的半監督學習的發展現狀，并對未來基于圖的半監督學習的發展做出展望。

關鍵詞 基于圖的半監督分類 機器學習 圖方法

中圖分類號：TP181 文獻標識碼：A

0引言

基于圖的半監督學習憑借其直觀性也逐漸被更多的學者所研究和使用。本文主要介紹了目前使用較多的基于圖的半監督學習的方法分類；介紹了基于圖的半監督學習目前的研究成果及現狀；最后給出基于圖的半監督學習下一步更待研究的方向。

1基于圖的半監督學習方法分類

1.1圖的構造及正則化框架

首先利用樣本集X構造一個無向加權圖G。圖當中的每個頂點代表了樣本集中的樣本，圖當中邊的權值表示了樣本對和之間的相似度；構造完圖之后，基于圖的學習方法通常假設樣本標簽在圖中的分布是平滑的，并由此根據邊的連接情況使已標記樣本的類別標簽在整個圖上不斷傳播并達到最終完成對未標記樣本的類別標簽的預測。通常，樣本對之間的相似度采用高斯核函數來計算。

圖模型構造好后，基于圖的半監督學習算法需要定義一個函數f。我們將基于圖的學習方法規范化，提出基于圖的學習的正則化框架。對于已標記樣本，令（f） 為損失函數，用來調節函數f分類標簽時預測標簽與真實標簽值之間的損失或誤差；令（f）為目標函數的調整項，使標簽分布在整個圖上并且有足夠的平滑性，通常采用引入正則項的方法來確保。一般而言，基于圖的學習方法通常都利用圖的拉普拉斯性質作為目標函數的調整項，以確保標簽能夠平滑的在整個圖上傳遞。

1.2基于圖的半監督學習方法分類

1.2.1標簽傳播算法

在標簽傳播算法中，使用的損失函數為，其中表示預測標簽概率，表示已標記樣本的真實標簽值，損失函數表示在標簽傳遞的過程中應當使預測的已標記樣本的標簽與真實標簽類別相同；在調整項中使用（f）=作為保障標簽在整個圖上的分布具有平滑性的調整項。

1.2.2圖的最小分割方法

圖的最小分割方法（graph mincut algorithm）是由Blum A在2002年提出的。它的主要思想是：在二分類問題中定義正標記樣本作為源點（source），負標記樣本作為匯點（sink），目標是：找到一個邊集，使得刪除該邊集之后能夠隔絕任意從源點到匯點的流量，并且最終找到的這個邊集為最小邊集。那些與源點連接的點被標記為正類，與匯點連接的點則被標記為負類。

1.2.3調和函數方法

基于高斯域（Gaussian fields）和調和函數（harmonic function）的方法，簡稱為調和函數方法，針對在圖的最小分割方法中未考慮樣本的分類概率的硬劃分（hard classification）的問題，采用了軟劃分（soft classification）的方法，將樣本的類別用取值連續的變量表示。

1.2.4局部全局一致性算法

Zhou等人在標簽傳播算法和調和函數方法的啟發下，提出基于局部與全局一致性的方法（learning with local and global consistency），簡稱LGC算法。LGC算法的調整項采用了對稱拉普拉斯矩陣，提高了分類的精度。保持局部一致性的目標就是要使該調節項最小。與調和函數的目標函數不同，LGC算法的損失項允許預測標簽與真實標簽之間有一定的誤差，并會使這種誤差最小化，使用這樣的方式保持樣本集的全局一致性。

2基于圖的半監督學習方法研究現狀

國外學者對基于圖的半監督學習研究起步較早。Yang等人在2007年時首次提出了利用LPA算法進行英漢雙語信息檢索；Raghavan U則在同年用圖方法進行網絡社區發現，用空手道俱樂部網和美國大學橄欖球網的實驗證明了其良好的檢測效果；此外，在降維研究方面也有不少較為成熟的成果：2004年，Argyrious等采用kd樹方法構造稀疏圖，通過線性系統的迭代計算加速分類學習的速度，Delalleau等通過基于所選樣本集的子集進行標記傳播并利用所選樣本與剩余樣本的關聯降低圖拉普拉斯矩陣的大小提出了一種無參數且支持直推式學習的算法。

我國在基于圖的半監督學習的研究方向上起步較晚，但發展迅速取得了不少成果。一方面，對算法本身進行了深入研究和改進。例如：王雪松等人在原算法基礎上提出了一種簡潔的優化算法，通過使用k近鄰圖代替全連接圖并且簡化目標函數，減少了參數造成的誤差影響；李明等人利用一種基于密度的快速聚類的方法對樣本數據先聚類后進行標簽傳遞，通過實驗最終證明在分類效果上該算法與原算法相比速度大幅提高；Wang等人利用線性近鄰傳遞思想，構建鄰接矩陣，提高分類效果并取得了好的成果。

另一方面，基于圖的半監督學習在其他學科領域發揮了支柱作用：丁宇新等研究中采用了局部全局一致性學習方法，以“人人網”數據作為實驗數據，對用戶的興趣與畢業學校進行預測；新浪微博也同樣利用了標簽傳播算法作為其背后的核心算法之一，進行更精準的廣告投放和內容投送。

3結論

通過對目前基于圖的半監督學習取得的進展和成果了解分析，從研究內容來看：基于圖的半監督學習的基礎理論研究已經成熟，并且其成果已經應用于許多實際問題中。如今，如何利用圖論知識優化構圖，尋找提高學習算法效率，減少計算開銷的新思路成為基于圖的半監督學習的熱點，也為今后的學習研究提供了大的發展空間；同時，如何將基于圖的半監督學習方法聯系到實際情況中，利用該方法對實際問題進行更好地挖掘和探索，從而利用隱含信息獲得知識。

參考文獻

[1] Chappele O，Scholkopf B.Semi-supervised learning[M].Cambridge：MIT Press，2006：193-196.

[2] Zhu X.J.and Ghahramani Z. Learning from labeled and unlabeled data with label propagation [R].Technical Report CMU-CALD-02-107.Carnegic Mellon University，2002：1-8.

[3] Blum A，Chawla S.Learning from labeled and unlabeled data using graph mincuts.Proceedings of the 18th International Conference on Machine Learning.Williamstorn，USA：Morgan Kaufmann Publisher，2001：19-26.

[4] Zhu X，Ghahramani Z，Lafferty J.Semi-supervised learning using Gaussian fields and harmonic functions[C]Proceedings of the 20th International Conference on Machine Learning.Washington：[s.n.]，2003：912-919.

[5] Zhou D，Bousquet O，Lal T N，et al.Learning with local and global consistency[C]Thrun S，Saul L，Schlkopf B，et al.Advances in Neural Information Processing Systems 16.Cambridge： MIT Press，2004：321-328.

[6] YANG L P，JI D H.Information Retrieval Using Label Propagation based ranking[C]，In： Proceedings of NTCIR-6 Workshop Meeting，Tokyo，Japan，2007：140-144.

[7] RAGBAVAN U N.ALBERT R. KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J].Physical Review E.2007（76）：1-12.

[8] Argyriou A.Efficient Approximation Methods for Harmonic Semi-supervised Learning [D].University College London，2004.

[9] Delalleau O.Bengio Y.and Roux N.L Efficient Non-parametric Function Induction in Semi-supervised Learning[A].Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics [C].New Jerscy，USA：Society for Artificial Intelligence and Statistics，2005：96-103.

[10] 王雪松，張曉麗，等.一種簡潔局部全局一致性學習[J].控制與決策，2011，26（11）：1726-1734.

[11] 李明.基于局部聚類與圖方法的半監督學習算法[J].自動化學報，2010，36（12）：1655-1660.

[12] Wang，Zhang.Label propagation through linear neighborhood[J].IEEE Trans on Knowledge and Data Engineering，2008，20（1）：55-67.

[13] 丁宇新，肖驍，等.基于半監督學習的社交網絡用戶屬性預測[J].通信學報，2014，35（8）：15-22.