小说网站开发需求分析,wordpress 主题 中国风,烟台高新区网站,太原网站排名外包**
2015年7月
** 加入滴滴打车3个半月#xff0c;感觉遇到和解决的技术问题超过之前1年的。写在这里给大家分享。 滴滴这边负责所有策略算法设计的是“策略组”#xff0c;大概有20几个员工。由于滴滴的业务线越来越多#xff08;出租车#xff0c;专车#xff0c;快车感觉遇到和解决的技术问题超过之前1年的。写在这里给大家分享。 滴滴这边负责所有策略算法设计的是“策略组”大概有20几个员工。由于滴滴的业务线越来越多出租车专车快车顺风车拼车大巴项目上线时间紧没有时间对策略算法做最好的设计和优化。于是新成立了一个通用模型组目标是抽取出不同业务线的共同点在一个更高的角度设计更好的策略算法特别是提供通用的大规模机器学习支持。我是这个team第一个员工。
订单分配
滴滴一个技术重点是订单分配全国每天有几百万的乘客通过滴滴叫车出行有近百万司机接滴滴的订单如何将订单分配给司机使得更多的人更快地打到车至少有如下问题需要考虑
从大的层面如何设计一套分配策略能够保证目标最大从小的层面分配订单时应该考虑到哪些因素距离是否顺路司机习惯偏好天气供求关系) 这些因素如何组合如何在更长的时间维度上做更优的分配比如当前时刻将乘客A分给司机B是最优的但几秒之后司机C出现了司机C离乘客A要近得多拼车更环保也能帮乘客省钱如何在订单分配中让尽可能多的人在保证体验的同时拼上车TRB中有非常多的文献乘客加价如何影响订单分配我们应该学习Uber的一些策略吗比如播单不告诉司机乘客的目的地
在创业初期可以用规则快速简单地实现现在滴滴已经初步有了一套理论上保证收益的分配策略需要我们进一步去优化效果和效率。
透露一下在整体策略中有一个部分是涉及到大规模机器学习样本是几十亿级别特征是亿级别这是我进来的第一个项目
动态调价
设想在周五的傍晚下班高峰又开始下大雨。在国贸商圈有1000个用户通过滴滴叫车而附近只有100辆车。如何做订单分配应该把有限的车给谁
首先我们需要定义一个目标动态调价的目的是什么最大化成交量最大化流水最大化愿加价乘客打车的成功率还是这几个目标的组合最合理
选定目标之后每个乘客应该加多少钱一个优质订单是不是应该少加点
滴米
为了促进订单成交除了给司机补贴和要求乘客加价是不是还有别的激励方案
于是滴滴牛逼的PM们推出了滴米这个牛逼的产品。滴米是一种虚拟货币对于优质订单一堆司机挤破头来抢我们就扣他们虚拟货币对于没人要的订单我们就奖励滴米。这样就调节了优质劣质订单冰火两重天的不和谐局面。关键是乘客和滴滴不用花一分钱!
产品很牛逼策略上如何支持一个订单发出前如何确定其是扣滴米还是奖励滴米扣多少奖多少每个司机一样吗整个策略会导致通货膨胀或者紧缩吗
到达时间预估
预估司机从A点到B点的时间消耗对滴滴挺重要。如果准确地预估基于哪些数据和因素这是一个机器学习问题吗有更巧妙的预估方法吗
工作感受
说了来滴滴3各月参与和了解的几个项目我觉得都非常有意思也非常有意义。说下来之后的几点体验
第一最大的体会是中国互联网行业特别是滴滴生机勃勃有太多有挑战的事情等着做。产品和策略迭代非常快基本上每天线上的策略设计和架构都会有一次优化上线你每次改动就会影响每天几百万人的出行体验。
第二相比我之前的工作在滴滴工作会和不同岗位的同学紧密合作每天和靠谱的策略组小伙伴一起做策略设计和讨论和90后PM mm们讨论进度和策略设计和QA团队合作测试保证上线风险可控和OP同学配合上线
第三滴滴的招聘质量提升非常快3个月前我刚入职周边同学大概还是百度同学的平均水平现在我参与的面试发的offer的质量基本和hulu差不多了。
最后昨天滴滴大巴上线了现在可供出行的产品线有出租车专车快车顺风车大巴。欢迎加入滴滴在滴滴最美好的阶段和牛逼的人做牛逼的事情一起改变中国人的出行体验。有兴趣的联系我: guodongdiditaxi.com.cn h1 classentry-title**ArchSummit2016干货分享
**
上周去参加了ArchSummit 2016是一个偏架构技术的会也有一些talk结合了架构和算法一起介绍。我听了十几个和大数据架构和算法比较相关的talk做了一点小结分享给大家。 Highlights
订单分配美团和菜鸟物流阿里旗下都简单介绍了自己的订单分配算法和滴滴分单场景有近似之处。美团的外卖配送在某些方面比滴滴的分单问题更有挑战性有一些思想可以借鉴比如权衡体验和效率的“压单”热门的机器学习算法 GBDT LR腾讯微信的用户相似度预估、广告点击率预估阿里推荐算法的点击率预估都在用。具体可以看Facebook在2014年的文章 FTRL这个算法是google在2011年左右publish的被国内各大公司作为online learning的重要选择我之前实验中做过评估其显著的几个优点样本只需要过一遍预测效果top稀疏模型
大规模分布式机器学习框架 Parameter Server若干公司提及包括一些规模不太大的公司第四范式、一点咨询目前来看parameter server还是大规模特征下的分布式机器学习框架的首选 Sparkspark简单易用当特征规模在千万之内还是很不多ThinkData给出自己开源的分布式机器学习算法库据称在预测效果和训练速度上都显著优于MLlib
图算法微信在做定向广告时需要构造用户在朋友网络上的“社交相似度”特征其使用了KDD2016最新的node2vec算法类似Random walk Word2vec据称效果显著有兴趣的可以去看paper知识图谱Knowledge graphFacebook的knowledge graph将这块带的很火在需要理解用户意图给出用户想要的结果的场景下大多会涉及。 本次有2个talk涉及阿里的自动问答系统一点咨询类似今日头条的新闻搜索深度学习这次几个talk上提到不过都还是在尝试感觉没有DL在其应用中还没发挥核心作用。包括阿里的自动问答第四范式架构引擎相关有2个talk影响较深刻一个是阿里双十一的流量规划和压测实践流量隔离压测 配比拉平可以减少直接在线上做压测的风险和人员投入成本另一个是百度的大数据系统技术栈百度文件系统BFS分布式数据库Tera都已在github开源值得学习一下 slides 下载 美团即时物流调度平台实践
现状美团外卖日订单800万平均配送时长从下单到送达降到了单均28min配送路程为2KM28min还是比较厉害的。
美团外卖配送算法在某些方面比滴滴的订单分配更复杂
滴滴订单分配的对象是司机和乘客而美团配送需要考虑三方骑手、乘客、餐厅。增加了不少复杂性比如需要考虑商家备餐时间的不确定性和差异性滴滴大部分订单都不是拼车而美团骑车平均会一次性配送5个订单订单匹配和组合的效率是核心问题路径规划的复杂性更高设想一个骑车同时被分配了5个订单候选的路径数配送目的地的复杂性外卖配送的目的地很多是小区送达X号楼X单元X层的房间和写字楼楼层应该要考虑更多的骑手个性化
美团的订单分配算法演进 这里的“压单”是等待更多类似的订单聚合起来一起分配给骑手。有点类似滴滴的拼车等待
在用的几个重要平台场景回放平台、算法仿真环境派单场景下、分布式计算平台
微信朋友圈基于社交相似度的定向广告技术
简介lookalike是一种经典的广告定向技术指的是找出和指定目标人群类似的人群。微信使用了包含图特征的有监督学习找出的目标微信用户做广告定向相比广告随机投放给active用户可以提高2-3倍的点击率。
算法概况目标是预估指定用户和另一个微信用户的相似度
训练样本的label获取找出公共展示广告较多的用户pair计算其相似度共同点击广告个数/共同展示的广告个数使用了用户pair之间的社交相似性特征通过node2vec network embedding算法生成机器学习模型SVRGBDTLR都做了尝试
使用node2vec生成社交相似度特征
node2vec Biased Random Walk Word2Vec node2vec in KDD 2016 http://www.kdd.org/kdd2016/papers/files/rfp0218-groverA.pdf 强调了调参网络深度和广度参数p、q的重要性
GBDTLR组合模型通过GBDT学习出高区分性的组合特征输入到LR中 Paper from Facebookhttp://www.quinonero.net/Publications/predicting-clicks-facebook.pdf (ADKDD 2014)
腾讯和阿里都做了尝试http://www.cbdio.com/BigData/2015-08/27/content_3750170.htm
一点资讯兴趣引擎-深度融合搜索和推荐
检索系统使用了WAND operatorhttp://cis.poly.edu/westlab/papers/cntdstrb/p426-broder.pdf WAND泛化了AND和OR操作是更强大的匹配操作符异构索引由于需要在几个维度近期和长期内容、编辑精品vs抓取内容、垂直频道vs全局内容、热门推荐和个性化推荐上兼顾搜索和推荐的效果搞了若干个内容索引后面会做自适应索引召回基于对query或者用户的理解决定从哪些索引返回结果自适应索引召回策略对Query做意图理解决定返回的文章 除了搜索词本身还考虑了时下热点用户浏览搜索上下文用户兴趣图谱用户demography等信息 决定从哪些下游索引、服务、内容中获取结果以及排序 树状知识图谱 提到了其在用未透露技术细节。树状知识图谱应该是内容推荐和搜索的关键模块模型训练与更新 online learning 准实时模型更新KAFKA – Storm – Online Learning声称在用Parameter server 模型使用了流行的FTRL 实验框架支持feature configuration
阿里-智能问答系统的实践
几种主流的问答匹配技术rule-based模板式匹配基于检索的模型基于统计机器翻译SMT基于深度学习模型 阿里目前以前三者为主基于深度学习模型在探索基于检索的问答模型还是基础方案 基本是搜索的一套方法在复杂问答场景不胜任意图识别上下文对话 意图识别被抽象成分类问题解决。该部分非常有挑战性阿里也还停留在基础阶段深度学习被应用在该分类任务中Knowledge graph有被应用语义挖掘同义语义挖掘、近似词挖掘、潜在语义分析LSAPLSALDA探索中Deep learning、Transfer learning、Reinforcement learning
ThinkDataFregata- Spark上的轻量级大规模机器学习算法库
已开源https://github.com/TalkingData/Fregata
基于Spark实现的分布式机器学习算法库目前只有几个基础的模型(LR、softmax、RDT)声称相比MLlib有更快的训练速度和更好的模型效果。
几个点评
提出了基于SGD改进的GSAGreedy Step Averaging优化算法出发点是解决SGD等常见的优化算法需要选择learning rate的问题该算法是Fregata实验效果优于MLlib的主要原因。文章见https://arxiv.org/pdf/1611.03608v1.pdfFregata强调样本一遍过完无需多次迭代提高了训练速度我理解这取决于给定算法是否需要迭代Fregata目前实现的少数几个模型不依赖于多遍迭代Fregata对标MLlib同基于Spark依然没有解决训练样本特征维度过高百万/千万级无法训练的问题不如Parameter Server目前只实现了LR、softmax、RDT少数几个模型且尚不兼容Spark1.6以上的版本
第四范式其构建机器学习产品的介绍
整体停下来干货很少。提到一个GDBT计算框架就是实现的Parameter Server。部署在HADOOP那套生态上YARN/HDFS等。
另外第四范式在尝试Deep Sparse Network戴总的研究方向Transfer learning声称“在研究如何应用”状态
阿里巴巴-天猫双11容量规划演进
容量规划经历的几个阶段 压测和容量评估不能以“点”的方式要做场景化压测和评估
容量评估主流程容量评估压测平台
自动化最终自动生成压测报告例行执行可以控制流量要求
流量隔离压测 配比拉平
阿里经历过直接在线上做全链路压测为了线上分享和人员精力消耗“几百人坐在一起盯着自己系统”采取了在隔离的集群上做压测可能占全部机器资源的90%压测完找到合理的机器分配比之后再在全部服务器上做配比拉平
百度Spider3.0背后的数据处理系统数据库Tera文件系统BFS
百度整体的大数据架构技术栈github page 整个Spider3.0处理流程增量处理、流式处理基本都围绕Tera数据库读写
数据爬取延迟从spider2.0的2~3天降低到spider3.0的5分钟
Tera百度高性能分布式NoSQL数据库Tera
对标google BigTable加强版Hbase已开源https://github.com/baidu/terakeywords分布式、列存储支持分布式事务万亿条记录百PB容量亿级QPS读写全局有序表快照支持回滚分布式按照row切割成大量的Tablet做到并发读写Tablets灵活地分裂与合并容错和备份先写log再写内存再固化到磁盘
BFS百度文件系统
见https://github.com/baidu/bfs
LinkedInLessons in Internet scale stream processing海量流数据处理经验总结 Apache Samza
LinkedIn开源的分布式流数据处理系统对应于Storm和Spark Streaming号称计算性能优于MR和Spark。 目前除LinkedInUber、Netflix等公司也在用Samza。 Posted by Dong Guo
2016-12-18T23:29:3208:00 pubdate data-updated“true”Dec 18th, 2016
越来越多人和公司认同data-drivern决策的必要性不仅是滴滴、Google、Microsoft、Linkedin、Amazon这些科技公司也包括传统意义上的非技术公司。Data-drivern的核心是Controlled experiment即大家常说的A/B Testing)按照字面理解就是将其它影响因素都control住保持一致实验结果只由预设的不同方案影响。 在滴滴算法团队很多时间和精力都在做各种策略和算法实验比如我们比较不同的订单分配策略哪个可以让接驾时间更短比如评估新的动态定价策略对乘客的留存和活跃度有什么样的影响。基于近期在做实验方面遇到的一些挑战思考以及上个周末看的几篇文章写一个小结在这里。先介绍几个controlled experiment相关的基础而重要的点总结做controlled experiment中的一些遇到的难点和挑战最后是一些实验方案和架构的构想。 1. 几个基础重要的知识点
1.1. A/A Testing
A/A测试是一个比较有效的实践去检测你的实验设置中是不是有bias。AA测试一般有两种实现方法一种就是仅在实验前做离线数据分析AA测试并不都需要去线上做实验另一种就是在线上setup A/B/A的实验。
1.2. Hypothesis Testing
A/B测试基本都需要通过假设检验计算猜想的置信度你想证明的东西称为alternative hypothesis(“备择假设”比如“我的新算法比老算法能提高CTR”反面称为null hypothesis即“零假设”即“我的新算法和老算法没啥差别”。通过收集A/B实验的数据计算B的均值X_b和A的均值X_a计算二者的diff X_d X_b – X_a如果零假设成立X_d应该较小。在假设策略A和B无明显差别的前提下可以得到X_d服从的分布X_D比较X_d和分布X_D利用小概率事情一次是不会发生的思想实际是设定置信度阈值比如0.05判断是接受还是拒绝零假设。具体公式后续补充
1.3. Sociation or Causality
相关性 因果性非常重要的sense。一个经典的例子是“大量样本表明口袋里有打火机的人得肺癌的概率显著高于口袋里没有打火机的人”
2. 做Controlled experiment容易犯的错误和挑战
通过AB测试产出正确的决策通常是一件非常不容易的事情我可以很容易列举10条常见的导致产出错误结论的原因。错误的结论包括false postive新方案无效或者有负向效果但通过实验得出有效的结论和false negtative新方案有效果但是通过实验判定无效其中false postive相比false negative对公司伤害可能更大。常见的观点是在科技公司的算法和策略优化中80%~90%的idea被验证是无效或者有负向效果的见Microsoft这篇文章【3】的5.1小节
2.1. 几条典型的产出错误结论的原因
AB流量划分不随机比如用用户ID最后一位数字做分流事后才发现该ID并不随机。可通过对数据源深入了解分析和AA测试来减少这方面的错误AB流量划分随机但是control或treatement会影响对方的流量导致对比结果的不可信错误的指标选取比如有时业务指标KPI很难量化选择的“近似”可量化的指标实际相比业务指标差很远实验结果未达到足够的置信度就宣布结论看p-value多break down指标看细节线下线上分流没有对齐实验设计、代码开发、指标选取都没有问题但是由于离线用日志评估结果时未使用和线上一致的分流方案典型的原因是没有将分流标志写入日志离线只能按照口头约定的逻辑重新实现分流逻辑常发生在开发和指标统计不是一个团队时必然导致统计结果有偏差实验期间外部因素干扰了实验结果比如天气或特殊事件任何一个环节的bug实验本身很完美但是你的或者老板给你定的KPI错了
2.2. 挑战1设计合适的AB流量划分方案
常见的流量划分方法有这么几种按照某种ID进行随机划分比如用户ID、session ID、cookie ID按照时间片进行划分比如每半个小时进行算法的轮换、按照地理区域划分比如将城市划分成网格交错apply不同的算法。
AB流量划分的第一点是保证划分的随机性通过做AA测试分析基本可以保证。第二点是保证control/treatment不影响对方的流量对于某些实验上面几种典型的流量划分方案就不可行了。假设滴滴要评估一个新的定价策略是否可以提高GMV我们看下这几种流量划分方案
按照乘客或者订单ID随机划分订单分配算法是全局的所以运力/司机是2个定价策略共享的按照时间片进行划分轮换在当前时间片apply某个定价策略可能会占用下个时间片的运力特别是时间片较短时比如不足一小时影响显著但是时间片越大时间本身引入的外界因素干扰就越大比如不同时段的需求、运力、天气等因素的差异按照地理区域划分同样有运力共享的问题
对于这个case如果你有好的流量划分idea非常欢迎和我交流
2.3. 挑战2确定正确的业务目标和实验指标
想清楚业务优化的目标是一切的基础比较容易犯的错误是优化了一个短期的目标而该短期目标和长期目标常常是冲突的。错误的KPI往往有两个来源一个是所谓的“目标分解阶段性目标”另一个是不了解各种指标之间存在千丝万缕联系的老大直接拍板了一个KPI如果能在不伤害其他指标的情况下做到优化KPI当然是好的但是老大只提了要优化KPI没有说其他指标不能受到影响。
Google在这篇文章【1】中提到了广告的投放不能仅看当下的收入应该看长期的收益年的粒度。如果给用户展示了过多的广告用户会自然地学习到对广告的blindness之后的广告CTR会显著下降。为了度量不同的广告策略对用户长期的影响作者设计AA – AB – AA实验
第一阶段AA挑选两拨有相同广告体验的用户且整体CTR差异不大第二阶段AB给其中一拨人B使用新的广告投放策略即更多的广告展示持续一段时间文中提到是90天第三阶段AA给用户群B恢复和A一致的广告体验对比两拨人的广告CTR 这个阶段采用BB也可行
这里涉及到一个问题用户对广告的blindness程度是受新策略作用时长影响的这种影响可能需要数个月才能收敛作者想去量化这种收敛后的长期影响文中提出了2个方法一个是用指数函数去fit CTR衰减曲线另一个是用机器学习模型去预测使用短期的CTR变化作者提到google在过去几年累积了上百个广告blindness相关的样本可以用作有监督学习。
我们在滴滴也犯过优化与长期目标矛盾的短期目标的错误这里就不细讲了。
3. 统一的一站式实验平台
公司内部需要有一套统一的一站式实验平台按照做实验的顺序包括较完整指标库、实验管理、新建实验、流量管理与冲突检测、实验上线、实时监控报警、查看实验结果等。几个要点如下
正确/权威/完整/统一的指标库每个实验都有自己的一级二级指标全局统一且正确的指标非常关键每次创建实验只需要从指标库中勾选需要观察的指标即可全局流量管理流量划分收敛到平台避免由于未经协调不同的小组创建了同一份流量上创建了冲突的实验且可以设计更高效的流量划分方案比如Google的支持多层正交实验的平台【2】实验管理/检查/分享所有的实验及配置都可在平台上清晰地查看有很多好处比如每个人都有机会了解正在执行的实验查看实验结果和结论专业的同学可以帮忙检查实验的配置创建实验无需开发产品和运营同学也可以操作上线实验实时监控及时发现问题实验创建过程中可以配置任意metric的预期range一旦在线上超过range自动发报警
Google这篇文章【2】提出了支持不同实验在同一个domain的不同layer上overlapping的实验平台架构值得一看。
4. 实验的评审和分享
创建一个公正的实验并产出可靠的结论是非常不容易的事情在目标设定、指标选取、分流方案、外部因素考虑、置信度等任意一个方面出错都可能导致产出误导的结论。所以有一个实验review或者评审的环节就很有帮助了文章【2】中也提到google有这样的实验委员会。
除了把控实验的指标分享讨论有趣的实验有助于stand on each others‘ shoulders这个可以通过wiki、邮件、或者在实验平台的相关页面分享给大家。
在滴滴待了16个月了这一篇说说我理解的未来的智能出行 整个城市的车辆都由一个中枢系统控制车辆的路径规划和控制可以最大化整体城市居民的出行效率交通拥堵从此消失车辆是自动驾驶的所以非常安全车内变成真正的生活空间交通标识和信号灯也不需要了人们不再购买车车也不再属于个人因为在城市的任何区域任何时间1分钟内就可以呼叫到车车辆都是电动的会自己选择合适时机去电池站更换电池。由于车辆没有驾驶室且车辆之间可以像积木一样拼接车辆的外形也会发生变化
归纳起来就是几个关键字共享出行、电气化、汽车网联、自动驾驶 滴滴、Uber、Google以及一众高校正在推进这一科幻版的未来场景 共享出行其是滴滴和Uber们的原始出发点目前中国每天有10~20M乘客通过共享的方式出行。 电气化电动车的成本显著低于汽油车滴滴正在推动更多电动车加入车主行列 自动驾驶这一块已经非常火了一方便有望大大降低交通事故发生率对于滴滴和Uber来说可以省掉司机支出极大地降低成本
Automated and Connected Vehicles技术目前是研究热点有一篇科普文章
