Pinterest使用的推薦系統(tǒng)

閱讀原因

1.這篇文章是graph embedding在推薦系統(tǒng)領(lǐng)域的成功應(yīng)用，值得借鑒

2.對其中使用的curriculum learning的具體實現(xiàn)感興趣，據(jù)說越來越難的訓(xùn)練樣本能夠獲得12%的效果提升

3.文章結(jié)合了random walk算法對node進行采樣，從而獲得了相等大小的子圖，組成一個batch

問題背景

Pinterest使用的內(nèi)容推薦系統(tǒng)，其中定義為pin（單個內(nèi)容實體），定義為board（相關(guān)聯(lián)的內(nèi)容集合）。泛化的說，pin為一個item，而board是用戶定義的上下文。這兩個不相交的集合構(gòu)成所有的節(jié)點，在這篇論文中沒有對節(jié)點進行區(qū)分，對每個點都計算了相應(yīng)的embedding vector。

圖1圖卷積網(wǎng)絡(luò)的計算示意

獲得node embedding的前向傳播算法

該論文使用的node u的前向傳播思路和之前的graphSAGE的思路相比沒有很大的改變，以下是對該算法的解釋：

1.第一行：執(zhí)行聚合函數(shù)，對u的鄰居節(jié)點feature計算聚合表達,參數(shù)是每個鄰居節(jié)點的權(quán)重。

2.如何獲得u的鄰居節(jié)點集合？論文使用了random walk方法，計算從u出發(fā)，其他直接相鄰節(jié)點的訪問次數(shù)，并進行L1歸一化，取前k個節(jié)點。（沒有經(jīng)過這樣的neighborhood sampling的方法，就直接取與u相鄰的所有節(jié)點，這樣每個節(jié)點形成的計算子圖都不一樣，memory的使用不穩(wěn)定。）

3.為什么選用concat()，因為根據(jù)論文[21]，concat的效果要比直接取這兩者的平均更好。我個人認為，作為u的鄰居的聚合表示向量，應(yīng)該不與(u的embedding vector)在同一個特征空間上。采用concatenate操作，可以使這兩個向量維數(shù)不同，并且不破壞各自的信息。

4.convolve stack：如何將距離節(jié)點u深度為k的計算子圖用于計算節(jié)點u呢？這就需要u的迭代計算，使用第k-1次迭代計算出的，計算第k次迭代的。是一個在第k次迭代中在所有節(jié)點共享的學(xué)習(xí)參數(shù)，但是每一次迭代的參數(shù)是不共享的。由于這樣的迭代計算，就像是CV中常見的堆疊卷積核的做法，所以也可以將第k次迭代計算稱為第k層。

訓(xùn)練算法

圖2  一個minibatch的訓(xùn)練過程

1-7行的循環(huán)：獲得集合M中從源節(jié)點出發(fā)，path為1到K的節(jié)點集合

8-14循環(huán)：獲得每一層的embed

5-17行：更新embedding

訓(xùn)練技巧

1.加速收斂[16]：論文用到比較大的batch size，做過deep learning實驗的人應(yīng)該有感受，面對較大的batch size，收斂是比較困難的，所以作者使用了[16]中提到的訓(xùn)練技巧。

2.negative sample與curriculum learnig：該論文的loss也使用了噪聲對比估計這一技巧，采樣500個negative sample進行l(wèi)oss的計算。比較不同的地方是，論文不對每個batch中的每個node都進行專門的negative sample，而是只對一個minibatch進行negative sample，這樣能夠節(jié)約時間。畢竟Pinterest面對的節(jié)點有二十億個，但是1對正例只對應(yīng)了500個負例，模型不易于學(xué)到重要的判別信息（500:2,000,000,000=1:2,000,000）。所以論文使用了hard sample來訓(xùn)練模型學(xué)會判別長相比較相似的難負例。而加入難樣本進行訓(xùn)練，當(dāng)然會使模型更難收斂，所以使用curriculum learning的思想，在第一個epoch不加入hard sample，在后面的訓(xùn)練中，逐漸增加hard sample的個數(shù)。hard sample是通過與當(dāng)前節(jié)點p相關(guān)的pagerank score決定的（具體怎么操作還是沒有明白）。[14]

圖3 hard sample的實例

這篇文章關(guān)于分布式系統(tǒng)的思考

1.CPU做的事：extracting features，re-indexing(建立計算當(dāng)前minibatch的子圖)，negative sampling；

2.GPU做的事：minibatch的計算；

3.每個minibatch接受的輸入形式：，包含minibatch nodes和他們的neighborhood，以及一個較小的、和相對應(yīng)的特征矩陣。

4.producer-consumer：CPU是minibatch的生產(chǎn)者，GPU是minibatch的消費者。

5.多GPU并行訓(xùn)練的更新：每個minibatch被分為等大的部分，使用相同的參數(shù)，累計各自的梯度，經(jīng)過聚合后再同步更新。

6.test時期的MapReduce：因為融合了神經(jīng)網(wǎng)絡(luò)的graph embedding模型都具有推斷功能，所以PinSAGE只使用了一部分數(shù)據(jù)來進行訓(xùn)練，用訓(xùn)練好的網(wǎng)絡(luò)對剩下的pin進行推斷。

·為了避免每個節(jié)點在每一層的重復(fù)計算（因為不同節(jié)點的鄰居有可能是相同的），首先一個job先將每個pin都map一遍，以供algorithm 1中使用。

·得到每個pin的embedding之后，另一個job則聚合board的embedding vector；

·之后，用目前獲得的vector，用兩個job迭代計算pin的vector（使用pooling方法進行聚合）

7.計算資源的使用：訓(xùn)練代碼實現(xiàn)在tensorflow上，使用了16塊K80在單機上進行訓(xùn)練，將圖和feature數(shù)據(jù)存域memory上（500GB）。推斷過程運行于hadoop2上，用了378個AWS節(jié)點。

原論文名：Graph Convolutional Neural Networks for Web-Scale Recommender Systems

[14]C.Eksombatchai,P.Jindal,J.Z.Liu,Y.Liu,R.Sharma,C.Sugnet,M.Ulrich,and J.Leskovec.2018.Pixie:A System for Recommending 3+Billion Items to 200+ Million Users in Real-Time.WWW(2018)

[16]P.Goyal,P.Dollár,R.Girshick,P.Noordhuis,L.Wesolowski,A.Kyrola,A.Tulloch,Y.Jia,and K.He.2017.Accurate,Large Minibatch SGD:Training ImageNet in 1 Hour.arXiv preprint arXiv:1706.02677(2017)

[21]T.N.Kipf and M.Welling.2017.Semi-supervised classification with graph convolutional networks.In ICLR