移动端转化延迟相关CPI转化率模型建模方法

介绍

很久没买美股了。昨天打开雪球扫了一眼结果惊呆了, 猎豹移动(CMCM)一天居然跌了40%, 其市值几乎和其现金等价物一致。于是搜了下新闻看到底发生了什么。后来了解到原来是Kochava(第三方监控公司)曝光猎豹旗下数款工具APP存在恶意欺诈行为,主要是大点击和安装劫持。做过移动广告的人应该都知道这两种模式,且这两种模式在行业内已经是不公开的秘密。之所以这两种恶意欺诈能够成功,主要还是因为现在移动应用市场归因机制的天然缺陷导致的。

目前国外应用市场相对比国内规范:国内各种应用市场,包括手机厂商自己的应用市场,以及BAT等巨头。而国外几乎只有两家,苹果的App Store和GooglePlay。但两种方式均存在安装归因缺陷。目前的方式是第三方监控公司(类似于Appsflyer, Adjust, Kochava等)监控来自某个应用或publisher的Impression或者click,之后在手机客户端产生app安装激活后,根据之前记录的来自该手机的impression和click,判定该安装应该归因给哪个publisher。该机制貌似合理,但存在很多问题:

  1. 归因时间过长,很多时候归因时间窗口能达到7天
  2. 第三方无法监控impression,click是否真实发生(可能是欺诈服务器自己构造的)
  3. 恶意抢归因:例如在用户没有看到,点击广告的情况下模拟impression和click, 让后来用户自然安装的应用被归因为广告的效果,或者直接监控手机用户的app下载,在检测到用户正在下载的时候发送该app的impression或者click强占该归因。可以认为和拦路抢劫比较类似

这些机制的存在都会导致整个移动互联网广告市场的混乱,大家不再专心做效果,而是将更多的心思和研发资源投入到如何构造更高明能绕过反作弊的机制。而辛苦做效果的广告公司却因为收益被抢而难于存活,形成劣币逐良币的恶性循环。

相关的欺诈反欺诈技术,不是一两篇文章能够描述透彻,也不是今天要讨论的内容。本文主要关注的点,主要还是讨论如何使用技术的问题,来对延迟归因进行建模。

图:CPI广告示例,流量测以cpm和publisher进行结算,广告主侧以cpi进行结算

之所以存在这个问题,是因为刚才提到,移动CPI(按安装付费)广告的归因窗口可以长达7天,甚至到30天:即广告在被展示后,点击后,最终的归因,例如移动CPI广告的安装激活可能在用户展示点击后的7天才会发生,这和传统的CTR预估问题不一样, 传统的CTR预估,可以认为在向用户展现广告后我们马上就能知道用户有没有点击,而手机移动端则可能需要7天甚至更长时间。这样在训练模型时,就会带来以下几个挑战:

  1. 数据量:对于CPI广告,安装毕竟是少数,如果仅使用有点击的训练样本进行训练,会导致训练样本较少,学习出来的模型能力较差
  2. 训练样本的选取有偏:即使是CPI广告,在线上进行预估的时候,也是有impression(甚至是有request)的时候就需要去预估CPI,而如果我们仅挑选有点击的展示作为样本进行训练,会导致和线上真实面对的分布不一致
  3. 如何选择训练样本? 传统方式下有以下几种方案:
    1. 因为新的广告不断出现,故需要模型及时更新避免效果损失,但如果在模型训练的时候,将暂时还没有转化的样本视为负样本,则可能将后续潜在的正样本也当做负样本进行训练,效果不会理想
    2. 收集满7天数据后进行训练。此时是否为真实正样本已经确定,但该方式的缺点是模型会滞后7天才能训练出来
    3. unlabeled的样本(还暂时没有conversion的样本随机作为负样本),相当于半监督学习,该方式的缺点是:线上click后产生conversion的分布并不是随机的,而是离点击时间越长,转化的概率越小

所以以上传统的3中方法都不太可取。而既然click后产生conversion的分布不是随机,而是离点击时间越长,转化概率越小,那能否将该信息建模到模型中。本文参考医学中的survival time analysis方法,根据click到conversion之间的时间差,对样本是否为真实正样本的概率进行建模。

图:impression->click->conversion的样本空间差异,如果仅用有click的样本训练pcvr,则会导致和线上impression的空间不一致

图:click->conversion用户安装,中间的时间间隔可以达到7天,导致7天内很多样本都是unlabel状态,因为并不能确定没有conversion的样本后续就不会有转化

问题定义

线上的目标是准确预估ecpm,即千次展现的花费。而ecpm可以进行如下拆解:

其中1)项我们可以认为是传统的pctr模型,2)为pctcvr模型,即在有impression,click的情况下产生conversion的概率

故可以对问题进行一下定义:

此处我们根据线上数据,能观察到的数据如下:

  1. xi:即特征
  2. yi:截止到现在,是否已经发生conversion
  3. ei:从点击到当前时间的时间差
  4. di:如果yi=1,则从click发生到conversion发生的时间差

以上定义存在以下约束关系:

  1. Y=0-->C=0 or E<D 还未观察到转化,则可能该样本为负样本永远不会转化;或者E<D,即后续会产生conversion只是现在暂时还未发生
  2. Y=1-->C=1
  3. P(C,D|X,E) = P(C,D|X) 即样本的固有属性,不会应为观察时间而改变

有了以上定义和约束关系后, 即可对问题进行重新建模,将问题建模为以下两个子模型:

  1. P(C|X):即传统的pcvr模型
  2. P(D|C=1,X):即给定样本特征后,且假设该样本为正样本的情况下,conversion发生的时间

再具体到具体模型的实现,P(C|X)为经典的pcvr预估模型,故可以使用传统的LR模型,或者更为复杂的模型。此处假设使用LR模型,即:

P(C|X) = 1/(1+exp(-w_lr*x))

而P(D|C=1,X)则使用指数分布进行建模,即:

P(D|C=1,X) = lambda(x)*exp(-lambda(x)*d),其中lambda(x)=exp(w_lambda*x)为hazard函数,此处借鉴了survial time analysis的思路。故最终建模中,需要学习的参数有两组:w_lr和w_lambda。

损失函数

对观察到的数据,分为两类:

  • P(Y=1,D=di|X=xi,E=ei),即已经观察到存在转化,为C=1的情况推理公式如下:
  • P(Y=0|X=xi,E=ei),即距点击已经过去了时间ei,但还未观察到conversion,推理公式如下:

在Y=0 and Y=1的情况都公式化后,根据我们能够拿到的数据<xi, yi, ei, di>,根据最大似然估计构建损失函数:

之后使用梯度下降法求解w_lr和w_lambda即可完成建模。

总结

  • 该方法适用于用户行为存在较长流量漏斗, g. 移动端request -> impression->click->conversion,且click->conversion存在较大延迟的场景
  • 该方法能够使用impression对应的数据进行建模,且建模的过程中引入了对click后产生conversion的时间观察,更符合样本的内在天然属性
  • 该方法不仅适用于移动端cpi广告,同时对电商类似的具有较长流量,交易漏斗的场景同样适用。

参考文献:

  1. <Mobvista海外移动变现系统核心技术>
  2. <变革:从运营驱动到数据驱动>
  3. Chapelle O. Modeling delayed feedback in display advertising[C]//Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014: 1097-1105

 

GITC演讲-滴滴路况感知AI及应用

背景介绍

第三次受邀作为嘉宾参加GITC人工智能方向的演讲。前两次的演讲题目都和推荐和变现相关。因为现在在滴滴负责地图感知AI团队,所以这次介绍的内容主要和地图AI相关。

地图与推荐&变现AI技术差异

地图中设计到的AI技术与推荐&变现既有相同的地方,但也有很多的不同。

地图是一个整体上环节较多的复杂问题,整个地图系统中涉及到数据采集,生产,更新;中台的各种数据引擎;以及最终的地图应用。而且在涉及到数据生产的过程中会更像传统行业的生产过程,会涉及到较多的生产工艺保证数据质量,如果数据质量上不去,后边的算法效果就无从谈起;同时整个地图产品中涉及到的环节较多,包括底层的物理世界感知,例如定位,地图匹配, 实时路况或者路况预测;作为引擎的路径规划(route planing),ETA,上层的导航等, 均是环环相扣,某个环节没做好,可能都会导致最终效果较差。同时地图还存在另外一个较大的问题:效果不容易评估。

而相较之下,变现或者推荐反倒是一个相对单纯的问题,所有的数据,包括内容数据,用户反馈数据均形成闭环,而且相对来说也较为容易评估

演讲内容

地图中AI的使用场景非常多,例如定位,地图匹配,实时/预测路况,上下车点,ETA,路径规划等。这次演讲的内容主要集中在地图感知AI。什么是地图感知AI? 说的简单一点,就是我们如何通过大规模的预采集数据,以及用户反馈数据,来感知物理时间中发生的和交通相关的状态和事件。该方向涉及到的环节也非常多,故这次演讲主要集中在底层的地图匹配和实时路况/路况预测两个方向。

图:地图感知AI技术:定位,地图匹配,(实时/预测)路况

地图匹配(Map-Matching)

图:基于隐马尔科夫模型的地图匹配(Map-Matching)

目前业界比较流行的地图匹配的算法来源,基本的思路都来自于微软09年发布的基于马尔科夫地图匹配算法。该算法的基本思路是将GPS点匹配某条候选道路的概率,拆解为发射概率(观察概率)与转移概率的组合。具体参见博文《LBS地图Map-Matching流行算法及应用

该方式的优点是模型相对简单,且在很多场景均能够取得较好的效果。但缺点也很明显:该算法很难进一步融入更丰富的特征, 例如GPS的精度,候选道路的属性等,以及运动信息(例如速度是否超过限速信息)

所以后来Map-Matching提升效果的思路逐渐演变为融合多维信息,而最直接的方法就是使用Shallow模型进行学习。

图:浅模型Map-Matching算法

路况预测

该方向一般一开始的做法,也是性价比最高的做法,都是快速根据专家的经验,使用规则的方式将效果快速做上去,因为现实物理世界情况太多,而且很多时候是只要某个因素发生的时候, 就能够确定现实物理世界发生的情况,但该情况覆盖的CASE却不多。所以一开始使用规则的方式,一方面性价比比较高,另外一方面也能够让我们把问题分析理解的更透彻,例如现实世界可能会出现哪些情况,应该使用那些规则来进行处理。而这些规则, 后续很容易转变为模型的特征输入。

图:Rule-based 路况发布

所以在rule-based的算法做到一定效果后,我们就开始尝试浅模型的方法,为了保持系统的可解释性,我们选择了经典的xgboost。虽然模型并没有那么高深,但效果提升比较明显。

图:浅模型路况发布

而后续需要进一步提升效果,就需要做两方面的工作:更多高质量,信息更丰富的数据, 以及表达能力更强的模型。

对于数据:GPS信息的使用虽然还有空间,但天花板已经比较明显,很难使用GPS就出现质的飞越;此处解决的思路是引入图像数据,因为图像是现实世界的绝对真实体现,信息丰富。

而从模型的角度,浅模型的缺点是很难将时间和空间关系建模进模型。解决的思路很直接:使用图卷积学习空间依赖关系,而使用时间序列学习时间依赖关系。目前该算法还在尝试中[6]

图:时空依赖模型

ETA

ETA内容在《工业界ETA技术及滴滴WDR模型》中进行介绍,故此处就不进行展开

图:DIDI WDR ETA[5]

更多内容请参见GITC发布的演讲视频,或参见PPT:滴滴地图感知AI技术及应用

参考文献

  1. 《2017年滴滴出行平台就业研究报告》
  2. 滴滴地图感知AI技术及应用
  3. Gers, Felix A., Jürgen Schmidhuber, and Fred Cummins. "Learning to forget: Continual prediction with LSTM." (1999): 850-855.
  4. Cheng, Heng-Tze, et al. "Wide & deep learning for recommender systems." Proceedings of the 1st Workshop on Deep Learning for Recommender Systems. ACM, 2016.
  5. Wang, Zheng, Kun Fu, and Jieping Ye. "Learning to Estimate the Travel Time." Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM, 2018.
  6. Zhang, Zhengchao, et al. "Multistep Speed Prediction on Traffic Networks: A Graph Convolutional Sequence-to-Sequence Learning Approach with Attention Mechanism." arXiv preprint arXiv:1810.10237 (2018).

https://outreach.didichuxing.com/tutorial/kdd2018/