【演算法比賽】NFL Big Data Bowl 數據挖掘比賽回顧

• 2020 年 4 月 3 日
• 筆記

本文原作者：孫雨豪，經授權後發布。

導語

NFL Big Data Bowl是Kaggle上的一個數據比賽，本文旨在通過回顧比賽，梳理和學習其中的建模思路（點數據挖掘、圖挖掘）、數據處理技巧（對抗驗證、數據增強）、模型集成技巧（Snapshot Ensembles）。

一.背景

筆者之前與隊友derkechao參加了Kaggle舉辦的NFL Big Data Bowl比賽並有幸躋身金牌區，本文旨在對比賽進行回顧總結以及學習其他參賽者的建模經驗。

1. NFL(National Football League)

職業橄欖球大聯盟（National Football League）簡稱NFL，居北美四大職業體育運動聯盟之首，也是世界上規模最大的職業橄欖球大聯盟

2. 美式橄欖球規則

美式橄欖球由相互競爭的兩隊各11人進行對抗，拿到控球權的一方是進攻方，目標是儘可能將球向對方陣地推進，爭取越過得分線進入對方端區得分。進攻的方法有兩種，持球球員(Rusher)帶球向前跑陣（沖球，rushing）或將球向前拋傳（傳球，passing）。防守方的目的則是儘可能阻止對方進攻得分，並迫使其喪失控球權。如果進攻一方得分成功或喪失控球權，雙方隊伍互換攻防，比賽就這樣輪流攻防的進行下去，直到四節比賽時間結束。

3. 預測沖球（rushing）結果

本次比賽的目的是通過持球瞬間的數據，預測該次沖球獲得的碼數（跑的距離）。預測結果為沖球不同距離的概率分布，即-99碼~99碼這199個距離分段下每個分段的概率，最終以Continuous Ranked Probability Score (CRPS)對預測結果進行評價，指標值越低效果越好。

可獲取的資訊包括隊員資訊、比賽資訊、環境資訊，詳細欄位可以參考（https://www.kaggle.com/c/nfl-big-data-bowl-2020/data）。根據前期的EDA（https://www.kaggle.com/jaseziv83/comprehensive-cleaning-and-eda-of-all-variables）我們可以發現沖球結果主要與隊員資訊相關（包括隊員畫像特徵、比賽站位、瞬時速度和加速度等），因而之後的建模中也主要考慮使用隊員的資訊進行建模。

二.建模

1. 數據預處理

1.1 緩解空間數據稀疏性-特徵相對化

由於原始的空間數據存在稀疏的性質（某人恰好在某個位置的概率很小），我們通常會使用相對位置、速度替代絕對位置、速度作為特徵，減小數據稀疏性帶來的難學習問題。在NFL比賽中我們將所有球員的位置、速度特徵都取持球球員的相對值。

1.2 特徵選擇-對抗驗證（Adversarial Validation）

特徵選擇相信大家都非常熟悉，不管是通過KS、AUC等指標篩選特徵還是利用樹模型篩選特徵，其實都是對特徵區分度進行測試。然而有時我們會發現某個特徵區分度很高但放在模型中卻讓結果變差了，這時我們可以通過對抗驗證的方法對特徵在訓練數據和驗證數據中的分布一致性進行檢測。具體的，通過將訓練數據標為1，驗證數據標為0並利用xgboost或lgbm建立二分類模型，通過模型AUC和特徵重要性我們可以發現某些特徵能準確區分訓練集和測試集，而這些特徵往往會對模型產生不好的影響，通常我們會進行處理或直接丟棄。

在NFL比賽中通過對抗驗證我們可以發現角度特徵在17年和18年的比賽中分布不一致，進一步分析可以發現兩年的0度方向不一致，若直接建模會導致結果較差。通過對該特徵進行旋轉修正可以獲得較大的分數提升。

從上圖可以看出2017年數據分布和2018-2019年數據分布不同，需要對特徵進行修正

1.3 數據增強-坐標翻轉

在機器學習任務中，當樣本量較小時，可能導致訓練數據分布與真實數據分布差別較大，從而導致學出來的模型無可避免地存在一定偏差。針對這種情況，我們一般可以採用遷移學習或者數據增強的方法來緩解問題，而在這個任務中由於沒有外部數據我們只能通過數據增強來緩解訓練數據存在偏差的問題。在影像類任務中我們可以採用平移、旋轉、翻轉、縮放、裁剪等操作，對於數值類任務可以用SMOTE等插值演算法進行數據增強，而位置類數據增強方法則和影像類似。這個任務中由於我們使用的特徵是相對於持球球員的，等價於進行平移增強，除此之外我們發現比賽在y軸方向存在對稱性，因而可以通過翻轉的方式進行增強。

2. 模型選擇分析

2.1 表格數據比賽常用技術方案

目前kaggle社區中針對於表格數據最熱門的模型莫過於梯度提升樹模型（xgboost,lgbm,catboost等），梯度提升樹模型的優勢在於不需要像nn一樣對模型結構和超參進行大量調試，同時計算速度也相對較快。相對的，樹模型對於前期特徵工程品質特別敏感，特徵處理的不同會對最終結果造成非常大的影響。表格數據類比賽常用的方法就是：使用樹模型做主模型並在其基礎上進行特徵工程，之後使用特徵這些特徵（可能有微調）用NN、SVM、KNN建模，由於這些模型結構原理差異較大，學出來的結果偏差不同，通過集成（Blending或Stacking）能一定程度上減小結果方差，從而提升最終效果。

2.2 NFL比賽相對於其他表格數據比賽的區別

（1）需要刻畫多個對象之間的關係

在對多個對象建模時，不僅需要對對象本身的屬性進行刻畫，還需要對對象之間的關係進行刻畫。當研究對象數量較少時，採用手工提取特徵的方式通常可以滿足需求，如針對兩個對象我們常常使用pairwise的模型進行建模。然而針對有22個隊員的任務來說，手工提取特徵變得十分困難，效果也難以保證。

相比於每個隊員本身的特徵，隊員之間的站位配合等因素對最終結果影響更大

（2）樣本缺失和結果平滑

由於xgboost和lgbm多分類任務需要每個類別都有樣本數據，而NFL比賽的訓練數據中缺少某些類別的樣本，故不能直接使用199分類模型，需要進行結果聚合（把199分類合併成20分類）或扔掉缺失類別，這導致了模型輸出結果不夠平滑，在crps指標上效果不太好。此外，如果將問題轉化成回歸問題，則會導致預測的概率密度集中在一個點上，也無法很好地適應crps指標。

（3）時間有限

由於整個模型訓練和預測需要在kaggle提供的服務上運行，且規定整體耗時不超過4小時。模型複雜度受到了一定限制，且無法進行太多模型的集成。因而效果好的單模型成了比賽制勝的關鍵。

結論：相對於梯度提升樹模型，nn模型在複雜關係建模和輸出結果連續性上更具有優勢。

3. 建模思路分析

3.1 拋磚引玉：MLP+Attention

整個比賽可以看作是1個持球球員(Rusher)和10個隊友突破敵方11個防守隊員的遊戲，一個基本思路是通過對這三部分資訊分別表徵，然後融合建模得到最終結果。一開始我們想到的方法是對於持球隊伍和敵方隊伍，分別使用不同的Dense層作為編碼器對每個球員的特徵進行Embedding,由於我們需要保證球員之間的無序性（在輸入層的順序不影響最終結果）所以需要在上層對每個隊伍球員的特徵進行聚合，而最通用的辦法就是Embedding求和得到隊伍的Embedding，之後再將兩個隊伍的Embedding拼接後通過Dense層+Softmax得到最終結果，網路結構如下圖所示。

然而這樣的結構在實驗的時候結果始終不夠理想，其中很大一個原因就是從球員Embedding生成球隊Embedding這步建模太過簡單，僅僅將所有隊員加和無法突出某些處在關鍵位置的球員對局勢的影響，為了解決這個問題筆者引入了Attention機制來建模每個球員的重要性，網路結構如下。

首先我們依舊通過Dense層對每個球員的特徵進行編碼，之後利用一個Attention層求取每個球員的重要性，再按照重要性對球員加權求和得到隊伍的Embedding。通過引入Attention機制筆者的隊伍排名最終前進了5名。

該模型的優點：

1. 結構簡單，計算速度快

2. 對持球球員、隊友、對方分別表徵，特徵選擇比較靈活

該模型的缺點：

1. 只是對整個球隊進行表徵，缺乏對球員之間關係的描述

2. 模型結構簡單，學習能力有限

3.2 增加模型複雜度：引入Transformer多頭注意力

由於MLP+Attention的模型存在結構過於簡單，且計算Attention Weight的時候缺乏對手的資訊，導致整個模型存在一定的資訊損失，而最近在NLP領域大火的Transformer則恰好能解決這個問題。

transformer的多頭注意力機制能學習更加複雜的對象間關係

Transformer的多頭注意力機制能從不同角度對每個對象的重要性進行評價，從而能更好的學習輸入對象中存在的各種關係並對其進行表徵。與LSTM等RNN單元不同的是，Transformer一次性讀取一整句話的內容並通過position embedding對詞的位置進行標定，而對於本次比賽任務來說，由於隊員間並沒有明確的排序，所以我們在使用Transformer的時候只要捨棄position embedding就能將其作為一個無順序的帶注意力機制的編碼器。整體網路結構示意圖如下。

模型採用了2層Encoder+2層Decoder的結構。Encoder的輸入為22個隊員（類比於22個詞）的特徵（類比於22個詞向量）輸入除了沒有position embedding之外和NLP任務一致。而Decoder側稍有不同，在NLP任務中Query使用的是前一個位置Decoder的輸出，而NFL比賽中使用的是rusher的feature作為Query，一方面是增強了對rusher資訊的關注，另一方面捨棄了順序資訊，保證只輸出一個向量。

該模型的優點：

 大量注意力機制使模型學習能力強

該模型的缺點：

仍然缺乏對球員之間關係的描述

3.3 問題的關鍵還是關係：用CNN進行圖建模

橄欖球比賽的本質是球員之間的合作和競爭，缺少了對關係的建模必然無法實現準確的預測，而一說到關係我們很容易想到通過圖模型對問題進行建模。而相對於其他圖挖掘任務來說，由於比賽的人數固定，球員之間關係網路的拓撲結構也就固定，因而我們可以直接通過cnn對關係進行建模。

回到MLP+Attention模型，我們仍然將球員分為持球球員、隊友、對手三部分，但現在我們不急著將這三部分資訊進行表徵，而是思考這三者的關係，持球球員仍是我們關注的核心，而隊友和對手，其實本質上是持球球員的Ego Network里的兩類節點，而對球員關係建模其實就是對這兩類節點形成的二部圖進行建模。

從圖的視角來看，其實就是對以持球球員為中心的隊友-對手二部圖進行建模

本次比賽第一名的隊伍使用了CNN對這個二部圖進行建模，CNN的每個channel為隊友和對手的鄰接矩陣，矩陣中每個元素為對應隊友-隊友Pair對的特徵，每個channel對應不同特徵。模型結構如下圖所示。

註：def指對手（denfense），off指進攻隊友（offense），rusher指持球球員，Sxy指速度的xy分量，X，Y為球員位置

輸入數據為（11x10x10）的Tensor（11個對手，10個隊友，10個特徵，每個channel可以看作是11個對手和10個隊友的鄰接矩陣），模型中使用了1×1卷積+Relu對每個隊友-對手Pair的10個特徵進行非線性變換，然後進行池化（保留對手維度），接著又進行了一維卷積和相對應的池化操作，最後通過Dense+Softmax層得到結果。

可以看出整個模型的特徵和結構都非常簡單，而與前面的模型唯一不同的是該模型對球員之間的關係進行了顯示的建模，而比賽結果也體現了其效果的顯著性，該模型當之無愧地獲得了比賽的第一名。

3.4 一個模型也能集成：Snapshot Ensembles解決多模型集成耗時問題

由於NFL比賽限定了訓練+預測整體耗時不能超過4小時，因而多個模型學習+集成的思路是不可行的，而Snapshot Ensembles則通過「一次訓練，多快照集成」的方式達到了集成的目的。Snapshot Ensembles通過在訓練過程中周期性地增大或減少學習率讓模型重複越過局部最優和接近局部最優的過程，實現每個快照擅長處理不同數據的目的。Snapshot Ensembles中的每個模型快照都不如通常恆定或遞減學習率學習出來的模型，但是多個快照集成之後卻能讓模型整體獲得提升，從而獲得更好的預測效果。

每個插旗的地方為一個snapshot

三.總結

從本次比賽中總結的經驗和教訓：

1. 建模時首先思考研究對象之間的關係是否是建模關鍵

最近幾年圖數據挖掘技術突飛猛進，對圖、關係的挖掘和建模得到了很大的發展。關係在現實生活中無處不在，如何理解數據中存在的關係將是建立一個「好」模型的關鍵。對於一個建模任務，首先要思考建模對象之間是否存在很強的關聯性，如果存在則需要從圖挖掘的角度進行切入。

2. 不僅要知道一個模型/演算法一般怎麼用，還要舉一反三了解其潛在的作用

我們都知道transformer在NLP任務中得到了廣泛的應用，但其本質其實還是一個基於注意力機制的編解碼器，如果了解到這一點則可以在很多其他類型任務中發揮其作用。在學習一個模型/演算法時，不僅要了解其一般怎麼用，還要從其本質分析其還能在哪些場景發揮作用，只有通過舉一反三我們才能使用有限的演算法更好的對數據進行建模。

3. 數據挖掘的根本問題還是在於對數據的理解

如果對圖數據不熟，則怎麼也會想到從關係的角度對橄欖球比賽進行建模。不同數據有不同的處理方法，掌握方法需要不斷積累，但同時也需要我們總結和抽象。一方面我們需要對不同類型的數據廣泛涉獵，保證在挖掘建模時思路不會僵硬，另一方面對於一類數據，我們不僅要掌握相關模型，也需要對 數據採集-數據處理-挖掘建模-上層應用 整個鏈路進行深入理解。

四.參考鏈接

對抗驗證介紹 ：https://www.kaggle.com/kevinbonnes/adversarial-validation

Transformer原理介紹：http://jalammar.github.io/illustrated-transformer/

數據增強介紹：https://zhuanlan.zhihu.com/p/41679153

Snapshot Ensembles介紹：https://zhuanlan.zhihu.com/p/62647769

另外分享一個介紹ensemble的好文：https://mlwave.com/kaggle-ensembling-guide/