本次要分享的是 14 年論文 DeepWalk: Online learning of Social Representations， 論文鏈接DeepWalk^[1]，參考的代碼CODE^[2]，本論文是圖表示學(xué)習(xí)領(lǐng)域內(nèi)的一篇較早的文章，是學(xué)習(xí)圖表示學(xué)習(xí)繞不過的一篇文章，雖然整體難度不大，但是文章所提出的方法個(gè)人感覺非常獨(dú)到和有趣。

論文動(dòng)機(jī)和創(chuàng)新點(diǎn)

• 本論文提出的是一種針對(duì)圖結(jié)構(gòu)的representation learning 方法，其從某種角度來說機(jī)器學(xué)習(xí)或深度學(xué)習(xí)的發(fā)展就是圍繞著representation learning 方法進(jìn)行的。

• 在自然語言處理領(lǐng)域，word2vec（以前總結(jié)的 word2vec^[3]）是一個(gè)非常基礎(chǔ)和著名的詞表示方法，利用 句子 中詞與詞之間的共現(xiàn)或相鄰關(guān)系，對(duì)詞進(jìn)行表示學(xué)習(xí)，所學(xué)習(xí)到的詞表示向量能準(zhǔn)確的刻畫詞與詞之間的實(shí)際意義關(guān)系。

• 那么在非語言結(jié)構(gòu)的其他結(jié)構(gòu)中，例如圖結(jié)構(gòu)中，是否可以根據(jù)圖中節(jié)點(diǎn)與節(jié)點(diǎn)相鄰關(guān)系，來學(xué)習(xí)每個(gè)節(jié)點(diǎn)的表示呢？顯然是可以的，論文中提出，在圖結(jié)構(gòu)中，以任意一個(gè)節(jié)點(diǎn)為起始節(jié)點(diǎn)，進(jìn)行隨機(jī)游走，當(dāng)游走到最長(zhǎng)的步數(shù)時(shí)，可以獲取一串由節(jié)點(diǎn)構(gòu)成的序列，這個(gè)序列就可以類比自然語言中的句子，節(jié)點(diǎn)類比句子中的詞，然后利用 word2vec 的方法對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行表示學(xué)習(xí)。

• 該論文所提出的方法是一種無監(jiān)督的特征學(xué)習(xí)方法，具體來說，就是從可截?cái)嗟碾S機(jī)游走中得到一串節(jié)點(diǎn)序列，利用 word2vec 方法學(xué)習(xí)每個(gè)節(jié)點(diǎn)的表示向量。我們認(rèn)為這樣學(xué)習(xí)到的表示向量可以捕捉到節(jié)點(diǎn)之間的鄰近相似關(guān)系以及其所屬社區(qū)（類別）的關(guān)系。

• 論文中講到所提方法有以下特點(diǎn) ① 適應(yīng)性：在實(shí)際的社交網(wǎng)絡(luò)中，由社交關(guān)系產(chǎn)生的圖是不斷發(fā)展的，而該方法可以自適應(yīng)的去學(xué)習(xí)，不必重復(fù)從頭再學(xué)習(xí)。② 社區(qū)意識(shí)：該方法學(xué)習(xí)到的隱空間應(yīng)該表示網(wǎng)絡(luò)中同質(zhì)節(jié)點(diǎn)或相鄰節(jié)點(diǎn)的距離遠(yuǎn)近信息。③ 低維度：當(dāng)帶標(biāo)簽的數(shù)據(jù)稀疏和低維度時(shí)，模型生泛化能力更好，訓(xùn)練更容易收斂。④ 連續(xù)性：該方法所學(xué)習(xí)到的表示是連續(xù)型的，因此具有光滑的決策邊界，魯棒性更高。

• 論文實(shí)驗(yàn)證明了，在缺乏足夠的帶標(biāo)簽數(shù)據(jù)時(shí)，本文所提方法比其他的無監(jiān)督表征學(xué)習(xí)方法效果上更好。

• 個(gè)人感覺，本論文在實(shí)驗(yàn)部分，某些細(xì)節(jié)并未講清，例如圖是如何構(gòu)建的？節(jié)點(diǎn)和邊的具體業(yè)務(wù)意義是什么？并未講清，只是籠統(tǒng)的說，利用這些數(shù)據(jù)構(gòu)圖，有多少個(gè)節(jié)點(diǎn)，多少條邊。

• 在實(shí)際應(yīng)用時(shí)，需根據(jù)業(yè)務(wù)邏輯，定義節(jié)點(diǎn)，以及根據(jù)某種規(guī)則定義連接節(jié)點(diǎn)的邊，由此可以構(gòu)成一張圖進(jìn)行表示學(xué)習(xí)。

Learning Social Representations

圖的定義

在社交網(wǎng)絡(luò)中多分類任務(wù)為例：

V 表示圖中的節(jié)點(diǎn)，節(jié)點(diǎn)的含義為圖中的類別(member)。E 表示圖中的邊，??表示一個(gè)帶標(biāo)簽的圖，其中， S 表示節(jié)點(diǎn)的特征空間大小，，??表示類別個(gè)數(shù)。

在實(shí)際應(yīng)用中，是需要根據(jù)業(yè)務(wù)的具體邏輯去構(gòu)建圖。傳統(tǒng)的機(jī)器學(xué)習(xí)方法是由 X 映射到 Y，模型所需要學(xué)習(xí)的是如何準(zhǔn)確的學(xué)習(xí)到這個(gè)映射函數(shù)。而本論文所提方法是獨(dú)立于標(biāo)簽的分布信息，由圖中的拓?fù)湫畔⑷W(xué)習(xí)節(jié)點(diǎn)的向量表示。是完全無監(jiān)督學(xué)習(xí)方法。

該方法所學(xué)習(xí)到的表示向量可以使用在任何的分類算法中。

隨機(jī)游走

以任意一個(gè)節(jié)點(diǎn)為起始節(jié)點(diǎn)，每次隨機(jī)的選擇與它鄰近節(jié)點(diǎn)進(jìn)行游走，直到達(dá)到最大步長(zhǎng)。這種截?cái)嗟碾S機(jī)游走方式提供了兩個(gè)優(yōu)點(diǎn)

• 局部探索游走很容易并行化進(jìn)行，幾個(gè)不同 walker 可以同時(shí)游走多條不同的線路。

• 從截?cái)嚯S機(jī)游走中獲取信息，當(dāng)圖結(jié)構(gòu)發(fā)生小的變化時(shí)，不需要重復(fù)重新的去學(xué)習(xí)。

在實(shí)際應(yīng)用時(shí)，方便很多。

長(zhǎng)尾分布

在論文指的是 power laws，其實(shí)和長(zhǎng)尾分布大同小異，在自然語言領(lǐng)域，我們發(fā)現(xiàn)大部分詞的詞頻都很小，只有少數(shù)詞的詞頻很高，符合長(zhǎng)尾分布。而在 YouTube Social Graph 中，進(jìn)行隨機(jī)游走，發(fā)現(xiàn)節(jié)點(diǎn)的分布也是符合這種長(zhǎng)尾分布的，如下圖所示：詞頻分布和節(jié)點(diǎn)頻率分布一致，因此認(rèn)為在自然語言處理領(lǐng)域內(nèi)有效的 word2vec 方法可以復(fù)用在圖結(jié)構(gòu)中。

Deep Walk

在這里插入圖片描述

以上兩個(gè)算法流程已經(jīng)能很好的說明 Deep Walk 的步驟，其中 SkipGram 算法表示由某個(gè)節(jié)點(diǎn)預(yù)測(cè)他周圍的節(jié)點(diǎn)，是 word2vec 方法中的一種模型。上述公式表示，由節(jié)點(diǎn)?來預(yù)測(cè)與之相鄰的周圍節(jié)點(diǎn)，其中所得到的副產(chǎn)品?這個(gè) embedding 矩陣就是我們要學(xué)習(xí)的目標(biāo)。

和自然語言處理相同，這里的 skip-Gram 同樣面臨計(jì)算復(fù)雜度很高的問題，如果不做任何處理，每次都需要對(duì)所有節(jié)點(diǎn)進(jìn)行概率計(jì)算，時(shí)間復(fù)雜度過高，訓(xùn)練緩慢，由此引入了 Hierarchical Softmax。

Hierarchical Softmax 是 NLP 中常用方法，詳情可以查看Hierarchical Softmax^[4]。其主要思想是以詞頻構(gòu)建 Huffman 樹，樹的葉子節(jié)點(diǎn)為詞表中的詞，相應(yīng)的高頻詞距離根結(jié)點(diǎn)更近。當(dāng)需要計(jì)算生成某個(gè)詞的概率時(shí)，不需要對(duì)所有詞進(jìn)行 softmax 計(jì)算，而是選擇在 Huffman 樹中從根結(jié)點(diǎn)到該詞所在結(jié)點(diǎn)的路徑進(jìn)行計(jì)算，得到生成該詞的概率，時(shí)間復(fù)雜度從 O(N) 降低到 O(logN)（N 個(gè)結(jié)點(diǎn)，則樹的深度 logN）。該方法同樣適用在圖結(jié)構(gòu)的 skip-Gram 模型中。

實(shí)驗(yàn)

論文中使用了三個(gè)數(shù)據(jù)集：

但是論文沒有詳細(xì)給出在三個(gè)數(shù)據(jù)集中，所構(gòu)成的圖結(jié)構(gòu)中節(jié)點(diǎn)以及邊的實(shí)際業(yè)務(wù)意義，例如在圖中，每個(gè)數(shù)據(jù)集中節(jié)點(diǎn)具體指的是什么？以什么樣的規(guī)則來定義邊的？

論文實(shí)驗(yàn)中，隨機(jī)抽取部分樣本作為訓(xùn)練集（帶 label），剩余的作為測(cè)試集，在訓(xùn)練集中，以上面所說的方式（DeepWalk+Skip-Gram+Hierarchical softmax）學(xué)習(xí)每個(gè)節(jié)點(diǎn)的表示向量，然后以學(xué)習(xí)到的表示向量作為特征，LR 分類器進(jìn)行訓(xùn)練，訓(xùn)練出一個(gè)分類模型；再在測(cè)試集上進(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果如下：可以看出當(dāng)選取較少的帶 label 訓(xùn)練數(shù)據(jù)時(shí)（label sparse），相對(duì)于其他方法，DeepWalk 的效果更好。

個(gè)人總結(jié)

本文所提方法不難，其 word2vec 也是很基礎(chǔ)的方法，但是能借此應(yīng)用到圖結(jié)構(gòu)中的確很有趣和有意義，使得 word2vec 這種簡(jiǎn)單有效的方法能應(yīng)用的更加廣泛。

參考資料

[1]

DeepWalk: http://www.perozzi.net/publications/14_kdd_deepwalk.pdf

[2]

CODE: https://github.com/phanein/deepwalk

[3]

以前總結(jié)的word2vec: https://blog.csdn.net/Mr_tyting/article/details/80091842

[4]

Hierarchical Softmax: https://blog.csdn.net/itplus/article/details/37969979

關(guān)于本站

“機(jī)器學(xué)習(xí)初學(xué)者”公眾號(hào)由是黃海廣博士創(chuàng)建，黃博個(gè)人知乎粉絲23000+，github排名全球前110名（32000+）。本公眾號(hào)致力于人工智能方向的科普性文章，為初學(xué)者提供學(xué)習(xí)路線和基礎(chǔ)資料。原創(chuàng)作品有：吳恩達(dá)機(jī)器學(xué)習(xí)個(gè)人筆記、吳恩達(dá)深度學(xué)習(xí)筆記等。

往期精彩回顧

• 那些年做的學(xué)術(shù)公益-你不是一個(gè)人在戰(zhàn)斗

• 適合初學(xué)者入門人工智能的路線及資料下載

• 吳恩達(dá)機(jī)器學(xué)習(xí)課程筆記及資源（github標(biāo)星12000+，提供百度云鏡像）
  

• 吳恩達(dá)深度學(xué)習(xí)筆記及視頻等資源（github標(biāo)星8500+，提供百度云鏡像）

• 《統(tǒng)計(jì)學(xué)習(xí)方法》的python代碼實(shí)現(xiàn)（github標(biāo)星7200+）
  

• 精心整理和翻譯的機(jī)器學(xué)習(xí)的相關(guān)數(shù)學(xué)資料

• 首發(fā)：深度學(xué)習(xí)入門寶典-《python深度學(xué)習(xí)》原文代碼中文注釋版及電子書

備注：加入本站微信群或者qq群，請(qǐng)回復(fù)“加群”

加入知識(shí)星球（4300+用戶，ID：92416895），請(qǐng)回復(fù)“知識(shí)星球”

總結(jié)

以上是生活随笔為你收集整理的员外陪你读论文：DeepWalk: Online learning of Social Representations的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。