FTRL
FTL Follow The Leader 在线学习的一种思路 #card
- 为了减少单个样本的随机扰动，每次找到让之前所有损失函数之和最小的参数。
- $w=\operatorname{argmin}{w} \sum{i=1}^{t} f_{i}(w)$
FTRL 带正则项的 FTL 算法 #card - $w=\operatorname{argmin}{w} \sum{i=1}^{t} f_{i}(w)+R(w)$
通过代理损失函数求解
[[稀疏性]] 模型稀疏好处
减少预测内存和复杂度，大量参数是零
利用 L1 正则不仅能获得稀疏，而且能降低模型过拟合带来的风险
稀疏模型，相对来说可解释性更好。
为什么 SGD 不一定能保证模型的稀疏性？#card
- 不同于 Batch，Online 中每次 的更新并不是沿着全局梯度进行下降，而是沿着某个样本的产生的梯度方向进行下降，整个寻优过程变得像是一个“随机” 查找的过程(SGD 中 Stochastic 的来历)，这样 Online 最优化求解即使采用 L1 正则化的方式， 也很难产生稀疏解。
数据集规模大，每一次计算全局梯度的代价变得过高，完成训练时间会变得很长。
在线学习：每次处理一个样本，处理过的样本会被丢弃。
特点 #card
每个特征一个学习率([[Adam]]中也实现了)
收敛速度快
L1 正则引入稀疏性，L2 正则引入平滑 [[弹性网络回归]]
How they choose to center the additional strong convexity used to guarantee low regret: RDA centers this regularization at the origin, while FOBOS centers it at the current feasible point. 结合[[FOBOS]]高精度以及 RDA 较好的稀疏性
- How they handle an arbitrary non-smooth regularization function $\Psi$. This includes the mechanism of projection onto a feasible set and how $L_1$ regularization is handled.
工业实践经验
第一个技巧是特征舍弃，在实际的应用场景下，有的特征出现的次数很少，但它们的种类特别多。由于是在线学习的环境，所以需要在线上不断学习的过程中决定当前出现的新特征是否要加入到模型中来学习。#card
第一种方案是按照概率来的，每出现一个新特征，我们就分配一个概率并把它加入到模型中，同时统计。如果特征出现的次数越来越多，被加入到模型中的概率也就越来越大。
第二种方案则是特征出现的次数超过n次，就被加入到模型中。
第二个技巧是量化，#card
- 本来保存一个权重需要32位浮点数，但是经过观察，大多数系数都集中在[-2,2]，那么就可以减少到16bit保存，其中2bit保存整数，13bit保存小数，剩下的1bit保存正负号。
第三个技巧则是负采样
- 负采样本身的含义是， :-> 所有的正样本都保留，但负样本只以r的概率保留。这样做很符合“复读机”理论，毕竟未点击占据大多数情况。
- 从上面讲的“为什么是Sigmoid函数”那里可以看出，函数的原始输出拟合的是真实的后验概率。如果进行了负采样，拟合的目标就不是真实的后验概率了。#card
在推荐场景下只关心物料之间的排序，负采样不改变相对顺序，可以忽略。
但如果是在广告场景下，要计算出价、CTR、CVR的乘积来竞价排名，这时就需要精确地知道CTR的值是多少。负采样对精确值有干扰，需要校正。