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/

[LBS]地图Map-Matching流行算法及应用

14年之前一直都在做推荐和变现相关的工作,甚至14年入职高德负责高德变现系统时候也是推荐&变现的延伸,但那时已经开始涉及LBS相关的领域,所以可以认为从工作到现在,自己在做的事就是两个方向: 推荐&变现(推荐和变现很多技术比较类似,所以暂且放到一起),以及LBS。今年初入职滴滴负责滴滴地图的部分AI业务后,主要的精力反倒是转到了地图行业,也算是重新回归LBS这个领域,这个过程中也在寻找地图和传统互联网技术(e.g. 推荐&变现)的结合点和爆发点。虽然目前还没找到,但总感觉是可以有明显的创新和爆发点的,原因如下:

  1. 推荐&变现,变现的主要技术还是纯线上,但现在纯线上流量似乎已经趋于垄断,想玩出花的机会正在变少(当然还还是有很多优秀的公司不断有新的突破,例如今日头条)
  2. 出行领域市场非常巨大,但涉及面比较广,而且这个行业现在似乎还处于传统行业向互联网转的过程中;相当于人们的刚需,现在并没有得到很好的满足
  3. 地图更偏传统行业,数据采集,清洗加工流程都比较重工艺和经验流程,中间很多环节还需要人工参与,成本较高,可改造潜力较大

所以想要找到创新的结合点和爆发点,就需要深入了解地图行业的细节。而如上提到:地图行业更偏传统行业,有很多自有的业务和技术需要学习,内容实在很多[4]。正好近期在整理地图行业的一个基本topic:Map-Matching(中文应该翻译为路网匹配,或者简称‘绑路’),所以就在此记录下这个方向的技术供自己备忘,也有利于同行参考。

Map-Matching背景介绍

一般LBS场景,最基础的数据有三种类型:路网数据, 用户(司机 or乘客)GSP数据,以及用户在产品中的交互数据。其中路网数据包括道路,POI点以及挖掘出来的描述静态物理世界的数据,用户在产品中的交互数据此处比较笼统,可以包含用户的静态Demographic和用户在产品中的使用习惯数据,而本文的重点相关的是第三类数据,即用户的GPS数据。

目前智能手机都集成有GPS芯片,能够间隔一定时间(例如1s)采集一次GPS定位信息, 该信息包括GPS横纵坐标,精度,速度,在各方向加速度等信息,因为采集周期较短,持续时间较长,故在用户量较大的应用中,该数据的规模会非常大,但也是最丰富的采集数据之一。而且该数据是对用户在物理世界时间空间最直接的描述,所以能够挖掘的信息非常丰富。

但问题来了,GPS点采集的时候因为卫星信号的强弱,或是设备周围信号受到干扰(例如有高楼),特别是民用GPS本来就会有误差,导致最后这些数据的漂移在几米到几十米不等,这样就会导致我们采集到的点都是有随机漂移的点,并不能完全反应用户真实的位置。而对于类似于高德,百度,滴滴的地图场景,我们需要知道车辆到底是以怎样的轨迹行驶,在什么时候行驶在什么路上。此时Map-Matching就是LBS服务较为基础的技术,因为它将不精确的用户轨迹点序列映射到确定的路网上。如下图示例:

图:MM示意,其中绿色点为GPS点,蓝色线为map-matching结果,可见GPS点存在飘逸,特别是道路比较密集的场景

虽然理论上GSP点的漂移为10米以内,但在实际应用场景中因为天气,周围环境(高楼,树木,卫星数量等)可能导致的GPS点偏移最高可达数十米,而对于城市中密集的路网来说, 数十米的漂移将会导致map-matching的错误概率大大增加。

而同时map-matching又是很多GPS/Trajectorys挖掘的基础(例如如何挖掘用户出行模型,如何对人流,交通进行建模等),所以map-matching是一个即基础,又重要,且具有较大挑战的基础研究应用方向[1][4]

图:Map-Matching在用户GSP/Trajectory Mining体系中的位置[1]

下文就对当前常用的map-matching算进行介绍,并对后续可能的研究方向进行分析阐述。

Map-Matching算法及挑战

那Map-Matching具体是什么,通俗来讲就是绑路(或者路网匹路),就是将收集到的同一用户(例如高德,百度地图或者滴滴地图司机)在时间空间维度的一系列存在精度损失的GPS点,匹配到最有可能的地图路网具体道路上。

但这个过程存在以下难点及挑战:

  1. GPS点存在精度损失(或漂移),精度损失在十米~数十米不等
  2. 城市道路密集,在小范围内可能存在较多道路
  3. 很多道路间距较小且平行(例如主辅路),或者主路出辅路的交叉口, 这些路上的GPS点甚至从统计的角度都看不出明显规律;或者存在垂直空间重合的路(例如路面和地下隧道平行)

以上都是map-matching在实际计算过程中的挑战,而且很多到现在都没有解决好,也没有很好的思路。

同时学术界和企业的研究关注点是不一样的,学术界主要基于公布的开源数据进行研究,这些数据有以下几个特点:

  1. 数据量较小
  2. 数据单一,一般除了GPS点外,没有其他数据可用
  3. 路线相对单一
  4. 对结果的精度要求相对不高(部分场景)

Map-Matching在滴滴的挑战

但企业就不一样,例如滴滴,和学术界研究的Map-Matching比起来,以下是主要的区别:

  1. 数据量非常大,每天几千万订单,汽车行驶过程中每秒或者每3秒一个GPS点,同时还有合作伙伴的数据;数据量大就会对实时处理性能,以及离线挖掘的数据处理能力提出挑战
  2. 大城市中路线比较复杂,道路比较密集
  3. 对精度要求非常高,甚至需要根据map-matching结果按照里程决定司机的收入,如果map-matching错误,不仅仅会影响到用户体验,还会导致司机或者滴滴平台的损失。例如绑路错误会直接导致平台判定司机行驶路线错误,导致计费错误。涉及到钱的,大家都异常关注和敏感

Map-Matching常用算法

Nearest Neighbor

该方法只是理论般的存在,在现实中根本无法使用, 因为精度太低。思路比较直观:直接计算对应GPS点和候选道路的投影距离,将GPS点匹配到最近的候选道路上。理论上可行,但具体应用的时候,因为城市道路比较密集,且GPS点存在较多漂移,故该方法不可用。一般甚至不会将该方法作为baseline。

图:nearest-neighbor方法,GPS点直接绑到投影距离最近的道路上

HMM

地图匹配中比较经典的方法是使用隐马尔科夫模型(HMM)来实现,该方法的使用方式主要来自于论文[2]。该论文2009年公开发表。目前国内几个互联网地图公司的map-matching算法实现的基本思路基本上都来源于该论文。该论文使用HMM对地图匹配过程进行建模,将匹配的概率分解为观察概率及转移概率的综合结果。

图:有r1,r2,r3三条候选link,两个gps点zt,zt+1,假设zt在r1,r3上的投影分别为xt,1,xt,3,zt+1在r2上的投影为xt+1,2,则该方法的核心思想为:route距离和greate circle距离越小,则可能性越大。此处greate circle为zt到zt+1的球面距离,route距离为假设汽车在某条route上行驶所产生的距离,例如途中的|xt,1-xt+1,2|_route和|xt,3-xt+1,2|_route

在此思路框架下,对观察概率(或叫Measurement probabilities,或emission probabilities),以及转移概率(transition probabilities)进行建模,建模方式如下:

 

观察概率:可以将观察概率建建模成mean为0的高斯分布

图:观察概率建模

其中gc表示为great circle的缩写,表示两点球面上的最短‘直线’距离。其内在含义就是, 如果点zt离ri的球面‘直线’距离越近, 则从观察的角度我们认为zt更有可能在ri上

转移概率:我们假设两个gps点zt,zt+1的距离和对应在道路上的投影点间的路径规划距离(route plan distance)的偏差越小,则说明汽车更有可能在沿ri,到rj的route上行驶(试验也证明这个假设是正确的)

图:转移概率:great cicle距离和route距离差值较小的绑路结果更有可能为真实的绑路结果

有了观察概率和转移概率后,使用维特比算法进行求解

具体涉及到观察概率中高斯分布中的方差,可以使用真值ri和zt的投影距离的Mean Absolute Deviation(MAD)进行参数估计

另外在线上系统使用中,为了保证算法的效果,一般会对数据进行预处理,包括但不限于:

  1. 寻找候选道路时,会仅将观察gps点zt一定半径范围内的link作为潜在的可能link,该半径以外的link将直接将观察概率设置为0。论文[2]中建议的半径范围为200M,但在实际使用中(例如滴滴的使用场景),该半径值会小很多, 因为滴滴的场景更偏城市,路网更加密集,且每秒需要并行处理的量比学术界高很多量级,故候选link搜索半径更小
  2. Route Plan距离和Greater Circle距离差超过阈值的后续link也会被直接置为概率为0, 其中的思想是我们认为这两个值比较相关, 偏差不可能太大
  3. 使用Route Plan距离,以及两个观察点zt+1, zt的时时间差计算出来的行驶速度大于阈值的route,也认为不可能成为候选link,例如计算出的行车速度超过150km/h

在该HMM算法框架下,能够衍生出很多的变种,它们中大部分都是围绕着如何引入更多的信息来对转移概率进行更精准的建模展开了,例如可以在转移概率中不仅考虑greate circle 和route plan distance的差值,还引入转弯次数作为影响因子[3]提升整体算法的效果

HMM+Shallow Model

从数据特征

HMM虽然是经典的map-matching算法,并且和其他算法相比效果上也有优势,但该算法框架下很难引入更多维度的丰富特征提高地图匹配的准确性。例如GPS点其实有很丰富的数据,例如点速度,点方向, gps点的精度;点和候选道路也有较多可以提取的信息, 例如投影距离,是否超速,是否逆行; 另外还可以加入路网特征,包括道路等级, 限速, 车道数等;最后也可以引入HMM中使用的转移概率等信息。以上信息均可以作为模型的输入。

Lable

地图匹配和路况发布一样,有一个最有挑战的问题就是真值的获取。

现在一般有三种方法来获取真值

  1. 人工标注:如果要使用模型, 那至少需要标注几百万的点(我们真的人工标注了几百万的点, 是不是觉得比较汗。。), 耗时耗人
  2. 规则选取:可以通过对已经发生完整轨迹,使用规则判定轨迹中间的部分的绑路结果,例如轨迹中间某段不能确定是在主路, 还是辅路, 但根据后来的轨迹方向可以确定(比如辅路有右拐但主路执行,且轨迹右拐,则说明之前的行驶点是在辅路上而非主路)
  3. 图像+ gps: 使用行车记录仪的图像,确定该图像对应的GPS点所属的道路

模型

使用一般的分类模型即可进行学习, 例如FM或者FFM

因为引入了更丰富的特征,故HMM+Shallow Model的方式效果一般都比HMM要好。我们的试验中,绑路准确性能够提升3.5%

近些年深度学习是模型算法的趋势,但该处我们并没有使用深度学习来解决该问题,主要的原因还是因为真值label获取相对困难,量级没上去,后续随着规则选取及图像的自动化label获取流程打通,成本降低后,会使用LSTM等时间序列模型来提升效果

IRL Map-Matching

学术界还有一类算法来提升Map-Matching ,就是使用强化学习[3]。其思路还是将Map-Matching问题建模为HMM,仍然是将最终的概率分解为观察概率(Measurement Probability)及转移概率(Transition Probability),只是具体操作的时候有以下两个变化:

  1. 计算转移概率的时候,不仅仅使用greate circle 距离和route plan距离的差值计算转移概率,同时引入转弯的信息计算转移概率
  2. 计算转弯概率权重的时候, 使用max entropy IRL进行参数估计。

作者号称该方法能够将error rate降低40%(impressive,但是我没尝试过)

Map-Matching后续研究方案

滴滴每天有接近3KW个订单,每个订单都能产生较多GPS数据,故在滴滴,Map-Matching的挑战主要有以下几个:

  1. 数据量巨大,需要在效果和性能间做tradeoff,甚至考虑到map-matching性能,我们会在客户端上使用简单算法进行地图匹配,只有等到客户端地图匹配置信度较低的时候,才请求后台服务
  2. 真值数据的缺失:人工标注始终成本比较高,而且准确性没有保障,故,如何使用多元数据获取map-matching的ground-truth也是一个挑战。 例如使用行车记录仪图像作为map-matching的真值标注

另外地图匹配处理的数据天然就是一序列的GPS点信息,故从处理算法的角度,比较适合使用时间序列模型来进行处理。目前我们也准备将底层的处理逻辑由原有HMM+Shallow模式向时间序列模型进行迁移。

Reference

  1. Zheng Y. Trajectory Data Mining: An Overview[M]. ACM, 2015.
  2. Newson P, Krumm J. Hidden Markov map matching through noise and sparseness[C]// ACM Sigspatial International Conference on Advances in Geographic Information Systems. ACM, 2009:336-343.
  3. Osogami T, Raymond R. Map matching with inverse reinforcement learning[C]// International Joint Conference on Artificial Intelligence. 2013:2547-2553.
  4. eta技术:http://www.semocean.com/lbs%E5%B7%A5%E4%B8%9A%E7%95%8Ceta%E5%BA%94%E7%94%A8%E5%8F%8A%E6%BB%B4%E6%BB%B4wdr%E6%8A%80%E6%9C%AF/

更多内容也可参见: http://www.semocean.com

推荐系统,变现系统CTR&CVR预估算法演进

背景介绍

在推荐系统,或者移动广告变现业务中,抛开内容的生产,用户的增长等挑战后,从算法的角度存在以下几个比较有挑战的技术点:

  1. 冷启动问题(Cold Start):新的用户如何处理
  2. 新广告探索(Exploitation&Exploration):没有历史统计信息的item或者广告如何快速确定其效果,既不能再新Ads上浪费过多流量,也不能每次都采用贪心算法仅关注短期利益
  3. 转化延迟产生建模问题(Modelling Delay Feedback):从点击到最终效果的产生中间有较长时间的间隔,如何对该问题进行建模。具体问题描述和解决方案可参见《移动端转化延迟相关CPI转化率模型建模方法
  4. 点击率预估(CTR)

这些问题解决的好坏都会严重影响系统的效果,而且每一个问题在工业界&学术界都有较多的研究。

下文主要对第4个问题:点击率预估近几年的发展进行简单总结,供大家参考。

广告和推荐算是比较经典老牌的大数据落地的业务场景,而其中的核心技术点CTR预估中使用的技术,也从最经典的LR,逐步发展到树模型,FM等,而近几年随着深度学习技术的发展成熟,现在CTR预估(包括转化率预估)也逐渐开始使用深度学习,并且在各大公司的业务场景中均已经得到较大程度的效果提升。下文就对近期出现的和深度学习相关的CTR预估模型进行总结。方便我个人review也供大家参考。

问题定义

可以简单定义CTR预估问题为预估P(C|X),其中:

  • C为是否点击
  • X为使用的特征,X在变现中会包含用户profile特征,用户行为特征,广告特征,场景上下文特征

当然,在更复杂的应用场景下,可能我们不仅需要预估CTR,同时还需要预估CVR(转化率),则此时的问题建模为:

ECPM=P(CLK|X) * P(Conversion|CLK,X) * CPA,此处主要讨论P(CLK|X).

LR

传统的方法主要是使用LR来进行CTR预估,该方法能够适用的主要原因是LR相对来说不仅比较简单,更偏记忆的模型,该模型会记忆高频出现的特征,相当于是对历史的exploitation。而且该模型容易进行并行化,线上处理也非常快,因为虽然训练的时候特征空间有数十亿维,但线上真实使用过程中,非0的特征一般也就就是个,所以处理性能较高。当然该模型缺点也比较明显,就是该模型更多是对历史的记忆,但需要很多人工特征组合,否则原特征的维度上可能不能很好地划分问题,同时人工特征组合也相当于增加了模型的个性化描述,效果会更好。

GBDT+LR

该方法是facebook发表的其广告系统中使用的CTR预估算法(参见《深度学习资料》),也算是业界比较经典的算法了。主要思路为:1,使用GBDT进行特征抽特征(进行自动特征组合);2,使用LR对GBDT抽取的特征(规则组合)进行权重学习。3,一般训练的方式为先将GBDT训练好,之后固定树模型并对叶子节点进行编码作为LR特征训练LR。该方式在业界有较为广泛的应用,例如滴滴路况预测中,能够提升有效准确率2%,而美团ETA应用中预估时间的MAE能够下降3.4%(与论文中3%的下降接近).;同时文中对影响CTR模型效果的几个因素进行了分析,得到以下几个结论:

  1. 模型的自动更新很重要:模型一周不更新,效果下降1%左右,考虑到性能,甚至可以gbdt模型更新频率相对低,lr更新相对快
  2. 对于gbdt+lr模型,historical特征较为重要(top 10特征均为historical特征),但contextal特征对cold start较为重要
  3. 参数更新的schedule方法中,per-coordination方式明显好于其他方式
  4. 在display ads中,训练时可以进行负采样,但后续线上使用的时候需将概率分布转换回原分布:q=1/(p+(1-p)/w),其中q为最终ctr值,p为采样后模型预估值,w为负采样比例

当然,如果只是预估排序而不是具体的CTR值,则可以不做步骤4。

该方式和单纯的LR相比,其实已经包含了自动特征抽取的思路,因为GBDT模型天然就是进行特征组合(抽取特征),之后再使用LR来学习这些组合特征的权重;而该方式的另外一个优点,就是能够很好地处理连续特征,如果单纯使用LR,我们还需要进行特征离散化,而GBDT天然就对连续特征进行处理。

图:GBDT+LR.使用GBDT进行特征自动组合,其实现在使用DNN的主要作用也可以认为是使用DNN自动抽取高维度特征

更进一步,在该算法的基础上逐渐出现了一系列变种,我们可以称为GBDT+LR Plus,其思路和GBDT+LR类似,只是受限于GBDT的结构,GBDT能够很自然地处理连续值特征,但对离散特征的处理不够好,反过来LR能够很好地处理连续值特征,所以后来衍生出来的模型结构, 一方面使用GBDT来提取特征后作为LR的输入,同时仍然保留离散特征作为LR的另一部分输入,这样LR模型就同时具有GBDT特征组合和离散特征。当然该处的LR可以换成FM,或者FFM等模型。具体的实例参见《深度学习资料》中关于CTR部分的Kaggle Criteo Ctr预估介绍:3 Idiots’s Approach for Display Ads Challenge. 为Kaggle上Critero ctr预估第一名使用的方法,主要的思路为:

  1. 使用GBDT对连续特征,以及出现频率极高的离散特征进行特征组合(类似于FB display ads ctr预估)
  2. 组合出来的特征,结合离散化后的连续值特征,原有离散特征(共3类特征)
  3. 使用FFM进行CTR预估,并在得到CTR值后对预估值进行Calibration(简单地加减一个固定值)

图:GBDT+LR Plus:GBDT后,离散特征仍然输入至线性模型,相当于线性模型的特征输入包含两部分:离散特征+GBDT组合特征

总体来说,这个时期大家的工作还都集中在如何使用浅模型让效果最优,例如很多公司在推荐系统中使用FM(例如头条的推荐系统),而类似于Kaggle这样的专门比赛的场景,则更倾向于ensemble的算法,例如《深度学习资料》介绍的Kaggle Avazu CTR预估:4 Idiots’s Approach for Display Advertising Click-through Rate Prediction. 另一个Kaggle上的display ads ctr prediction 比赛,冠军组使用的方法介绍中,有两个关键点:1,ensemble,目前已经成为competition的标配;2,feature engineering,文中使用了较多单独构造的feature,例如user /deviceid count,  hourly impression count; user installed app bagging,  user click action的编码等。最终获奖的模型为20个ffm的ensenbling

Wide&Deep

之后很长时间,工业界使用的方法都是类似于GBDT+LR,FM,FFM之类的浅模型;如果是比赛场景,则更多会在这些模型的基础上进行essemble。而对于深度学习,大家基本上都持观望态度,一方面是大家会有一个初步的判断,就是深度学习更多适用于信息完全且格式规范化的问题,例如图像(输入图像中包含所有信息,格式统一),而能不能应用在信息稀疏的场景有待验证;另一方面是深度学习对计算资源的要求比较高,一般没有GPU卡基本上不用去尝试,速度非常慢,而GPU卡的成本又非常高,所以很多公司并不会投入那么高的成本去尝试一个未知的东西,特别是创业型公司或者业务驱动的公司。直到2016年,随着GooglePlay app推荐场景,以及Youtube视频推荐场景下google在深度学习推荐上取得明显效果,且论文发布后,深度学习在这个领域的应用才得到更多的关注。

以GooglePlay app推荐为例,GooglePlay App推荐:《深度学习资料》:Cheng H T , Koc L , Harmsen J , et al. Wide & Deep Learning for Recommender Systems[J]. 2016.提出了Wide&Deep方法(同时可参见《lbs工业界eta应用及滴滴wdr技术》),主要思路是使用Wide线性部分作为Memorization,对历史信息进行exploit,而使用Deep部分,对特征进行自动的更高层次的组合与抽象(个人理解和NLP中的模式类似,Deep部分能够学习复杂计算,同时对特征进行组合并生成embedding)进行自动特征组合,并进行更高层次的泛化,相当于对训练数据中的信息进行explore。该方法同时解决了wide需要进行手动特征组合的缺点,以及Deep有可能过拟合的缺点;而训练的方式为进行Jointly training,其中wide部分使用ftrl训练,deep部分使用adagrid后adam进行训练...Note…P.S. 目前Wide&Deep已经作为一个标准Framework解决分类和回归问题,例如滴滴ETA模型,我们使用Wide&Deep&Recurrent的WDR方法进行ETA预估(可参见《lbs工业界eta应用及滴滴wdr技术》)

图:Wide&Deep:离散特征进行embedding之后和连续特征进行concat作为deep输入

W&D变种

Wide&Deep推出后,基本上就作为业界的一个baseline的算法框架使用,在这个过程中也会有比较多的网络改进。改进的思路也基本上是在弥补Wide&Deep的各种不足。而优化的方向,基本上就是两个:要么优化wide部分的能力,要么优化deep部分的能力和效果。

Deep Cross Network

例如:Wang R, Fu B, Fu G, et al. Deep & cross network for ad click predictions[C]//Proceedings of the ADKDD’17. ACM, 2017: 12. 提出的DCN,在DNN的基础上,增加使用cross network对特征进行交叉。文中cross network有两个特点:

  1. 能够限定特征交叉的阶数(bounded order),且可以认为cross network的depth数,就是特征交叉的阶数
  2. 每次进行特征交叉的时候,相当于同时在做和第一层输入的交叉,同时在学习上一层的残差。最后cross network再和dnn进行combination。和deepfm相比:相同点是网络结构比较类似。不同点在于cross network从理论上能够从cross network的网络层数控制feature intesection的阶数..Note..

图:DCN示意图:DNN的同时,增加cross network

具体推导公式为:

图:DCN网络交叉方式:每一层均和输入进行交叉学习残差。同时可以认为cross network的层数,就是特征交叉的阶数

DeepFM

另一种比较常见的模型结构是DeepFM. 2017 Huawei App Recommender Ctr Prediction:Guo H , Tang R , Ye Y , et al. DeepFM: A Factorization-Machine based Neural Network for CTR Prediction[J]. 2017.华为App应用市场发布的推荐方法,基于Wide&Deep,区别在于两点:

将Google的Wide部分的LR模型换为FM,用于学习特征二阶交叉

不同于其他Deep的模型,FM和Deep部分使用的特征的Embedding是相同的,相当于low &hight order feature intesection都会反映到Embedding中在Wide部分和Deep部分进行共享,且训练速度和FNN(FM与训练V作为Deep Model Embedding参数初始化),PNN(Embedding和First Hiden Layer之间进行一次inner production,效果不错但增加了全连接规模导致训练较慢)要好。PS.在滴滴ETA模型中,我们就借鉴了DeepFM思路,不过其中的Deep部分会比较复杂,同时在最终的融合部分,增加了初始Additive ETA Model…..Note。该方式与传统的Wide&Deep方式相比的优势是,对于Wide部分,模型不用再使用太多人工特征,可以认为FM能够很好地完成低阶(二阶)特征组合

图:DeepFM网络结构图:1,wide部分使用FM代替;2,embedding wide&deep共享

Deep Interest Network

Zhou G , Song C , Zhu X , et al. Deep Interest Network for Click-Through Rate Prediction[J]. 2017.目前deep learning在CTR&CVR预估上,使用较多的方法是Embedding&MLP的方式,思路是对原来稀spase features先进行embedding,之后进行feature group wise的pooling,例如sum或者average,之后得到定长的vector再输入MLP(MLP可以有很多变种,例如res-net思路)。该方式在淘宝上的缺点是:user的兴趣可能不止一个,例如年轻妈妈可能关注自己喜欢的时尚衣服,同时也在购买婴儿用品,故直接sum/average的user featrues pooling方式存在信息损失,既进行pooling后,在embedding空间中得到的向量可能和该用户的众多兴趣距离都较远。故Deep Interest Network将user behavioral embeddings与ads的embedding使用local network的方式进行学习,最大程度上根据用户historical 的behavioral feature体现与ads的相关性,从网络结构的角度,我们可以认为是每个ads去和最相近的user behavior embedding来进行权重分配,以便突出地体现和该广告相关的用户行为…Note..

图:DIN(Deep Intresting Network)

FM深度化

CTR预估模型的另外一个发展方向是在原来FM的基础上,引入深度学习的思想,将二者结合起来,者可以认为是FM的扩展或者能力的增强

例如Attention Factorization Machine

Xiao J, Ye H, He X, et al. Attentional factorization machines: Learning the weight of feature interactions via attention networks[J]. arXiv preprint arXiv:1708.04617, 2017.网络结构中的设计思想是认为FM中,每个特征对应的隐变量(embedding)在使用过程中的权重都相同(均为1)是不合理的。特征在进行交叉的时候,权重应该不一样。故在FM结构中增加attention network来学习特征embedding进行element-wise交叉时候的权重。该方法一方面能够提升效果,另一方面,也能够根据特征交叉过程中的权重,分析交叉特征的重要性:通过分析网络产生的attention score,能够观测到哪些特征的组合重要性更高(和未做attention的fm相比)。而文中通过先固定attention score训练fm embedding,之后再固定embedding训练attention权重的方式,也验证了在传统fm上增加attention network的确对最终的效果有正向作用..Note..

图:添加了Attention的FM,背后的intuition是fm进行二阶交叉时,特征的重要性是不一样的,通过Attention来捕捉该差异

又例如在Neural Factorization Machine中,He X, Chua T S. Neural factorization machines for sparse predictive analytics[C]//Proceedings of the 40th International ACM SIGIR conference on Research and Development in Information Retrieval. ACM, 2017: 355-364.在FM后增加了隐藏层,以便在原有FM线性二阶交叉的基础上增加非线性的更多特征交叉。这类方法我们都可以认为是在FM的基础上,使用DNN的思路,对FM进行能力的增强。

图:Neural Factorization Machine在FM进行二阶embedding交叉后,引入DNN进行更高阶交叉

总结

当前的CTR预估已经大规模使用深度学习,而且在工业界和学术界仍然在不断地有新的网络结构出现,所以不出意外这些新的网络结构的研究应该还能火两三年。但今年去加拿大参加NeuraIPS时发现一个趋势,就是很多研究人员,以及类似于Google这样的公司都在大力投入到AutoML中,也就是使用机器学习的方法,类似于搭积木似的去寻找最优化的网络结构(超参数)组合,所以会不会两三年后,网络结构的创新,会被AutoML所取代?这个不得而知

参考文献
  1. 深度学习资料
  2. lbs工业界eta应用及滴滴wdr技术
  3. Practical Lessons from Predicting Clicks on Ads at Facebook[J]. 2014:1-9..
  4. Mcmahan H B , Holt G , Sculley D , et al. Ad click prediction:a view from the trenches[C]// Acm Sigkdd International Conference on Knowledge Discovery & Data Mining. ACM, 2013
  5. Cheng H T , Koc L , Harmsen J , et al. Wide & Deep Learning for Recommender Systems[J]. 2016.
  6. 3 Idiots’s Approach for Display Ads Challenge.
  7. 4 Idiots’s Approach for Display Advertising Click-through Rate Prediction.
  8. Guo H , Tang R , Ye Y , et al. DeepFM: A Factorization-Machine based Neural Network for CTR Prediction[J]. 2017.
  9. Zhou G , Song C , Zhu X , et al. Deep Interest Network for Click-Through Rate Prediction[J]. 2017.
  10. 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.
  11. Wang R, Fu B, Fu G, et al. Deep & cross network for ad click predictions[C]//Proceedings of the ADKDD’17. ACM, 2017: 12.
  12. Xiao J, Ye H, He X, et al. Attentional factorization machines: Learning the weight of feature interactions via attention networks[J]. arXiv preprint arXiv:1708.04617, 2017. He X, Chua T S. Neural factorization machines for sparse predictive analytics[C]//Proceedings of the 40th International ACM SIGIR conference on Research and Development in Information Retrieval. ACM, 2017: 355-364.

协同过滤中item-based与user-based选择依据

协同过滤是大家熟知的推荐算法。 总的来说协同过滤又可以分为以下两大类:
  1. Neighborhood-based:计算相似item 或user后进行推荐
  2. Model-based: 直接训练模型预测Rating
在Neighborhoold-based算法中,又细分为user-based CF(Collaborative Filtering)和item-based CF。合适选择使用userd-based CF,什么时候item-based CF更适用就会是一个需要权衡的问题。一般而言,可以以下几个标准进行选择:
  1. Accuracy:一般而言,少数置信的邻居的推荐要比很多的没有太多区分性的邻居更加准确,所以一般我们会选择数量较少的因素(item or user)作为based的算法。 例如, amazon中的商品的种类很多,但远没有注册的用户多,所以该场景使用item-based CF比较合适; 反过来,在百度关键词推荐系统中,商业客户(user)量级是100W左右,而待推荐的关键词(item)是10亿量级,此时使用user-based会是更明智的选择。
  2. Efficiency
  3. Stability:一般情况下倾向于使用变动频率和变动量较少的因素作为based的因素, 例如item变动较少, 则选择item-based, 否则选择user-based
  4. Justifablity(说服力):推荐系统中,推荐理由越白盒,用户越容易理解就越有说服力。所以从这方面考虑,item-based CF会更有说服力,例如显示‘因为你浏览了三星 Galaxy,所以给你推荐了HTC One’的理由会比‘和你相似的用户也喜欢XXX’更有说服力,因为推荐系统是不披露哪些用户和我详细,怎么证明和我相似的,而且这种说法显得比较含糊。
  5. Serendipity:多样性就是user-based的一大优势,和自己相似的用户,总能发现一些自己还没发现的新东西。 如果追求多样性, userd-based会是不错的选择。
当然上述原则都不是绝对的,而且在真实工业界推荐系统中, 两种方法一般都是混合着使用。例如百度关键词推荐系统中,就会分别使用item-based和user-based方法找到待推荐关键词候选后,再统一使用model进行后续ranking。
参考文献:
  1. RSs Handbook
  2. Evaluating Collaborative Filtering Recommender Systems, Jonathan L.Herlocker
也可关注我的微博:  weibo.com/dustinsea
也可直接访问: http://semocean.com