最近在看FTRL相关的一些资料，主要是冯扬的《在线最优化求解》。作者从稀疏性的角度将在线学习发展过程中出现的几种优化算法娓娓道来，既有详细的推导过程，也有感性的理解，是不可多得的学习材料。下面是我在学习过程中的一些认识，记录下来。
在求解目标函数的最优解时，一般使用梯度下降算法。如果模型数据比较少，我们可以计算全局的梯度，这就是batch gradient descent。也有一种模式是来一个样本就更新一遍参数，这就是stochastic gradient descent（SGD）。当然，还有一种居中的方法，这就是mini-batch gradient descent。 SGD 和min-batch SGD 比较适合增量更新，所以在在线学习中经常使用。但是在SGD过程中，由于使用的是单个样本的梯度，并不是全局的梯度方向，这样，更新方向很可能并不是全局最优的，所以，这种情况下即使使用了L1正则，也很难得到稀疏模型。而模型的稀疏性的好处又很多，比如在内存和响应时间上更友好，可以增加泛化性，降低过拟合。所以在在线学习中，模型稀疏性是一个非常重要的目标。
为了实现稀疏性，学术界在L1正则的基础上提出了一系列的优化算法。最简单粗暴的就是简单截断法,就是小于一定阈值就把参数置0，这个显然是不合理的，可以说是伤敌一千自损八百。于是出现了截断梯度法(Truncated Gradient, TG)，主要思想是每隔k步执行一次梯度截断，这个截断更soft，表达式如下：
图像如下：
左侧是简单截断法，右侧是截断梯度法。可以看到，右侧又引入了一个参数\(\alpha\),当参数权重绝对值小于\(\alpha\)时，参数才会置0，当参数处在\(\alpha\)和\(\theta\)之间时，参数在正常的梯度下降上又做了一个偏移。当参数绝对值大于\(\theta\)时，参数就是正常的梯度下降了。
可以看出，当\(\alpha=\theta\)时，截断梯度法就是简单截断法。 如果 \(\theta = \infty\)且k=1时，截断梯度法就是L1正则了。
L1-FOBOS的表达式如下:
也就是说，如果当前迭代之后参数的值小于一个阈值，那么，参数就被置为0。否则，就在正常梯度下降的基础上做了一个微调，这个微调会让参数向0的方向靠近，同时，随着迭代，靠近的力度慢慢减小。
当 \(𝜃 = ∞，𝑘 = 1，𝜆_{𝑇𝐺}^{(t)} = 𝜂^{(𝑡+\frac{1}{2})}𝜆\) 时，L1-FOBOS 就是TG。所以，L1-FOBOS 就是TG的一种特殊形式罢了。
特殊点我理解就在于阈值随着迭代不断减小，所以参数置为0的概率越来越低，模型的稀疏性也就越来越难以保证了。
RDA是微软在10年提出的一种算法，该算法不像前面的两种算法，它不依赖于梯度下降。所以它的准确性可能不如前面两个，但是稀疏性却进一步得到了保证。
L1-RDA的表达式如下：
\(\overline g_i^t=\frac{1}{t}\sum_{r=1}^t g_i^{(r)}\) 表示过去一段时间内的梯度的均值。
可以看出来，RDA的思想是过去一段时间内梯度均值小于阈值，那么这个参数就置为0，否则就按照上面的等式来更新。 从更新公式可以看到，没有一点梯度下降的影子，只是在梯度均值上做了微调。前面是缩放，后面是将参数往0的方向推，且推进的力度是恒定的。
为什么RDA的稀疏性更好呢？从上面的表达式可以看出来，RDA的阈值是恒定的，就是正则项系数，所以L1-RDA的截断相比L1-FOBOS更激进，所以更容易产生稀疏解。
有实验表明，L1-FOBOS 这一类基于梯度下降的方法有比较高的精度，但是L1-RDA 却能在损失一定精度的情况下产生更好的稀疏。而下面的FTRL 综合了二者的优点，在精度和稀疏性上兼顾的更好。
FTRL的更新公式如下：
\(\lambda_1,\lambda_2\)分别是L1、L2正则项系数。
可以看出，FTRL的阈值是固定的，所以稀疏性上和RDA是类似的。
在参考链接1中，作者证明了，在FTRL中去掉正则项之后，其实就是在做梯度下降。这样的话，FTRL 既获得了稀疏解，同时解的精度也比较好。
之前的算法的学习率对所有参数都是一样的，而FTRL在实现的时候还有一个trick，就是学习率对每个参数都是不一样的。
如何理解这个公式呢?
该公式反应了数据在不同维度上的特征分布的不均匀性，如果包含w某一个维度特征的训练样本很少，每一个样本都很珍贵，那么该特征维度对应的训练速率可以独自保持比较大的值，每来一个包含该特征的样本，就可以在该样本的梯度上前进一大步，而不需要与其他特征维度的前进步调强行保持一致。
如果特征1 比特征2 的变化更快，那么在维度1上的学习率应该下降得更快。
代码实现： https://www.kaggle.com/jiweiliu/ftrl-starter-code
代码实现上比较简单，基本上可以对照着公式看。
由于FTRL可以应用在不同的算法上，在网上找到一份FM的FTRL实现，可以学习下
https://github.com/CastellanZhang/alphaFM http://castellanzhang.github.io/2016/10/16/fm_ftrl_softmax/
ToDo:
下面是上面这些算法的论文，抽空看下，对理解原理会更有帮助
Adaptive Bound Optimization for Online Convex Optimization 首次提出FTRL
Follow-the-Regularized-Leader and Mirror Descent:Equivalence Theorems and L1 Regularization FTRL 原理
Ad Click Prediction: a View from the Trenches google工程化实践
Sparse Online Learning via Truncated Gradient 截断梯度法
Efficient Online and Batch Learning using Forward Backward Splitting FOBOS
Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization RDA
参考:
1.http://vividfree.github.io/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0/2015/12/05/understanding-FTRL-algorithm
2.http://www.huaxiaozhuan.com/%E6%B7%B1%E5%BA%A6%E5%AD%A6%E4%B9%A0/chapters/4_optimization.html
3.https://liam.page/2019/08/31/a-not-so-simple-introduction-to-FTRL/