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等等。不过碍于我还是个菜鸟，还需要大量的时间才能读懂啊(汗)
