91插插插影视花花,夜夜看久久伊人,亚洲日韩人妻视频网址

基于矩陣分解

快速簡(jiǎn)潔，但屬性信息與結(jié)構(gòu)信息的融合比較困難。

1. Skip-Gram with Negative Sampling (SGNS)

損失函數(shù)

將中心詞 $w$ 與上下文 $c$ 的共現(xiàn)概率用sigmoid表示為
$\delta(\vec{w}^T\vec{c}) = \frac{1}{1+e^{-\vec{w}^T\vec{c}}}$
隨機(jī)抽取k個(gè)負(fù)樣本，則損失函數(shù)可寫(xiě)為
$L = -\sum_w \sum_c d(w,c)\left[ \log(\delta(\vec{w}^T\vec{c}))+k\mathbb{E_{c_n \sim P_D}}\log(\delta(-\vec{w}^T\vec{c_n})) \right]$

使用 $d(c)$ 表示語(yǔ)料中包含上下文 $c$ 的組合數(shù)量， $D$ 表示語(yǔ)料中所有 $(w,c)$ 組合對(duì)的集合， $c_n$ 為采樣到的上下文向量，服從分布 $P_D=\frac{d(c)}{|D|}$ 。

負(fù)樣本損失表示為 $\delta(-\vec{w}^T\vec{c})$ 有利于后續(xù)推導(dǎo)。

等價(jià)于SPMI的分解

對(duì) $L$ 中的 $(w,c)$ 進(jìn)行合并同類(lèi)項(xiàng)，得到

$L(w,c) = d(w,c)\log(\delta(\vec{w}^T\vec{c}))+kd(w)\frac{d(c)}{|D|}\log(\delta(-\vec{w}^T\vec{c}))$
對(duì) $x=\vec{w}^T\vec{c}$ 求導(dǎo)等零，得
$x=\vec{w}^T\vec{c}=\log(\frac{|D|d(w,c)}{d(w)d(c)})-\log(k)$
正好是逐點(diǎn)互信息(Pointwise Mutual Information)矩陣漂移Shifted了 $log(k)$ ，即SPMI。

PMI中元素為 $PMI(x,y)=\log\frac{P(x,y)}{P(x)P(y)}$ 。

PMI矩陣中的無(wú)關(guān)向量為 $-\infty$ ，可以規(guī)定只要positive，得到PPMI，即 $PPMI=max(PMI,0)$ 。

兩者結(jié)合，得SPPMI(Shifted Positive PMI)矩陣，即 $SPPMI_k(w,c)=max(PMI(w,c)-log(k),0)$ 。

這里證明為了方便，只在兩個(gè)節(jié)點(diǎn)之間進(jìn)行了化簡(jiǎn)和推導(dǎo)，其中softmax退化為了sigmiod。

同樣可以證明，基于Hierarchical Softmax的Skip-Gram分解的矩陣是
$M_{wc} = \log(\frac{d(w,c)}{d(w)})$

中心詞向量 $\vec{w}$ 矩陣 $W=[\vec{w_1},\vec{w_2}...]$ ，上下文向量 $\vec{c}$ 矩陣 $C=[\vec{c_1},\vec{c_2}...]$ ，記SPMI為 $A$ ，則分解任務(wù)為
$A_{n \times n} = W_{d \times n}^TC_{d \times n}$
加上正則項(xiàng)后，優(yōu)化目標(biāo)為
$L = ||A-W^TC||_F^2 + \frac{1}{2}(||W||_F^2+||C||_F^2)$

2. DeepWalk

DeepWalk

從每個(gè)節(jié)點(diǎn)出發(fā)n_walks次，每次均勻采樣連接節(jié)點(diǎn)，延申長(zhǎng)度達(dá)walk_length后停止一次游走，生成一個(gè)序列。對(duì)采樣的序列，使用word2vec的skip-gram直接訓(xùn)練。

Node2Vec

改進(jìn)游走方式，以便相似節(jié)點(diǎn)和同一社區(qū)節(jié)點(diǎn)更接近。

廣度優(yōu)先策略，使同一社區(qū)節(jié)點(diǎn)更接近；
深度優(yōu)先策略，使不通社區(qū)內(nèi)的相似節(jié)點(diǎn)更接近。

假設(shè)已由 $t$ 走到 $v$ ，下一個(gè)節(jié)點(diǎn)用 $x$ 表示，則游走方向由下式控制
$a_{pq}(t,x) = \begin{cases} \frac{1}{p} & d_{tx}=0\\ 1 & d_{tx}=1\\ \frac{1}{q} & d_{tx}=2 \end{cases}$
其中 $d_{tx}$ 表示從 $t$ 到 $x$ 的最短路徑長(zhǎng)度。同時(shí)可以考慮邊權(quán)重。

3. Text-Associated DeepWalk (TADW)

DeepWalk的本質(zhì)是在近似重建 $t$ 步共現(xiàn)概率矩陣。結(jié)合Hierarchical Softmax的Skip-Gram分解的矩陣
$M_{wc} = \log(a_{wc}) \\ a_{wc} = \frac{d(w,c)}{d(w) }$
我們只需要找到 $a_{wc}$ 的合理表達(dá)，即可直接通過(guò)矩陣分解解決問(wèn)題。

對(duì)DeepWalk，假設(shè)只走1步，不妨設(shè)為 $w$ 到 $c$ ，則兩點(diǎn)共現(xiàn)的條件概率應(yīng)為 $a_{wc}=1/d_w$ ， $d_w$ 為節(jié)點(diǎn) $w$ 的出度。我們將對(duì)應(yīng)的標(biāo)準(zhǔn)化的鄰接矩陣記為 $A$ 。與PageRank所使用的矩陣一致。

于是 $t$ 步共現(xiàn)概率矩陣和要分解的矩陣是
$\hat{A}=(A+A^2+...+A^t)/t \\ M = \log(\hat{A})$
相應(yīng)的損失函數(shù)為
$L = ||M-W^TC||_F^2 + \frac{1}{2}(||W||_F^2+||C||_F^2)$
融合屬性矩陣 $S$ 則為
$L = ||M-W^TCS^T||_F^2 + \frac{1}{2}(||W||_F^2+||C||_F^2)$