deepwalk算法核心的步驟

在數(shù)據(jù)量越來越大的今天，word2vec是通過字詞的共現(xiàn)關(guān)系來學習字詞的向量表示，Graph Embeding的思想類似于word2vec，通過圖中節(jié)點與節(jié)點的共現(xiàn)關(guān)系來學習節(jié)點的向量表示，構(gòu)成文本序列從而計算相互關(guān)聯(lián)出現(xiàn)的詞的概率，從而計算詞向量表示文本。那么在圖模型中的關(guān)鍵的問題就是如何來描述節(jié)點與節(jié)點的共現(xiàn)關(guān)系，于是方法是利用DeepWalk來采樣這樣的文本序列，通過隨機游走(RandomWalk)的方式在圖中進行節(jié)點采樣，從而就能夠輸入序列計算圖的向量表示。所以deepwalk算法核心的步驟就是兩步：

RandomWalk

Skip-Gram

RandomWalk是一種可重復訪問已訪問節(jié)點的深度優(yōu)先遍歷算法。給定當前訪問起始節(jié)點，從其鄰居中隨機采樣節(jié)點作為下一個訪問節(jié)點，重復此過程，直到訪問序列長度滿足預設(shè)條件。

算法過程就是輸入一個圖，輸出節(jié)點表示的矩陣，簡單對步驟進行解析：

初始化：從 $\mathcal{U}^{|V| \times d}$ 樣本空間中采樣，embedding的大小為 $d$

構(gòu)建一棵二叉樹Hierarchical Softmax

開始做 $\gamma$ 步的隨機游走，這里的 $\gamma$ 是初始化好的超參數(shù)

打亂采樣得到的節(jié)點

這個循環(huán)是開始以每個節(jié)點為根節(jié)點開始做長度為 $t$ 的隨機游走，這里的 $t$ 為初始化的超參數(shù)。然后按窗口 $w$ 進行SkipGram學習文本序列

SkipGram

一般提到word2vec有兩種主要的算法，Cbow和Skip-Gram，都是在統(tǒng)計語言模型的基礎(chǔ)上計算一個詞在文本中出現(xiàn)的概率用來作為這個詞的表示向量，于是優(yōu)化目標就是最大化$Pr(w_n|w_0,w_1,...,w_{n-1})$ 。 $w$ 表示的就是詞。

SkipGram就是用當前詞來預測上下文。丟掉了詞序并且不考慮與當前詞的距離。優(yōu)化目標是最大化同一個句子中同時出現(xiàn)的詞的共現(xiàn)概率：

預測給到的詞從整個詞表vocabulary中選擇，因此在輸出的時候會計算softmax進行選擇，維度為 $|V|$ ，計算的維度會非常大，因此采用Hierarchical Softmax來構(gòu)建二叉樹進行選擇，每個詞就只需要計算 $log_2^{|V|}$ 次。

Node2Vec

node2vec依然采用的是隨機游走的方式獲取頂點的臨近頂點序列，但不同的是node2vec采用的是一種有偏的隨機游走。給定當前頂點 $v$，訪問下一個頂點的概率是：

$\pi{vx}$ 是頂點 $v$ 到頂點 $x$ 之間的轉(zhuǎn)移概率， $Z$ 是歸一化參數(shù)。 node2vec引入兩個超參數(shù) $p$ 和 $q$ 來控制隨機游走的策略，假設(shè)當前隨機游走經(jīng)過邊 $(v, x) $ 到達頂點 $t$ ，設(shè) $\pi{vx}=\alpha{pq}(t, x)\cdot w{vx}$ ， $w_{vx}$ 是頂點 $v$ 和 $x$ 之間的邊權(quán)。

$d{tx}$ 為頂點 $t$ 和頂點 $x$ 之間的最短路徑距離。參數(shù)$p$和參數(shù)$q$的意義：控制重復訪問剛剛訪問過的頂點的概率。$p$作用于$d{tx}=0$，表達的意義就是頂點$x$就是訪問當前頂點$v$之前剛剛訪問過的頂點。如果$p$較高，則訪問剛剛訪問過的頂點的概率會變低，反之變高。$q$控制著游走是向外還是向內(nèi)，如果$q>1$，隨機游走傾向于訪問和節(jié)點$t$相接近的頂點（類似于$BFS$）。如果$q<1$，則傾向于訪問遠離$t$的頂點（類似于$DFS$）。

Graph Convolutional Network

Graph Embedding的意義就在于能夠利用圖結(jié)構(gòu)處理非結(jié)構(gòu)化數(shù)據(jù)，因此在cv和nlp領(lǐng)域能夠更進一步結(jié)合先驗知識進行特征學習，因此是深度學習領(lǐng)域的重要發(fā)展方向。定義圖$G=(V,E)$，$V$為節(jié)點的集合，$E$為邊的集合，對于每個節(jié)點$i$， 均有其特征$x_i$，特征矩陣可以用$X_{N*D}$來表示，其中$N$表示節(jié)點數(shù)，$D$表示每個節(jié)點的特征編碼尺寸，在nlp應(yīng)用中就是embedding_size。對于圖的理解有一個經(jīng)典的思想：

圖中的每個結(jié)點無時無刻不因為鄰居和更遠的點的影響而在改變著自己的狀態(tài)直到最終的平衡，關(guān)系越親近的鄰居影響越大。

實際上從鄰居節(jié)點獲取信息的思想在很多領(lǐng)域都有應(yīng)用，例如：word2vec和pagerank。很多參考的理解描述了更加細節(jié)的數(shù)學原理：從傅立葉變換到拉普拉斯算子到拉普拉斯矩陣。很難理解。

責任編輯：haq