7次KDD Cup&Kaggle冠軍的經驗分享:從多領域優化到AutoML框架

美團技術團隊 2022-01-07 18:04:41 阅读数:528

kdd cup&kaggle cup kaggle 分享

反饋快速,競爭激烈的算法比賽是算法從業者提昇技術水平的重要方式,從若幹行業核心問題抽象出的算法比賽具有很强的實際意義。本文結合筆者在7次Kaggle/KDD Cup中的冠軍經驗,對於多領域建模優化,AutoML技術框架,以及面對新問題如何分析建模三個方面進行了介紹。希望能够讓讀者收獲比賽中的通用高效建模方法與問題理解思路。

1 背景與簡介

反饋快速、競爭激烈的算法比賽是算法從業者提昇技術水平的重要方式。從若幹行業核心問題中抽象出的算法比賽題目具有很强的實際意義,而比賽的實時積分榜促使參加者不斷改進,以試圖超越當前的最佳實踐,而且獲勝方案對於工業界與學術界也有很强的推動作用,例如KDD Cup比賽產出的Field-Aware Factorization Machine(FFM)算法[1]、ImageNet比賽產出的ResNet模型[2]在業界都有著廣泛的應用。

美團到店廣告質量預估團隊在美團內部算法大賽MDD Cup中獲得了第一名,受大賽組委會的邀請,希望分享一些比較通用的比賽經驗。本文是筆者7次Kaggle/KDD Cup冠軍經驗(如下圖1所示)的分享,希望能幫助到更多的同學。

圖1 國際頂級比賽冠軍經曆

大家都知道,Kaggle/KDD Cup的比賽均為國際頂級賽事,在比賽圈與工業界有著很大的影響力。具體而言,Kaggle是國際上最大的頂級數據挖掘平臺,擁有全球幾十萬用戶,通過高額獎金與分享氛圍產出了大量優秀算法方案,例如Heritage Health獎金高達三百萬美元。目前,Kaggle比賽在艾滋病研究、棋牌評級和交通預測等方面均取得了突出成果,得益於此,Kaggle平臺後來被Google公司收購。

ACM SIGKDD (國際數據挖掘與知識發現大會,簡稱 KDD)是數據挖掘領域的國際頂級會議。KDD Cup比賽是由SIGKDD主辦的數據挖掘研究領域的國際頂級賽事。從1997年開始,每年舉辦一次,是目前數據挖掘領域最具影響力的賽事。該比賽同時面向企業界和學術界,雲集了世界數據挖掘界的頂尖專家、學者、工程師、學生等參加,為數據挖掘從業者們提供了一個學術交流和研究成果展示的平臺。

通過分析不難發現,KDD Cup舉辦20年來,一直緊密結合工業界前沿與熱點問題,演進主要分為三個階段。第一階段從2002年左右開始,專注於互聯網的熱點推薦系統方面問題,包括推薦、廣告,行為預測等;第二階段聚焦在傳統行業問題,比較關注教育、環境、醫療等領域;而在第三階段,自2019年以來,重點關注非監督問題,例如AutoML、Debiasing、强化學習等問題,這類比賽的共同特點是通過以前方法難以解决現有的新問題。這三個階段趨勢也一定程度反應著當前工業界與學術界的難點與重點,無論從方式、方法,還是從問題維度,都呈現出從窄到寬,從標准向非標准演進的趨勢。

圖2 KDD Cup近20年問題趨勢

本文會先介紹筆者的7次KDD Cup/Kaggle比賽冠軍的方案與理解,問題涉及推薦、廣告、交通、環境、人工智能公平性等多個領域問題。接著會介紹在以上比賽中發揮關鍵作用的AutoML技術框架,包括自動化特征工程,自動化模型優化,自動化模型融合等,以及如何通過該技術框架系統性建模不同的問題。最後再介紹以上比賽形成的通用方法,即面對一個新問題,如何進行分析、理解、建模、與挑戰解决、從而實現問題的深度優化。

本文主要面向以下兩類讀者,其他感興趣的同學也歡迎了解。

  • 算法比賽愛好者,希望理解國際數據挖掘頂級比賽冠軍方案的方法與邏輯,取得更好的名次。
  • 工業界工程師與研究員,借鑒比賽方法,應用於實際工作,取得更優的結果。

2 多領域建模優化

本部分將我們將以上比賽分為三個部分進行方案介紹,第一部分為推薦系統問題;第二部分為時間序列問題,跟第一部分的重要差別在於預測的是未來的多點序列,而非推薦系統的單點預估;第三部分為自動化機器學習問題,該問題比賽輸入不為單一數據集,而是多問題的多數據集,並且在最終評估的b榜數據集問題也是未知的。因此,對於方案的魯棒性要求非常高。如錶1所示,後續將具體介紹七個比賽賽道的獲勝方案,但會合並為五個核心解决方案進行具體的介紹。

錶1 競賽及解决方案

2.1 推薦系統問題

本節主要介紹Kaggle Outbrain Ads Click Prediction和KDD Cup 2020 Debiasing比賽。二者任務都是面向用戶下一次點擊預估問題,但因為應用場景與背景的不同,存在著不同的挑戰:前者的數據規模龐大,涉及到數億個用戶在千級別數量异構站點上的數十億條瀏覽記錄,對模型優化、融合有著嚴格的要求;後者則尤為關注推薦系統中的偏差問題,要求參賽選手提出有效的解决方案,來緩解選擇性偏差以及流行度偏差,從而提高推薦系統的公平性。本節將分別介紹這兩場比賽。

Kaggle Outbrain Ads Click Prediction:基於多層級多因子的模型融合方案

競賽問題與挑戰:競賽要求在Outbrain網頁內容發現平臺上,預估用戶下一次點擊網頁廣告,具體參考:Kaggle Outbrain比賽介紹詳情[26]。參賽選手會面對以下兩個重要挑戰:

  • 异構性:平臺提供需求方平臺(DSP)廣告投放服務,涉及到用戶在數千個异質站點上的行為刻畫。
  • 超高維稀疏性:特征高維稀疏,數據規模龐大,包含了7億個用戶、20億次瀏覽記錄。

基於多層級多因子的模型融合方案:針對本次賽題的挑戰,我們隊采用了基於多層級多因子的模型融合方案來進行建模。一方面對於异構站點行為,單一模型不易於全面刻畫,另一方面,億級別的數據規模給多模型的分別優化帶來了較大的空間。由於FFM具有强大的特征交叉能力以及較强的泛化能力,能更好地處理高維稀疏特征。因此,我們選擇該模型作為融合基模型的主模型。模型融合通過不同模型學習到有差异性的內容,從而有效挖掘用戶在不同站點上的异質行為。模型融合的關鍵是產生並結合“好而不同”的模型[3][4]。基於多層級多因子的模型融合方案首先通過模型差异性、特征差异性多個角度來構造模型之間的差异性,然後通過多層級以及使用基學習器的多特征因子(模型pCTR預估值、隱層錶征)進行融合:

圖3 多層級多因子模型融合

具體地,如上圖3所示。第一層級的目的是構建出有差异性的單個模型,主要通過不同類型的模型在用戶最近行為、全部行為數據以及不同特征集合上分別進行訓練,來產生差异性。第二層級則通過不同單個模型的組合進一步產生差异性,差异性的提昇來源於兩個方面,分別是模型組合方式的不同(用不同模型,根據單模型特征進行打分)以及用於模型組合的特征因子的不同,這裏特征因子包括模型的打分以及模型中的隱層參數。第三層級則是考慮如何將不同融合結果組合在一起。由於劃分出來的驗證數據集較小,如果使用複雜非線性模型往往容易過擬合。所以這裏使用了一個基於約束的線性模型來獲得第二層級模型的融合權重。

上述方案同我們業務中模型相比,采用更多的模型融合,在取得高精度的同時產生了更高的開銷,而在實際業務中要更加注重效果與效率的平衡。

KDD Cup 2020 Debasing:基於i2i多跳遊走的Debiasing方案

競賽問題與挑戰:競賽是以電子商務平臺為背景,預估用戶下一次點擊的商品。並圍繞著如何緩解推薦系統中的選擇性偏差以及流行度偏差進行展開,具體參考:KDD Cup 2020 Debiasing比賽介紹詳情[27]。推薦系統中的偏差問題有很多,除了上述兩種偏差,還有曝光偏差、比特次偏差等等[5][6]。我們團隊之前也對比特次偏差進行了相關研究[7]。而本次競賽為了更好地衡量推薦系統對曆史低熱度商品的推薦效果,選手的成績主要采用[email protected]_half指標進行排名。該指標是從整個評測數據集中取出一半曆史曝光少的點擊商品,由於是低熱度且有被點擊的商品,可以跟更好的評估偏差問題。本次比賽包含了以下挑戰:

  • 賽題只提供點擊數據,構造候選集時需要考慮選擇性偏差問題。
  • 不同商品熱度差异大,商品曆史點擊次數呈現一個長尾分布,數據存在嚴重的流行度偏差問題,並且評估指標 [email protected]_half 用於考察低熱度商品的排序質量。

基於i2i遊走的Debiasing排序方案:我們的方案為基於i2i建模的排序框架。如圖所示,整體流程包含四個階段:i2i構圖與多跳遊走、i2i樣本構建、i2i建模以及u2i排序。前兩個階段解决了選擇性偏差問題,後兩個階段則側重於解决流行度偏差問題。

圖4 基於i2i的建模框架

第一個階段是基於用戶行為數據和商品多模態數據構建i2i圖,並在該圖上多跳遊走生成候選樣本。這種方式擴大了商品候選集,更好地近似系統真實候選集,緩解了選擇性偏差。

第二個階段是根據不同i2i關系計算i2i候選樣本的相似度,從而决定每種i2i關系下候選樣本的數量,最終形成候選集。通過不同候選的構造方法,探索出更多有差异的候選商品,可以進一步緩解選擇性偏差問題。

第三個階段包括基於i2i樣本集的自動化特征工程,以及使用流行度加權的損失函數進行消除流行度偏差的建模。自動化特征工程中包含了商品多模態信息的刻畫,這類信息能够反應商品在熱度信息以外的競爭關系,能够一定程度上緩解流行度偏差問題。而流行度加權的損失函數定義如下:

其中,參數α與流行度成反比,來削弱流行商品的權重,從而消除流行度偏差。參數β是正樣本權重,用於解决樣本不平衡問題。

第四個階段首先將i2i打分通過Max操作進行聚合,突出打分集合中低熱度商品的高分信號,從而緩解流行度偏差問題。然後對商品列錶的打分結合商品熱度進行調整處理,進而緩解流行度偏差問題。

關於該比賽的更多細節,大家可以參考《KDD Cup 2020 Debiasing比賽冠軍技術方案及在美團的實踐》一文。

2.2 時間序列問題

時序系列問題:時間序列問題相比於推薦系統問題的有較大差异。在任務上,推薦系統預測的是未來單個點,而時間序列預測未來多個點;在數據上,推薦系統通常包含用戶、商品、上下文等多維信息,時間序列通常包含時間空間上變化的數值序列信息。

時間序列競賽:在本文中,時間序列競賽主要介紹KDD Cup 2018 Fresh Air和KDD Cup 2017 HighWay Tollgates Traffic Flow Prediction。它們都是時間序列問題,前者是預測未來兩天的污染物濃度以及變化,後者是預測未來幾個小時高速交通情况和變化。它們的共同點一是傳統行業問題,實際意義强;二是存在各種突變性、穩定性低;三是都涉及到多地域、多空間問題,需結合時空進行建模。它們的异同點是污染物濃度突變需要一個短期時間才能發生,數據在突變時存在一定規律性,但交通突變具有强偶發性,交通道路容易受到偶發性車禍、偶發性地質灾害等影響,數據不會呈現出明顯的規律性。

KDD Cup 2018 Fresh Air:基於時空門控DNN和Seq2Seq的空氣質量預測方案

競賽問題及挑戰:競賽目標是預測北京和倫敦48個站點在未來48小時裏PM2.5/PM10/O3的濃度變化,具體參考: KDD Cup 2018比賽介紹詳情[28]。參賽選手需要解决以下兩個挑戰:

  • 時序性:預測未來48小時的污染濃度情况,實際污染物濃度存在突變的情况。如圖5所示,站點2在05-05以及05-06、05-07之間存在大量的波動和突變。
  • 空間性:不同站點上污染物濃度有明顯差异,並且和站點之間的拓撲結構相關聯。如圖所示,站點1、2的波形有較大差別,但是在05-07產生了相同的凸起。

圖5 時空挑戰圖

基於Spatial-temporal Gated DNN與Seq2Seq的模型融合方案[9]:為了强化時間序列和空間拓撲的建模,我們引入了Spatial-temporal Gated DNN與Seq2Seq兩個模型,並與LightGBM一起構建模型融合方案,具體如下。

(1)Spatial-temporal Gated DNN:對於時序問題而言,由於未來預測臨近時間點的統計特征值差异較小,直接使用DNN模型會使得不同小時和站點的預測值差异性小,因此我們在DNN中引入Spatial-temporal Gate來突出時空信息。如下圖6所示,Spatial-temporal Gated DNN采用了雙塔結構,拆分了時空信息和其他信息,並且通過門函數來控制和强調時空信息,最終能够提高模型對時空的敏感度,實驗中發現引入swish激活函數f(x) = x · sigmoid(x)能提昇模型精度。

圖6 Spatial-temporal Gated DNN

(2)Seq2Seq:盡管Spatial-temporal Gated DNN相比DNN對時空信息進行了强化,但是它們的數據建模方式都是將樣本的曆史數據複制48份,分別打上未來48小時的標簽,相當於分別預測48小時的污染濃度值。這種方式其實和時間序列預測任務有所脫離,失去了時間連續性。而Seq2Seq建模方式可以很自然地解决這一問題,並且取得了不錯的效果。下圖7是本次比賽中,我們采用的Seq2Seq模型結構。針對時序性挑戰,曆史天氣特征通過時間前後組織成序列輸入到編碼器當中,解碼器依賴於編碼結果以及未來天氣預報特征進行解碼,得到48小時的污染物濃度序列。未來天氣預報信息對齊到解碼器每個小時的解碼過程中,解碼器可以通過天氣預報中的天氣信息(比如風級、氣壓等)來有效預估出突變值。針對空間性挑戰,方案在模型中加入站點嵌入以及空間拓撲結構特征來刻畫空間信息,在模型中和天氣信息進行拼接以及歸一化,從而實現時空聯合建模。

圖7 Seq2Seq模型

(3)模型融合:我們隊采用了Stacking融合的方式,單個學習器通過不同模型、數據、建模方式來構建差异性。LightGBM模型使用了天氣質量、曆史統計、空間拓撲等特征,Spatial-temporal Gate則是引入了門結構,强化了時空信息。Seq2Seq利用序列到序列的建模方式,刻畫了序列的連續性、波動性。最後使用了基於約束的線性模型將不同的單個學習器進行融合。

更多詳情,大家可參考SIGKDD會議論文:AccuAir: Winning Solution to Air Quality Prediction for KDD Cup 2018

KDD Cup 2017 Traffic Flow Prediction:基於交叉驗證降噪與多損失融合的高穩定性交通預測方案

競賽問題及挑戰:競賽目標是以20分鐘為時間窗口,給定前2小時高速公路入口到關卡的行駛狀况,預測未來2小時的行駛狀况,具體可參考:KDD Cup 2017比賽介紹詳情[29]。競賽根據行駛狀况的不同,分為了行駛時間預測和交通流量預測兩個賽道。參賽選手需要解决以下兩個挑戰:

  • 數據小、噪聲多。如下圖8所示,框中時間段的數值分布和其他時間段的分布有明顯的差异。

圖8 交通流量數據中的噪音

  • 極值對結果影響大,評估指標使用了MAPE,如下式,其中 At 代錶實際值,Ft 代錶預測值,當實際值為較小值(特別為極小值)時,這一項對整個和式的貢獻擁有很大的權重。

基於交叉驗證降噪的極值點優化模型融合方案:

(1)基於交叉驗證的降噪,由於在線僅能進行一天一次的提交,並且最終的評測會由A榜測試集切到B榜測試集,並且由於A榜數據集小在線評測指標存在不穩定性,故而離線迭代驗證的方式就顯得尤為重要。為了能使離線迭代置信,我們采用兩種驗證方式進行輔助,第一種是下一天同時間段驗證,我們在訓練集最後M天上對每一天都取在線同一時間段的數據集,得到M個驗證集。第二種是N-fold天級采樣驗證,類似N-fold交叉驗證,我們取最後N天的每一天數據作為驗證集,得到N個驗證集。這兩種方法共同輔助模型離線效果的迭代,保證了我們在B榜上的魯棒性。

(2)極值點問題優化和模型融合:由於MAPE對於極值較敏感,我們在標簽、損失、樣本權重等不同方面分別進行多種不同處理,例如標簽上進行Log變換和Box-Cox變換,Log變換是對標簽進行Log轉換,模型擬合後對預估值進行還原,這樣能幫助模型關注於小值同時更魯棒,損失使用MAE、MSE等多種,樣本權重上利用標簽對樣本進行加權等,我們在XGBoost、LightGBM、DNN上引入這些處理生成多個不同模型進行模型融合,優化極值點問題,達到魯棒效果。

備注:特別感謝共同參加KDD Cup 2017的陳歡、燕鵬、黃攀等同學。

2.3 自動化機器學習問題

自動化機器學習問題[10]主要包括KDD Cup 2019 AutoML和KDD Cup 2020 AutoGraph比賽。該類問題,一般具有以下三個特性:

  • 數據多樣性强:15+個數據集,來源於不同領域問題,且不會標識數據來源,要求選手設計的自動化機器學習框架能够兼容多領域的數據,並對不同領域數據做出一定的適配。
  • 自動化的魯棒性:公共排行榜與私有榜評測數據不一樣,最終評分按照多個數據集的平均排名/得分得到,要求能够在不曾見過的數據集上得到魯棒的結果。
  • 性能限制:與現實問題搜索空間有較大對應,需要在有限時間和內存上求解。

KDD Cup 2020 AutoGraph:基於代理模型的自動多層次圖學習優化方案

競賽問題及挑戰:自動化圖錶示學習挑戰賽(AutoGraph)是第一個應用於圖結構數據的AutoML挑戰,詳情請見KDD Cup 2020 AutoGraph 比賽介紹[30]。競賽選擇圖結點多分類任務來評估錶示學習的質量,參與者需設計自動化圖錶示學習[11-13]解决方案。該方案需要基於圖的給定特征、鄰域和結構信息,高效地學習每個結點的高質量錶示。比賽數據從真實業務中收集,包含社交網絡、論文網絡、知識圖譜等多種領域共15個,其中5個數據集可供下載,5個反饋數據集評估方案在公共排行榜的得分,剩餘5個數據集在最後一次提交中評估最終排名。

圖9 AutoGraph圖數據集概覽

每個數據集給予了圖結點id和結點特征,圖邊和邊權信息,以及該數據集的時間預算(100-200秒)和內存算力(30G)。每個訓練集隨機將劃分40%結點為訓練集,60%結點為測試集,參賽者設計自動化圖學習解决方案,對測試集結點進行分類。 每個數據集會通過精度(Accuracy)來確定排名,最終排名將根據最後5個數據集的平均排名來評估。綜上,本次比賽需要在未見過的5個數據集上直接執行自動化圖學習方案,參賽者當時面臨著以下挑戰:

  • 圖模型具有高方差、穩定性低等特點。
  • 每個數據集都有嚴格的時間預算和內存算力限制。

基於代理模型的自動化多層次模型優化[14]

圖10 AutoHEnsGNN框架

多類別層次化圖模型優化:

(1)候選圖模型的生成:現實世界中的圖通常是多種屬性的組合,這些屬性信息很難只用一種方法捕捉完全,因此,我們使用了基於譜域、空域、Attention機制等多種不同類型的模型來捕捉多種屬性關系。不同模型在不同數據集上效果差异較大,為了防止後續模型融合時加入效果較差的模型,會對GCN、GAT、APPNP、TAGC、DNA、GraphSAGE、GraphMix、Grand、GCNII等候選模型進行快速篩選,得到模型池。

(2)層次模型集成:這部分共包含兩個維度的集成。第一層為模型自集成,為了解决圖模型對初始化特別敏感,同種模型精度波動可達±1%的問題,采用了同模型的自集成,同時生成多個同種模型,並取模型預測的平均值作為該種模型的輸出結果,成功降低了同種模型方差,提高了模型在不同數據集上的穩定性。第二層為不同模型集成,為了有效地利用來自本地和全球鄰域的信息,充分捕獲圖的不同性質,我們采用加權集成了不同種類的圖模型,進一步提高性能。同時針對在參數搜索階段,需要同時優化模型內參數α,以及多種模型加權集成參數β,使用模型集成參數和模型內參數通過互迭代的梯度下降進行求解,有效提昇了速度。

圖11 多類別層次化圖模型優化

基於代理模型與最終模型的兩階段優化:數據集采樣,對子圖根據Label進行層次采樣,减少模型驗證時間;代理模型與Bagging,計算多個較小隱層模型的平均結果,快速對該類模型進行評估。使用Kendall Rank和SpeedUp平衡准確度與加速倍率,得到合適的代理模型。最終通過代理模型得到了最優的超參數,然後再對最終的大模型在搜索好的參數上進行模型訓練。

具體詳情,大家可參考團隊ICDE 2022論文,AutoHEnsGNN: Winning Solution to AutoGraph Challenge for KDD Cup 2020

3 AutoML技術框架

3.1 自動化框架概述

圖12 AutoML整體框架

經過上述的多場比賽,團隊在多領域建模中不斷總結與優化,抽象出其中較為通用的模塊,總結得到針對數據挖掘類問題時的一套較為通用的解决方案——AutoML框架。該框架包含數據預處理,自動化特征工程[15]和自動化模型優化[16-20]三個部分。其中數據預處理部分主要負責特征分類、數據編碼、缺失值處理等常見的基礎操作,不過多展開。主要針對AutoML框架的自動化特征工程和自動化模型優化兩個部分進行詳細介紹。

3.2 自動化特征工程

圖13 自動化特征工程

特征工程是機器學習中至關重要的工作,特征的好壞直接决定了模型精度的上限。目前常見的方式是人工手動對特征進行組合與變換,但人工特征挖掘存在速度較慢、無法挖掘全面等問題。因此,設計全面挖掘的自動化特征工程能够比較好地解决上述問題,自動化特征工程主要包含三個部分:

  • 一、二階特征算子:對數據的基礎操作,可以得到更為複雜的高階特征。特征算子包含三個,頻數編碼是指對於類別型特征在樣本中次數、nunique等值的統計。目標編碼指對數值型特征進行均值、求和、最大最小、百分比特等操作。時序差分是指對於對時間特征進行差分處理。一階算子使用一個實體計算,二階算子使用二個實體計算,如用戶在某品類下的訂單數量,使用了用戶與品類兩個實體。
  • 快速特征選擇:因為自動化特征工程是針對全部實體依次按照不同特征算子進行的笛卡爾積組合,會產生大量的無效特征,故需要進行快速特征選擇。使用LightGBM模型快速識別有效特征及無用特征,從指標提昇及特征重要性角度考慮,裁剪掉沒用的特征,同時標識重要特征與其他特征再次進行更為高階的組合。
  • 高階特征算子:基於一、二階特征算子組合構建的新特征,進一步與其他特征進行高階組合,基於K階(K>=1)的K+1高階組合循環迭代,能够產出大量人為考慮不足的高階特征。

高階特征算子按多實體結果是否完全匹配,分為Match方式——匹配全部實體,All方式——匹配部分實體,得到另一實體的全部值的計算結果,這樣兩種特征產出方式。下圖中舉例說明,Match方式匹配用戶與時間段兩個實體,得到用戶在該時間段的平均訂單價格;All方式則只匹配用戶,得到用戶在所有時間段的平均訂單價格。

圖14 高階算子特征產出方式

相較於DeepFM、DeepFFM等算法,自動化特征工程具有三個方面的優勢。首先在存在多錶信息的情况下,容易利用非訓練數據的信息,如在廣告場景中,通過特征可以利用自然數據的信息,相比直接使用自然數據訓練,不容易產生分布不一致等問題;其次,只通過模型自動交叉學習,對於某些强特征交叉沒有手動構造學習得充分,許多顯示交叉特征如用戶商品點擊率等往往有較强的業務意義,讓模型直接感知組合好的特征往往比自動學習特征間的關系更為簡單;第三方面對於許多高維度稀疏ID特征,如億級別以上的推薦或廣告場景中,DeepFM、DeepFFM對於這些特征的學習很難充分,自動化特征工程能給這些稀疏ID構造很强的特征錶示。

3.3 自動化模型優化

圖15 自動化模型優化

基於重要度的網格搜索:在我們框架中采用的是全局基於重要度按照貪心的方式進行搜索,加快速度;得到的最優結果再進行小領域更詳細網格搜索,緩解貪心策略導致的局部最優。根據以往比賽經驗,總結不同模型的超參重要性排序如下:

  • LightGBM:學習率>樣本不平衡率>葉子數>行列采樣等。
  • DNN:學習率>Embedding維度>全連接層數和大小。值得一提的是,超參搜索在整個迭代過程中會進行多次,同時迭代前期與迭代後期參數搜索策略也有所不同,迭代前期,一般會選擇更大的學習率,更小Embedding維度和全連接層數等,降低模型參數量加快迭代速度,而在後期則選擇更多參數,獲得更好的效果。
  • 模型融合:模型融合的關鍵點在於構造模型間的差异性,LightGBM和DNN的模型本身差异性較大,同種模型中差异性主要體現在,數據差异、特征差异、超參差异三個方面。數據差异主要通過自動化行采樣實現,自動生成不同數據采樣的模型;特征差异通過自動化列采樣,生成特征采樣的模型;超參差异通過高優參數擾動生成,在最優局部進行參數組網格局部擾動。模型融合方法一般Blending、Stacking或簡單Mean Pooling等,融合前進行需要進行模型粒度剪枝(去除效果較差的模型避免影響融合效果)與正則化。

3.4 AutoML框架近期實戰:MDD Cup 2021美團外賣圖譜推薦比賽冠軍方案

在2021年8-9月美團舉行的內部算法比賽MDD Cup 2021中,美團到店廣告平臺質量預估團隊應用了AutoML框架並獲得了冠軍。下面結合這場比賽,介紹框架在具體問題中的應用。

MDD Cup 2021需要參賽者根據用戶、商家在圖譜中的屬性、用戶的曆史點擊、實時點擊以及下單行為,預測下次購買的商家。包含四周的135萬個訂單行為,涉及20萬個用戶,2.9萬個商家,17.9萬個菜品,訂單關聯菜品數據共438萬條,構成知識圖譜。使用[email protected]作為評價指標。

數據預處理階段:進行特征分類、异常值處理、統一編碼等操作。主要涉及用戶(用戶畫像特征等)、商家(品類、評分、品牌等)、菜品(口味、價格、食材等)三種實體數據及點擊、購買(LBS、價格、時間等)兩類交互數據,對原始數據進行特征分類、數據編碼、缺失值處理等常見預處理操作。

自動化特征工程:一、二階特征算子,首先對於類別、數據、時序、標簽四類原始特征,按照可抽象的三種實體及兩類交互數據進行一、二階特征交叉,運用頻數編碼、目標編碼與時序差分算子操作,在多時段上統計得到一、二階統計特征。舉例說明,如頻數編碼可計算用戶點擊某商家的次數、用戶購買商家品類的nunique值,用戶在某場景的下單數量等。目標編碼可計算用戶的平均訂單價格,用戶點擊次數最多的商家品類等。時序差分可計算如用戶購買某口味菜品的平均時間差等。多時段統計則意味著上述特征均可在不同時段上計算得到。

圖16 多階特征交叉

快速特征選擇,上述自動產出的一、二階統計特征數量共有1000+,其中存在大量無效特征,故使用LightGBM模型,從指標提昇與重要性角度進行特征篩選與重要標識。如用戶 x 菜品口味的特征沒什麼效果,進行篩除;用戶最常購買的價格區間則很有效果,標識為重要特征進行高階組合。

高階特征算子,基於一、二階特征算子組合構建的新特征,可以作為輸入進行高階特征組合。這裏值得一提的是,高階特征組合存在兩種形式,第一種原始特征的更高階組合,如用戶在某個商家中最喜歡的菜品口味,結合三個實體,並不需要額外的運算,第二種需使用一、二階新特征,其中頻數編碼的結果可以直接使用,目標編碼與時序差分需要先進行數值分桶操作轉換為離散值後才可使用,如用戶訂單價格區間的眾數 x 商家訂單價格平均值的分桶的聯合count。循環進行特征組合與篩選後就得到了最終的特征集。

自動化模型優化:模型部分使用了LightGBM和DIN的融合方案,迭代過程中多次進行了自動超參搜索,通過自動化行、列采樣及最優參數局部擾動構造了具有差异性的多個模型,融合得到最終的結果。

4 通用建模方法與理解

本節會就比賽的通用建模方法進行介紹,即面對一個新問題,如何進行快速高效的整體方案設計。

4.1 建模框架與方法

在面對新問題時,我們主要將技術框架分為以下三個階段,即探索性建模、關鍵性建模、自動化建模。三個階段具有逐漸深化,進一步補充的作用。

圖17 三階段算法建模

探索性建模:比賽前期,首先進行問題理解,包括評估指標與數據錶理解,然後進行基礎的模型搭建,並線上提交驗證一致性。在一致性驗證過程中往往需要多次提交,找到同線上指標一致的評估方式。探索性建模的核心目標是要找到迭代思路與方法,所以需要對問題做多方面探索,在探索中找到正確的方向。

一般在非時序問題,采用N-fold方法構造多個驗證集,並可以靈活變換生成種子,得到不同的集合。而在時序問題,一般會采用滑窗方式,構造同線上提交時間一致的驗證集,並可以向前滑動k天,來構造k個驗證集。在多個驗證集評估中,可以參考均值,方差,極值等參考指標綜合評估,得到同線上一致的結果。

關鍵性建模:比賽中期,會就關鍵問題進行深挖,達成方案在榜單Top行列,在問題理解方面,會盡可能就評估方式進行損失函數自定義設計。

分類問題優化,可以結合Logloss、AUC Loss[21]、NDCG Loss等不同損失函數進行Mix Loss設計。而回歸問題的損失函數設計要更複雜,一方面可以結合平方誤差,絕對值誤差等進行損失函數設計,另一方面可以結合Log變換,Box-cox變換等解决回歸异常值等問題。

自動化建模:比賽後期,由於基於人的理解一方面在細節與角度有盲區,另一方面較難進行抽象關系的建模,所以我們會采用自動化建模進行補充。如下圖18所示,先基於關系型多錶輸入,進行自動化關聯,然後通過生成式自動化特征工程構建大量特征,再進行特征選擇與迭代,然後基於模型輸入進行自動化超參搜索與模型選擇,最終基於多模型進行自動化融合構建,將生成的多元化模型關系進行選擇與賦權。

圖18 自動化建模框架

自動化建模一般采用如圖18的框架,先進行多錶關聯,然後基於先擴展後過濾的邏輯進行特征選擇,下一步基於精選特征與多個超參範圍進行超參搜索,最後采用XGBoost[22]、LightGBM、DNN、RNN、FFM等不同模型進行自動化模型融合。

4.2 同工業界方法聯系

算法比賽相對於工業界實際情况而言,一個重要區別是工業界涉及線上系統,在工程方面性能的挑戰更大,在算法方面涉及更多的線上線下效果一致性問題。因此算法比賽會在模型複雜度、模型精度更進一步,在算法比賽中也產出了ResNet、Field-aware Factorization Machine(FFM)、XGBoost等算法模型,廣泛應用於工業界實際系統。

在空氣質量預測中,我們采用了時空結合的Spatial-temporal Gated DNN網絡進行有效建模,同空氣質量問題相接近,在美團的實際業務中也面臨著時空相結合的建模問題,以用戶行為序列建模為例。我們對用戶的曆史時空信息和當前時空信息進行了充分的建模和交互[24]。我們分辨出用戶行為的三重時空信息,即:用戶點擊發生時的時間、用戶請求發出的地理比特置、用戶所點擊的商戶的地理比特置。

基於上述三重時空信息,我們提出Spatio-temporal Activator Layer(如圖19):三邊時空注意力機制神經網絡來對用戶曆史行為進行建模,具體通過對請求經緯度信息、商戶經緯度信息和請求時間的交互進行學習。針對空間信息交叉,我們進一步采用地理比特置哈希編碼和球面距離相結合的方式;針對時間信息交叉,我們也采用絕對與相對時間相結合的方式,有效實現用戶行為序列在不同時空條件下的三邊錶達。最後,經上述網絡編碼後的時空信息經過注意力機制網絡融合,得到LBS場景下用戶超長行為序列對不同請求候選的個性化錶達。

相比較而言,比賽中的Spatial-temporal Gated DNN更注重時空融合信息對於預測值的影響,由於需要預測的時間序列問題,更側重於不同的時間、空間信息有能够將差异性建模充分。而在美團業務中的時空網絡注重於細粒度刻畫空間信息,源於不同的球面距離,不同的區塊比特置影響大,需要多重信息深度建模。更多詳情,大家可參考團隊的CIKM論文:Trilateral Spatiotemporal Attention Network for User Behavior Modeling in Location-based Search[23]

圖19 基於三邊時空注意力機制的用戶行為序列網絡

在實際建模中,相對於比賽涉及到更多線上部分,而比賽主要專注於離線數據集的精度極值。同Debiasing比賽相比,在實際線上系統中,涉及到Bias等更多的問題,以Position Bias為例,實際的展示數據高比特點擊率天然高於低比特,然而一部分是源於用戶高低比特之間的瀏覽習慣差异,因此對於數據的直接建模不足以錶征對於高低比特廣告點擊率與質量的評估。我們在美團實際廣告系統中,設計了比特置組合預估框架進行建模,取得不錯的效果,這裏不再詳述。具體詳情,大家可參考團隊SIGIR論文:Deep Position-wise Interaction Network for CTR Prediction[7]

4.3 建模關鍵理解

一致的評估方式是决定模型泛化能力的關鍵

在比賽的機制中,通常最終評測的Private Data和此前一直榜單的Public Data並不是一份數據,有時切換數據會有幾十名的名次抖動,影響最終排名。因此避免過擬合到常規迭代的Public Data是最終取勝的關鍵。那麼在此問題上,如何構造同線上分布一致的驗證集呢?從一致性角度,一般會構造時間間隔一致的驗證集。而部分問題數據噪音較重,可以用動態滑窗等方式構造多個驗證集相結合。一致的驗證集决定著後面的迭代方向。

大數據注重模型的深化,小數據注重模型的魯棒

不同數據集注重的內容不一樣,在數據充分的場景下,核心問題是模型深化,以解决特征之間交叉,組合等複雜問題。而在小數據下,因為噪音多,不穩定性强,核心問題是模型的魯棒。高數據敏感性是方案設計的關鍵。

方差與偏差的平衡是後期指導優化的關鍵

從誤差分解角度去理解,平方誤差可以分解為偏差(Bias)與方差(Variance)[25],在中前期模型複雜度較低時,通過提昇模型複雜度,能够有效减低偏差。而在偏差已經被高度優化的後期,方差的優化是關鍵,因此在後期會通過Emsemble等方式,在單模型複雜度不變的基礎上,通過模型融合優化結果。

AutoML的關鍵是人為先驗的不斷减少

在運用AutoML框架的同時,會有一些超參數等隱蔽的人為先驗,把AutoML技術也以模型視角來理解,同樣存在模型複雜度越高越容易過擬合的問題,迭代中的一個關鍵問題不是評估效果的好壞,而是方案是否存在不必要的超參數等信息,能否不斷地簡化AutoML的建模,不斷地自動化,自適應適配各類問題。

最後,也特別感謝Convolution Team、Nomo Team、Getmax Team、Aister Team等隊伍的隊友們。

總結

本文基於筆者7次算法比賽的冠軍經曆,分享推薦系統、時間序列及自動化機器學習等不同領域比賽中的算法經驗,接著結合具體問題介紹AutoML技術框架,最後總結比賽中通用的建模方案,結合工業界方案介紹其與比賽的聯系。希望文章中的一些算法比賽相關經驗能够幫助算法愛好者更好地參與競賽,能為大家提供一些思路,啟迪更多的工程師與研究員在實際工作中取得更優結果。未來,我們團隊將持續關注國際算法競賽,積極進行比賽思路與工業方案結合的嘗試,同時也歡迎大家加入我們團隊,文末附有招聘信息,期待你的郵件。

作者簡介

胡可、興元、明健、堅强,均來自美團廣告平臺質量預估團隊。

參考文獻

  • [1] Juan Y , Zhuang Y , Chin W S , et al. Field-aware Factorization Machines for CTR Prediction[C]// the 10th ACM Conference. ACM, 2016.
  • [2] He K , Zhang X , Ren S , et al. Identity Mappings in Deep Residual Networks[J]. Springer, Cham, 2016.
  • [3] Ali, Jehad & Khan, Rehanullah & Ahmad, Nasir & Maqsood, Imran. (2012). Random Forests and Decision Trees. International Journal of Computer Science Issues(IJCSI). 9.
  • [4] Robi Polikar. 2006. Ensemble based systems in decision making. IEEE Circuits and systems magazine 6, 3 (2006), 21–45.
  • [5] Jiawei Chen, Hande Dong, Xiang Wang, Fuli Feng, Meng Wang, and Xiangnan He. 2020. Bias and Debias in Recommender System: A Survey and Future Directions. arXiv preprint arXiv:2010.03240 (2020).
  • [6] H. Abdollahpouri and M. Mansoury, “Multi-sided exposure bias in recommendation,” arXiv preprint arXiv:2006.15772, 2020.
  • [7] Huang J, Hu K, Tang Q, et al. Deep Position-wise Interaction Network for CTR Prediction[J]. arXiv preprint arXiv:2106.05482, 2021.
  • [8] KDD Cup 2020 Debiasing比賽冠軍技術方案及在美團的實踐.
  • [9] Luo Z, Huang J, Hu K, et al. AccuAir: Winning solution to air quality prediction for KDD Cup 2018[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019: 1842-1850.
  • [10] He Y, Lin J, Liu Z, et al. Amc: Automl for model compression and acceleration on mobile devices[C]//Proceedings of the European conference on computer vision (ECCV). 2018: 784-800.
  • [11] Yang Gao, Hong Yang, Peng Zhang, Chuan Zhou, and Yue Hu. 2020. Graph neural architecture search. In IJCAI, Vol. 20. 1403–1409.
  • [12] Matheus Nunes and Gisele L Pappa. 2020. Neural Architecture Search in Graph Neural Networks. In Brazilian Conference on Intelligent Systems. Springer, 302– 317.
  • [13] Huan Zhao, Lanning Wei, and Quanming Yao. 2020. Simplifying Architecture Search for Graph Neural Network. arXiv preprint arXiv:2008.11652 (2020).
  • [14] Jin Xu, Mingjian Chen, Jianqiang Huang, Xingyuan Tang, Ke Hu, Jian Li, Jia Cheng, Jun Lei: “AutoHEnsGNN: Winning Solution to AutoGraph Challenge for KDD Cup 2020”, 2021; arXiv:2111.12952.
  • [15] Selsaas L R, Agrawal B, Rong C, et al. AFFM: auto feature engineering in field-aware factorization machines for predictive analytics[C]//2015 IEEE International Conference on Data Mining Workshop (ICDMW). IEEE, 2015: 1705-1709.
  • [16] Yao Shu, Wei Wang, and Shaofeng Cai. 2019. Understanding Architectures Learnt by Cell-based Neural Architecture Search. In International Conference on Learning Representations.
  • [17] Kaicheng Yu, Rene Ranftl, and Mathieu Salzmann. 2020. How to Train Your Super-Net: An Analysis of Training Heuristics in Weight-Sharing NAS. arXiv preprint arXiv:2003.04276 (2020).
  • [18] Haixun Wang, Wei Fan, Philip S Yu, and Jiawei Han. 2003. Mining concept-drifting data streams using ensemble classifiers. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. 226–235.
  • [19] Robi Polikar. 2006. Ensemble based systems in decision making. IEEE Circuits and systems magazine 6, 3 (2006), 21–45.
  • [20] Chengshuai Zhao, Yang Qiu, Shuang Zhou, Shichao Liu, Wen Zhang, and Yanqing Niu. 2020. Graph embedding ensemble methods based on the heterogeneous network for lncRNA-miRNA interaction prediction. BMC genomics 21, 13 (2020), 1–12.
  • [21] Rosenfeld N , Meshi O , Tarlow D , et al. Learning Structured Models with the AUC Loss and Its Generalizations.
  • [22] Chen T , Tong H , Benesty M . xgboost: Extreme Gradient Boosting[J]. 2016.
  • [23] Qi, Yi, et al. "Trilateral Spatiotemporal Attention Network for User Behavior Modeling in Location-based Search", CIKM 2021.
  • [24] 廣告深度預估技術在美團到店場景下的突破與暢想.
  • [25] Geurts P . Bias vs Variance Decomposition for Regression and Classification[J]. Springer US, 2005
  • [26] Kaggle Outbrain比賽鏈接: www.kaggle.com/c/outbrain-….
  • [27] KDD Cup 2020 Debiasing比賽鏈接 tianchi.aliyun.com/competition….
  • [28] KDD Cup 2018比賽鏈接:www.biendata.xyz/competition….
  • [29] KDD Cup 2017比賽鏈接:tianchi.aliyun.com/competition….
  • [30] KDD Cup 2020 AutoGraph比賽鏈接:www.automl.ai/competition…

招聘信息

美團到店廣告平臺算法團隊立足廣告場景,探索深度學習、强化學習、人工智能、大數據、知識圖譜、NLP和計算機視覺前沿的技術發展,探索本地生活服務電商的價值。主要工作方向包括:

  • 觸發策略:用戶意圖識別、廣告商家數據理解,Query改寫,深度匹配,相關性建模。
  • 質量預估:廣告質量度建模。點擊率、轉化率、客單價、交易額預估。
  • 機制設計:廣告排序機制、競價機制、出價建議、流量預估、預算分配。
  • 創意優化:智能創意設計。廣告圖片、文字、團單、優惠信息等展示創意的優化。

崗比特要求

  • 有三年以上相關工作經驗,對CTR/CVR預估、NLP、圖像理解、機制設計至少一方面有應用經驗。
  • 熟悉常用的機器學習、深度學習、强化學習模型。
  • 具有優秀的邏輯思維能力,對解决挑戰性問題充滿熱情,對數據敏感,善於分析/解决問題。
  • 計算機、數學相關專業碩士及以上學曆。

具備以下條件優先

  • 有廣告/搜索/推薦等相關業務經驗。
  • 有大規模機器學習相關經驗。

感興趣的同學可投遞簡曆至:[email protected](郵件標題請注明:廣平算法團隊)。

閱讀美團技術團隊更多技術文章合集

前端 | 算法 | 後端 | 數據 | 安全 | 運維 | iOS | Android | 測試

| 在公眾號菜單欄對話框回複【2020年貨】、【2019年貨】、【2018年貨】、【2017年貨】等關鍵詞,可查看美團技術團隊曆年技術文章合集。

| 本文系美團技術團隊出品,著作權歸屬美團。歡迎出於分享和交流等非商業目的轉載或使用本文內容,敬請注明“內容轉載自美團技術團隊”。本文未經許可,不得進行商業性轉載或者使用。任何商用行為,請發送郵件至[email protected]申請授權。

版权声明:本文为[美團技術團隊]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201071804402877.html