在线学习算法 - OGD =》 FOBOS =》 RDA =》 FTRL

优化函数

优化函数：

其中x表示模型的参数，xi表示模型的第i个参数。

L(x)是逻辑回归的似然函数的负对数。

最右边那一项是L1正则项。

可以考虑加上L2正则来防止过拟合。

OGD算法

假设模型参数为x，第t个样本的特征表示为vt

则样本label为1的概率为：

该样本对应的对数损失函数为：

令

则lt关于xt的求导过程如下：

上式即为第t个样本的梯度gt。

原始的OGD使用的迭代公式为：

其中et表示非增的学习率，也叫做步长，

OGD的算法比较简单，不够好，也不产生稀疏解。

FTRL-Proximal算法

{x_{t + 1}} = {{rm{argmin}}}limits_x left( {{g_{1:t}} cdot x + frac{1}{2} sum limits_{s = 1}^t {sigma _s}x - {x_s}_2^2 + {lambda _1}{x_1}} right)

https://raw.githubusercontent.com/sjtuhzc/CTR-estimator/master/CTRmodel.scala

零散笔记

1. 在线凸优化和在线Bayesian

在线凸优化方法有很多，像FOBOS算法、RDA、FTRL等。

在线Bayesian 方面有比如AdPredictor 算法、基于内容的在线矩阵分解算法等。

2. 次梯度在不可微点的应用

the iterates of the subgradient method are very rarely at the points of non-differentiability。

3. H. Brendan McMahan 3年的paper

2010年 理论性paper，未介绍正则化项迭代

2011年 regret bound，引入通用正则化项

2011年 OGD、FOBOS、RDA与FTRL的关系

2013年 工程实现、伪代码

4. 批量算法（batch）

image.png

∏表示投影，∏右下角符号表示x的取值范围。

参考：http://www.cnblogs.com/EE-NovRain/p/3810737.html

公式中的gt表示次梯度，在求解约束优化问题时，很容易得到不符合约束的解，这时候需要向符合约束的解进行投影。

该方法又叫做投影梯度下降。

5. 混合正则化项

例如1范数与2范数强凸项的混合：

6. 在线算法

在线算法参数更新公式：

其中αt表示学习率，gt表示单点loss的次梯度，ξt表示混合正则化项的第二项梯度。

C表示约束空间，如1范数的约束空间，方法类似投影梯度下降的做法。

7. 稀疏的重要性

减少predict时的内存和复杂度

8. 稀疏解

稀疏解的三种解法：

简单截断

image.png

简单截断方法有问题：权重小，可能是确实是无用特征，还或者可能是该特征才刚被更新一次（例如训练刚开始的阶段、或者训练数据中包含该特征的样本数本来就很少），另外，简单rounding技术太aggressive了，可能会破坏在线训练算法的理论完备性。

TG（Truncated gradient）

image.png

黑盒去除法

黑盒的方法去除一些特征，然后重新训练的看被消去的特征是否有效。

需要在数据集上对算法跑多次，所以不太实用。

9. 几种在线学习算法的区别

image.png

第一项：梯度或累积梯度

第二项：L1正则化项的处理

第三项：low regret的需求，不要离已迭代结果，或者0太远

原网址: 访问
创建于: 2019-04-12 01:24:49
目录: default
标签: 无

未标明原创文章均为采集，版权归作者所有，转载无需和我联系，请注明原出处，南摩阿彌陀佛，知识，不只知道，要得到

请先后发表评论
  • 最新评论
  • 总共0条评论