predict

为什么要预估点击率

Posted on by snoopy

背景

想到这个题目是因为 @lijiefei 某天跟我说他有师弟面淘宝时被问到 “点击率预估的目标到底是什么”, 笨狗当时胡乱扯了一通, 发现要把这个似乎已经是真理的事情掰清楚还没那么容易, 于是有此念想写文一篇详细分析下原因

我和 jiefei 认识是在百度做搜索广告的时候, 那就从搜索广告开始说为什么要预估点击率, 以及预估点击率的目标. 先申明一些名词和假定:
1) 每个广告 (Ad) 有一个出价 (Bid), 并有其在某情形下实际的点击率 (Click-Through-Rate, CTR)
2) 广告按点击收费 (Charge per Click, CPC), 下面我们会分别讨论一价计费 (First-Price, FP, 即广告出价多少则一次点击计费多少) 和二价计费 (Second-Price, SP, 即广告按下一位出价来支付点击价格, 更普遍的是 GSP)
3) 千次展现收费 (Cost Per Mille, CPM, 或 RPM, R for Revenue), 即对点击付费广告其展示一千次情况下的收入 (一价计费下等价于 1000*CTR*Bid), 或是展示广告的千次展现固定价格
4) 预估点击率 (predict CTR, pCTR) 是指对某个广告将要在某个情形下展现前, 系统预估其可能的点击概率

目标分类

搜索广告跟自然结果一个很大的区别就是自然结果只要有一点相关就应该放到所有结果里去, 至于先后位置那个再说, 而广告, 是有个相关性的准入门槛的, 不相关的广告出价再高, 丢出来还是会被骂死. 那怎么判断相关? 用户会用鼠标点击来对结果投票, 相关的广告会被点击, 不相关的广告不会被点击, 那很自然就能得出 “点击率和相关性正相关” 这个结论 (至于描述里写 “二十五岁以下免进” 但实际是钢材广告的这种诱骗行为后面再说怎么处理). 那对于这种相关性准入的场景, 预估点击率就是预估广告是否相关, 最朴素情况下这是个二分类问题, 那不管预估成怎样, 只要有一种分割方法能分开是否相关就行了. 此时预估点击率的目标是能对广告按相关与否分类 (或说按相关性排序并给出一个截断值). 评估分类问题好坏, 一般都是看准确和召回两个指标, 用人工打分的记录来做回归验证就行

目标排序

判断相关与否只是点击率预估对广告的一个小辅助, 我们来看看广告的目标是什么? 没错, 是赚钱. (我曾经在其他场合说过广告的目标是维持用户体验下持续赚钱, 不过跟赚钱这一简化目标这不冲突, 前面相关性上已经保证了维持用户体验, 那只要能让广告主还有的赚, 就能持续赚钱) 我们再把问题简化下, 如果广告都是一样的固定价格, 且就以这个价格按点击计费, 那在 PV 一定且预算充分的情况下, 更高的点击率则意味着更赚钱. 这样目标可以等价于怎么挑出更赚钱的广告, 就是那些点击率最高的广告, 我们只要能弄明白广告实际点击率的高低关系就能取得收益最大化, 预估点击率在这时候又是个排序问题, 我们只要弄对广告之间的序关系, 就可以收益最大. 评估排序问题的好坏, 一个经典方法是对 pCTR 的 ROC 曲线算 AUC (曲线下面积), 实际上我见过的做法也都是通过评估 AUC 的高低来判断点击率预估模型的好坏

目标带权排序

上一段里对广告这个业务做了很多简化, 比如大家价格都是一样的, 如果我们考虑价格不一样的情况, 那预期收益就会变成 (价格Bid*点击率CTR), 这个值很多地方也叫 CPM 或 RPM. 如果是对 CPM 排序, 那就需要我们预估的点击率在维持序关系正确的前提下, 还要保证相互之间的缩放比是一样的. 比如有广告 A, B, C, 实际点击率是 5%, 3%, 1%, 那在价格一致的情况下, 我预估成 5-3-1 还是 5-4-3 是没关系的, 但在价格不一样的情况下, 比如 1, 1.5, 3, 这时候 5-4-3 的预估点击率值会让他们的预估排名和实际排名刚好颠倒过来, 不过预估 5-3-1 或 10-6-2 (放大一倍) 倒没关系. 为了评估这个结果, 可以在描 ROC 曲线时把价格乘上去, 那最后还是判断排序问题的好坏, 加了价格的 AUC 我们可以叫 wAUC (weighted-AUC), 这个离线评估和在线效果依然可以对等

目标准确

从准确召回到 AUC 再到 wAUC, 看起来对已有问题可以完美解决了? 不过广告计费显然不是 FP 这么简单, 在 Google 的带领下几乎所有的搜索引擎都使用了 GSP (Generalized Second Price) 来对广告点击进行计费, 这里再简单解释下最简版 GSP 是怎么回事:
1) 所有广告按 CPM 排序 (即 CTR*Bid)
2) 排最后的广告收底价 (Reserved Price, RP)
3) 其他广告按他的下一位 CPM_i+1 除以他的 CTR_i 并加一个偏移量来计费, 并保证比底价高, 即 Price_i = max(CPM_i+1/CTR_i + delta_price, RP)

至于 GSP 的细节和为什么这么做能保证收入和体验的平衡等可以详见相关论文, 我们只讨论在 GSP 模式下, 点击率预估的作用和关键点. 根据介绍 GSP 时最后那个公式, 如果把 CPM_i+1 拆成 CTR_i+1*Bid_i+1, 看起来只要保证同比缩放还是会没问题? 但是, 凡事怕但是, 在搜索广告里, 不同的展现位置对点击率还有影响, 比如广告 A, B 在第一位点击率是 5%, 3%, 而在第二位是 3%, 2%, 那只是同比缩放就很难保证最终比较是一致的问题了, 所以最好还是保证预估值跟实际值尽可能接近的好, 这样才能在预估时获得更实际用时完全一样的场景. 评估准确度, 我们有 MAE 和 MSE 等一堆指标, 也是现成的工作的比较好的东西

扩展和吐槽

有行家可能会吐槽说我刚那个不同广告在不同位置的衰减不一致这个说法, 跟公开论文说的不一样, Yahoo 的 paper 里说不同广告在同位置的衰减是一样的. 我只能说, 骚年, 你太天真了… 衰减因子怎么可能只是 f(pos) 这样一个简单函数, 从实际情况来看, 衰减函数和广告是有关的, 但我们又不能对每个广告都去估一个 f(pos, ad), 好在, 我们发现可以把不同的广告做聚类后得到一个 f(pos, type) 的函数簇, 事实上, 最后的衰减函数不仅仅有 pos 和 type 两个因子, 而且里面的因子可以极度简化, 最后的衰减用简单函数就能很好拟合, 我说的够多了, 再说估计要被前东家找麻烦, 你们来感受一下就好

前面也提到介绍的 GSP 是最简版的, 那如果是正常版会有什么不一样? 那就是排序时用的是 Quality*Bid, 这个 Quality 百度叫质量度, 也就是广大广告主望眼欲穿的那几颗星. Quality 和 CTR 有什么不一样? 最简情况下这两个当然是一样的, 但是我们可能还要考虑广告主的信誉度, 目标网页的质量等因素 (比如前面提到过的那种描述欺诈或诱导的广告在这个 Quality 因子里被调整掉), 最后这个 Quality 就会是包含了 CTR 的一个多因子复合值, 那要准确估计这个复合值, 当然也要求其中的每个因子的值尽可能准确. 这里在炒冷饭说准确度, 以及 MAE/MSE 的作用

实际上据我所知各搜索广告平台用的是比正常版的 GSP 还加强或改造过的版本, 里面的因子, 公式, 逻辑更复杂. 在这种情况下还是需要继续强调 CTR 预估的准, 才能做更精确的预估, 从而带来更大的收益

广告之外

呼~ 说完了搜索广告, 我们再简单说下内容广告. 搜索广告几乎都是点击付费, 而内容广告同时存在按点击付费和按展现付费, 那怎么比较一个按点击付费的广告和一个按展现付费的广告哪个预期收益更高? 同样是 CPM, 按展现付费的广告给的是确定值, 而按点击付费的是一个预估值, 通过 Bid*pCTR 得到, 如果 pCTR 不准, 就会导致点击付费广告的预期收益计算不准, 则不一定受益最大. 继续强调预估的准的好处

说完广告我们就能说说其他的, 比如搜索, 比如推荐, 这几个的优化目标如果是带来的量, 因为总体 PV 我们没法人工干预, 且每个点击是等价的, 那最后的优化就变成了点击率, 预估的序关系越接近真实, 可获得的收益更高. 如果不同的点击价值不一样, 那就可以把这个点击换做价格代入广告的模型, 因为没有二价计费那么讨厌的变换, 所以就按一价计费来考虑, 保证序正确且等比缩放就能保证收益最大. 如果再激进一点, 评估收益时还加入更复杂的因子而不仅仅是价格这个独立因素, 那自然就要求点击率预估准确, 从而保证做决策时和实际情况一致, 继而保证最终的优化目标最大化

总结

1) 点击率预估是为产品的最终目标服务的, 最终目标可以是广告的收入, 广告的相关性, 推荐的接受率等, 看具体场景
2) 点击率预估的直接目标根据需求场景不同, 分别是保证预估值和实际值分类正确, 预估序和实际序正确, 预估值和实际值是等比缩放的, 预估值等于实际值
3) 要保证离线评估点击率预估的效果, 分别可用分类的准确率和召回率, 排序的 AUC, 带权排序的 wAUC, 相似度 MAE/MSE 来评估

机器学习手记系列 1: Pearson 相关系数

Posted on by snoopy

系列说明

按合总指示, 给人人的机器学习小组写点科普性质的东西. 其实自己好像一直都没去系统的学过这些东西, 都是野路子乱搞, 这里把过去学的一点东西写出来, 记录一下, 班门弄斧, 欢迎拍砖.

自己接触到的机器学习, 几乎都是在用历史预估未来某事件发生的概率 (广告点击率, 推荐接受度, 等等).

将这个过程细化一下, 首先都是对历史样本提取特征, 将样本转换成用特征序列来描述, 将同类事件合并, 然后通过某种拟合方式去让特征带上合适的权重, 用于描述事件发生的概率, 最后对还未发生的同类事件, 同样将其转换成特征序列, 用学出来的权重转换成预估概率.

这里有两个关键问题, 一是特征选取, 二是拟合还原方法. 特征选取是为了将样本做合理拆分合并, 同质的才划分到一起, 不然就最后的预估还是随机猜. 拟合还原方法是保证在对数据做了合理拆分后, 能将特征的权重拟合到原数据上且能在预估时还原成概率.

问题

对怎么选特征, 似乎从来都没有好的普适性方法, 但是怎么验证选的特征靠不靠谱, 方法倒是挺多. 先抛开选特征的指导方向不说 (说也说不清), 如果我们选出了一类描述特征, 怎么验证其效果?

特征效果验证

最直接粗暴也是终极方案就是直接拿到线上去应用, 好就是好, 不好就是不好. 这是一句彻底的废话, 也是真理… 不过实际操作中很难真的去这么做, 一是如果要完成整个流程会比较耗时和麻烦, 二是没有那么多线上资源拿来实验, 三是如果实验不好带来的负面影响会非常大, 广告会损失收入, 推荐会严重影响用户体验. 所以如果线下没验证的心里有谱, 没人敢直接拍上去实验的, 老板也不会让乱来, 都是钱和能转换成钱的用户啊.

退回到离线验证上, 终极离线验证也还是拿机器学习的产出 (分类树, LR 模型, 或别的什么) 去评估一部分实验数据, 然后看对实验数据的预估结果是否和实验数据的实际表现一致. 这个还是存在耗时耗资源的问题, 后面再说, 先说简单的.

不管是分类树, 还是 LR 或别的 boosting 什么的, 都是希望能找到有区分度的特征, 能将未来不同的数据尽可能划开. 如果特征是一个 0/1 特征, 那数据就应该能明显被分成不一样的两份. 比如在豆瓣, “历史上关注过计算机类别书目的人” 是一个 0/1 特征, 如果拿这个特征来分拆人群, 并评估 “未来是否关注计算机类别书目”, 评估指标的 1 绝大部分都落在区分特征的 1 中, 那说明这是一个非常正相关的区分 (曾经干过某事的人会继续干另一件事), 效果很好, 反之拿去评估 “未来是否关注女性言情小说类别书目”, 很可能评估指标的 1 绝大部分都落在区分特征的 0 里, 那是非常负相关的区分 (曾经干过某事的人不会再干另一件特定的事), 效果也挺好, 但是如果是评估 “未来是否会关注武侠”, 评估指标的 1 是比较均匀的散布在区分特征的 0/1 里, 那就说明这个特征对该评估指标没有区分度, 还不如没有. (这些例子是随便拍脑袋写的, 不保证其正确性)

如果是一维连续特征, 则最后总特征总可以转换成一个一维向量 (连续值可以离散化成整数区间), 跟 0/1 特征一样, 比较这个特征的自变量取值向量和对应到评估数据上的取值向量的相关度就能判断效果好坏 (正相关或负相关都是好的). 一般最简单的是使用 Pearson (皮尔生) 乘积矩相关系数 r 来做是否线性相关的判断, 英文 wiki 上的条目 Pearson product-moment correlation coefficient 对该系数的含义和计算方法有比较详细的说明, 中文翻译比较杂, 百度百科上的是皮尔森相关系数, 微软的翻译是皮尔生相似度. 简要的说, pearson 相关系数是一个 [-1, 1] 之间的实数, 取值越接近 -1 表示特征值和评估值越负线性相关, 越接近 1 表示越正相关, 越接近 0 表示越不相关 (只是线性, 可能会有其他相关的关系).

还是拿豆瓣的例子说, 比如 “历史上关注过计算机类别书的数量” 作为一个人群划分特征, 那这维特征的自变量向量会是 <0, 1, 2, ...>, 为了取值方便, 将其截断到超过十本的也等于 10, 则向量变为 <0, 1, ..., 10>, 如果去评估 “继续关注计算机类别书的概率”, 这个概率取值可能是 <0.0, 0.1, ..., 1.0>, 则其 Pearson 相似度会是 1. (当然, 这个例子举的太假了点, 先这么着吧)

将问题化简为算特征取值和评估指标的 Pearson 相似度后需要做的工作就会少很多, 直接跑个 Map/Reduce 从 LOG 里提取下数据, 然后看看值的相关性就知道特征是否有区分度了, 没区分度的可以先不考虑 (或者将曲线相关的可能转变成线性关系, 再判断), 有区分度的才继续走更完整的离线验证, 加入分类树或概率模型和其他特征一起作用看效果, 如果还不错就上线实验.

微软的 Excel 里就带了 Pearson 相似度的计算公式, 可以很方便的拿来评估, 说明和用法请见微软帮助页面 PEARSON 函数. 如果要自己计算, 可以参考 wiki 的这个公式:

Pearson 相似度计算公式

C 的实现源码如下 (注意某些情况下可能会有计算精度丢失, 带来结果的不确定性)

double pearson_r(double x[], int x_n, double y[], int y_n) {
  if (x_n != y_n || x_n == 0) {
    return 0;
  }

  double n = (double)(x_n);
  double sum_x = 0;
  double sum_y = 0;
  double sum_x_sq = 0;
  double sum_y_sq = 0;
  double sum_x_by_y = 0;
  
  for (int i = 0; i < x_n; ++i) {
    sum_x += x[i];
    sum_y += y[i];
    sum_x_sq += x[i]*x[i];
    sum_y_sq += y[i]*y[i];
    sum_x_by_y += x[i]*y[i];
  }
  double res = n*sum_x_by_y - sum_x*sum_y;
  res /= sqrt(n*sum_x_sq - sum_x*sum_x);
  res /= sqrt(n*sum_y_sq - sum_y*sum_y);
  return res;
}