七、LS-PLM 模型
论文
“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 模型
LS-PLM
模型基于分而治之的策略:- 首先将特征空间划分为几个局部区域
- 然后在每个区域中建立一个广义线性模型
- 最后将每个广义线性模型加权作为最终输出
LS-PLM
具有非线性、可扩展性、稀疏性的优点。- 非线性:如果特征空间划分区域足够多,则
LS-PLM
模型将拟合任何复杂的非线性函数。 - 可扩展性:
LS-PLM
可以扩展到超大规模和超高维特征。 - 稀疏性:带有 和 正则化的
LS-PLM
模型具有很好的稀疏性。
- 非线性:如果特征空间划分区域足够多,则
给定数据集 ,其中:
LS-PLM
算法基于分而治之的策略,将整个特征空间划分为一些局部区域,对每个区域采用广义线性分类模型:其中:
为模型参数。
因此 有 两种表示方法:
列向量: 。其中:
表示第 列。
行向量: 。其中:
表示第 行。
因此我们有: ,其中 为行索引、 为列索引:
将样本划分到 个区域
对每个空间进行预测
用于对结果进行归一化
一种简单的情形是:
此时有:
这可以被认为是一种混合模型:
其中:
表示样本划分到区域 的概率。它满足:
表示在区域 中,样本 属于正类的概率。
论文主要研究这种简单的模型。
LS-PLM
模型的目标函数为:其中:
loss
是负的对数似然损失函数:和 是 和 正则化项:
- 该正则化先计算每个维度在各区域的正则化,然后将所有维度的正则化直接累加。
- 正则化主要用于特征选择; 主要用于模型稀疏性,但是它也有助于特征选择。
7.2 优化算法
由于 和 正则化项是非凸、非光滑的函数,因此
LS-PLM
的目标函数 采用传统的算法(如:随机梯度下降)难以优化。论文提出了一种有效的基于方向导数和拟牛顿法的优化算法。
定义方向导数为:
当 时, 就是使得函数值 下降的方向。其中
对应于参数 的方向。
可以证明:对于任意的参数 和任意方向 , 的方向导数都存在。
证明过程:
第一项:因为 是光滑的、可微的,所以有:
这里的向量点积是将两个张量展平为两个一维向量,再进行点积。
第二项:
根据:
其中 是 的第 行组成的向量。
则有:
第三项:
考虑到:
因此有:
最终得到方向导数:
其中 分别表示 的第 行的行向量; 分别表示 的第 行第 列。 表示向量长度。
既然代价函数的方向导数存在,则可以求得代价函数降低最多的那个方向作为梯度下降的方向。
由于代价函数降低的幅度与方向 的长度有关,因此给定长度约束 ,其中
C
是一个常数。即:这是一个带约束的最优化问题,最终解得:
其中:
给定方向向量 ,我们可以通过
LBFGS
算法估计出海森矩阵的逆矩阵 ,其中用到辅助向量 。最后得到参数更新的方向 。但是论文采用了两个技巧:
保证参数更新的方向和方向向量 一致。
由于目标函数 是非凸的,因此不能保证 是正定的。因此:
- 当 时,采用 来更新
- 当 时,采用 来更新
其中 为参数更新方向, 函数用于确保参数更新的方向和 的方向一致。
当得到参数更新方向 ,我们通过线性搜索来查找最佳步长 ,则得到参数更新:
但是论文还添加了约束条件:每轮迭代前后,参数的正负号保持不变。因此有:
其中:
存放 每个参数的正负号(如果 则使用 的正负号)。
确保 的正负号和 一致,也即和 的正负号一致。
因此要想参数 符号发生改变,唯一的机会是当 时基于 的符号来改变。
LS-PLM
模型优化算法:输入:训练集
输出:模型参数
步骤:
随机初始化参数
迭代: ,其中 为最大迭代步数。迭代步骤为:
计算
计算
更新
判断停止条件:
如果 满足停止条件(如 ,或者 ),则停止迭代并返回 。
否则继续迭代,并更新 :
.
7.3 模型实现
为了在工业场景中应用 ,论文基于分布式学习框架来实现
LS-PLM
模型。框架中包含两种类型的计算单元:server
:每个server
结点分别独立的存储全局模型中的一部分。worker
:每个worker
结点存储部分训练样本,以及一个局部模型。该局部模型仅仅保存用于训练本地样本的模型参数。
其中每个计算结点包含一个
server
结点和一个worker
结点。这种方式充分利用了server
结点的计算能力,又可以和worker
结点很方便的共享内存。在每次迭代过程中:
- 每个
worker
首先用本地数据和局部模型计算损失和下降方向(数据并行) - 然后
server
将损失loss
、方向 、以及其它需要用于计算 的项汇总,从而计算 (模型并行) - 最终
worker
同步最新的
为了提高训练速度,论文优化了特征计算过程。
如图所示:用户
U1
在一个session
中看到三条广告,因此产生三个样本。事实上,这三个样本共享U1
的画像特征(如:年龄、性别、城市、兴趣爱好等)。由于大量的计算几种在 和 , 因此可以将计算拆解成样本共享特征和样本非共享特征:
其中 表示样本的共享特征, 为样本的非共享特征。对于共享特征,每个用户只需要计算一次并保存起来,后续该用户的所有样本都可以直接复用该计算结果。
因此共享特征计算优化步骤为:
- 将训练样本根据共享特征分组(如:
年龄、城市、性别
),共享特征相同的样本划分到同一个worker
中。 - 每组共享特征仅需要存放一次,从而节省内存。如:
年龄 = 20, 城市 = 北京,性别 = 女
这组特征只需要存放一次,该组的所有样本不需要重复存储该组特征。 - 在更新损失函数和梯度时,每组共享特征只需要计算一次,从而提高计算速度。
由于阿里巴巴的生产数据具有共享特征的模式,因此该技巧可以大幅度提高训练速度。在
100
个worker
、每个worker
12个CPU core, 11GB
内存的条件下,实验结果表明:内存显著降低到1/3
,计算速度加快12
倍左右。- 将训练样本根据共享特征分组(如:
7.4 实验结论
论文使用了阿里巴巴移动展示广告的 7 个数据集,它们是在不同日期收集的,但是数据集各自的收集时间是连续的。
每个数据集的训练集、验证集、测试集的比例约为 7: 1 : 1 。
区域数量 :参数 的物理意义是区域数量,它控制了模型的容量。
越大则模型容量越大,拟合能力越强,但是模型训练代价也越大。因此实际应用中必须在模型的拟合能力和训练成本之间平衡。
模型在数据集
1
上的结果如下图所示。当 时,模型测试
AUC
明显强于 。当 时,模型测试
AUC
相对于 虽然有所提升,但是提升幅度很小。因此后续采用 。
正则化可以缓解模型过拟合,除此之外 和 正则化都会使得模型更稀疏。如结果所示:
仅采用 正则化,最终保留了
9.4%
的非零权重,从而保留了18.7%
的特征。这是因为特征数量时参数数量的一半,因此非零特征比例是非零参数比例的一倍。
仅采用 正则化,最终保留了
1.9%
的非零特征,从而保留了12.7%
的特征(谨慎怀疑这里有问题)。联合采用 正则化和 正则化,最终得到更稀疏的模型,以及泛化能力更强的模型。
LS-PLM
和LR
模型在 7 个数据集上的对比如下图所示(评估指标为测试auc
):所有超参数通过
grid search
搜索。其中:LS-PLM
的超参数 , 最佳超参数为LR
采用 正则化,超参数 ,最佳超参数为