我的Kaggle初體驗 -- Grupo Bimbo Inventory Demand

雖說自己是Kaggle新手，但是我自己已經有三年多機器學習經驗啦，做過演算法也做過應用，對大部分常用模型都有一定的了解。但是關於怎樣在Kaggle中獲得好成績，在比賽開始的時候我還什麼都不知道，所以前兩個星期各種做無用功。

這個比賽的目的是預測 Grupo Bimbo Inventory Demand：Grupo Bimbo公司服務於墨西哥幾乎所有的零售商，給他們提供食物和飲料產品；每個零售商每周進貨和退貨的數據，在Grupo Bimbo的資料庫都有記錄；這個進貨和退貨的過程很大程度上都伴隨的成本（包括運輸成本，損耗成本等）；這次比賽提供了整個墨西哥7周（標籤為3-11周）的數據，前5周（3-9周）有數據的demand label作為訓練集合，後2周（10，11）沒有label作為test集；這兩周中前一周（第10周）作為public leaderboard，後一周（第11周）作為private leaderboard用來作為最終的排名。

我就用時間順序來敘述一下整個過程。

Problem Formulation Got Wrong

一開始我覺得這是一個時間序列預測的問題，所以我首先想到的是HMM，給一個（客戶，產品）的Tuple，對其歷史數據做建模。這樣大概做了一周，我發覺意義不大，主要原因是有相當比例的客戶每周是會引進新的產品的，並不是每個（客戶，產品）都有足夠的歷史數據來支撐模型的估算。我後來想想，我應該做一些Data Exploration的工作，尤其是在建模之前，不然就會吃很多虧，以為數據是什麼樣，而實際上並不是這樣。

我後來想想應該把它設計成一個監督學習的問題，這樣才能最大程度發揮數據的潛能。這樣做最為直接的辦法是，用3-8周的數據為第9周做特徵，得到的模型可以預測第10周（用4-9周的數據做特徵），這樣做了之後我在leaderboard上的成績很快就進入了前20%。

Validation Strategy Got Wrong

但是很快我就發現這樣做會碰到一個瓶頸：本地Cross Validation的結果明明提升了，但是在Leaderboard上的結果卻沒有。仔細思考一番就會發現，原因在於我local validation的split （random split）和train/test split （split by time）是不一致的，這樣在local validation得到的超參數在train/test split上並不是最優的。想到這個層次後，我就調整了自己的validation strategy，用3-7周為第8周做特徵，然後訓練，類似的用第9周做validation，得到的超參數在第9周重新訓練模型，在第10周也就是public leaderboard做test。這樣做了之後我很快就進入10%。

Feature Engineering

接下來做的事情就是增加更多的特徵，但是我自己並不是特別有做特徵的經驗，這個時候怎麼辦呢？我點開Leaderboard（LB）上排名前20的人，一個人一個人的看他們以前都參加過什麼比賽，在哪些比賽中表現的比較好，那些比賽他們用了什麼方法。一般Prize Winner都會分享自己的solution，我想他們既然能做好一定是有一些常規經驗可以借鑒的。

前面提到由於歷史數據有很大比例的缺失（因為客戶每周都會引進新的產品）如何對這部分缺失的歷史數據做補全就變得挺重要了。LB上有些人在過去的比賽中曾經用過Field-aware Factorization Machine（FFM）贏過一些forecasting性質的比賽，這是一種Factorization Machine的變體，具有比較廣泛的實用性。受這些內容的啟發，並在了解了其基本原理後，我就用網上找的代碼實現了一些基於FFM的特徵，於是不出意外我就很快進入前20了。

再然後我感覺我對自己使用XGBoost缺乏經驗，裡面有很多參數我都不太清楚。我就去網上找有沒有相關經驗分享的Slides和視頻。Kaggle每隔一段時間就會邀請一些全站排名很高的人來做講座，網上都有他們的視頻，這些視頻通常都會分享一些調參數和做特徵的經驗，看了這些資料後我在XGB的調參有了很大的進步，自己的LB排名一度到了第二，截圖留念！

在關於做特徵的方向上，我也做了一些探索性的工作。我把Validation集上的Error拿出來做了一些簡單的分析。發現產生較大Error的原因主要有兩方面，一方面是就是我之前所說的Missing History，這類Error可以通過一些協同過濾的辦法有效規避，另一方面是一些客戶會不定期的退貨，相比進貨量，退貨量的預測是非常困難的。作為供貨方的Grupo Bimbo並沒有提供這方面的信息，某種程度來說，我個人覺得這個問題是Unsolvable的。

之後又做了一些特徵，排名也始終在前三。這個時候我突然發現了一個嚴重的問題，那就是比賽的最終排名是依據第11周的結果而不是第10周，所以我無論怎麼優化第10周都不代表我能很高的預測第11周。在傳統time series的預測問題中，為了預測第11周，可以先預測第10周然後再假設第10周的數據已知，然後再預測第11周。但是這裡並不適用，因為第10周的數據被downsample了。所以我覺得可能有必要直接做一個獨立的Two-Week-Ahead Forescasting的模型。

我做了一個簡單的假想實驗：假設現在第10周是private board，而第9周是public board，也就是說我只能在第8周上train模型，並且做特徵的時候也不能用最近的那周的數據，因為對第10周來說，我並沒有第9周的完整數據。現在有兩個方案：

1. 還是像之前那樣做，在第8周上訓練，然後把第10周當作第9周一樣做預測
2. 重新做特徵，把特徵中關於上一周的信息都抹掉，重新在第8周上訓練，然後在第9周上驗證，最後在第10周上測試。

這兩個方案用來測試第10周的時候都沒有用到第9周的數據，實驗結果表明前一種方案比後一種要差0.002。這個差別已經在public LB上影響排名了，並且隨著更多特徵的加入，這個差別還可能會更大。另一方面我注意到它們訓練得到的XGB模型也是不太一樣的，在前一種方案里，上周的歷史特徵會比較dominate這個模型，其importance score非常高，而後一種方案里，歷史特徵被比較均勻的分布在上兩周，上三周，上四周等。基於這些觀察，我傾向於後一種方案才是正確的validation方案。

這個時候離比賽結束還有不到兩個月，也是從這個時候開始，因為調整了validation strategy，我的public LB分就沒再增長過，直到比賽的最後一天。

Solution Implementation

由於數據規模比較大（Billion級別，數據量大於通常的Kaggle比賽），用Python筆記本的內存已經吃不動了，我一開始採取的方案是先把所有數據導入到MySQL，做了Index後，從Matlab里每次從資料庫retrieve一小撮數據做處理。這樣雖然能裝下筆記本的內存，但是計算時間實在太高了，每次過一遍所有數據做一個特徵要幾個小時。後來我完全放棄了MySQL+Matlab的組合，而選擇使用C++和Python的組合。

準確來說，我用C++做特徵工程，其中用標準庫實現一些簡單的數據結構（鏈表等，方便數據的Index），原來需要幾個小時的特徵工程，現在只需要幾分鐘了，由於用C++可以精確管理內存，整個過程的內存開銷也基本壓縮到2G左右。對於內存開銷過大的模型，比如FFM，XGB，我則在Server並行著跑，然後把結果寫在硬碟上。最終我的整個方案的迭代周期被縮短到一小時以內。

No Progress

自從我調整了Validation Strategy後，我在單個模型的Performance上似乎遇到了瓶頸，主要表現在於新加了特徵後，雖然訓練集（第8周），驗證集（第9周）的結果都提升了，但是測試集（第10周）反而會變差。仔細思考一番後，我覺得有可能是以下原因：

• 不同周的數據本身就不滿足相同分布，過分的最求某幾周的Performance會導致其他周的結果變差
• 模型太過複雜（特徵太多），所以出現了Overfitting Backtest
• 代碼Bug

卡了幾天後，我就把這個事情放一邊了出去歡快的玩耍了，去了馬德里和塞維利亞玩了一圈，看看歐洲杯什麼的。

Team Up

在我出去玩的這段時間，又有很多新的隊伍參加進來，其中包括超過一半Kaggle全站排名前50的競爭者。排名靠前的人發現自己的Progress放緩後也開始紛紛Merge Team，力求提升排名。

在離比賽差不多還有20天的時候，我也覺得應該找人Merge Team，說不定不同的Team會有不同的思路。我在比賽論壇發了帖子，此時我的public LB排名已經掉出前十了，但是我相信可能有一半排名比我高的Team並沒有察覺One-week-ahead 和Two-week-ahead的不同，或者察覺了但是不覺得這是一個嚴重的問題：後天會不會下雨應該和明天會不會下雨差不多概率吧。

最後一個對Kaggle非常有經驗的小夥伴（Kaggle全站排名前20）聯繫了我，當時他排在大約前2%這樣。我們Merge後交流了一下彼此工作，我從他那了解到FTRL模型，雖然扮演的角色和FFM差不多，但是原理很不一樣，如果和我的模型組合到一起說不定會有更多的提升；他從我這了解了更加正確的Validation Strategy，也調整了他當下調參的策略。

組隊後我開始著手ensemble兩人的模型，算是有了一些progress。比起我幾周前的最好Single Model大約提生了不到0.003，考慮到正確的validation辦法還能存在0.002的advantage，我覺得在private leaderboard上有超越在public LB分比我們高0.005的人的可能性（而且事實證明這確實發生了）這樣就可能進入前10了。

也是在組隊的這段時間，我陸續發現我之前的C++程序有一些不大不小的Bug。。。Orz，這大概解釋我為什麼我的Progress突然就Stop了，淚。

Final Result

最終的結果我們排在了1969個隊伍的第11位，我已經挺滿意啦。最終，我們確實超過了很多原本public LB排在我們之前的隊伍，但同時也有一些聰明的隊伍超過了我們。我相信最終前10的隊伍確實都做了足夠豐富的特徵，並且絕大部分也使用了正確的validation方案。撒花！

最後我有一些感想：

1. Kaggle比賽的門檻並不高，但是每個人剛開始參加能獲得什麼樣的成績很大程度上跟這個人的學習能力和數學編程基礎比較有聯繫。與其說是機器學習的比賽，不如說是對相關基礎的一個全面考察的過程。
2. Kaggle比賽是有經驗可循的，但是這些經驗都是建立在正確理解問題的基礎上的。所以我覺得並不存在絕對的經驗，更重要的是學會用科學的方法去驗證或否定這些經驗。比如在這次比賽中，傳統的Cross Validation和Backtest Validation都不是最優方案，獨立發現正確的Validation Strategy至關重要。
3. 如果想要獲獎一定要在每個方面做到極致，這也是我覺得跟前三名的差距。我相信從方案上看，我覺得排名靠前的隊伍的大致方向都是差不多的，但是在特徵工程方面，在模型的驗證和Ensemble方面，肯定存在差距。我們的最終方案大概包括不到20個特徵，而我看到第4名的隊伍有超過100+的特徵集合，所以那5個千分點也是Significant！

推薦閱讀：