ctr那些事儿

[TOC]

CTR概述

转自【https://zhuanlan.zhihu.com/p/31499375】

click through rate 是用来估计一个用户(缩写为u)是否会点击一个广告或其它item(缩写为a)的技术

v2-e5998fc5f766e99bbe92be20711a7206_hd

问题的核心在于建模,即:寻找一个函数 f 可以学习出数据中 f: X \to y 的映射,即尽可能用数据 (X,y) 拟合 f 。这可以简化地理解为一个分类(Classification)问题

作为一种预估问题,CTR预估潜在地包含了假设:过去的规律在未来依然有效。

我们会自然地想到,从历史估计未来,最简单的方式就是对历史数据做统计。那么是否用统计值来预估就可以了?

不然。

首先,统计量本身有置信度的概念,数据中很难保证每个特征都有充足的数据支持每个特征的置信度。比如,张三看了1kw的广告、点击了1k次,或许可以说张三的点击率是0.01%;但如果李四只看了1次广告、没有点击,却不能简单地认为李四的点击率一定为0%。其次,历史上一定有未被观察(unseen)的事件。比如“张三看宝马会点击”是一个事件,但张三不可能看过所有的广告;张三在历史上没有看过奔驰广告,统计也就无法得知他是否会点击奔驰广告。

从另一个角度讲,传统的Machine Learning问题为便于建模,一般会隐含数据服从Gaussian分布的假设;但在互联网主要的展示(impression)、点击(click)、关注(follow)、转发(re-twitter)、交易(order)等数据中,由于强烈的“头部效应”,整体数据是呈现幂指数分布的——由于长尾的存在,对于部分特征来讲数据一定是不充分的。

于是我们总结出CTR预估第一个问题:CTR预估是在不完善信息下做出的决策。换句话说就是:总有统计上不充分的情况出现,无论是unseen事件,还是seen但事件重复次数较少的情况。

回到“过去的规律在未来依然有效”这个假设。在实际应用中,这个假设是双刃剑:

  • 好的方面:过去的规律意味着可以利用历史信息,也就意味着利用更大量的样本(instance)、构造大量的特征(feature)、使用复杂的模型(model)的可能性。这也是CTR预估算法从2007年使用LR建模之后十多年不断发展和分化的基础。
  • 坏的方面:这个假设在现实中并不完全成立——数据的分布在并不被模型预知的情况下变动着。用户行为影响ranking,ranking反过来也会影响用户行为;再加上用户分布变化对数据分布的扰动、运营手段对数据分布的扰动等等复杂因素,经常会导致模型刚上线效果最好,然后可能渐渐地就不好用了。

这就是CTR预估第二个问题:**CTR预估是在变化的分布上做出的估计。**换句话说就是:总有从历史上得不到的规律。

对于这两个问题,常见的解决思路有:

  • 针对在不完善信息下做出决策的问题:

    • 试:引入E&E机制快速试错;
    • 泛:引入更通用、更泛化的特征,在无法精细估计的情况下给出一个更通用的估计。
  • 针对在变化的分布上做出估计的问题:

    • 快:更快的模型迭代更新速度、在线学习;
    • 猜:引入博弈论,强化学习,对用户-系统交互行为进行建模。

一个例子

考虑一个简单的CTR预估场景的例子。这里有两个特征(position_id、ad)。为了方便,我们把相同特征下的曝光和点击进行计数,聚合在一起。

v2-e366cc1eea72ef722c49a8933e1e46e0_hd

以第一行数据为例:“ad=宝马”在“position_id=1”的位置曝光了10次,有6次点击。

我们把每个特征进行one-hot encoding:

v2-0d6a9486da21453f893c09ce72dfa7c5_hd

下面我们入手开始CTR预估建模。对于CTR预估问题,工业界解决的起点其实和大部分机器学习的通用思路是一致的:**先给出并使用一个较粗糙的解,然后把求解问题转化成一个优化问题。**毕竟,“随机猜”(random)也是一种模型,只是效果比较差而已。我们要优化出比random更好的解,也就是从test AUC = 0.5开始进行优化。

CTR系统核心建模是针对展示(pv)和点击(click)的关系进行建模的:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~y_{click} = Bernoulli(p_{ctr})

这一点是众多CTR预估算法的共同基础。而针对 p_{ctr} 建模主要有两大类途径:

v2-97bfe6be9ef47f6544fb5aa78a225d59_hd

以线性模型LR为例,核心建模为: \begin{split} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~p_{ctr} &= f(\phi(x)) \ &= \frac{1}{1+e^{-\phi(x)}}\ \phi(x) &= w^Tx \end{split} 在上图的例子中, x 为四维one-hot特征的取值,如对于上例的第一行数据:x_1=1, x_2=0, x_3=1, x_4=0. 对应地,我们估计出的 w 也是一个四维向量,分别代表特征“psid=1、psid=2、ad=宝马、ad=奔驰”的权重。由这些权重,我们就可以估计出各种 x 取值下的点击率。

可以看到,线性模型假设模型 f(·)线性可分的。当然,这并不意味着线性模型无法表示非线性:我们可以在feature X 中增加非线性特征来提供非线性。与此对应的是,非线性模型在模型假设中直接具有非线性

线性模型中,一般特征的规模都会特别大。这是因为线性模型如果要达到与非线性模型相似的模型效果(或者说表达能力),需要在特征侧做大量的工作:比如把原本非线性表达的特征离散化成局部线性的特征、把单一实体变换为高维度的one-hot encoding特征、以及由于上述的操作大量分割了实体之间的关系而需要添加大量组合(crossing)特征等等。这些变换都会大幅增加稀疏特征的维度。

如果我们把线性模型和非线性模型的计算链路展开,会发现线性模型的特征维度高但计算深度少,模型相对很“宽(wide)”;而非线性模型则相对更“深(deep)”,模型计算更为复杂。相对应地,有些模型更倾向于在特征侧进行优化,而有的模型更针对于模型侧的调优。

模型侧和特征侧优化

CTR预估中,模型侧的优化主要集中在各类非线性模型上,如基于Kernel的模型、NN、Boosting等。在实际的CTR预估系统中,NN和Boosting较为常用,而kernel的身影比较少见。这是因为基于kernel的模型中特征维度通常很高,且 O(N^2) 的时间复杂度太高难以满足工业要求。

在实际工程中,对模型侧的优化主要体现在:观察数据找规律,建模调参线上试。大致的步骤包括:

  1. 观察数据;
  2. 找到规律;
  3. 根据规律做模型的假设;
  4. 对模型假设中的参数用数据进行拟合;
  5. 把拟合的结果用到线上,看看效果怎么样。

举个例子:在某业务中,我们通过观察数据,认为图像特征是主要的影响CTR预估效果的因素;则我们在建模中引入CNN假设进行joint training,然后调参、离线验证,验证ok进行线上实验,完成一轮优化。其中,掌握模型的理论本质、适用范围和复杂度,针对需求对模型进行选择和业务适配,是模型侧优化的主要工作。

特征侧优化

特征侧有相对有迹可循的优化方法。常用的是层次化特征:保证细粒度ID无法命中的时候,层次化“上位”更粗粒度特征可以生效。

如某个场景中有如下的特征层次关系,其曝光量如色阶所示:

2-2215e475e08325a0139828d2d00d8623_hd

  • 1阶特征中,“小吃套餐”特征曝光太少,特征置信度低,则至少上位特征“某的基”可以命中生效。这是一个从最细粒度到更粗粒度的扩展过程;
  • 2阶组合特征中,最细粒度的“小吃素材&顶部通栏2号位”曝光很少很难命中优化,可以取其中某一个的上位,形成“某的基&顶部通栏2号位”;或者如果还不够,则扩充更多的维度,如“某的基&通栏” 。越宏观的特征表达出的个性化信息越少,但是在数据不足时,能表达出特性的概率越大。

一图以蔽之,模型侧和特征侧优化方法可以比较总结如下:

v2-ddeb06abfa253f77304644badb7bbb61_hd

逻辑回归