近日，在中國(guó)北京舉辦的 CIKM 2019 AnalytiCup 中，來(lái)自青島大學(xué)和春秋航空的成員組成的團(tuán)隊(duì) QDU 摘得了“用戶興趣高效檢索”賽道的桂冠。

本文由 QDU 團(tuán)隊(duì)獨(dú)家供稿，AI開發(fā)者號(hào)稍加整理如下，希望能給開發(fā)者們一些經(jīng)驗(yàn)與啟發(fā)。

CIKM AnalytiCup 介紹

CIKM 是中國(guó)計(jì)算機(jī)學(xué)會(huì)（CCF）推薦的數(shù)據(jù)庫(kù)/數(shù)據(jù)挖掘/內(nèi)容檢索領(lǐng)域的 B 類會(huì)議。 CIKM AnalytiCup 挑戰(zhàn)賽是會(huì)議同期舉行的國(guó)際數(shù)據(jù)挖掘比賽，今年由 CIKM、阿里媽媽、阿里巴巴算法大學(xué)、阿里云天池共同承辦，挑戰(zhàn)賽分為兩個(gè)賽道，用戶興趣高效檢索（Efficient User Interests Retrieval）和用戶行為多樣性預(yù)測(cè)（Predicting User Behavior Diversities in A Dynamic Interactive Environment）。 QDU 團(tuán)隊(duì)在用戶興趣高效檢索賽道中斬獲冠軍。

QDU 團(tuán)隊(duì)介紹

本次冠軍團(tuán)隊(duì) QDU 的參賽成員包括：

• 薛傳雨，青島大學(xué)大四學(xué)生，曾獲得數(shù)據(jù)挖掘比賽冠軍與季軍。

• 張卓然，春秋航空算法工程師，曾多次獲得數(shù)據(jù)挖掘比賽前十名的成績(jī)。

• 吳舜堯，青島大學(xué)助理教授，曾獲得數(shù)據(jù)挖掘比賽冠亞軍。

團(tuán)隊(duì)在本次競(jìng)賽上有幾大主要優(yōu)勢(shì)：

• 團(tuán)隊(duì)隊(duì)員有豐富的數(shù)據(jù)挖掘經(jīng)驗(yàn)，積累了數(shù)據(jù)挖掘比賽的很多技巧。

• 團(tuán)隊(duì)成員從事推薦系統(tǒng)與復(fù)雜網(wǎng)絡(luò)方面的研究，了解推薦系統(tǒng)的基本算法并有能力改進(jìn)算法。

• 團(tuán)隊(duì)成員嘗試將統(tǒng)計(jì)領(lǐng)域最新理論與方法應(yīng)用于數(shù)據(jù)挖掘比賽，這些嘗試為模型的性能與精度帶來(lái)了一定提升。

賽題介紹

用戶興趣高效檢索聚焦在解決大規(guī)模推薦中用戶興趣檢索的問(wèn)題上，任務(wù)要求在很短時(shí)間內(nèi)從千萬(wàn)級(jí)的商品庫(kù) C 中為用戶挑選出最可能感興趣的 k 個(gè)商品。復(fù)賽還要求為每個(gè)用戶進(jìn)行推薦時(shí)的時(shí)間復(fù)雜度小于 O(n)。其中，。此外，復(fù)賽提交的方案需在一個(gè) 8 核 60G P100 的 GPU 容器中對(duì) 6 萬(wàn)線上用戶進(jìn)行推薦，限時(shí) 1 小時(shí)。不僅對(duì)復(fù)雜度有要求，對(duì)內(nèi)存、CPU 等資源也有限制。

數(shù)據(jù)集包括用戶行為文件、用戶信息文件與商品信息文件。用戶信息包含用戶 ID、性別、年齡與購(gòu)買力，商品信息包含商品 ID、類目 ID、店鋪 ID 與品牌 ID（若有商品價(jià)格，有望提高推薦效果），用戶行為涉及 16 天（由某個(gè)周五開始）的用戶對(duì)商品的行為日志。

評(píng)測(cè)指標(biāo)

比賽要求預(yù)測(cè)一組給定用戶在第 17 天感興趣的商品列表。需要注意的是，初賽與復(fù)賽的方案評(píng)價(jià)方式有較大差別：

（1）初賽提供了待預(yù)測(cè)用戶的信息、第 1~16 天的行為日志及感興趣的商品信息，參賽選手可以僅適用待預(yù)測(cè)用戶的信息設(shè)計(jì)方案，將預(yù)測(cè)結(jié)果提交到線上進(jìn)行評(píng)測(cè)，評(píng)價(jià)指標(biāo)為 與 的加權(quán)均值，G_u 為用戶 u 的真實(shí)未來(lái)興趣商品集合，H_u 為用戶 u 的歷史行為類目商品子集，  為選手產(chǎn)出的用戶 u 的未來(lái)興趣商品預(yù)測(cè)集合。其中，Novel-Recall@50 要求推薦的商品不能與歷史感興趣商品屬同一類別，因而難度很大。

（2）復(fù)賽將待預(yù)測(cè)的用戶信息等文件置于線上，不允許打印相關(guān)信息等內(nèi)容，而且對(duì)運(yùn)行時(shí)間及資源又添加了限制。利用線上用戶行為日志等信息建模效果尚可，但復(fù)雜度可能會(huì)超出要求，因而很多信息及模型需要在線下統(tǒng)計(jì)、訓(xùn)練。此外，評(píng)價(jià)指標(biāo)變?yōu)榱?，H_u 為用戶 u 的歷史行為商品集合。該指標(biāo)比初賽簡(jiǎn)單些，因?yàn)榭梢酝扑]同類商品，這在真實(shí)業(yè)務(wù)及該數(shù)據(jù)集中都較常見。

賽題解析及相關(guān)方法介紹

本賽道由阿里巴巴集團(tuán)阿里媽媽事業(yè)部營(yíng)銷技術(shù)團(tuán)隊(duì)出題。從賽題的設(shè)置來(lái)看，本次賽題主要想要解決的問(wèn)題，和實(shí)際大規(guī)模推薦系統(tǒng)中的 Match 階段面臨的挑戰(zhàn)非常類似，即如何在線上系統(tǒng)實(shí)際資源有限的情況下，從大規(guī)模候選集中迅速、準(zhǔn)確地找到一個(gè)較小的用戶興趣子集，以供后續(xù)模塊繼續(xù)處理。此前，由于客觀存在的算力資源限制，學(xué)術(shù)界及工業(yè)界對(duì)這一問(wèn)題的研究，大部分集中在如何提升檢索效率上。

在推薦系統(tǒng)發(fā)展初期，解決這一問(wèn)題的主要思路為采用“協(xié)同過(guò)濾”的方法。這一類方法的中心思想為：“相似”的用戶，可能會(huì)對(duì)“相似”的商品感興趣。因此，在實(shí)際應(yīng)用中，這類方法通常首先會(huì)通過(guò)各種相似性計(jì)算規(guī)則，將商品聚類到相似性 Tag 下；然后在召回階段，通過(guò)用戶輸入首先召回一些 Tag，再將 Tag 下掛載的商品作為召回集輸出。比如，經(jīng)典的 Item-CF^[5] 方法通過(guò)相似性計(jì)算，首先得到每個(gè)商品的相似商品；然后在進(jìn)行推薦時(shí)，把用戶歷史訪問(wèn)過(guò)商品的相似商品作為召回集。這類方法在實(shí)現(xiàn)上較為簡(jiǎn)單，但是基于規(guī)則的相似性計(jì)算及“用戶-Tag-商品”的兩段式召回模式，限制了整體的精確度。另外，由于整體的召回思路是基于歷史行為找相似，因此召回結(jié)果在多樣性和發(fā)現(xiàn)性上表現(xiàn)欠佳。

隨著興趣建模及索引技術(shù)的發(fā)展，學(xué)術(shù)界和工業(yè)界對(duì)召回系統(tǒng)的研究逐步過(guò)渡到了第二階段，即通過(guò)基于向量的興趣模型加向量相似性檢索來(lái)實(shí)現(xiàn)一段式召回。在索引端，日益完善的向量相似性檢索技術(shù)，為這一方案的應(yīng)用提供了效率上的保障；在模型端，其核心思想是通過(guò)訓(xùn)練用戶興趣模型，使得模型產(chǎn)出的用戶向量與商品向量之間的距離度量（如內(nèi)積距離等），能表示用戶對(duì)商品的興趣度。這類方法首次實(shí)現(xiàn)了對(duì)大規(guī)模候選集的一段式召回，其代表性的工作為 YouTube-DNN 模型^[6]。然而，由于對(duì)向量相似性檢索的依賴，這一方案在興趣度量方面受到了一定的限制，只能使用內(nèi)積模型來(lái)度量用戶對(duì)商品的興趣，一些能在排序階段使用的更先進(jìn)的模型結(jié)構(gòu)，以及一些用戶-商品的交叉特征等，無(wú)法被有效利用。

當(dāng)前，隨著 GPU、人工智能計(jì)算芯片等硬件的快速發(fā)展，系統(tǒng)整體能使用的算力資源，相比之前有了極大的提升。而更強(qiáng)大的基礎(chǔ)算力，促使我們?cè)诿鎸?duì)這一問(wèn)題時(shí)需要重新思考：如何設(shè)計(jì)新的算法，使其能夠盡可能地利用豐富的算力資源，來(lái)提升召回的精準(zhǔn)度。面對(duì)這一問(wèn)題，阿里媽媽技術(shù)團(tuán)隊(duì)提出了一種基于可學(xué)習(xí)的樹索引加任意檢索模型的深度樹匹配方法^[7,8]。該方法使用了樹索引結(jié)構(gòu)來(lái)解決檢索的效率問(wèn)題，因?yàn)榛跇涞臋z索算法時(shí)間復(fù)雜度為對(duì)數(shù)級(jí)別，所以即使面對(duì)超大規(guī)模商品庫(kù)也能夠勝任；以在樹索引結(jié)構(gòu)中檢索相關(guān)商品為目標(biāo)，得益于樹檢索天然的復(fù)雜度優(yōu)勢(shì)及 GPU 等硬件提供的強(qiáng)勁算力，任意的深度模型都可以被用作檢索模型，來(lái)學(xué)習(xí)如何在樹索引中檢索目標(biāo)，而不局限于內(nèi)積模型的形式，因此打開了模型能力的天花板。此外，樹索引和檢索模型，可以在數(shù)據(jù)驅(qū)動(dòng)的方式下進(jìn)行聯(lián)合優(yōu)化來(lái)達(dá)到系統(tǒng)整體效能的最優(yōu)。深度樹匹配方案在阿里媽媽展示廣告核心資源位已經(jīng)全面應(yīng)用，取得了顯著的實(shí)際業(yè)務(wù)提升。

主辦方從工業(yè)界實(shí)踐中面臨的實(shí)際問(wèn)題與挑戰(zhàn)出發(fā)，希望參賽選手能結(jié)合業(yè)界當(dāng)前技術(shù)的整體發(fā)展階段，思考如何在召回階段盡可能地利用系統(tǒng)算力資源，來(lái)實(shí)現(xiàn)最優(yōu)檢索的目標(biāo)，進(jìn)而孕育出解決問(wèn)題的新方法。

核心思路

初賽方案僅基于規(guī)則做了 Match 階段，里面有些技巧，感興趣的同學(xué)可以關(guān)注薛傳雨的 github（https://github.com/ChuanyuXue/CIKM-2019-AnalytiCup），之后會(huì)在上面發(fā)布代碼。下面重點(diǎn)闡述復(fù)賽方案。圖  1 給出了推薦系統(tǒng)的經(jīng)典流程，先從千萬(wàn)級(jí)商品庫(kù)中為指定用戶召回幾百或幾千個(gè)候選商品，再建模為候選商品排序，選出少量商品作為最終的推薦列表。

 

圖1 推薦系統(tǒng)經(jīng)典流程

數(shù)據(jù)分析與探索

數(shù)據(jù)分析與探索對(duì)方案設(shè)計(jì)有重要的指導(dǎo)作用。下面介紹幾個(gè)關(guān)鍵的分析。在做 EDA 時(shí)，數(shù)據(jù)集被切分為了兩部分，第 1~14 天日志被視為“歷史”行為，第 15 天日志視為“未來(lái)”行為，從而可以分析對(duì)“未來(lái)”行為有重要影響的“歷史”行為特點(diǎn)。

圖 2 用戶對(duì)“歷史”感興趣同類商品的“未來(lái)”行為統(tǒng)計(jì)分析。

用戶行為共有 4 種類型：’pv’（瀏覽）、’fav’（喜歡）、’cart’（加入購(gòu)物車）和’buy’（購(gòu)買）。按照感興趣程度，可將這4種類型的權(quán)重依次設(shè)為 1、2、3、4（論壇發(fā)布的初賽 baseline 即是這樣設(shè)置，效果尚可）。圖 2 先獲取了用戶“歷史”感興趣的商品類別，然后統(tǒng)計(jì)了“未來(lái)”對(duì)歷史感興趣的同類別商品的行為。圖 2 表明“未來(lái)”感興趣的商品（出現(xiàn)在第 15 天日志中的商品）幾乎不會(huì)是以往購(gòu)買過(guò)的同類商品。因而，在復(fù)賽方案中將’buy’的權(quán)重設(shè)為 1。實(shí)際上，4 種行為的權(quán)重仍可調(diào)優(yōu)，但限于時(shí)間和精力未做。

圖 3 “未來(lái)”感興趣商品在第 1~14 天被感興趣的次數(shù)

如圖 3 所示，“未來(lái)”感興趣商品在第 14 天被感興趣的次數(shù)組多，距第 14 天越遠(yuǎn)次數(shù)越少。因而，考慮時(shí)間因素對(duì)行為重要性的影響，按下式調(diào)整行為權(quán)重：

其中，是四種行為的權(quán)重，T_u,i 代表距最大時(shí)間戳 D_max 的遠(yuǎn)近，R_u,i 是考慮時(shí)間因素后評(píng)估用戶 u 對(duì)商品 i 的感興趣程度。

圖 4 沒有區(qū)分行為的種類，統(tǒng)一分析了用戶在“未來(lái)”是否仍會(huì)對(duì)“歷史”感興趣的商品類別及店鋪感興趣。如圖 4-(a) 所示，用戶在“未來(lái)”仍會(huì)對(duì)“歷史”感興趣的商品類別有較高興趣；圖 4-(b) 則表明，用戶在“未來(lái)”對(duì)歷史感興趣的店鋪有較低的興趣。進(jìn)而，針對(duì)類別/店鋪提取了一些特征，詳見對(duì)排序階段的介紹。

 

             (a)         

        

                (b)

圖 4 用戶是否仍會(huì)對(duì)“歷史”感興趣的商品類別及店鋪感興趣。

召回階段

 

圖 5 基于 Item CF 的召回流程

召回的策略有很多，即使是基于規(guī)則的策略效果也可以。在復(fù)賽后期，團(tuán)隊(duì)花費(fèi)了很大精力實(shí)現(xiàn)了一種 Item CF 算法，效果也有明顯提升。圖 5 給出了基于 Item CF 做召回的流程，先利用龐大的歷史日志統(tǒng)計(jì) item-item 相似性矩陣，再結(jié)合目標(biāo)用戶的歷史行為做推薦。實(shí)現(xiàn)的難點(diǎn)在于對(duì)約 8000 萬(wàn)歷史日志做統(tǒng)計(jì)的復(fù)雜度太高，需要做優(yōu)化代碼、做并行化處理。

如圖 6 所示，將用戶分為了若干組，并行處理每組內(nèi) item-item 共現(xiàn)頻率的統(tǒng)計(jì)，最終將與每個(gè)商品最相似性的 500 個(gè)商品存在字典中。實(shí)際上，對(duì)復(fù)賽訓(xùn)練集統(tǒng)計(jì)后，發(fā)現(xiàn)字典中鍵值數(shù)僅有 40 多萬(wàn)。 此外，為了提高效率，團(tuán)隊(duì)使用了 Cython 實(shí)現(xiàn)統(tǒng)計(jì)共現(xiàn)頻率的代碼。整個(gè)流程較復(fù)雜，感興趣的同學(xué)可以看隨后開源的代碼。

 

圖 6 并行統(tǒng)計(jì) item-item 相似性，并轉(zhuǎn)存為字典

Item CF 相似性指標(biāo)關(guān)乎召回的效果。在實(shí)現(xiàn)時(shí)團(tuán)隊(duì)借鑒了 2015 年騰訊 SIGMOD 論文 [1]。在 9 月初，按照關(guān)聯(lián)規(guī)則中置信度計(jì)算 Item CF 相似性如下：

 

其中，代表對(duì)商品感興趣的用戶集合。顯然，?；谠撝笜?biāo)做召回，線上效果為0.045。

在此基礎(chǔ)上，考慮到用戶活躍度（感興趣的商品數(shù)）對(duì)相似性的影響，改進(jìn)了上述指標(biāo)：

 

其中，是全體用戶集合，Ui 是對(duì)商品 i 感興趣的用戶集合；Wu 代表用戶 u 對(duì)相似性的貢獻(xiàn)度，代表用戶感興趣的商品集合。當(dāng)  w—>1 時(shí)，等價(jià)于?；诟倪M(jìn)指標(biāo)做召回，并做了些額外處理，線上效果為 0.053。

排序階段

召回階段獲得少量（300 或 500）候選商品后，可以構(gòu)建排序模型獲得最終的推薦列表。我們將排序任務(wù)轉(zhuǎn)化為二類判別問(wèn)題。在建模前，需要切分?jǐn)?shù)據(jù)集。如圖 7 所示，利用第 1-15 天數(shù)據(jù)做召回、生成特征，利用第 16 天的數(shù)據(jù)生成標(biāo)簽，從而生成線上訓(xùn)練集；利用 1-16 天數(shù)據(jù)做召回、生成特征，生成線上測(cè)試集，加載訓(xùn)練后的模型及相關(guān)文件完成預(yù)測(cè)。

需要特別注意的是，訓(xùn)練集中的正樣本和負(fù)樣本都是從召回列表中生成的，而不是將每個(gè)用戶感興趣的商品都拿出來(lái)做正樣本。這是因?yàn)椋芏嘤脩舾信d趣的商品對(duì)應(yīng)的特征取值都無(wú)法統(tǒng)計(jì)，使得這些正樣本失去了統(tǒng)計(jì)意義，對(duì)訓(xùn)練模型有負(fù)面影響。另一個(gè)賽道的亞軍也是這樣做的，他的解釋也很好，“希望建模樣本與召回樣本同分布”。本賽道很多同學(xué)都未能建模做 Ranking，應(yīng)該是沒能發(fā)現(xiàn)采樣的技巧。

圖 7 排序階段劃分?jǐn)?shù)據(jù)

圖 8 為提取的特征列表，只有 64 個(gè)。其中，Item CF 的相似性特征是強(qiáng)特征。最終使用了 Catboost 和 Lightgbm 建模。Catboost 對(duì)過(guò)擬合的處理較好，使用了全部特征（線上效果為 0.0616）；Lightgbm 使用全部特征效果不佳，故做了特征選擇，最終只使用了 36 個(gè)特征。

圖 8 特征列表（共 64 個(gè)）

為了減少特征的數(shù)量，在比賽中使用了多種特征選擇方法。雖然 xgboost、lightgbm、catboost 可以做特征重要性分析，但很多同學(xué)可能注意到把選出的重要特征給梯度提升樹模型建模并無(wú)明顯提升。我們做特征選擇的思路是“劣汰優(yōu)勝”，先基于獨(dú)立性檢驗(yàn)剔除關(guān)聯(lián)弱的特征，再?gòu)氖Ｓ嗵卣髦羞x擇重要性高的特征。兩變量獨(dú)立是指兩變量既不存在線性相關(guān)性，也不存在非線性關(guān)聯(lián)。我們采用 Mean Variance Test^[2,3] 做“劣汰”，這是首都師范大學(xué)崔恒建教授 2015 年發(fā)表于統(tǒng)計(jì)領(lǐng)域頂刊 JASA 的工作，2018 年進(jìn)行了拓展，可用于做獨(dú)立性檢驗(yàn)及特征選擇。該方法可檢驗(yàn)一個(gè)離散型變量與一個(gè)連續(xù)型變量間是否獨(dú)立，對(duì)變量的分布無(wú)假定（Distribution free），并且計(jì)算簡(jiǎn)單（只是計(jì)數(shù)）。這里僅列出其部分理論（圖 9），感興趣的同學(xué)可以交流，該方法已被 Chuanyu 做成了工具包，已開源在他的 github。此外，團(tuán)隊(duì)成員在 IJCAI 2018 和資金流入流出預(yù)測(cè)課程視頻（天池 AI 課程，之后可能上線）中都使用 Mean Variance Index 做過(guò)特征選擇，效果都不錯(cuò)。

圖 9 Mean Variance Test簡(jiǎn)介

最后，團(tuán)隊(duì)進(jìn)行了簡(jiǎn)單的模型融合。為了提高穩(wěn)健性，依次采用了調(diào)和平均值、幾何平均值和算數(shù)表均值（圖 10），線上效果為 0.0622。

圖 10 模型融合

其他嘗試

還有一些基于規(guī)則的策略及其他方案沒有介紹。例如，基于同類商品的規(guī)則做召回、基于同店鋪的規(guī)則做召回、基于 word2vector 的思路做召回（借助 faiss）、基于 MinHash LSH 做 Item CF、取最近 100 條用戶行為做統(tǒng)計(jì)等等。感興趣的同學(xué)可以交流。

比賽的收獲與感想

參加 CIKM 挑戰(zhàn)賽的原因有二：（1）希望驗(yàn)證自身技術(shù)和研究?jī)r(jià)值；（2）參加會(huì)議，與專家交流，幫助薛傳雨申請(qǐng) 2020Fall 的博士或研究型碩士（可聯(lián)系 cs_xcy@126.com）。受限于復(fù)賽任務(wù)要求，我們沒能在比賽中使用開發(fā)的推薦系統(tǒng)框架（一種基于組間效應(yīng)的增量推薦系統(tǒng)框架[4]）。

想法比套路重要得多。大家在做比賽時(shí)，應(yīng)該把精力放在數(shù)據(jù)分析與探索，從而提取有用的規(guī)則，利用規(guī)則進(jìn)行初步想法的驗(yàn)證；進(jìn)而，基于規(guī)則生成特征，再考慮建模、模型融合。其次要敢于嘗試新的思路，比起在原來(lái)的方案上調(diào)整參數(shù)，對(duì)算法進(jìn)行改進(jìn)或引入新算法可能會(huì)帶來(lái)更有大的提升。另一方面，建議大家學(xué)好統(tǒng)計(jì)，讀讀統(tǒng)計(jì)學(xué)領(lǐng)域的論文，有助于加深對(duì)機(jī)器學(xué)習(xí)的理解。此外，在比賽后幾天，要休息好、能沉住氣，不能過(guò)于急躁。最后，僅僅提高技術(shù)是不足夠的，學(xué)好英語(yǔ)、提高表達(dá)能力也很關(guān)鍵。

參考文獻(xiàn)

[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

雷鋒網(wǎng)

雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。