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

語言: CN / TW / HK

反饋快速,競爭激烈的演算法比賽是演算法從業者提升技術水平的重要方式,從若干行業核心問題抽象出的演算法比賽具有很強的實際意義。本文結合筆者在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]。而本次競賽為了更好地衡量推薦系統對歷史低熱度商品的推薦效果,選手的成績主要採用NDCG@50_half指標進行排名。該指標是從整個評測資料集中取出一半歷史曝光少的點選商品,由於是低熱度且有被點選的商品,可以跟更好的評估偏差問題。本次比賽包含了以下挑戰:

  • 賽題只提供點選資料,構造候選集時需要考慮選擇性偏差問題。
  • 不同商品熱度差異大,商品歷史點選次數呈現一個長尾分佈,資料存在嚴重的流行度偏差問題,並且評估指標 NDCG@50_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萬條,構成知識圖譜。使用Hitrate@5作為評價指標。

資料預處理階段:進行特徵分類、異常值處理、統一編碼等操作。主要涉及使用者(使用者畫像特徵等)、商家(品類、評分、品牌等)、菜品(口味、價格、食材等)三種實體資料及點選、購買(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比賽連結: https://www.kaggle.com/c/outbrain-click-prediction.
  • [27] KDD Cup 2020 Debiasing比賽連結 https://tianchi.aliyun.com/competition/entrance/231785/introduction.
  • [28] KDD Cup 2018比賽連結:https://www.biendata.xyz/competition/kdd_2018/.
  • [29] KDD Cup 2017比賽連結:https://tianchi.aliyun.com/competition/entrance/231597/introduction.
  • [30] KDD Cup 2020 AutoGraph比賽連結:https://www.automl.ai/competitions/3

招聘資訊

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

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

崗位要求

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

具備以下條件優先

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

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

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

前端 | 演算法 | 後端 | 資料 | 安全 | 運維 | iOS | Android | 測試

| 在公眾號選單欄對話方塊回覆【2020年貨】、【2019年貨】、【2018年貨】、【2017年貨】等關鍵詞,可檢視美團技術團隊歷年技術文章合集。

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