传统CTR 预估模型

CTR 预估模型主要用于搜索、推荐、计算广告等领域的 CTR 预估，其发展经历了传统 CTR 预估模型、神经网络CTR 预估模型。
传统 CTR 预估模型包括：逻辑回归LR 模型、因子分解机FM 模型、梯度提升树 GBDT 模型等。其优点是：可解释性强、训练和部署方便、便于在线学习。
本章主要介绍传统 CTR 预估模型。

一、LR 模型[2007]

在 cost-per-click:CPC 广告中广告主按点击付费。为了最大化平台收入和用户体验，广告平台必须预测广告的 CTR ，称作 predict CTR: pCTR 。对每个用户的每次搜索query，有多个满足条件的广告同时参与竞争。只有 pCTR x bid price 最大的广告才能竞争获胜，从而最大化 eCPM ：
$\text{eCPM} = \text{pCTR} \times \text{bid}$
基于最大似然准则可以通过广告的历史表现得统计来计算 pCTR 。假设广告曝光了 100次，其中发生点击 5pCTR = 5% $\text{CTR}_{\text{true}}$ 。
这种计算 pCTR 的方式对于新广告或者刚刚投放的广告问题较大：
- 新广告没有历史投放信息，其曝光和点击的次数均为 0 。
- 刚刚投放的广告，曝光次数和点击次数都很低，因此这种方式计算的 pCTR 波动非常大。
  如：一个真实 CTR 为 5% 的广告必须曝光 1000次才有 85% 的信心认为 pCTR 与真实 CTR 的绝对误差在1% 以内。真实点击率越低，则要求的曝光次数越多。
为解决这个问题，论文 《Predicting Clicks: Estimating the Click-Through Rate for New Ads》 提出利用 LR 模型来预测新广告的CTR。
从经验上来看：广告在页面上的位置越靠后，用户浏览它的概率越低。因此广告被点击的概率取决于两个因素：广告被浏览的概率、广告浏览后被点击的概率。
因此有：
$p(\text{click} \mid \text{ad},\text{pos}) = p(\text{click} \mid \text{ad},\text{pos},\text{seen}) \times p(\text{seen} \mid \text{ad}, \text{pos})$
假设：
- 在广告被浏览（即：曝光）到的情况下，广告被点击的概率与其位置无关，仅与广告内容有关。
- 广告被浏览的概率与广告内容无关，仅与广告位置有关。
  广告可能被拉取（推送到用户的页面），但是可能未被曝光（未被用户浏览到）。
则有：
$p(\text{click} \mid \text{ad},\text{pos}) = p(\text{click} \mid \text{ad}, \text{seen}) \times p(\text{seen} \mid \text{pos})$
- $p(\text{click} \mid \text{ad}, \text{seen})$ 就是我们关注和预测的 CTR 。
- 第二项与广告无关，是广告位置（即：广告位）的固有属性。
  $\text{impress}(\text{pos} )$ $\text{seen}(\text{pos})$ ，则：
  $p(\text{seen} \mid \text{pos}) = \frac{\text{seen}(\text{pos} )}{\text{impress}(\text{pos} )}$
  这也称作广告位的曝光拉取比。

1.1 数据集构造

通常广告主会为一个订单 order 给出多个竞价词 term，如：


xxxxxxxxxx
4
1
Title: Buy shoes now,
2
Text: Shop at our discount shoe warehouse!
3
Url: shoes.com
4
Terms: {buy shoes, shoes, cheap shoes}.

此时广告系统会为每个竞价词生成一个广告，每个广告对应相同的Title/Text/Url、但是不同的竞价词。

数据集包含 1万个广告主，超过 1百万个广告、超过 50万竞价词（去重之后超过 10万个竞价词）。注意，不同的竞价词可能会展示相同的广告。
- 样本的特征从广告基本属性中抽取（抽取方式参考后续小节）。广告的基本属性包括：
  - landing page 落地页：点击广告之后将要跳转的页面的 url。
  - bid term：广告的竞价词。
  - title：广告标题。
  - body：广告的内容正文。
  - display url：位于广告底部的、给用户展示的 url。
  - clicks：广告历史被点击的次数。
  - views：广告历史被浏览的次数。
- 将每个广告的真实点击率 CTR 来作为 label 。
  CTR $\overline{\text{CTR}}$ 来作为 CTR 。
为了防止信息泄露，训练集、验证集、测试集按照广告主维度来拆分。最终训练集包含 70% 广告主、验证集包含 10% 广告主、测试集包含 20% 广告主。每个广告主随机选择它的 1000个广告，从而确保足够的多样性。
因为同一个广告主的广告之间的内容、素材、风格相似度比较高，点击率也比较接近。
对于有专业投放管理的那些优质广告主，在数据集中剔除它们。因为：
- 优质广告主的广告通常表现出不同于普通广告主的行为：
  - 两种广告主的广告具有不同的平均点击率
  - 优质广告主的广告的点击率方差较低（表现比较稳定）、普通广告主的广告的点击率方差较高（表现波动大）
- 广告平台更关注于普通广告主，因为这些普通广告主的数量远远超过优质广告主的数量，而且这些普通广告主更需要平台的帮助。
100 $\overline{\text{CTR}}$ 来近似真实 CTR 来作为 label ，对于曝光次数较少的广告二者可能相差很远，这将导致整个训练和测试过程中产生大量噪音。
曝光阈值的选取不能太大，也不能太小：
- 阈值太小，则导致 label 中的噪音太多。
- 阈值太大，则离线训练样本（大曝光的广告）和在线应用环境（大量新广告和小曝光广告）存在gap，导致在线预测效果较差。

1.2 LR模型

论文将 CTR 预估问题视作一个回归问题，采用逻辑回归 LR 模型来建模，因为 LR 模型的输出是在 0 到 1 之间。
$\text{pCTR} = \frac{1}{1+\exp(-\sum_{i} w_i\times f_i)}$
$f_i$ $i$ $w_i$ 为该特征对应的权重。采用负号的原因是使得权重、特征和 pCTR 正相关：权重越大则 pCTR 越大。
- 模型通过 limited-memory Broyden-Fletcher-Goldfarb-Shanno:L-BFGS 算法来训练。
- 模型的损失函数为交叉熵：
  $\mathcal L = -[\overline{\text{CTR}}\times \log (\text{pCTR}) + (1-\overline{\text{CTR}})\times\log (1-\text{pCTR})]$
- $\sigma$ $\sigma$ 为超参数，其取值集合为 [0.01,0.03,0.1,0.3,1,3,10,30,100]，并通过验证集来选取最佳的值。
$\sigma = 0.1$ 的效果最好。
论文采取了一些通用的特征预处理方法：
- 模型添加了一个bias feature1 $b$ $b\times 1$ 。
  $\sum_{i} w_i\times f_i + b \rightarrow \sum_{i} w_i\times f_i + b\times 1 = \sum_{i^\prime} w_{i^\prime}\times f_{i^\prime}$
- $f_i$ $\log(f_i+1)$ $f_i^2$ 1 $f_i$ 取值为0 。
- 对所有特征执行标准化，标准化为均值为 0、方差为1 。
  注意：对于验证集、测试集的标准化过程中，每个特征的均值、方差使用训练集上的结果。
- 对所有特征执行异常值截断：对于每个特征，任何超过均值 5个标准差的量都被截断为 5个标准差。
  $f_1$ 的均值为 20，方差为 2 。则该特征上任何大于30 的值被截断为 30、任何小于 10 的值被截断为 10 。
  注意：对于验证集、测试集的异常值截断过程中，每个特征的均值、方差使用训练集上的结果。
评价标准：
- baseline ：采用训练集所有广告的平均 CTR 作为测试集所有广告的 pCTR 。
  即：测试集里无论哪个广告，都预测其 CTR 为一个固定值，该值就是训练集所有广告的平均 CTR 。
- 评估指标：测试集上每个广告的 pCTR 和真实点击率的平均 KL 散度。
  $\overline{\mathbb D_{KL}} = \frac 1T \sum_{i=1}^T \left(\text{pCTR}(\text{ad}_i) \times \log \frac{\text{pCTR}(\text{ad}_i)}{\overline{\text{CTR}}(\text{ad}_i)} + (1-\text{pCTR}(\text{ad}_i)) \times \log \frac{1-\text{pCTR}(\text{ad}_i)}{1-\overline{\text{CTR}}(\text{ad}_i)}\right)$
  KL $\text{pCTR}$ 和真实点击率之间的偏离程度。一个理想的模型，其 KL 散度为 0 ，表示预估点击率和真实点击率完全匹配。
  为了更好的进行指标比较，论文实验中也给出了测试集的 MSE （均方误差）指标。
模型不仅可以用于预测新广告的 pCTR ，还可以为客户提供优化广告的建议。
可以根据模型特征及其重要性来给广告主提供创建广告的建议，如：广告标题太短建议增加长度。

1.3 特征工程

1.3.1 Term CTR Feature Set

不同竞价词的平均点击率存在明显的差异，因此在预测某个广告的点击率时，相同竞价词的其它类似广告可能有所帮助。
因此论文对此提出两个特征，称作相同竞价词特征集 Term CTR Feature Set 。
对于广告 adterm $\text{ad}_\text{term}$ )
- 针对该 term 竞价的其它广告主所有广告的数量：
  $f_0 = N(\text{ad}_\text{term})$
  由于同一个广告主的不同广告之间相关性比较强，因此这里用其它广告主的广告作为特征来源。否则容易出现信息泄露。
- 针对该 term 竞价的其它广告主的广告点击率（经过归一化）：
  $f_1 = \frac{\alpha \overline{\text{CTR}} +N(\text{ad}_\text{term})\times \text{CTR}(\text{ad}_\text{term})}{\alpha + N(\text{ad}_\text{term})}$
  其中：
  - $\overline{\text{CTR}}$ 是训练集上所有广告的平均点击率
  - $N(\text{ad}_\text{term})$ 是针对该 term 竞价的其它广告主所有广告的数量
  - $\text{CTR}(\text{ad}_\text{term})$ 是针对该 term 竞价的其它广告主所有广告的平均点击率
  - $\alpha$ term $N(\text{ad}_\text{term}) =0$ $f_1 = \text{CTR}(\text{ad}_\text{term})$ 。
    $\alpha$ 代表了term 竞价的广告数量的先验强度，默认取值为 1 。
    $\alpha$ 的取值不敏感。
模型新增这两个特征的实验结果如下图所示，可见 term ctr feature set 使得评估指标 “平均 KL 散度” 提升了 13.28%。

1.3.2 Related Term CTR Feature Set

预测某个广告的点击率时，相关竞价词的其它类似广告可能也有所帮助。
如：广告 a 的竞价词是 “电脑”，广告 b 的竞价词是 “买电脑”，则广告 b 的点击率对于预测广告 a 的点击率是有帮助的。
考虑竞价词的子集/超集。
t $\mathbf R_{m,n}(t)$ （一个竞价词term 可能包含多个单词word，这里不考虑word 之间的词序）：
$\mathbf R_{m,n}(t) = \begin{cases}& |\text{ad}_{\text{term}}\cap t | >0 \;\text{and}\\ \text{ad: } &|t- \text{ad}_{\text{term}} | = m \;\text{and} \\ &| \text{ad}_{\text{term}} -t| =n \end{cases}$
如：t 是 red shoes
- 如果广告的竞价词是buy red shoest $\mathbf R_{0,1}$
- 如果广告的竞价词是 shoest $\mathbf R_{1,0}$
- 如果广告的竞价词是red shoest $\mathbf R_{0,0}$
- 如果广告的竞价词是blue shoest $\mathbf R_{1,1}$
$\mathbf R_{m,n}(t)$ 的定义可知：
- $\mathbf R_{0,0}$ 代表广告的竞价 term 和 t 完全匹配。
- $\mathbf R_{m,0}$ 代表广告的竞价 termt $m$ 个单词之外其它单词完全相同（不考虑词序）。
- $\mathbf R_{0,n}$ 代表广告的竞价 termt $n$ 个单词之外其它单词完全相同（不考虑词序）。
假设 * 为任意数值，则定义：
- $\mathbf R_{0,*}(t)$ 表示 t 的任何超集（不考虑词序）作为竞价term 的广告的集合。
- $\mathbf R_{*,0}(t)$ 表示 t 的任何子集（不考虑词序）作为竞价term 的广告的集合。
定义相关竞价词的一组特征，它们称为相关竞价词特征集 Related Term CTR Feature Set：
- 在 term 相关的竞价词上竞价的其它广告主所有广告的数量：
  $v_{m,n}(\text{term}) = |\mathbf R_{m,n}(\text{term})|$
- 在 term 相关的竞价词上竞价的其它广告主所有广告的平均点击率:
  $\overline{\text{CTR}_{m,n}}(\text{term}) = \frac{1}{|\mathbf R_{m,n}(\text{term})|}\sum_{x\in \mathbf R_{m,n}(\text{term})}\text{CTR}_x$
  $\text{CTR}_x$ 表示广告 x 的真实点击率。
  和 Term CTR Feature Set 一样，这里也采用平滑：
  $\text{CTR}_{m,n}(\text{term}) = \frac{\beta \overline{\text{CTR}} +|\mathbf R_{m,n}(\text{term})|\times \overline{\text{CTR}_{m,n}}(\text{term})}{\beta + |\mathbf R_{m,n}(\text{term})|}$
  $\beta$ 表示平滑系数。
$m,n\in \{0,1,2,3,*\}$ 一共 5x5=25 种组合，得到 25 x 2 =50 个 related term ctr特征。测试集的 “平均 KL 散度” 表明：采用这一组特征之后，取得了接近 20% 的提升。

1.3.3 Ad Quality Feature Set

即使是同一个竞价term，不同广告的点击率也存在显著差异。从经验来看，至少有五种粗略的要素影响用户是否点击：
- 外观 Appearance：外观是否美观。
- 吸引力 Attention Capture：广告是否吸引眼球。
- 声誉 Reputation：广告主是否知名品牌。
- 落地页质量 Landing page quality：点击广告之后的落地页是否高质量。
  虽然用户只有点击之后才能看到落地页，但是我们假设这些落地页是用户熟悉的广告主（如 ebay, amazon ），因此用户在点击之前就已经熟知落地页的信息。
- 相关性 Relevance：广告与用户 query 词是否相关。
针对每个要素，论文给出一些特征：
- 外观Appearance：
  - 广告标题包含多少个单词。
  - 广告标题是在广告体内还是在广告体外。
  - 标题是否正确的大小写首字母。
  - 广告标题是否包含了太多的感叹号、美元符号或其它标点符号。
  - 广告标题用的是短词还是长词。
- 吸引力 Attention Capture：
  - 标题是否包含暗示着转化的单词，如购买 buy、加入join、订阅subscribe 等等。
  - 这些转化词是否出现在广告体内还是广告体外。
  - 标题是否包含数字（如折扣率，价格等）。
- 声誉Reputation：
  - 底部展示的 URL 是否以 .com/.net/.org/.edu 结尾。
  - 底部展示的的 url 多长。
  - 底部展示的url 分为几个部分。
    如 books.com 只有两部分，它比 books.something.com 更好。
  - 底部展示的url 是否包含破折号或者数字。
  因为好的、短的 .com 域名比较贵，因此 url 体现了广告主的实力。
- 落地页质量Landing page quality：
  - 落地页是否包含 flash。
  - 落地页页面哪部分采用大图。
  - 落地页是否符合 W3C。
  - 落地页是否使用样式表。
  - 落地页是否弹出广告。
- 相关性 Relevance：
  - 竞价词是否出现在标题。
  - 竞价词的一部分是否出现在标题。
  - 竞价词或者竞价词的一部分是否出现在广告体内。
  - 如果出现，则竞价词或者竞价词的一部分占据广告体的几分之一。
最终在这 5 个要素种抽取了 81个特征。
某些特征可以出现在多个要素里，如：广告内容中美元符号数量。该特征可能会增加吸引力，但是会降低外观。
除了以上5个内容要素，还有一个重要的内容要素：广告文本的单词。
我们统计广告标题和正文中出现的 top 10000 个单词，将这1万个单词出现与否作为 unigram 特征。因为某些单词更容易吸引用户点击，因此unigram 特征能够弥补注意力要素遗漏的特征。
注意：构造特征时，标题和正文的 unigram 分别进行构造。即：单词是否出现在标题中、单词是否出现在正文中。
如下所示：单词 shipping 更倾向于在高 CTR 广告中出现，这意味着 shipping 更容易吸引用户点击。图中的三条曲线从上到下依次代表：
- 每个单词在高 CTR 广告中出现的平均频次。
- 每个单词在所有广告中出现的平均频次。
- 每个单词在低 CTR 广告中出现的平均频次。
以上5个内容要素，以及 unigram 特征一起构成了广告质量特征集 Ad Quality Feature Set。结果表明：
- 该组特征能够显著提升性能，将测试集的 “平均 KL 散度” 提升约 3.8 % 。
- 考虑去掉 unigram 特征，结果表明：
  - 仅仅 5 个因素的 81 个特征能够提升约 1.1 %。
  - unigram 特征能够提升约 2.7 % 。

1.3.4 Order Specificity Feature Set

有的订单定向比较窄。如：


xxxxxxxxxx
4
1
Title: Buy shoes now,
2
Text: Shop at our discount shoe warehouse!
3
Url: shoes.com
4
Terms: {buy shoes, shoes, cheap shoes}.

该订单的竞价词都和 shoes 相关，定向比较狭窄。

而有的订单定向比较宽，如：


xxxxxxxxxx
4
1
Title: Buy [term] now,
2
Text: Shop at our discount warehouse!
3
Url: store.com
4
Terms: {shoes, TVs, grass, paint}

该订单的竞价词不仅包含shoes，还包括 TV、grass 等等。

我们预期：定向越宽的订单，其平均CTR 越低；定向越窄的订单，其平均CTR 越高。

为了考虑捕捉同一个订单内不同广告的联系，论文提出了订单维度特征集 Order Specificity Feature Set 。
- 同一个订单中，去重之后不同竞价词term 的数量：
  $Num(\text{order}_{\text{unique_term}})$
- 同一个订单中，竞价词 term 的类别分布。分布越集中，定向越窄；分布越分散，定向越宽。
  - 利用搜索引擎搜索每个竞价词 term ，并通过文本分类算法对搜索结果进行分类，将每个竞价词term 划分到 74个类别中。
  - 计算每个订单的竞价词term 的类别熵，并将类别熵作为特征。
采用该特征集之后，测试集的 “平均 KL 散度” 提升约 5.5 % 。

1.3.5 Search Data Feature Set

事实上可以通过使用外部数据来构造特征。
如：给定一个竞价词term，可以通维基百科来判断它是否是一个众所周知的词，也可以通过同义词词库来查找其同义词等等。
因此构建外部搜索数据特征集 Search Data Feature Set，其中包括：
- 每个竞价词term，网络上该 term 出现的频率。
  这可以利用搜索引擎的搜索结果中包含该 term 的网页数量来初略估计。
- 每个竞价词term，搜索引擎的query 中出现该term 的频率。
  这可以用近三个月搜索引擎的搜索日志中，query 里出现该 term 的数量来粗略估计。
这两个特征离散化为 20个桶，仔细划分桶边界使得每个桶具有相同数量的广告。
单独采用该特征集之后，测试集的 “平均 KL 散度” 提升约 3.1 % 。但是融合了前面提到的特征之后没有任何改进，这意味着该特征集相比前面的几个特征集是冗余的。

1.3.6 更多特征

当独立的考虑每个feature set 时，测试集的 “平均 KL 散度” 提升效果如下：
- related term ctr feature set：19.67% 。
- ad quality feature set：12.0%。
- unigram features along：10.2%。
- order specificity feature set：8.9%。
- search data feature set ：3.1%。
有几个特征探索方向：
- 可以将广告的竞价词 term 进行聚类，从而提供广告之间的关系。这是从语义上分析竞价词term 的相似性。这组特征称作 Related Term Feature Set 。
- 可以基于用户的 query 来构造特征。
  在完全匹配条件下竞价词和用户搜索词完全相同，但是在更宽松的匹配下竞价词和搜索词可能存在某种更广义的关联。此时了解搜索词的内容有助于预测广告的点击率。
  因此可以基于用户的搜索词 query term 来构建特征，如： query term 和 bid term 相似度、 query term 的单词数、query term 出现在广告标题/广告正文/落地页的频次。
- 可以将落地页的静态排名和动态排名信息加入特征。如：用户访问落地页或者域名的频率、用户在落地页停留的时间、用户在落地页是否点击回退等等。
一个推荐的做法是：在模型中包含尽可能多的特征。这带来两个好处：
- 更多的特征带来更多的信息，从而帮助模型对于广告点击率预测的更准。
- 更多的特征带来一定的冗余度，可以防止对抗攻击。
  广告主有动力来攻击特征来欺骗模型，从而提升广告的 pCTR ，使得他的广告每次排名都靠前。
  假设模型只有一个特征，该特征是 ”竞价词是否出现在标题“ 。广告主可以刻意将竞价词放置到广告标题，从而骗取较高的 pCTR 。
  一旦模型有多个特征，那么广告主必须同时攻击这些特征才能够欺骗模型。这种难度要大得多。

1.4 特征重要性

由于模型采用逻辑回归，因此可以直观的通过模型权重看到哪些特征具有最高权重、哪些特征具有最低权重。
模型的top 10 和 bottom 10 权重对应的特征如下：
特征的权重不一定直接表示其重要性，因为特征之间不是独立的。
$\text{word_len}$ $\text{text_len}$ $\text{word_count}$ $\text{text_len}$ $\text{word_count}$ 有一个较大的负权重。
$\text{word_len} = \text{text_len}/ \text{word_count}$ $\text{word_len}$ $\text{text_len}$ $\text{word_len}$ $\text{word_count}$ 负相关。
在 unigram features 中，top 10 和 bottom 10 权重对应的特征如下。
可以看到：
- 排在前面的是更为成熟established 的实体词，如 official,direct,latest,version 。
- 排在后面的是更为吸引眼球的实体词，如 quotes, trial, deals, gift, compare 。
从经验上看：用户似乎更愿意点击声誉更好的、更成熟的广告，而不愿意点击免费试用、优惠类的广告。

1.5 曝光量

假设模型能准确预估广告的点击率，一个问题是：广告经过多少次曝光之后，观察到的点击率和预估的点击率接近。
定义观察到的点击率为：
$\text{CTR}^* = \frac{ \text{click}}{\text{expo}}$
定义预测的点击率为：
$\hat p = \frac{\alpha p_0+ \text{click}}{\alpha + \text{expo}}$
其中：
- $\text{expo}$ $\text{click}$ $p_0$ CTR $\alpha$ 是先验曝光次数。
- $p_0$ pCTR $\alpha$ 是一个超参数。
- $\hat p$ 是结合了模型预估的 pCTR 和广告已经产生的曝光、点击之后，预测的点击率。
  模型预测的 pCTR 没有考虑广告当前的曝光、点击，因此需要修正。
定义期望绝对损失 expected absolute error:EAE：
$\mathbb E[\text{err}\mid \text{expo} ] = \sum_{\text{click}=1}^\text{expo} p(\text{click}\mid \text{expo} )\times |\hat p -\text{CTR}^*|$
$p(\text{click}\mid \text{expo} )$ 表示给定曝光的条件下，点击click 次的概率。它通过统计其它广告得到。
EAE $\hat p$ 和 CTR 的绝对误差。这和模型优化目标平均KL 散度不同。
baseline 和 LR 模型的 EAE 结果如下所示。可以看到：
- 在广告的曝光量超过 100时，baseline 和 LR 模型的 EAE 几乎相同。
- 在广告的曝光量小于 50 时，LR 模型的EAE 更低。
因此模型对于曝光量100以内的广告具有明显优势。这也是前面预处理将 100次曝光作为阈值截断的原因。
对于百万级别广告的广告系统，如果在广告曝光的前100次期间对广告的CTR 预估不准，则导致这些广告以错误的顺序展示，从而导致收入减少和用户体验下降。
预处理选择 100 次曝光作为截断阈值，是希望样本的观察 CTR 具有合理的置信水平。
事实上有一些广告系统更关注于曝光量更大的广告，希望对这些广告能够预测更准确。更大曝光量意味着label 中更少的噪音，模型会学习得效果更好。
但是这也意味着广告样本不包含那些被系统判定为低价值的广告，因为系统没有给这些低价值广告足够多的曝光机会。
当曝光阈值提升到 1000次时，模型效果如下。可以看到：曝光量超过1000的广告比曝光量100的广告，模型预测效果（以测试集的平均KL 散度为指标）提升了 40%左右（ (41.88-29.47)/29.47 ）。

二、POLY2 模型[2010]

LR 模型只考虑特征之间的线性关系，而POLY2 模型考虑了特征之间的非线性关系。
- 捕获非线性特征的一个常用方法是采用核技巧，如高斯核RBF，将原始特征映射到一个更高维空间。在这个高维空间模型是线性可分的，即：只需要考虑新特征之间的线性关系。
  但是核技巧存在计算量大、内存需求大的问题。
- 论文 《Training and Testing Low-degree Polynomial Data Mappings via Linear SVM》 提出多项式映射 polynomially mapping 数据的方式来提供非线性特征，在达到接近核技巧效果的情况下大幅度降低内存和计算量。
$n$ $\mathbf{\vec x} = [x_1,\cdots,x_n]^T$ 。
$K(\mathbf{\vec x}_i,\mathbf{\vec x}_j) = (\gamma \mathbf{\vec x}_i\cdot \mathbf{\vec x}_j +r)^d$ $\gamma,r$ $d$ 为多项式的度degree 。
根据定义，多项式核等于样本在高维空间向量的内积：
$K(\mathbf{\vec x}_i,\mathbf{\vec x}_j) = \phi(\mathbf{\vec x}_i) \cdot \phi(\mathbf{\vec x}_j)$
$\phi$ 是映射函数。
$d=2$ 时，有：
$\phi(\mathbf{\vec x}) = [1,\sqrt{2\gamma}x_1,\cdots,\sqrt{2\gamma}x_n,\gamma x_1^2,\cdots,\gamma x_n^2,\sqrt2 \gamma x_1x_2,\cdots,\sqrt 2 \gamma x_{n-1}x_n ]^T$
$\sqrt 2$ $\phi(\mathbf{\vec x}_i) \cdot \phi(\mathbf{\vec x}_j)$ 的表达更简洁。
如果不用核技巧，仅仅考虑使用一个多项式进行特征映射，则我们得到：
$\phi(\mathbf{\vec x}) = [1,x_1,\cdots,x_n,x_1^2,\cdots,x_n^2,x_1x_2,\cdots,x_{n-1}x_n]^T$
结合LR 模型，则得到 POLY2 模型：
$z(\mathbf{\vec x}) = w_0 + \sum_{i=1}^nw_i\times x_i + \sum_{i=1}^n\sum_{j=i}^n w_{i,j}\times x_i\times x_j\\ y(\mathbf{\vec x}) = \frac{1}{1+\exp(-z(\mathbf{\vec x}))}$
$\frac{n\times (n-1)}{2}$ 个。
POLY2 模型的优缺点：
- 优点：除了线性特征之外，还能够通过特征组合自动捕获二阶特征交叉产生的非线性特征。
- 缺点：
  - 参数太多导致计算量和内存需求发生爆炸性增长。
    如计算广告场景中，原始样本特征可能达到上万甚至百万级别，则特征的交叉组合达到上亿甚至上万亿。
  - 数据稀疏导致二次项参数训练困难，非常容易过拟合。
    $w_{i,j}$ $x_i,x_j$ $w_{i,j}$ 的样本明显不足，很容易发生过拟合。

三、FM模型[2011]

推荐系统中的评级预测rating prediction 主要依赖于以下信息：谁who（哪个用户）对什么what（哪个 item，如电影、新闻、商品）如何how评级。有很多方法可以考虑关于 who （关于用户的人口统计信息，如年龄、性别、职业）、what （关于item 属性的信息，如电影类型、产品描述文本的关键词）的附加数据。
除了有关评级事件rating event 中涉及的实体的此类数据之外，还可能存在有关评级事件发生当前情况的信息，例如当前位置location、时间、周边的人、用户当前心情等等。这些场景信息通常称作上下文 context 。因为从决策心理学知道一个人的环境和情绪确实会影响他们的行为，所以在推荐系统中利用上下文信息是可取的。上下文感知评级预测context-aware rating prediction 依赖于谁who在何种上下文context下如何how评价什么what的信息。
经典的推荐系统方法不考虑上下文信息。一些方法执行数据的预处理 pre-processing或后处理post-processing，使得标准方法具有上下文感知能力。虽然这种临时解决方案可能在实践中起作用，但是它们的缺点是过程中的所有步骤都需要监督和微调。
将各种输入数据统一到一个模型中的方法在这方面更为实用，理论上也更为优雅。目前，在预测准确性方面最灵活和最强的方法是 Multiverse Recommendation ，它依赖于 Tuckercategorical context $O(d^K)$ $d$ $K$ 是所涉及变量的数量。
在论文 《Fast Context-aware Recommendations with Factorization Machines》 中，作者提出了一种基于分解机 Factorization Machine: FM 的上下文感知评级预测器。FM 包括并可以模拟推荐系统中最成功的方法，包括句子分解 matrix factorizion: MF、SVD++、PITF 。
- 作者展示了 FM 如何应用于各种上下文字段，包括离散型categorical 字段、离散集合set categorical 字段、实值real-valued 字段。相比之下， Multiverse Recommendation 模型只适合于离散型 categorical 上下文变量。
- FM $d$ $K$ $O(dK)$ Multiverse Recommendation $P(d^K)$ $d$ 上是多项式的。
- 为了学习 FM 模型的参数，论文提出了一种基于交替最小二乘法 alternating least squares: ALS 的新算法。新算法在给定其它参数的情况下找到一个参数的最优解，并且在几次迭代之后找到所有参数联合最优解。
  stochastic gradient descent: SGD $O(|\mathbb S|dK)$ $|\mathbb S|$ 为训练样本的数量。
  和 SGD 相比，新算法的主要优点是无需确定学习率。这在实践中非常重要，因为 SGD 学习的质量在很大程度上取决于良好的学习率，因此必须进行代价昂贵的搜索。这对于 ALS 来讲不是必需的。
- 最后，论文的实验表明：上下文感知 FM 可以捕获上下文信息并提高预测准确性。此外 FM 在预测质量和运行时间方面都优于 state-of-the-art 的方法 Multiverse Recommendation 。

3.1 相关工作

推荐系统的大多数研究都集中在仅分析 user-item 交互的上下文无关方法上。在这里，矩阵分解matrix factorization: MF方法非常流行，因为它们通常优于传统的 knn 方法。
也有研究将用户属性或 item 属性等元数据结合到预测中，从而扩展了矩阵分解模型。然而，如果存在足够的反馈数据，元数据对评分预测的强 baseline 方法通常只有很少或者没有改善。这种用户属性/item 属性和上下文之间的区别在于：属性仅仅被附加到 item 或者用户（例如，给电影附加一个流派的属性），而上下文被附加到整个评级事件（如，当评级发生时用户当时的心情）。
和关于标准推荐系统的大量文献相比，上下文感知推荐系统的研究很少。最基本的方法是上下文预过滤pre-filtering 和后过滤 post-filtering，其中应用标准的上下文无关推荐系统，并在应用推荐器recommender 之前基于感兴趣的上下文对数据进行预处理、或者对结果进行后处理。更复杂的方法是同时使用所有上下文和 user-item 信息来进行预测。
也有人建议将上下文视为动态的用户特征，即可以动态变化。另外有一些关于 item 预测的上下文感知推荐系统的研究，将推荐视为一个排序任务，而本文将推荐视为回归任务。
Multiverse Recommendation 基于Tuckeritem $\mathbf B$ $K$ $\mathbf V^{(k)}$ ：
$\hat y =f(u,i,c_3,\cdots,c_K) = \sum_{l_1=1}^{d_1}\cdots\sum_{l_K=1}^{d_K}b_{l_1,\cdots,l_K} \times\left[ v_{u,l_1}^{(U)}\times v_{i,l_2}^{(I)}\times \prod_{k=3}^Kv_{c_k,l_k}^{(C_k)}\right]$
其中：
$\mathbf B\in \mathbb R^{d_1\times d_2\times\cdots\times d_K}\\ \mathbf V^{(U)} \in \mathbb R^{M \times d_1},\mathbf V^{(I)} \in \mathbb R^{N \times d_2},\mathbf V^{(C_k)} \in \mathbb R^{|\mathbb C_k| \times d_k}$
这种方式存在三个问题：
- $d$ $O(d^K)$ $K$ 增加，则计算复杂度指数型增长。
- 仅能对离散型 categorical 上下文特征建模：无法处理数值型特征、离散集合型 categorical set 特征。
- 交叉特征高度稀疏：这里执行的是 K 路特征交叉（前面的 POLY2 模型是两路特征交叉），由于真实应用场景中单个特征本身就已经很稀疏，K 路特征交叉使得数据更加稀疏，难以准确的预估模型参数。
Attribute-aware Recommendation：与通用上下文感知方法的工作对比，对属性感知或专用推荐系统的研究要多得多。有一些工作可以处理用户属性和 item 属性的矩阵分解模型的扩展，还有一些关于考虑时间效应的工作。然而，所有这些方法都是为特定问题设计的，无法处理我们在本工作中研究的上下文感知推荐的通用设置。
当然，对于特定的和重要的问题（如时间感知推荐或属性感知推荐），专用模型的研究是有益的。但是另一方面，研究上下文感知的通用方法也很重要，因为它们提供了最大的灵活性，并且可以作为专用模型的强 baseline 。
Alternating Least Square Optimization：对于矩阵分解模型，Bell 和 Koren 提出了一种交替优化所有 user factor 和所有 item factor 的 ALS 方法。由于所有user/itemfactor matrix $O(d^3)$ 。标准 ALS 的这种复杂度问题是 SGD 方法在推荐系统文献中比 ALS 更受欢迎的原因。
Pilaszy 等人提出一个接一个地优化每个user/item 中的 factorALS $O(d)$ ，因为避免了矩阵求逆。一次优化一个factor 的思路与我们将 ALS 算法应用于FM 的思路相同。
这两种方法仅适用于矩阵分解，因此无法处理任何上下文，例如我们提出的对所有交互进行建模的 FM 中的上下文。此外，我们的 ALS 算法还学习了全局bias 和基本的 1-way 效应。

3.2 模型

FM 模型是一个通用模型，它包含并可以模拟几个最成功的推荐系统，其中包括矩阵分解 matrix factorization: MF、SVD++、PITF。我们首先简要概述了 FM 模型，然后详细展示了如何将其应用于上下文感知数据，以及在 FM 中使用这种上下文感知数据会发生什么。最后我们提出了一种新的快速 alternating least square: ALS 算法，和 SGD 算法相比它更容易应用，因为它不需要学习率。

3.2.1 FM 模型

$\mathbb U=\{u_1,u_2,\cdots,u_M\}$ $\mathbb I = \{i_1,i_2,\cdots,i_N\}$ ，模型是一个评分函数：
$f:\mathbb U\times \mathbb I\rightarrow \mathbb R$
$y=f(u,i)$ $u$ $i$ 的评分。
$\mathbb S \in \mathbb U\times \mathbb I, \forall (u,i)\in \mathbb S,\tilde y=f(u,i)$ 。目标是求解剩余用户在剩余物品上的评分：
$\hat y = f(u,i) ,\;\forall(u,i) \in \complement_\mathbb S$
$\complement_\mathbb S$ $\mathbb S$ 的补集。
- 通常评分问题是一个回归问题，模型预测结果是评分的大小。此时损失函数采用MAE/MSE 等等。
  也可以将其作为一个分类问题，模型预测结果是各评级的概率。此时损失函数是交叉熵。
- 当评分只有 0 和 1 时，这表示用户对商品 “喜欢/不喜欢”，或者 “点击/不点击”。这就是典型的点击率预估问题。
事实上除了已知部分用户在部分物品上的评分之外，通常还能够知道一些有助于影响评分的额外信息。如：用户画像、用户行为序列等等。这些信息称作上下文 context 。
$c \in \mathbb C$ $\mathbb C$ $\mathbb C_3,\cdots,\mathbb C_K$ ，则模型为：
$f:\mathbb U\times \mathbb I \times \mathbb C_3\times\cdots\times\mathbb C_K\rightarrow \mathbb R$
3 $u$ $i$ 也是上下文的一种。
如下图所示为评分矩阵，其中：
$\mathbb U = \{\text{A},\text{B},\text{C}\},\quad \mathbb I = \{\text{TI},\text{NH},\text{SW},\text{ST}\}\\ \mathbb C_3 = \{\text{S},\text{N},\text{H}\},\quad \mathbb C_4 = \{\text{A},\text{B},\text{C}\}\\ y\in \{1,2,3,4,5\}$
所有离散特征都经过one-hot 特征转换。
上下文特征 context 类似属性 property 特征，它和属性特征的区别在于：
- 属性特征是作用到整个用户（用户属性）或者整个物品（物品属性），其粒度是用户级别或者物品级别。
  如：无论用户 “张三” 在在评分矩阵中出现多少次，其性别属性不会发生改变。
- 上下文特征是作用到用户的单个评分事件上，粒度是事件级别，包含的评分信息更充足。
  如：用户 ”张三“ 在评价某个电影之前已经看过的电影，该属性会动态改变。
事实上属性特征也称作静态画像，上下文特征也称作动态画像。业界主流的做法是：融合静态画像和动态画像。
另外，业界的经验表明：动态画像对于效果的提升远远超出静态画像。
和 POLY2 相同FM 也是对二路特征交叉进行建模，但是FM 的参数要比 POLY2 少得多。
将样本重写为：
$\mathbf{\vec x} =(x_1,x_2,x_3,\cdots,x_K)^T =(u,i,c_3,\cdots,c_K)^T$
则 FM 模型为：
$\hat y(\mathbf{\vec x}) = w_0 + \sum_{i=1}^K w_i\times x_i + \sum_{i=1}^K\sum_{j=i+1}^K \hat w_{i,j}\times x_i\times x_j$
$\hat w_{i,j}$ 是交叉特征的参数，它由一组参数定义：
$\hat w_{i,j} = <\mathbf{\vec v}_i,\mathbf{\vec v}_j> = \sum_{l=1}^d v_{i,l}\times v_{j,l}$
即：
$\hat{\mathbf W} = \begin{bmatrix} \hat w_{1,1}& \hat w_{1,2}&\cdots&\hat w_{1,K}\\ \hat w_{2,1}& \hat w_{2,2}&\cdots&\hat w_{2,K}\\ \vdots & \vdots&\ddots&\vdots\\ \hat w_{K,1}& \hat w_{K,2}&\cdots&\hat w_{K,K}\\ \end{bmatrix} = \mathbf V^T\mathbf V = \begin{bmatrix} \mathbf{\vec v}_1^T\\ \mathbf{\vec v}_2^T\\ \vdots\\ \mathbf{\vec v}_K^T \end{bmatrix} \begin{bmatrix}\mathbf{\vec v}_1&\mathbf{\vec v}_2&\cdots& \mathbf{\vec v}_K \end{bmatrix}$
模型待求解的参数为：
$w_0\in \mathbb R,\mathbf{\vec w}\in \mathbb R^K\\ \mathbf V = (\mathbf{\vec v}_1,\cdots,\mathbf{\vec v}_K) \in \mathbb R^{d\times K}$
其中：
- $w_0$ 表示全局偏差。
- $w_i$ $i$ 个特征和目标之间的关系。
- $\hat w_{i,j}$ $(i,j)$ 二路交叉特征和目标之间的关系。
- $\mathbf{\vec v}_i$ $i$ representation vector $\mathbf V$ $i$ 列。
FM $O(K\times K\times d) = O(K^2d)$ $O(Kd)$ ：
$\sum_{i=1}^K\sum_{j=i+1}^K \hat w_{i,j}\times x_i\times x_j = \sum_{i=1}^K\sum_{j=i+1}^K\sum_{l=1}^d v_{i,l}\times v_{j,l}\times x_i\times x_j\\ = \sum_{l=1}^d \left(\sum_{i=1}^K\sum_{j=i+1}^K (v_{i,l}\times x_i) \times (v_{j,l}\times x_j)\right)\\ = \sum_{l=1}^d \frac 12\left(\left(\sum_{i=1}^Kv_{i,l}\times x_i\right)^2 - \sum_{i=1}^K v_{i,l}^2\times x_{i}^2\right)$
因此有：
$\hat y(\mathbf{\vec x}) = w_0 + \sum_{i=1}^K w_i\times x_i +\frac 12 \sum_{l=1}^d\left(\left(\sum_{i=1}^Kv_{i,l}\times x_i\right)^2 - \sum_{i=1}^K v_{i,l}^2\times x_{i}^2\right)$
$O(Kd)$ 。
将 FMFM $<\mathbf{\vec v}_i,\mathbf{\vec v}_u>$ 。此外，FM 模型还包含了所有上下文变量的所有 pair 对的交互。这表明 FM 自动包含了矩阵分解模型。
FM 模型可以用于求解分类问题（预测各评级的概率），也可以用于求解回归问题（预测各评分大小）。
- 对于回归问题，其损失函数为MSE 均方误差：
  $\mathcal L = \sum_{(\mathbf{\vec x},y)\in \mathbb S} \left(\hat y(\mathbf{\vec x}) - y\right)^2 + \sum_{\theta\in \mathbf \Theta} \lambda_{\theta} \times \theta^2$
- 对于二分类问题，其损失函数为交叉熵：
  $\phi (\mathbf{\vec x}) = w_0 + \sum_{i=1}^K w_i\times x_i +\frac 12 \sum_{l=1}^d\left(\left(\sum_{i=1}^Kv_{i,l}\times x_i\right)^2 - \sum_{i=1}^K v_{i,l}^2\times x_{i}^2\right)\\ p(\hat y = y\mid \mathbf{\vec x}) = \frac{1}{1+\exp({-y\phi(\mathbf{\vec x})})} \\ \mathcal L = \left(- \sum_{(\mathbf{\vec x},y)\in \mathbb S} \log p(\hat y = y\mid \mathbf{\vec x})\right) + \sum_{\theta\in \mathbf \Theta} \lambda_{\theta} \times \theta^2$
  其中：
  - $y\in \{-1,1 \}$ 一共两个等级。
  - $p(\hat y=y\mid \mathbf{\vec x})$ $\mathbf{\vec x}$ $y$ 的概率，满足：
$p(\hat y = 1 \mid \mathbf{\vec x}) = \frac{1}{1+\exp({-\phi(\mathbf{\vec x})})} \\ p(\hat y = -1 \mid \mathbf{\vec x}) = \frac{1}{1+\exp({\phi(\mathbf{\vec x})})}$
$\mathbf \Theta = \{w_0,\mathbf{\vec w}, \mathbf V\}$ $\lambda_\theta$ $\theta$ 的正则化系数，它是模型的超参数。
可以针对每个参数配置一个正则化系数，但是选择合适的值需要进行大量的超参数选择。论文推荐进行统一配置：
- $w_0$ $\lambda_{w_0} = 0$ ，这表示不需要对全局偏差进行正则化。
- $w_i$ $\lambda_w$ 。
- $v_{i,l}$ $\lambda_v$ 。
FM 模型可以处理不同类型的特征：
- 离散型特征 categorical：FM 对离散型特征执行 one-hot 编码。
  如，性别特征：“男” 编码为 (0,1)，“女” 编码为 (1,0) 。
- 离散集合特征 categorical set：FM 对离散集合特征执行类似 one-hot 的形式，但是执行样本级别的归一化。
  如，看过的历史电影。假设电影集合为：“速度激情9，战狼，泰囧，流浪地球”。如果一个人看过 “战狼，泰囧，流浪地球”，则编码为 (0,0.33333,0.33333,0.33333) 。
- 数值型特征 real valued：FM直接使用数值型特征，不做任何编码转换。
FM 的优势：
- 给定特征 representation 向量的维度时，预测期间计算复杂度是线性的。
- 在交叉特征高度稀疏的情况下，参数仍然能够估计。
  因为交叉特征的参数不仅仅依赖于这个交叉特征，还依赖于所有相关的交叉特征。这相当于增强了有效的学习数据。
- 能够泛化到未被观察到的交叉特征。
  设交叉特征 “看过电影 A且年龄等于20” 从未在训练集中出现，但出现了 “看过电影 A” 相关的交叉特征、以及 “年龄等于20” 相关的交叉特征。
  于是可以从这些交叉特征中分别学习 “看过电影 A” 的 representation 、 “年龄等于20”的 representation，最终泛化到这个未被观察到的交叉特征。

3.2.2 ALS 优化算法

a. 最优化解

FM 的目标函数最优化可以直接采用随机梯度下降 SGD 算法求解，但是采用 SGD 有个严重的问题：需要选择一个合适的学习率。
- 学习率必须足够大，从而使得 SGD 能够尽快的收敛。学习率太小则收敛速度太慢。
- 学习率必须足够小，从而使得梯度下降的方向尽可能朝着极小值的方向。
  由于 SGD 计算的梯度是真实梯度的估计值，引入了噪音。较大的学习率会放大噪音的影响，使得前进的方向不再是极小值的方向。
我们提出了一种新的交替最小二乘 alternating least square:ALS 算法来求解 FM 目标函数的最优化问题。与 SGD 相比ALS 优点在于无需设定学习率，因此调参过程更简单。
根据定义：
$\hat y(\mathbf{\vec x};\mathbf \Theta) = w_0 + \sum_{i=1}^K w_i\times x_i +\frac 12 \sum_{l=1}^d\left(\left(\sum_{i=1}^Kv_{i,l}\times x_i\right)^2 - \sum_{i=1}^K v_{i,l}^2\times x_{i}^2\right)$
$\theta \in \mathbf \Theta = \{w_0,\mathbf{\vec w}, \mathbf V\}$ $\hat y$ $\theta$ 的线性部分和偏置部分：
$\hat y(\mathbf{\vec x};\mathbf \Theta) = h_{\theta}(\mathbf{\vec x}) \times \theta +g_\theta(\mathbf{\vec x})$
$g_\theta(\mathbf{\vec x}), h_\theta(\mathbf{\vec x})$ $\theta$ 无关。如：
- $w_0$ 有：
  $h_{w_0} = 1\\ g_{w_0} = \sum_{i=1}^K w_i\times x_i +\frac 12 \sum_{l=1}^d\left(\left(\sum_{i=1}^Kv_{i,l}\times x_i\right)^2 - \sum_{i=1}^K v_{i,l}^2\times x_{i}^2\right)$
- $w_i,i=1,2\cdots,K$ 有：
  $h_{w_i} = x_i\\ g_{w_i} = w_0 + \sum_{j=1,j\ne i}^K w_j\times x_j +\frac 12 \sum_{l=1}^d\left(\left(\sum_{j=1}^Kv_{j,l}\times x_j\right)^2 - \sum_{j=1}^K v_{j,l}^2\times x_{j}^2\right)$
- $v_{i,l}, i=1,2,\cdots,K,l=1,2,\cdots,d$ 有：
  $h_{v_{i,l}} = \sum_{j=1,j\ne i}^K v_{j,l} \times x_j\times x_i\\ g_{v_{i,l}} = w_0 + \sum_{j=1}^K w_j\times x_j +\sum_{i^\prime=1}^K\sum_{j^\prime=i^\prime+1}^K\sum_{\substack{l^\prime=1,\\ l^\prime\ne l \;\&\; i^\prime \ne i \;\&\; j^\prime \ne i }}^d v_{i^\prime,l^\prime}\times v_{j^\prime,l^\prime}\times x_{i^\prime}\times x_{j^\prime}$
因此有：
$\frac{\partial \hat y(\mathbf{\vec x};\mathbf \Theta)}{\partial \theta} = h_\theta(\mathbf{\vec x})$
考虑均方误差损失函数：
$\mathcal L = \sum_{(\mathbf{\vec x},y)\in \mathbb S} \left(\hat y(\mathbf{\vec x};\mathbf \Theta) - y\right)^2 + \sum_{\theta\in \mathbf \Theta} \lambda_{\theta} \times \theta^2$
最小值点的偏导数为 0 ，有：
$\frac{\partial L}{\partial \theta} = 2\sum_{(\mathbf{\vec x},y)\in \mathbb S} \left(\hat y(\mathbf{\vec x};\mathbf \Theta) - y\right)\times \frac{\partial \hat y(\mathbf{\vec x};\mathbf \Theta)}{\partial \theta} + 2\times \lambda_{\theta} \times \theta = 0$
则有：
$\theta = - \frac{\sum_{(\mathbf{\vec x},y)\in \mathbb S}(g_\theta(\mathbf{\vec x})-y)\times h_\theta(\mathbf{\vec x}) }{\left(\sum_{(\mathbf{\vec x},y)\in \mathbb S} h^2_\theta(\mathbf{\vec x})\right)+\lambda_\theta }$
ALS $\theta \in \mathbf \Theta = \{w_0,\mathbf{\vec w}, \mathbf V\}$ 即可得到模型的最优解。
- $w_0,\mathbf{\vec w}$ $\mathbf V$ 0 $\sigma$ 的正太分布随机初始化。
- 每一轮迭代时：
  - $w_0,\mathbf{\vec w}$ ，因为相对于二阶交叉的高阶特征，低阶特征有更多的数据来估计其参数，因此参数估计更可靠。
  - $\mathbf V$ 。这里按照维度优先的准确来估计：先估计所有 representation 向量的第 1 维度，然后是第 2 维，... 最后是第 d 维。
    这是为了计算优化的考量。

b. 计算优化

ALS $g_\theta(\mathbf{\vec x})$ $h_\theta(\mathbf{\vec x})$ 。
$g_\theta(\mathbf{\vec x})$ $h_\theta(\mathbf{\vec x})$ 的计算复杂度为：
- $h_{w_0}(\mathbf{\vec x})$ $O(1)$ $g_{w_0}(\mathbf{\vec x})$ $O(Kd)$ 。
- $h_{w_i}(\mathbf{\vec x})$ $O(1)$ $g_{w_i}(\mathbf{\vec x})$ $O(Kd)$ 。
- $h_{v_{i,l}}(\mathbf{\vec x})$ $O(K)$ $g_{v_{i,l}}(\mathbf{\vec x})$ $O(K^2d)$ 。
$\theta$ $O(|\mathbb S|\times K^2\times d)$ 。
$\theta$ $O(|\mathbb S|\times K^2\times d)$ $O(|\mathbb S|\times \bar K\times d)$ $\bar K$ 表示平均非零特征的数量：
- $e$ $(g_\theta(\mathbf{\vec x})-y)$ 的计算代价。
- $q$ $h_\theta$ 的计算代价。
- $\mathbb S$ 的稀疏性降低整体计算代价。
$e$ ：
定义误差项：
$e(\mathbf{\vec x},y;\mathbf \Theta) := \hat y(\mathbf{\vec x}; \mathbf \Theta) - y$
$\hat y(\mathbf{\vec x};\mathbf \Theta) = h_{\theta}(\mathbf{\vec x}) \times \theta +g_\theta(\mathbf{\vec x})$ ，则有：
$g_\theta(\mathbf{\vec x})-y = e(\mathbf{\vec x},y;\mathbf \Theta) - \theta\times h_\theta(\mathbf{\vec x})$
$e(\mathbf{\vec x},y;\mathbf \Theta)$ $(g_\theta(\mathbf{\vec x})-y)$ 的计算复杂度也会降低。
- 首先对每个样本，计算其初始误差：
  $\mathbf{\vec e} = \left(e(\mathbf{\vec x}_1,y_1;\mathbf \Theta ),\cdots,e(\mathbf{\vec x}_{|\mathbb S|},y_{|\mathbb S|};\mathbf \Theta )\right)^T \in \mathbb R^{|\mathbb S|}$
  $\hat y$ $O(K\times d)$ $\mathbf{\vec e}$ $O(|\mathbb S|\times K\times d)$ 。
- $\theta$ $\theta^*$ 时，重新计算误差：
  $e(\mathbf{\vec x},y;\mathbf \Theta^*) = \hat y(\mathbf{\vec x}; \mathbf \Theta^*) - y = h_{\theta}(\mathbf{\vec x}) \times \theta^* +g_\theta(\mathbf{\vec x}) - y\\ = h_{\theta}(\mathbf{\vec x}) \times \theta+g_\theta(\mathbf{\vec x}) - y + h_{\theta}(\mathbf{\vec x})(\theta^*-\theta)\\ = e(\mathbf{\vec x},y;\mathbf \Theta) + h_{\theta}(\mathbf{\vec x})(\theta^*-\theta)$
  $h_\theta(\mathbf{\vec x})$ $O(1)$ ）。
$q$ 值：
$h_\theta(\mathbf{\vec x})$ $h_{w_0}(\mathbf{\vec x}),h_{w_i}(\mathbf{\vec x})$ $O(1)$ $h_{v_{i,l}}(\mathbf{\vec x})$ 的计算复杂度。
$h_{v_{i,l}} (\mathbf{\vec x})$ ，有：
$h_{v_{i,l}}(\mathbf{\vec x}) = \sum_{j=1,j\ne i}^K v_{j,l} \times x_j\times x_i = x_i\times \left[\sum_{j=1 }^K v_{j,l} \times x_j\right] - v_{i,l}\times x_i^2$
定义：
$q(\mathbf{\vec x},l;\mathbf\Theta) := \sum_{j=1}^Kv_{j,l}\times x_j$
$q(\mathbf{\vec x},l;\mathbf\Theta)$ $h_{v_{i,l}}(\mathbf{\vec x})$ 的计算复杂度也会降低。
- representation $q$ 值：
  $\mathbf Q= \begin{bmatrix} q(\mathbf{\vec x}_1,1;\mathbf\Theta)&q(\mathbf{\vec x}_1,2;\mathbf\Theta)&\cdots& q(\mathbf{\vec x}_1,d;\mathbf\Theta)\\ q(\mathbf{\vec x}_2,1;\mathbf\Theta)&q(\mathbf{\vec x}_2,2;\mathbf\Theta)&\cdots& q(\mathbf{\vec x}_2,d;\mathbf\Theta)\\ \vdots&\vdots&\ddots&\vdots\\ q(\mathbf{\vec x}_{|\mathbb S|},1;\mathbf\Theta)&q(\mathbf{\vec x}_{|\mathbb S|},2;\mathbf\Theta)&\cdots& q(\mathbf{\vec x}_{|\mathbb S|},d;\mathbf\Theta) \end{bmatrix}\in \mathbb R^{|\mathbb S|\times d}$
  $O(|\mathbb S|\times K\times d)$ 。
- $v_{j,l}$ $v_{j,l}^*$ $q$ 值：
  $q(\mathbf{\vec x},l;\mathbf\Theta ^*)= q(\mathbf{\vec x},l;\mathbf\Theta) +(v_{j,l}^* - v_{j,l})\times x_l$
  $O(1)$ 。
- $q(\mathbf{\vec x},l;\mathbf\Theta)$ ，则有：
  $h_{v_{i,l}}(\mathbf{\vec x}) = q(\mathbf{\vec x},l;\mathbf\Theta) - v_{i,l}\times x_i^2$
  $O(1)$ 。
$\mathbb S$ 的稀疏性：
根据：
$\theta = - \frac{\sum_{(\mathbf{\vec x},y)\in \mathbb S}(g_\theta(\mathbf{\vec x})-y)\times h_\theta(\mathbf{\vec x}) }{\left(\sum_{(\mathbf{\vec x},y)\in \mathbb S} h^2_\theta(\mathbf{\vec x})\right)+\lambda_\theta }$
- $w_0$ $O(|\mathbb S|\times K)$
  $w_0\leftarrow \frac{\sum_{(\mathbf{\vec x},y)\in \mathbb S}\left[e(\mathbf{\vec x},y;\mathbf \Theta)-w_0\right] }{|\mathbb S|+\lambda_{w_0} }$
- $w_i,v_{i,l}$ $\mathbb S$ $h_\theta(\mathbf{\vec x}) \ne 0$ $x_i \ne 0$ 的样本。
  $O(|\mathbb S|\times \bar K\times d)$ $\bar K$ 表示平均非零特征的数量。
ALS 优化算法：
- 输入：
  - $\mathbb S$
  - $\mathbf V$ $\sigma$
- $w_0,\mathbf{\vec w},\mathbf V$
- 算法步骤：
  - 参数初始化：
    $w_0 \leftarrow 0\\ w_i \leftarrow 0,i=1,2,\cdots,K\\ v_{i,l} \leftarrow \mathcal N(0,\sigma),i=1,\cdots,K;l=1,\cdots,d\\$
  - $\mathbf{\vec e},\mathbf Q$ ：
    $e(\mathbf{\vec x},y;\mathbf \Theta) \leftarrow \hat y(\mathbf{\vec x},y)-y,\quad (\mathbf{\vec x},y)\in \mathbb S\\ q(\mathbf{\vec x},l;\mathbf\Theta) \leftarrow \sum_{i=1}^K v_{i,l}\times x_i,\quad (\mathbf{\vec x},y)\in \mathbb S,l=1,2,\cdots,d$
  - 迭代直至目标函数收敛或者达到指定步数，每一轮迭代过程为：
    - $w_0$ ：
      $w_0^* \leftarrow - \frac{\sum_{(\mathbf{\vec x},y)\in \mathbb S}\left[e(\mathbf{\vec x},y;\mathbf \Theta)-w_0\right] }{|\mathbb S|+\lambda_{w_0} }\\ e(\mathbf{\vec x},y;\mathbf \Theta^*) \leftarrow e(\mathbf{\vec x},y;\mathbf \Theta ) +(w_0^* -w_0)\\ w_0\leftarrow w_0^*$
    - $w_i,i=1,2\cdots,K$ ：
      $w_i^* = - \frac{\sum_{(\mathbf{\vec x},y)\in \mathbb S}(e(\mathbf{\vec x},y;\mathbf \Theta) - w_i\times x_i)\times x_i}{\left(\sum_{(\mathbf{\vec x},y)\in \mathbb S} x_i^2\right)+\lambda_{w_i} }\\ e(\mathbf{\vec x},y;\mathbf \Theta^*) \leftarrow e(\mathbf{\vec x},y;\mathbf \Theta ) +(w_i^* -w_i)\times x_i\\ w_i\leftarrow w_i^*$
    - $v_{i,l},i=1,\cdots,K;l=1,\cdots,d$ ：
      $l$ $i$ $q(\mathbf{\vec x},l;\mathbf \Theta)$ 。
      $h_{v_{i,l}}(\mathbf{\vec x}) = q(\mathbf{\vec x},l;\mathbf\Theta) - v_{i,l}\times x_i^2\\ v_{i,l}^* = - \frac{\sum_{(\mathbf{\vec x},y)\in \mathbb S}[e(\mathbf{\vec x},y;\mathbf \Theta) -v_{i,l}\times h_{v_{i,l}}(\mathbf{\vec x})]\times h_{v_{i,l}}(\mathbf{\vec x}) }{\left(\sum_{(\mathbf{\vec x},y)\in \mathbb S} h^2_{v_{i,l}}(\mathbf{\vec x})\right)+\lambda_{v_{i,l}} }\\ e(\mathbf{\vec x},y;\mathbf \Theta^*) \leftarrow e(\mathbf{\vec x},y;\mathbf \Theta ) +(v_{i,l}^* -v_{i,l})\times x_i\\ q(\mathbf{\vec x},l;\mathbf \Theta^*) \leftarrow q(\mathbf{\vec x},l;\mathbf \Theta ) +(v_{i,l}^* -v_{i,l})\times x_i\\ v_{i,l} \leftarrow v_{i,l}^*$
.

3.3 实验

在本节中，我们根据实验研究了和 state-of-the-art 的上下文感知方法 Multiverse Recommendation 的对比。此外，我们检查了 SGD 对学习率选择的敏感性，以及我们的 ALS 优化是否可以在没有学习率这个超参数的情况下成功工作。
数据集：
- Food 数据集：包含 212 个用户对 20 个菜单 item 的 6360 个评分（从 1 分到 5 分），其中包含两个上下文变量：第一个上下文变量捕获用户评分的场景是虚拟的 virtual 还是真实的 real（即用户想象自己饿了、还是用户真的饿了）；第二个上下文变量刻画用户的饥饿程度。
- Adom 数据集：包含 1524 个电影评分（从 1 分到 15 分），其中包含五个上下文变量，这些上下文变量关于同伴、工作日、以及其它时间信息。
- Yahoo! Webscope 数据集：包含 221367《Multiverse recommendation: n-dimensional tensor factorization for context-aware collaborative filtering》 $\alpha=\beta\in \{0.1,\cdots,0.9\}$ 一共九个数据集。
baseline 方法：我们将 context-aware FM 和 Multiverse Recommendation 进行比较。注意：Multiverse Recommendation 已经在上述三个数据集上超越了其它上下文感知推荐算法。
我们使用 FM no-context作为上下文无感context-unaware 的 baseline，其中仅使用用户变量和 item 变量生成特征向量，这相当于具有 bias 项的矩阵分解。这是最强的上下文无关推荐算法之一。
FM 使用我们提出的 ALS 算法进行优化，Multiverse Recommendation 使用原始论文中提出的 SGD 算法来学习。
评估方式：我们从每个数据集中删除了 5% 的样本，用作调优超参数以获得最佳 MAE 的验证集。在超参数搜索之后，我们对剩下的 95% 数据集进行 5-fold 交叉验证，即不再使用验证集。我们报告了 5 次实验的平均 RMSE 和 MAE。
所有方法都是 C++ 实现的，并在相同的硬件上运行。我们使用 ALS 优化的 FM 实现、Multiverse Recommendation 实现和数据集生成脚本可以从我们的网站上下载。
ALS vs SGD：我们在 Webscope 数据集上将 SGD 实现的测试误差和我们的 ASL 方法进行了比较，实验结果如下图所示。左图绘制了三种学习率选择的测试误差曲线，右侧的两个图分别显示了在 10 次和100次迭代后不同学习率得到的测试误差曲线（由于 ALS 没有学习率超参数，因此表现为一条水平直线）。可以看到：
- SGD 的优化效果很大程度上取决于学习率和迭代次数。当精心挑选合适的学习率、足够大的迭代次数（根据验证集执行早停策略从而防止过拟合），SGD 可以达到 ALS 的效果。
- ALS 不需要精心的、耗时的搜索合适的学习率，就可以达到很好的效果。
该实验表明：SGD 需要仔细且耗时地搜索学习率，而ALS 不需要这样的搜索因为它没有这个超参数。在预测质量方面SGD 的性能与 ALS 一样好，但是前提是选择了正确的学习率。这使得 ALS 在应用中明显有利。
Multiverse Recommendation $O(d^K)$ $d$ $d$ $K$ FM $d$ $K$ $O(dK)$ 。
webscope $K=4$ $d\in \{1,2,4,8,16,32,64,128\}$ Multiverse Recommendation $d=32$ 。实验结果如下图所示（单位为妙），其中左图为对数尺度。可以看到，实验结果和理论复杂度分析相匹配：
- FM11s $d=128$ ）。
- Multiverse Recommendation $d^4$ $d=16$ 30 $d=32$ 的运行时间大约是 8 小时。
预测质量：最后我们想知道，上下文感知 FM 的灵活性和快速运行时间是否会以较差的预测质量为代价。为此我们比较了 Food、Adom、Webscope 数据集上的预测质量，如下图所示。可以看到：
- 上下文感知 FM 和 Multiverse Recommendation 对 Food 和 Adom 数据集的预测质量相当。
- 上下文感知 FM 和 Multiverse Recommendation 都优于上下文无感方法（相当于矩阵分解模型）。
在第三个实验中，我们考察了人工特征丰富的 Webscope 数据集，其中上下文变量（由 context influence 刻画）对于评分的影响越来越大。结果如下图所示，可以看到：
- 上下文感知的 FM 和 Multiverse Recommendation 都受益于对上下文有更强依赖性的评分。
- 当评分更依赖于上下文时，上下文无关 FM 的预测质量会变差，因为对于上下文无关 FM，上下文是未观测到的，因此它们无法解释这种依赖性。
- 将两种上下文感知方法相互比较，可以看到 FM 始终生成比 Multiverse Recommendation 更好的预测。例如，RMSE 下降 0.10 ~ 0.15 ，而 MAE 下降 0.08 ~ 0.10 。
结论：实验结果表明：
- 上下文感知 FM 能够考虑上下文信息来增强预测。
- 在运行时间方面 FM 是线性的，这使得它们可以应用于大维度的因子、更多上下文变量。相比之下，Multiverse Recommendation 无法处理大维度的因子、也无法处理很多上下文变量。
- FM 在运行时间方面的优势并没有以预测质量为代价，相反：
  - 在稠密数据集（Food 和 Adom）上，上下文感知 FM 和 Multiverse Recommendation 的预测质量相当。
  - 而在稀疏数据集上，上下文感知 FM 的性能优于 Multiverse Recommendation 。
- 最后，ALS 优化的 FM 很容易应用，因为它不像 SGD 那样对学习率进行昂贵的搜索。

四、FFM模型[2016]

click-through rate: CTR $N$ $\left\{\mathbf{\vec x}_i,y_i\right\}_{i=1}^N$ $\mathbf{\vec x }_i\in \mathbb R^K$ $K$ $y_i$ 为 label 。我们通过求解以下最优化问题从而得到逻辑回归模型：
$\min_{\mathbf{\vec w}} \frac{\lambda}{2} \|\mathbf{\vec w}\|_2^2 + \sum_{i=1}^N \log \left(1 +\exp\left(-y_i \phi_\text{LM}\left(\mathbf{\mathbf{\vec w}},\mathbf{\vec x}_i\right)\right)\right)$
$\lambda\ge 0$ $\phi_\text{LM}\left(\mathbf{\vec w},\mathbf{\vec x}\right) =\mathbf{\vec w}\cdot \mathbf{\vec x}$ 。
学习特征交叉效应看起来对 CTR 预估至关重要。这里我们考虑下表中的人造数据集，以便更好地理解特征交叉，其中 + 表示点击量、- 表示不点击量。Gucci 的广告在 Vogue 上的点击率特别高，然而这些信息对于线性模型来说很难学习，因为线性模型分别学习 Gucci 和 Vogue 的两个权重。
为了解决这个问题，已经有两个模型来学习特征交叉效应：
- 第一个模型是二次多项式映射 degree-2 polynomial mapping: Poly2，为每个特征交叉学习专门的权重。
- 第二个模型是分解机 factorization machine: FM，通过将特征交叉分解为两个潜在向量的乘积来学习特征交叉效应。
FM 的一种变体，称作成对交互张量分解 pairwise interaction tensor factorization: PITF ，用于个性化的 tag 推荐。在 2012 年的 KDD Cup 中，Team Opera Solutions 提出了一种称作因子模型 factor model 作为 PITF 的泛化，称作 field-aware factorization machine: FFM。
PITF 和 FFM 的区别在于：PITF 考虑了 user、item、tag 三个特殊的字段field，而 FFM 更加通用。由于 FFM 是针对比赛的整体解决方案，因此对它的讨论是有限的，主要包含以下结论：
- FFM 使用随机梯度 SG 来解决优化问题。为了避免过拟合，Team Opera Solutions 只训练了一个 epoch。
- FFM 在Team Opera Solutions 尝试的六个模型中表现最好。
在论文 《Field-aware Factorization Machines for CTR Prediction》 中，作者旨在具体建立 FFM 作为 CTR 预估的有效方法。论文的主要结果如下：
- 尽管 FFM 被证明是有效的，但是本文可能是唯一发表的、将 FFM 应用于 CTR 预估问题的研究。为了进一步证明 FFM 在 CTR 预估方面的有效性，作者使用 FFM 作为主要模型，从而赢得由 Criteo 和 Avazu 主办的两场全球 CTR 比赛。
- 论文将 FFM 和两个相关模型 Poly2 和 FM 进行比较。作者首先从概念上讨论为什么 FFM 可能比它们更好，并通过实验来查看准确性和训练时间方面的差异。
- 论文提出了训练 FFM 的技术，包括用于 FFM 的有效并行优化算法、以及早停以避免过拟合。
- 为了让 FFM 可以被大家使用，论文发布了一个开源软件。

4.1 模型

bias $\mathbf{\vec x}=(x_1,\cdots,x_K)\in \mathbb R^K$ ，
- POLY2 模型为：
  $\hat y(\mathbf{\vec x}) =\phi_\text{POLY2} (\mathbf{\vec w},\mathbf{\vec x})= \sum_{i=1}^K\sum_{j=i+1}^K w_{i,j}\times x_i\times x_j\\$
  $O(K^2)$ $O(K^2)$ 。
  $O(\bar K^2)$ $\bar K$ 为平均非零特征数量。
- FM 模型为：
  $\hat y(\mathbf{\vec x}) =\phi_\text{FM} (\mathbf V,\mathbf{\vec x})= w_0 + \sum_{i=1}^K w_i\times x_i + \sum_{i=1}^K\sum_{j=i+1}^K \hat w_{i,j}\times x_i\times x_j\\ \hat w_{i,j} = <\mathbf{\vec v}_i,\mathbf{\vec v}_j> = \sum_{l=1}^d v_{i,l}\times v_{j,l}$
  $O(K\times d)$ $O(K^2\times d)$ 。
  通过重写上式：
  $\hat y(\mathbf{\vec x}) =\phi_\text{FM} (\mathbf V,\mathbf{\vec x}) = \frac 12 \sum_{l=1}^d\left(\left(\sum_{i=1}^Kv_{i,l}\times x_i\right)^2 - \sum_{i=1}^K v_{i,l}^2\times x_{i}^2\right)$
  $O(K\times d)$ 。
  $O(\bar K^2)$ $\bar K$ 为平均非零特征数量。

Rendle 解释了为什么当数据集稀疏时，FM 可以比 Poly2 更好。这里我们用上述人工数据集给出类似的说明。
例如，对于 pair (ESPN, Adidas) 只有一个负样本：
- Poly2 $w_\text{ESPN,Adidas}$ 学习一个非常负的权重。
- 对于 FM(ESPN, Adidas) $\mathbf{\vec v}_\text{ESPN}\times \mathbf{\vec v}_\text{Adidas}$ $\mathbf{\vec v}_\text{ESPN}$ $\mathbf{\vec v}_\text{Adidas}$ 也可以从其它pair 中学习（如 (ESPN,Nike), (NBC, Adidas)），所以预测会更准确。
另一个例子是没有针对 (NBC, Gucci) 的训练数据：
- 对于 Poly2，对这个pair 的预测是无意义的trivial。
- FM $\mathbf{\vec v}_\text{NBC}$ $\mathbf{\vec v}_\text{Gucci}$ 仍然可以从其它 pair 中学习，因此仍然可以做出有意义的预测。
Poly2 $O(K^2)$ 。由于 CTR 预估任务中的特征数量通常很大，因此Poly2 不可行。 Vowpal Wabbit: VW 这个广泛使用的机器学习 package 通过哈希来解决这个问题。我们的实现方法也类似，具体而言：
$\hat y(\mathbf{\vec x}) = \phi_\text{POLY2} (\mathbf{\vec w},\mathbf{\vec x})= \sum_{i=1}^K\sum_{j=i+1}^K w_{h(i,j)}\times x_i\times x_j\\ h(i,j) = \left(\frac{1}{2}(i+j)(1+j+1)+j\right)\mod B$
$B$ 是一个用户指定的超参数。
FFM 的思想来源于个性化tag 推荐的 PITF。PITF 假设有三个可用字段field，包括 User、Item、Tag，并且在独立的潜在空间中分解 (User, Item)、(User, Tag)、(Item, Tag)。FFM 将 PITF 推广到更多字段（如 AdID、AdvertiserID、UserID、QueryID），并将其有效地应用于 CTR 预估。
由于 PITF 仅针对三个特定字段（User, Item, Tag），而 FFM 原始论文缺乏对 FFM 的详细讨论，因此这里我们提供了对 CTR 预估的 FFM 的更全面的研究。
对于大多数 CTR 数据集，特征 features 可以分组为字段 fields。在我们前面的示例中，ESPN, Vogue, NBC 三个特征属于 Publisher 字段，另外三个特征 Nike, Gucci, Adidas 属于 Advertiser 字段。FFM 是利用字段信息的 FM 变体。
为了解释 FFM 的工作原理，我们考虑以下示例：
```
xxxxxxxxxx
1
1
Publisher (P): ESPN; Advertiser (A): Nike; Gender (G): Male; Clicked: Yes
```
考虑对于 FM，有：
$\hat y(\mathbf{\vec x}) =\phi_\text{FM} (\mathbf V,\mathbf{\vec x}) = \mathbf{\vec v}_\text{ESPN}\cdot \mathbf{\vec v}_\text{Nike} +\mathbf{\vec v}_\text{ESPN}\cdot \mathbf{\vec v}_\text{Male} + \mathbf{\vec v}_\text{Nike}\cdot \mathbf{\vec v}_\text{Male}$
在 FM 中，每个特征只有一个潜在向量来学习和其它特征的潜在效应 latent effectESPN $\mathbf{\vec v}_\text{ESPN}$ Nike $\mathbf{\vec v}_\text{ESPN}\cdot \mathbf{\vec v}_\text{Nike}$ Male $\mathbf{\vec v}_\text{ESPN}\cdot \mathbf{\vec v}_\text{Male}$ ）。然而，因为 Nike 和 Male 属于不同的字段，(EPSN, Nike) 和 (EPSN, Male) 的潜在效应可能不一样。
在 FFM 中，每个特征有若干个潜在向量，这依赖于其它特征的字段数量。例如在这个例子中：
$\hat y(\mathbf{\vec x}) =\phi_\text{FFM} (\mathbf V,\mathbf{\vec x}) = \mathbf{\vec v}_\text{ESPN,A}\cdot \mathbf{\vec v}_\text{Nike,P} +\mathbf{\vec v}_\text{ESPN,G}\cdot \mathbf{\vec v}_\text{Male,P} + \mathbf{\vec v}_\text{Nike,G}\cdot \mathbf{\vec v}_\text{Male,A}$
其中：
- (ESPN, NIKE) $\mathbf{\vec v}_\text{ESPN,A}$ $\mathbf{\vec v}_\text{Nike,P}$ 学习，因为 Nike 属于 Advertiser 字段、ESPN 属于 Publisher 字段。
- (ESPN, Male) $\mathbf{\vec v}_\text{ESPN,G}$ $\mathbf{\vec v}_\text{Male,P}$ 学习，因为 Male 属于 Gender 字段、 ESPN 属于 Publisher 字段。
- (Mike, Male) $\mathbf{\vec v}_\text{Nike,G}$ $\mathbf{\vec v}_\text{Male,A}$ 学习，因为 Male 属于 Gender 字段、 Nike 属于 Advertiser 字段。
FFM 模型用数学语言描述为：
$\hat y(\mathbf{\vec x}) =\phi_\text{FFM} (\mathbf V,\mathbf{\vec x})=\sum_{i=1}^K\sum_{j=i+1}^K \hat w_{i,j}\times x_i\times x_j\\ \hat w_{i,j} = <\mathbf{\vec v}_{i,f_j},\mathbf{\vec v}_{j,f_i}> = \sum_{l=1}^d v_{i,f_jl}\times v_{j,f_i,l}$
$f_i$ $i$ field $F$ field $1\le F\le K$ ）。
$O(K\times d\times F)$ $O(\bar K^2\times d)$ $\bar K$ 是样本中平均非零特征数。
和 FM 相比，通常 FFM 中 representation 向量的维度要低的多。即：
$d_{\text{FFM}} \ll d_{\text{FM}}$
.

4.2 优化算法

FFM 模型采用随机梯度下降算法来求解，使用 AdaGrad 优化算法。
$(\mathbf{\vec x},y)$ $\mathcal L$ 退化为：
$\mathcal L = \log (1+\exp(-y\phi_\text{FFM}(\mathbf V,\mathbf{\vec x}))) + \sum_{\theta\in \mathbf \Theta} \lambda_{\theta} \times \frac 12 \theta^2$
bias $\lambda_\theta=\lambda$ ，则有：
$g_{w_0} =\frac{\partial \mathcal L }{\partial w_0} = \lambda w_0 + \kappa\\ \mathbf{\vec g}_{\mathbf{ w}} = \nabla_{\mathbf{\vec w}} \mathcal L = \lambda\mathbf{ \vec w} + \kappa\times \mathbf{\vec x}\\ \mathbf{\vec g}_{\mathbf{ v}_{i,f}} = \nabla_{\mathbf{\vec v}_{i,f }} \mathcal L = \lambda \mathbf{\vec v}_{i,f } + \sum_{f_j \ne f} \kappa \times \mathbf{\vec v}_{j,f_i}\times x_i\times x_j\\ i=1, \cdots,K;f=1,\cdots,F$
$\sum_{f_j\ne f}$ field f $\kappa$ 表示：
$\kappa = \frac{\partial \log(1+\exp(-y\phi))}{\partial \phi_\text{FFM}} = -\frac{y}{1+\exp(y\phi_\text{FFM}(\mathbf{\vec x}))}$
- 对梯度的每个维度，计算累积平方：
  $G_{w_0} \leftarrow G_{w_0} + g_{w_0}^2\\ G_{w_i} \leftarrow G_{w_i} + g_{w_i}^2 \\ G_{v_{i,f,l}} \leftarrow G_{v_{i,f,l}} + g_{v_{i,f,l}}^2\\ i=1,\cdots,K;\;f=1,\cdots,F;\;l=1,\cdots,d$
  $g_{w_i}$ $\mathbf{\vec g}_{\mathbf w}$ $i$ $i=1,2,\cdots,K$ $g_{v_{i,f,l}}$ $\mathbf{\vec g}_{\mathbf{ v}_{i,f}}$ $l$ $l=1,2,\cdots,d$ 。
- 更新参数：
  $\theta \leftarrow \theta - \frac{\eta}{\sqrt{G_\theta}} g_{\theta}$
  $\eta$ $\theta \in \{w_0,\mathbf {\vec w},\mathbf{\vec v}_{i,f}\}$ 。
模型参数需要合适的初始化。论文推荐：
- $\mathbf{\vec v}_{i,f}$ $[0,1/\sqrt d]$ 中随机初始化。
- $G_\theta$ 1 $\frac {1}{\sqrt{G_\theta}}$ 太大，从而导致前进方向较大的偏离损失函数降低的方向。
$w_0,\mathbf {\vec w}$ $\sigma$ 的正态分布来初始化它们。
论文推荐采用样本级别的归一化，这可以提升模型泛化能力。
注：如果采用 Batch normalization 效果可能会更好。论文未采用 BN，是因为论文发表时 BN 技术还没有诞生。
FFM 的 AdaGrad 优化算法：
- 输入：
  - $\mathbb S$
  - $\eta$
  - $T$
  - $w_0,\mathbf{\vec w }$ $\sigma$
- $\mathbf \Theta^*$
- 算法步骤：
  - $G_{\theta}$ ：
    $G_\theta = 1\\ (w_0,\mathbf{\vec w}) \leftarrow \mathcal N(0,\sigma)\\ \mathbf{\vec v}_{i,f}\leftarrow [0,1/\sqrt d]$
  - $T$ 步，每一步的过程为：
    - $\mathbb S$ $(\mathbf{\vec x},y)$
    - $\kappa$ ：
      $\kappa = -\frac{y}{1+\exp(y\phi_\text{FFM}(\mathbf{\vec x}))}$
    - $g_{w_0},G_{w_0}$ $w_0$
    - $i=1,\cdots,K$ ：
      - $g_{w_i},G_{w_i}$ $w_i$
      - $j=i+1,\cdots,K$
        $\mathbf{\vec g}_{v_{i,f}}$
        $l=1,\cdots,d$ $G_{i,f,l}$ $v_{i,f,l}$

4.3 field 分配

大多数数据集的结构是：
```
xxxxxxxxxx
1
1
label  feat1:val1 feat2:val2 ...,
```
其中 (feat:value) 表示特征索引及其取值。对于 FFM，我们扩展上述格式为：
```
xxxxxxxxxx
1
1
label field1:feat1:val1 field2:feat2:val2
```
也就是我们必须为每个特征分配相应的字段。
为某些类型的特征分配字段很容易，但是对于其他一些特征可能比较困难。接下来我们在三种典型类型的特征上讨论这个问题。
离散型特征 categorical ：通常对离散型特征进行 one-hot 编码，编码后的所有二元特征都属于同一个 field 。例如，性别字段：G:G-Male:1、G:G-Male:0 。
数值型特征 numuerical：数值型特征有两种处理方式：
- dummy field $F=K$ ， FFM 退化为 Poly2 模型。例如论文引用量 Cite:Cite:3，其中分配的字段和特征名相同。
- 数值特征离散化之后，按照离散型特征分配 field 。例如，论文引用量 Cite:3:1，其中 3 表示特征名（桶的编号）。
  论文推荐采用这种方式，缺点是：
  - 难以确定合适的离散化方式。如：多少个分桶？桶的边界如何确定？
  - 离散化会丢失一些信息。
离散集合特征categorical set（论文中也称作 single-fieldfield $F=1$ ， FFM 退化为 FM 模型。
如 NLP 情感分类任务中，特征就是单词序列。
- 如果对整个sentence 赋一个field，则没有任何意义，因为此时可能的特征范围是天文数字。
- 如果对每个wordfield $F$ $O(FKd)$ 无法接受。

4.4 实验

这里我们首先提供实验配置的细节，然后我们研究超参数的影响。我们发现，和逻辑回归以及 Poly2 不同，FFM 对 epoch 数量很敏感，因此我们提出了早停策略。最后我们将 FFM 和包括 Poly2, FM 在内的其它 baseline 进行对比，除了预估准确性之外我们还对比了训练时间。
数据集：我们主要考虑来自 Kaggle 比赛的两个数据集 Criteo 和 Avazu。对于特征工程，我们主要应用了我们的成功方案，但是移除了复杂的部分。例如，我们在 Avazu 数据集的成功方案包含了 20ensemble $10^6$ 个特征。这两个数据集的统计信息如下：
对于这两个数据集，测试集中的标签都是不可用的，所以我们将可用的数据分为训练集和验证集，拆分方式为：对于 Criteo，最后 6040618 行用于验证集；对于 Avazu，最后 4218938 行用于验证集。我们用以下术语来表示各个不同的数据集：
- Va：上述拆分的验证集。
- Tr：从原始训练集中剔除验证集之后，得到的新训练集。
- TrVa：原始的训练集。
- Te：原始的测试集，其 label 未公布，所以我们必须将我们的预测结果提交给评估系统从而获得 score 分。为了避免测试集过拟合，竞赛组织者将该数据集分为两个子集：public set （竞赛期间 score 可见）、private set（竞赛期间 score 不可见且只有竞赛结束后 score 才公布）。最终排名由 private set 决定。
配置：所有实验都是在 Linux 工作站上运行，该工作站配置为两个 Intel Xeo E6-2620 2.0GHz 处理器、128GB 内存。
评估指标：我们考虑 logloss 作为评估指标，其中：
$\text{logloss} = \frac{1}{m}\sum_{i=1}^m \log(1+\exp(-y_i \phi(\Theta,\mathbf{\vec w}_i)))$
其中：
- $m$ $y_i$ 为测试样本 label 。
- $\Theta$ $\phi(\cdot)$ $\phi_\text{LM},\phi_\text{Poly2},\phi_\text{FM},\phi_\text{FFM}$ 。
$d$ representation $\lambda$ $\eta$ （学习率）的影响。所有结果都是在验证集上得到。为了加快实验，我们从 Criteo新训练集中随机抽取 10% 样本作为训练集、从 Criteo验证集中随机选择 10% 样本作为测试集。
- $d$ $d$ 的取值（论文中用 k 这个不同的符号），第二列为平均每个epoch 的计算时间，第三列为验证集的 logloss 。
  可以看到：不同的representationFFM $d$ 值。
  SSE $d=1,2,3$ 时每个 epoch 计算时间几乎相同。
- $\lambda$ 的实验效果如下图所示。可以看到：
  - 如果正则化系数太小，则模型太复杂，容易陷入过拟合。
  - 如果正则化系数太大，则模型太简单，容易陷入欠拟合。
  一个合适的正则化系数不大不小，需要精心挑选。
- $\eta$ 的实验效果如下图所示：可以看到：
  - 如果学习率较小，虽然模型可以获得一个较好的性能，但是收敛速度很慢。
  - 如果学习率较大，则目标函数很快下降，但是目标函数不会收敛到一个较低的水平。
早停：FFM 对于训练 epoch 次数很敏感。为解决该问题，我们对 FFM 执行早停策略：
- 首先将数据集拆分为训练集、验证集。
- 在通过训练集训练的每个 epoch 结束时，计算验证集的 logloss 。
- 如果验证集的 loglossepoch $\text{epoch}_{best}$ ，并停止当前训练。
- $\text{epoch}_{best}$ 个 epoch 。
该方案存在一个潜在的缺点：logloss 对 epoch 次数高度敏感，以及验证集上的最佳 epoch 不一定是测试集上的最佳 epoch。因此早停得到的模型无法保证在测试集上取得最小的 logloss 。
我们也尝试了其它的避免过拟合的方法，比如 lazy update 和 ALS-based 优化，但是这些方法效果都不如早停策略。
我们在 Criteo 和 Avazu 数据集上比较了不同算法、不同优化方式、不同超参数的结果。
我们选择了四种算法，包括LM 模型（线性模型）、POLY2 模型、FM 模型、FFM 模型。我们选择了三种优化算法，包括SG （随机梯度下降）、CD（坐标下降）、Newton（牛顿法）、ALS 。另外我们还选择了不同超参数。
- LIBFM 支持SG,ALS,MCMC 三种优化算法，但是我们发现 ALS 效果最好。因此这里 LIBFM 使用 ALS 优化算法。
- FM、FFM 都是基于 SG 优化算法来实现的，同时对于 SG 优化算法采取早停策略。
- 对于非 SG 优化算法，停止条件由各算法给出合适的停止条件。
从实验结果可以看到：
- FFM 模型效果最好，但是其训练时间要比 LM 和 FM 更长。
- LM 效果比其它模型都差，但是它的训练要快得多。
- FM 是一种较好的平衡了预测效果和训练速度的模型，这就是效果和速度的平衡。
- POLY2 比所有模型都慢，因为其计算代价太大。
- 从两种 FM 的优化方法可见，SG 要比 ALS 优化算法训练得快得多。
- 逻辑回归是凸优化问题，理论上 LM 和 POLY2 的不同优化算法应该收敛到同一个点，但实验表明并非如此。原因是：我们并没有设置合适的停止条件，这使得训练过程并没有到达目标函数极值点就提前终止了。
我们比较了其它数据集上不同模型的表现。其中：
- KDD2010-bridge,KDD2012,adult 数据集包含数值特征和离散特征，我们将数值特征执行了离散化。
- cod-rna,ijcnn 数据集仅仅包含数值特征，我们将数值特征进行两种处理从而形成对比：将数值特征离散化、每个数值特征作为一个field （称作 dummy fields ）。
- phishing 数据集仅仅包含离散特征。
实验结果表明：
- FFM 模型几乎在所有数据集上都占优。这些数据集的特点是：
  - 大多数特征都是离散的。
  - 经过 one-hot 编码之后大多数特征都是稀疏的。
- 在 phishing,adult 数据集上 FFM 几乎没有优势。原因可能是：这两个数据集不是稀疏的，导致 FFM,FM,POLY2 这几个模型都具有几乎相同的表现。
- 在 adult 数据集上LM 的表现和 FFM,FM,POLY2 几乎完全相同，这表明在该数据集上特征交叉几乎没有起到什么作用。
- 在 dummy fields 的两个数据集上 FFM 没有优势，说明 field 不包含任何有用的信息。
- 在数值特征离散化之后，尽管 FFM 比 FM 更有优势，但还是不如使用原始数值特征的 FM 模型。
  这说明数值特征的离散化会丢失一些信息。
从实验中总结的 FFM 应用场景：
- 数据集包含离散特征，且这些离散特征经过one-hot 编码。
- 经过编码后的数据集应该足够稀疏，否则 FFM 无法获取较大收益（相对于 FM ）。
- 不应该在连续特征的数据集上应用 FFM，此时最好使用 FM 。

五、GBDT-LR 模型[2014]

数字广告 didital advertising 是一个价值数十亿美元的产业，并且每年都在急剧增长。在大多数在线广告平台中，广告的投放是动态的，根据用户的兴趣来个性化投放。机器学习在计算候选广告对用户的预期效用expected utility 方面发挥着核心作用，并以这种方式提高了市场效率。
Varian （论文 《Position auctions》）和 Edelman 等人（论文 《 Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords》）在 2007 年发表的开创性论文描述了由 Google 和 Yahoo! 开创的点击出价bid per click、点击扣费 pay per click 。同年，微软也在建立一个基于相同拍卖模型（论文《Predicting clicks: Estimating the click-through rate for new ads》）的sponsored search 市场。广告拍卖auction的效率取决于点击率预估的准确性 accuracy 和校准 calibration 。点击率预估系统需要健壮性robust和适应性adaptive，并且能够从大量数据中学习。点击率预估系统是大多数在线广告系统的核心。Facebook 拥有超过 7.5 亿的日活用户、超过 100 万的活跃广告主，因此预估广告的点击率是一项具有挑战性的机器学习任务。论文 《Practical Lessons from Predicting Clicks on Ads at Facebook》分享了满足这些要求的、从真实世界数据执行的实验中得出的洞察insight。
在 sponsored search 广告中，user query 用于检索和 query 显式或者隐式匹配的候选广告。在 Facebook 中，广告不是与 query 相关，而是指定人口统计特性和兴趣的定向targeting 。因此，当用户访问 Facebook 时，合格 eligible 的广告数量可能超过 sponsored search 搜索量。为了处理每个请求的大量候选广告（每当用户访问 Facebook 时都会触发广告请求），Facebook 将首先构建一系列计算代价递增的、级联cascade 的 classifiers （即matching、ranking 等一系列模型）。在本文中，论文关注级联分类器最后阶段的点击率预估模型，即为最终候选广告集合生成预测的模型。
论文发现：将决策树与逻辑回归相结合的混合模型比这两种方法中的任何一个都高出 3%以上。这种提升对于整体系统性能有重大影响。许多基础的超参数会影响系统的最终预测性能。毫不意外，最重要的是拥有正确的特征：比其它特征，那些捕获有关用户历史信息和广告历史信息的特征占统治地位。一旦有了正确的特征和正确的模型（决策树加逻辑回归），其它因素就发挥了很小的作用（即使是很小的改进，在如此规模的任务中也很重要）。针对数据新鲜度freshness 、学习率模式schema、数据采样而选择最佳处理方式会稍微改善模型，尽管改善的幅度远不如添加高价值特征、或者选择正确的模型。
论文从实验设置概述开始，然后评估不同的概率线性分类器 probabilistic linear classifiers 以及不同的在线学习算法。在线性分类的背景下，论文继续评估特征变换和数据新鲜度的影响。
受到实际经验教训的启发，尤其是在数据新鲜度和在线学习方面，论文提出了一个模型架构，该架构包含一个在线学习层online learning layer ，同时生成相当紧凑的模型。接下来描述了在线学习层所需的一个关键组件，即online joiner ，它是一种实验性的基础设施，可以生成实时训练数据real-time training data 的实时流live stream 。
最后，论文提出了用内存、计算时间、处理大量数据和准确性进行 tradeoff 的方法。包括为大规模 application 优化内存和延迟的使用方法，以及训练数据规模和准确性之间权衡的研究。

5.1 实验配置

为了实现严格可控的实验，我们选取了 2013 年第四季度的任意一周，从而作为离线训练数据。我们将离线数据划分为训练集和测试集，并使用它们来模拟流式数据 streaming data，从而进行在线训练和预估。论文中的所有实验都使用相同的训练集/测试集。
评估指标：由于我们最关心的是各个因素factors对于机器学习模型的影响，因此我们使用预估的准确性来评估，而不是与利润和收入直接相关的指标。在这里我们使用归一化熵 Normalized Entropy: NE 和校正calibration 作为我们的主要评估指标。
- 归一化熵（更准确地讲，归一化交叉熵Normalized Cross- Entropy ）等于每次曝光的平均对数损失除以背景熵 background entropy 。
  $N$ CTR $\bar p$ $i$ $p_i$ $y_i\in \{-1,+1\}$ 。
  - 定义背景点击率 background CTR 为样本集合经验 CTR ，它的熵定义为背景熵：
    $H_{bg} = - \bar p\log \bar p - (1-\bar p)\log(1-\bar p)$
    背景熵衡量了样本集合的类别不平衡程度，也间接的衡量了样本集合的预测难度。
    类别越不均衡预测难度越简单，因为只需要将所有样本预测为最大的类别即可取得非常高的准确率。
  - 定义模型在样本集合熵的损失函数为：
    $\mathcal L = - \sum_{i=1}^N\left(\frac{1+y_i}{2}\log p_i + \frac{1-y_i}{2}\log (1-p_i)\right)$
    每个样本的损失为交叉熵。
  - 定义归一化熵 NE 为：模型在所有样本的平均损失函数除以背景熵。
    $\text{NE} = \frac{\mathcal L /N}{H_{bg}}$
    $N$ 是为了剔除样本集合大小的影响。
  NE 相对损失函数的优势在于：NE 考虑了样本集预测的难易程度。在平均损失相同的情况下，样本集越不均衡则越容易预测，此时 NE 越低。
  归一化熵可以用于计算相对信息增益 Relative Information Gain: RIG，其中 RIG = 1 - NE 。
- 校正 Calibration 是平均预估点击率和经验点击率的比值。换句话讲，它是期望点击次数和实际观察到点击次数的比值。calibration 是一个非常重要的指标，因为准确且校准良好的 CTR 预估对于在线竞价和拍卖的成功至关重要。calibration 和 1.0 的差异越小，模型越好。
注意，AUC 也是评估模型能力的一个很好的指标，但是 AUC 反应的模型对样本的排序能力：auc=0.8 表示 80% 的情况下，模型将正样本预测为正类的概率大于模型将负样本预测为正类的概率。
在现实环境中，我们期待预测是准确的，而不仅仅是获得最佳的排序，从而避免潜在的投放不足 under-delivery 、以及投放过度 over-delivery 。
NE 衡量的预估好坏并不隐式地反映 calibration 。例如，如果模型高估了 2 倍，然后我们使用一个全局的因子 0.5 来固定地校准：
- 因为校准不改变模型的排序能力，所以 AUC 保持不变。
- 因为校准后的 pCTR 分布与样本的标签分布距离更近，所以NE 会得到改善。
有关这些指标的深入研究，可以参考 《Predictive model performance: Offline and online evaluations》 。

5.2 预估模型结构

这里我们展示了一个混合模型结构：boosted decision trees: BDT 和概率稀疏线性分类器probabilistic sparse linear classifier 的拼接，如下图所示。其中输入特征通过 BDT 进行变换，每棵子树的输出都被视为稀疏线性分类器的离散输入特征。 BDT 已经被证明是非常强大的特征变换。
- 我们首先展示了决策树是非常强大的输入特征变换，可以显著提高概率线性分类器。
- 然后我们展示了更新鲜 fresher 的训练数据如何导致更准确的预估，这激发了使用在线学习方法来训练线性分类器的思想。
- 最后我们比较了两个概率线性分类器家族的许多在线学习变体。

5.2.1 决策树特征变换

有两种最简单的特征转换方式：
- 连续特征离散化：将连续特征的取值映射到一个个分散的分桶里，从而离散化。这里桶的数量和边界难以确定，通常有两种方法：
  - 通过人工根据经验来设定分桶规则。
- 利用后续的分类器来显式的学习这个非线性映射，从而学习出有意义的分桶数量和边界。
- 离散特征交叉：类似 FM 模型采用二路特征交叉（或者更高阶）来学习高阶非线性特征。
  对于连续特征可以先离散化之后再执行特征交叉，如 kd 树就是典型的代表。
Boosted decisition tree:BDT 就是结合了上述两种方式的一个强大的特征提取器。对于 BDT，我们将每棵子树视为一个离散特征，其叶结点的编号为特征的取值并执行 one-hot 编码。
假设 BDT 有两棵子树，第一棵有 3 个叶结点，第二棵有2 个叶结点。则样本提取后有两个特征：第一个特征取值为 {1,2,3}，第二个特征取值为 {1,2} 。假设某个样本被划分到第一棵子树的叶结点 2，被划分到第二棵子树的叶结点 1，则它被转换后的特征为：[0,1,0,1,0]。其中：前三项对应于第一个离散特征的 one-hot，后两项对应于第二个离散特征的 one-hot 。
我们使用的 BDT 为梯度提升树 Gradient Boosting Machine:GBM ，其中使用了经典的 L2-TreeBoost 算法。在每次学习迭代中，都会创建一棵子树对残差进行建模。我们可以将基于 BDT 的变换理解为一种监督特征编码：
- 它将一组实值向量 real-valued vector 转换为一组二元向量 binary-valued vector 。
- 每棵子树从根节点到叶节点的遍历表示某些特征转换规则。
- 在转换后的二元向量上拟合线性分类器本质上是学习每个规则的权重。
我们进行了实验以显示将树特征作为线性模型输入的效果。我们对比了两种逻辑回归模型：一种具有树特征变换，另一种具有普通特征（未变换的）。我们还对比了一个 BDT 模型。对比结果如下表所示，可以看到：
- 树特征变换有助于将归一化熵降低 3.4% 以上。这是一个非常显著的提升。
- 有意思的是，单独使用 LR 和单独使用 Tree 模型具有相差无几的预测准确性（实际上 LR 稍微好一点），但是它们的组合使得准确性大幅上升。

5.2.2 数据新鲜度

点击率预估系统通常部署在数据分布随时间变化的动态环境中。我们研究了训练数据新鲜度freshness对于预测性能的影响。为此，我们在某一天训练一个模型并在连续几天内对其进行测试。我们为 BDT 模型、带tree-transformed 的逻辑回归模型进行实验。实验中，我们训练一天的数据，并评估连续六天中每一天的归一化熵。
结果如下图所示，指标是相对于最差的 NE 的比例（最差的 NE 发生在 Trees only 模型延迟 6 天时）。可以看到：
- 随着训练集和测试集之间延迟的增加，两种模型的预估准确性显著下降。
- 通过将每周训练改为每天训练，NE 可以减少大约 1% 。
这些发现表明：每天进行重新训练是值得的。
考虑数据新鲜度，我们需要用最新的样本更新模型。有两种更新策略：
- 每天用最新的数据重新训练模型。重新训练模型所需的时间各不相同，取决于训练样本的数量、子树的数量、每棵子树的叶节点数量、cpu、内存等因素。通常在大规模集群中可以在几个小时内完成训练。
- 每天或者每隔几天来训练特征提取器 BDT ，但是用最新的数据在线近乎实时地训练 LR 线性分类器。

5.2.3 学习率

为了最大限度地提高数据新鲜度，一种选择是在线训练线性分类器，即在带 label 的曝光信息到达时直接训练。这里我们评估了几种为基于 SGD 的逻辑在线学习设置学习率的方法。
- per-coordinate $t$ $i$ 的学习率为：
  $\eta_{t,i} = \frac{\alpha}{\beta +\sqrt{\sum_{j=1}^t (\mathbf{\vec g}_j)_i^2}}$
  $\alpha,\beta$ $(\mathbf{\vec g}_j)_i$ $j$ $i$ 的分量。
  - $i$ 的梯度越大，说明该特征方向波动较大，则学习率越小，学习速度放慢。
  - $i$ 的梯度越小，说明该特征方向波动较小，则学习率越大，学习速度加快。
- per-weight $t$ $i$ 的学习率为：
  $\eta_{t,i} = \frac{\alpha}{ {n_{t,i}}}$
  $\alpha$ $n_{t,i}$ $t$ $i$ 上有取值的所有样本数量。
  在广告场景中，这些特征在大多数情况下都没有取值，因此对应的权重很难有更新机会。
  - $i$ 上有取值的样本越多，则可供学习的样本也多，则学习率越小，学习速度放慢。
  - $i$ 上有取值的样本越少，则可用学习的样本也少，则学习率越大，学习速度加快。
- per-weight square root $t$ $i$ 的学习率为：
  $\eta_{t,i} = \frac{\alpha}{\sqrt{n_{t,i}}}$
- global $t$ 次迭代所有特征的学习率都为：
  $\eta_{t,i} = \frac{\alpha}{\sqrt t}$
- constant $t$ 次迭代所有特征的学习率都为：
  $\eta_{t,i} = \alpha$
前三种方式针对每个特征都有不同的学习率，最后两种方式对所有特征采用相同的学习率。所有超参数都通过网格搜索来调优，最优值如下表所示。
我们将学习率下限设定为 0.00001 从而用于在线的 continuous learning 。我们使用上述学习率方案在相同数据集上训练和测试 LR 模型，实验结果如下图所示。可以看到：
- per-coordinate 方法获得最好的表现，而 per-weight 效果最差。per-weight square root 和 constant 方案具有相似、但是稍差的效果。
- 全局学习率表现不佳，其主要原因是：每个特征上训练样本数量不平衡。
  一些高频特征上（如：“是否男性” 特征）的样本数量较多，而另一些低频特征（如：“是否明星” ）上的样本数量较少。在全局学习率策略下，低频特征学习率太快降低到很小的值，使得最优化难以收敛到最优点。
- 虽然 per-weight 策略解决了该问题，但是它仍然表现不佳。主要原因是：虽然它对低频特征的学习率控制较好，但是它对高频特征的学习率控制较差。它对所有特征的学习率都下降得太快，在算法收敛到最优点之前训练就过早终止了。这解释了为什么该方案是所有学习率方案中最差的。

5.3 ONLINE DATA JOINER

如前所述，更新鲜的训练数据会提高预估准确性。这里我们介绍一个实验系统，该系统生成用于在线学习训练线性分类器的实时训练数据。我们将这个系统称作 online joiner ，因为它的关键操作是以在线方式将 label （是否点击）和训练数据（广告曝光）进行关联。
在线训练框架最重要的是为模型提供在线学习的标注样本。点击行为比较好标记，但是“不点击”行为难以标记。因为广告并没有一个“不点击”按钮来获取不点击的信息。因此，如果一个曝光在一个时间窗内未发生点击行为，则我们标记该次曝光是未点击的。
之所以要设定一个时间窗，是因为广告曝光和用户点击之间存在时间差。这里有两个原因：
- 给用户曝光一个广告后，用户不会立即点击。如：用户会简单浏览广告的内容再决定是否点击。对于视频类广告，用户甚至会观看完整视频之后再决定是否点击。
  因此曝光事件和点击事件这两个事件存在时间差。
- 广告系统的曝光日志和点击日志通常都是分开的、独立的实时数据流。这两个数据流回传到在线训练系统可能并不是同步的，存在数据回传时间差。
这个等待时间窗口需要仔细调优：
- 如果窗口太长，那么会延迟实时训练数据，数据 freshness 较差。同时为了存储更长时间的曝光数据内存代价也较高。
- 如果窗口太短，那么会导致部分点击丢失，因为相应的曝光可能已经被标记为 no click 并移出内存。这会对点击覆盖率 click coverage 产生不利影响。其中点击覆盖率指的是成功关联曝光的点击占所有点击的比例。
因此，online joiner 必须在新近程度 recency 和点击覆盖率之间取得平衡。点击覆盖率低意味着实时训练集会有 bias：经验 CTR 略低于 ground truth 。这是因为如果等待时间足够长，那么标记为 no click 的部分曝光会被标记为 click。通过挑选合适的时长，可以降低经验的 CTR 偏差到百分之一以下，同时内存代价也可以接受。
Facebook 在线训练框架如下图所示：
- 用户浏览 Facebook 时向 Ranker 模块发送一个广告请求，请求中包含 request ID 。
- Ranker 模块根据在线模型的预测结果，向用户返回一个广告，同时在曝光实时数据流中增加一条曝光日志。
- 如果用户点击广告，则前端打点系统上报点击事件，在后台点击实时数据流中增加一条点击日志。
- 通过 Oneline Joiner 模块实时获取最近一个时间窗的曝光、点击日志，并拼接样本特征来构造训练集。
- Trainer 模块根据构造的训练集执行在线训练，训练好的模型部署到线上供 Ranker 模块使用。
这会形成一个数据闭环，使得模型能够捕捉到最新的数据分布。
在线训练需要增加对实时训练数据的异常保护。假设实时训练数据出现问题（如：前端打点上报出现异常、Online Joiner 工作异常等），导致大量的点击数据丢失。那么这批实时训练样本存在缺陷，它们的经验 CTR 非常低甚至为 0。如果模型去学习这样一批样本，则模型会被带偏：对任何测试样本，模型都会预测出非常低、甚至为零的点击率。
根据广告点击价值 eCPM = BID x pCTR，一旦预估点击率 pCTR 为零则广告的 eCPM 为零。那么这些广告几乎没有竞争力，竞争失败也就得不到曝光机会。因此需要增加实时训练数据的异常检测机制。如：一旦检测到实时训练数据的分布突然改变，则自动断开online trainer 和 online joiner 的连接。

5.4 优化技巧

子树的数量：在 GBDT-LR 模型中子树的数量越大模型表现越好，但是计算代价、内存代价越高。随着子树的增多，每增加一棵子树获得的效益是递减的。这就存在平衡：新增子树的代价和效益的平衡。
我们将子树的数量从 1 增加到 2000，并使用一整天的数据训练模型、第二天的数据测试模型性能。我们限制每棵子树的叶子不超过 12 个。和之前的实验类似，我们使用归一化熵 NE 作为评估指标。
实验如下图所示，其中 NE submodel0, NE submodel1 使用全量训练数据、不同的超参数来训练，而NE submodel2 使用 1/4 的训练数据。可以看到：
- NE 随着子树数量的增加而下降，但是最后增加的1000棵子树获得的效益很低。几乎所有的 NE 改善都来自于前 500 棵子树，最后 1000 棵子树得到的 NE 下降不足 0.1% 。
- NE submodel2 由于训练数据更少，使得模型在 1000 棵子树之后出现过拟合（NE 增加）。
特征的数量：特征数量是另一个模型属性，可以影响到估计准确性和计算性能之间的 tradeoff。特征越多模型表现越好，但是计算代价、内存代价越高。但是随着特征的增多，尤其是无效特征的增多，每增加一个特征获得的效益是递减的。这就存在平衡：新增特征的代价和效益的平衡。
为了更好地理解特征数量的影响，我们首先评估特征重要性。我们使用统计的 Boosting Feature Importance，有三种统计方法（如 XGBoolst/LightGBM ）：
- weight：特征在所有子树中作为分裂点的总次数。
- gain：特征在所有子树中作为分裂点带来的损失函数降低总数。
- cover：特征在所有子树中作为分裂点包含的总样本数。
通常情况下，少数特征贡献了大部分解释，而剩余特征仅具有微小的贡献。如下图所示，top 10 特征贡献了大于一半的重要性，最后 300 个特征贡献了不到 1% 的重要性。下图中，左轴给出了对数尺度的特征重要性，右轴给出了累计特征重要性。
基于这一发现，我们进一步试验仅保留 top10,top20,top50,top100,top200 重要性的特征，并评估模型性能的影响。实验结果如下，可以看到：归一化熵随着我们包含更多特征而具有类似的收益递减特性。
接下来我们将对历史特征historica features 和上下文特征 contextual features 进行研究。出于数据敏感性和公司政策，我们无法透露我们使用的实际特征的详细信息。上下文特征可以是本地时间、星期几等，历史特征可以是广告累计的点击量等。
历史特征和上下文特征：BDT 模型中用到的特征分类两类：上下文特征和历史统计特征。
- 上下文特征：曝光广告的当前上下文信息。如：用户设备、用户所在页面的信息等等。
- 历史统计特征：广告的历史统计行为，或者用户的历史统计行为。如：广告的上周平均点击率，用户的历史平均点击率。
这里我们研究这两种类型的特征如何影响系统性能。
首先我们检查这两类特征的相对重要性。我们通过按重要性对所有特征进行排序，然后计算 top k 个重要特征中历史特征的百分比。结果如下所示，其中 Y 轴表示在 top k 特征中历史特征的占比。
可以看到：历史特征比上下文特征提供了更多的解释。按照重要性排序的 top 10 特征都是历史特征。在所有 top 20 特征中，只有 2 个上下文特征，而历史特征占据了 75% 。
为了更好地比较这两类特征，我们训练了两个仅包含上下文特征和历史特征的 BDT 模型，然后将这两个模型与所有特征的完整模型进行比较，结果如下表所示。我们再次验证，总体而言，历史特征比上下文特征发挥更大的作用。在仅有上下文特征的情况下，我们的 NE 损失了 4.5% 。相反，在仅有历史特征的情况下，我们的 NE 损失小于 1% 。
应该注意的是：上下文特征对于处理冷启动问题非常重要。对于新用户和新广告，上下文特征对于合理的点击率预估是必不可少的。
最后，我们在连续几周内评估仅有历史特征或仅有上下文特征的训练模型，以测试这两种类型特征对数据新鲜度的依赖性。实验结果如下图所示。可以看到：具有上下文特征的模型比具有历史特征的模型更依赖于数据新鲜度。这符合我们的直觉，因为历史特征描述了长期累计的用户行为，这比上下文特征要稳定得多。

5.5 训练大量数据

Facebook 每天的广告曝光量非常大。即使是每个小时，数据样本也可能上亿。用于控制训练成本的常用技术是减少训练数据量。本节中，我们评估两种降采样技术，均匀降采样和负降采样。在每种情况下，我们训练一组包含 600 棵树的 boosted tree model ，并是使用 calibration 和归一化熵来评估这些模型。
$p_{sample}$ 来随机采样。该方法容易实现，且采样后的样本分布和采样前保持不变。这样使得训练数据集的分布基本和线上保持一致。
我们评估了 0.001,0.01,0.1,0.5,1 这几种采样率。结果表明：更多的数据带来更好的模型。但是采用 10% 的训练样本相对于全量样本仅仅损失了 1%的预测能力，而训练代价降低一个量级。在该采样率下的 calibration 甚至没有性能下降。注意：calibration 越接近 1.0 越好。
$p_{sample}$ 来随机采样。该方法可以缓解类别不平衡问题。但是，采样后的样本分布和采样前不再相同，导致训练集的分布和线上不再保持一致。因此需要对模型进行校准。
我们评估了 0.0001, 0.001, 0.01, 0.1 这几种采样率。可以看到：负采样率对训练模型的性能有显著影响。将负采样率设置为 0.025 可以实现最佳性能。
Re-Calibration ：负降采样可以加快训练速度，改善模型能力。但是负采样中的训练数据分布和线上数据分布不一致，因此必须对模型进行校准。
假设采样之前样本集的平均 CTR 为 0.1% 。当执行采样率为 0.01 的负降采样之后，由于正样本数量不变、负样本数量降低到之前的 0.01 ，因此采样后的样本集的平均 CTR 为 10% 。此时需要校准模型，使得模型的预估平均 CTRCTR $\hat y$ ，则校准后的预估结果为：
$\hat y_{new} = \frac{\hat y}{\hat y + (1-\hat y)/s}$
$s$ 为负采样比例。

5.6 总结

我们从 Facebook 广告数据的实验中提出了一些实践经验教训，这激发了用于点击率预估的有前途的混合模型架构。
- 数据新鲜度很重要，至少每天都值得重新训练。在本文中，我们进一步讨论了各种在线学习方案。我们还展示了允许生成实时训练数据的基础设施。
- 使用 BDT 转换实值输入特征显著提高概率线性分类器的预测准确性。这激发了一种混合模型架构，该架构将 BDT 和稀疏线性分类器拼接起来。
- 具有 per-coordinate 学习率的 LR 模型比其它正在研究的 LR SGD 学习率方案表现更好。
同时我们还描述了在大规模机器学习中优化内存和延迟的技巧：
- 我们提出了 BDT 的子树数量和准确性之间的 trade-off。保持较少的子树数量从而减少内存和计算量是有利的。
- BDT 提供了一种通过特征重要性进行特征选择的便捷方法。可以激进地减少使用特征的数量，同时预测准确性只会略微下降。
- 我们分析了上下文特征和历史特征的效果。对于有历史特征的广告和用户，这些特征提供了比上下文特征更出色的预测性能。
- 最后，我们讨论了对训练数据进行降采样的方法，如均匀采样和负采样。

六、FTRL工程应用[2013]

在线广告是一个价值数十亿美金的行业，它是机器学习巨大成功的案例之一。赞助搜索广告sponsored search advertising 、上下文广告contextual advertising 、展示广告display advertising、实时竞价拍卖real-time bidding auction 都在很大程度上依赖于模型准确、快速、可靠地预估广告点击率的能力。这种问题设置problem setting 也推动该领域解决大规模问题，即使在十年前，这也是几乎不可想象的。典型的工业模型可以使用相应的大规模特征空间，每天提供数十亿次事件的预测，然后从产生的大量数据中学习。
论文 《Ad Click Prediction: a View from the Trenches》 介绍了一系列案例研究，这些案例研究来自于最近在谷歌用于赞助搜索广告的 CTR 部署系统的实验setting 。这些改进包括基于 FTRL-Proximal 在线学习算法（具有极好的稀疏性sparsity和收敛性convergence ）的传统监督学习环境下的改进，以及per-coordinate 学习率的使用。
因为 CTR 预估问题已经得到了很好的研究，所以作者选择关注一系列不太受关注、但是在工作系统中同样重要的主题。作者探索内存节省memory savings 、性能分析performance analysis、预测置信度confidence in predictions 、calibration、特征管理feature management 等问题，其严谨性和传统上用于设计有效学习算法的问题相同。最后，作者还详细介绍了几个没有收益的方向，尽管这些方向在其他文献中取得了理想的效果。
因此，论文的目的是让读者了解理论进步和实际工程之间的密切关系，并展示在复杂动态系统中应用传统机器学习方法时出现的深层挑战。同时，论文也分享可能适用于其它大规模问题领域的技巧和洞察。

6.1 系统概览

query $q$ query $q$ $a$ $p(\text{click}\mid q,a)$ 。
我们系统中使用的特征来自于各种来源，包括 query、广告创意文本、各种与广告相关的元数据。数据往往非常稀疏，每个样本通常只有一小部分非零特征。诸如正则化的逻辑回归之类的方法非常适合这类问题。每天需要进行数十亿次预测，并在观察到新的样本时快速更新模型。当然，这个数据生产速度意味着训练数据集是巨大的。数据是由一个基于 Photon system 的流式服务 streaming service 提供的。
由于近年来大规模学习large-scale learning 得到了很好的研究，我们没有在本文中投入大量篇幅详述我们的系统架构。然而我们注意到，我们的训练方法和 Google Brain 团队描述的 Downpour SGD 方法相似，不同之处在于我们训练的是单层模型而不是多层神经网络。这使得我们能够处理更大的数据集和更大的模型（模型具有数十亿个参数）。因为训练好的模型被复制到很多数据中心进行serving，因此我们更关心 serving 时的稀疏化，而不是训练期间的稀疏化。
我们系统的整体框架如图所示：
- Probalistic Feature Inclusion：概率性特征纳入模块，主要用于降低特征数量来优化内存。
- Parallelized Model Training：多模型并行训练模块，主要用于超参数选择中，提高多模型并行训练的效率。
- Calibration：模型校准模块，主要用于校准模型的系统性预测 bias。
- Progressive Validation Metrics：模型性能分析模块，主要用于分析模型在验证集上的性能。
- Model Serving Replicas：模型部署模块，主要用于部署模型到线上。

6.2 在线学习和稀疏性

6.2.1 FTRL-Proximal

$\mathbf{\vec x}$ 可能有数十亿维，但是通常每个样本只有数百个非零值。这可以通过从磁盘或网络的流式样本 streaming examples 来对大型数据集进行有效的训练，因为每个训练样本只需要考虑一次。
如果我们采用逻辑回归来建模，那么我们可以使用以下在线框架。
$t$ $\mathbf{\vec x}_t\in \mathbb R^d$ $\mathbf{\vec w}_t$ $p_t = \sigma\left(\mathbf{\vec w}_t\cdot \mathbf{\vec x}_t\right)$ $\sigma(\cdot)$ 为 sigmoidlabel $y_t\in \{0,1\}$ ，那么 logloss 为：
$\mathcal l_t(\mathbf{\vec w}_t) = -y_t\log p_t - (1-y_t)\log (1-p_t)$
显然有：
$\nabla_{\mathbf{\vec w}_t} \mathcal l_t = \left(\sigma\left(\mathbf{\vec w}_t\cdot \mathbf{\vec x}_t\right)-y_t\right)\mathbf{\vec x}_t = (p_t - y_t) \mathbf{\vec x}_t$
online gradient descent: OGD $\mathbf{\vec w}$ 中非零权重的数量是内存占用的决定因素。
不幸的是，OGD 在生成稀疏模型方面并不是特别有效。事实上，简单地将 L1 正则化添加到损失函数中，基本上永远不会产生完全为零的权重。更复杂的方法，如 FOBOS 和梯度截断，确实成功地引入了稀疏性。和 FOBOS 相比，Regularized Dual Averaging: RDA 算法产生了更好的准确性accuracy 和稀疏性sparsity 的tradeoff。
然而，我们已经观察到梯度下降风格的方法可以在我们的数据集上产生比 RDA 更好的准确性。那么，我们能否同时获得 RDA 提供的稀疏性和 OGD 提供的准确性？答案是肯定的，使用 Follow The (Proximally) Regularized Leader: FTRL-Proximal 算法。在没有正则化的情况下，FTRL-ProximalOGD $\mathbf{\vec w}$ 的alternative lazy representation， L1 正则化可以更有效地实现。
FTRL-Proximal 算法在另一篇论文中（《Follow-the-regularized-leader and mirror descent: Equivalence theorems and L1 regularization》）以便于理论分析的方式构建。这里我们专注于描述一个实际的实现。
$\mathbf{\vec g}_t\in \mathbb R^d$ ，OGD 的更新为：
$\mathbf{\vec w}_{t+1} = \mathbf{\vec w}_t - \eta_t\mathbf{\vec g}_t$
$\eta_t$ 为 non-increasinglearning rate schedule $\eta_t = 1/\sqrt{t}$ 。
$\mathbf{\vec g}_{1:t} = \sum_{s=1}^t \mathbf{\vec g}_s$ ，那么FTRL-Proximal 算法使用以下更新：
$\mathbf{\vec w}_{t+1} = \arg\min_{\mathbf{\vec w}} \left( \mathbf{\vec g}_{1:t} \cdot \mathbf{\vec w} + \frac 12\sum_{s=1}^t\sigma_s\left\|\mathbf{\vec w} - \mathbf{\vec w}_s\right\|_2^2 + \lambda_1\left\|\mathbf{\vec w}\right\|_1\right)$
$\sigma_s$ $\sum_{s=1}^t \sigma_s = 1/\eta_t$ 。
从表面上来看，FTRL-ProximalOGD $\lambda_1=0$ $\lambda_1\gt 0$ 的 FTRL-Proximal 更新在产生稀疏性方面做得更好（参考下面实验的结果）。
FTRL-Proximal $w_i$ 对应一个值），因为我们可以将 argmin 重写为：
$\left(\sum_{s=1}^t (\mathbf{\vec g}_s-\sigma_s\mathbf{\vec w}_s)\right)\cdot \mathbf{\vec w} + \frac {1}{\eta_t} \left\|\mathbf{\vec w} \right\|_2^2 + \lambda_1\left\|\mathbf{\vec w}\right\|_1 +\text{const}$
$\mathbf{\vec z}_{t-1} = \sum_{s=1}^{t-1} (\mathbf{\vec g}_s-\sigma_s\mathbf{\vec w}_s)$ ，则有：
$\mathbf{\vec z}_t = \mathbf{\vec z}_{t-1} + \mathbf{\vec g}_t -\left(\frac{1}{\eta_t} -\frac{1}{\eta_{t-1}} \right) \mathbf{\vec w}_t$
$\mathbf{\vec w}_{t+1}$ 的解可以 per-coordinate 来计算到：
$w_{t+1,i} = \begin{cases} 0,& \text{if}\quad |z_{t,i}|\lt \lambda_1\\ -\eta_t(z_{t,i}-\text{sgn}(z_{t,i})\lambda_1),&\text{else} \end{cases}$
$i=1,2,\cdots,d$ 。
FTRL-Proximal $\mathbf{\vec z}\in \mathbb R^d$ OGD $\mathbf{\vec w}\in \mathbb R^d$ per-coordinate $\lambda_2$ 的 L2 正则化。
$-\eta_t\mathbf{\vec z}_t$ $\mathbf{\vec z}_t$ $\lambda_1=0$ $\mathbf{\vec w}_{t+1}$ 。
$\eta_t=\eta$ $\lambda_1=0$ 时，很容易看出FTRL-Proximal 等于 OGD，因为我们有：
$\mathbf{\vec w}_{t+1} = -\eta\mathbf{\vec z}_t = -\eta\sum_{s=1}^t \mathbf{\vec g}_s\Longrightarrow \mathbf{\vec w}_{t+1} = \mathbf{\vec w}_{t} - \eta\mathbf{\vec g}_t$
这正是梯度下降所起到的作用。
Per-Coordinate FTRL-Proximal 的逻辑回归算法（带 L1 正则化和 L2 正则化）：
- 输入：
  - $\alpha,\beta,\lambda_1,\lambda_2$
  - $\mathbb D=\left\{(\mathbf{\vec x}_t,y_t)\right\}_{t=1}^T$
- $\mathbf{\vec w}$
- 算法步骤：
  - $\mathbf{\vec z}_0=\mathbf{\vec 0}\in \mathbb R^d ,\mathbf{\vec n}=\mathbf{\vec 0}\in \mathbb R^d$ $\mathbf{\vec n}$ 存储累计梯度向量。
  - $t=1,\cdots,T$ ，迭代步骤为：
    - $\mathbf{\vec x}_t$ $\mathbb I=\{i\mid x_{t,i}\ne 0,1\le i\le d\}$ 为当前样本的非稀疏特征集合。
    - $i\in \mathbb I$ 有
      $w_{t,i} = \begin{cases} 0,& \text{if}\quad |z_{t-1,i}|\lt \lambda_1\\ -\left(\frac{\beta+\sqrt{n_i}}{\alpha}+\lambda_2\right)^{-1}(z_{t-1,i}-\text{sgn}(z_{t-1,i})\lambda_1),&\text{else} \end{cases}$
      $\eta_{i} = \left(\frac{\beta+\sqrt{n_i}}{\alpha}+\lambda_2\right)^{-1}$ $n_i$ $t$ 相关的。
    - $p_t = \sigma\left(\mathbf{\vec x}_t\cdot \mathbf{\vec w}_{t}\right)$ 。
    - labey $y_t\in \{0,1\}$ 。
    - $i\in \mathbb I$ 有
      $g_{t,i} = (p_t - y_t) x_{t,i} \\ \sigma_{i}=\left(\frac{1}{\eta_{i}} - \frac{1}{\eta_{i-1}}\right) = \frac{1}{\alpha}\left(\sqrt{n_i + g_{t,i}^2}-\sqrt {n_i}\right)\\ z_i\leftarrow z_i + g_{t,i}-\sigma_i w_{t,i}\\ n_i=n_i+g_{t,i}^2$
FTRL-Proximal 优化算法的实验结果如下表所示。评估指标为 AucLoss = 1- AUC。考虑到损失一般是越小越好，而 AUC 是越大越好，因此我们采用 1 - AUC 。
OGD-Count $k$ $k$ $k$ FTRL-Proximal $k$ 会导致更差的 AucLoss。
可以看到：在模型大小和准确性 tradeoff 方面，带 L1 正则化的 FTRL-Proximal 显著优于 RDA 和 FOBOS。
总体而言，这些结果表明 FTRL-Proximal 显著改善了稀疏性，同时具有相同或更好的预测准确性。

6.2.2 per-coordinate 学习率

OGD $\eta_t = 1/\sqrt t$ ，该学习率对于所有 coordinates 都是相同的。我们在 FTRL-Proximal 中采用 per-coordinate 学习率：
$\eta_{t,i} = \frac{\alpha}{\beta+\sqrt{\sum_{s=1}^t g_{s,i}^2}}$
该学习率在某种意义上几乎是最优的 near-optimal 。
- $\alpha$ $\beta$ 从而得到良好的性能。根据经验：
  - $\alpha$ 的最佳值根据特征和数据集的不同而有很大差异。
  - $\beta = 1$ 通常就足够了，这只是确保早期的学习率不会太高。
- $\sum_{s=1}^t g_{s,i}^2$ 使用 0.5 以外的幂次。
如前所述，Per-Coordinate FTRL-Proximal 算法要求我们跟踪每个特征的累计梯度、以及累计平方梯度。后面会介绍另一种节省内存的公式，其中累计平方梯度在多个模型上均摊。
我们通过测试两个相同的模型来评估 per-coordinateper-coordinate $\alpha$ 为每个模型单独调优。
我们在一个有代表性的数据集上运行，并使用 AucLoss 作为我们的评估指标。结果表明：与全局学习率 baseline 相比，使用 per-coordinate 学习率将 AucLoss 降低了 11.2%。在我们的设置中，AucLoss 降低 1% 就被认为是很大的。

6.3 内存优化

如前所述，我们使用 L1 正则化从而节省预测期间的内存。在这里，我们将描述在训练期间节省内存的其它技巧。
特征优化：在很多具有高维数据的领域中，绝大多数特征都是极为稀疏的。事实上在我们的一些模型中，一半的 unique 特征在数十亿个样本的整个数据集中仅出现一次。
跟踪这些稀疏特征的统计数据是昂贵的，这些特征永远不会有任何实际用途。不幸的是，我们事先不知道哪些特征将是稀疏的。预处理数据从而去除稀疏特征在 online setting 中是有问题的：
- 额外读取然后写入数据的代价非常昂贵。
- $k$ 次），则不再尝试使用这些特征建模，从而难以评估预处理在准确性方面的代价。
一类方法通过 L1 正则化来实现训练中的稀疏性，不需要跟踪特征的任何统计。随着训练的进行，这允许删除信息较少的特征。然而我们发现，与在训练中跟踪更多特征、并仅为 serving 进行稀疏化的方法（如 FTRL-Proximal ）相比，这种稀疏化方式导致了不可接受的准确性损失。
我们探索的另一类方法是概率性的特征纳入 probabilistic feature inclusion ，其中新特征在首次出现时以概率方式纳入模型中。这实现了预处理数据的效果，但是可以在 online setting 中执行。我们为该方法测试了两种实现方式：
- Poisson Inclusion $p$ $1/p$ 的几何分布。
- Bloom Filter Inclusioncounting Bloom filters $n$ $n$ 次（根据过滤器），我们将其添加到模型中，并将其用于后续观察中的训练。
  注意，该方法也是概率性的，因为 counting Bloom filters 可能会出现false positivesfalse negatives $n$ 次的特征。
这些方法的实验效果如下表所示。可以看到：这两种方法都运行良好，但是布隆过滤器方法为 RAM 节省和预测质量损失提供了更好的 tradeoff 。
固定精度浮点数：通常我们用 32位或者64位浮点数来存储模型参数。实际中发现：几乎所有的参数取值都在 [-2, +2] 之间。同时，分析表明：对模型参数取如此高的精度完全没有必要。这促使我们探索使用 16 位固定精度的 q.23 编码，而不是浮点编码。在 q2.13 编码中：1个bit 表示正负、2个 bit 表示整数部分、13个 bit 表示小数部分。
采用16位浮点数带来的精度下降会导致 OGD 过程中产生累积舍入误差。事实上在使用 32位浮点数（而不是 64 位浮点数）时，我们也能够观察到舍入误差。一个简单的随机舍入策略可以缓解该问题：
$\tilde w_i = 2^{-13}\lfloor 2^{13} w_i +R \rfloor$
其中：
- $w_i$ 为原始的参数。
- $\tilde w_i$ 为引入随机舍入策略调整后的参数，它以 q2.13 格式存储。
- $R$ 为一个随机数，它从 0~1 均匀分布随机采样。
最终在没有损失模型预测能力的情况下，相比于 64 位双精度浮点数，采用 q2.13 精度之后模型大小降低了 75%。
多模型并行训练：有时候我们需要训练多个模型，这些模型采用相同的算法但是不同的超参数来训练，这些模型称作变种模型。最后选择最佳的超参数及对应的模型。
一种简单的方式是：先用给定的算法训练好一个模型，然后用该模型作为变种模型的初始化点来训练变种模型。这种方式比较简单，容易实现。但是缺点是：无法处理特征裁剪、或者学习率调整等场景。
实际上有一些数据可以在多个模型之间共享，如：训练样本。另一些数据无法在多个模型之间共享，如：每个模型的参数值。我们可以在同一张哈希表中存储每个模型的参数值，从而分摊存储 key（一个字符串或者哈希后的数值）的成本。
任何不具有指定特征的变体都会将该特征的权重存储为零，从而浪费少量空间。此外，我们将这些特征的学习率设为零。这使得我们可以同时并行训练多个模型，所有 per-coordinate 元数据的平摊成本被降低。通过这种方式不仅节省了内存，还节省了网络带宽（因为每个样本只需要读取一次）、节省 CPU（只需要查找一个哈希表，并且从训练数据中只需要生成一次特征而不是每个模型一次）、以及节省磁盘。
单值结构Single Value Structure ：有时我们希望一起评估非常多的模型变体的集合，这些变体仅通过添加或删除一小部分特征而不同。在这里，我们可以使用一种更为压缩的数据结构，这种结构既有损lossy又特别，但实际上却给出了非常有用的结果。
这个 Single Value Structure 仅为 per-coordinate 存储一个权重值，该值由包含该特征的所有模型变体共享，而不是为每个模型变体存储单独的权重值。一个 bit-field 用于跟踪哪些模型变体包含给定的特征。注意，这在本质上 《Fast prediction of new feature utility》 的方法相似，但是也允许评估特征删除和特征添加。和多模型并行训练相比，增加模型变体的 RAM 成本增长要慢得多。
OGD $i^*$ 由所有变种模型共享）：
- 计算所有变种模型在该维度的参数更新值：
  $w^{(m)}_{t+1,i^*} = w_{t,i^*} - \eta_{t,i^*} ^{(m)}\times g_{t,i^*}^{(m)},\quad m=1,2,\cdots,M$
  $M$ $w_{t,i^*}$ $i^*$ $w^{(m)}_{t,i^*}$ $m$ 的具体参数。
- 计算最新的共享参数值：
  $w_{t+1,i^*} = \frac{\sum_{m=1}^M w^{(m)}_{t+1i^*} }{M}$
我们对比了使用 Single Value Structure 训练的大量模型变体和使用多模型并行训练的相同变体。结果显示：不同变体的相对性能几乎相同，但是 Single Value Structure 在 RAM 占用方面中节省了一个数量级。
学习率计算：如前所述，我们需要存储每个特征的累计梯度、以及累计平方梯度。虽然可以通过精确地计算梯度来得到学习率的准确值，但是可以对学习率计算进行粗略的近似。
$i^*$ $i^*$ $P$ $N$ $p = \frac{P}{N + P}$ 。设我们采用逻辑回归模型，则有梯度：
$g_{i^*} = (p-y)\times x_{i^*}$
one-hot $i^*$ $x_{i^*} = 1$ $y=1$ $g_{i^*} = p-1$ $y=0$ $g_{i^*} = p$ coordinate $i^*$ 的累计平方梯度为：
$\sum_{s=1}^t g_{s,i^*}^2 = \sum_\text{click}(p_s-1)^2 + \sum_\text{noclick} p_s^2 \simeq P\times (1-p)^2 + N\times p^2\\ = P\times \left(1 - \frac{P}{N+P}\right)^2 + N\times\left(\frac{P}{N+P}\right)^2 = \frac{PN}{P+N}$
$p_t = p$ 是固定的。
coordinate $i^*$ 的学习率为：
$\eta_{t,i^*} = \frac{\alpha}{\beta+\sqrt{\sum_{s=1}^t g_{s,i^*}^2}} = \frac{\alpha}{\beta+\sqrt{PN/(P+N)}}$
因此可以基于每个特征上发生的点击/不点击计数来近似累计平方梯度，从而调整学习率。允许这样做的原因：学习率是模型的超参数，其取值不必非常精确。实验表明：这种方式得到的学习率，与采用累计平方梯度得到的学习率，二者表现相当。
$N,P$ 的成本被摊销，总的存储成本较低。
另外，计数可以使用可变长度 bit 编码，并且绝大多数特征不需要很多 bit 。这可以进一步降低存储成本。
训练数据降采样：在典型的推荐、搜索等场景中，点击率CTR 通常远低于 50%CTR $r$ $r\in (0,1]$ 。
1 $1/r$ $s_j$ $j$ 1 $r$ $\beta_j$ 1 $1/r$ ），那么：
$\mathbb E[\mathcal l_j(\mathbf{\vec w})] = s_j\beta_j\mathcal l_j(\mathbf{\vec w}) = l_j(\mathbf{\vec w})$
这意味着：降采样训练数据上的期望加权损失函数等于原始数据集上的损失函数。
$r$ $r$ 值无关。

6.4 模型评估

虽然可以直接利用实时流量来评估模型效果，但是这种评估的代价太大：在实时流量中上新模型可能会降低这些流量的收入，因为新模型的效果在评估之前是未知的，可能更好、但是大多数情况下是更坏。
可以通过历史日志来评估模型效果。由于不同的评估指标衡量了模型在不同方面的能力，因此我们评估了一组指标：aucloss（即：1-auc）、logloss、平方误差。为了保持一致性，这些指标都是越小越好。

6.4.1 渐进式验证

我们通常使用渐进式验证 progressive validation（有时称作在线损失），而不是交叉验证、也不是在 hold out 数据集上评估。因为学习过程中计算梯度无论如何都需要计算一个 prediction，所以我们可以低成本地将这些 prediction 以每小时汇总的方式输出，用于后续分析。我们还根据各种数据 sub-slices 计算这些指标，例如按照国家、query 主题、layout 等进行细分。
$(\mathbf{\vec x}_t,y_t)$ oneline learning $p_t$ $l_t$ $\mathbf{\vec g}_t$ $p_t$ 记录下来供后续的模型评估。
- 我们每个小时汇总一次，得到该小时内每个样本的真实值、预测值。基于这些数据得到小时级别的模型评估指标。因此可以得到随时间推进的模型能力变化趋势。
- $(\mathbf{\vec x}_{t-1},y_{t-1})$ $(\mathbf{\vec x}_t,y_t)$ $(\mathbf{\vec x}_{t},y_{t})$ $(\mathbf{\vec x}_{t+1},y_{t+1})$ 、... 。这使得我们可以将 100% 的数据用于训练和验证。相比较于传统的交叉验证只有部分数据用于验证，这里的验证集更大，得到的验证结果也更具有统计意义。
  这很重要，因为某些性能的改进可能需要在大规模的验证集上评估才有意义（如：改进可能很小，比如千分之五），置信度才比较高。
用绝对值来评估模型能力可能会产生误导。假如某个场景点击率是 50%，另一个场景点击率是 2% 。事实上前者的 logloss 的绝对值可能会超过后者，因为 logloss 及其它指标可能会根据问题的难度（即贝叶斯风险）而变化。
这个问题非常重要。因为 CTR 会根据不同国家/地区、以及 query 而不同。query 在一天中的不同时段的分布不同，因此评估指标的均值会在一天之内发生变化。
因此我们更关注相对变化：模型的评估指标相对于 baseline 的变化。根据我们的经验，随着时间的推进，相对变化会更加稳定。
需要注意的是：我们必须在同一批数据上产生的同一个指标才有比较意义。如：A 模型在某个时间段上得到的模型指标，和 B 模型在另一个时间段上得到的模型指标之间不可比较。因为 A 模型和 B 模型的评估数据都不同。

6.4.2 通过可视化加深理解

大规模机器学习的一个隐藏陷阱是：统计指标可能受到数据中某些属性分布的影响。如：给定一个验证集，模型 A 的准确率比模型 B 更高。很有可能该验证集中 “女性” 用户非常多，而模型 A 对于 “女性” 用户的预测比模型 B 更准。
因此我们不仅要给出模型在整体验证集上的评估指标，还要在验证集数据的每个切片 slice 上给出评估指标。如：模型在每个国家上的评估指标、模型在每个性别上的评估指标、模型在每个主题上的评估指标 .... 。
因为有数百种方法可以对数据进行有意义的切片，所以我们必须能够有效地检查数据的可视化 summary。为此，我们开发了一种称为 GridViz 的高维交互式可视化，可以全面了解模型性能。来自 GridViz 的一个视图的截图如下图所示，该图展示了baseline 模型相比，三个模型（不包括 baseline 模型）的一组根据 query 主题的切片。其中 AucLoss 和 LogLoss 的结果基于一系列 query 主题来计算。
- 指标值由彩色单元格表示，行与模型名称相对应，列与数据的每个 unique 切片相对应。
- 列的宽度表示切片的重要性，并且可以设置为反映诸如曝光次数、或点击次数之类的统计量。下图中，列宽反映了曝光次数。
- 单元格的颜色反映了与 baseline 相比的指标值，这有助于快速扫描异常值和感兴趣的区域，从而直观地了解整体性能。
  - 当列足够宽时将显示所选指标的数值，否则所选指标数值不展示。
  - 可以选择多个指标，这些指标将一起显示。
- 当用户将鼠标悬停在单元格上之时，会弹出给定单元格的详细报告。
- 由于存在数百种可能的切片，我们设计了一个交互式界面，允许用户通过下拉菜单或切片名称正则化表达式选择不同的切片。
- 可以对列进行排序并修改色标的动态范围从而适配手头的数据。
总体而言，该工具使得我们能够显著提高我们对各种数据集的模型性能的理解深度，并确定需要改进的高影响区域。

6.5 置信度

对很多application，重要的是不仅要预估广告的点击率，还要量化预估的置信度。置信度可以用于衡量和控制 explore-exploit tradeoffs。通常采用置信区间confidence intervals 来评估不确定性，但是在这里不适用：
- 标准的方法用于评估完全收敛的 batch 学习模型，且没有正则化。
  而 FTRL 模型是在线学习，不再满足独立同分布 IID 的样本假设，因此甚至无法定义收敛性。并且模型是经过正则化的。
- 标准的方法需要求解一个 n x n 矩阵的逆，这里 n 的规模达到数十亿甚至百亿，因此无法计算。
- 此外，至关重要的是，任何置信度估计都需要在预测时以极低的成本进行计算。也就是说，置信度估计的耗时和预估本身的耗时差不多。
为此，我们提出了一种称之为不确定性得分uncertainty score 的启发式方法，它在计算上易于处理，并且在衡量预估准确性的质量方面做得很好。
uncertainty scoreper-coordinate $n_{t,i}=\sum_{s=1}^t g_{s,i}^2$ $\eta_{t,i} = \frac{\alpha}{\beta+\sqrt{n_{t,i}}}$ $n_{t,i}$ 较大的特征获得了较小的学习率，正是因为我们相信当前的权重更有可能是准确的。
1 $|x_i| \le 1$ $g_i = (p_t - y_t)\times x_i$ $y_t\in \{0,1\}, 0\le p_t \le 1$ $|g_i| \le 1 \times 1 = 1$ 。
$\lambda_1=\lambda_2=0$ ，因此 FTRL-ProximalOGD $\mathbf{\vec x}$ ，其预估的不确定性为：
$|\mathbf{\vec x}\cdot \mathbf{\vec w}_t - \mathbf{\vec x}\cdot \mathbf{\vec w}_{t+1} | \le \sum_{i:|x_i| \ne 0} \eta_{t,i} |g_{t,i}|\times x_i\le \sum_{i:|x_i| \ne 0} \eta_{t,i} \times x_i =\vec\eta_t \cdot \mathbf{\vec x}$
$\mathbf{\vec x}$ $u(\mathbf{\vec x}) = \mathbf{\vec \eta}_t \cdot \mathbf{\vec x}$ 。这种方式定义的置信度指标计算非常方便。
$\mathbf{\vec w}$ 非常稳定，在前后两次迭代之间的变化几乎为零。

为验证这种置信度指标的有效性，我们执行以下实验：
- $\mathbb D$ 上训练模型 A ，但是使用稍微不同的特征。
- $y$ A $p(\mathbf{\vec x})$ $y$ $\mathbb D_p$ 。
- $\mathbb D_p$ 上用 FTRL 算法训练模型 B 。
- $\mathbf {\vec x}$ ，假设模型 A 的预测结果为 pB $\tilde p$ 。则得分误差为：
  $e(\mathbf{\vec x}) = |\sigma^{-1}(p) - \sigma^{-1}(\tilde p) |$
  $\sigma^{-1}$ $\sigma(z) = \frac{1}{1+\exp(-z)}$ $\mathbf{\vec x} \times \mathbf{\vec w}$ 。
  $e(\mathbf{\vec x})$ 的物理意义为：由于标记噪声的引入，导致模型预测的波动范围。
- $u(\mathbf{\vec x})$ $e(\mathbf{\vec x})$ 相符。
$e$ $u$ ，x/y 轴归一化成 0~125%, 50%, 75% $e$ $u$ 成正向关系：得分误差越大，不确定性得分越大。
$u(\mathbf{\vec x})$ $e(\mathbf{\vec x})$ 比较匹配，而且置信度指标计算量非常小。

6.6 模型校正

准确的、且经过良好校正 calibration 的 CTR 预估不仅对于竞价至关重要，还允许将竞价中的优化问题（如拍卖机制优化、出价优化）和机器学习问题解耦。
很多因素可能会导致模型产生系统性偏差，如：模型的前提假设不成立、优化算法本身的缺陷、训练或预测期间无法获取某些重要特征。为解决该问题，我们提出 calibration layer 来校正预测的 CTR ，使得预测 CTR 和经验 CTR 适配。
$\mathbb D$ CTR $p$ $\mathbb D$ CTR $q$ $p \simeq q$ bias $q-p$ 。
$\pi_{\mathbb D} (p)$ CTR $q$ 。
$\pi_{\mathbb D}(p) = \gamma\times p^{\kappa}$ $\gamma,\kappa$ $\mathbb D$ 上学习。
bias $\pi(\cdot)$ 是单调递增函数。如：采用 isotonic 回归。这种方式的优点是通用性更强，无论平均预测 CTR 较高还是较低，它都能很好的校正。
值得注意的是，如果没有很强的、额外的假设，系统中固有的反馈回路使得我们无法为校正的影响impact 提供理论上的保证。
对于数据集，我们通常需要对不同数据区间对应的子集进行校正。因为很有可能模型对 “女性” 用户预测的平均 CTR 偏高，对“男性”用户预测的平均 CTR 偏低，但是整体预测的平均 CTR 较好。这时我们需要分别针对 “女性” 用户、“男性” 用户分别进行模型校正。

6.7 自动特征管理

可扩展scalable 的机器学习的一个重要方面是管理 installation 的规模，包括构成机器学习系统的所有配置、开发人员、代码、计算资源。一个有趣的案例是机器学习特征空间的管理。
我们可以将特征空间刻画为上下文和语义的一组信号，其中每个信号（例如“广告中的单词”、“原产国”等等）都可以转换为一组实值特征以供学习。在大多数系统中，许多开发人员可能会异步地进行信号开发。一个信号可能有许多版本，比如特征升级。工程团队可能会消费那些并不是他们直接开发的信号。信号可以在多个不同的学习平台上使用，并应用于不同的学习问题。
为了处理 use cases 的组合增长，我们部署了元数据索引，用于管理数百个活跃模型对数千个输入信号的消费。
- 索引会针对各种问题被手动或自动地注释，比如废弃、特定于某些平台、特定于某些领域。
- 新模型和活跃模型消费的信号由自动告警系统审核。
- 不同学习平台共享一个通用的接口，用于向中央索引报告信号消费。
- 当一个信号被废弃时（例如，当有新版本可用时），我们可以快速识别信号的所有消费者并跟踪替换操作。当信号的改进版本可用时，可以提醒消费者尝试新版本。
- 新信号可以通过自动测试进入审核，并列入白名单以供纳入。白名单既可用于确保生产系统的正确性，也可以用于使用自动特征选择的学习系统。
- 没有任何消费者的信号自动标记，从而自动进行代码清理和相关数据的删除。
有效的自动化信号消费管理可以确保在第一时间内正确地完成更多的学习。这减少了浪费和重复的工程工作，节省了很多工程时间。在运行学习算法之前验证配置的正确性，可以消除很多模型不可用的情况，从而节省大量潜在的资源浪费。

6.8 无效的探索

这里我们简要报告几个（可能令人惊讶）没有产生显著收益的方向。
积极的特征哈希 Aggressive Feature Hashing：近年来，出现了一系列工作围绕使用特征哈希来降低大规模机器学习的内存成本。我们测试了这种方法，但是发现：这种方式会带来模型预测能力的明显下降，因此无法应用。
dropout：基于 dropout 的正则化并不会带来任何好处，甚至会降低模型预测能力。其根本原因是：在 CTR预估任务中数据特征非常稀疏，经过 dropout 之后更为稀疏。
在计算机视觉任务中，输入特征是非常密集的，且标签是比较干净的。此时 dropout 将高度相关的特征分离开，从而产生更健壮的分类器。
而在 CTR 预估任务中，输入特征是非常稀疏的，且标签是带噪音的。此时 dropout 会显著降低学习的数据量，降低学习效果。
Feature Bagging $k$ $k$ $k$ $k$ 个模型的预测均值为该样本的预测结果。这是一种管理 bias-variance tradeoff 的潜在有效方法。该方法略微降低模型预测能力，大约损失 AucLoss 的 0.1%到 0.6% 。
Feature Vector Normalization $\frac{\mathbf{\vec x} }{ ||\mathbf{\vec x}||}$ ，最终效果不理想。我们猜测原因是：per-coordinate 的学习率和样本归一化相互作用，导致效果下降。

七、LS-PLM 模型[2017]

点击率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 模型。
- 稀疏性sparsityonline serving $L_1$ $L_{2,1}$ 正则化的 LS-PLM 可以实现良好的稀疏性。
带有稀疏正则化的 LS-PLM 的学习可以转化为一个非凸、非可微的优化问题，这个问题很难解决。论文针对此类问题提出了一种基于方向导数directional derivatives 和拟牛顿法的有效优化方法。
由于能够捕获非线性模式、以及对海量数据的可扩展性，LS-PLM 已经成为阿里巴巴在线展示广告系统display advertising system 中的主力 CTR 预估模型，并从 2012 年初以来为数亿用户提供服务。它还应用于推荐系统、搜索引擎、以及其它产品系统。

7.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$
一种简单的情形是：
$\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$ 无法捕获足够多的非线性，因此该模型比较鸡肋。
下图说明了在一个 demo 数据集中，该 LS-PLM 和 LR 模型的差异。图 A) 是 demo 数据集，这是一个二分类问题，红点属于正类、蓝点属于负类。图 B) 显示了使用 LR 模型的分类结果，图 C) 显示了使用LS-PLM 模型的分类结果。可以清晰地看到 LS-PLM 能够捕获到数据中的非线性模式。
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 优化算法

定义方向导数为：
$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 。

如前所述，我们针对大规模 CTR 预估问题的目标函数既不是凸函数、也不是平滑函数。在这里，我们提出了一种通用且有效的优化方法来解决此类非凸问题。
$\mathbf \Theta$ $\mathbf v$ $f^\prime(\mathbf \Theta;\mathbf{ v} )$ $f^\prime(\mathbf \Theta;\mathbf{ v} )$ $\mathbf \Theta$ $\mathbf v$ 都存在，这就是下面的引理。
$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$ ，即右方向导数。
$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$
$\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})$
证明见原始论文。
受 OWLQNsign $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)}$ 决定的象限。
$\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}$ 的符号来改变。
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}^{<t >}\\ \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 模型实现

这里我们首先提供针对大规模数据的 LS-PLM 模型的并行实现，然后介绍一个有助于大大加快训练过程的重要技巧。
为了在大规模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 首先用本地数据和局部模型计算损失和下降方向（数据并行）。
- 然后 serverloss $\mathbf v^{(t)}$ $\mathbf \Theta^{(t+1)}$ $\mathbf\Theta^{(t+1)}$ (模型并行)。
- worker $\mathbf{\Theta}^{(t+1)}$ 。
除了通用并行实现之外，我们还优化了在线广告环境中的实现。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 实验

数据集：我们的数据集来自于阿里巴巴的移动展示广告产品系统。我们在连续的一段时间收集了七个数据集，旨在评估所提出模型的一致性consist 性能。在每个数据集中，训练集/验证集/测试集是从不同的日期不相交地收集的，比例约为 7:1:1 。我们的评估指标为 AUC。
数据集的详细数据如下表所示。
$M$ $M$ 的物理意义是区域数量，它控制了模型的容量。
$M$ 越大则模型容量越大，拟合能力越强，但是模型训练代价也越大。因此实际应用中必须在模型的拟合能力和训练成本之间平衡。
模型在数据集 1 上的结果如下图所示。我们测试了 M = 6,12,24,36。可以看到：
- $M=12$ AUC $M=6$ 。
- $M = 24,36$ AUC $M =12$ $M = 12$ 。

$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$ 表现最佳。
和 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 可以安全地部署到在线生产系统中。