七、LS-PLM 模型

1. 论文 “Learning Piece-wise Linear Models from Large Scale Data for Ad Click Prediction” 提出了 “Large Scale Piece-wise Linear Model:LS-PLM” 模型来求解 CTR 预估问题，并给出了有效的优化算法来训练 LS-PLM 模型。

   该模型自2012年以来作为阿里巴巴在线展示广告系统中的主要 CTR 预测模型。

7.1 模型

1. LS-PLM 模型基于分而治之的策略：

   • 首先将特征空间划分为几个局部区域
   • 然后在每个区域中建立一个广义线性模型
   • 最后将每个广义线性模型加权作为最终输出

2. LS-PLM 具有非线性、可扩展性、稀疏性的优点。

   • 非线性：如果特征空间划分区域足够多，则 LS-PLM 模型将拟合任何复杂的非线性函数。
   • 可扩展性：LS-PLM 可以扩展到超大规模和超高维特征。
   • 稀疏性：带有 和 正则化的 LS-PLM 模型具有很好的稀疏性。

3. 给定数据集 ，其中：

   

   LS-PLM 算法基于分而治之的策略，将整个特征空间划分为一些局部区域，对每个区域采用广义线性分类模型：

   

   其中：

   • 为模型参数。

     

     因此 有 两种表示方法：

     • 列向量： 。其中：

       

       表示第 列。

     • 行向量： 。其中：

       

       表示第 行。

     因此我们有： ，其中 为行索引、 为列索引：

     

   • 将样本划分到 个区域

   • 对每个空间进行预测

   • 用于对结果进行归一化

4. 一种简单的情形是：

   

   此时有：

   

   这可以被认为是一种混合模型：

   

   其中：

   • 表示样本划分到区域 的概率。它满足：

     

   • 表示在区域 中，样本 属于正类的概率。

   论文主要研究这种简单的模型。

5. LS-PLM 模型的目标函数为：

   

   其中：

   • loss 是负的对数似然损失函数：

     

   • 和 是 和 正则化项：

     

     • 该正则化先计算每个维度在各区域的正则化，然后将所有维度的正则化直接累加。
     • 正则化主要用于特征选择； 主要用于模型稀疏性，但是它也有助于特征选择。

7.2 优化算法

1. 由于 和 正则化项是非凸、非光滑的函数，因此 LS-PLM 的目标函数 采用传统的算法（如：随机梯度下降）难以优化。

   论文提出了一种有效的基于方向导数和拟牛顿法的优化算法。

2. 定义方向导数为：

   

   当 时， 就是使得函数值 下降的方向。其中

   

   对应于参数 的方向。

   可以证明：对于任意的参数 和任意方向 ， 的方向导数都存在。

   证明过程：

   

   • 第一项：因为 是光滑的、可微的，所以有：

     

     这里的向量点积是将两个张量展平为两个一维向量，再进行点积。

   • 第二项：

     

     根据：

     

     其中 是 的第 行组成的向量。

     则有：

     

   • 第三项：

     

     考虑到：

     

     因此有：

     

   最终得到方向导数：

   

   其中 分别表示 的第 行的行向量； 分别表示 的第 行第 列。 表示向量长度。

3. 既然代价函数的方向导数存在，则可以求得代价函数降低最多的那个方向作为梯度下降的方向。

   由于代价函数降低的幅度与方向 的长度有关，因此给定长度约束 ，其中 C 是一个常数。即：

   

   这是一个带约束的最优化问题，最终解得：

   

   其中：

   

4. 给定方向向量 ，我们可以通过 LBFGS 算法估计出海森矩阵的逆矩阵 ，其中用到辅助向量 。最后得到参数更新的方向 。

   但是论文采用了两个技巧：

   • 保证参数更新的方向和方向向量 一致。

   • 由于目标函数 是非凸的，因此不能保证 是正定的。因此：

     • 当 时，采用 来更新
     • 当 时，采用 来更新

     

     其中 为参数更新方向， 函数用于确保参数更新的方向和 的方向一致。

5. 当得到参数更新方向 ，我们通过线性搜索来查找最佳步长 ，则得到参数更新：

   

   但是论文还添加了约束条件：每轮迭代前后，参数的正负号保持不变。因此有：

   

   其中：

   • 存放 每个参数的正负号（如果 则使用 的正负号）。

   • 确保 的正负号和 一致，也即和 的正负号一致。

     因此要想参数 符号发生改变，唯一的机会是当 时基于 的符号来改变。

6. LS-PLM 模型优化算法：

   • 输入：训练集

   • 输出：模型参数

   • 步骤：

     • 随机初始化参数

     • 迭代： ，其中 为最大迭代步数。迭代步骤为：

       • 计算

       • 计算

       • 更新

       • 判断停止条件：

         • 如果 满足停止条件（如 ，或者 ），则停止迭代并返回 。

         • 否则继续迭代，并更新 ：

           

   .

7.3 模型实现

1. 为了在工业场景中应用 ，论文基于分布式学习框架来实现 LS-PLM 模型。框架中包含两种类型的计算单元：

   • server：每个 server 结点分别独立的存储全局模型中的一部分。
   • worker：每个 worker 结点存储部分训练样本，以及一个局部模型。该局部模型仅仅保存用于训练本地样本的模型参数。

   其中每个计算结点包含一个 server 结点和一个 worker 结点。这种方式充分利用了 server 结点的计算能力，又可以和 worker 结点很方便的共享内存。

   

   在每次迭代过程中：

   • 每个 worker 首先用本地数据和局部模型计算损失和下降方向（数据并行）
   • 然后 server 将损失 loss、方向 、以及其它需要用于计算 的项汇总，从而计算 (模型并行)
   • 最终 worker 同步最新的

   

2. 为了提高训练速度，论文优化了特征计算过程。

   如图所示：用户 U1 在一个 session 中看到三条广告，因此产生三个样本。事实上，这三个样本共享 U1 的画像特征（如：年龄、性别、城市、兴趣爱好等）。

   

   由于大量的计算几种在 和 ， 因此可以将计算拆解成样本共享特征和样本非共享特征：

   

   其中 表示样本的共享特征， 为样本的非共享特征。对于共享特征，每个用户只需要计算一次并保存起来，后续该用户的所有样本都可以直接复用该计算结果。

   因此共享特征计算优化步骤为：

   • 将训练样本根据共享特征分组（如：年龄、城市、性别 ），共享特征相同的样本划分到同一个 worker 中。
   • 每组共享特征仅需要存放一次，从而节省内存。如：年龄 = 20, 城市 = 北京，性别 = 女 这组特征只需要存放一次，该组的所有样本不需要重复存储该组特征。
   • 在更新损失函数和梯度时，每组共享特征只需要计算一次，从而提高计算速度。

   由于阿里巴巴的生产数据具有共享特征的模式，因此该技巧可以大幅度提高训练速度。在 100 个 worker 、每个 worker 12个 CPU core, 11GB 内存的条件下，实验结果表明：内存显著降低到 1/3，计算速度加快 12 倍左右。

   

7.4 实验结论

1. 论文使用了阿里巴巴移动展示广告的 7 个数据集，它们是在不同日期收集的，但是数据集各自的收集时间是连续的。

   每个数据集的训练集、验证集、测试集的比例约为 7: 1 : 1 。

   

2. 区域数量 ：参数 的物理意义是区域数量，它控制了模型的容量。

   越大则模型容量越大，拟合能力越强，但是模型训练代价也越大。因此实际应用中必须在模型的拟合能力和训练成本之间平衡。

   模型在数据集 1 上的结果如下图所示。

   • 当 时，模型测试 AUC 明显强于 。

   • 当 时，模型测试 AUC 相对于 虽然有所提升，但是提升幅度很小。

     因此后续采用 。

   

3. 正则化可以缓解模型过拟合，除此之外 和 正则化都会使得模型更稀疏。如结果所示：

   • 仅采用 正则化，最终保留了 9.4% 的非零权重，从而保留了 18.7% 的特征。

     这是因为特征数量时参数数量的一半，因此非零特征比例是非零参数比例的一倍。

   • 仅采用 正则化，最终保留了 1.9% 的非零特征，从而保留了 12.7% 的特征（谨慎怀疑这里有问题）。

   • 联合采用 正则化和 正则化，最终得到更稀疏的模型，以及泛化能力更强的模型。

   

4. LS-PLM 和 LR 模型在 7 个数据集上的对比如下图所示（评估指标为测试 auc ）：

   所有超参数通过 grid search 搜索。其中：

   • LS-PLM 的超参数 ， 最佳超参数为
   • LR 采用 正则化，超参数 ，最佳超参数为