优化函数

优化函数：

其中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太远