十一、Online Learning

1. 常见的梯度下降法、牛顿法、拟牛顿法属于批学习batch 方法，每次迭代都需要对全量训练样本重新学习一遍。

   当面临搜索、推荐等高维度（数十亿甚至上百亿维度）、大尺度（百亿规模甚至千亿规模）数据的场景时，传统的批学习方法效率太低。

   解决该问题的方法是：在线学习 online learning 。

2. 最简单的在线学习策略是在线梯度下降Oneline Gradient Descent:OGD 。它是当 batch size = 1 的 mini-batch 随机梯度下降法的特殊情形。

   该算法每次迭代仅训练最新的样本，每个样本只被训练一次。

3. 不同于 mini-batch随机梯度下降，在 OGD 中，算法每次梯度更新并不是沿着全局梯度的负方向进行前进，而是带有非常大的随机性。

   这样即使采用 L1 正则化，模型也很难产生稀疏解。而在线学习过程中，稀疏性是一个主要追求目标，因为稀疏解有以下优点：

   • 可以降低有效特征数量，起到特征选择作用
   • 降低模型大小
   • 线上预测时，降低计算量

11.1 梯度截断法 TG

1. 为得到稀疏解，最简单的方式是进行梯度截断：每隔 步，当权重低于阈值 时截断为 0 。

   

   其中：

   

   该方法容易理解、实现简单，但是实际中很少应用。因为权重系数较小的原因，很可能是因为该维度训练不足（如出现该特征的样本太少）引起的，并不是因为该特征不重要引起的。简单的截断可能造成该部分特征丢失。

2. 梯度截断法 Truncated Gradient:TG 是对简单截断的一种改进。当权重低于阈值 时，它不是直接降低到 0 ，而是慢慢降低到 0 。

   

   其中：

   

   • 决定了参数的稀疏程度。这两个值越大，则模型的稀疏性越强。
   • 当 时，即 ，则有 。此时 TG 法退化到简单截断法。

   下图中，x 表示 z， 表示

   

11.2 FOBOS

1. 前向后向切分FOBOS:Forward-Backward Splitting 将权重更新分为两个步骤：

   

   其中 用于对参数进行正则化。

   该更新过程分为两步：

   • 第一步为标准的梯度下降

   • 第二步对梯度下降的结果进行微调。其中：

     • 为距离约束，用于保证微调发生在梯度下降结果的附近
     • 为正则化，用于产生稀疏性。 是正则化的学习率。

2. 将第一步方程代入第二步，有：

   

   为求得最优解，根据梯度为零有：

   

   因此有：

   

   可以看到：

   • 不仅与迭代期的状态 有关，还和迭代后的状态 有关。这就是 “前向”、“后向” 的由来。
   • FOBOS 与常规梯度下降在于 FOBOS 多了一项： 。

3. 当在 L1 正则化下， 。令 ，记 则有：

   

   由于求和项中每一项都是非负的，因此当每一项都最小时，整体最小。即：

   

   设 是最优解，则必有 。如果 ，则有：

   

   因此 必然不是最优解，矛盾。

   既然有 ，则分情况讨论：

   • 当 时，则有 ，则原始问题转化为：

     

     解得：

   • 当 时，有 ，则原始问题转化为：

     

     解得：

   因此得到 FOBOS 在 L1 正则化条件下的更新方程：

   

   其中 为符号函数：当 时取值为 -1；当 时取值为 1；当 时取值为 0 。

4. 重新调整更新公式：

   

   • 当一条样本产生的梯度 不足以对维度 的权重产生足够大的变化时，权重 被截断为 0 。

   • 当 ，，TG 更新方程退化为：

     

     因此当 时 ，TG 退化为 L1-FOBOS 。

11.3 RDA

1. TG,FOBOS 等算法都是基于随机梯度下降 SGD 算法而来，而正则对偶平均 Regularized Dual Averaging: RDA 算法是基于简单对偶平均法 Simple Dual Averaging Scheme 而来。

   RDA 的权重特新方程为：

   

   其中：

   • 表示梯度 对 的积分中值（积分平均值）
   • 为正则化项
   • 是一个辅助的严格凸函数
   • 是一个非负的非递减序列

2. 在 L1 正则化的情况下， 。设 ，它满足严格凸函数的条件。设 ，它满足非负非递减。则有：

   

   将其拆解为各维度的最小化问题，则有：

   

   其中 为所有梯度的均值。

   求解该方程，得到权重更新公式：

   

   因此当维度 上的累积梯度均值的绝对值小于 时，发生阈值截断。

3. L1-RDA 和 L1-FOBOS 的比较：

   • 对于L1-FOBOS ，当 时执行梯度截断。通常选择 时随着时间 下降的，因此 L1-FOBOS 的截断阈值是随着时间变化的。

     而 L1-RDA 的截断阈值 是固定的常数，因此相比 L1-FOBOS 更激进，也更容易产生稀疏性。

   • L1-RDA 基于梯度的累积均值 来判断，而 L1-FOBOS 基于最近的单次梯度 来判断。

     而梯度累积均值比单次梯度更稳定。

   • L1-RDA 的更新过程中， 与前一时刻的 无关，仅仅由梯度累积均值 来决定。

     而 L1-FOBOS 的更新过程中， 由前一时刻的 、 共同决定。

11.4 FTRL

1. 实验证明：L1-FOBOS 这类基于梯度下降的方法具有较高的精度，但是 L1-RDA 却具有更好的稀疏性。Follow the Regularized Leader : FTRL 结合了两者的优点：即具有较好的稀疏性，又具有较高的精度。

2. FTRL 综合考虑了 FOBOS 和 RDA ，其特征权重更新公式为：

   

   其中 为超参数。

   重新调整最优化目标为：

   

   令 ，考虑到最后一项与 无关，因此有：

   

   将其拆解为各维度的最小化问题，则有：

   

   求解该最优化问题，得到 FTRL 的参数更新方程：

   

   因此 L1 正则化项引入稀疏性，L2 正则化项平滑求解结果。

3. 对于TG,FOBOS 等基于随机梯度下降的算法，学习率通常是全局的：每个维度的学习率都是相同的。如： 。

   RDA 算法没有学习率的概率，该算法未用到学习率。

   在 FTRL 算法中，不同维度的学习率是单独考虑的 Per-Coordinate Learning Rates 。

   

   这是由于：

   • 如果某个特征的变化更快（梯度更大），说明损失函数在这一带变化比较剧烈，则我们学习的步伐减缓（学习率更小）。
   • 如果某个特征变化更慢（梯度更小），说明损失函数在这一带非常平缓，则我们学习的步伐可以加快（学习率更大）。

   同时 也是每个维度不同。令：

   

   则有：

   

   .