今天介紹的這個演算法，Follow-The-Regularized-Leader (FTRL) Proximal ，是Google於2011年 [1] 提出，2013年 [2] 加入修改並作了針對廣告點擊率 (Click Through Rate) 預測的應用探討的一個機器學習演算法。在Kaggle上面兩次CTR比賽冠軍都使用這個演算法。
這學期人工智慧課程我和阿牧、Tommy參加了Kaggle的CTR比賽。這次資料是由中國的網路行銷公司提供 2014/10/21~30共四千萬筆資料當訓練集，2014/10/31四百萬筆資料當測試，比較各隊的預測值之對數損失(logarithmic loss)。目前我們使用這個演算法達到 0.394 的準確度，在全體排名到達前三分之一。而事實上，前面的參賽者大多是使用FTRL演算法。
這個演算法是基於OGD(online gradient descent)，使其更加稀疏(sparsity)的版本。
2. 演算法介紹
FTRL的核心是一種online logistic regression，在原始演算法上加入L1, L2 regularization和 adaptive learning，其演算法如下：
T是每筆資料，I則是feature domain。更新每個變數的權重時，會參考L1的值，因此很能夠達到稀疏性，同時，每個變數的更新速度都跟它先前的表現有關(G1:t)。除了L1，L2也被加進去進一步防止 over-fitting。
3. 演算法實現
這個演算法的 Python code下載地方在此，需要的記憶體很小，用一般CPU跑這次比賽的資料 (四千萬筆資料，21個變數，開一個2^25的feature vector) 大概只要半個小時。提供者是Kaggle世界排名前兩百的 Tinrtgu 大大。
關於這個code的討論和各種修改版本，可以到這裡來看眾神人的討論。
4. Reference
[1] Follow-the-regularized-leader and mirror descent: Equivalence theorems
and L1 regularization. In AISTATS, 2011.H. B. McMahan.
一些反思：
事實上我是透過比賽的討論版上，Tingrtu的PO文才知道有這個演算法的。感謝他之餘，也深感學術文化的差異。如果是我的話肯定不會把方法講出來。事實上我認為它如果沒公布這個方法，可能也只有前百名才能達到0.4以下。
後記：
第一次撰寫類似學習筆記這類的文章，如果有寫錯或是寫作技巧可以改進的地方，還請不吝在底下留言指教。事實上這個演算法的論文探討的相當詳細，包括在大量數據下可以怎麼省記憶體同時維持預測率、feature drop-out等等。不過礙於我還是個菜鳥，還需要大量的時間才能讀懂啊(汗)
