基于圖的半監(jiān)督學(xué)習(xí)方法綜述

韓靈珊

摘 要 半監(jiān)督學(xué)習(xí)是機(jī)器學(xué)習(xí)中結(jié)合監(jiān)督學(xué)習(xí)和無監(jiān)督聚類方法的一類學(xué)習(xí)方法?；趫D的半監(jiān)督學(xué)習(xí)憑借其直觀性得到了半監(jiān)督學(xué)習(xí)領(lǐng)域?qū)＜业那嗖A。本文對常用的半監(jiān)督學(xué)習(xí)方法進(jìn)行了介紹和闡述，介紹了基于圖的半監(jiān)督學(xué)習(xí)的發(fā)展現(xiàn)狀，并對未來基于圖的半監(jiān)督學(xué)習(xí)的發(fā)展做出展望。

關(guān)鍵詞 基于圖的半監(jiān)督分類 機(jī)器學(xué)習(xí) 圖方法

中圖分類號：TP181 文獻(xiàn)標(biāo)識碼：A

0引言

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

1基于圖的半監(jiān)督學(xué)習(xí)方法分類

1.1圖的構(gòu)造及正則化框架

首先利用樣本集X構(gòu)造一個(gè)無向加權(quán)圖G。圖當(dāng)中的每個(gè)頂點(diǎn)代表了樣本集中的樣本，圖當(dāng)中邊的權(quán)值表示了樣本對和之間的相似度；構(gòu)造完圖之后，基于圖的學(xué)習(xí)方法通常假設(shè)樣本標(biāo)簽在圖中的分布是平滑的，并由此根據(jù)邊的連接情況使已標(biāo)記樣本的類別標(biāo)簽在整個(gè)圖上不斷傳播并達(dá)到最終完成對未標(biāo)記樣本的類別標(biāo)簽的預(yù)測。通常，樣本對之間的相似度采用高斯核函數(shù)來計(jì)算。

圖模型構(gòu)造好后，基于圖的半監(jiān)督學(xué)習(xí)算法需要定義一個(gè)函數(shù)f。我們將基于圖的學(xué)習(xí)方法規(guī)范化，提出基于圖的學(xué)習(xí)的正則化框架。對于已標(biāo)記樣本，令（f） 為損失函數(shù)，用來調(diào)節(jié)函數(shù)f分類標(biāo)簽時(shí)預(yù)測標(biāo)簽與真實(shí)標(biāo)簽值之間的損失或誤差；令（f）為目標(biāo)函數(shù)的調(diào)整項(xiàng)，使標(biāo)簽分布在整個(gè)圖上并且有足夠的平滑性，通常采用引入正則項(xiàng)的方法來確保。一般而言，基于圖的學(xué)習(xí)方法通常都利用圖的拉普拉斯性質(zhì)作為目標(biāo)函數(shù)的調(diào)整項(xiàng)，以確保標(biāo)簽?zāi)軌蚱交脑谡麄€(gè)圖上傳遞。

1.2基于圖的半監(jiān)督學(xué)習(xí)方法分類

1.2.1標(biāo)簽傳播算法

在標(biāo)簽傳播算法中，使用的損失函數(shù)為，其中表示預(yù)測標(biāo)簽概率，表示已標(biāo)記樣本的真實(shí)標(biāo)簽值，損失函數(shù)表示在標(biāo)簽傳遞的過程中應(yīng)當(dāng)使預(yù)測的已標(biāo)記樣本的標(biāo)簽與真實(shí)標(biāo)簽類別相同；在調(diào)整項(xiàng)中使用（f）=作為保障標(biāo)簽在整個(gè)圖上的分布具有平滑性的調(diào)整項(xiàng)。

1.2.2圖的最小分割方法

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

1.2.3調(diào)和函數(shù)方法

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

1.2.4局部全局一致性算法

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

2基于圖的半監(jiān)督學(xué)習(xí)方法研究現(xiàn)狀

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

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

另一方面，基于圖的半監(jiān)督學(xué)習(xí)在其他學(xué)科領(lǐng)域發(fā)揮了支柱作用：丁宇新等研究中采用了局部全局一致性學(xué)習(xí)方法，以“人人網(wǎng)”數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，對用戶的興趣與畢業(yè)學(xué)校進(jìn)行預(yù)測；新浪微博也同樣利用了標(biāo)簽傳播算法作為其背后的核心算法之一，進(jìn)行更精準(zhǔn)的廣告投放和內(nèi)容投送。

3結(jié)論

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

參考文獻(xiàn)

[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] 王雪松，張曉麗，等.一種簡潔局部全局一致性學(xué)習(xí)[J].控制與決策，2011，26（11）：1726-1734.

[11] 李明.基于局部聚類與圖方法的半監(jiān)督學(xué)習(xí)算法[J].自動(dòng)化學(xué)報(bào)，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] 丁宇新，肖驍，等.基于半監(jiān)督學(xué)習(xí)的社交網(wǎng)絡(luò)用戶屬性預(yù)測[J].通信學(xué)報(bào)，2014，35（8）：15-22.