CTR预估综述

CTR预估

CTR预估作为推荐系统最重要的应用场景, 主要任务是对给定的<user, item>对, 评估出点击的概率. 要求预估出的值绝对准确, 因为对于TOP3的CTR预估值为0.9, 0.8, 0.7, 或0.5, 0.4, 0.3, 虽然展示排序相同, 但置信程度的差别代表着曝光收费的截然不同. CTR预估任务往往对模型有着更高的要求.

与其他的推荐任务系统相同, 常见的CTR预估系统也是由召回和排序两个环节组成, 其中排序环节根据实际业务需求, 又可以继续划分为粗排, 精排, 重排这三部分, 简单来说, 这四个环节各自的目的为:

召回: 根据用户特征, 从海量物品中, 高效快速地找回一小部分用户可能感兴趣的物品, 减少后续排序模型的计算负担
粗排: 有些召回模型比较简单, 为了保证召回率, 让召回环节返回较多的候选物品, 或者使用的精排模型比较复杂, 为了减轻精排环节的压力, 保证推测速度, 在召回和精排之间加入一个粗排环节, 在保证精准的前提下, 进一步减少向后传送的物品数量
精排: 保证推荐效果的核心部分, 在保证线上速度和承受能力极限的前提下, 可以使用尽可能复杂的特征, 复杂的深度模型, 尽可能地对物品进行预估排序
重排: 融合业务策略, 推荐去重, 多样性保证, 业务逻辑主导

大部分推荐模型都可以应用在从召回到精排的各个阶段, 各阶段也可以使用同种模型, 只是在训练样本的组织, 使用的特征, 训练使用的损失函数和优化器, 以及线上工作方式上有所区别. 因此, 首先按时间顺序, 简要的介绍各类推荐系统中常用的, 经过工业验证过的各种模型.

推荐模型

数据样式

在梳理模型之前, 首先需要了解推荐系统中使用样本的形式. 推荐系统的特征分为两大类: 数值型特征和类别特征. 类别特征是推荐的核心特征, 占据了特征维度的绝大多数部分, 也包含了绝大部分信息, 在推荐算法中无处不在:

userId, itemId对于大的系统往往是百万千万, 每一个都是一个维度
用户的画像(如用户的点击行为), 物品的画像(如文章的tags)
特征之间的交互生成的新特征

即便是数值型特征, 也经常将其分箱/分桶, 离散转换成类别特征. 再将所有类别特征按分箱展开(One-hot), 如用户的年龄段特征包含4个类型: 少年, 青年, 中年, 老年, 将其转化为4个特征, 每个特征只有1/0两种取值, 代表样本是否属于此箱.

这是推荐系统常常使用的数据处理方法, 这样得到的特征高维, 常常有上亿维. 但非常稀疏, 尽管有上亿标签, 但有值特征可能只有几十个而已. 稀疏也保证了存储和计算的可能性, 而特征二值化带来了更少的计算量, 很大程度上避免了乘法计算.

LR

Logistic Regression是一个对稀疏样本非常友好的模型, 且可解释性很好, 训练得到的模型可以看作一个超大的评分卡模型.

推荐任务中使用逻辑回归模型, 在于它是一个非常善于记忆的模型, 训练样本中较常出现的特征共现模式模型都会很好的学习到, 在预测时遇到这种见过的模型, 准确率往往也会很好.

由于每个特征(包括特征工程中人工产生的交叉特征)都有对应的权重, 这些权重就代表着这一项的贡献, 或称为评分. 各项评分线性叠加得到得分总和. 通过训练, 在正样本中出现频率高的特征评分越高, 在负样本中出现频率高则评分越低. 例如由正常样本训练得到的SCORE(<春节, 中国人, 饺子>)=5这项交叉特征的评分为正, SCORE(<春节, 鲱鱼罐头>)=-100这项交叉特征评分很低, 如果要预测的样本中此项特征为1, 则该样本很可能不会被点击.

这就是业务可解释性良好的由来, 一个超大的评分卡模型.

LR的优点是强于记忆, 但缺点也非常明显, 没有扩展能力, 挖掘不出新的模式, 一切都依赖于输入的特征范围. 这就要求:

强大的特征工程
探索尽可能多的特征交叉

因此, 逻辑回归效果的好坏, 完全在于特征工程的效果, 需要投入大量人力持续迭代, 成本是很高的.

GBM + LR

LR面临着沉重的人工特征工程的问题, 探索简化甚至省去特征工程步骤是工业所需要的. 另外, 特征的分箱优劣也会对最后的指标及效果起到重要的影响.

GBM + LR的模型结构如上图. 基于决策树的GBM能力强, 在很多任务中都能取得很好的表现. 对于每个样本, 它在每棵决策树中都会被分配在一个叶子节点中. 我们再将所有叶子节点作为特征, 样本被分配至该节点对应的特征值为1, 否则为0, 送入后续的LR模型, 得到最后的概率输出.

相比于LR直接使用人工特征, 本结构首先使用GBM对原始特征进行编码转化, 得到抽象的二值特征. 而训练GBM的过程就是探索更好的特征编码逻辑, 这个过程中GBM会学到合理的分箱方式, 特征之间的交叉信息等等.

这种结构的初始版本是GBDT与LR的组合, 而后续XGBoost和LightGBM模型凭借更加优异的表现, 代替了GBDT的位置.

GBM + LR结构有着区别与LR的优势:

省去了一些特征工程的工作, 如分箱等, 适用于数值型特征为主的场景
支持特征缺失
带来了部分自动特征工程的效果

但这种结构的缺点也很明显:

GBM的训练和LR是分离的, 非端到端训练, 会带来误差的累积
失去了LR良好的可解释性, 叶子节点特征的意义不好描述
随着推荐系统的发展, 现在使用的特征一般是将业务数据转换为大量的二值化特征, 数据维度高且非常稀疏. 树模型结构对这种结构表现较差, 容易引起过拟合

FM(Factorization Machines)

FM对探索自动化特征交叉又迈出了巨大的一步, 带了了自动而全面的特征交叉. 简单来说, FM在LR基础上显式地增加了二阶特征交叉部分. LR的线性部分为:

\text{logit} = w_0 + \sum_{i=1}^{n}w_ix_i

其中特征的数量为 $n$ . 且我们假设使用的特征都是二值化后的特征, 取值只有1/0两种.而FM的预测公式可以记为:

\text{logit} = w_0 + \sum_{i=1}^{n}w_ix_i + \sum_{i=1}^{n}\sum_{j=i+1}^{n}<v_i,v_j>x_ix_j

可以看到前两项就是LR的部分, 最后一项是所有特征二阶交叉的部分.

对于最后一项, 两两特征交叉得到的新特征对应的权值没有使用独立的 $w_{ij}$ , 而是使用了向量点积 $<v_i,v_j>$ , $v_i$ 是特征 $i$ 对应的隐向量, $v_j$ 是特征 $j$ 对应的隐向量.

这是因为输入数据的特征维度往往至少都是百万级别, 经过二阶交叉后, 每个交叉项单独分配一个参数, 需要的参数矩阵的空间复杂度就是 $O(n^2)$ , 是系统所不能承受的. 而借助矩阵分解(Matrix Factorization)的思路, 通过维护一个可训练的大小为 $(n,k)$ 的矩阵, 使得每个特征对应一个长度为 $k$ 的向量, 在特征交叉时, 对应向量点击得到权重.

这样处理的优点很多:

空间复杂度将为 $O(kn)$
不同特征的参数之间得到了共享, 由此可以使用embedding技术进行离线计算存储

关于参数共享, 使用梯度下降的方法优化, 之前的模型特征参数都是在样本出现该特征时才会得到训练, 这样对于一些比较冷门的特征, 往往不能得到很好的训练, 从而影响了推荐系统的多样性.

但在FM中, 交叉特征 $<v_i,v_j>$ , $<v_j,v_k>$ 共现, 虽然 $<v_i,v_k>$ 的共现情况可能在训练集中很少甚至没有, 但他们之间的相关性依然能够得到体现.

总结FM模型:

保留的LR部分, 优秀的记忆功能得到了保证
引入二阶交叉, 带来了自动特征相关, 引入了扩展性能
仍然是线性模型, 保留了LR $O(n)$ 的时间复杂度以及良好的可解释性

Wide & Deep

随着深度学习的发展, 深度模型在各领域都取得了重大的突破, 在推荐领域也推进了CTR预估效果的大幅提升. 从引入深度学习模型开始, 推荐模型逐渐转至黑箱, 特征工程逐渐减少, 更青睐与交给模型进行更深程度的处理. 在原来记忆的基础上, 对推荐系统的扩展性能带来了飞速的提升.

综合记忆和扩展, 是推荐系统的重点. 过去的线性模型在记忆部分表现较好, 但扩展依赖繁重的特征工程. 深度模型由于其复杂的模型结构, 带来了未可知的扩展性. 因此Wide&Deep直观的将两者结合, 整个模型由Wide和Deep两部分组成, 分别负责记忆和扩展部分:

Wide部分就是基础的线性模型, 这部分的特征仍然是一些特征工程产生的基础特征与交叉特征, 将基础特征记为 $x_i$ , 交叉特征记为 $\phi_k$ .

Deep部分是直观的FNN, 输入的特征首先转换为embedding, 经过完整的网络后得到输出.

Wide&Deep网络的推理输出由两部分相加组成:

\text{logit} = \mathbf{w}_{w i d e}^{T}[\mathbf{x}, \phi(\mathbf{x})]+\mathbf{w}_{d e e p}^{T} a^{\left(l_{f}\right)}+b

训练方法

Wide&Deep模型的训练方法比较特殊, Wide和Deep两部分是分开使用不同的优化方法训练的.

Wide部分使用L1 FTRL训练. FTRL是一种稀疏性很好的随机梯度下降方法, 可以做到来一个样本就训练一次, 进而实现模型的在线更新. 在传统模型中经常使用, 因此用来训练Wide这种线性部分.

Deep部分使用Adagrad这种自适应学习率的优化器.

特征分配

论文中以Google Play场景中推荐APP为例, Deep部分使用数值型特征, 以及有必要转成embedding的特征, 而Wide部分使用了两类APPID的乘积, 得到的Multi-hot特征是极为稀疏的.

可以看出Wide部分适合极为稀疏的特征输入, 结合FTRL训练方法, 训练的时间复杂度很低. Deep部分使用数值特征和embedding向量的拼接, 得到的是稠密向量, 不存在稀疏问题, 因而使用深度的训练方法更为合适.

DeepFM

Wide部分改造

DIN

引入Attention结构, 加权平均历史行为数据, 开辟了高效使用历史信息的途径.

模型演进

CTR预估模型的发展, 最明显的是特征数据在还原它本来的形式.

样本构造

CTR预估样本由<user, item, label>组成, 其中label为0未点击, 1点击. 但在整条链路中, 召回和排序过程的侧重点不同, 在数据形式和数据集构造方面也会有所不同.

总的来说主要有两点不同:

负样本采集生成方法不同
排序鼓励交叉, 召回要求解耦

排序

负样本生成

排序阶段需要对上一步给出的<user, item>列表中的每一条给出点击率的评估, 因而更适合使用pointwise loss, 如最长用的binary cross entropy loss.

正样本自然是真实的用户点击样本, 而且由于正样本比例较少, 往往在训练时还会对正样本进行加权.

负样本的选取强调真实负样本, 一定是给用户真实曝光过而被用户忽略的item, 才能称为负样本. 虽然被模型推荐出去, 但用户没有看到而没有产生点击, 不代表用户对此条不敢兴趣.

因此常使用above-click方法, 即只拿用户点击的item的位置以上的未点击item作为负样本.

交叉特征

排序模型除了使用user特征, item特征, 最终要的是使用大量的交叉统计特征, 这类特征直接衡量user与item的匹配性, 提供直接有效的贡献.

召回

负样本生成

召回的任务与直接评估CTR存在一定差异. CTR预估排序阶段是从用户可能喜欢的items中选出最喜欢的, 面对的数据是比较友好的. 但召回阶段面对的是各种质量的数据, 因此如果直接使用与排序阶段相同的数据, 对召回模型来说数据是有偏差的, 接受的数据偏向优秀, 离线和在线一定会有表现差异.

因此召回任务可以总结为在全量数据中找出用户可能感兴趣的item, 在组织训练数据时为了贴近真实分布, 一般使用各种负采样方法在全量物料库中采样.

此外, 召回阶段可以使用同排序阶段的方法, 逐条判断是否应该召回, 使用pointwise loss, 沿用<user, item, label>的样本形式. 而召回阶段不强调预测结果的绝对准确, 只需保证更合适的排名相对考前, 得到召回机会即可, 因此使用Pairwise Hinge Loss更为合适, 样本由<user, item+, item->组成, 保证<user, item+>比<user, item->的匹配度高于一个阈值即可.

解耦

召回场景每次的user请求, 都面对着百万千万级的候选items, 如果user与每个候选item都计算交叉统计特征, 产生的计算量是无法满足线上实时性要求的, 同样离线计算存储带来的存储量也是无法承受的, 且失去了动态性. 因此, 召回模型使用的特征, 要求user与item特征分离, 不能产生交叉.

虽然放弃这部分强特征对效果有负面影响, 但召回的任务并不是精确评价点击, 只使用user与item的独立特征依旧能够很好的完成承担的任务.