556
千人千麵智能淘寶店鋪背後的算法研究登陸人工智能頂級會議AAAI 2017
電商時代，消費者對推薦係統已經不再陌生。“驀然回首”，你發現喜歡的商品就在首頁顯眼處。
如今，不僅僅是電商網站首頁會給你貼心推薦。你逛進一家淘寶商家的店鋪，也很有可能享受到推薦算法的服務。
這是阿裏商家事業部推出的智能店鋪“千人千麵”模塊。
阿裏商家事業部相關負責人介紹，單純通過算法做出的商品推薦，未必符合商家利益。常有商家抱怨，自家想賣的商品得不到推薦，營銷被算法牽著鼻子走。而“千人千麵”，就是先讓商家給出他們想要推送的商品集，算法再從指定候選集中為進入某家商鋪的消費者做個性化推薦。如此一來，算法可以為商家的營銷服務，為商家既定的 營銷計劃“錦上添花”。
不過要做到這一點並不簡單。
業界推薦係統往往由Matching和Ranking兩部分組成。Matching部分會根據全網用戶的瀏覽、加購、收藏等行為數據，在一個龐大的商品池中找出較小的候選集。 Ranking則是利用綜合用戶Profile，偏好，以及商品特征等信息訓練得出的一個打分排序模型。
但是，阿裏電商目前擁有百萬級別的活躍店鋪，單個用戶在單個特定店鋪內的行為記錄非常匱乏，很難按傳統方法有效進行matching。
對此，阿裏商家事業部提出一種高可擴展性的Graph Embedding（圖嵌入）方法，並創新性地將它應用到商品的embedding中。它能夠以非常小的存儲空間來計算任意兩個商品的相似度。就算你此前從未踏足這家店鋪，算法也能根據你此前在別家的瀏覽記錄，從店鋪裏挑出你可能喜歡的商品，擺在你麵前。
模塊投入使用後，商家的商品點擊率提升了30%，成交量提升60%。
從學術層麵來說，該Graph Embedding方法可學習到能夠描述圖中節點間高階的、非對稱相似度的低維Embedding向量，並且可以在理論上解釋這種基於機器學習的方法和基於預定義的傳統節點間相似度的關係，相關論文已被人工智能領域的頂級會議AAAI'2017接收。
以下是論文的中文描述：
工業界的推薦係統通常由Matching和Ranking兩個部分組成，Matching部分會根據全網用戶的瀏覽、加購、收藏等行為數據，利用協同過濾一類的算法（例如基於商品的ItemCF）在一個龐大的商品池中找出一個足夠小的候選集，以縮小後續算法需要評估的範圍。Ranking則是利用綜合用戶Profile，偏好，以及商品特征等額外信息訓練得出的一個打分排序模型。
我們的推薦場景，即對於店鋪私域內的千人千麵推薦模塊來說，其與公網推薦的重要區別在於，推薦的目標僅限於很小的一部分商家指定的商品集。
傳統的Matching這部分所遇到的難題在於，阿裏電商目前擁有百萬級別的活躍店鋪，這使得單個用戶在單個店鋪內的行為記錄非常稀疏。而在很多情況下，用戶在近期首次進入某商鋪主頁時，由於缺乏店內的行為信息（如足跡商品），很難有效利用店內ItemCF來進行推薦。
ItemCF的核心問題之一在於如何有效衡量與計算item與item之間的相似度\parencite{recsurvey05}。對於全網推薦的應用場景，由於商品數量太大，通常我們會離線計算出每個item前k個相似的item list\parencite{itemcftopk}，來用於在線打分的推薦方案。
然而，如果我們直接用全網topk item相似度的數據，對於每個商品來說，與他相似的商品數目其實可能很多，但由於topk的限製（通常小於200），隻有極少數店鋪的商品才能夠被召回，即基於全網top-k的商品相似度在同店推薦中的召回能力比較有限。
當然，我們可以使用同樣的方法，對於每個店鋪，僅計算店鋪內部的i2i數據，來完成推薦。這樣做的缺陷在於，完全無法覆蓋用戶沒有店內足跡的情況。
因此，為了提高相似商品的召回，以覆蓋用戶沒有店內足跡的情況，我們使用了圖嵌入算法APP來基於用戶瀏覽記錄來做商品嵌入——試圖將商品嵌入到一個低維空間中，同時保存一些商品之間的結構特征，即商品相似度。這樣就可以用穩定、較小的代價在線算出任意兩個商品之間的相似度了。
“旺鋪智能版智能模塊“是一款麵向中小商家的、商家可運營的個性化商品裝修模塊。在商家側算法提供麵向場景的選品，同時允許商家對算法商品池進行調整，或者完全手動建立商品池；在消費者端，個性化算法基於商家設置的商品池對訪客進行實時投放。產品設計上一定程度上滿足了商家確定性需求，在此基礎上通過個性化算法提升成交轉化。
我們研究Graph Embedding的初衷是為旺鋪模塊千人千麵場景提供覆蓋率高的Match支持。因為用戶在店鋪內部的行為稀疏，傳統的基於I2I的 match覆蓋率較低。而通過Embedding可以計算出任意兩個商品之間的Match分數，極大改善覆蓋率問題。
我們提出一種高可擴展性的Graph Embedding方法，該方法可學習到能夠可描述圖中節點間高階的、非對稱相似度的低維Embedding向量。同時我們提供理論上的解釋，來闡述這種基於機器學習的方法和基於預定義的傳統節點I2I相似度的關係。
圖是一種抽象程度高、表達能力強的數據結構，它通過對節點和邊的定義來描述實體和實體之間的關聯關係。常用的圖有社交關係網絡，通信網絡，商品網絡，知識圖譜等等。
而如何衡量圖中節點之間的相似度，對於朋友推薦、商品推薦、以及常見的分類聚類問題來說都是一個很重要的前置步驟。Graph Embedding可以理解成是一種降維技術，它可以將圖中的節點映射到一個低維空間裏，我們隻需要通過計算低維向量之間的關係，就可以得到原來節點之間的關聯關係。
盡管傳統Embedding技術被研究了很久，但他們的複雜度往往都在N^2級別以上，難以適應大規模數據。最近的一係列可擴展性較強的Graph Embedding工作主要是從DeepWalk【6】開始，後麵有Line【7】，Node2vec【2】等等。DeepWalk在原圖中做了一些路徑采樣，然後將路徑當作一個句子，路徑中的點當作單詞，之後就采用word2vec中提出的Skip-Gram with Negative-Sampling【5】方式進行訓練，得到每一個節點的embedding向量。Line隻針對邊進行采樣。Node2vec可以調節參數來進行BFS或者DFS的抽樣。
然而圖中的路徑采樣在概率上有著非常嚴重的非對稱性，之前的這些方法並沒有注意到這件事，也沒有從理論上來思考為什麼這麼幹不太科學。
例如在有向圖（圖1）中，對於A來說，可能並不關心C，而對於C來說，A很可能是他的興趣點。即使在無向圖中（圖2），也有同樣的現象。這樣的節點非對稱性關係是由於節點周圍的圖結構不同造成的。而從C出發的路徑C->B->A和從A出發的路徑A->B->C有著完全不相同的概率（0.5，0.08）。因此我們不能認為C->B->A這條路徑的產生會帶來一個（A->C）的正樣本。
圖 1有向圖中的非對稱性
圖 2 無向圖中的非對稱性
我們的工作所做的改進其實非常簡單，首先為了有能力表達非對稱性相似度，我們為每個節點引入了兩種Embedding向量，分別是Source向量和Target向量，如圖一所示。我們將對於A來說B的相似度記為 sim(A，B) ，並使用Source(A)與Target(B)的點積來表示，圖一中我們可以從Embedding中算出sim(A，C)
圖 3節點的兩種Embedding 身份
其次我們遵循了一種標準的、用來估計Rooted PageRank【3】的蒙特卡洛隨機遊走的方法【1】【8】來進行正例的采樣。
節點u對於節點v的Rooted PageRank（PPR）值代表了從v出發落在u點的概率。我們認為以這種方式生成圖中節點對的正樣例是更加自然、合理、有說法的。
這類遊走方法都是基於常見的Random Ｗalk with Restart，即從一個點出發以（1-alpha）的概率選擇鄰居進行跳轉，另外alpha的概率跳轉回自己。那麼現有的幾種方法稍有一些區別：
例如Monte Carlo End Point隻保留首次跳轉之前的節點，Monte Carlo Full Path保留路徑上的所有節點，將路徑的後綴也當作有效的采樣【1】。因為這兩條路徑對於起始點來說可以看作是相互獨立的。在最新的工作中也有對前綴路徑進行重用的【8】，就不再此展開。值得注意的是，後兩種的采樣效率相對於1來說要更高，盡管這三種方法都在各自的文章中被證明是正確且有Bound的。
我們遵循這類遊走方法，企圖給圖中的節點對創造一些正樣本。對於每一個被標記為正例的樣本（A, B）我們會根據目標函數更新A的source向量和B的target向量。並且隨機采樣其他的節點作為負樣本。
我們定義給定節點u，可以預測到節點v的概率
利用Skip-Gram with Negative-Sampling【5】，近似等價於優化
K是負采樣數，P_D（n）在圖中可用均勻分布替代。則總的目標函數如下：
下麵我們來解釋一個有趣的現象，我們非對稱的點積最終會是以學習出兩點之間的PPR的對數為目標。
這裏，類似於Levy【4】的證明，當維數充分大時，可看作互相獨立的變量。於是另下式為0：
得到：
由於|V|, k均為常數，我們可以看出x隻跟Rooted PageRank的模擬值Sim_u(v)呈對數關係。通過以上證明，論證了該方法可以保持非對稱的、高階相似度的說法，因為Rooted PageRank就是一種非對稱的、高階的相似度度量。
Link Prediction Task（AUC）：Embedding方法相對於傳統Pre-defined i2i指標來說，在AUC上很占便宜。因為傳統指標大多基於2跳以內的關係，包括阿裏內部使用的Swing。這樣就有很多正例的結果是0——完全無法和負例分開，AUC不高。可以看出我們的方法（APP）在比現有的方法要好一些。
下表是為了體現非對稱性的優勢，而在負樣本中加大了單向邊的比例，即A->B有邊，B->A無邊。可以看出我們與之前的方法在LinkPrediction任務上有顯著提升。
Node Recommendation：
值得注意的是，在尋找topk的這個問題當中，我們發現之前的Embedding方法似乎並沒有傳統指標靠譜。但我們的方法可以比較好的反應Topk的相似關係。
為了緩解用戶在店鋪內部行為的稀疏性，我們將用戶Session中的全網點商品擊序列轉化成一個全網商品點擊轉換圖。之後應用我們的Graph Embedding方法得到商品向量。該向量可以用來計算用戶點擊行為所產生的商品之間的相似度。下圖是我們與傳統topk i2i方法在真實場景中的點擊率比較。
我們的這項工作目前還隻是作為Match打分的基礎算法，我們正在嚐試進一步融合一些外部信息，如商品文本屬性、類目信息等，提高長尾商品的結構化Embedding質量。
【1】 Fogaras, D.; R´acz, B.; Csalog´any, K.; and Sarl´os, T. 2005. Towards scaling fully personalized pagerank: Algorithms, lower bounds, and experiments. Internet Mathematics 2(3):333–358.
【2】 Grover, A., and Leskovec, J. 2016. node2vec: Scalable feature learning for networks. In International Conference on Knowledge Discovery and Data Mining. ACM.
【3】 Haveliwala, T. H. 2002. Topic-sensitive pagerank. In Proceedings of the 11th international conference on World Wide Web, 517–526. ACM.
【4】 Levy, O., and Goldberg, Y. 2014. Neural word embedding as implicit matrix factorization. In Advances in neural information processing systems, 2177–2185.
【5】 Mikolov, T.; Sutskever, I.; Chen, K.; Corrado, G. S.; and Dean, J. 2013. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems, 3111–3119.
【6】 Perozzi, B.; Al-Rfou, R.; and Skiena, S. 2014. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, 701–710. ACM.
【7】 Tang, J.; Qu, M.;Wang, M.; Zhang, M.; Yan, J.; and Mei, Q. 2015. Line: Large-scale information network embedding. In Proceedings of the 24th International Conference on World Wide Web, 1067–1077. ACM.
【8】 Liu, Q.; Li, Z.; Lui, J.; and Cheng, J. 2016. Powerwalk: Scalable personalized pagerank via random walks with vertex-centric decomposition. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, 195–204. ACM.
最後更新：2017-06-22 11:32:30