七、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 模型 - 图1七、LS-PLM 模型 - 图2 正则化的 LS-PLM 模型具有很好的稀疏性。
  3. 给定数据集 七、LS-PLM 模型 - 图3 ,其中:

    七、LS-PLM 模型 - 图4

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

    七、LS-PLM 模型 - 图5

    其中:

    • 七、LS-PLM 模型 - 图6 为模型参数。

      七、LS-PLM 模型 - 图7

      因此 七、LS-PLM 模型 - 图8 有 两种表示方法:

      • 列向量:七、LS-PLM 模型 - 图9 。其中:

        七、LS-PLM 模型 - 图10

        七、LS-PLM 模型 - 图11 表示第 七、LS-PLM 模型 - 图12 列。

      • 行向量:七、LS-PLM 模型 - 图13 。其中:

        七、LS-PLM 模型 - 图14

        七、LS-PLM 模型 - 图15 表示第 七、LS-PLM 模型 - 图16 行。

      因此我们有:七、LS-PLM 模型 - 图17 ,其中 七、LS-PLM 模型 - 图18 为行索引、 七、LS-PLM 模型 - 图19 为列索引:

      七、LS-PLM 模型 - 图20

    • 七、LS-PLM 模型 - 图21 将样本划分到 七、LS-PLM 模型 - 图22 个区域

    • 七、LS-PLM 模型 - 图23 对每个空间进行预测

    • 七、LS-PLM 模型 - 图24 用于对结果进行归一化

  4. 一种简单的情形是:

    七、LS-PLM 模型 - 图25

    此时有:

    七、LS-PLM 模型 - 图26

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

    七、LS-PLM 模型 - 图27

    其中:

    • 七、LS-PLM 模型 - 图28 表示样本划分到区域 七、LS-PLM 模型 - 图29 的概率。它满足:

      七、LS-PLM 模型 - 图30

    • 七、LS-PLM 模型 - 图31 表示在区域 七、LS-PLM 模型 - 图32 中,样本 七、LS-PLM 模型 - 图33 属于正类的概率。

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

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

    七、LS-PLM 模型 - 图34

    其中:

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

      七、LS-PLM 模型 - 图35

    • 七、LS-PLM 模型 - 图36七、LS-PLM 模型 - 图37七、LS-PLM 模型 - 图38七、LS-PLM 模型 - 图39 正则化项:

      七、LS-PLM 模型 - 图40

      • 该正则化先计算每个维度在各区域的正则化,然后将所有维度的正则化直接累加。
      • 七、LS-PLM 模型 - 图41 正则化主要用于特征选择; 七、LS-PLM 模型 - 图42 主要用于模型稀疏性,但是它也有助于特征选择。

7.2 优化算法

  1. 由于 七、LS-PLM 模型 - 图43七、LS-PLM 模型 - 图44 正则化项是非凸、非光滑的函数,因此 LS-PLM 的目标函数 七、LS-PLM 模型 - 图45 采用传统的算法(如:随机梯度下降)难以优化。

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

  2. 定义方向导数为:

    七、LS-PLM 模型 - 图46

    七、LS-PLM 模型 - 图47 时,七、LS-PLM 模型 - 图48 就是使得函数值 七、LS-PLM 模型 - 图49 下降的方向。其中

    七、LS-PLM 模型 - 图50

    七、LS-PLM 模型 - 图51 对应于参数 七、LS-PLM 模型 - 图52 的方向。

    可以证明:对于任意的参数 七、LS-PLM 模型 - 图53 和任意方向 七、LS-PLM 模型 - 图54七、LS-PLM 模型 - 图55 的方向导数都存在。

    证明过程:

    七、LS-PLM 模型 - 图56

    • 第一项:因为 七、LS-PLM 模型 - 图57 是光滑的、可微的,所以有:

      七、LS-PLM 模型 - 图58

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

    • 第二项:

      七、LS-PLM 模型 - 图59

      根据:

      七、LS-PLM 模型 - 图60

      其中 七、LS-PLM 模型 - 图61七、LS-PLM 模型 - 图62 的第 七、LS-PLM 模型 - 图63 行组成的向量。

      则有:

      七、LS-PLM 模型 - 图64

    • 第三项:

      七、LS-PLM 模型 - 图65

      考虑到:

      七、LS-PLM 模型 - 图66

      因此有:

      七、LS-PLM 模型 - 图67

    最终得到方向导数:

    七、LS-PLM 模型 - 图68

    其中 七、LS-PLM 模型 - 图69 分别表示 七、LS-PLM 模型 - 图70 的第 七、LS-PLM 模型 - 图71 行的行向量; 七、LS-PLM 模型 - 图72 分别表示 七、LS-PLM 模型 - 图73 的第 七、LS-PLM 模型 - 图74 行第 七、LS-PLM 模型 - 图75 列。七、LS-PLM 模型 - 图76 表示向量长度。

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

    由于代价函数降低的幅度与方向 七、LS-PLM 模型 - 图77 的长度有关,因此给定长度约束 七、LS-PLM 模型 - 图78,其中 C 是一个常数。即:

    七、LS-PLM 模型 - 图79

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

    七、LS-PLM 模型 - 图80

    其中:

    七、LS-PLM 模型 - 图81

  4. 给定方向向量 七、LS-PLM 模型 - 图82,我们可以通过 LBFGS 算法估计出海森矩阵的逆矩阵 七、LS-PLM 模型 - 图83 ,其中用到辅助向量 七、LS-PLM 模型 - 图84 。最后得到参数更新的方向 七、LS-PLM 模型 - 图85

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

    • 保证参数更新的方向和方向向量 七、LS-PLM 模型 - 图86 一致。

    • 由于目标函数 七、LS-PLM 模型 - 图87 是非凸的,因此不能保证 七、LS-PLM 模型 - 图88 是正定的。因此:

      • 七、LS-PLM 模型 - 图89 时,采用 七、LS-PLM 模型 - 图90 来更新
      • 七、LS-PLM 模型 - 图91 时,采用 七、LS-PLM 模型 - 图92 来更新

      七、LS-PLM 模型 - 图93

      其中 七、LS-PLM 模型 - 图94 为参数更新方向,七、LS-PLM 模型 - 图95 函数用于确保参数更新的方向和 七、LS-PLM 模型 - 图96 的方向一致。

  5. 当得到参数更新方向 七、LS-PLM 模型 - 图97 ,我们通过线性搜索来查找最佳步长 七、LS-PLM 模型 - 图98,则得到参数更新:

    七、LS-PLM 模型 - 图99

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

    七、LS-PLM 模型 - 图100

    其中:

    • 七、LS-PLM 模型 - 图101 存放 七、LS-PLM 模型 - 图102 每个参数的正负号(如果 七、LS-PLM 模型 - 图103 则使用 七、LS-PLM 模型 - 图104 的正负号)。

    • 七、LS-PLM 模型 - 图105 确保 七、LS-PLM 模型 - 图106 的正负号和 七、LS-PLM 模型 - 图107 一致,也即和 七、LS-PLM 模型 - 图108 的正负号一致。

      因此要想参数 七、LS-PLM 模型 - 图109 符号发生改变,唯一的机会是当 七、LS-PLM 模型 - 图110 时基于 七、LS-PLM 模型 - 图111 的符号来改变。

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

    • 输入:训练集 七、LS-PLM 模型 - 图112

    • 输出:模型参数 七、LS-PLM 模型 - 图113

    • 步骤:

      • 随机初始化参数 七、LS-PLM 模型 - 图114

      • 迭代:七、LS-PLM 模型 - 图115 ,其中 七、LS-PLM 模型 - 图116 为最大迭代步数。迭代步骤为:

        • 计算 七、LS-PLM 模型 - 图117

        • 计算 七、LS-PLM 模型 - 图118

        • 更新 七、LS-PLM 模型 - 图119

        • 判断停止条件:

          • 如果 七、LS-PLM 模型 - 图120 满足停止条件(如 七、LS-PLM 模型 - 图121,或者 七、LS-PLM 模型 - 图122 ),则停止迭代并返回 七、LS-PLM 模型 - 图123

          • 否则继续迭代,并更新 七、LS-PLM 模型 - 图124

            七、LS-PLM 模型 - 图125

    .

7.3 模型实现

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

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

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

    七、LS-PLM 模型 - 图126

    在每次迭代过程中:

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

    七、LS-PLM 模型 - 图131

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

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

    七、LS-PLM 模型 - 图132

    由于大量的计算几种在 七、LS-PLM 模型 - 图133七、LS-PLM 模型 - 图134 , 因此可以将计算拆解成样本共享特征和样本非共享特征:

    七、LS-PLM 模型 - 图135

    其中 七、LS-PLM 模型 - 图136 表示样本的共享特征, 七、LS-PLM 模型 - 图137 为样本的非共享特征。对于共享特征,每个用户只需要计算一次并保存起来,后续该用户的所有样本都可以直接复用该计算结果。

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

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

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

    七、LS-PLM 模型 - 图138

7.4 实验结论

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

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

    七、LS-PLM 模型 - 图139

  2. 区域数量 七、LS-PLM 模型 - 图140 :参数 七、LS-PLM 模型 - 图141 的物理意义是区域数量,它控制了模型的容量。

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

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

    • 七、LS-PLM 模型 - 图143 时,模型测试 AUC 明显强于 七、LS-PLM 模型 - 图144

    • 七、LS-PLM 模型 - 图145 时,模型测试 AUC 相对于 七、LS-PLM 模型 - 图146 虽然有所提升,但是提升幅度很小。

      因此后续采用 七、LS-PLM 模型 - 图147

    七、LS-PLM 模型 - 图148

  3. 正则化可以缓解模型过拟合,除此之外 七、LS-PLM 模型 - 图149七、LS-PLM 模型 - 图150 正则化都会使得模型更稀疏。如结果所示:

    • 仅采用 七、LS-PLM 模型 - 图151 正则化,最终保留了 9.4% 的非零权重,从而保留了 18.7% 的特征。

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

    • 仅采用 七、LS-PLM 模型 - 图152 正则化,最终保留了 1.9% 的非零特征,从而保留了 12.7% 的特征(谨慎怀疑这里有问题)。

    • 联合采用 七、LS-PLM 模型 - 图153 正则化和 七、LS-PLM 模型 - 图154 正则化,最终得到更稀疏的模型,以及泛化能力更强的模型。

    七、LS-PLM 模型 - 图155

  4. LS-PLMLR 模型在 7 个数据集上的对比如下图所示(评估指标为测试 auc ):

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

    • LS-PLM 的超参数 七、LS-PLM 模型 - 图156, 最佳超参数为 七、LS-PLM 模型 - 图157
    • LR 采用 七、LS-PLM 模型 - 图158 正则化,超参数 七、LS-PLM 模型 - 图159,最佳超参数为 七、LS-PLM 模型 - 图160

    七、LS-PLM 模型 - 图161