Dong Guo's Blog

ArchSummit2016干货分享

| Comments

上周去参加了ArchSummit 2016,是一个偏架构技术的会,也有一些talk结合了架构和算法一起介绍。我听了十几个和大数据架构和算法比较相关的talk,做了一点小结分享给大家。

Highlights

  1. 订单分配:美团和菜鸟物流(阿里旗下)都简单介绍了自己的订单分配算法,和滴滴分单场景有近似之处。美团的外卖配送在某些方面比滴滴的分单问题更有挑战性,有一些思想可以借鉴,比如权衡体验和效率的“压单”;

  2. 热门的机器学习算法:

    GBDT + LR:腾讯微信的用户相似度预估、广告点击率预估,阿里推荐算法的点击率预估都在用。具体可以看Facebook在2014年的文章;

    FTRL:这个算法是google在2011年左右publish的,被国内各大公司作为online learning的重要选择,我之前实验中做过评估,其显著的几个优点:样本只需要过一遍,预测效果top,稀疏模型

  3. 大规模分布式机器学习框架:

    Parameter Server:若干公司提及,包括一些规模不太大的公司(第四范式、一点咨询),目前来看parameter server还是大规模特征下的分布式机器学习框架的首选

    Spark:spark简单易用,当特征规模在千万之内还是很不多,ThinkData给出自己开源的分布式机器学习算法库,据称在预测效果和训练速度上都显著优于MLlib

  4. 图算法:微信在做定向广告时,需要构造用户在朋友网络上的“社交相似度”特征,其使用了KDD2016最新的node2vec算法,类似Random walk + Word2vec,据称效果显著,有兴趣的可以去看paper;

  5. 知识图谱(Knowledge graph):Facebook的knowledge graph将这块带的很火,在需要理解用户意图给出用户想要的结果的场景下大多会涉及。 本次有2个talk涉及:阿里的自动问答系统,一点咨询(类似今日头条)的新闻搜索;

  6. 深度学习:这次几个talk上提到,不过都还是在尝试,感觉没有DL在其应用中还没发挥核心作用。包括阿里的自动问答,第四范式

  7. 架构引擎相关,有2个talk影响较深刻,一个是阿里双十一的流量规划和压测实践(流量隔离压测 + 配比拉平可以减少直接在线上做压测的风险和人员投入成本),另一个是百度的大数据系统技术栈(百度文件系统BFS,分布式数据库Tera都已在github开源,值得学习一下)

slides 下载

美团:即时物流调度平台实践

现状:美团外卖日订单800万,平均配送时长(从下单到送达)降到了单均28min,配送路程为2KM,28min还是比较厉害的。

美团外卖配送算法在某些方面比滴滴的订单分配更复杂:

  1. 滴滴订单分配的对象是司机和乘客,而美团配送需要考虑三方(骑手、乘客、餐厅)。增加了不少复杂性,比如需要考虑商家备餐时间的不确定性和差异性
  2. 滴滴大部分订单都不是拼车,而美团骑车平均会一次性配送5个订单,订单匹配和组合的效率是核心问题
  3. 路径规划的复杂性更高(设想一个骑车同时被分配了5个订单,候选的路径数)
  4. 配送目的地的复杂性:外卖配送的目的地很多是小区(送达X号楼X单元X层的房间)和写字楼(楼层),应该要考虑更多的骑手个性化

美团的订单分配算法演进

这里的“压单”是等待更多类似的订单,聚合起来一起分配给骑手。有点类似滴滴的拼车等待

在用的几个重要平台:场景回放平台、算法仿真环境(派单场景下)、分布式计算平台

微信朋友圈基于社交相似度的定向广告技术

简介:lookalike是一种经典的广告定向技术,指的是找出和指定目标人群类似的人群。微信使用了包含图特征的有监督学习找出的目标微信用户做广告定向,相比广告随机投放给active用户,可以提高2-3倍的点击率。

算法概况:目标是预估指定用户和另一个微信用户的相似度

  1. 训练样本的label获取:找出公共展示广告较多的用户pair,计算其相似度:共同点击广告个数/共同展示的广告个数
  2. 使用了用户pair之间的社交相似性特征,通过node2vec network embedding算法生成
  3. 机器学习模型:SVR,GBDT+LR都做了尝试

使用node2vec生成社交相似度特征

node2vec = Biased Random Walk + Word2Vec node2vec in KDD 2016: http://www.kdd.org/kdd2016/papers/files/rfp0218-groverA.pdf 强调了调参(网络深度和广度参数p、q)的重要性

GBDT+LR组合模型(通过GBDT学习出高区分性的组合特征,输入到LR中)

Paper from Facebook:http://www.quinonero.net/Publications/predicting-clicks-facebook.pdf (ADKDD 2014)

腾讯和阿里都做了尝试:http://www.cbdio.com/BigData/2015-08/27/content_3750170.htm

一点资讯:兴趣引擎-深度融合搜索和推荐

  1. 检索系统使用了WAND operator:http://cis.poly.edu/westlab/papers/cntdstrb/p426-broder.pdf WAND泛化了AND和OR操作,是更强大的匹配操作符

  2. 异构索引:由于需要在几个维度(近期和长期内容、编辑精品vs抓取内容、垂直频道vs全局内容、热门推荐和个性化推荐)上兼顾搜索和推荐的效果,搞了若干个内容索引,后面会做自适应索引召回(基于对query或者用户的理解决定从哪些索引返回结果)

  3. 自适应索引召回策略:对Query做意图理解,决定返回的文章 除了搜索词本身,还考虑了时下热点,用户浏览搜索上下文,用户兴趣图谱,用户demography等信息 决定从哪些下游索引、服务、内容中获取结果,以及排序

  4. 树状知识图谱 提到了其在用,未透露技术细节。树状知识图谱应该是内容推荐和搜索的关键模块

  5. 模型训练与更新 online learning 准实时模型更新(KAFKA –> Storm –> Online Learning),声称在用Parameter server 模型使用了流行的FTRL 实验框架支持feature configuration

阿里-智能问答系统的实践

  1. 几种主流的问答匹配技术:rule-based模板式匹配,基于检索的模型,基于统计机器翻译SMT,基于深度学习模型 阿里目前以前三者为主,基于深度学习模型在探索
  2. 基于检索的问答模型还是基础方案 基本是搜索的一套方法,在复杂问答场景不胜任(意图识别,上下文对话)
  3. 意图识别,被抽象成分类问题解决。该部分非常有挑战性,阿里也还停留在基础阶段,深度学习被应用在该分类任务中
  4. Knowledge graph有被应用
  5. 语义挖掘:同义语义挖掘、近似词挖掘、潜在语义分析(LSA,PLSA,LDA)
  6. 探索中:Deep learning、Transfer learning、Reinforcement learning

ThinkData:Fregata- Spark上的轻量级大规模机器学习算法库

已开源:https://github.com/TalkingData/Fregata

基于Spark实现的分布式机器学习算法库,目前只有几个基础的模型(LR、softmax、RDT),声称相比MLlib有更快的训练速度和更好的模型效果。

几个点评:

  1. 提出了基于SGD改进的GSA(Greedy Step Averaging)优化算法(出发点是解决SGD等常见的优化算法需要选择learning rate的问题),该算法是Fregata实验效果优于MLlib的主要原因。文章见:https://arxiv.org/pdf/1611.03608v1.pdf
  2. Fregata强调样本一遍过完,无需多次迭代,提高了训练速度(我理解这取决于给定算法是否需要迭代,Fregata目前实现的少数几个模型不依赖于多遍迭代)
  3. Fregata对标MLlib,同基于Spark,依然没有解决训练样本特征维度过高(百万/千万级)无法训练的问题,不如Parameter Server
  4. 目前只实现了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

  1. 对标google BigTable,加强版Hbase,已开源:https://github.com/baidu/tera
  2. keywords:分布式、列存储,支持分布式事务,万亿条记录,百PB容量,亿级QPS读写,全局有序表,快照支持回滚
  3. 分布式:按照row切割成大量的Tablet,做到并发读写,Tablets灵活地分裂与合并
  4. 容错和备份:先写log,再写内存,再固化到磁盘

BFS:百度文件系统

见:https://github.com/baidu/bfs

LinkedIn:Lessons in Internet scale stream processing(海量流数据处理经验总结)

Apache Samza

LinkedIn开源的分布式流数据处理系统,对应于Storm和Spark Streaming,号称计算性能优于MR和Spark。 目前除LinkedIn,Uber、Netflix等公司也在用Samza。

Comments