機器學習筆記：FTRL-Proximal

1. 簡介

今天介紹的這個演算法，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.

[2] Ad Click Prediction: a View from the Trenches. H. Brendan McMahan,Gary Holt, D. Sculley et al.

一些反思：
事實上我是透過比賽的討論版上，Tingrtu的PO文才知道有這個演算法的。感謝他之餘，也深感學術文化的差異。如果是我的話肯定不會把方法講出來。事實上我認為它如果沒公布這個方法，可能也只有前百名才能達到0.4以下。

後記：
第一次撰寫類似學習筆記這類的文章，如果有寫錯或是寫作技巧可以改進的地方，還請不吝在底下留言指教。事實上這個演算法的論文探討的相當詳細，包括在大量數據下可以怎麼省記憶體同時維持預測率、feature drop-out等等。不過礙於我還是個菜鳥，還需要大量的時間才能讀懂啊(汗)

那隻貓依然在等待

　　最初搬進宿舍，舍外有兩隻貓，一隻黑白斑，一隻棕白斑。小棕白在我大三時被兩位女士領養，據說牠後來自己跑走，但並沒有再回來。

　　跟曾經把我抓傷過好幾次、經常占據宿舍旁seven內貨架的小棕白不一樣，小黑白很安靜內斂，經常坐在石階上看著來往的人群，像是在等待什麼。小黑白有個令人費解的習慣──牠經常就坐在店門口的腳踏墊上，望著裡面，卻始終不敢踏進去。在一個寒冷的台北冬夜，我嘗試輕輕推牠的背，讓牠進到裡面取暖，但牠前腳才跨過那個界線，便馬上轉身離去。我本以為他會生氣的對我喵喵叫，但他只是回頭看我一眼，便離去。連一聲抗議也沒有。

　　小黑白平時是由seven的員工餵食，他們輪流買些貓乾糧，每天在兩個固定時段將牠的食盆裝滿。如果超過時間沒人前來餵食，小黑白便會在店門口外喵喵叫上許久。說起來這大概是他除了叫春以外，唯一會發出聲音的時刻。而平常會讓人摸個夠的牠，此時也會對伸過來的手感到反感。當然，假如你伸過來的手裡有貓飼料的話另當別論。

　　前陣子seven因為合約到期，結束在宿舍旁的經營。在工人將裡面的擺設肢解拆掉的過程，我意外的在舍區的另一端看見小黑白，遠遠的望著這裡。

　　工人離去。原先明亮的地方此時空盪盪的，沒有一點光照進來。幾天下來，小黑白依然在同樣的地方附近遊蕩，在同樣的石階上靜靜的坐著看著往來的人群，依然在等待著什麼的樣子。