機器之心發布
機器之心編輯部
在不久前結束的 KDD Cup 2020 競賽中，美團到店廣告平臺搜索廣告算法團隊在 Debiasing、AutoGraph、Multimodalities Recall 三道賽題中獲得了兩冠一季的成績。本文將介紹該隊伍的解決方案。
ACM SIGKDD （國際數據挖掘與知識發現大會，簡稱 KDD）是數據挖掘領域的國際頂級會議。KDD Cup 比賽是由 SIGKDD 主辦的數據挖掘領域頂級賽事，該賽事自 1997 年開始，每年舉辦一次，是目前數據挖掘領域最具影響力的賽事。
KDD Cup 2020 共設置五道賽題（四個賽道），分別涉及 Debiasing（數據偏差問題）、Multimodalities Recall（多模態召回問題）、AutoGraph（自動化圖表示學習）、對抗學習問題和強化學習問題。
圖 1：KDD 2020 會議
美團到店廣告平臺搜索廣告算法團隊的黃堅強、胡可、漆毅、曲檀、陳明健、鄭博航、雷軍與中科院大學唐興元共同組建參賽隊伍 aister，參加了 Debiasing、AutoGraph、Multimodalities Recall 三道賽題，並最終在 Debiasing、AutoGraph 賽道中獲得冠軍（1/1895、1/149），在 Multimodalities Recall 賽道中獲得季軍（3/1433）。
圖 2：KDD Cup 2020 Debiasing、AutoGraph、Multimodalities Recall 賽題榜單
本文將分別介紹 aister 團隊針對 Debiasing、AutoGraph 和 Multimodalities Recall 三道賽題的解決方案。
Debiasing 賽題
賽題介紹與問題分析
KDD Cup Debiasing 賽題是電子商務用戶下一次點擊商品預測（Next-Item Prediction）問題，核心關注點在於如何解決推薦系統偏差。
推薦系統面臨的一個嚴峻挑戰是公平性（Fairness）問題，即如果機器學習系統配備了短期目標（例如短期的點擊、交易），單純朝短期目標進行優化將會導致嚴重的「馬太效應」，熱門商品容易受到更多的關注，冷門商品愈發被遺忘，從而造成系統中的流行度偏差。並且大多數模型和系統的迭代依賴於頁面瀏覽（Pageview）數據，而曝光數據是實際候選中經過模型選擇的一個子集，不斷地依賴模型選擇的數據與反饋再進行訓練，將形成選擇性偏差。
上述流行度偏差與選擇性偏差不斷積累，就會導致系統中的「馬太效應」越來越嚴重。因此，人工智慧公平性問題對於推薦系統的不斷優化至關重要，這將對推薦系統的發展以及生態環境產生深遠的影響。
賽題提供了用戶點擊數據與商品多模態數據，但用戶特徵數據大量缺失。為了聚焦消除偏差問題，賽題提供的評測指標包括 NDCG@50_full、NDCG@50_half、hitrate@50_full、hitrate@50_half。
NDCG@50_full、NDCG@50_half 這兩項指標用於排名評估。首先通過 NDCG@50_full 篩選出前 10% 的隊伍，然後在這些隊伍中使用 NDCG@50_half 進行最終排名。NDCG@50_half 是在長尾商品數據上進行評測，能夠更好地評估選手們對數據偏差的優化。
NDCG@50_full：與常規推薦系統評價指標 NDCG 一致，該指標在整個評測數據集上評估每次用戶請求所推薦的前 50 個商品列表的平均排序效果。該評測集被稱為 full 評測集。
NDCG@50_half：關注偏差問題。從整個 full 評測數據集中取出一半歷史曝光少的點擊商品，對這些商品的推薦列表進行 NDCG 指標評估。該評測集被稱為 half 評測集。
為了更好地理解賽題，該團隊對提供的數據進行了分析。
商品多模態數據分析：商品多模態數據包含文本向量及圖片向量，覆蓋率高達 92.52%，我們可以根據向量來計算商品間的文本相似度及圖片相似度。由於用戶信息及商品信息的缺少，如何利用好這些僅有的商品多模態向量對於整個任務而言是極其重要的。
選擇性偏差分析：如表 1 所示，該團隊對基於 i2i（item2item）點擊共現以及基於 i2i 向量相似度兩種 Item-Based 協同過濾方法所召回的商品候選集進行對比，發現兩種召回方法在評測集上都有一個較低的 hitrate。不管使用哪種方法，系統都存在較大的選擇性偏差，即推薦給用戶的樣本是根據系統來選擇的，真實的候選集合大大超過了推薦給用戶的樣本，導致訓練數據帶有選擇性偏差。進一步地，該團隊發現基於 i2i 點擊共現在 full 評測集上相對於 half 評測集有更高的 hitrate，說明其更偏好於流行商品；相反，基於 i2i 向量相似度的召回方法對於流行度無偏好。同時兩種方式召回的候選集只有 4% 的重複率，因此我們需要結合點擊共現和向量相似度兩種商品關係來生成更大的訓練集，從而緩解選擇性偏差。
表 1：i2i 點擊共現與 i2i 向量相似度的召回 hitrate
流行度偏差分析：如圖 3 所示，該團隊對商品的流行度進行了分析，其中橫坐標為商品點擊頻數，即商品流行度，縱坐標為商品個數。圖中對流行度做了截斷，橫坐標最大值本應為 228。可以看出，大部分商品的流行度較低，符合長尾分布。
圖中的兩個箱型圖分別是 full 評測數據集商品流行度的分布，以及 half 評測數據集商品流行度的分布。從這兩個箱型圖可以看出，流行度偏差存在於數據集中。整個 full 評測集中有一半評測數據是基於流行度較低的商品，而另一半評測數據商品的流行度較高，直接通過點擊商品去構建樣本，會導致數據中擁有較多流行度高的正例商品，從而形成流行度偏差。
圖 3：商品的流行度偏差
不同於傳統的封閉數據集點擊率預估問題（CTR 預估），上述數據特點與評測方式更關注偏差優化。賽題中主要存在兩種偏差：選擇性偏差（Selection Bias）和流行度偏差（Popularity Bias）。
選擇性偏差：曝光數據是由模型和系統選擇的，與系統中的全部候選集不一致。
流行度偏差：商品歷史點擊次數呈現長尾分布，因此流行度偏差存在於頭部商品和尾部商品之間。如何解決流行度偏差是賽題的核心挑戰之一。
冠軍解決方案
針對選擇性偏差和流行度偏差這兩項挑戰，aister 團隊進行了建模設計，有效地優化了上述偏差。已有的 CTR 建模方法可以理解為 u2i 建模，通常刻畫用戶在特定請求上下文中對候選商品的偏好，而該團隊的建模方式是學習用戶的每個歷史點擊商品和候選商品的關係，可以理解為 u2i2i 的建模。這種建模方法更有助於學習多種 i2i 關係，並且輕鬆地將 i2i 圖中的一跳關係拓展到多跳關係。多種 i2i 關係可以探索更多無偏數據，進而增大商品候選集和訓練集，達到緩解選擇性偏差的目的。
同時，考慮到流行商品引起的流行度偏差，該團隊在構圖過程中對邊權引入流行度懲罰，使得多跳遊走時更有機會探索到低流行度的商品，同時在建模過程以及後處理過程中引入了流行度懲罰，緩解流行度偏差。
最終，該團隊形成了一個基於 i2i 建模的排序框架，框架圖如圖 4 所示。在此框架中商品推薦過程被分為三個階段，分別是：基於多跳遊走的 i2i 候選樣本生成、基於流行度偏差優化的 i2i 建模，以及用戶偏好排序。
圖 4：基於 i2i 建模的排序框架
1. 基於多跳遊走的 i2i 候選樣本生成
為了探索更多的 i2i 無偏候選樣本來進行 i2i 建模，從而緩解選擇性偏差，該團隊構建了一個具有多種邊關係的 i2i 圖，並在構邊過程中引入了流行度懲罰來消除流行度偏差。
如圖 5 所示，i2i 圖的構建與多跳遊走 i2i 候選樣本的生成過程被分為三個步驟：i2i 圖的構建、i2i 多跳遊走以及 i2i 候選樣本生成。
圖 5：基於多跳遊走的 i2i 候選樣本生成
i2i 圖的構建：i2i 圖中存在一種結點即商品結點，兩種邊關係即點擊共現邊和多模態向量邊。點擊共現邊基於用戶的歷史商品點擊序列而構建，邊的權重通過以下公式得到，其在兩個商品間的用戶歷史點擊共現頻數的基礎上，考慮了每次點擊共現的時間間隔因子，並加入了用戶活躍度懲罰以及商品流行度懲罰（用戶活躍度即用戶的歷史點擊次數，商品流行度即商品的被點擊次數），通過懲罰它們來緩解流行度偏差。
i2i 多跳遊走：該團隊通過枚舉不同的一跳 i2i 關係，組合構成不同類型的二跳 i2i 關係，並在構建好二跳 i2i 關係之後刪除原本的一跳 i2i 關係來避免冗餘，這樣就形成了圖 5 中的五種多跳 i2i 關係。多跳 i2i 關係得分由以下公式得來，即對每條路徑的邊權相乘得到路徑分，並對所有路徑分求平均。通過不同邊類型多跳遊走的方式，更多商品有更多的機會和其他商品構建多跳關係，從而擴大了商品候選集，緩解了選擇性偏差。
i2i 候選樣本生成：每種 i2i 關係根據 i2i 得分對所有商品的候選商品集合分別進行排序和截斷，每種 i2i 關係間的相似度熱圖如圖 6 所示。相似度是通過兩種 i2i 關係構造的候選集重複度計算得出，我們可以根據不同 i2i 關係之間的相似度來確定候選商品集合的數量截斷，以得到每種 i2i 關係中每個商品的 i2i 候選集，供後續 i2i 建模使用。
圖 6：i2i 關係相似度熱圖
2. 基於流行度偏差優化的 i2i 建模
該團隊通過 u2i2i 建模轉換，將傳統的基於 u2i 的 CTR 預估建模方式轉換為 i2i 建模方式。它可以輕鬆使用多跳 i2i 關係，同時該團隊引入帶流行度懲罰的損失函數，使 i2i 模型朝著緩解流行度偏差的方向學習。
如圖 7 所示，該團隊拆分用戶前置點擊行為序列，將每一個點擊的商品作為 source item，從 i2i graph 中的多跳遊走候選集中抽取 target item，形成 i2i 樣本集。對於 target item 集合，該團隊基於用戶下一次點擊的商品與 target item 是否一致來引入該樣本的標籤。這樣，就可以將基於用戶選擇的序列建模轉變為基於 i2i 的建模，通過兩個商品點擊的時間差以及點擊次數間隔，從側面引入用戶的序列信息，強調 i2i 的學習，從而達到消除選擇性偏差的目的。最終用戶的推薦商品排序列表可以基於用戶下的 i2i 打分進行 target item 排序。
圖 7：i2i 訓練樣本生成
如圖 8 所示，該團隊利用自動化特徵工程思想探索高階特徵組合，緩解了偏差問題業務含義抽象的問題。他們通過人工構造一些基礎特徵（如頻數特徵、圖特徵、行為特徵和時間相關特徵等），將基礎特徵類型劃分為 3 種：類別特徵、數值特徵以及時間特徵。然後，基於這些特徵做高階特徵組合，每一次組合形成的特徵都會加入下一次組合的迭代之中，以此降低高階組合的複雜度。該團隊基於特徵重要性和 NDCG@50_half 進行快速的特徵選擇，從而挖掘到更深層次的模式，同時節省了大量的人力成本。
圖 8：自動化特徵工程
在模型方面，他們嘗試了 LightGBM、Wide&Deep、時序模型等，最終由於 LightGBM 在 tabular 上的優異表現力，選擇了 LightGBM。在模型訓練中，該團隊使用商品流行度加權損失來消除流行度偏差，損失函數 L 參見下式。其中，參數 α 與流行度成反比，以削弱流行商品的權重，消除流行度偏差。參數 β 是正樣本權重，用來解決樣本不平衡問題。
3. 用戶偏好排序
最終，用戶的商品偏好排序是通過用戶的歷史點擊商品來引入 i2i，繼而對 i2i 引入的所有商品形成最終的排序問題。在排序過程中，根據圖 7 所示，target item 集合是由每一個 source item 分別產出的，所以不同的 source item 以及不同的多跳遊走 i2i 關係可能會產出相同的 target item。
因此，我們需要考慮如何將相同用戶的相同 target item 的模型打分值進行聚合。如果直接進行概率求和會加強流行度偏差，而直接取均值又容易忽略掉一些強信號。最終，該團隊對一個用戶多個相同的 target item 採用最大池化聚合方式，然後對用戶的所有 target item 進行排序，該方法在 NDCG@50_half 上取得了不錯的效果。
為了進一步優化 NDCG@50_half 指標，該團隊對所得到的 target item 打分進行後處理，通過提高低流行度商品的打分權重，來進一步打壓高流行度的商品，最終在 NDCG@50_half 上取得了更好的效果，這其實是 NDCG@50_full 與 NDCG@50_half 的權衡。
評估結果
在基於多跳遊走的 i2i 候選樣本生成過程中，各種 i2i 關係的 hitrate 如表 2 所示。可以發現，在相同長度為 1000 的截斷下對多種方法做混合會有更高的 hitrate 提升，能夠引入更多無偏數據來增大訓練集和候選集，從而緩解系統的選擇性偏差。
表 2：不同 i2i 關係的 hitrate
最終，由美團搜索廣告團隊組建的 Aister 在包括 NDCG 和 hitrate 的各項評價指標中都取得了第 1 名。如表 3 所示，NDCG@50_half 比第二名高出 6.0%，NDCG@50_full 比第二名高出 4.9%，NDCG@50_half 相較於 NDCG@50_full 有更明顯的優勢，這說明該團隊針對消除偏差問題做出了更好的優化。
表 3：不同參賽團隊解決方案的 NDCG 評估結果
AutoGraph 賽題
賽題介紹與問題分析
KDD Cup AutoGraph 賽題是有史以來第一個應用於圖結構數據的自動化機器學習（AutoML）挑戰，參與者需設計一個解決方案來自動化進行圖表示學習問題。
傳統做法一般利用啟發法從圖中提取每個結點的特徵，而近些年來，研究者提出了大量用於圖表示學習任務的複雜模型（如圖神經網絡），使許多下遊任務取得了最新成果。然而，這些方法需要投入大量的計算和專業知識資源，才能獲得令人滿意的任務性能。
而 AutoML 是一種降低機器學習應用人力成本的有效方法，在超參數調整、模型選擇、神經架構搜索和特徵工程方面取得了巨大成功。如何將 AutoML 應用於圖表示學習任務也是業界關注的熱點問題。
本次 AutoGraph 競賽針對自動化圖表示學習這一前沿領域，選擇了圖結點多分類任務來評估表示學習的質量。競賽官方準備了 15 個圖結構數據集，5 個供下載以便離線開發解決方案，5 個評估公共排行榜得分，5 個評估最終排名。這些數據集均從真實業務中收集，每個數據集提供了圖結點 id 和結點特徵、邊和邊權信息，以及數據集的時間預算。參賽者必須在給定的時間預算和算力內存限制下設計自動化圖學習解決方案。每個數據集會通過精度來評估準確性，最終排名基於 5 個測試數據集的平均排名。
Aister 團隊對五個離線圖數據集進行分析後，發現圖的類型多種多樣。如表 4 所示，從圖的平均度可以看出離線圖 3、4 較為稠密，而圖 1、2、5 較為稀疏；從特徵數量可以看出圖 5 無結點特徵，其餘圖有結點特徵；同時我們可以發現，圖 4 是有向圖，而其餘圖是無向圖。
從表 4 我們可以看出，大部分圖數據集的時間限制在 100 秒左右，這是一個很短的時間限制。大部分神經網絡架構和超參數搜索方案都需要較長的搜索時間，數十個小時甚至長達數天。因此，不同於神經網絡架構搜索，我們需要一個架構和超參數快速搜索的方案。
表 4：五個離線圖數據集的概況
如圖 9 所示，該團隊發現在圖數據集 5 上存在模型訓練不穩定的問題，模型在某個 epoch 上驗證集精度顯著下降。該團隊認為這主要是因為圖數據集 5 易於學習，會發生過擬合現象，因此在自動化建模過程中需要保證模型的強魯棒性。
圖 9：模型在訓練過程中的不穩定性
同時，從圖 10 可以發現，保證每個數據集排名的穩定性相比於優化某個數據集的精度更為重要。例如數據集 5 模型精度差異僅為 0.15% 卻導致了十個名次的差異，數據集 3 模型精度差異有 1.6% 卻僅導致 7 個名次的差異。因此，該團隊需要採用排名魯棒的建模方式，來增強數據集排名的穩定性。
圖 10：不同選手在不同數據集上的精度及排名
基於以上數據分析，該賽題存在以下三個挑戰：
圖數據的多樣性：解決方案要在多個不同的圖結構數據上均達到優秀效果。圖的類型多種多樣，包含了有向圖 / 無向圖、稠密圖 / 稀疏圖、帶特徵圖 / 無特徵圖等。
超短時間預算：大部分數據集的時間限制在 100 秒左右，在圖結構和參數搜索方面需要有一個快速搜索方案。
魯棒性：在 AutoML 領域，魯棒性是非常重要的因素。最後一次提交要求選手在之前沒見過的數據集上進行自動化建模。
冠軍解決方案
針對以上三個挑戰，aister 團隊設計了一個自動化圖學習框架，如圖 11 所示，該框架對輸入的圖進行預處理和圖特徵構建。
圖 11：自動化圖學習框架
aister 團隊使用了多種具有不同特點的圖神經網絡，採用圖神經網絡結構和超參數快速搜索方法，還設計了一個多級魯棒性模型融合策略，來分別克服上述三項挑戰。最終，該團隊的自動化圖學習解決方案在較短的時間內對多個不同圖結構數據進行結點分類，並達到魯棒性效果。接下來，我們將詳細介紹整個解決方案。
1. 圖神經網絡模型
為了克服圖的多樣性挑戰，該團隊結合譜域及空域兩類圖神經網絡方法，採用 GCN、TAGConv、GraphSAGE、GAT 四個圖神經網絡模型對多種不同圖結構數據進行更好地表示學習，每個模型針對不同類型的圖結構數據具備各自的優勢。
圖作為一種非歐式空間結構數據，其鄰居結點個數可變且無序，因此直接設計卷積核是困難的。譜域方法通過圖拉普拉斯矩陣的譜分解，在圖上進行傅立葉變換得到圖卷積函數。GCN 作為譜域的經典方法，公式如下所示：
其中 D 是對角矩陣，每個對角元素為對應結點的度，A 是圖的鄰接矩陣，其通過給每個結點加入自環使卷積函數獲取自身結點信息，並在傅立葉變換之後使用切比雪夫一階展開近似譜卷積，使每一個卷積層僅處理一階鄰域信息，通過堆疊多個卷積層達到多階鄰域信息傳播。
由於依賴拉普拉斯矩陣，GCN 等譜域方法並不能很好地處理有向圖，有向圖無法直接定義拉普利矩陣及其譜分解，因此該團隊將有向圖的邊進行反轉改為無向圖。GCN 方法簡單且有效，該團隊將 GCN 應用到所有數據集上，大部分數據集能取得較好的效果。
相較於堆疊多層獲取多階鄰域信息的 GCN 方法，TAGConv 通過鄰接矩陣的多項式拓撲連接來獲取多階鄰域信息，公式如下所示：
可以發現，其通過預先計算鄰接矩陣的 k 次冪，在訓練過程中實現多階鄰域卷積並行計算，且高階鄰域的結果不受低階鄰域結果的影響，從而加快模型在高階鄰域中的學習。就實驗結果來看，其在稀疏圖上能快速收斂，相比於 GCN 能夠達到更好的效果。
相較於利用傅立葉變換來設計卷積核參數的譜域方法，空域方法的核心在於直接聚合鄰居結點的信息，難點在於如何設計帶參數、可學習的卷積核。GraphSAGE 提出了經典的空域學習框架，通過圖採樣與聚合來引入帶參數可學習的卷積核，其核心思想是對每個結點採樣固定數量的鄰居，這樣就可以支持各種聚合函數。均值聚合函數的公式如下所示，其中的聚合函數可以替換為帶參數的 LSTM 等神經網絡：
由於 GraphSAGE 帶有鄰居採樣算子，因此 Aister 團隊引入該圖神經網絡來極大地加速稠密圖的計算。就實驗結果而言，其在稠密圖上的運行時間遠小於其他圖神經網絡，並且由於採樣能一定程度上避免過擬合，因此它在有些稠密圖上能夠達到較好的效果。
GAT 方法將 Attention 機制引入圖神經網絡，公式如下所示：
其通過圖結點特徵間的 Attention 計算每個結點與其鄰居結點的權重，通過權重對結點及其鄰居結點進行聚合作為結點的下一層表示。
通過 Masked Attention 機制，GAT 能處理可變個數的鄰居結點，並且其使用圖結點及其鄰居結點的特徵來學習鄰居聚合的權重，有效利用結點的特徵信息進行圖卷積，泛化效果更強，它參考了 Transformer 引入 Multi-head Attention 的做法來提高模型的擬合能力。GAT 利用結點特徵來計算結點與鄰居結點間的權重，因此在帶有結點特徵的數據集上表現優異，但如果特徵維度多就會使得 GAT 計算緩慢，甚至出現內存溢出的現象。這就需要在特徵維度多的情況下對 GAT 的參數進行搜索限制，要求其在一個參數量更小的空間下搜索。
2. 超參快速搜索
由於超短時間預算的挑戰，該團隊需要設計一個超參快速搜索方法，來保證花較少的時間就可以對每個圖模型進行參數搜索，並且在每個數據集上儘可能地使用更多的圖模型進行訓練和預測。如圖 12 所示，該團隊將參數搜索分為線下搜索和線上搜索兩部分。
圖 12：超參快速搜索
該團隊在線下搜索時，針對每一個圖模型在多個數據集上使用一個大的搜索空間去確定圖結構和參數邊界，保證每個數據集在這個邊界中都有較好的效果。
具體而言，他們基於有向圖 / 無向圖、稀疏圖 / 稠密圖、帶特徵圖 / 無特徵圖等不同圖類型對不同模型的大多數參數進行了搜索，確定了幾個重要的超參數，例如對於稀疏圖，調整 TAGConv 多項式的階數，可使其卷積感受野更大，迅速對數據集進行擬合。該團隊在線下主要確定了不同圖模型學習率、卷積層數、隱層神經元個數這三個重要參數的邊界。
由於線上的時間預算限制，該團隊基於線下的參數邊界
確定了一個小的參數搜索子空間，以便執行線上搜索。由於時間預算相對較少，沒有充足的時間在參數上做完整的訓練驗證搜索，因此該團隊設計了一個快速參數搜索方法。
對於每個模型的超參空間，通過少量 epoch 的訓練來比較驗證集精度，從而確定超參數。如圖 13 所示，該團隊通過 16 輪的模型訓練，來選取驗證集精度最優的學習率 0.003，此舉意在確定哪些超參數可使模型快速擬合該數據集而不追求選擇最優的超參數，以加快參數搜索和模型訓練。
圖 13：少量 epoch 模型訓練下不同學習率的驗證集精度
通過快速超參搜索，該團隊保證每個模型在每個數據集上均能在較短時間內確定超參數，從而利用這些超參數進行每個模型的訓練。
3. 多級魯棒模型融合
由於該次競賽通過數據集排名平均來確定最終排名，故而魯棒性是特別重要的。為了達到魯棒效果，該團隊採用了一個多級魯棒模型融合策略。
如圖 14 所示，在數據層面進行切分來進行多組模型訓練，每組模型包含訓練集及驗證集，通過驗證集精度使用 Early Stopping 來保證每個模型的魯棒效果。每組模型包括多種不同的圖模型，每種圖模型訓練 n 次進行均值融合得到穩定效果。由於不同種類圖模型的驗證精度差異較大，因此需要對不同種類的圖模型根據圖的稀疏性以及驗證集精度進行稠密度自適應帶權融合，以便利用不同模型在不同數據集上的差異性，最後再對每組圖模型進行均值融合來利用數據間的差異性。
圖 14：多級魯棒模型融合
評估結果
表 5 展示了不同圖模型在五個離線圖數據集上的測試精度：與「圖神經網絡模型」章節所描述的一致，GCN 在各個圖數據集上有較好的效果，而 TAGConv 在稀疏圖數據集 1、2、5 有更優異的效果，GraphSAGE 在稠密圖數據集 4 上取得最好的效果，GAT 在有特徵的數據集 1、2、4 中表現較為良好，而模型融合在每個數據集上均取得更穩定且更好的效果。
表 5：不同圖模型在五個離線圖數據集上的測試精度
如表 6 所示，該團隊的解決方案在每個圖數據集上均達到魯棒性效果，每個數據集的排行均保持較領先的水平，並避免過度擬合，從而在平均排行上取得第一，最終 aister 團隊在 KDD Cup 2020 AutoGraph 賽題上獲得冠軍。
表 6：Top 5 參賽隊伍在最後 5 個數據集上所有圖數據集的平均排行及在每個圖數據集的單獨排行
Multimodalities Recall 賽題
賽題介紹與分析
多模態召回賽題由阿里巴巴達摩院智能計算實驗室發起並組織，關注電商行業中的多模信息學習問題。
2019 年，全世界線上電商營收額達到 3530 億美元。據相關預測，到 2022 年，總營收將增長至 6540 億美元。大規模的營收和高速增長預示著，消費者對於電商服務有著巨大需求。跟隨這一增長，電商行業中各種模態的信息越來越豐富，如直播、博客等等。怎樣在傳統的搜尋引擎和推薦系統引入這些多模信息，更好地服務消費者？這值得相關從業者深入探討。基於此背景，主辦方發起了該賽題。
主辦方提供了淘寶商城的真實數據，包括兩部分：一是搜索短句（query）相關，為原始數據；二是商品圖片相關，考慮到智慧財產權等，提供的是使用 faster rcnn 基於圖片提取出的特徵向量。兩部分數據被組織為基於 query 的圖片召回問題，即有關文本模態和圖片模態的召回問題。
為方便理解，主辦方提供了少量真實圖片及其對應的原始數據，如圖 15 所示。該圖例是一個正樣例，其 query 為 sweet french dress；圖片主體部分是一名身著甜美裙裝的女性，主體部分以外，則有大量雜亂信息，包括一個手提包、一些氣球以及一些商標和促銷文字信息。賽題本身不提供原始圖片，提供的是 faster rcnn 基於圖片提取出的特徵向量，即圖片中被框出的幾個部分。可見，一方面 faster rcnn 提取了圖片中有明顯語義的內容，有助於模型學習；另一方面，faster rcnn 的提取會包含較多的框，這些框體現不出主次之分；此外，faster rcnn 也並非完美無缺，因而多模態召回問題還有賴進一步地挖掘。
圖 15：搜索短語與圖片的匹配示例
本次賽題設置的評價指標為 NDCG@5，計算邏輯如下：在給定的測試集裡，每條 query 會給出約 30 個樣本，其中大約 6 條為正樣本，其餘為負樣本；賽題需要選手設計匹配算法，召回出任意 5 條正樣本，即可獲得該 query 的全部分數，否則，按照召回的正樣本條數來計算 NDCG 指標作為該 query 的分數。全部 query 的分數進行平均，即為最終得分。
主辦方提供了三份數據集，分別是訓練集、驗證集和測試集。各個數據集的基本信息如表 7 所示。
表 7：數據集概況
為進一步探索數據特徵，該團隊將驗證集給出的原始圖片和特徵信息做了聚合展現，表 8 是一組示例。
表 8：搜索短語與圖片的匹配正負例
根據如上基本信息，該團隊總結了數據集的三個重要特點：
訓練集和驗證集 / 測試集的數據特點大不相同。訓練集量級顯著高於驗證集 / 測試集，足有三百萬條 query-image 對，是驗證集 / 測試集的一百倍以上。同時，訓練集的每條 query-image 對均被視為正樣本，這和驗證集給出的一條 query 下掛多個有正有負的 image 截然不同。而通過對驗證集原始圖片和 query 進行可視化探索，可以發現驗證集數據質量很高，應該為人工標註。考慮人工標註成本和負樣本的缺失，訓練集極大可能描述的是點擊關係，而非人工標準的語義匹配關係。該團隊的解決方案必須考慮「訓練集和測試集並不匹配」這一基本特點。
圖片信息複雜，常常包含多個物體。這些物體均被框出作為給定特徵，但各個框之間的語義信息並不平等；某些是噪音，如 query (men's high collar sweater) 下的墨鏡、圍巾、相機等框圖，某些又因商品展示需要而重複，如 query (breathable and comfortable children's shoes) 下重複鞋的框圖。平均來說，一張圖片有 4 個框，怎麼將多個框包含的語義信息去噪、綜合，得到圖片的語義，是建模的重點。
query 作為給定的原始文本，有著與常用語料截然不同的構造和分布情況。從示例表可見，query 並非自然語句，而是一些屬性和商品實體連綴成的短語。經過統計發現，90% 的 query 由 3-4 個單詞組成；訓練集有約 150 萬不同的 query，其詞表大小在 15000 左右；通過最後一個單詞，可將全部 query 歸約為大約 2000 類，每一類是一個具體的商品名詞。我們需要考慮文本數據的這些特質，進行針對性處理。
從上述數據集的三個特點出發，該團隊總結了此競賽的兩大主要挑戰。
分布不一致問題：經典統計機器學習的基礎假設是訓練集和測試集分布一致，不一致的分布通常會導致模型學偏，訓練集和驗證集效果難以對齊。我們必須依賴已有大規模訓練集中的點擊信號和和測試集同分布的小規模驗證集，設計可行的數據構建方法和模型訓練流程，採取諸如遷移學習等技術，來處理這一問題。
複雜多模信息匹配問題：怎麼進行多模信息融合是多模態學習中的基礎性問題，而怎麼對複雜的多模信息進行語義匹配，是本競賽特有的挑戰。從數據看，一方面商品圖片多框，信息含量大、噪點多；另一方面用戶搜索 query 一般具有多個細粒度屬性詞，且各個詞均在語義匹配中發揮作用。這就要求我們在模型設計上針對性地處理圖和 query 兩方面的複雜性，並做好細粒度匹配。
競賽技術方案
該團隊的方案直接回應了上述兩項挑戰，其主體部分包含兩方面內容：一是通過聯合多樣化的負採樣策略和蒸餾學習來橋接訓練數據和測試集的分布，處理分布不一致問題；二是採取細粒度的文本 - 圖片匹配網絡，進行多模信息融合，處理複雜多模信息匹配問題。最後，通過兩階段訓練和多模融合，進一步提升模型表現。
整個方案的流程如圖 16 所示：
圖 16：基於多樣化負採樣的多階段蒸餾學習框架
下面我們來看該方案的各個部分。
1. 多樣化負採樣策略和預訓練
訓練集和測試集分布不一致。最直觀的不一致是，訓練集中只有正樣本，沒有負樣本，因此需要設計負採樣策略來構造負樣本，並儘可能使得採樣的樣本靠近測試集的真實分布。
最直觀的想法是隨機採樣。隨機採樣簡單易行，但和驗證集區別較大。分析驗證集發現，同一 query 下的候選圖片通常有著緊密的語義關聯。如「甜美法式長裙」這一 query 下，待選的圖片全是裙裝，只是在款式上有所不同。這說明，這一多模匹配賽題需要在較細的屬性粒度上對文本和圖片進行匹配。從圖片標籤和 query 詞兩個角度出發，我們可以通過相應的聚類算法，使得待採樣的空間從全局細化為相似語義條目，從而達到負採樣更貼近測試集分布的目的。
基於如上分析，該團隊設計了如表 9 所示的四種採樣策略來構建樣本集。這四種策略中，隨機採樣得到的正負樣本最容易區分，按 query 最後一詞採樣得到的正負樣本最難區分；在訓練中，該團隊從基準模型出發，先在最簡單的隨機採樣上訓練基準模型，然後在更困難的按圖片標籤採樣、按 query 的聚類採樣上基於先前的模型繼續訓練，最後在最難的按 query 最後一詞採樣的樣本上訓練。這樣由易到難、由遠到近的訓練方式，有助於模型收斂到驗證集分布上，在測試集上取得更好的效果。
表 9：多樣化負採樣
2. 蒸餾學習
儘管使用多種採樣策略，可從不同角度逼近測試集的真實分布，但由於未直接利用測試集信息指導負採樣，因此該方法仍存在不足。
於是，該團隊採用蒸餾學習的辦法，來進一步優化負採樣邏輯，以便獲取更貼近測試集的 label 分布。如圖 17 所示，在通過訓練集負採樣得到的樣本集上預訓練以後（第 1 步）；將該模型在驗證集上進一步 finetune，得到微調模型（第 2 步）；利用微調模型，反過去在訓練集上打偽標籤，作為 soft label，並把 soft label 引入 loss，和原始的 0-1 hard label 聯合學習（第 3 步）。這樣，在訓練集的訓練上，直接引入了驗證集的分布信息，進一步貼近了驗證集分布，提升了預訓練模型的表現。
圖 17：多階段蒸餾學習
3. 細粒度匹配網絡
多模態學習方興未艾，各類任務、模型層出不窮。針對此次競賽面臨的複雜圖片和搜索 query 匹配的問題，參照 CVPR 2017 VQA 競賽的冠軍方案，該團隊設計了圖 18 所示的神經網絡模型作為主模型。
圖 18：細粒度匹配網絡
該模型的設計主要考慮以下三點：
利用帶門全連接網絡做語義映射。圖片和 query 處於不同的語義層級，需利用函數映射到相同的語義空間，該團隊採取兩個全連接層的方式達到該目的。實驗發現，全連接層的隱層大小是比較敏感的參數，適當增大隱層，可在不過分增加計算複雜度的情況下，顯著提升模型效果。此外，如文獻所述，使用帶門的全連接層可進一步提升語義映射網絡的效果。
採用雙向 attention 機制。圖片和 query 均由更細粒度的子語義單元組成。具體來說，一張圖片上可能有多個框，每個框均有獨立的語義信息；一個 query 分為多個詞，每個詞也蘊含獨立的語義信息。這一數據特點是由電商搜索場景決定的。因而，在模型設計時，需考慮到單個子語義單元之間的匹配。該團隊採用單個詞和全部框、單個框和全部詞雙方向的注意力機制，去捕捉這些子單元的匹配關係和重要程度。
使用多樣化多模融合策略。多模信息融合有很多手段，大部分最終歸結為圖片向量和 query 向量之間的數學操作符。考慮到不同融合方式各有特點，多樣融合能夠更全面地刻畫匹配關係，因此該團隊採用了 Kronecker Product、Vector concatenation 和 self-attention 三種融合方式，將經過語義空間轉化和 attention 機制映射後的圖片向量和 query 向量進行信息融合，並最終送入全連接神經網絡，最終得到匹配與否的概率值。
多模融合
在上述技術手段的處理下，可以得到多個基礎模型。這些模型均可在驗證集上進行 finetune，從而使其效果更貼近真實分布。一方面，finetune 階段可繼續使用前述的神經網絡匹配模型。另一方面，前述神經網絡可作為特徵提取器，將其在規模較小的驗證集上的輸出，放入樹模型重新訓練。這一好處是樹模型和神經網絡模型異質性大，融合效果更好。最終，該團隊提交的結果是多個神經網絡模型和樹模型融合的結果。
評估結果
以隨機採樣訓練的粗粒度（圖片表示為所有框的平均，query 表示為所有詞的平均）匹配網絡為基準模型，表 10 列出了該團隊解決方案各個部分對基準模型的提升效果。
表 10：不同方法的 NDCG 提升
總結
KDD Cup 競賽與工業界聯接十分緊密，每年的賽題緊扣業界熱點問題與實際問題，歷年的 Winning Solution 對工業界也有很大的影響。例如，KDD Cup 2012 獲勝方案產出了 FFM (Feild-aware Factorization Machine) 與 XGBoost 的原型，在工業界取得廣泛應用。
今年 KDD Cup 的幾大賽題也是當前廣告與推薦領域中最具挑戰性的問題，本文介紹了美團搜索廣告團隊在 KDD Cup 2020 Debiasing、AutoGraph、Multimodalities Recall 三個賽題上取得兩冠一季的解決方案。
Debiasing 賽題解決方案從消除推薦數據偏差的目的出發，進行 i2i 多跳遊走、i2i 建模以及 u2i 排序，克服了選擇性偏差和流行度偏差兩個賽題挑戰。
AutoGraph 賽題解決方案將 AutoML 應用於自動化圖表示學習中，通過搭建多種圖神經網絡，並採用快速參數搜索方法以及多級魯棒模型融合策略，來克服圖數據的多樣性、超短時間預算以及魯棒性等三個賽題挑戰。
Multimodalities Recall 賽題解決方案通過多樣化負採樣策略和預訓練、蒸餾學習等方法，搭建細粒度匹配網絡並採用多模型融合等方法來克服分布不一致問題以及複雜多模信息匹配問題等兩個賽題挑戰。
這些解決方案多數從數據分析出發來定位賽題難點，找尋賽題突破口，從而設計賽題解決方案來克服賽題挑戰。同樣地，這種解決問題的思路也有助於美團到店廣告團隊在廣告領域上做進一步的探索。
aister 團隊簡介
黃堅強，美團廣告平臺搜索廣告算法團隊算法工程師，畢業於北京大學。
胡可，美團廣告平臺搜索廣告算法團隊資深算法專家，畢業於香港中文大學。
陳明健，美團廣告平臺搜索廣告算法團隊算法工程師，畢業於北京大學。
漆毅，美團廣告平臺搜索廣告算法團隊算法工程師，畢業於清華大學。
唐興元，畢業於中國科學院大學。
曲檀，美團廣告平臺搜索廣告算法團隊算法工程師，畢業於中國人民大學。
雷軍，美團廣告平臺搜索廣告算法團隊研究員，畢業於清華大學。