和自己赛跑的人
分享一个巨牛的技术文档集合： 阿里双十一9年算法工程介绍《九年双十一－互联网技术超级工程》，其中介绍了阿里双十一过程中应用到的基础架构，算法，应用策略等，非常系统全面。很多算法细节并未展开，但也是从宏观上了解阿里内部技术栈，以及业务背后使用的技术非常系统的材料。材料可以从引入列表下载，也可关注微信公众号‘‘阿里技术’’下载。
另外最近的感受，就是阿里在技术的投入越来越大，沉淀越来越厚。以前经常说：百度的技术，腾讯的产品，阿里的运营。但随着阿里经济体越来越庞大，生态越发全面的同时，内部技术建设也越来越领先同行，而且阿里的技术不仅能在工业界落地，同时在学术界也产生更多贡献：现在很多顶会都能看到很多阿里技术成果的身影；同时对开源也有更多的项目贡献。
P.S. 长期招人：搜索，推荐，机器学习，语音，期待你加入阿里经济体，让天下没有难做的生意： ）
参考文献：
《九年双11：互联网技术超级工程》：
https://102.alibaba.com/downloadFile.do?file=1516614343703/AliDouble11.pdf
最近看了一篇比较有意思的文章，关于滴滴'猜你去哪儿'功能的算法实现，在这里记录下。
产品
图：滴滴'猜你去哪儿'产品形态
从产品的角度，滴滴'猜你去哪儿'是在用户打开滴滴，用户还未输入的情况下，猜测用户的想去的目的地（POI）并以TIPS的形式直接进行提示，该功能从产品上有两个好处：1是能够减少用户的输入，如果猜测准确，用户直接点击目的地POI即可；2是能够提升用户对滴滴的好感，提升用户体验和粘性，毕竟用户都是感性的，这样一个功能点如果足够准，就能让用户印象深刻
技术
首先分析下该产品的业务场景：用户打开滴滴，绝大部分情况下，都是心中已经有要去的地点了，技术需要做的只是将该POI猜对并提示出来。所以该场景所使用的技术，就和传统的视频，音乐，甚至电商推荐有很大区别：该过程不需要协同，而在乎准确，用户不会因为你打开滴滴的时候推荐的POI和他的兴趣比较相关就会去，在打开滴滴前，用户就已经做了决定。
换句话说，用户要去的地方是极度个性化的，几乎没有泛化，所以在技术上有以下两点设计：1，召回的目的地候选POI就是用户的常去地；2，去什么地方仅取决于用户及他所处的上下文，此处上下文包括位置，时间等。而所有的上下文中，从滴滴的论文中可以看到，最重要的就是3个因素：出发时间，出发地点，是否为工作日
图：最有效的场景上下文
算法
滴滴使用了一个比较简单的算法来解决该问题：针对每个用户的数据，对每一个去过的候选目的地，使用高斯分布来构建基于上下文的条件概率分布。之所以使用，之所以使用高斯分布，是从数据上来看，出发上下文和去的目的地之间，分布的确是一个钟形。
图：特定目的地出发时间分布
如上图，如仅考虑时间一个维度，用户出发去特定目的地的分布，符合高斯分布。
故使用的模型形式如下：
图：贝叶斯模型
其中 X为当前用户所处上下文， Y=yi表示目的地为yi。其模型形式为给定上下文后，计算用户去目的地yi的概率，转化为使用贝叶斯方式计算，此时只要计算用户去各个目的地的先验，以及用户去各目的地的上下文概率即可。
先验计算比较直接，直接统计用户去各目的地的频次即可。
图：特定目的地概率统计
P（X|Y=yi）则将其表示为高斯分布。简单出发，此处 X如果仅包涵时间维度的话，作如下表示：
图：建模为条件概率分布
高斯分布仅需要给出 u 和 variance即可。而两个值通过观测样本即可给出。但此处有个细节，就是时间是以24小时的周期函数，不能直接使用数值方式计算均值u，故文中提出了计算时间维度u的方法。
图：求解u
其思路比较直接，其中有两个关键点：1，时间以24小时作为周期，那么两个时间的差，不能大于12小时；2，u和所有时间点的差值的平方和最小，求解u即可。
图：求解u，时间距离定义
同理可求解variance。
以上方法仅使用了时间一个上下文，在实际中较为重要的上下文为时间，出发位置，是否工作日，以相似的方式，将模型构建为多维高斯分布并使用贝叶斯方式即可计算。
结果透出
使用以上方法，即可计算用户在特定场景上下文情况下去特定POI的概率。当用户使用滴滴时，只需要使用该用户当前的场景上下文，使用以上方法均计算一遍概率，再根据阈值挑出TOP N即可作为'猜你去哪儿'的结果
算法不足
该方法的优点是足够简单，结果容易解释。缺点也很明显，主要包含以下几点：
1，场景上下文使用较少，也不太方便引入更多上下文，例如天气等
2，用户行为使用较少，仅使用上下文信息进行单点预测，没有用到用户的行为轨迹信息
解决第一个问题的思路比较直接：更多的特征，描述能力更强的模型。
第二个问题会比较有挑战，受限于滴滴的产品使用场景，滴滴能拿到的数据仅为用户行前的位置信息，以及用户行中的轨迹订单信息，但对用户行前之前的数据一无所知，所以如果华为，或者小米这样从底层操作系统的角度就能够完整拿到用户轨迹的厂商，就能够使用用户长期行为模式，短期轨迹和即时上下文，更加精准地预估用户行为。当然这样也会面临着更大的用户隐私风险，毕竟用户的轨迹信息基本是用户最私密的数据了。
参考文献
Zhang L, Hu T, Min Y, et al. A Taxi Order Dispatch Model based On Combinatorial Optimization[C]// Acm Sigkdd International Conference on Knowledge Discovery & Data Mining. 2017.
参加了NeuraIPS回来后，公司让参会的几个同学都找个topic给公司其他人做一个分享，因为自己对AutoML比较感兴趣，所以就选在在公司分享这个话题。
其实我个人对AutoML这个方向没啥研究，也不是专家，只是对这个方向比较感兴趣。原因有二，一是觉得这个方向比较有意义，如果真的做成了，生产力提升不说，很多初中级的调参侠就要失业了，影响还是比较大的；二是一直在追推荐相关的技术，发现很多Paper都是在讲如何创新性地提出一个网络结构应对特殊场景，思路很像Neural Architecture Search做的工作，感觉这些事就应该AutoML来做。
下面就进入正文介绍分享的内容。
大家在用机器学习解决具体问题的时候，流程一般比较长。一般包括以下几个步骤：
这里边会存在以下几个挑战：
所以这个时候的理想手段，就是使用AutoML，快速建立一套不错的机器学习流程来解决任务，不一定是最好的（也可能是最好的），但性价比比较高。这时留给人的主要工作，主要就是定义任务，收集数据以及线上部署及线上效果评估分析以及一些更有创造力，更有深度的工作
图：AutoML整体流程示意图
如果我们形式化地定义AutoML，则可以有以下定义：
图：AutoML形式化定义
简单来说就是：最优化整个学习工具（过程）的效果，优化的参数变量就是一组配置，限定条件有两个，1是没有人工参与，2是计算资源可控。该处的配置是个广义概念，包括使用哪些特征工程方法，使用什么模型，模型的超参数以及优化算法的种类和设置等
图：机器学习过程，人工调参并迭代
图：AutoML过程，机器自动完成特征工程，模型选择及调参
总结下来说，可以认为AutoML的特点是：效果好，性能优，无人工参与
那AutoML中会涉及到哪些技术呢？从问题的setup来划分，我们可以根据将机器学习过程进行拆解来解决该问题。例如将整个机器学习问题拆解为：选择哪些特征工程方法，什么模型，什么优化算法，以及对应的参数。这是偏传统Shallow模型的流程；近些年DNN逐渐成为解决机器学习问题的主流手段后，AutoML也出现了另外一类端到端的方法，就是基于DNN的方法，默认问题都是用DNN来解决，而这其中需要机器做的就是找到一种适合该机器学习任务的网络，这类方法也叫NAS(Neural Architecture Searching)
从另外一个技术维度，又可以将AutoML方法划分为Basic方法和Experienced方法。这种划分方式的依据是AutoML是着眼于拿到手要解决的任务自动快速找到一个最优配置，还是根据历史上其他机器学习任务作为经验的学习来源，找到一种最优配置。
当然，AutoML在具体实施的过程中也面临很多挑战，主要是以下几点：
要求解AutoML问题的配置，一般会将整个AutoML在框架上分为两个组件。Optimizer和Evaluator，有些系统中也叫Tuner和Assessor，名字不一样，定义大同小异
图：AutoML的一般框架
Optimizer主要负责寻找合适的配置，Evaluator负责评估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的具体方法相对会简单一些，主要有以下几类：
Meta Learning相当于使用完全不一样的另外一个思路来产生配置。它从过往的多个机器学习任务中进行经验学习，相当于对于Meta Learning来说，学习的样本是过往的多个机器学习任务，将过往的机器学习任务进行特征表示，例如过往机器学习任务的数据量大小，正负样本比例等统计信息，以及使用的机器学习算法，配置等作为特征去train一个Meta Learner。之后对于新来的机器学习任务，使用Meta Learner推荐一组配置去进行验证.此处Meta Learner可以是比较简单的模型。该方式的优点是能够减少搜索空间，提升效果，不过如何提取特征，如何进行表示会比较有挑战(就像其他传统机器学习任务一样)，而且以机器学习任务作为训练样本，这个事也不是每个公司都能够做到的，这也可能是现在AutoML公司的先发优势，假设这些公司占了先机接了很多AutoML需求，则就能获取大量供Meta Learner进行学习的训练样本，而其它公司很难有这样的条件和实力获取这些训练样本
早年在百度负责商业搜索推荐系统的时候，当时就想百度可以做一套通用推荐系统，该系统可以供中小网站主进行站内推荐：中小网站主提供数据，该系统自动为中小网站主定制推荐服务。该系统对中小网站主的价值是中小网站主获得了推荐系统的能力，对百度的价值是百度获得了这些网站的用户行为数据。但当时在百度组织结构划分的情况下该工作不太容易推进，同时项目系统的目标也没那么明确。但该系统可以认为从技术的角度就是需要AutoML的能力。
技术发展到现在，后续AutoML的发展还是很有希望能够有所突破的，原因有以下几点：
那后续会不会出现这样的场景：公司定义好一个机器学习任务后，就使用AutoML技术来解决，现在公司中的各种调参侠，除了对业务比较精通的那些同学外，其他都失业?这个是大家需要考虑的问题
图：使用RNN进行NAS网络生成
目前很多主流的公司都有自己AutoML的解决方案，例如Google,Microsoft，国内的第四范式。其中部分项目是开源的，大家可以上github了解
图：微软Neural Network Intelligence
图：微软NNI提供提供的主要算法
很久没买美股了。昨天打开雪球扫了一眼结果惊呆了， 猎豹移动（CMCM）一天居然跌了40%， 其市值几乎和其现金等价物一致。于是搜了下新闻看到底发生了什么。后来了解到原来是Kochava(第三方监控公司)曝光猎豹旗下数款工具APP存在恶意欺诈行为，主要是大点击和安装劫持。做过移动广告的人应该都知道这两种模式，且这两种模式在行业内已经是不公开的秘密。之所以这两种恶意欺诈能够成功，主要还是因为现在移动应用市场归因机制的天然缺陷导致的。
目前国外应用市场相对比国内规范：国内各种应用市场，包括手机厂商自己的应用市场，以及BAT等巨头。而国外几乎只有两家，苹果的App Store和GooglePlay。但两种方式均存在安装归因缺陷。目前的方式是第三方监控公司（类似于Appsflyer, Adjust, Kochava等）监控来自某个应用或publisher的Impression或者click，之后在手机客户端产生app安装激活后，根据之前记录的来自该手机的impression和click，判定该安装应该归因给哪个publisher。该机制貌似合理，但存在很多问题：
这些机制的存在都会导致整个移动互联网广告市场的混乱，大家不再专心做效果，而是将更多的心思和研发资源投入到如何构造更高明能绕过反作弊的机制。而辛苦做效果的广告公司却因为收益被抢而难于存活，形成劣币逐良币的恶性循环。
相关的欺诈反欺诈技术，不是一两篇文章能够描述透彻，也不是今天要讨论的内容。本文主要关注的点，主要还是讨论如何使用技术的问题，来对延迟归因进行建模。
图：CPI广告示例，流量测以cpm和publisher进行结算，广告主侧以cpi进行结算
之所以存在这个问题，是因为刚才提到，移动CPI(按安装付费)广告的归因窗口可以长达7天，甚至到30天：即广告在被展示后，点击后，最终的归因，例如移动CPI广告的安装激活可能在用户展示点击后的7天才会发生，这和传统的CTR预估问题不一样， 传统的CTR预估，可以认为在向用户展现广告后我们马上就能知道用户有没有点击，而手机移动端则可能需要7天甚至更长时间。这样在训练模型时，就会带来以下几个挑战：
所以以上传统的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的概率
故可以对问题进行一下定义：
此处我们根据线上数据，能观察到的数据如下：
以上定义存在以下约束关系：
有了以上定义和约束关系后， 即可对问题进行重新建模，将问题建模为以下两个子模型：
再具体到具体模型的实现，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。
对观察到的数据，分为两类：
在Y=0 and Y=1的情况都公式化后，根据我们能够拿到的数据<xi, yi, ei, di>，根据最大似然估计构建损失函数：
之后使用梯度下降法求解w_lr和w_lambda即可完成建模。
参考文献：
第三次受邀作为嘉宾参加GITC人工智能方向的演讲。前两次的演讲题目都和推荐和变现相关。因为现在在滴滴负责地图感知AI团队，所以这次介绍的内容主要和地图AI相关。
地图中设计到的AI技术与推荐&变现既有相同的地方，但也有很多的不同。
地图是一个整体上环节较多的复杂问题，整个地图系统中涉及到数据采集，生产，更新；中台的各种数据引擎；以及最终的地图应用。而且在涉及到数据生产的过程中会更像传统行业的生产过程，会涉及到较多的生产工艺保证数据质量，如果数据质量上不去，后边的算法效果就无从谈起；同时整个地图产品中涉及到的环节较多，包括底层的物理世界感知，例如定位，地图匹配， 实时路况或者路况预测；作为引擎的路径规划（route planing），ETA，上层的导航等， 均是环环相扣，某个环节没做好，可能都会导致最终效果较差。同时地图还存在另外一个较大的问题：效果不容易评估。
而相较之下，变现或者推荐反倒是一个相对单纯的问题，所有的数据，包括内容数据，用户反馈数据均形成闭环，而且相对来说也较为容易评估
地图中AI的使用场景非常多，例如定位，地图匹配，实时/预测路况，上下车点，ETA，路径规划等。这次演讲的内容主要集中在地图感知AI。什么是地图感知AI？ 说的简单一点，就是我们如何通过大规模的预采集数据，以及用户反馈数据，来感知物理时间中发生的和交通相关的状态和事件。该方向涉及到的环节也非常多，故这次演讲主要集中在底层的地图匹配和实时路况/路况预测两个方向。
图：地图感知AI技术：定位，地图匹配，（实时/预测）路况
图：基于隐马尔科夫模型的地图匹配（Map-Matching）
目前业界比较流行的地图匹配的算法来源，基本的思路都来自于微软09年发布的基于马尔科夫地图匹配算法。该算法的基本思路是将GPS点匹配某条候选道路的概率，拆解为发射概率（观察概率）与转移概率的组合。具体参见博文《LBS地图Map-Matching流行算法及应用》
该方式的优点是模型相对简单，且在很多场景均能够取得较好的效果。但缺点也很明显：该算法很难进一步融入更丰富的特征， 例如GPS的精度，候选道路的属性等，以及运动信息（例如速度是否超过限速信息）
所以后来Map-Matching提升效果的思路逐渐演变为融合多维信息，而最直接的方法就是使用Shallow模型进行学习。
图：浅模型Map-Matching算法
该方向一般一开始的做法，也是性价比最高的做法，都是快速根据专家的经验，使用规则的方式将效果快速做上去，因为现实物理世界情况太多，而且很多时候是只要某个因素发生的时候， 就能够确定现实物理世界发生的情况，但该情况覆盖的CASE却不多。所以一开始使用规则的方式，一方面性价比比较高，另外一方面也能够让我们把问题分析理解的更透彻，例如现实世界可能会出现哪些情况，应该使用那些规则来进行处理。而这些规则， 后续很容易转变为模型的特征输入。
图：Rule-based 路况发布
所以在rule-based的算法做到一定效果后，我们就开始尝试浅模型的方法，为了保持系统的可解释性，我们选择了经典的xgboost。虽然模型并没有那么高深，但效果提升比较明显。
图：浅模型路况发布
而后续需要进一步提升效果，就需要做两方面的工作：更多高质量，信息更丰富的数据， 以及表达能力更强的模型。
对于数据：GPS信息的使用虽然还有空间，但天花板已经比较明显，很难使用GPS就出现质的飞越；此处解决的思路是引入图像数据，因为图像是现实世界的绝对真实体现，信息丰富。
而从模型的角度，浅模型的缺点是很难将时间和空间关系建模进模型。解决的思路很直接：使用图卷积学习空间依赖关系，而使用时间序列学习时间依赖关系。目前该算法还在尝试中[6]
图：时空依赖模型
ETA内容在《工业界ETA技术及滴滴WDR模型》中进行介绍，故此处就不进行展开
图：DIDI WDR ETA[5]
更多内容请参见GITC发布的演讲视频，或参见PPT：滴滴地图感知AI技术及应用
14年之前一直都在做推荐和变现相关的工作，甚至14年入职高德负责高德变现系统时候也是推荐&变现的延伸，但那时已经开始涉及LBS相关的领域，所以可以认为从工作到现在，自己在做的事就是两个方向： 推荐&变现（推荐和变现很多技术比较类似，所以暂且放到一起），以及LBS。今年初入职滴滴负责滴滴地图的部分AI业务后，主要的精力反倒是转到了地图行业，也算是重新回归LBS这个领域，这个过程中也在寻找地图和传统互联网技术（e.g. 推荐&变现）的结合点和爆发点。虽然目前还没找到，但总感觉是可以有明显的创新和爆发点的，原因如下：
所以想要找到创新的结合点和爆发点，就需要深入了解地图行业的细节。而如上提到：地图行业更偏传统行业，有很多自有的业务和技术需要学习，内容实在很多[4]。正好近期在整理地图行业的一个基本topic：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具体是什么，通俗来讲就是绑路（或者路网匹路），就是将收集到的同一用户（例如高德，百度地图或者滴滴地图司机）在时间空间维度的一系列存在精度损失的GPS点，匹配到最有可能的地图路网具体道路上。
但这个过程存在以下难点及挑战：
以上都是map-matching在实际计算过程中的挑战，而且很多到现在都没有解决好，也没有很好的思路。
同时学术界和企业的研究关注点是不一样的，学术界主要基于公布的开源数据进行研究，这些数据有以下几个特点：
但企业就不一样，例如滴滴，和学术界研究的Map-Matching比起来，以下是主要的区别：
该方法只是理论般的存在，在现实中根本无法使用， 因为精度太低。思路比较直观：直接计算对应GPS点和候选道路的投影距离，将GPS点匹配到最近的候选道路上。理论上可行，但具体应用的时候，因为城市道路比较密集，且GPS点存在较多漂移，故该方法不可用。一般甚至不会将该方法作为baseline。
图：nearest-neighbor方法，GPS点直接绑到投影距离最近的道路上
地图匹配中比较经典的方法是使用隐马尔科夫模型（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)进行参数估计
另外在线上系统使用中，为了保证算法的效果，一般会对数据进行预处理，包括但不限于：
在该HMM算法框架下，能够衍生出很多的变种，它们中大部分都是围绕着如何引入更多的信息来对转移概率进行更精准的建模展开了，例如可以在转移概率中不仅考虑greate circle 和route plan distance的差值，还引入转弯次数作为影响因子[3]提升整体算法的效果
从数据特征
HMM虽然是经典的map-matching算法，并且和其他算法相比效果上也有优势，但该算法框架下很难引入更多维度的丰富特征提高地图匹配的准确性。例如GPS点其实有很丰富的数据，例如点速度，点方向， gps点的精度；点和候选道路也有较多可以提取的信息， 例如投影距离，是否超速，是否逆行； 另外还可以加入路网特征，包括道路等级， 限速， 车道数等；最后也可以引入HMM中使用的转移概率等信息。以上信息均可以作为模型的输入。
Lable
地图匹配和路况发布一样，有一个最有挑战的问题就是真值的获取。
现在一般有三种方法来获取真值
模型
使用一般的分类模型即可进行学习， 例如FM或者FFM
因为引入了更丰富的特征，故HMM+Shallow Model的方式效果一般都比HMM要好。我们的试验中，绑路准确性能够提升3.5%
近些年深度学习是模型算法的趋势，但该处我们并没有使用深度学习来解决该问题，主要的原因还是因为真值label获取相对困难，量级没上去，后续随着规则选取及图像的自动化label获取流程打通，成本降低后，会使用LSTM等时间序列模型来提升效果
学术界还有一类算法来提升Map-Matching ，就是使用强化学习[3]。其思路还是将Map-Matching问题建模为HMM，仍然是将最终的概率分解为观察概率(Measurement Probability)及转移概率（Transition Probability），只是具体操作的时候有以下两个变化：
作者号称该方法能够将error rate降低40%(impressive，但是我没尝试过)
滴滴每天有接近3KW个订单，每个订单都能产生较多GPS数据，故在滴滴，Map-Matching的挑战主要有以下几个：
另外地图匹配处理的数据天然就是一序列的GPS点信息，故从处理算法的角度，比较适合使用时间序列模型来进行处理。目前我们也准备将底层的处理逻辑由原有HMM+Shallow模式向时间序列模型进行迁移。
更多内容也可参见: http://www.semocean.com
最近几年共享经济比较火，也出现了很多成功的共享经济企业，而共享经济中比较成功的模式大部分都围绕着共享出行展开业务，例如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(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却非常有挑战。挑战主要来自于以下几方面：
数量较少但影响全局的事件：而碰到节假日或者恶劣天气，整个物理世界的交通也会从系统层面恶化导致预测算法整体失效
但ETA又是一个很基础的关键技术，其应用场景非常广泛， 例如路径规划中用来寻找时间最短的行驶路径，分单，定价，拼单等场景都依赖于ETA。其准确性会直接影响到整个共享出行平台的效率，举几个例子：
因为上述ETA的基础性&重要性，目前滴滴每天的ETA调用次数超过40 billions次（数据出处：https://outreach.didichuxing.com/tutorial/kdd2018/）
传统方法主要分为两类：
图：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方法的问题是很难直接使用这些特征，但复杂模型却能够使用这些特征提升模型的效果。这些特征包括：
模型候选的优化目标可以是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两部分的作用如下：
但在滴滴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机制的深度网络，以后再向大家介绍。
更多内容也可参见: http://www.semocean.com
在推荐系统，或者移动广告变现业务中，抛开内容的生产，用户的增长等挑战后，从算法的角度存在以下几个比较有挑战的技术点：
这些问题解决的好坏都会严重影响系统的效果，而且每一个问题在工业界&学术界都有较多的研究。
下文主要对第4个问题：点击率预估近几年的发展进行简单总结，供大家参考。
广告和推荐算是比较经典老牌的大数据落地的业务场景，而其中的核心技术点CTR预估中使用的技术，也从最经典的LR，逐步发展到树模型，FM等，而近几年随着深度学习技术的发展成熟，现在CTR预估（包括转化率预估）也逐渐开始使用深度学习，并且在各大公司的业务场景中均已经得到较大程度的效果提升。下文就对近期出现的和深度学习相关的CTR预估模型进行总结。方便我个人review也供大家参考。
可以简单定义CTR预估问题为预估P(C|X)，其中：
当然，在更复杂的应用场景下，可能我们不仅需要预估CTR，同时还需要预估CVR（转化率），则此时的问题建模为：
ECPM=P(CLK|X) * P(Conversion|CLK,X) * CPA，此处主要讨论P(CLK|X).
传统的方法主要是使用LR来进行CTR预估，该方法能够适用的主要原因是LR相对来说不仅比较简单，更偏记忆的模型，该模型会记忆高频出现的特征，相当于是对历史的exploitation。而且该模型容易进行并行化，线上处理也非常快，因为虽然训练的时候特征空间有数十亿维，但线上真实使用过程中，非0的特征一般也就就是个，所以处理性能较高。当然该模型缺点也比较明显，就是该模型更多是对历史的记忆，但需要很多人工特征组合，否则原特征的维度上可能不能很好地划分问题，同时人工特征组合也相当于增加了模型的个性化描述，效果会更好。
该方法是facebook发表的其广告系统中使用的CTR预估算法(参见《深度学习资料》)，也算是业界比较经典的算法了。主要思路为：1，使用GBDT进行特征抽特征（进行自动特征组合）；2，使用LR对GBDT抽取的特征（规则组合）进行权重学习。3，一般训练的方式为先将GBDT训练好，之后固定树模型并对叶子节点进行编码作为LR特征训练LR。该方式在业界有较为广泛的应用，例如滴滴路况预测中，能够提升有效准确率2%，而美团ETA应用中预估时间的MAE能够下降3.4%（与论文中3%的下降接近）.；同时文中对影响CTR模型效果的几个因素进行了分析，得到以下几个结论：
当然，如果只是预估排序而不是具体的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预估第一名使用的方法，主要的思路为：
图：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
之后很长时间，工业界使用的方法都是类似于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输入
Wide&Deep推出后，基本上就作为业界的一个baseline的算法框架使用，在这个过程中也会有比较多的网络改进。改进的思路也基本上是在弥补Wide&Deep的各种不足。而优化的方向，基本上就是两个：要么优化wide部分的能力，要么优化deep部分的能力和效果。
例如：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有两个特点：
图：DCN示意图:DNN的同时，增加cross network
具体推导公式为：
图：DCN网络交叉方式：每一层均和输入进行交叉学习残差。同时可以认为cross network的层数，就是特征交叉的阶数
另一种比较常见的模型结构是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共享
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）
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进行更高阶交叉
指在NN的基础上，充分考虑推荐场景下Spatio&Temporal特征，此处空间时间维度的特征在不同场景下含义可以不一致，例如在论文《Deep Spatio-Temporal Neural Networks for Click-Through Rate Prediction》中，主要思想还是使用深度学习进行高维特征交叉。创新点在于该点击率模型同时考虑了空间关系和时间关系对点击率的影响。
该处的空间关系指即将展现的候选广告之前的作为上下文的广告，作为该ad的context，而该用户历史上点击过&未点击的ads则作为空间时序上用户的兴趣表达（该思想和DIN类似）
在具体实施时，文中使用了递进的三种模型：1，特征embedding后直接进行sum pooling；2，解决加入attention机制解决sum pooling带来的信息丢失问题；3，引入context和target的交叉解决context对多个广告不变的问题
总体文章的思路比较直接，最重要创新就是同时引入上下文和用户时间维度上的兴趣表达
当前的CTR预估已经大规模使用深度学习，而且在工业界和学术界仍然在不断地有新的网络结构出现，所以不出意外这些新的网络结构的研究应该还能火两三年。但今年去加拿大参加NeuraIPS时发现一个趋势，就是很多研究人员，以及类似于Google这样的公司都在大力投入到AutoML中，也就是使用机器学习的方法，类似于搭积木似的去寻找最优化的网络结构（超参数）组合，所以会不会两三年后，网络结构的创新，会被AutoML所取代？这个不得而知
之前受邀在QCON进行了名为海外移动变现核心技术的演讲。正好近期也在总结过去一段时间的工作，所以就直接在这儿总结了。
Mobvista的移动变现业务，从流量侧来看，主要分三类流量：
Affiliates买量过程人工运营成分比较多，而DSP可以是一个专门的TOPIC，所以此处就主要介绍Mobvista的自有流量业务的挑战，以及解决方案。
移动变现，特别是国际化移动变现过程中，面临的挑战非常多，以下是主要的挑战：1，广告样式多样化：banner,appwall, offerwall, native, interstitial, native video, rewarded video。 样式丰富，效果表现不一，导致要进行算法抽象，数据共享的时候存在较大挑战
2，转化路径较长：impression -> click -> install(安装激活) -> 应用内付费。。 甚至impression之前的展示广告是否返回成功，SDK加载是否成功等都是问题
3，流量参差不齐，不同国家间网络基础设施也有较大差异
4，移动广告的归因方式， 决定了产业中出现了较多的黑科技。这个之后值得用大篇幅进行介绍
以上这些问题，都是对算法的较大挑战，也早就叫较多算法优化点以及衍生的创收的黑科技。
为了应对上述挑战， 我们必须有较为完善的架构， 算法解决这些挑战。 以下为Mobvista变下架构， 主要包含如下及部分，从左至右分别为流量侧到广告主侧
1.SDK：我们会开发SDK对开发者变现流量进行托管， SDK不仅支持IOS系统， 也支持ANDROID系统， 同时支持多种广告形式， 包括native, appwall和video等广告样式， 从功能上SDK主要负责广告分发， 展现控制， 缓存机制及消费空。 其中自创的缓存机制配合算法， 不仅能大幅减少广告请求交互， 提升广告加载， 展现速度，同时还能保证开发这的ECPM
2.Mobvista会对对外的API进行封装， 所以提供直接的OPEN API供开发者调用。 当然， 一般需要配合SDK的控制机制， 才能达到较高的受益
3.Mobvista同时提供完善的广告设置管理portal对广告素材，预算， 展现机制等进行管理控制，方便对广告的金细化运营
4.同时系统中还有完善的实验机制及样式模板管理， 方便整个系统对效果的优化
5.画红线的部分主要包括我们使用大数据平台对ECPM的模型训练及预估机制
对于模型相关的组件， 在省略了工程细节后， 主要是以下算法策略在系统中的重要组件。
与传统变现系统的较大差别， 在于我们为了处理长转化路径问题，对模型进行了拆分， 拆分为CTR预估模型及CVR模型；
同时为了解决多样性问题， 我们设计了定制的优质campaign探索机制， 及Mobvista的Exploration&Exploitation机制；
同时我们使用模型assabling的方法， 对LR, GBDT， FM等模型进行组合，提升预估精度
Ecpm就是我们预估的目标， 以下是我们对ecpm的拆解方法： 其中 ctr及cvr是未知量， 需要模型进行预估。
预估的方法比较直接： 我们寻找优质高效特征对样本进行描述， 同时使用点击和安装作为labels， 之后训练模型对ctr, cvr进行预估， 最后 使用 ecpm = 1000 * ctr * cvr * price 的方式计算ecpm， 并按照计算ecpm进行广告排序推荐
每次模型升级后会使用a/b test机制进行效果测试， 选出效果最好的模型
下图为我们的模型算法框架图。
为了适应我们全球化的变现业务需求， 我们的大数据机器学习平台是给予亚马逊aws云计算搭建的。
平台分为在线预估部分和离线部分，离线部分又分为日志处理及模型训练与配置模块
我们的日志具有较强的多样性及复杂性， 主要体现在两方面：
1.Mobvsita流量覆盖230+个国家， 故我们再多国及地区均有服务器， 数据需要从多地多服务器进行快速收集汇总
2.Mobvista有多条产品线， 不同产品线为适应业需求特性， 会使用不同存储系统对数据进行存储， 故须要从不同系统中对数据进行收集汇总， 包括DynamoDB, MongoDB, 以及内部的多种API接口
数据均使用AWS EMR分布式系统进行汇总， 计算机清洗。 我们会使用azkaban任务调度系统周期性定时启动生成EMR平台， 对数据进行处理， 处理后的日志按照访问实时性要求高低分别存放在 AWS redshift和S3上。 同时我们会根据数据量大小及计算任务复杂度动态调整EMR集群资源， 在保证计算任务实时性要求的同时， 减少计算资源浪费。 并在AWS上搭建机器学习平台进行模型训练。
更多内容可以参见PPT：
更多内容可直接访问: semocean.com
图：滴滴ETA（接驾ETA以及送驾ETA）