0
近日，在中國北京舉辦的 CIKM 2019 AnalytiCup 中，來自青島大學和春秋航空的成員組成的團隊 QDU 摘得了“用戶興趣高效檢索”賽道的桂冠。
本文由 QDU 團隊獨家供稿，AI開發者號稍加整理如下，希望能給開發者們一些經驗與啟發。
CIKM AnalytiCup 介紹
CIKM 是中國計算機學會（CCF）推薦的數據庫/數據挖掘/內容檢索領域的 B 類會議。 CIKM AnalytiCup 挑戰賽是會議同期舉行的國際數據挖掘比賽，今年由 CIKM、阿里媽媽、阿里巴巴算法大學、阿里云天池共同承辦，挑戰賽分為兩個賽道，用戶興趣高效檢索（Efficient User Interests Retrieval）和用戶行為多樣性預測（Predicting User Behavior Diversities in A Dynamic Interactive Environment）。 QDU 團隊在用戶興趣高效檢索賽道中斬獲冠軍。
QDU 團隊介紹
本次冠軍團隊 QDU 的參賽成員包括：
薛傳雨，青島大學大四學生，曾獲得數據挖掘比賽冠軍與季軍。
張卓然，春秋航空算法工程師，曾多次獲得數據挖掘比賽前十名的成績。
吳舜堯，青島大學助理教授，曾獲得數據挖掘比賽冠亞軍。
團隊在本次競賽上有幾大主要優勢：
團隊隊員有豐富的數據挖掘經驗，積累了數據挖掘比賽的很多技巧。
團隊成員從事推薦系統與復雜網絡方面的研究，了解推薦系統的基本算法并有能力改進算法。
團隊成員嘗試將統計領域最新理論與方法應用于數據挖掘比賽，這些嘗試為模型的性能與精度帶來了一定提升。
賽題介紹
用戶興趣高效檢索聚焦在解決大規模推薦中用戶興趣檢索的問題上，任務要求在很短時間內從千萬級的商品庫 C 中為用戶挑選出最可能感興趣的 k 個商品。復賽還要求為每個用戶進行推薦時的時間復雜度小于 O(n)。其中，
。此外，復賽提交的方案需在一個 8 核 60G P100 的 GPU 容器中對 6 萬線上用戶進行推薦，限時 1 小時。不僅對復雜度有要求，對內存、CPU 等資源也有限制。
數據集包括用戶行為文件、用戶信息文件與商品信息文件。用戶信息包含用戶 ID、性別、年齡與購買力，商品信息包含商品 ID、類目 ID、店鋪 ID 與品牌 ID（若有商品價格，有望提高推薦效果），用戶行為涉及 16 天（由某個周五開始）的用戶對商品的行為日志。
評測指標
比賽要求預測一組給定用戶在第 17 天感興趣的商品列表。需要注意的是，初賽與復賽的方案評價方式有較大差別：
（1）初賽提供了待預測用戶的信息、第 1~16 天的行為日志及感興趣的商品信息，參賽選手可以僅適用待預測用戶的信息設計方案，將預測結果提交到線上進行評測，評價指標為 
與
的加權均值，Gu 為用戶 u 的真實未來興趣商品集合，Hu 為用戶 u 的歷史行為類目商品子集， 
為選手產出的用戶 u 的未來興趣商品預測集合。其中，Novel-Recall@50 要求推薦的商品不能與歷史感興趣商品屬同一類別，因而難度很大。
（2）復賽將待預測的用戶信息等文件置于線上，不允許打印相關信息等內容，而且對運行時間及資源又添加了限制。利用線上用戶行為日志等信息建模效果尚可，但復雜度可能會超出要求，因而很多信息及模型需要在線下統計、訓練。此外，評價指標變為了 
，Hu 為用戶 u 的歷史行為商品集合。該指標比初賽簡單些，因為可以推薦同類商品，這在真實業務及該數據集中都較常見。
賽題解析及相關方法介紹
本賽道由阿里巴巴集團阿里媽媽事業部營銷技術團隊出題。從賽題的設置來看，本次賽題主要想要解決的問題，和實際大規模推薦系統中的 Match 階段面臨的挑戰非常類似，即如何在線上系統實際資源有限的情況下，從大規模候選集中迅速、準確地找到一個較小的用戶興趣子集，以供后續模塊繼續處理。此前，由于客觀存在的算力資源限制，學術界及工業界對這一問題的研究，大部分集中在如何提升檢索效率上。
在推薦系統發展初期，解決這一問題的主要思路為采用“協同過濾”的方法。這一類方法的中心思想為：“相似”的用戶，可能會對“相似”的商品感興趣。因此，在實際應用中，這類方法通常首先會通過各種相似性計算規則，將商品聚類到相似性 Tag 下；然后在召回階段，通過用戶輸入首先召回一些 Tag，再將 Tag 下掛載的商品作為召回集輸出。比如，經典的 Item-CF[5] 方法通過相似性計算，首先得到每個商品的相似商品；然后在進行推薦時，把用戶歷史訪問過商品的相似商品作為召回集。這類方法在實現上較為簡單，但是基于規則的相似性計算及“用戶-Tag-商品”的兩段式召回模式，限制了整體的精確度。另外，由于整體的召回思路是基于歷史行為找相似，因此召回結果在多樣性和發現性上表現欠佳。
隨著興趣建模及索引技術的發展，學術界和工業界對召回系統的研究逐步過渡到了第二階段，即通過基于向量的興趣模型加向量相似性檢索來實現一段式召回。在索引端，日益完善的向量相似性檢索技術，為這一方案的應用提供了效率上的保障；在模型端，其核心思想是通過訓練用戶興趣模型，使得模型產出的用戶向量與商品向量之間的距離度量（如內積距離等），能表示用戶對商品的興趣度。這類方法首次實現了對大規模候選集的一段式召回，其代表性的工作為 YouTube-DNN 模型[6]。然而，由于對向量相似性檢索的依賴，這一方案在興趣度量方面受到了一定的限制，只能使用內積模型來度量用戶對商品的興趣，一些能在排序階段使用的更先進的模型結構，以及一些用戶-商品的交叉特征等，無法被有效利用。
當前，隨著 GPU、人工智能計算芯片等硬件的快速發展，系統整體能使用的算力資源，相比之前有了極大的提升。而更強大的基礎算力，促使我們在面對這一問題時需要重新思考：如何設計新的算法，使其能夠盡可能地利用豐富的算力資源，來提升召回的精準度。面對這一問題，阿里媽媽技術團隊提出了一種基于可學習的樹索引加任意檢索模型的深度樹匹配方法[7,8]。該方法使用了樹索引結構來解決檢索的效率問題，因為基于樹的檢索算法時間復雜度為對數級別，所以即使面對超大規模商品庫也能夠勝任；以在樹索引結構中檢索相關商品為目標，得益于樹檢索天然的復雜度優勢及 GPU 等硬件提供的強勁算力，任意的深度模型都可以被用作檢索模型，來學習如何在樹索引中檢索目標，而不局限于內積模型的形式，因此打開了模型能力的天花板。此外，樹索引和檢索模型，可以在數據驅動的方式下進行聯合優化來達到系統整體效能的最優。深度樹匹配方案在阿里媽媽展示廣告核心資源位已經全面應用，取得了顯著的實際業務提升。
主辦方從工業界實踐中面臨的實際問題與挑戰出發，希望參賽選手能結合業界當前技術的整體發展階段，思考如何在召回階段盡可能地利用系統算力資源，來實現最優檢索的目標，進而孕育出解決問題的新方法。
核心思路
初賽方案僅基于規則做了 Match 階段，里面有些技巧，感興趣的同學可以關注薛傳雨的 github（https://github.com/ChuanyuXue/CIKM-2019-AnalytiCup），之后會在上面發布代碼。下面重點闡述復賽方案。圖 1 給出了推薦系統的經典流程，先從千萬級商品庫中為指定用戶召回幾百或幾千個候選商品，再建模為候選商品排序，選出少量商品作為最終的推薦列表。
圖1 推薦系統經典流程
數據分析與探索
數據分析與探索對方案設計有重要的指導作用。下面介紹幾個關鍵的分析。在做 EDA 時，數據集被切分為了兩部分，第 1~14 天日志被視為“歷史”行為，第 15 天日志視為“未來”行為，從而可以分析對“未來”行為有重要影響的“歷史”行為特點。
圖 2 用戶對“歷史”感興趣同類商品的“未來”行為統計分析。
用戶行為共有 4 種類型：’pv’（瀏覽）、’fav’（喜歡）、’cart’（加入購物車）和’buy’（購買）。按照感興趣程度，可將這4種類型的權重依次設為 1、2、3、4（論壇發布的初賽 baseline 即是這樣設置，效果尚可）。圖 2 先獲取了用戶“歷史”感興趣的商品類別，然后統計了“未來”對歷史感興趣的同類別商品的行為。圖 2 表明“未來”感興趣的商品（出現在第 15 天日志中的商品）幾乎不會是以往購買過的同類商品。因而，在復賽方案中將’buy’的權重設為 1。實際上，4 種行為的權重仍可調優，但限于時間和精力未做。
圖 3 “未來”感興趣商品在第 1~14 天被感興趣的次數
如圖 3 所示，“未來”感興趣商品在第 14 天被感興趣的次數組多，距第 14 天越遠次數越少。因而，考慮時間因素對行為重要性的影響，按下式調整行為權重：
其中，
是四種行為的權重，Tu,i 代表距最大時間戳 Dmax 的遠近，Ru,i 是考慮時間因素后評估用戶 u 對商品 i 的感興趣程度。
圖 4 沒有區分行為的種類，統一分析了用戶在“未來”是否仍會對“歷史”感興趣的商品類別及店鋪感興趣。如圖 4-(a) 所示，用戶在“未來”仍會對“歷史”感興趣的商品類別有較高興趣；圖 4-(b) 則表明，用戶在“未來”對歷史感興趣的店鋪有較低的興趣。進而，針對類別/店鋪提取了一些特征，詳見對排序階段的介紹。
(a)
(b)
圖 4 用戶是否仍會對“歷史”感興趣的商品類別及店鋪感興趣。
召回階段
圖 5 基于 Item CF 的召回流程
召回的策略有很多，即使是基于規則的策略效果也可以。在復賽后期，團隊花費了很大精力實現了一種 Item CF 算法，效果也有明顯提升。圖 5 給出了基于 Item CF 做召回的流程，先利用龐大的歷史日志統計 item-item 相似性矩陣，再結合目標用戶的歷史行為做推薦。實現的難點在于對約 8000 萬歷史日志做統計的復雜度太高，需要做優化代碼、做并行化處理。
如圖 6 所示，將用戶分為了若干組，并行處理每組內 item-item 共現頻率的統計，最終將與每個商品最相似性的 500 個商品存在字典中。實際上，對復賽訓練集統計后，發現字典中鍵值數僅有 40 多萬。 此外，為了提高效率，團隊使用了 Cython 實現統計共現頻率的代碼。整個流程較復雜，感興趣的同學可以看隨后開源的代碼。
圖 6 并行統計 item-item 相似性，并轉存為字典
Item CF 相似性指標關乎召回的效果。在實現時團隊借鑒了 2015 年騰訊 SIGMOD 論文 [1]。在 9 月初，按照關聯規則中置信度計算 Item CF 相似性如下：
其中，代表對商品感興趣的用戶集合。顯然，
。基于該指標做召回，線上效果為0.045。
在此基礎上，考慮到用戶活躍度（感興趣的商品數）對相似性的影響，改進了上述指標：
其中，是全體用戶集合，Ui 是對商品 i 感興趣的用戶集合；Wu 代表用戶 u 對相似性的貢獻度，
代表用戶感興趣的商品集合。當 w—>1 時，
等價于
。基于改進指標做召回，并做了些額外處理，線上效果為 0.053。
排序階段
召回階段獲得少量（300 或 500）候選商品后，可以構建排序模型獲得最終的推薦列表。我們將排序任務轉化為二類判別問題。在建模前，需要切分數據集。如圖 7 所示，利用第 1-15 天數據做召回、生成特征，利用第 16 天的數據生成標簽，從而生成線上訓練集；利用 1-16 天數據做召回、生成特征，生成線上測試集，加載訓練后的模型及相關文件完成預測。
需要特別注意的是，訓練集中的正樣本和負樣本都是從召回列表中生成的，而不是將每個用戶感興趣的商品都拿出來做正樣本。這是因為，很多用戶感興趣的商品對應的特征取值都無法統計，使得這些正樣本失去了統計意義，對訓練模型有負面影響。另一個賽道的亞軍也是這樣做的，他的解釋也很好，“希望建模樣本與召回樣本同分布”。本賽道很多同學都未能建模做 Ranking，應該是沒能發現采樣的技巧。
圖 7 排序階段劃分數據
圖 8 為提取的特征列表，只有 64 個。其中，Item CF 的相似性特征是強特征。最終使用了 Catboost 和 Lightgbm 建模。Catboost 對過擬合的處理較好，使用了全部特征（線上效果為 0.0616）；Lightgbm 使用全部特征效果不佳，故做了特征選擇，最終只使用了 36 個特征。
圖 8 特征列表（共 64 個）
為了減少特征的數量，在比賽中使用了多種特征選擇方法。雖然 xgboost、lightgbm、catboost 可以做特征重要性分析，但很多同學可能注意到把選出的重要特征給梯度提升樹模型建模并無明顯提升。我們做特征選擇的思路是“劣汰優勝”，先基于獨立性檢驗剔除關聯弱的特征，再從剩余特征中選擇重要性高的特征。兩變量獨立是指兩變量既不存在線性相關性，也不存在非線性關聯。我們采用 Mean Variance Test[2,3] 做“劣汰”，這是首都師范大學崔恒建教授 2015 年發表于統計領域頂刊 JASA 的工作，2018 年進行了拓展，可用于做獨立性檢驗及特征選擇。該方法可檢驗一個離散型變量與一個連續型變量間是否獨立，對變量的分布無假定（Distribution free），并且計算簡單（只是計數）。這里僅列出其部分理論（圖 9），感興趣的同學可以交流，該方法已被 Chuanyu 做成了工具包，已開源在他的 github。此外，團隊成員在 IJCAI 2018 和資金流入流出預測課程視頻（天池 AI 課程，之后可能上線）中都使用 Mean Variance Index 做過特征選擇，效果都不錯。
圖 9 Mean Variance Test簡介
最后，團隊進行了簡單的模型融合。為了提高穩健性，依次采用了調和平均值、幾何平均值和算數表均值（圖 10），線上效果為 0.0622。
圖 10 模型融合
其他嘗試
還有一些基于規則的策略及其他方案沒有介紹。例如，基于同類商品的規則做召回、基于同店鋪的規則做召回、基于 word2vector 的思路做召回（借助 faiss）、基于 MinHash LSH 做 Item CF、取最近 100 條用戶行為做統計等等。感興趣的同學可以交流。
比賽的收獲與感想
參加 CIKM 挑戰賽的原因有二：（1）希望驗證自身技術和研究價值；（2）參加會議，與專家交流，幫助薛傳雨申請 2020Fall 的博士或研究型碩士（可聯系 cs_xcy@126.com）。受限于復賽任務要求，我們沒能在比賽中使用開發的推薦系統框架（一種基于組間效應的增量推薦系統框架[4]）。
想法比套路重要得多。大家在做比賽時，應該把精力放在數據分析與探索，從而提取有用的規則，利用規則進行初步想法的驗證；進而，基于規則生成特征，再考慮建模、模型融合。其次要敢于嘗試新的思路，比起在原來的方案上調整參數，對算法進行改進或引入新算法可能會帶來更有大的提升。另一方面，建議大家學好統計，讀讀統計學領域的論文，有助于加深對機器學習的理解。此外，在比賽后幾天，要休息好、能沉住氣，不能過于急躁。最后，僅僅提高技術是不足夠的，學好英語、提高表達能力也很關鍵。
參考文獻
[1] Y. Huang et al. Tencentrec: Real-time stream recommendation in practice. Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. 2015: 227-238.
[2] H. Cui et al. Model-free feature screening for ultrahigh dimensional discriminant analysis. Journal of the American Statistical Association. 2015, 110(510): 630-641.
[3] H. Cui et al. A Distribution-Free Test of Independence and Its Application to Variable Selection. arXiv preprint arXiv:1801.10559, 2018.
[4] C. Xue et al. An Incremental Group-Specific Framework Based on Community Detection for Cold Start Recommendation. IEEE Access. 2019, 7: 112363-112374.
[5] B. Sarwar et al. Item-based Collaborative Filtering Recommendation Algorithms. WWW. 2001: 285-295
[6] P. Covington et al. Deep Neural Networks for YouTube Recommendations. RecSys. 2016: 191-198
[7] H. Zhu et al. Learning Tree-based Deep Model for Recommender Systems. KDD. 2018: 1079-1088
[8] H. Zhu et al. Joint Optimization of Tree-based Index and Deep Model for Recommender Systems. NeurIPS. 2019
雷鋒網
雷峰網版權文章，未經授權禁止轉載。詳情見轉載須知。
