传统CTR 预估模型

1. CTR 预估模型主要用于搜索、推荐、计算广告等领域的 CTR 预估，其发展经历了传统 CTR 预估模型、神经网络CTR 预估模型。

   传统 CTR 预估模型包括：逻辑回归LR 模型、因子分解机FM 模型、梯度提升树 GBDT 模型等。其优点是：可解释性强、训练和部署方便、便于在线学习。

   本章主要介绍传统 CTR 预估模型。

一、LR 模型[2007]

1. 在 cost-per-click:CPC 广告中广告主按点击付费。为了最大化平台收入和用户体验，广告平台必须预测广告的 CTR ，称作 predict CTR: pCTR 。对每个用户的每次搜索query，有多个满足条件的广告同时参与竞争。只有 pCTR x bid price 最大的广告才能竞争获胜，从而最大化 eCPM ：

   $$\text{eCPM} = \text{pCTR} \times \text{bid}$$

   基于最大似然准则可以通过广告的历史表现得统计来计算 pCTR 。假设广告曝光了 100次，其中发生点击 5次，则 pCTR = 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。

2. 从经验上来看：广告在页面上的位置越靠后，用户浏览它的概率越低。因此广告被点击的概率取决于两个因素：广告被浏览的概率、广告浏览后被点击的概率。

   因此有：

   $$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 数据集构造

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、但是不同的竞价词。

2. 数据集包含 1万个广告主，超过 1百万个广告、超过 50万竞价词（去重之后超过 10万个竞价词）。注意，不同的竞价词可能会展示相同的广告。

   • 样本的特征从广告基本属性中抽取（抽取方式参考后续小节）。广告的基本属性包括：

     • landing page 落地页：点击广告之后将要跳转的页面的 url。
     • bid term：广告的竞价词。
     • title：广告标题。
     • body：广告的内容正文。
     • display url：位于广告底部的、给用户展示的 url。
     • clicks：广告历史被点击的次数。
     • views：广告历史被浏览的次数。

   • 将每个广告的真实点击率 CTR 来作为 label 。

     考虑到真实点击率 CTR 无法计算，因此根据每个广告的累计曝光次数、累计点击次数从而得到其经验点击率 $\overline{\text{CTR}}$ 来作为 CTR 。

3. 为了防止信息泄露，训练集、验证集、测试集按照广告主维度来拆分。最终训练集包含 70% 广告主、验证集包含 10% 广告主、测试集包含 20% 广告主。每个广告主随机选择它的 1000个广告，从而确保足够的多样性。

   因为同一个广告主的广告之间的内容、素材、风格相似度比较高，点击率也比较接近。

4. 对于有专业投放管理的那些优质广告主，在数据集中剔除它们。因为：

   • 优质广告主的广告通常表现出不同于普通广告主的行为：

     • 两种广告主的广告具有不同的平均点击率
     • 优质广告主的广告的点击率方差较低（表现比较稳定）、普通广告主的广告的点击率方差较高（表现波动大）

   • 广告平台更关注于普通广告主，因为这些普通广告主的数量远远超过优质广告主的数量，而且这些普通广告主更需要平台的帮助。

5. 对于曝光量少于100的广告，在数据集中剔除它们。因为我们使用经验点击率 $\overline{\text{CTR}}$ 来近似真实 CTR 来作为 label ，对于曝光次数较少的广告二者可能相差很远，这将导致整个训练和测试过程中产生大量噪音。

   曝光阈值的选取不能太大，也不能太小：

   • 阈值太小，则导致 label 中的噪音太多。
   • 阈值太大，则离线训练样本（大曝光的广告）和在线应用环境（大量新广告和小曝光广告）存在gap，导致在线预测效果较差。

1.2 LR模型

1. 论文将 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$ 的效果最好。

2. 论文采取了一些通用的特征预处理方法：

   • 模型添加了一个bias feature，该特征的取值恒定为 1。即：将偏置项 $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 。

     注意：对于验证集、测试集的异常值截断过程中，每个特征的均值、方差使用训练集上的结果。

3. 评价标准：

   • 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 （均方误差）指标。

4. 模型不仅可以用于预测新广告的 pCTR ，还可以为客户提供优化广告的建议。

   可以根据模型特征及其重要性来给广告主提供创建广告的建议，如：广告标题太短建议增加长度。

1.3 特征工程

1.3.1 Term CTR Feature Set

1. 不同竞价词的平均点击率存在明显的差异，因此在预测某个广告的点击率时，相同竞价词的其它类似广告可能有所帮助。

   因此论文对此提出两个特征，称作相同竞价词特征集 Term CTR Feature Set 。

   对于广告 ad 的竞价词 term （记作 $\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

1. 预测某个广告的点击率时，相关竞价词的其它类似广告可能也有所帮助。

   如：广告 a 的竞价词是 “电脑”，广告 b 的竞价词是 “买电脑”，则广告 b 的点击率对于预测广告 a 的点击率是有帮助的。

2. 考虑竞价词的子集/超集。

   给定一个竞价词 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 shoes，则该广告属于t 的 $\mathbf R_{0,1}$
   • 如果广告的竞价词是 shoes，则该广告属于 t 的 $\mathbf R_{1,0}$
   • 如果广告的竞价词是red shoes，则该广告属于t 的 $\mathbf R_{0,0}$
   • 如果广告的竞价词是blue shoes，则该广告属于t 的 $\mathbf R_{1,1}$

3. 由 $\mathbf R_{m,n}(t)$ 的定义可知：

   • 广告集合 $\mathbf R_{0,0}$ 代表广告的竞价 term 和 t 完全匹配。
   • 广告集合 $\mathbf R_{m,0}$ 代表广告的竞价 term 比 t 少了 $m$ 个单词之外其它单词完全相同（不考虑词序）。
   • 广告集合 $\mathbf R_{0,n}$ 代表广告的竞价 term 比 t 多了 $n$ 个单词之外其它单词完全相同（不考虑词序）。

   假设 * 为任意数值，则定义：

   • $\mathbf R_{0,*}(t)$ 表示 t 的任何超集（不考虑词序）作为竞价term 的广告的集合。
   • $\mathbf R_{*,0}(t)$ 表示 t 的任何子集（不考虑词序）作为竞价term 的广告的集合。

4. 定义相关竞价词的一组特征，它们称为相关竞价词特征集 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

1. 即使是同一个竞价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个特征。

2. 某些特征可以出现在多个要素里，如：广告内容中美元符号数量。该特征可能会增加吸引力，但是会降低外观。

3. 除了以上5个内容要素，还有一个重要的内容要素：广告文本的单词。

   我们统计广告标题和正文中出现的 top 10000 个单词，将这1万个单词出现与否作为 unigram 特征。因为某些单词更容易吸引用户点击，因此unigram 特征能够弥补注意力要素遗漏的特征。

   注意：构造特征时，标题和正文的 unigram 分别进行构造。即：单词是否出现在标题中、单词是否出现在正文中。

   如下所示：单词 shipping 更倾向于在高 CTR 广告中出现，这意味着 shipping 更容易吸引用户点击。图中的三条曲线从上到下依次代表：

   • 每个单词在高 CTR 广告中出现的平均频次。
   • 每个单词在所有广告中出现的平均频次。
   • 每个单词在低 CTR 广告中出现的平均频次。

   

4. 以上5个内容要素，以及 unigram 特征一起构成了广告质量特征集 Ad Quality Feature Set。结果表明：

   • 该组特征能够显著提升性能，将测试集的 “平均 KL 散度” 提升约 3.8 % 。

   • 考虑去掉 unigram 特征，结果表明：

     • 仅仅 5 个因素的 81 个特征能够提升约 1.1 %。
     • unigram 特征能够提升约 2.7 % 。

   

1.3.4 Order Specificity Feature Set

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

   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 越高。

2. 为了考虑捕捉同一个订单内不同广告的联系，论文提出了订单维度特征集 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

1. 事实上可以通过使用外部数据来构造特征。

   如：给定一个竞价词term，可以通维基百科来判断它是否是一个众所周知的词，也可以通过同义词词库来查找其同义词等等。

   因此构建外部搜索数据特征集 Search Data Feature Set，其中包括：

   • 每个竞价词term，网络上该 term 出现的频率。

     这可以利用搜索引擎的搜索结果中包含该 term 的网页数量来初略估计。

   • 每个竞价词term，搜索引擎的query 中出现该term 的频率。

     这可以用近三个月搜索引擎的搜索日志中，query 里出现该 term 的数量来粗略估计。

   这两个特征离散化为 20个桶，仔细划分桶边界使得每个桶具有相同数量的广告。

   单独采用该特征集之后，测试集的 “平均 KL 散度” 提升约 3.1 % 。但是融合了前面提到的特征之后没有任何改进，这意味着该特征集相比前面的几个特征集是冗余的。

   

1.3.6 更多特征

1. 当独立的考虑每个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%。

2. 有几个特征探索方向：

   • 可以将广告的竞价词 term 进行聚类，从而提供广告之间的关系。这是从语义上分析竞价词term 的相似性。这组特征称作 Related Term Feature Set 。

   • 可以基于用户的 query 来构造特征。

     在完全匹配条件下竞价词和用户搜索词完全相同，但是在更宽松的匹配下竞价词和搜索词可能存在某种更广义的关联。此时了解搜索词的内容有助于预测广告的点击率。

     因此可以基于用户的搜索词 query term 来构建特征，如： query term 和 bid term 相似度、 query term 的单词数、query term 出现在广告标题/广告正文/落地页的频次。

   • 可以将落地页的静态排名和动态排名信息加入特征。如：用户访问落地页或者域名的频率、用户在落地页停留的时间、用户在落地页是否点击回退等等。

3. 一个推荐的做法是：在模型中包含尽可能多的特征。这带来两个好处：

   • 更多的特征带来更多的信息，从而帮助模型对于广告点击率预测的更准。

   • 更多的特征带来一定的冗余度，可以防止对抗攻击。

     广告主有动力来攻击特征来欺骗模型，从而提升广告的 pCTR ，使得他的广告每次排名都靠前。

     假设模型只有一个特征，该特征是 ”竞价词是否出现在标题“ 。广告主可以刻意将竞价词放置到广告标题，从而骗取较高的 pCTR 。

     一旦模型有多个特征，那么广告主必须同时攻击这些特征才能够欺骗模型。这种难度要大得多。

1.4 特征重要性

1. 由于模型采用逻辑回归，因此可以直观的通过模型权重看到哪些特征具有最高权重、哪些特征具有最低权重。

   模型的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}$ 负相关。

2. 在 unigram features 中，top 10 和 bottom 10 权重对应的特征如下。

   可以看到：

   • 排在前面的是更为成熟established 的实体词，如 official,direct,latest,version 。
   • 排在后面的是更为吸引眼球的实体词，如 quotes, trial, deals, gift, compare 。

   从经验上看：用户似乎更愿意点击声誉更好的、更成熟的广告，而不愿意点击免费试用、优惠类的广告。

   

1.5 曝光量

1. 假设模型能准确预估广告的点击率，一个问题是：广告经过多少次曝光之后，观察到的点击率和预估的点击率接近。

   定义观察到的点击率为：

   $$\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 散度不同。

2. baseline 和 LR 模型的 EAE 结果如下所示。可以看到：

   • 在广告的曝光量超过 100时，baseline 和 LR 模型的 EAE 几乎相同。
   • 在广告的曝光量小于 50 时，LR 模型的EAE 更低。

   因此模型对于曝光量100以内的广告具有明显优势。这也是前面预处理将 100次曝光作为阈值截断的原因。

   对于百万级别广告的广告系统，如果在广告曝光的前100次期间对广告的CTR 预估不准，则导致这些广告以错误的顺序展示，从而导致收入减少和用户体验下降。

   

3. 预处理选择 100 次曝光作为截断阈值，是希望样本的观察 CTR 具有合理的置信水平。

   事实上有一些广告系统更关注于曝光量更大的广告，希望对这些广告能够预测更准确。更大曝光量意味着label 中更少的噪音，模型会学习得效果更好。

   但是这也意味着广告样本不包含那些被系统判定为低价值的广告，因为系统没有给这些低价值广告足够多的曝光机会。

   当曝光阈值提升到 1000次时，模型效果如下。可以看到：曝光量超过1000的广告比曝光量100的广告，模型预测效果（以测试集的平均KL 散度为指标）提升了 40%左右（ (41.88-29.47)/29.47 ）。

   

二、POLY2 模型[2010]

1. LR 模型只考虑特征之间的线性关系，而POLY2 模型考虑了特征之间的非线性关系。

   • 捕获非线性特征的一个常用方法是采用核技巧，如高斯核RBF，将原始特征映射到一个更高维空间。在这个高维空间模型是线性可分的，即：只需要考虑新特征之间的线性关系。

     但是核技巧存在计算量大、内存需求大的问题。

   • 论文 《Training and Testing Low-degree Polynomial Data Mappings via Linear SVM》 提出多项式映射 polynomially mapping 数据的方式来提供非线性特征，在达到接近核技巧效果的情况下大幅度降低内存和计算量。

2. 设低维样本空间为 $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)$ 的表达更简洁。

3. 如果不用核技巧，仅仅考虑使用一个多项式进行特征映射，则我们得到：

   $$\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}$ 个。

4. POLY2 模型的优缺点：

   • 优点：除了线性特征之外，还能够通过特征组合自动捕获二阶特征交叉产生的非线性特征。

   • 缺点：

     • 参数太多导致计算量和内存需求发生爆炸性增长。

       如计算广告场景中，原始样本特征可能达到上万甚至百万级别，则特征的交叉组合达到上亿甚至上万亿。

     • 数据稀疏导致二次项参数训练困难，非常容易过拟合。

       参数 $w_{i,j}$ 的训练需要大量的 $x_i,x_j$ 都非零的样本。而大多数应用场景下，原始特征本来就稀疏（非零的样本数很少），特征交叉之后更为稀疏（非零的样本数更少）。这使得训练 $w_{i,j}$ 的样本明显不足，很容易发生过拟合。

三、FM模型[2011]

1. 推荐系统中的评级预测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 ，它依赖于 Tucker 分解并允许使用任何离散型上下文categorical 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 相关工作

1. 推荐系统的大多数研究都集中在仅分析 user-item 交互的上下文无关方法上。在这里，矩阵分解matrix factorization: MF方法非常流行，因为它们通常优于传统的 knn 方法。

   也有研究将用户属性或 item 属性等元数据结合到预测中，从而扩展了矩阵分解模型。然而，如果存在足够的反馈数据，元数据对评分预测的强 baseline 方法通常只有很少或者没有改善。这种用户属性/item 属性和上下文之间的区别在于：属性仅仅被附加到 item 或者用户（例如，给电影附加一个流派的属性），而上下文被附加到整个评级事件（如，当评级发生时用户当时的心情）。

   和关于标准推荐系统的大量文献相比，上下文感知推荐系统的研究很少。最基本的方法是上下文预过滤pre-filtering 和后过滤 post-filtering，其中应用标准的上下文无关推荐系统，并在应用推荐器recommender 之前基于感兴趣的上下文对数据进行预处理、或者对结果进行后处理。更复杂的方法是同时使用所有上下文和 user-item 信息来进行预测。

   也有人建议将上下文视为动态的用户特征，即可以动态变化。另外有一些关于 item 预测的上下文感知推荐系统的研究，将推荐视为一个排序任务，而本文将推荐视为回归任务。

2. Multiverse Recommendation 基于Tucker 分解技术来直接分解用户张量、item 张量、所有离散上下文变量的张量，从而求解该问题。它将原始的评分矩阵分解为一个小的矩阵 $\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 路特征交叉使得数据更加稀疏，难以准确的预估模型参数。

3. Attribute-aware Recommendation：与通用上下文感知方法的工作对比，对属性感知或专用推荐系统的研究要多得多。有一些工作可以处理用户属性和 item 属性的矩阵分解模型的扩展，还有一些关于考虑时间效应的工作。然而，所有这些方法都是为特定问题设计的，无法处理我们在本工作中研究的上下文感知推荐的通用设置。

   当然，对于特定的和重要的问题（如时间感知推荐或属性感知推荐），专用模型的研究是有益的。但是另一方面，研究上下文感知的通用方法也很重要，因为它们提供了最大的灵活性，并且可以作为专用模型的强 baseline 。

4. Alternating Least Square Optimization：对于矩阵分解模型，Bell 和 Koren 提出了一种交替优化所有 user factor 和所有 item factor 的 ALS 方法。由于所有user/item 的整个 factor matrix 是联合优化的，因此计算复杂度为 $O(d^3)$ 。标准 ALS 的这种复杂度问题是 SGD 方法在推荐系统文献中比 ALS 更受欢迎的原因。

   Pilaszy 等人提出一个接一个地优化每个user/item 中的 factor，这导致 ALS 算法复杂度为 $O(d)$ ，因为避免了矩阵求逆。一次优化一个factor 的思路与我们将 ALS 算法应用于FM 的思路相同。

   这两种方法仅适用于矩阵分解，因此无法处理任何上下文，例如我们提出的对所有交互进行建模的 FM 中的上下文。此外，我们的 ALS 算法还学习了全局bias 和基本的 1-way 效应。

3.2 模型

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

3.2.1 FM 模型

1. 推荐系统面临的问题是评分预测问题。给定用户集合 $\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 时，这表示用户对商品 “喜欢/不喜欢”，或者 “点击/不点击”。这就是典型的点击率预估问题。

2. 事实上除了已知部分用户在部分物品上的评分之外，通常还能够知道一些有助于影响评分的额外信息。如：用户画像、用户行为序列等等。这些信息称作上下文 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 特征转换。

   

3. 上下文特征 context 类似属性 property 特征，它和属性特征的区别在于：

   • 属性特征是作用到整个用户（用户属性）或者整个物品（物品属性），其粒度是用户级别或者物品级别。

     如：无论用户 “张三” 在在评分矩阵中出现多少次，其性别属性不会发生改变。

   • 上下文特征是作用到用户的单个评分事件上，粒度是事件级别，包含的评分信息更充足。

     如：用户 ”张三“ 在评价某个电影之前已经看过的电影，该属性会动态改变。

   事实上属性特征也称作静态画像，上下文特征也称作动态画像。业界主流的做法是：融合静态画像和动态画像。

   另外，业界的经验表明：动态画像对于效果的提升远远超出静态画像。

4. 和 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$ 列。

5. 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)$ 。

6. 将 FM 模型和标准的矩阵分解模型进行比较，可以看到：FM 也恰好包含这种分解 $<\mathbf{\vec v}_i,\mathbf{\vec v}_u>$ 。此外，FM 模型还包含了所有上下文变量的所有 pair 对的交互。这表明 FM 自动包含了矩阵分解模型。

7. 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$ 。

8. 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直接使用数值型特征，不做任何编码转换。

9. FM 的优势：

   • 给定特征 representation 向量的维度时，预测期间计算复杂度是线性的。

   • 在交叉特征高度稀疏的情况下，参数仍然能够估计。

     因为交叉特征的参数不仅仅依赖于这个交叉特征，还依赖于所有相关的交叉特征。这相当于增强了有效的学习数据。

   • 能够泛化到未被观察到的交叉特征。

     设交叉特征 “看过电影 A且 年龄等于20” 从未在训练集中出现，但出现了 “看过电影 A” 相关的交叉特征、以及 “年龄等于20” 相关的交叉特征。

     于是可以从这些交叉特征中分别学习 “看过电影 A” 的 representation 、 “年龄等于20”的 representation，最终泛化到这个未被观察到的交叉特征。

3.2.2 ALS 优化算法

a. 最优化解

1. FM 的目标函数最优化可以直接采用随机梯度下降 SGD 算法求解，但是采用 SGD 有个严重的问题：需要选择一个合适的学习率。

   • 学习率必须足够大，从而使得 SGD 能够尽快的收敛。学习率太小则收敛速度太慢。

   • 学习率必须足够小，从而使得梯度下降的方向尽可能朝着极小值的方向。

     由于 SGD 计算的梯度是真实梯度的估计值，引入了噪音。较大的学习率会放大噪音的影响，使得前进的方向不再是极小值的方向。

   我们提出了一种新的交替最小二乘 alternating least square:ALS 算法来求解 FM 目标函数的最优化问题。与 SGD 相比ALS 优点在于无需设定学习率，因此调参过程更简单。

2. 根据定义：

   $$\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$ 有：