Question

1. 点击率click-through rate: CTR 预估是价值数十亿美金的在线广告行业的核心问题。为了提高 CTR 预估的准确性，越来越多的数据被牵涉进来，使得 CTR 预估成为一个大规模的机器学习问题，具有海量样本和高维特征。

   • 传统的解决方案是应用以并行方式训练的线性逻辑回归 logistic regression: LR 模型。具有 $ L_1 $ 正则化的 LR 模型可以生成稀疏解，使得在线预估更快。

     不幸的是，CTR 预估问题是一个高度非线性的问题。特别是，用户点击的生成涉及很多复杂的因素，例如广告质量、上下文信息、用户兴趣以及这些因素的复杂交互。为了帮助 LR 模型捕获非线性，人们探索了特征工程技术feature engineering technique ，这既费时又费力。

   • 另一个方向是通过精心设计的模型捕获非线性。

     • Facebook 使用混合模型，将决策树和逻辑回归相结合。决策树起到了非线性特征变换的作用，其输出被馈入 LR 模型。然而，基于树的方法不适合非常稀疏和非常高维的数据。
     • Rendle S. 2010 引入了因子分解机 Factorization Machine: FM ，它涉及使用二阶函数（或使用其它阶数的函数）的特征之间的交互。但是，FM 无法拟合数据中的所有通用非线性模式（比如比二阶更高的高阶模式）。

   在论文 《Learning Piece-wise Linear Models from Large Scale Data for Ad Click Prediction》 中，作者提出了一个分段线性模型以及针对大规模数据的训练算法，并将其命名为大规模分段线性模型Large Scale Piecewise Linear Model: LS-PLM 。LS-PLM 遵循分而治之的策略，即先将特征空间划分为若干个局部区域，然后在每个区域拟合一个线性模型，最后得到加权线性预测组合的输出。注意：这两步是以监督方式同时学习的，旨在最小化预测损失。

   LS-PLM 在三个方面优于 web-scale 的数据挖掘：

   • 非线性nonlinearity：有了足够多的划分区域，LS-PLM 可以拟合任何复杂的非线性函数。
   • 可扩展性scalability：和 LR 模型类似，LS-PLM 可以扩展到海量样本和高维特征。论文设计了一个分布式系统，可以在数百台机器上并行训练模型。在阿里巴巴在线生产系统中，每天都会训练和部署数十个具有数千万参数的 LS-PLM 模型。
   • 稀疏性sparsity：模型稀疏性是工业场景中 online serving 面临的实际问题。论文展示了具有 $ L_1 $ 和 $ L_{2,1} $ 正则化的 LS-PLM 可以实现良好的稀疏性。

   带有稀疏正则化的 LS-PLM 的学习可以转化为一个非凸、非可微的优化问题，这个问题很难解决。论文针对此类问题提出了一种基于方向导数directional derivatives 和拟牛顿法的有效优化方法。

   由于能够捕获非线性模式、以及对海量数据的可扩展性，LS-PLM 已经成为阿里巴巴在线展示广告系统display advertising system 中的主力 CTR 预估模型，并从 2012 年初以来为数亿用户提供服务。它还应用于推荐系统、搜索引擎、以及其它产品系统。

7.1 模型

1. 给定数据集 $ \mathbb D = \{(\mathbf{\vec x}_1,y_1),\cdots,(\mathbf{\vec x}_N,y_N)\} $ ，其中：

   $ \mathbf{\vec x}_i = (x_{i,1},\cdots,x_{i,d})^T\in \mathbb R^d,\quad y_i\in \{0,1\} $

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

   $ p(y=1\mid \mathbf{\vec x}) = g\left(\sum_{m=1}^M \sigma(\mathbf{\vec u}_m\cdot \mathbf{\vec x})\times \eta(\mathbf{\vec w}_m\cdot \mathbf{\vec x})\right) $

   其中：

   • $ \sigma (\mathbf{\vec u}_m\cdot \mathbf{\vec x}) $ 将样本划分到 $ M $ 个区域， $ \eta(\mathbf{\vec w}_m\cdot \mathbf{\vec x}) $ 对每个空间进行预测， $ g(\cdot) $ 用于对结果进行归一化。

   • $ \mathbf \Theta=\left[\mathbf{\vec u}_1,\cdots,\mathbf{\vec u}_M,\mathbf{\vec w}_1,\cdots,\mathbf{\vec w}_M\right]^\top \in \mathbb R^{2M\times d},\mathbf{\vec u}_m\in \mathbb R^d,\mathbf{\vec w}_m\in \mathbb R^d $ 为模型参数。其中：

     $ \Theta_{m,j} = \begin{cases} u_{m,j},& 1\le m\le M\\ w_{m-M,j},& M+1\le m\le 2M \end{cases},\quad j=1,\cdots,d $

2. 一种简单的情形是：

   $ \sigma(\mathbf{\vec u}_m\cdot \mathbf{\vec x}) = \frac{\exp(\mathbf{\vec u}_m\cdot \mathbf{\vec x})}{\sum_{m^\prime=1}^M\exp(\mathbf{\vec u}_{m^\prime}\cdot \mathbf{\vec x})}\\ \eta(\mathbf{\vec w}_m\cdot \mathbf{\vec x}) = \frac{1}{1+ \exp(-\mathbf{\vec w}_m\cdot \mathbf{\vec x})}\\ g(z) = z $

   此时有：

   $ p(y=1\mid \mathbf{\vec x}) = \sum_{m=1}^M \frac{\exp(\mathbf{\vec u}_m\cdot \mathbf{\vec x})}{\sum_{m^\prime=1 }^M \mathbf{\vec u}_{m^\prime }\cdot \mathbf{\vec x}} \times \frac{1}{1+ \exp(-\mathbf{\vec w}_m\cdot \mathbf{\vec x})} $

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

   $ p(y = 1\mid \mathbf{\vec x}) = \sum_{m=1}^M p(z=m\mid {\mathbf{\vec x}}) \times p(y = 1\mid z=m,\mathbf{\vec x}) $

   其中：

   • $ p(z=m\mid {\mathbf{\vec x}}) = \frac{\exp(\mathbf{\vec u}_m\cdot \mathbf{\vec x})}{\sum_{m^\prime }^M \mathbf{\vec u}_{m^\prime }\cdot \mathbf{\vec x}} $ 表示样本划分到区域 $ m $ 的概率。它满足：

     $ p(z=m\mid {\mathbf{\vec x}}) \ge 0,\quad \sum_{m=1}^M p(z=m\mid {\mathbf{\vec x}}) = 1 $

   • $ p(y = 1\mid z=m,\mathbf{\vec x}) = \frac{1}{1+ \exp(-\mathbf{\vec w}_m\cdot \mathbf{\vec x})} $ 表示在区域 $ m $ 中，样本 $ \mathbf{\vec x} $ 属于正类的概率。

   我们主要研究这种简单的模型。

   读者注：该模型的参数空间放大了 $ O(M) $ 倍。考虑到 CTR 预估场景中，逻辑回归模型的参数规模可以高达十亿级，因此 $ M $ 不能太大。但是太小的 $ M $ 无法捕获足够多的非线性，因此该模型比较鸡肋。

3. 下图说明了在一个 demo 数据集中，该 LS-PLM 和 LR 模型的差异。图 A) 是 demo 数据集，这是一个二分类问题，红点属于正类、蓝点属于负类。图 B) 显示了使用 LR 模型的分类结果，图 C) 显示了使用LS-PLM 模型的分类结果。可以清晰地看到 LS-PLM 能够捕获到数据中的非线性模式。

   

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

   $ \mathcal J = \text{loss}(\mathbf \Theta) + \lambda ||\mathbf \Theta||_{2,1} + \beta ||\mathbf \Theta||_1 $

   其中：

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

     $ \text{loss}(\mathbf\Theta) = -\sum_{i=1}^N\left[y_i\log p(y_i = 1 \mid \mathbf{\vec x}_i;\mathbf\Theta) + (1-y_i)\log p(y_i = 0 \mid \mathbf{\vec x}_i;\mathbf\Theta) \right] $

   • $ ||\mathbf \Theta||_{2,1} $ 和 $ ||\mathbf\Theta||_1 $ 是 $ L_{2,1} $ 和 $ L_1 $ 正则化项：

     $ ||\mathbf\Theta||_{2,1} = \sum_{j=1}^d\sqrt{\sum_{m=1}^{2M}\Theta_{i,j}^2} ,\quad ||\mathbf\Theta||_1 =\sum_{j=1}^d\sum_{m=1}^{2M}|\Theta_{i,j}| $

     这些正则化先计算每个维度在各区域的正则化，然后将所有维度的正则化直接累加。

     • $ ||\mathbf \Theta||_{2,1} $ 正则化主要用于特征选择。在我们的模型中，特征的每个维度都和 $ 2M $ 个参数相关联。 $ L_{2,1} $ 正则化预期将单个特征的所有 $ 2M $ 个参数推到零，即抑制那些不太重要的特征。
     • $ ||\mathbf\Theta||_1 $ 主要用于模型稀疏性，但是它也有助于特征选择。它可以强制特征的参数尽可能为零，这有助于提高模型的解释能力和泛化性能。

     但是， $ L_1 $ 范数和 $ L_{2,1} $ 范数都是非平滑函数。这导致目标函数是非凸的和非光滑的，使得很难应用那些传统的梯度下降优化方法或 EM 方法。

7.2 优化算法

1. 定义方向导数为：

   $ f^\prime(\mathbf \Theta;\mathbf{ v}) = \lim_{\alpha \rightarrow 0} \frac{f(\mathbf\Theta+\alpha\mathbf{ v}) - f(\mathbf\Theta)}{\alpha} $

   当 $ f^\prime(\mathbf \Theta;\mathbf{ v} ) \lt 0 $ 时， $ \mathbf{ v} $ 就是使得函数值 $ f(\mathbf \Theta) $ 下降的方向。其中

   $ \mathbf v = \begin{bmatrix} v_{1,1}&v_{1,2}&\cdots& v_{1,d}\\ v_{2,1}&v_{2,2}&\cdots &v_{2,d}\\ \vdots&\vdots&\ddots &\vdots\\ v_{2M,d}&v_{2M,2}&\cdots &v_{2M,d}\\ \end{bmatrix}\in \mathbb R^{2M\times d} $

   $ v_{m,j} $ 对应于参数 $ \Theta_{m,j} $ 的方向。

   定义符号函数 $ \text{sgn}(\cdot) $ 为：

   $ \text{sgn}(x) = \begin{cases} 1,& x\gt 0\\ 0,& x = 0\\ -1, & x\lt 0 \end{cases} $

   定义投影函数 $ \pi(\cdot) $ 为：

   $ \pi_{m,j}(\mathbf \Theta,\mathbf \Omega) = \begin{cases} \Theta_{m,j}, & \text{sgn}(\Theta_{m,j}) = \text{sgn}(\Omega_{m,j})\\ 0,&\text{other} \end{cases} $

   它表示将 $ \mathbf \Theta $ 投影到 $ \mathbf \Omega $ 定义的象限 orthant 。

2. 如前所述，我们针对大规模 CTR 预估问题的目标函数既不是凸函数、也不是平滑函数。在这里，我们提出了一种通用且有效的优化方法来解决此类非凸问题。

   由于我们目标函数的负梯度并不是对所有的 $ \mathbf \Theta $ 都存在，因此我们采用方向 $ \mathbf v $ 来替代，其中该方向是最小化方向导数 $ f^\prime(\mathbf \Theta;\mathbf{ v} ) $ 。方向导数 $ f^\prime(\mathbf \Theta;\mathbf{ v} ) $ 对任何 $ \mathbf \Theta $ 和方向 $ \mathbf v $ 都存在，这就是下面的引理。

3. 引理：当目标函数 $ f(\mathbf \Theta) $ 由一个损失函数、一个 $ L_1 $ 正则化项、一个 $ L_{2,1} $ 正则化项组成时（比如前述的目标函数），那么方向导数 $ f^\prime(\mathbf \Theta;\mathbf{ v} ) $ 对任何 $ \mathbf \Theta $ 和方向 $ \mathbf v $ 都存在。

   证明过程：

   $ f^\prime(\mathbf \Theta;\mathbf{ v}) = \lim_{\alpha\rightarrow 0 } \frac{f(\mathbf\Theta + \alpha \mathbf{ v})-f(\mathbf\Theta)}{\alpha}\\ = \lim_{\alpha\rightarrow 0 } \frac{\text{loss}(\mathbf\Theta + \alpha \mathbf{ v})-\text{loss}(\mathbf\Theta)}{\alpha} + \lim_{\alpha\rightarrow 0 }\lambda \frac{||\mathbf\Theta + \alpha \mathbf{ v}||_{2,1}-||\mathbf\Theta||_{2,1}}{\alpha}\\ + \lim_{\alpha\rightarrow 0 }\beta \frac{||\mathbf\Theta + \alpha \mathbf{ v}||_{1}-||\mathbf\Theta||_{1}}{\alpha} $

   • 第一项：因为 $ \text{loss}(\mathbf\Theta) $ 是光滑的、可微的，所以有：

     $ \lim_{\alpha\rightarrow 0 } \frac{\text{loss}(\mathbf\Theta + \alpha \mathbf{ v})-\text{loss}(\mathbf\Theta)}{\alpha} = (\nabla_{\mathbf\Theta}\text{loss}) \cdot \mathbf{ v} = \sum_{m=1}^{2M}\sum_{j=1}^d \frac{\partial \text{loss}}{\partial \Theta_{m,j}}\times v_{m,j} $

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

   • 第二项：

     $ \lim_{\alpha\rightarrow 0 }\lambda \frac{||\mathbf\Theta + \alpha \mathbf{ v}||_{2,1}-||\mathbf\Theta||_{2,1}}{\alpha} \\ = \lim_{\alpha\rightarrow 0 }\lambda \frac{\sum_{j=1}^d\left(\sqrt{\sum_{m=1}^{2M}(\Theta_{m,j}+\alpha \times v_{m,j})^2 } -\sqrt{\sum_{m=1}^{2M} \Theta_{m,j}^2 }\right)}{\alpha} $

     根据：

     $ \lim_{\alpha\rightarrow 0 } \frac{ \sqrt{\sum_{m=1}^{2M}(\Theta_{m,j}+\alpha \times v_{m,j})^2 } -\sqrt{\sum_{m=1}^{2M} \Theta_{m,j}^2 } }{\alpha} = \begin{cases} \frac{ \mathbf \Theta_{:,j}\cdot \mathbf v_{:,j}}{ || \mathbf \Theta_{:,j}||_{2}}, &|| \mathbf \Theta_{:,j}||_{2} \ne 0\\ ||\mathbf v_{:,j}||_{2},&|| \mathbf \Theta_{:,j}||_{2} = 0 \end{cases} $

     其中： $ \mathbf \Theta_{:,j}\in \mathbb R^{2M} $ 为 $ \mathbf \Theta $ 的第 $ j $ 列组成的向量； $ \mathbf v_{:,j}\in \mathbb R^{2M} $ 是 $ \mathbf v $ 的第 $ j $ 列组成的向量。

     则有：

     $ \lim_{\alpha\rightarrow 0 }\lambda \frac{||\mathbf\Theta + \alpha \mathbf{ v}||_{2,1}-||\mathbf\Theta||_{2,1}}{\alpha} = \lambda \left( \sum_{\substack{1\le j\le d\\|| \mathbf \Theta_{:,j}||_{2 }\ne 0}}\frac{ \mathbf \Theta_{:,j}\cdot \mathbf v_{:,j}}{ || \mathbf \Theta_{:,j}||_{2 }} +\sum_{\substack{1\le i\le d\\|| \mathbf \Theta_{:,j}||_{2 } = 0}} || \mathbf v_{:,j}||_{2 }\right) $

   • 第三项：

     $ \lim_{\alpha\rightarrow 0 }\beta \frac{||\mathbf\Theta + \alpha \mathbf{ v}||_{1}-||\mathbf\Theta||_{1}}{\alpha} = \lim_{\alpha\rightarrow 0 }\beta \frac{\sum_{j=1}^d\sum_{m=1}^{2M} \left(|\Theta_{m,j} +\alpha\times v_{m,j}|-|\Theta_{m,j}|\right)}{\alpha} $

     考虑到：

     $ \lim_{\alpha\rightarrow 0 } \frac{|\Theta_{m,j} +\alpha\times v_{m,j}|-|\Theta_{m,j}|}{\alpha} = \begin{cases} \text{sgn}(\Theta_{m,j})\times v_{m,j},& \Theta_{m,j}\ne 0\\ |v_{m,j}|,&\Theta_{m,j} = 0 \end{cases} $

     因此有：

     $ \lim_{\alpha\rightarrow 0 }\beta \frac{||\mathbf\Theta + \alpha \mathbf{ v}||_{1}-||\mathbf\Theta||_{1}}{\alpha} = \beta \left(\sum_{\substack{1\le j \le d\\ 1\le m\le 2M\\ \Theta_{m,j} \ne 0}} \text{sgn}(\Theta_{m,j})v_{m,j}+\sum_{\substack{1\le j \le d\\ 1\le m\le 2M\\ \Theta_{m,j} = 0}} |v_{m,j}| \right) $

   最终得到方向导数。

   注意：这里的方向导数中假设 $ \alpha \gt 0 $ ，即右方向导数。

4. 由于方向导数 $ f^\prime(\mathbf \Theta;\mathbf{ v} ) $ 对任何 $ \mathbf \Theta $ 和方向 $ \mathbf v $ 都存在，因此当 $ f(\mathbf \Theta) $ 的负梯度不存在时，我们选择最小化方向导数 $ f^\prime(\mathbf \Theta;\mathbf{ v} ) $ 的方向作为下降方向。

   由于代价函数降低的幅度与方向 $ \mathbf{ v} $ 的长度有关，因此我们约束方向 $ \mathbf v $ 的长度 $ ||\mathbf v ||\le C $ ，其中 $ C $ 是一个常数。因此我们得到一个带约束的最优化问题：

   $ \mathbf{ v}^* = \arg\max_{\mathbf{ v}} f^\prime(\mathbf\Theta;\mathbf{ v})\\ s.t. ||\mathbf{ v}|| \le C $

5. 命题：给定一个光滑的损失函数 $ \text{loss}(\mathbf \Theta) $ 、以及一个目标函数 $ f(\mathbf \Theta)=\text{loss}(\mathbf \Theta) + \lambda ||\mathbf \Theta||_{2,1} + \beta||\mathbf \Theta||_1 $ ，则有界的、且最小化方向导数 $ f^\prime(\mathbf \Theta;\mathbf{ v} ) $ 的方向 $ \mathbf v $ 如下：

   $ v_{m,j} = \begin{cases} s_{m,j} - \beta\times \text{sgn}(\Theta_{m,j}),&\Theta_{m,j}\ne 0\\ \max(|s_{m,j}|-\beta,0)\times\text{sgn}(s_{m,j}),& \Theta_{m,j}=0,||\mathbf \Theta_{:,j}||_{2}\ne 0\\ \frac{\max(||\mathbf b_{:,j}||_{2} -\lambda,0)}{||\mathbf b_{:,j}||_{2}} \times b_{m,j},&||\mathbf \Theta_{:,j}||_{2} = 0 \end{cases} $

   其中：

   $ s_{m,j} = - (\nabla_{\mathbf\Theta}\text{loss})_{m,j} - \lambda\frac{\Theta_{m,j}}{||\mathbf \Theta_{:,j}||_{2}}\\ b_{m,j} = \max(|- (\nabla_{\mathbf\Theta}\text{loss})_{m,j}|-\beta,0)\times \text{sgn}(- (\nabla_{\mathbf\Theta}\text{loss})_{m,j}) $

   证明见原始论文。

6. 受 OWLQN 方法的启发，我们还限制模型参数在每次迭代中不改变符号sign 。在第 $ t $ 次迭代，给定最小化方向导数的方向 $ \mathbf v^{(t)} $ 和旧的模型参数 $ \mathbf \Theta^{(t)} $ ，则下一轮参数的象限约束为：

   $ \xi_{m,j}^{(t)} = \begin{cases} \text{sgn}\left(\Theta_{m,j}^{(t)}\right),&\Theta_{m,j}^{(t)} \ne 0\\ \text{sgn}\left(v_{m,j}^{(t)}\right),&\Theta_{m,j}^{(t)} = 0 \end{cases} $

   即：

   • 当 $ \Theta_{m,j}^{(t)}\ne 0 $ 时，新的 $ \Theta_{m,j} $ 在不改变符号。
   • 当 $ \Theta_{m,j}^{(t)} = 0 $ 时，我们为新的 $ \Theta_{m,j} $ 选择由 $ d_{m,j}^{(t)} $ 决定的象限。

7. 得到最小化方向导数的方向 $ \mathbf v $ 之后，我们并不是沿着 $ \mathbf v $ 的方向更新参数，而是沿着由 LBFGS 计算的下降方向来更新模型参数（从而加快收敛速度，因为二阶优化算法收敛速度更快）。此时需要计算在给定象限上目标函数的逆海森矩阵，其中用到辅助向量 $ \mathbf{ y}^{(t)},\mathbf{ s}^{(t)} $ 的序列。最后得到参数更新的方向 $ \mathbf H^{(t)} \mathbf v^{(t)} $ 。 这里我们采用两个技巧：

   • 首先，我们约束参数更新的方向位于针对于 $ \mathbf v^{(t)} $ 的象限。

   • 其次，由于我们的目标函数是非凸的，我们无法保证 $ \mathbf H^{(t)} $ 为正定的。我们使用 $ \mathbf y^{(t)}\cdot \mathbf s^{(t)}\gt 0 $ 作为条件来确保 $ \mathbf H^{(t) } $ 是正定矩阵：当 $ \mathbf{ y}^{(t)}\cdot \mathbf{ s}^{(t)} \gt 0 $ 时，采用 $ \mathbf H^{(t)} $ 来更新；新当 $ \mathbf{ y}^{(t)}\cdot \mathbf{ s}^{(t)} \le 0 $ 时，采用 $ \mathbf v^{(t)} $ 来更新。

     $ \mathbf p^{(t)} = \begin{cases} \pi\left(\mathbf H^{(t)}\mathbf v^{(t)},\mathbf v^{(t)}\right),& \mathbf{ y}^{(t)}\cdot \mathbf{ s}^{(t)} \gt 0\\ \mathbf v^{(t)},&\mathbf{ y}^{(t)}\cdot \mathbf{ s}^{(t)} \le 0 \end{cases} $

     其中 $ \mathbf{\vec p}^{(t)} $ 为参数更新的方向。

   给定参数更新方向，我们使用回溯线性搜索backtracking line search 来找到合适的步长 $ \alpha $ 。和 QWLQN 一样，我们将新的 $ \mathbf \Theta^{(t+1)} $ 投影到 $ \xi^{(t)} $ 给定的象限：

   $ \mathbf \Theta^{(t+1)} = \pi\left(\mathbf\Theta^{(t)} + \alpha \mathbf p^{(t)},\xi^{(t)}\right) $

   因此要想参数 $ \Theta_{m,j} $ 符号发生改变，唯一的机会是当 $ \Theta_{m,j} =0 $ 时基于 $ v_{m,j} $ 的符号来改变。

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

   • 输入：训练集 $ \mathbb D = \{(\mathbf{\vec x}_1,y_1),\cdots,(\mathbf{\vec x}_N,y_N)\} $

   • 输出：模型参数 $ \mathbf \Theta $

   • 步骤：

     • 随机初始化参数 $ \mathbf\Theta^{(0)} $ 。

     • 迭代： $ t=0,1,2,\cdots, T $ ，其中 $ T $ 为最大迭代步数。迭代步骤为：

       • 计算 $ \mathbf v^{(t)} $ 、 $ \mathbf p^{(t)} $ 、 $ \mathbf\Theta^{(t+1)} $ 。

       • 判断停止条件：如果 $ \mathbf \Theta^{(t+1)} $ 满足停止条件（如 $ ||\mathbf \Theta^{(t+1)} - \mathbf \Theta^{(t)}||_2\le \epsilon $ ，或者 $ |\mathcal J(\mathbf \Theta^{(t+1)}) - \mathcal J(\mathbf \Theta^{(t)})|\le \epsilon $ ），则停止迭代并返回 $ \mathbf \Theta^{(t+1)} $ 。否则继续迭代，并更新 $ \mathbf{ y} , \mathbf{ s} $ ：

         $ \mathbf{y}^{(t+1)} = \mathbf{\Theta}^{(t+1)}-\mathbf{\Theta}^{}\\ \mathbf{s}^{(t+1)} = -\mathbf{v}^{(t+1)}- (-\mathbf{v}^{(t)} ) $

   上述伪代码相比标准 LBFGS 算法仅有几处不同：

   • 使用最小化非凸目标函数的方向导数的方向 $ \mathbf v^{(t)} $ 代替负梯度。
   • 更新方向被约束到由所选方向 $ \mathbf v^{(t)} $ 定义的给定象限。当 $ \mathbf H^{(t)} $ 是非正定矩阵时，切换到 $ \mathbf v^{(t)} $ 。
   • 在线性搜索期间，每个搜索点都投影到前一个点的象限。

7.3 模型实现

1. 这里我们首先提供针对大规模数据的 LS-PLM 模型的并行实现，然后介绍一个有助于大大加快训练过程的重要技巧。

2. 为了在大规模setting 中应用LS-PLM 模型优化算法，我们使用分布式学习框架实现它，如下图所示。这是 parameter server 的变体。在我们的实现中，每个计算节点同时运行一个 server 节点和一个 worker 节点，目的是：

   • 最大限度地利用 CPU 的计算能力。在传统的 parameter server setting 中，server 节点作为分布式 KV 存储来使用，具有 push/pull 操作的接口，计算成本低。将 server 节点与 worker 节点一起运行可以充分利用算力。
   • 最大限度地利用内存。今天的机器通常有大内存，例如 128 GB。通过运行在同一个计算节点上，server 节点和 worker 节点可以更好地共享和利用大内存。

   

   简而言之，框架中有两个角色：

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

   在每次迭代过程中：

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

   

3. 除了通用并行实现之外，我们还优化了在线广告环境中的实现。CTR 预估任务中的训练样本通常具有非常相似的共同特征common feature模式。如下图所示：用户 U1 在一个 session 中看到三条广告，因此产生三个样本。事实上，这三个样本共享 U1 的画像特征（如：年龄、性别、城市、兴趣爱好等）。

   

   由于大量的计算集中在 $ \mathbf{\vec u}_m\cdot \mathbf{\vec x} $ 和 $ \mathbf{\vec w}_m\cdot \mathbf{\vec x} $ ， 因此可以将计算拆解成样本共享特征和样本非共享特征：

   $ \mathbf{\vec u}_m\cdot \mathbf{\vec x} = \mathbf{\vec u}_{m,c}\cdot \mathbf{\vec x}_c + \mathbf{\vec u}_{m,nc}\cdot \mathbf{\vec x}_{nc}\\ \mathbf{\vec w}_m\cdot \mathbf{\vec x} = \mathbf{\vec w}_{m,c}\cdot \mathbf{\vec x}_c + \mathbf{\vec w}_{m,nc}\cdot \mathbf{\vec x}_{nc} $

   其中： $ \mathbf{\vec x}_c $ 表示样本的共享特征， $ \mathbf{\vec x}_{nc} $ 为样本的非共享特征。

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

   具体而言，我们在以下三个方面优化了具有共同特征的并行实现技巧：：

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

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

   

7.4 实验

1. 数据集：我们的数据集来自于阿里巴巴的移动展示广告产品系统。我们在连续的一段时间收集了七个数据集，旨在评估所提出模型的一致性consist 性能。在每个数据集中，训练集/验证集/测试集是从不同的日期不相交地收集的，比例约为 7:1:1 。我们的评估指标为 AUC。

   数据集的详细数据如下表所示。

   

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

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

   模型在数据集 1 上的结果如下图所示。我们测试了 M = 6,12,24,36。可以看到：

   • 当 $ M=12 $ 时，模型测试 AUC 明显强于 $ M=6 $ 。
   • 当 $ M = 24,36 $ 时，模型测试 AUC 相对于 $ M =12 $ 虽然有所提升，但是提升幅度很小。因此后续实验采用 $ M = 12 $ 。

3. 正则化的效果：为了使得模型更简单、泛化能力更强，我们使用了了 $ L_1 $ 和 $ L_{2,1} $ 正则化来约束模型使得模型更稀疏。这里我们评估这两个正则化的效果，结果如下表所示。可以看到：

   • 不出所料， $ L_1 $ 和 $ L_{2,1} $ 正则化都可以使得我们的模型更稀疏。
   • 仅采用 $ L_{2,1} $ 正则化，最终保留了 9.4% 的非零权重，从而保留了 18.7% 的特征。
   • 仅采用 $ L_1 $ 正则化，最终保留了 1.9% 的非零权重，从而保留了 12.7% 的特征。
   • 联合采用 $ L_1 $ 正则化和 $ L_{2,1} $ 正则化，最终得到更稀疏的模型，以及泛化能力更强的模型。

   

   在这个实验中： $ M = 12 $ ； $ \beta $ 和 $ \lambda $ 在范围 {0.01, 0.1, 1, 10}内执行网格搜索，最后 $ \beta=1,\gamma=1 $ 表现最佳。

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

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

   • LS-PLM 的超参数 $ \beta \in \{0.01,0.1,1,10\},\lambda \in \{0.01,0.1,1,10\} $ ， 最佳超参数为 $ \lambda = 1,\beta = 1 $ 。
   • LR 采用 $ L_1 $ 正则化，超参数 $ \beta \in \{0.01,0.1,1,10\} $ ，最佳超参数为 $ \beta = 1 $ 。

   可以看到：

   • LS-PLM 显著超越了 LR，平均 AUC 提升为 1.4%，这对于在线广告系统的整体性能有显著影响。
   • 此外这个提升是稳定的，这确保了 LS-PLM 可以安全地部署到在线生产系统中。