CTR 预估模型

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

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

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

一、LR 模型

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

    基于最大似然准则可以通过广告的历史表现得统计来计算 pCTR 。假设广告曝光了 100次,其中发生点击 5 次,则 pCTR = 5%。其背后的假设是:忽略表现出周期性行为或者不一致行为的广告,随着广告的不断曝光每个广告都会收敛到一个潜在的真实点击率

    这种计算 pCTR 的方式对于新广告或者刚刚投放的广告问题较大:

    • 新广告没有历史投放信息,其曝光和点击的次数均为 0 。

    • 刚刚投放的广告,曝光次数和点击次数都很低,因此这种方式计算的 pCTR 波动非常大。

      如:一个真实 CTR5% 的广告必须曝光 1000次才有 85% 的信心认为 pCTR 与真实 CTR 的绝对误差在1% 以内。真实点击率越低,则要求的曝光次数越多。

    为解决这个问题,论文 《Predicting Clicks: Estimating the Click-Through Rate for New Ads》 提出利用 LR 模型来预测新广告的CTR

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

    因此有:

    假设:

    • 在广告被浏览(即:曝光)到的情况下,广告被点击的概率与其位置无关,仅与广告内容有关。

    • 广告被浏览的概率与广告内容无关,仅与广告位置有关。

      广告可能被拉取(推送到用户的页面),但是可能未被曝光(未被用户浏览到)。

    则有:

    • 第一项 就是我们关注和预测的 CTR

    • 第二项与广告无关,是广告位置(即:广告位)的固有属性。

      可以通过经验来估计这一项:统计该广告位的总拉取次数 ,以及总曝光次数 ,则:

      这也称作广告位的曝光拉取比。

1.1 数据集构造

  1. 通常广告主会为一个订单 order 给出多个竞价词 term,如:

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

  2. 数据集包含 1万个广告主,超过 1百万个广告、超过 50万竞价词(去重之后超过 10万个竞价词)。

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

      • landing page 落地页:点击广告之后将要跳转的页面的 url
      • bid term:广告的竞价词
      • title:广告标题
      • body:广告的内容正文
      • display url:位于广告底部的、给用户展示的 url
    • 将每个广告的真实点击率 CTR 来作为 label

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

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

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

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

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

      • 两种广告主的广告具有不同的平均点击率
      • 优质广告主的广告的点击率方差较低(表现比较稳定)、普通广告主的广告的点击率方差较高(表现波动大)
    • 广告平台更关注于普通广告主,因为这些普通广告主的数量远远超过优质广告主的数量,而且这些普通广告主更需要平台的帮助。

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

    曝光阈值的选取不能太大,也不能太小:

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

1.2 LR模型

  1. 论文将 CTR 预估问题视作一个回归问题,采用逻辑回归 LR 模型来建模,因为 LR 模型的输出是在 01 之间。

    其中 表示从广告中抽取的第 个特征(如广告标题的单词数量), 为该特征对应的权重。采用负号的原因是使得权重、特征和 pCTR 正相关:权重越大则 pCTR 越大。

    • 模型通过 limited-memory Broyden-Fletcher-Goldfarb-Shanno:L-BFGS 算法来训练。

    • 模型的损失函数为交叉熵:

    • 权重通过均值为零、方差为 的高斯分布来随机初始化。其中 为超参数,其取值集合为 [0.01,0.03,0.1,0.3,1,3,10,30,100],并通过验证集来选取最佳的值。

      通过实验发现, 的效果最好。

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

    • 模型添加了一个bias feature,该特征的取值恒定为 1。即:将偏置项 视为

    • 对于每个特征 ,人工构造额外的两个非线性特征:: 。加 1 是防止 取值为 0 。

    • 对所有特征执行标准化,标准化为均值为0、方差为1 。

      注意:对于验证集、测试集的标准化过程中,每个特征的均值、方差使用训练集上的结果。

    • 对所有特征执行异常值截断:对于每个特征,任何超过均值 5 个标准差的量都被截断为 5 个标准差。

      如:特征 的均值为 20,方差为 2 。则该特征上任何大于30 的值被截断为 30、任何小于 10 的值被截断为 10

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

  3. 评价标准:

    • baseline :采用训练集所有广告的平均 CTR 作为测试集所有广告的 pCTR

      即:测试集里无论哪个广告,都预测其 CTR 为一个固定值,该值就是训练集所有广告的平均 CTR

    • 评估指标:测试集上每个广告的 pCTR 和真实点击率的平均 KL 散度。

      KL 散度衡量了 和真实点击率之间的偏离程度。一个理想的模型,其 KL 散度为 0 ,表示预估点击率和真实点击率完全匹配。

      为了更好的进行指标比较,论文实验中也给出了测试集的 MSE (均方误差)指标。

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

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

1.3 特征工程

1.3.1 Term CTR Feature Set

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

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

    对于广告 ad 的竞价词 term (记作 )

    • 针对该 term 竞价的其它广告主所有广告的数量:

      由于同一个广告主的不同广告之间相关性比较强,因此这里用其它广告主的广告作为特征来源。否则容易出现信息泄露。

    • 针对该 term 竞价的其它广告主的广告点击率(经过归一化):

      其中:

      • 是训练集上所有广告的平均点击率

      • 是针对该 term 竞价的其它广告主所有广告的数量

      • 是针对该 term 竞价的其它广告主所有广告的平均点击率

      • 是平滑系数,为了防止某些新的 term 出现导致 。如果不采取平滑,则有

        代表了term 竞价的广告数量的先验强度,默认取值为 1 。

        实验发现,结果对 的取值不敏感。

    模型新增这两个特征的实验结果如下图所示,可见 term ctr feature set 使得评估指标 “平均 KL 散度” 提升了 13.28%

1.3.2 Related Term CTR Feature Set

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

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

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

    给定一个竞价词 t,定义其相关广告集合为 (一个竞价词term 可能包含多个单词word,这里不考虑word 之间的词序):

    如:tred shoes

    • 如果广告的竞价词是buy red shoes,则该广告属于t
    • 如果广告的竞价词是 shoes,则该广告属于 t
    • 如果广告的竞价词是red shoes,则该广告属于t
    • 如果广告的竞价词是blue shoes,则该广告属于t
  3. 的定义可知:

    • 广告集合 代表广告的竞价 termt 完全匹配。
    • 广告集合 代表广告的竞价 termt 少了 个单词之外其它单词完全相同(不考虑词序)。
    • 广告集合 代表广告的竞价 termt 多了 个单词之外其它单词完全相同(不考虑词序)。

    假设 * 为任意数值,则定义:

    • 表示 t 的任何超集(不考虑词序)作为竞价term 的广告的集合。
    • 表示 t 的任何子集(不考虑词序)作为竞价term 的广告的集合。
  4. 定义相关竞价词的一组特征,它们称为相关竞价词特征集 Related Term CTR Feature Set

    • term 相关的竞价词上竞价的其它广告主所有广告的数量:

    • term 相关的竞价词上竞价的其它广告主所有广告的平均点击率:

      其中 表示广告 x 的真实点击率。

      Term CTR Feature Set 一样,这里也采用平滑:

      其中 表示平滑系数。

    论文中采取了 一共 5x5=25 种组合,得到 25 x 2 =50related 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. 有的订单定向比较窄。如:

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

    而有的订单定向比较宽,如:

    该订单的竞价词不仅包含shoes,还包括 TVgrass 等等。

    我们预期:定向越宽的订单,其平均CTR 越低;定向越窄的订单,其平均CTR 越高。

  2. 为了考虑捕捉同一个订单内不同广告的联系,论文提出了订单维度特征集 Order Specificity Feature Set

    • 同一个订单中,去重之后不同竞价词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 set19.67%
    • ad quality feature set12.0%
    • unigram features along10.2%
    • order specificity feature set8.9%
    • search data feature set3.1%
  2. 有几个特征探索方向:

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

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

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

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

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

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

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

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

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

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

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

1.4 特征重要性

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

    模型的top 10bottom 10 权重对应的特征如下:

  2. 特征的权重不一定直接表示其重要性,因为特征之间不是独立的

    假设有一个重要的特征是文本中每个单词的平均长度(即:平均多少个字符) ,但我们并没有直接给出这个特征,而是给出相关的两个特征:文本总字符数 、文本总单词数 。那么我们会发现:特征 具有一个较大的正权重、特征 有一个较大的负权重。

    因为 ,所以特征 和特征 正相关,而特征 和特征 负相关。

  3. unigram features 中,top 10bottom 10 权重对应的特征如下。

    可以看到:

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

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

1.5 曝光量

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

    定义观察到的点击率为:

    定义预测的点击率为:

    其中:

    • 是广告的曝光次数, 为广告的点击次数, 为先验CTR 是先验曝光次数。

    • 是模型预估得到的 pCTR ,而 是一个超参数。

    • 是结合了模型预估的 pCTR 和广告已经产生的曝光、点击之后,预测的点击率。

      模型预测的 pCTR 没有考虑广告当前的曝光、点击,因此需要修正。

    定义期望绝对损失 expected absolute error:EAE

    其中: 表示给定曝光的条件下,点击click 次的概率。它通过统计其它广告得到。

    EAE 刻画了在不同曝光量的条件下,模型给出的 CTR 的绝对误差。这和模型优化目标平均KL 散度不同。

  2. baselineLR 模型的 EAE 结果如下所示。可以看到:

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

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

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

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

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

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

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

二、POLY2 模型

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

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

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

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

  2. 设低维样本空间为 维度,低维样本

    多项式核定义为: 。其中 为超参数, 为多项式的度degree

    根据定义,多项式核等于样本在高维空间向量的内积:

    其中 是映射函数。

    时,有:

    使用 是为了 的表达更简洁。

  3. 如果不用核技巧,仅仅考虑使用一个多项式映射,则我们得到:

    结合LR 模型,则得到 POLY2 模型:

    新增的组合特征一共有 个。

  4. POLY2 模型的优缺点:

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

    • 缺点:

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

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

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

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

三、FM模型

  1. 推荐系统面临的问题是评分预测问题。给定用户集合 、物品集合 ,模型是一个评分函数:

    表示用户 对物品 的评分。

    其中已知部分用户在部分物品上的评分: 。目标是求解剩余用户在剩余物品上的评分:

    其中 的补集。

    • 通常评分问题是一个回归问题,模型预测结果是评分的大小。此时损失函数采用MAE/MSE 等等。

      也可以将其作为一个分类问题,模型预测结果是各评级的概率。此时损失函数是交叉熵。

    • 当评分只有 01 时,这表示用户对商品 “喜欢/不喜欢”,或者 “点击/不点击”。这就是典型的点击率预估问题。

  2. 事实上除了已知部分用户在部分物品上的评分之外,通常还能够知道一些有助于影响评分的额外信息。如:用户画像、用户行为序列等等。这些信息称作上下文 context

    对每一种上下文,我们用变量 来表示, 为该上下文的取值集合。假设所有的上下文为 ,则模型为:

    上下文的下标从 3 开始,因为可以任务用户 和商品 也是上下文的一种。

    如下图所示为评分矩阵,其中:

    所有离散特征都经过特征转换。

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

    • 属性特征是作用到整个用户(用户属性)或者整个物品(物品属性),其粒度是用户级别或者物品级别。

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

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

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

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

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

3.1 模型

  1. Multiverse Recommendation 基于矩阵分解技术求解该问题,它将原始的评分矩阵分解为一个小的矩阵 个因子矩阵

    其中:

    这种方式存在三个问题:

    • 计算复杂度太高:假设每个特征的维度都是 ,则计算复杂度为 。一旦上下文特征数量 增加,则计算复杂度指数型增长。
    • 仅能对离散型 categorical 上下文特征建模:无法处理数值型特征、离散集合型 categorical set 特征。
    • 交叉特征高度稀疏:这里执行的是 K 路特征交叉(前面的 POLY2 模型是两路特征交叉),由于真实应用场景中单个特征本身就已经很稀疏,K 路特征交叉使得数据更加稀疏,难以准确的预估模型参数。
  2. Fast Context-aware Recommendations with Factorization Machines 论文提出了 FM 算法来解决该问题。

    POLY2 相同FM 也是对二路特征交叉进行建模,但是FM 的参数要比 POLY2 少得多。

    将样本重写为:

    FM 模型为:

    其中 是交叉特征的参数,它由一组参数定义:

    即:

    模型待求解的参数为:

    其中:

    • 表示全局偏差
    • 用于捕捉第 个特征和目标之间的关系
    • 用于捕捉 二路交叉特征和目标之间的关系。
    • 代表特征 representation vector,它是 的第 列。
  3. FM 模型的计算复杂度为 ,但是经过数学转换之后其计算复杂度可以降低到

    因此有:

    其计算复杂度为

  4. FM 模型可以用于求解分类问题(预测各评级的概率),也可以用于求解回归问题(预测各评分大小)。

    • 对于回归问题,其损失函数为MSE 均方误差:

    • 对于二分类问题,其损失函数为交叉熵:

      其中:

      • 评级集合为 一共两个等级
      • 为样本 预测为评级 的概率,满足:

    损失函数最后一项是正则化项,为了防止过拟合, 。其中 为参数 的正则化系数,它是模型的超参数。

    可以针对每个参数配置一个正则化系数,但是选择合适的值需要进行大量的超参数选择。论文推荐进行统一配置:

    • 对于 ,正则化系数为 ,这表示不需要对全局偏差进行正则化。
    • 对于 ,统一配置正则化系数为
    • 对于 ,统一配置正则化系数为
  5. FM 模型可以处理不同类型的特征:

    • 离散型特征 categoricalFM 对离散型特征执行 one-hot 编码。

      如,性别特征:“男” 编码为 (0,1),“女” 编码为 (1,0)

    • 离散集合特征 categorical setFM 对离散集合特征执行类似 one-hot 的形式,但是执行样本级别的归一化。

      如,看过的历史电影。假设电影集合为:“速度激情9,战狼,泰囧,流浪地球”。如果一个人看过 “战狼,泰囧,流浪地球”, 则编码为 (0,0.33333,0.33333,0.33333)

    • 数值型特征 real valuedFM直接使用数值型特征,不做任何编码转换。

  6. FM 的优势:

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

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

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

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

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

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

3.2 ALS 优化算法

3.2.1 最优化解

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

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

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

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

    论文提出了一种新的交替最小二乘 alternating least square:ALS 算法来求解 FM 目标函数的最优化问题。

    SGD 相比ALS 优点在于无需设定学习率,因此调参过程更简单。

  2. 根据定义:

    对每个 ,可以将 分解为 的线性部分和偏置部分:

    其中 无关。如:

    • 对于 有:

    • 对于 有:

    • 对于 有:

    因此有: