阿里KDD2017論文:基於大規模圖計算的本地算法對展示廣告的行為預測

2020-12-04 機器之心Pro

本文由機器之心編輯，「機器之心」專注生產人工智慧專業性內容，適合開發者和從業者閱讀參考。點擊右上角即刻關注。

在 2017 國際知識發現與數據挖掘大會（KDD）全球論文投稿中，阿里集團和螞蟻金服共有 5 篇論文被大會收錄，本次被收錄論文涵蓋深度學習、大規模圖計算、商品智能排序等多個研究領域，基於真實的業務場景或數據樣本，文中部分方法結論已經在業務中運用。如深度學習語義建模研究中提出了一種新的文本語義編碼算法 conv-RNN，該模型在參考了較為常用的文本語義編碼模型循環神經網絡與卷積神經網絡的同時，進行了進一步的文本語義編碼優化，實現更為精準的文本分類和問答匹配並已應用於阿里智能音響「天貓精靈」。

KDD 的英文全稱是 Knowledge Discovery and Data Mining，即知識發現與數據挖掘，由美國計算機協會 ACM 下的數據挖掘分會舉辦，是國際數據挖掘領域的頂級會議。KDD 2017 共吸引全世界 1144 篇論文投遞，收錄 216 篇，包括清華、中科院、阿里在內的中國大陸學術界和工業界共被收錄 25 篇。

本文介紹了阿里被 KDD 2017 接收的論文《Local Algorithm for User Action Prediction Towards Display》。

論文地址：https://drive.google.com/file/d/0B_QtfVz5m-4_MkZpd1VIRUZSWm8/view

我們解決的問題

用戶行為建模在計算廣告中是至關重要的，它通過跟蹤用戶的在線行為建立用戶的產品，然後根據用戶的興趣和需求提供相關的廣告。準確的模型將導致更高的定位精度，從而提高廣告效果。直觀上，類似的用戶往往對展示的廣告具有類似的行為（例如，展示，點擊，轉換）。

然而，據我們所知，以前的工作沒有太多明確地調查各種類型的用戶行為的相似之處，並且將它們納入廣告響應目標和預測中，主要是由於問題規模過大。為彌合這一差距，本文中，我們使用二分圖來表示歷史用戶行為，其中包括用戶節點和廣告客戶活動節點，以及過去反映各種類型的用戶- 廣告營銷活動交互的邊。

基於這種表示，我們研究了用戶行為建模和動作預測的隨機步行本地算法，其計算複雜度僅取決於輸出群集的大小，而不是整個圖形。我們的目標是通過利用歷史用戶-用戶 (user-user)，廣告系列活動 (campaign- campaign) 和用戶-活動 (user-campaign) 交互來改善行為預測。

特別地，我們提出了伴隨 ADNI 算法的二分圖 AdvUserGraph。ADNI 將 NIBBLE 算法擴展到 AdvUserGraph，並且能夠將由感興趣的用戶組成的本地群集發現到特定的廣告客戶活動。我們還提出了 ADNI 的兩個擴展，提高了效率。所提出的算法的性能表現在合成數據和世界領先的需求側平臺（Demand Side Platform），表明它們在預測極少數事件的有效性。

大規模圖計算本地算法的意義

今天，存在無數的應用程式，需要對某些類型的大型圖表進行分析，例如社交網絡，蛋白質相互作用網絡，共同作者網絡等，甚至全球網絡估計至少包含 47.4 億頁。因此，即使是中等大網絡的分析也是數萬個頂點的數量級，構成重大挑戰。處理這些問題的一種方法是將這些網絡劃分成更小，更易管理的部件，並行處理。然而，在這些網絡之一中建立最優聚類頂點的 NP 完整問題已經在十多年了。

分割大圖確實是一個計算上的重要問題：存在很少的方法可以在接近甚至 O(n2) 或 O(m) 的時間內對 n 個頂點和 m 個邊緣進行分割。近年來的一個突破是圖形分割的局部方法的出現，實現了邊緣數量接近線性的時間複雜性。這些方法中的第一種是通過稱為 NIBBLE[1] 的局部聚類算法來實現的。NIBBLE 可以最大限度地減少無向未加權圖的聚類質量公制切割電導。給定一個起始頂點，它可以證明在時間上靠近該頂點的簇 (O(2blog6m)/4)，其與輸出簇的大小成比例。尋找一個與其大小成正比的時間段是本身非常有價值的例程，作者展示了如何使用 NIBBLE 作為一個子例程，從大圖中重複刪除小簇，以獲得近似線性的時間圖分區算法。後來使用 PageRank 向量擴展了 NIBBLE，並且表明，通過單個 PageRank 向量的掃描可以得到具有 cut conductance 為的切割。

凸面優化已經成為不同領域的圖形建模越來越流行的方式。然而，隨著數據集越來越複雜，經典的凸優化通常由於缺乏可擴展性而失敗。最近 [2] 提出了 Network Lasso，並開發了一個快速，可擴展和分布式的解算器，並在圖形相關問題中看到幾個成功的應用。NIBBLE 和 PageRank NIBBLE 都是本地算法，它可以找出包含或靠近給定頂點的解決方案，而無需查看整個圖形。本地算法的運行時間，當查詢非空本地簇時，輸出簇的大小几乎是線性的。

模型的構成

我們首先把問題抽象成二分圖: user nodes & adv/campaign nodes，

這二者邊的建立，可以是 impression, click and/or conversion，一般情況下 impression 的數量遠遠大於 click，遠遠大於 conversion，但是這三者帶來的價值卻正好是相反的，及 value(impression)<value(click)<value(conversion)。基於這個問題，我們借鑑 tf-idf 的思想，我們假設節點之間的邊是一個 document，三種不同種類的節點是三個獨特的 term。假定 f(eij,di) 是 term eij 在 documentdi 出現的頻次，我們使用以下 log 變換去定義 term 的頻率 (tf):

Inverse document frequency (idf) 定義如下:

最終 tf-idf 的定義如下：

基於這個圖定義，我們提出了 NIBBLE 算法的變形和兩個延展，並證明了計算時間最多 O((k/γk+1)logm/)。

實驗結果

在 AUC，CVR 和 ROI 的結果上，我們都大幅度的超過了之前的 state-of-arts，並為全球第二大的競價平臺帶來了數以百萬計的美金收益。

參考文獻

[1] D. Spielman and S. Teng. A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning. SIAM Journal of Computation, 42:1–26, 2013.

[2] D. Hallac, J. Leskovec, and S. Boyd. Network lasso: Clustering and optimiza- tion in large graphs. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD'15, pages 387–396, 2015.

相關焦點

  • 中國軍團稱霸KDD:華人博士獲最佳論文,清華北大華為等榜上有名
    強調論文可復現而且最重要的是，KDD今年還在投稿通知中特別強調——可復現性——且規定該項會作為最佳論文評選資格，論文需要額外提交內容展示可復現內容。包括實驗方法、經驗評估和結果，也鼓勵在論文中公開研究代碼和數據，儘可能完整地描述論文中使用的算法和資源。
  • 論文詳解:滴滴大數據預測用戶目的地,準確率超90% | KDD 2017
    2017中滴滴研究院副院長葉傑平所帶的滴滴團隊關於計程車組合優化分單模型和目的地預測的論文《A Taxi Order Dispatch Model based On Combinatorial Optimization》被收錄。
  • 視覺信息助力廣告點擊率預估-京東廣告團隊技術論文入圍KDD2020
    近日，來自京東廣告團隊的一篇論文《Category-Specific CNN for Visual-aware CTR Prediction at JD.com》，即《在京東，視覺助力點擊率預估——基於給定類目信息的卷積神經網絡》被KDD2020成功收錄。
  • 視覺信息助力廣告點擊率預估——京東廣告團隊技術論文入圍KDD2020
    論文構建了一種基於特定類目的卷積神經網絡(Category-Specific CNN, CSCNN)，該算法有效利用了電商領域中豐富的商品類目信息，創新性的將商品類目信息與商品主圖共同作為主圖特徵提取模塊的輸入，提取基於特定先驗類目信息的商品主圖特徵，大大提高了CTR預估的準確度。儘管京東的廣告業務在業界起步的比較晚，但增速卻讓人刮目相看。
  • 谷歌的KDD 2017:九篇錄用+雙料博士論文獎
    《DeepWalk: Online Learning of Social Representations》實際上是 Bryan Perozzi 最初在 KDD』14 投遞的一篇論文，論文使用從截斷的隨機遊走獲得的一系列本地信息，以學習圖中節點的潛在表徵（如社交網絡用戶）的方法。
  • 用AI算法預測空氣品質,阿里媽媽選手斬獲KDD Cup 2018 三項大獎
    值得一提的是，胡可就職於阿里媽媽搜索直通車算法團隊，他主要的工作內容是做廣告排序算法，如應用深度學習模型解決業務問題，團隊也在應用並優化多種深度學習模型，其日常工作中積累的深度學習經驗在比賽中起到了關鍵作用。
  • 谷歌的KDD 2017:九篇錄用+雙料博士論文獎,超百位員工參與
    《DeepWalk: Online Learning of Social Representations》實際上是 Bryan Perozzi 最初在 KDD』14 投遞的一篇論文，論文使用從截斷的隨機遊走獲得的一系列本地信息，以學習圖中節點的潛在表徵（如社交網絡用戶）的方法。
  • KDD 2018:滴滴提出WDR模型顯著提升ETA預測精度
    事項：KDD 2018獨家約稿
  • 港科大KDD 2017錄用論文作者詳解:基於異構信息網絡元結構融合的...
    作者介紹本文主要介紹 KDD 2017 的一篇有關推薦系統的論文：「Meta-Graph Based Recommendation Fusion over Heterogeneous Information Networks」 這篇論文被KDD 2017的research track接收並做口頭報告(錄取率8.6%)。
  • 不一樣的論文解讀:2018 KDD best paper「Embeddings at Airbnb」
    這個思路也可以理解成另一種簡單的多目標融合策略，另一篇阿里的論文也值得一讀，提出了完整空間多任務模型（Entire Space Multi-Task Model，ESMM）來解決。數據稀疏是核心困難Word2vec 的算法並不神奇，還是依賴實體出現的頻次，巧婦難為無米之炊，如果實體本身在語料中出現很少，也很好學到好的表達。曾
  • 精彩論文|基於嵌入波矢濾波算法設計的「域」復用計算全息圖
    撰稿人 | 武霖論文題目 | 基於嵌入波矢濾波算法設計的「域」復用計算全息圖Domain multiplexed computer-generated holography designed by wavevector filtering embedded algorithm主要作者| Lin Wu（武霖），Ziyang Zhang
  • 網絡表示學習領域(NRL/NE)必讀論文匯總
    傳統的機器學習方法依賴於用戶定義的啟發式方法來提取編碼關於圖的結構信息的特徵（例如，度數統計或內核函數）。然而，近年來，使用基於深度學習和非線性降維的技術，自動學習將圖結構編碼為低維嵌入的方法出現了激增。在這裡，我們提供了關於圖形表示學習領域進展的關鍵概念回顧，包括基於矩陣分解的方法，基於隨機遊走的算法和圖形卷積網絡。文中回顧了嵌入單個節點的方法以及嵌入整個（子）圖的方法。
  • 假期薦讀:一文看盡2019-2020各大頂會 Graph Neural Network 論文(附連結)
    SGD訓練的GCN算法——Cluster-GCN，高效解決工業界訓練大規模深層圖卷積神經網絡問題，性能大幅提升基礎上依靠可訓練更深層網絡優勢達到SOTA效果，並開源了原始碼。作者們主要處理包含異構節點和異構邊的圖的表示學習問題。阿里電商的數據由用戶和商品構成的圖就是異構的，不僅包含異構的節點（用戶和商品），而且包含異構的邊（用戶和商品的多種交互行為，比如點擊、購買等）。不僅如此，圖中的節點還包含著豐富的屬性。
  • ICLR 2018最佳論文:基於梯度的元學習算法
    於 4 月 30 日開幕的 ICLR 2018 最近公布了三篇最佳論文，分別關注於最優化方法、卷積神經網絡和元學習算法。不出所料的是，這三篇最佳論文在 2017 年 11 月公布的評審結果中，都有很高的得分。機器之心以前已經介紹過關於修正 Adam 與球面 CNN 的最佳論文，本文將重點介紹第三篇關於元學習的最佳論文。
  • 論文主題、引用量、中國機構 & 華人學者，KDD 2020 關鍵數據搶先看
    多元時間序列預測背後的一個基本假設是其變量相互依賴，但仔細觀察，可以說現有的方法未能充分利用變量對之間潛在的空間相關性。近年來，圖神經網絡（GNNs）在處理關係依賴方面表現出了很高的能力。GNNs需要定義良好的圖結構來進行信息傳播，這意味著它們不能直接應用於依賴關係未知的多元時間序列。本文提出了一個專門針對多元時間序列數據設計的通用圖神經網絡框架。
  • 滴滴KDD 2019 論文詳解:基於深度價值網絡的多司機智能派單模型
    今年，滴滴共有三篇Oral論文入選KDD2019，研究內容涵蓋基於深度學習方法自動化地生成工單摘要、基於深度強化學習與半馬爾科夫決策過程進行智能派單及模仿學習和GAN在環境重構的探索。本文是對滴滴Oral論文《A Deep Value-networkBased Approach for Multi-Driver Order Dispatching》的詳細解讀。
  • 阿里發布的機器學習平臺PAI2.0,和騰訊的DX-I區別在哪? | 雲棲2017...
    不過，PAI2.0還提供了邏輯回歸、隨機森林、GBDT、KMeans等常規的機器挖掘算法，以及文本分析和圖算法。底層計算資源的支持對於底層計算資源，PAI2.0提供了雲端異構計算資源，包含CPU、GPU、FPGA。在GPU方面，PAI2.0可以靈活實現多卡調度。DX-I主要基於騰訊雲的GPU計算平臺，和異構計算相比還是略顯單薄。
  • CVPR2017精彩論文解讀:效果更顯著的模型壓縮算法和泛化優化算法
    下文是優必選雪梨AI研究院對其入選CVPR 2017的兩篇論文《基於低秩稀疏分解的深度模型壓縮算法》和《利用奇異值界定提升深度神經網絡訓練效果和識別精度》進行的解讀，除此之外他們還對會上Workshop競賽的進行了相關介紹。
  • 計算廣告中主要模塊、策略及其場景(下)
    該模型可以用來預測特定特定廣告、人群、重複投放次數下的轉化率。轉化率預測時，要特別注意是否有足夠的歷史數據，此外預測不可貿然交給機器完成，要把統計、經驗等結合起來估算轉化率。當然，如果是DSP廣告主類型和轉化流程基本一致，例如專注於遊戲客戶的DSP或者是專注於阿里體系內電商的阿里媽媽，那麼在轉化數據充分情況下可採用機器學習建模方法預測。
  • 解讀騰訊優圖ICCV2017 12篇論文:全球首個AI卸妝效果的算法等
    此次騰訊優圖入選的論文提出了諸多亮點：全球首個AI卸妝效果的算法；現今最準確的單張圖像深度估計算法；完美解決多幀信息融合困難的多幀超解析度視頻結果；史無前例的手機雙攝圖像匹配和分割研究成果。新智元此前曾報導，騰訊優圖是騰訊AI的三大核心支柱之一，與微信AI團隊和新成立的騰訊AI Lab共同驅動騰訊的 AI 發展。