Airbnb深度学习搜索引擎实践-Embedding使用

real-time personalization using embeddings for search ranking at airbnb

内容简介

搜索排序和推荐系统在类似于网页搜索内容发布等场景都是比较重要的技术,但是很难有统一的技术能够适用于所有的场景。
在爱彼迎的场景中,需要同时满足商家和用户的偏好需求。而且在特定的时间,一个民宿只能接待一位客人。
文中使用embedding技术对list和用户进行建模,以便用在搜索和推荐中。这两个频道带来的转化占了99%以上。并且能做到实时的个性化。从离线和在线的ab test效果都验证比较好。

intoduction

随着数据的增长继续学习,在搜索和推荐中的个性化应用都比较成熟,有很多的发展。有些集中在engagement的优化,有些集中在购买的优化,有些则集中在双边的优化。例如像租房行业中的airbnb打车行业中的uber,都会涉及到供需双方的满足。
airbnb需要满足双边的供应和需求双方包括说客人的预计定酒店地点,日期以及说酒店的一些要求,比如容忍的客户数,是否有宠物,要把不匹配的酒店放在比较低的排序位置。
最后使用的方法是将问题建模成pairwise排的问题,并使用lambda rank方式实现。
在爱彼迎的场景中,一般用户有需求的时候都会在同session中搜索多次,所以我们可以个性化的向用户推荐同一session中用户可能喜欢的item,以及将排序比较高的推荐出来,但没有被点击的item作为负例。
方法:
在具体实现的时候,使用用户有过交互的item作为trigger,使用搜索session的数据训练word representation,并计算与trigger item的相似度,以便在搜索和推荐中作为排序similarity的度量。
兴趣建模方式

  1. 使用用户近期点击行为作为用户短期的兴趣偏好
  2. 使用用户预定的行为作为用户长期的偏好
  3. 因为用户预定的行为会比较稀疏,所以将用户映射到群体使用规则的方式
  4. User和item都映射到同样一个向量空间,以便计算其相似度

文章的贡献

  1. 实时个性化:传统的方法是离线计算好user 2 item或者说item 2 item的内容,之后在线去拉倒排,本文使用的方法是将用户即时的交互item embedding化,然后再去查相似的item。做到实时个性化
  2. 适应具有聚集性的数据的训练模式:在短租市场中,用户一般是在特定的时间,只针对特定的区域有需求,故在训练的时数据的负样本选择需要具有区域性聚集
  3. 将转化作为全局的内容
  4. 用户类别embedding:很多文章对每一个用户进行一个embedding,但是在短租市场,用户行为非常稀疏,故将用户的类别进行embedding
  5. 将用户拒绝作为负例

方法

文中将embedding分成两种,一种是用户实时短期item的embedding,另一种是user type和item的embedding,表征长期实时兴趣。

相当于优化每个session中每一个item对应的上下文的概率最大化。

此处的概率是用softmax来表示。
note:以上公式中,m为前后上下文的窗口长度,V为字典大小。使用以上方式,得到的li的representation,在session中越相似,则距离约近。
此处V表示id数量较大,所以使用随机负采样方式来降低数量提升计算的速度。
负采样
负采样的方法为,使用click和对应session中的上下文作为positive pairs(c,l),以及click和随机采样的上下文作为negative pairs(c,l)进行模型训练。以下为对应的优化目标,其中Dp为positive pairs集合,Dn为negative pairs集合。

将session分为两种

  1. 第1种是以完成订单预定的session, booked session
  2. 第2种是有点击,但没有预定的session,exploratory session
    为了让预定作为一个全局的上下文,在每一个booked session中的样本,都强制将预定的item作为结束的item。

对于exploratory session,则优化目标仍然为公式(3)
Adapting training for congregated search:
以上公式的random sampling会导致random sampling出来的负样本都是和本次搜索地域不一致的结果,最终导致模型学习出来的是区域之间的相关性,为了解决该问题,增加对同区域结果的sampling

上式中Dmn为在l的同区域中sampling出来的结果

冷启动

新加入的店面没有embedding,此时我们会用距离内的相似民宿的中心点来进行表示,比如说找到半径10英里内,相同price以及相同房型等其他属性相同的三个embedding,然后做一个平均,来表示新的民宿的embedding作为冷启动。用该方法能够覆盖98%的new item。

embedding效果的检验

使用围围度为32的embedding进行表征,发现地理位置的聚类关系的确编码进去了,同时房型价格的信息也编码进去了。

user-type & listing-type embeddings

目的是捕捉用户的长期兴趣。但是存在以下几方面的挑战:

  1. 数据较为稀疏。
  2. 很多预定的session长度为1,没法学习。一般出现5~10次才能学习出来。
  3. 用户预定的间隔很长,可能偏好已经改变了。

具体的实现方式为将用户按照meta信息进行聚类分为人群,将listing/item按照meta信息进行聚类,按照聚类后的群体构建预定session进行训练。相当于学习的对象由原来的list_id,变为list_type
用户的长期兴趣可能会改变,故在具体学习操作的时候,将user和listing映射到同一vector space中进行学习。

构造(u_type1,l_type1)的用户群体,listing群体的点击session,之后进行训练,即可将user和listing映射到相同vector space中

模型训练

以30分钟作为一个session进行模型训练
去除无效的点击,例如点击后在页面时间较短的点击
将session处理为同时包含booking&EXPLORATION的session形式

评估方式

给定用户最近的点击,以及待排序的candidate, 看最终被预定的item是否能够被排上来

线上使用的方式,为使用GBDT模型进行特征组合, 使用user, listing embedding构建各种特征进行模型训练

reference

原论文参见:

https://pan.baidu.com/s/1R8xeb0iRq089myl3oXJlZA 提取码:1j9n
更多内容参见: www.semocean.com
P.S. 急招推荐,搜索,语音算法人才,阿里P6~P8,欢迎推荐和自荐,简历请发至 haibo.lihaibo@alibaba-inc.com

亚马逊semantic product search

亚马逊semantic product search

网上一直有一种说法,就是在Google的工程师非常鄙视亚马逊的工程师,觉得他们技术不行,Google的技术比较牛叉,但是很多业务场景Google就是做不过亚马逊,最典型的就是云计算市场,Google的市场份额还不如阿里,更别说亚马逊的老本行电商。而亚马逊也一直奉行简单有效为客户服务的原则推进业务。 例如这篇论文中描述的亚马逊电商product search,技术比较简单,没有很高端复杂的模型,但大家在工业界的实践中是可以作为参考的,是一种简单有效的语义搜索方法。该论文发表于2019年KDD大会,下边的内容更多是一个论文的笔记,作为一个备忘,大家最好参考原论文一起阅读。

基于字面匹配的缺点

  1. 第一上下位同意反义处理不好,例如语义的泛化(hypermyms),同义词(synonyms),反义词(antonyms)
  2. 第二形态学变换处理不好,比如说woman and women
  3. 第三拼写错误处理不好。

本文提出的语义方法解决问题的思路:

  1. 第一是loss function处理正负样本
  2. 第二是针对average pooling和ngram捕捉语法的pattern
  3. 第三是使用哈希处理字典中不存在的单词的问题OOV,应对0次学习问题
  4. 第四是进行了并行优化。

本文面临的场景是用户的行为数据量非常多,但是有噪音,同时用户在搜索的时候,是针对某一个比较窄的领域进行搜索,在这个过程当中还需要兼顾发现性。

模型

本文使用的模型的主要特点

  1. 第一是使用embedding方式将query,product映射到相同的空间
  2. 第二是生成embedding之后,使用average pooling的方式将embedding压缩到相同的维度。之所以能够用average pooling主要的考虑有两点(没有使用RNN的原因)
    第一是query和product都比较短,没有太强的持续依赖的关系
    第二是query一般都包含在product之中。同时因为quarry比较短,所以将query和product映射到同一空间中,无需额外参数

图:模型示意图

Loss function

使用pointwise 3阶段hingle loss作为lose function

相当于综合考虑了样本的三种情况:

  1. 第一正样本为用户购买的product
  2. 第二就是用户看到了(impressed),但是没有购买的结果
  3. 第3种是随机采样出来的结果作为副样本

相当于将label分成三种,三种有不同的域值,使用hingle loss方式进行建模

tokenization methods

本文使用不同维度的力度的embedding对query, product进行表达.主要分为以下几种:

  1. word unigram:基于单词的unigram
  2. word n-gram:用来捕捉PHRASE信息,以及对应的附属信息,例如用户如果买的是iPhone手机壳跟iPhone手机其实是不一样的,使用n-gram可以捕捉该类信息
  3. character trigram:用来捕捉拼写错误信息或者像size型号之类似的信息

同时文中使用harsh trick来解决embedding没有表达到生僻词的情况。
最后在应用的时候,作者将所有的tokens组成一个bag of tokens,之所以能够那么做而没有考虑持续的原因,是因为query和product的title一般都相对较短,用这样的方式其实也能表达序列的关系,而不用用到rnn这样的模型。实验证明不用rn效果的影响也不大。

note:对于OOV的部分(word, n-gram, char-trigram)则使用hash trick的方式进行处理,将query, product中相同的部分映射到相同的bin中(参见图5)
该方法的好处,一方面能够保证高频的元素都能够找到,另一方面,query和product中OOV的元素都能够映射到相同的部分。

data

使用11months的search logs作为训练数据, 使用1month作为evaluation。
文中使用用户数据来进行模型的训练使用和query和products的counts作为权重。
在构造样本的时候,一个query之下有6个impression的product和7个random的products和一个有购买的products。

实验指标

matching:抽取20k个query,看从100万的语料库里边能召回多少购买的products。
ranking:主要看NDCG,mrr。

Result

设置:文中固定dimension为256,batch size=8192,adam作为优化算法。。。
结论:

  1. L2比L1正则更好,原因可能是L2对于cosine计算相似度的情况下,对于outlier更加泛化
  2. 效果 3 part > 2 part loss
  3. average pooling效果优于gru/lstm,猜测可能是因为该场景中序列长度较短,RNN的效果没有发挥出来
  4. tokenization算法中,unigrams+bigrams+char trigrams算法效果最好; 增加OOV在保证参数不变的情况下效果更好

后续:借鉴意义

在后续推荐业务中存在的借鉴意义如下:
poi2poi embedding表示:计算可以使用该方法对搜索业务中 query-点击poi数据进行embedding,获取poi embedding,计算i2i
tag2tag embedding表示:将tag作为token,使用搜索数据进行训练,得到tag和poi在同一空间中的embedding表示
poi属性2poi的embedding表示

reference

原论文参见:
复制这段内容后打开百度网盘手机App,操作更方便哦 链接:https://pan.baidu.com/s/1VITC73pw9fURLJ-K_7Kb3g 提取码:4h43
更多内容参见: www.semocean.com
P.S. 急招推荐,搜索,语音算法人才,阿里P6~P8,欢迎推荐和自荐,简历请发至 haibo.lihaibo@alibaba-inc.com

 

增加User Memory Embedding的深度点击率预估模型

这次参加了KDD 2019的大规模稀疏特征模型workshop,其中有比较多的论文是关于如何改进推荐,变现场景CTR预估模型的效果提升的。感觉今年很多的论文改进方向都集中在了如何更好地引入用户历史行为特征及兴趣。 无论是引入RNN, transformer,或者其他的weighted pooling,都基本是是类似的思路。

以下就简单介绍下这次KDD收录的文章《Click-Through Rate Prediction with the User Memory Network》的思路,细节就不展开了,具体可以参见附件。

在按照CPC收费的广告业务中,Revenue=bid*ctr,故ctr预估的准确性一直是广告业务中的核心技术问题。现在深度学习已经成为ctr预估的标配,但传统DNN的深度ctr模型未考虑用户的点击历史行为,效果有待提升。而另一方面,RNN类的序列模型能够刻画用户的历史行为序列提升预估准确性,单RNN类的模型存在两个缺点:1是模型会比较复杂,2是数据的准备也会既复杂又冗余。

本文为了解决该问题,引入了用户唯独的like and dislike history的vector描述,两个vector作为用户feature和广告的其他feature进行concat作为input进行模型训练和预测。该方式既引入了用户的history信息,又避免了使用RNN类的模型带来的复杂性。需要注意的是,like/dislike的向量为user-wise的,故每个user都会有两个用来表示这两个历史信息的向量。

p.s. 其实这样的思路在很多场景中军可以使用,例如在地图领域,理论上引入了RNN的ETA效果也会更好, 因为用于表示道路的link客观上就是呈现出序列的特性,但ETA作为基础设施访问量非常大,实效性要求又会比较高,故线上几乎不可能使用RNN作为实现方案,所以可以使用固定长度的vector对序列的link进行表示,以便使用定长的向量,一定程度上就可以表示出序列的特性,相当于是序列信息的一种折中方案。

文中提到的CTR模型如下:

图:memory network for ctr prediction

该方法在传统的DNN基础上,在将特征进行embedding的时候,引入额外的两个用户级别用于表示like&dislike的vector作为history memory信息,一定程度上引入了历史序列信息。

References:

  1. Ouyang W, Zhang X, Ren S, et al. Click-Through Rate Prediction with the User Memory Network[J]. arXiv: Information Retrieval, 2019
  2. 论文下载:复制这段内容后打开百度网盘手机App,操作更方便哦 链接:https://pan.baidu.com/s/1gFsuIIFzuKQROFLotfZldg 提取码:181v

 

 

图像质量打分算法-NIMA

业务背景
随着手机性能提升,网络速度改善流量资费下降,原有网络上消费的内容很大程度上都被图片,视频所取代。此时很多应用中就会碰到一个技术问题,如何评价图像,甚至视频的质量。而这里边一个比较重要的场景,就是如何选择内容的头图。例如大众点评UGC评价推荐的首图,爱奇艺、优酷视频的头图。好的头图能够提升内容的表达能力,提升用户体验,从业务指标上也能从内容的点击率体现出来,所以,需要一种可靠的图像质量打分算法,该算法不仅需要能够识别技术上质量差的图片(例如清晰度差,饱和度,噪音点多等),还要根据具体的业务场景,判断该图片适用于该业务场景的程度,例如美团点评的头图如果是菜品时,显示已经就餐完毕的残羹冷炙就不合适,而爱奇艺,优酷等视频网站,则不适合出色情的头图。

算法
业界有很多算法解决此类问题,例如BDN(Brain-Inspired Deep Networks for Image Aesthetics Assessment)中使用多路人工构建特征进行打分能够在该类问题中取得较好成绩。
比较有名的end2end方法,是2017年Google Research发表的NIMA算法(Neural Image Assessment算法)。正好这几天有时间业看了下论文,感觉Google的论文都是比较接地气的:不复杂,能解决实际问题,甚至拿来修改下就可以在实际场景中使用。
该论文解决Image Assessment的算法的思想主要如下:

  1. 使用预训练的ImageNet网络作为Baseline,该处的Baseline可以是MobileNet,VGG16,Inception等
  2. 在Baseline的基础上,将最后一层替换掉,使用随机初始化的FC进行任务Fine Tuning
  3. 使用的数据集论文中提到3个,AVA,TID2013,LIVE。数据集中对图片的标注,均是同一个Image多个人进行打分,用打分分布进行描述,包含mean,deviation。使用上述数据集进行模型Fine Tuning
  4. 论文中考虑到各个打分等级虽然是离散的,但却是有顺序的(Ordered),所以模型最终的loss并不是使用cross entropy进行衡量,而是使用EMD,这样有助于将各个离散的分档的大小关系考虑到任务重,缓解了cross entropy将各个类别看成相互独立的缺点

图:NIMA算法架构图,使用ImageNet任务网络(MobileNet,VGG16,Inception)移出最后一层,然后新增随机初始化FC。训练loss使用EMD(Earth Mover’s Distance),其度量的是两个分布的距离。 此处的CDF_p(k) 为从1,到k个类别上的概率累加

图:EMD loss

总结
在很多任务重,NIMA都能够表现良好,甚至使用AVA公开数据进行训练后的模型就能够取得较好成绩,但是很多时候,我们还是需要根据具体业务进行定制,特别是加入符合业务场景需求的训练样本,例如电商UGC中不能出现色情内容,单是否出现年轻,二次元的美女可以加分? 另外文中使用EMD来缓解cross entropy不能建模ordered category信息缺点的思路,也可以在很多场景中借鉴,例如地图中,路况状态一般分为:畅通,缓行,拥堵,极度拥堵,如果直接使用cross entropy就将各种状态之间的顺序关系丢弃了,此时使用EMD作为loss,而仍然将问题看成是分类问题会更加合适。

Reference
Zhangyang Wang, Florin Dolcos, Diane Beck, Shiyu Chang, Thomas S. Huang:
Brain-Inspired Deep Networks for Image Aesthetics Assessment. CoRR abs/1601.04155
NIMA: Neural Image Assessment. 原论文下载地址:https://arxiv.org/abs/1709.05424

github Keras实现:https://github.com/titu1994/neural-image-assessment

 

 

 

 

 

AutoML技术&应用

介绍

参加了NeuraIPS回来后,公司让参会的几个同学都找个topic给公司其他人做一个分享,因为自己对AutoML比较感兴趣,所以就选在在公司分享这个话题。

其实我个人对AutoML这个方向没啥研究,也不是专家,只是对这个方向比较感兴趣。原因有二,一是觉得这个方向比较有意义,如果真的做成了,生产力提升不说,很多初中级的调参侠就要失业了,影响还是比较大的;二是一直在追推荐相关的技术,发现很多Paper都是在讲如何创新性地提出一个网络结构应对特殊场景,思路很像Neural Architecture Search做的工作,感觉这些事就应该AutoML来做。

下面就进入正文介绍分享的内容。

What&Why

大家在用机器学习解决具体问题的时候,流程一般比较长。一般包括以下几个步骤:

  • 定义任务
  • 收集数据
  • 特征工程
  • 模型选择
  • 选择优化算法&参数
  • 评估效果(效果不好则迭代)
  • 发布&上线

这里边会存在以下几个挑战:

  1. 用machine learning解决问题的任务的pipeline比较长,包含定义问题,收集数据,数据预处理,模型选择,优化算法,以及这个过程的反复迭代,效果OK后再上线部署。里边混合着工程,算法,策略,很多时候一个人还搞不定
  2. 这方面的专家很贵,而且。之前爆出过机器学习的博士应届生薪水到60~80W,不是一般公司能够承受的
  3. 一般的专家就精通某个业务领域。而CV,NLP,语音等不同领域又有很大差异

所以这个时候的理想手段,就是使用AutoML,快速建立一套不错的机器学习流程来解决任务,不一定是最好的(也可能是最好的),但性价比比较高。这时留给人的主要工作,主要就是定义任务,收集数据以及线上部署及线上效果评估分析以及一些更有创造力,更有深度的工作

图:AutoML整体流程示意图

如果我们形式化地定义AutoML,则可以有以下定义:

图:AutoML形式化定义

简单来说就是:最优化整个学习工具(过程)的效果,优化的参数变量就是一组配置,限定条件有两个,1是没有人工参与,2是计算资源可控。该处的配置是个广义概念,包括使用哪些特征工程方法,使用什么模型,模型的超参数以及优化算法的种类和设置等

图:机器学习过程,人工调参并迭代

图:AutoML过程,机器自动完成特征工程,模型选择及调参

总结下来说,可以认为AutoML的特点是:效果好,性能优,无人工参与

How

那AutoML中会涉及到哪些技术呢?从问题的setup来划分,我们可以根据将机器学习过程进行拆解来解决该问题。例如将整个机器学习问题拆解为:选择哪些特征工程方法,什么模型,什么优化算法,以及对应的参数。这是偏传统Shallow模型的流程;近些年DNN逐渐成为解决机器学习问题的主流手段后,AutoML也出现了另外一类端到端的方法,就是基于DNN的方法,默认问题都是用DNN来解决,而这其中需要机器做的就是找到一种适合该机器学习任务的网络,这类方法也叫NAS(Neural Architecture Searching)

从另外一个技术维度,又可以将AutoML方法划分为Basic方法和Experienced方法。这种划分方式的依据是AutoML是着眼于拿到手要解决的任务自动快速找到一个最优配置,还是根据历史上其他机器学习任务作为经验的学习来源,找到一种最优配置。

当然,AutoML在具体实施的过程中也面临很多挑战,主要是以下几点:

  1. 目标函数与参数配置无法直接关联,难于优化。从AutoML的形式化定义我们可以认为AutoML是一个优化问题:AutoML拿到一个任务后,最后产出是一组最优的配置。但是我们很难像传统机器学习一样,写出目标函数后求一阶导数或者二阶导数进行求解,我们可以认为AutoML是零阶导数问题,所以求解需要用另外一些优化方法
  2. 超参数空间较大。选择什么样的特征工程方法,算法,正则,学习率等都是超参数,超参数空间非常大,难于优化
  3. 函数的评估代价较为昂贵。每选定一组超参数后都去train一个模型然后验证效果,时间和计算成本都非常高

要求解AutoML问题的配置,一般会将整个AutoML在框架上分为两个组件。Optimizer和Evaluator,有些系统中也叫Tuner和Assessor,名字不一样,定义大同小异

图:AutoML的一般框架

Optimizer主要负责寻找合适的配置,Evaluator负责评估Optimizer找到的配置,并将评估反馈回传到Optimizer以便Optimizer后续的决策

Optimizer

Optimizer可以认为是AutoML中研究最多最重要的组件,它直接决定了AutoML是否能够(快速)发现最优的配置,拿到最优的效果,经常使用的Optimizer算法有以下几种:

Simple Search Approachs:该方式就是暴力搜索,例如Grid Search,这个是我们经常使用的搜索算法,其做法是将各个维度的参数使用笛卡尔积的方式进行组合,优点是比较简单,缺点是组合方式呈指数爆炸,并且会将搜索试验的机会浪费在不重要的参数上;稍微改进的方式是Random Search,其优势是在各个维度上的试验次数都变多了,这样更容易在important的dimension上找到最优点,因为假设各个维度的参数相对独立。但总体Simple Search方法的缺点都是每次试验都是相对独立的,这就导致后续的搜索不能用到前边搜索的经验。

图:Simple Search Approach

Heuristic Method:该方式使用类似于自然界中种群行为和进化的思路。例如PSO(Particle Swarm Optimizer)会对新的参数进行探索,探索的方向是表现比较好的配置周边的配置(也可以认为是正向反馈较多的方向),就类似于飞行中鸟群会向虫子比较多的方向移动;另一种方法是Evoluationary Method,该类算法的思路是每次选出两个效果最好的配置(ancestor)进行杂交变异(crossover&mutation),类似于人的基因进化过程。Heuristic Method方法的优点是有效,思路容易理解,缺点是没有强的理论依据。

图:Heuristic Method

Model-based Method:该类方法是使用Samples(配置)产生模型,之后使用该模型产生一个比较好的配置,然后让Evaluator验证该配置,之后再使用该sample(配置)来更新该模型。经常使用的model-based方法为Baysian Method和Classification Method.其中Classification Method对samples进行二分类,每次从positive中找出一个sample去进行验证,验证结果再反馈更新模型

图:Model based Method

Reinforcement Learning Method:使用强化学习来找配置,当然有很多人也会有不同的声音,认为RL是比Optimizer复杂很多的问题,使用极度复杂的技术来解决相对简单的问题本身就是个问题,不合理。

图:Reinforcement Learning based Method

Evaluator

Evaluator主要关注三方面的指标:评估准确性,评估效率以及优化反馈。其中评估准确性和效率很多时候需要进行权衡

Evaluator的具体方法相对会简单一些,主要有以下几类:

  1. Direct Evaluation:这是最粗暴的方式,相当于选定配置后直接train model,然后进行验证,是最慢的方式,当然也是验证结果最置信的方式
  2. Sub-Sampling:选定配置后,仅使用一部分采样后的样本来验证参数,优点是速度比较快,缺点是验证结果不一定置信,因为sub-sample set不一定能够完全代表总体数据集合
  3. Early Stop:验证过程中进行提前停止,减少迭代次数或者迭代时间,其中的假设是一个配置如果比较好,那么训练到一半的时候效果应该也比较好。该假设可能会产生噪音。一种Early Stopd的策略是并行跑多个配置,迭代特定次数后,保留效果最好的一半配置继续跑,这样不停减半淘汰
  4. Parameter Reusing:每次模型训练使用上次的权重进行初始化。该方式的优点是快,缺点是可能引入bias,因为不同的start point的结果可能不一致

Meta Learning

Meta Learning相当于使用完全不一样的另外一个思路来产生配置。它从过往的多个机器学习任务中进行经验学习,相当于对于Meta Learning来说,学习的样本是过往的多个机器学习任务,将过往的机器学习任务进行特征表示,例如过往机器学习任务的数据量大小,正负样本比例等统计信息,以及使用的机器学习算法,配置等作为特征去train一个Meta Learner。之后对于新来的机器学习任务,使用Meta Learner推荐一组配置去进行验证.此处Meta Learner可以是比较简单的模型。该方式的优点是能够减少搜索空间,提升效果,不过如何提取特征,如何进行表示会比较有挑战(就像其他传统机器学习任务一样),而且以机器学习任务作为训练样本,这个事也不是每个公司都能够做到的,这也可能是现在AutoML公司的先发优势,假设这些公司占了先机接了很多AutoML需求,则就能获取大量供Meta Learner进行学习的训练样本,而其它公司很难有这样的条件和实力获取这些训练样本

应用

早年在百度负责商业搜索推荐系统的时候,当时就想百度可以做一套通用推荐系统,该系统可以供中小网站主进行站内推荐:中小网站主提供数据,该系统自动为中小网站主定制推荐服务。该系统对中小网站主的价值是中小网站主获得了推荐系统的能力,对百度的价值是百度获得了这些网站的用户行为数据。但当时在百度组织结构划分的情况下该工作不太容易推进,同时项目系统的目标也没那么明确。但该系统可以认为从技术的角度就是需要AutoML的能力。

技术发展到现在,后续AutoML的发展还是很有希望能够有所突破的,原因有以下几点:

  1. 深度学习已经成为解决机器学习任务的标配
  2. 算力的持续增长
  3. 作为解决各种特定应用场景的tricky网络持续出现(算是AutoML的需求场景和价值)
  4. NAS(Neural Architecture Search)技术成为热点并逐渐有所突破

那后续会不会出现这样的场景:公司定义好一个机器学习任务后,就使用AutoML技术来解决,现在公司中的各种调参侠,除了对业务比较精通的那些同学外,其他都失业?这个是大家需要考虑的问题

图:使用RNN进行NAS网络生成

目前很多主流的公司都有自己AutoML的解决方案,例如Google,Microsoft,国内的第四范式。其中部分项目是开源的,大家可以上github了解

图:微软Neural Network Intelligence

图:微软NNI提供提供的主要算法

Refference

  1. Quanming Y, Mengshuo W, Hugo J E, et al. Taking Human out of Learning Applications: A Survey on Automated Machine Learning[J]. 2018.
  2. Pham, Hieu, et al. “Efficient Neural Architecture Search via Parameter Sharing.” arXiv preprint arXiv:1802.03268 (2018).

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

[LBS]工业界ETA应用及滴滴WDR技术

介绍

最近几年共享经济比较火,也出现了很多成功的共享经济企业,而共享经济中比较成功的模式大部分都围绕着共享出行展开业务,例如Uber,Lyft, 中国的滴滴,以及近两年遍地开花的共享单车公司(虽然现在部分共享单车的业务已经在停滞或萎缩)

与此同时,很多关键技术也随着共享经济的发展而被重视起来。像MM(Map Matching)[10],RP(Route Plan),Navi(Navigation)以及ETA(Estimation Time of Arrival),这些都是LBS中比较基础同时比较重要的关键技术,无论是共享单车,出租,快车,顺风车等在进行调度,收费定价的时候,都会涉及这些关键技术。

本文就向大家专门介绍其中的一个关键技术:ETA,内容包括: ETA是什么? 为什么重要? 常用ETA技术有哪些,有哪些优缺点,以及现在up-to-date的ETA技术实现细节及效果。特别会重点介绍目前滴滴已经公开发表的WDR模型在ETA上取得的成果

P.S. 本文不会透露滴滴出行内部仍在进行的项目及对应数据,涉及到的技术细节及数据均已通过论文,或者PR文对外公开发表

图:滴滴ETA(接驾ETA以及送驾ETA)

ETA是什么

从业务的角度讲,ETA就是预估一个行程中,从出发时间到到达时间的时间差,例如滴滴快车中预估到达时间,或者高德导航中规划路线行驶所花的时间

图:高德ETA(2:整体路径规划时间预估)

从技术上,我们可以将ETA的一次调用,看成是一次query,每个query的内容为:<o_i,d_i,s_i>,表示第i个请求o,d,s分别表示起点位置(original),终点位置(destination),起点时刻,ETA需要给出的就是t_i  = e_i – s_i,其中e_i为行驶到终点的时刻

ETA问题看似很直接,但现实中需要准确预估ETA却非常有挑战。挑战主要来自于以下几方面:

  1. 时空维度上数据较为稀疏:因为需要预估的物理世界的数据,在时空维度上非常稀疏,虽然滴滴对外宣称每天有近3KW单的订单,但这些订单所产生的轨迹,也不足于充分覆盖时间+空间的路网数据。例如光北京的路网link数就有超过1Million,而从时间的维度,每2分钟发布一次路网交通状况,全天时间维度上有720的时间切片,故时空维度仅北京市共需发布约2亿个发布值,轨迹数据覆盖会非常稀疏。
  2. 存在较多突发局部事件:且很多时候还存在较多不确定性,例如突发性的车祸,或者交通灯损坏,修路,交通管制,等都会导致路网历史信息失效。

数量较少但影响全局的事件:而碰到节假日或者恶劣天气,整个物理世界的交通也会从系统层面恶化导致预测算法整体失效

为什么重要

但ETA又是一个很基础的关键技术,其应用场景非常广泛, 例如路径规划中用来寻找时间最短的行驶路径,分单,定价,拼单等场景都依赖于ETA。其准确性会直接影响到整个共享出行平台的效率,举几个例子:

  1. 体验:选定一条路线后,起终点的预估时间不准确,会直接影响用户对平台的信任,特别是很多时间敏感场景,例如赶飞机
  2. 计价:很多共享出行平台都会在计费的时候引入行驶时间,ETA不准会导致计价预估不准,如果是事前一口价等策略,则可能导致平台亏钱
  3. 调度:例如拼车场景,ETA不准则会导致拼成率大打折扣,影响用户体验,口碑及平台,司机收益

因为上述ETA的基础性&重要性,目前滴滴每天的ETA调用次数超过40 billions次(数据出处:https://outreach.didichuxing.com/tutorial/kdd2018/)

WDR模型

传统方法主要分为两类:

  1. route-based method: 该类方法将route 的ETA问题分解为 subroute+crossing的子eta问题。其中subroute为待预估的<o, d> route的子route, 一般地图行业叫link,为表征地图路网的最小单位,长度为数米到数百米不等,crossing为交叉路口,交叉路口因受到交通灯等的影响,故单独抽离出来。该类方法一般可以作为ETA的baseline,来评估复杂ETA算法的效果。该方法的优点就是计算比较直观,简单,而且具有很强的可解释性,出了问题后容易分析定位。缺点也很明显:时间空间上数据覆盖较低,误差容易积累,因为没有用上道路,时序,个性化等特征,故效果有提升空间。具体参见图:route-base method方法示意
  2. 另一类算法我们称为data-driven method,例如在预估<o, d>的ETA时,可以使使用neighborhood-based的方法找到相似的轨迹时间进行加权来计算ETA[5],类似于推荐问题(具体参见图:neighborhood-based方法),该类问题的缺点仍然是时空上的覆盖较为稀疏,比较适合车流量较大,速度相对均衡的高速或者快速路。例如,在公开的‘Shanghai Taxi Data’上, 虽然后超过3亿个点的记录,但仍然有50%的道路没有被任何轨迹覆盖,且该数据还没考虑时间维度,并且在时间维度上,高峰期和平峰期的数据分布也不一样

图:route-base method方法示意图

图:neighborhood-based方法

在解决ETA问题的同时,也会衍生出来不同分支的子问题,例如比较重要的一类问题是:我们不仅需要预估具体route的eta,同时需要预估对应eta的概率。应为有些场景我们并不需要最短的eta,但需要时间预估最准确的eta,例如赶飞机火车的场景, 一条预估50分钟的路线并不比另一条1小时的route好, 如果后者的预估置信度比前者高很多的话。该类问题可以参考[7]

而比较up-to-date的方法是使用模型来解ETA问题

问题定义

使用传统机器学习的概念, 可以将ETA问题定义为regression问题,即每条sample为给定<o,d,s>以及该sample对应的特征, 将问题建模成回归问题,使用模型来回归具体的ETA值

特征

传统的route-based方法及data-driven方法仅使用计算的路网的traffic特征来计算ETA,该处的traffic仅指具体子route(或称为link)的通行速度(或者对应的通行时间,因确定route后,route长度固定,故通行速度和时间可以相互转换)。

Traffic特征是计算ETA极其重要的特征,但在计算ETA的过程中,我们能够获取到更多更丰富的特征来提升ETA预估的准确性。route-based方法和data-driven方法的问题是很难直接使用这些特征,但复杂模型却能够使用这些特征提升模型的效果。这些特征包括:

  1. 空间特征spatial information:包括<o, d>路线之间经过的link序列,交叉路口序列(intersections),经过的红绿灯信息,走过的(拥堵)POI等
  2. 时间信息(temporal information):例如当前时间的月份,是一年中的第几天,周,小时等;以及根据历史信息计算出来是否为早晚高峰or非早晚高峰,是否节假日等;这些特征可能需要经过预处理才能得到, 甚至需要将时间信息映射到频域,找出频域特征后引入模型(参见后续博文:《LBS时空特征的提取技术》)
  3. 路况信息(traffic information):每两分钟发布一次全网(路网中所有link)的通行速度,该通行速度作为该2分钟时间片内全路网通行能力的重要描述。该路况信息在ETA的计算过程中比较基础也至关重要,发布路况的准确性会直接影响最终ETA的预估准确性,而且根据该路况信息,即可使用route-based方法计算出baseline的ETA。
    另外路况信息发布是否准确也是一大挑战,因为在时空维度下,经过每个 link的轨迹数也比较少
  4. 个性化信息(personalized information) 包括driverid, 乘客id以及汽车相关的属性
  5. 其他特征:例如天气特征等,该类特征对大盘的影响相对较少, 但对用户体验影响非常大,例如下雨天,整体路网的拥堵程度会大幅上升,但下雨天的占比相对较少, 导致模型不一定能学出该规律,但异常天气下如果ETA不准,又会极度影响用户体验,故最后可能需要使用一些特殊逻辑进行定制处理

优化目标

模型候选的优化目标可以是MAPE,MAE,MSE等,考虑到预估偏差的大小对用户感知体验的影响,与行程本身的时长有关, 故前期在提升模型总体效果的时候,离线模型使用MAPE作为优化目标。在模型基础能力提升到一定程度后, 主要考虑用户体验影响较大的极端CASE时,会同时兼顾异常CASE率,对模型效果进行评估。

其中MAPE定义为:

模型

如,‘问题定义’部分所述,问题一旦定义成regression后, 即可使用传统回归模型进行解决。

近些年深度学习比较火,所以在有足够数据,足够计算资源,对效果又有较高要求的场景, 一般都会使用的深度学习来解决。相较之下,传统的浅模型就没有那么高端了, 但这些模型在特定的场景, 仍然会是比较好的选择。 例如我们在使用模型预估当前的路况状态(行驶道路的状态:畅通,缓行,拥堵)的情况下,使用GBDT仍然会是比较好的选择, 一则我们的Ground Truth较少,目前主要还是通过人工标注获取, 另外则是我们的应用场景需要有较强的可解释性,否则收到用户或者业务方的投诉case时,很难进行分析解释。

在ETA场景中, 浅模型和深度模型的特点如下:

浅模型

传统效果较好浅的模型有gbdt, fm, 这两个模型各有优缺点, gbdt上手比较方便,且能够直接处理连续值,能够自己进行特征选择与组合,但gbdt很难处理特征量较大的场景;fm的效果依赖于特征的表达, 表达能力有限, 对于滴滴的ETA,我们能够获取海量的训练数据,且从加强表达能力的角度考
虑, 深度学习会更胜一筹

图:Wide&Deep模型示意

深度模型

常用的深度模型很多,而且各自有适合自己的优缺点和应用场景,而现在的趋势是构建复杂网络,在复杂网络模型中, 结合浅模型和深度模型的优点,最大化提升预估效果,比较经典且在工业界落地的方法是GooglePlay App推荐场景使用的方法,参见《Wide&Deep Learning for Recommender System》,该方法使用线性模型作为Wide部分进行exploitation,而使用Deep部分进行exploration

Wide&Deep两部分的作用如下:

  1. Wide部分为线性模型,将特征映射到较高维度空间;一般具体的特征会先进行交叉(也相当于在线性模型中引入部分非线性特征);Wide部分主要作用是做memorization,可以充分exploit历史信息,具有较强的可解释性,并且效率较高
  2. Deep部分:将高维特征映射到低维的dense特征(进行embedding),之后进行concate。 Deep部分主要是进行exploration;embedding相当于从已经出现过的数据中学习feature的co-corelation,deep部分更倾向于多样性进行explore

但在滴滴ETA场景,我们引入了世界序列模型LSTM,因为传统W&D方案存在缺点:每个sample的feature必须要对齐,但对于给定<o,d>pair对应的route中,组成route的link数量不一样,一般起终点间距小则link数量会少,反之则link数量会比较多,这些link自身的属性可以作为强特征,对最终ETA的效果影响较大,但传统W&D模型在使用的时候,因为不能处理变长的link序列,故模型很难用到link的local,而只能用到这些link的统计信息,故需要引入额外的网络结构来学习这些local信息;此时时间序列模型能够处理变长输入,故是较好的选择。

所以很自然地在W&D模型基础上增加LSTM结构来adopt local的link序列信息,最终形成滴滴ETA使用的WDR模型

图:WDR模型,其中Wide部分既有dense特征也有sparse特征;而Deep部分的Sparse特征需要首先使用embedding方式转为Dense特征,之后进行Concatenation

 

说到这里简单岔开一下,我们在进行特征设计,或者模型网络结构设计的时候,背后都是有容易理解&解释的Philosopy的:W&D的思路是使用Wide部分进行Memorization,以便对历史信息进行exploitation,使用Deep部分寻找特征之前潜在的Co-Correlation,对特征进行exporation,而R(LSTM)部分则是为了处理W&D处理不好的link边长序列

在具体实现过程中,线性部分一般会先做特征交叉;Deep部分会先将稀疏特征使用embedding方式转成dense特征,lstm部分则在输入link序列后,使用最终的hidden status输入值最后一层,作为最上层regression

评测方法

在评测模型的时候,我们首先对数据进行了预处理,移除了异常的trajectories, 例如travel time < 60s 或者speed>120km/h的trajectories;之后我们使用3个月的数据,并分接驾数据(pick-up)和送驾(trip)数据分别进行模型训练,并将接下来两周的数据按时间维度分为两份,分别作为验证集合(validation)和测试集(test)评估模型效果

指标

离线使用MAPE(之前提总体乘坐时间越长,偏差的容忍就越长)在线则同时使用MAPE, APE20, bad case率对模型效果进行评估,其中: APE20表示absolute error 小于 20%的case的占比,而相反地,bad case 率定位为预估偏差大于50%,或者大于180秒的case,该指标用于衡量bad case出现的概率,控制极端误差case对用户体验的影响

效果

此处仅给出送驾段MAPE衡量的模型效果,现实中送驾段MAPE能从baseline的15.01%降低到WDR的11.66%,而WDR效果可以比GBDT好2.5%.

其中WDR的R部分, 在送驾段能带来1.77%的MAPE收益,可见将local的link信息使用时间序列方法引入模型,能够带来较大的效果提升。

当然,在算法需要上线时,还需要考虑线上服务的性能,故我们还尝试了另外一种更高效的基于Attention机制的深度网络,以后再向大家介绍。

参考文献

  1. 《2017年滴滴出行平台就业研究报告》
  2. Gers, Felix A., Jürgen Schmidhuber, and Fred Cummins. “Learning to forget: Continual prediction with LSTM.” (1999): 850-855.
  3. Cheng, Heng-Tze, et al. “Wide & deep learning for recommender systems.” Proceedings of the 1st Workshop on Deep Learning for Recommender Systems. ACM, 2016.
  4. 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.
  5. Wang, Hongjian, et al. “A simple baseline for travel time estimation using large-scale trip data.” Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2016.
  6. Wang, Yilun, Yu Zheng, and Yexiang Xue. “Travel time estimation of a path using sparse trajectories.” Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014.
  7. Asghari, Mohammad, et al. “Probabilistic estimation of link travel times in dynamic road networks.” Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, 2015.
  8. https://outreach.didichuxing.com/tutorial/kdd2018/
  9. google官方wide&deep实现:https://github.com/tensorflow/models/tree/master/official/wide_deep
  10. map-matching:http://www.semocean.com/lbs%E5%9C%B0%E5%9B%BEmap-matching%E6%B5%81%E8%A1%8C%E7%AE%97%E6%B3%95%E5%8F%8A%E5%BA%94%E7%94%A8/

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