推薦系統(tǒng)入門實(shí)踐（5）召回之node2vec

這部分算是圖模型吧豆巨，會比較簡略铃绒。

node2vec召回

簡單說呢，node2vec是通過構(gòu)造item（根據(jù)需要哄辣，其實(shí)uploader或者user也可以用）之間的關(guān)系圖吐根，根據(jù)邊的權(quán)值來選擇相關(guān)的item正歼，構(gòu)造sentence。然后怎么樣拷橘？然后word2vec啊局义。word2vec，或者說item2vec冗疮，是通過單一用戶來構(gòu)造sentence的萄唇，node2vec打破了這一限制。

先貼幾個鏈接：1. node2vec論文鏈接 2. 靠譜的知乎文章 3. 靠譜的知乎文章2

算法有兩個假設(shè)赌厅，一是條件獨(dú)立假設(shè)穷绵，就是說每個鄰居點(diǎn)之間相互獨(dú)立；二是特征空間對稱假設(shè)特愿，就是說兩個點(diǎn)之間是互相影響的仲墨。這兩個假設(shè)是為了導(dǎo)出目標(biāo)函數(shù)服務(wù)的勾缭，詳細(xì)看上面的三個鏈接，這里略去了目养。既然最后還是要用word2vec俩由，其實(shí)推導(dǎo)過程也都是相似的，有些trick也是相通的癌蚁，比如負(fù)采樣之類幻梯。

我認(rèn)為從item2vec進(jìn)化到node2vec，關(guān)鍵的點(diǎn)在于努释，圖怎么構(gòu)造碘梢？sentence怎么構(gòu)造？

先說圖伐蒂，我們就以item圖為例煞躬。我們手里有的數(shù)據(jù)是用戶的行為歷史，理解為每個user跟著一串item list逸邦，在實(shí)踐中恩沛，會限制行為的時間范圍（例如2h內(nèi)的行為list或者若干次刷新內(nèi)的行為list），也會限制list的長度缕减。然后呢雷客，按照行為順序連線，最后存起來是“item1 item2 weight"的形式桥狡。貼一段代碼品品意思：

    sortedUserActionRdd.repartition(600).flatMap(
      x => {
        val result = ListBuffer[(String, Float)]()
        val actionSet = x._2
        if(actionSet.length >= 2){
          var index = 1
          while (index < actionSet.length){
            val curAction = actionSet(index)
            val lastAction = actionSet(index-1)
            if(curAction._4.toLong - lastAction._4.toLong < TWO_HOUR_MILL){
              val weight = lastAction._2 * curAction._2 * curAction._3
              if(lastAction._1 > curAction._1){
                result.append((lastAction._1 + "\t" + curAction._1, weight))
              }else{
                result.append((curAction._1 + "\t" + lastAction._1, weight))
              }
            }
            index = index + 1
          }
        }
        result
      }
    ).reduceByKey(_ + _).map(x => x._1 + "\t" + x._2).saveAsTextFile(outputPath)

上面的代碼注意到搅裙，item之間是有個weight的，最后是reduceByKey加和了一下总放。這個weight是什么呈宇？其實(shí)可以自己定義。上面代碼里使用的是：source_item完成度 * target_item完成度 * 二者時長得分的較大值局雄。注意，完成度也是可以自己定義的存炮，例如為了避免極值影響太大炬搭，可以取log(x+1)，這里x是傳統(tǒng)意義上的完成度穆桂；時長得分也是自己定義的宫盔，因?yàn)闀r長指標(biāo)比較重要，所以需要考慮下視頻時長本身的影響享完。

時長得分可以設(shè)計為一個偏移過的SIGMOD灼芭，參數(shù)可以通過擬合視頻時長的累積分布得到（python里有scipy.optimize，可以curve_fit）：

  def calDurationScore(timeDuration: Float): Float = {
    (0.96179781 - 9.11275437/(1 + Math.exp(0.54759073 * (timeDuration/100 + 3.90174182)))).toFloat
  }

好了般又，有了圖怎么構(gòu)造sentence彼绷？BFS和DFS當(dāng)然是可以的巍佑，n2v用了一種參數(shù)控制的隨機(jī)游走方法。

image.png

上式定義了從v到轉(zhuǎn)移到x的概率寄悯，其中pi是未歸一的萤衰，Z是歸一化常數(shù)。Pi_vx = alpha_pq(t,x) * w_vx猜旬，其中alpha的公式如下：

image.png

上面這一堆圖其實(shí)是說了件什么事呢脆栋，就是我從t走到了v，下一步要去哪的問題洒擦。p控制了返回t的概率椿争，p高那就返回概率低；q控制“in-out"的概率熟嫩，q高就傾向于訪問t的近鄰（跑不遠(yuǎn)）丘薛。直觀來說，p高q低傾向于DFS邦危，這時候會挖掘更高階的協(xié)同信息洋侨，可以作為item2vec的有效補(bǔ)充；p低q高傾向于BFS倦蚪，更多的是一階協(xié)同希坚；p=q=1的時候就是隨機(jī)游走。

從采樣序列的過程可以看到陵且，node2vec比item2vec進(jìn)步的地方就在于裁僧，i2v的正樣本是有概率在n2v中出現(xiàn)的，而n2v中可能出現(xiàn)高階協(xié)同的正樣本慕购，這就打破了單個user的限制聊疲。舉例來說，用戶1的行為ab沪悲，用戶2的行為ac获洲，在i2v里面是不可能有bc這個樣本，而n2v里面可以有殿如。

算法過程：

image.png

注意到這里有個alias采樣贡珊，它的時間復(fù)雜度是O(1)，具體介紹看大佬關(guān)于采樣的分享涉馁。

關(guān)于node2vec具體的實(shí)現(xiàn)代碼可以看大佬g(shù)ithub鏈接门岔，這部分我也沒有細(xì)看了（難點(diǎn)吧也是...后面如果有機(jī)會再補(bǔ)充，如果我不懶的話）烤送。

實(shí)踐中寒随，item圖的node2vec指標(biāo)效果跟item2vec差不多(原因可能是p=0.5,q=2)，但是占比卻高很多（短視頻里）。這是為什么妻往？n2v跟i2v單召回源指標(biāo)差不多可以理解互艾，因?yàn)榻５臉颖净臼且粯拥模ɑ蛘哒f類似的），建模方式不一樣蒲讯。占比高說明觸發(fā)源比較多,這樣用戶看了一個視頻可能沒有i2v忘朝，但是會有n2v。n2v整體效果提升是因?yàn)樗麛D占了一些比他差的召回源的流量判帮，比如標(biāo)簽召回等局嘁。

加個問題，n2v如何對新物品進(jìn)行召回晦墙？參考阿里的論文其實(shí)是加入了side_info悦昵，比如item的up、tag等等（例如原本的skip gram輸入是i1輸出是i2晌畅，這時候輸入就變成了i1,tag...輸出還是i2）但指，然后對新物品就用side_info的均值來代替。簡單貼個圖：

image.png

graphsage召回

這部分待補(bǔ)充吧抗楔，實(shí)踐中效果一般棋凳，主要是因?yàn)闆]來得及優(yōu)化就換業(yè)務(wù)了。