标签归档:2017

如此逼真的高清图像居然是端到端网络生成的?GANs 自叹不如 | ICCV 2017

雷锋网 AI 科技评论按:生成式对抗性网络 GANs 是近几年最热门的机器学习范式之一,它“图像生成效果好”和“训练困难、效果不稳定”的特点吸引了许许多多研究者付出精力进行 GANs 的研究。虽然它在大尺寸图像和图像逼真程度方面的表现仍然有限,但仍然是目前最好的图像生成范式。

所以当看到如此逼真的高分辨率生成图像的时候,我们几乎要以为这是 GANs 的新突破。虽然图中还有一些扭曲和不自然,但是细节和物体的结构已经比较完善。然而定睛一看,这样的效果居然是一个单向的端到端网络完成的!

介绍这项成果的论文「Photographic Image Synthesis with Cascaded Refinement Networks」(用级联优化网络生成照片级图像)已被 ICCV 2017 收录,这篇论文是斯坦福大学博士陈启峰(第一作者)和英特尔实验室视觉组主管 Vladlen Koltun 共同完成的;两人此前也有合作。陈启峰初中时就开始学习信息学,不仅2008年全奖就读香港科技大学,2012年时更同时被斯坦福大学、哈佛大学、MIT、普林斯顿大学、UC 伯克利、UCLA等9所高校全奖录取硕士博士学位,最终选择了斯坦福大学,并于今年6月获得计算机博士学位。

以下雷锋网 AI 科技评论就对这篇论文做详细的介绍。

想法提出

作者们的目标是生成大尺寸的、质量接近照片的图像。这个目标有足够的难度,现有的基于 GANs 的方法生成的图像在尺寸和逼真程度上都有各种问题,而 GANs 本身训练困难的特点更是雪上加霜。所以 GANs 的方法不适用。

作者们想到了这样一个点子,假如给定一个街道布局,比如左图这样,不同的物体也做出了语意级别的区分,一个熟练的画手可以很快根据这样的布局画出一幅画,专业的艺术家甚至可以可以据此创造出像照片一样真实的画作。那么,能否把这样的能力赋予一个计算模型呢?就是给定一个带有语意物体布局的场景(左图),能否让一个人工智能系统生成一张这个场景对应的照片级的图像(右图)呢?

另一方面,这个任务也有现有的成果可以类比,那就是图像的语意分割。“从一张真实世界的图像生成语义分割布局图像”,就和作者们的想法“从语义布局图像生成照片级图像”互为逆任务。既然图像分割可以用端到端卷积网络来做,那么从“分割结果”生成图像也就可以用端到端卷积网络来做。

图像生成任务有哪些特点

不过端到端网络的总体结构还不足以保证图像的质量。所以作者们在根据其它现有的网络结构做了很多实验以后,列举出了三项他们认为非常重要的特点,模型要满足这三点才能有足够好的表现。

全局的协调性: 照片中物体的结构要正确,许多物体的结构都不是在局部独立存在的,它们可能有对称性。比如如果一辆车左侧的刹车灯亮了,那右侧的刹车灯也要亮。

高分辨率:为了达到足够高的分辨率,模型需要具有专门的分辨率倍增模块。

记忆力 (Memory):网络需要有足够大的容量才能复现出图像中物体足够多的细节。一个好的模型不仅在训练集中要有好的表现,也要有足够的泛化能力,都需要网络容量足够大。

巧妙的网络结构设计

为了同时达到以上的三个特点,作者们设计了一个由多个分辨率倍增模块组成的级联优化网络 CRN。

模型一开始生成的图像分辨率只有 4×8,通过串接的多个分辨率倍增前馈网络模块,分辨率逐步翻番,最终达到很高的图像分辨率(比如最后一个模块把512×1024的图像变成1024×2048)。这就是论文标题的“Cascaded Refinement Networks”的体现。这样做的好处是,

1. 覆盖大范围的物体特征一开始的时候都是在很小的临近范围内表示的,它们的总体特征在一开始就是协调的,在分辨率逐步升高的过程中也能够保持下来,就达到了“全局的协调性”。

2. 在提高分辨率的过程中,使用串接的多个前馈网络模块就可以对整个模型做端到端的训练,如果这部分用 GANs 就没办法端到端训练,而且分辨率选择的灵活性也变差了。这样就保证了“高分辨率”。

3. 增加更多的分辨率倍增模块可以提高网络容量,作者们表示只要硬件能够支持就可以增加更多的模块,现在他们实验中用到的网络有超过1亿个参数,已经用尽了GPU的显存空间,但是有明确的证据表明继续增大网络容量可以继续提高图像质量。这样模块化的网络也就非常方便在硬件资源充足的情况下拓展网络容量。

每个分辨率增倍模块都在各自的分辨率下工作,它们的输入有两部分,一部分是降采样到当前模块分辨率的输入语义布局图像 L,另一部分是上一级模块的输出特征层 Fi-1 (最初的模块没有这一项输入),其中包含若干个 feature map。输出的 Fi 分辨率在输入 Fi-1 的基础上长宽都为2倍。

单个模块的示意图,L 和 Fi-1 为模块输入;语义布局图像 L 需要降采样,来自上一个模块的 Fi-1 需要升采样。

每个模块都由输入、中间、输出三个特征层组成,其中在输入层直接翻倍分辨率,并且没有使用升倍卷积,因为那样会带来特征的瑕疵。除了最后一个模块要输出最终结果外,每个模块的每个层后都跟着一个 3×3 卷积层、正则化层和LReLU非线性层。

对于论文中测试的输出分辨率为 1024 x 2048 的模型,一共用到了9个分辨率增倍模块。在每个模块的特征层中包含 feature map 数目的选择上,第一个到第五个模块为1024,第六到第七为512,第八个为128,最后一个为32。

训练损失和训练过程

“从语义布局图像生成照片级图像”其实是一个约束不完全的问题,同一个布局图像对应的足够真实的照片级图像可以有许多种。所以即便在训练时,作者们也是把布局对象对应的照片称为“参考图像”而已。

损失函数设计

对于约束不完全的训练问题,作者们希望找到一个最适合的损失函数。若直接对训练输出和参考图像做像素对像素的对比,会对足够真实的内容也造成很大的惩罚,比如生成的车颜色不同的时候就会有很大惩罚,但这其实是不必要的。所以作者们选择了内容表征的方法,或者说是感知损失、特征匹配的方法,跟视觉网络中的特征匹配激活对应,这样就与参考图像的低级特征保持了足够的距离。

具体的做法上作者们另辟蹊径,借助一个 VGG-19 图像感知模型,提取它识别的图像特征中高低不同的某几层作为计算训练损失的依据,从而同时涵盖了图像特征中边缘、颜色等低级细粒度特征和物体、类别等高级总体布局特征,从而构建了全面、强力的损失函数。

生成多样化的图像

作者们认为,既然“从语义布局图像生成照片级图像”本身就会带来多种结果,所以他们应当让模型也生成多种不同的结果。他们首先尝试了让网络生成多张不同的图像然后从中选出最好的一张;然后最终更换为了一个更强大的损失函数,它起到的作用类似于在所有生成图像中分别选择每个语义类别对应的图像中最真实的那部分, 然后把它们全部拼在一起,从而让最终的输出图像得到了非常高的真实度。下图即为加入多样性损失之后,让模型从同一个输入生成的9张不同图像。

效果测试

作者们把所提的CRN网络与在同样的测试条件下与其它网络做了对比,包括 GANs(修改了鉴别器加入了语意分割损失)、全分辨率网络(中间层也是全分辨率,与 CRN 相同损失函数)、自动编解码器、只使用低级图像空间损失的CRN、以及 图到图转换GAN(论文中以Isola et al.指代)。

另一组对比

图中可以看到,基于 Cityscapes 和 NYU 两个数据集的测试中,论文中提出的 CRN 都取得了非常好的观感,与其它的相比,简直就像是真实的照片;所用到的训练样本数目也仅仅分别为 3000 张和 1200张而已。

作者们也通过 Amazon MTurk 众包平台平台进行了量化对比测试:每次给被试者提供两张图像,一张来自 CRN,一张来自其它网络,看看他们有多高的比例认为 CRN 的图像更真实。

结果非常有说服力,只有采用了相同的损失函数的全分辨率网络取得了与 CRN 接近的成绩。这首先说明了作者们选择的损失函数效果非常好,准确地训练出了网络构建重要特征的能力;而另一方面因为全分辨率网络的中间层特征太多,导致足够 CRN 训练 1024×2048 分辨率的显存只够全分辨率网络训练 256×512,这也体现了级联优化模块结构的优点。CRN 同时在分辨率和真实度上取胜。

泛化能力

我们可以看到,对于高质量的语义布局输入,CRN表现出了很高的水平。那么模型的泛化能力如何呢?在与论文作者陈启峰博士取得联系并表达了我们的疑问后,陈启峰博士介绍了两项模型泛化的结果。

粗粒度语义布局输入

可以看到,对于粗粒度的语义布局图像输入,模型也维持了相当的表现,并没有因此造成严重的细节损失;物体结构的完整和清晰程度有所下降的。

从GTA5游戏生成图像

作者们的另一个想法是把这项技术用来给游戏生成真实的画面,成为一种新的渲染逼真游戏画面的方式。他们尝试的游戏是 GTA5,用 Cityscapes 数据集训练模型以后,从 GTA5 抓取语义布局作为模型输入,得到的结果同样充实、逼真,单独看画面根本想不到和 GTA5 有任何联系。陈启峰博士表示,“语义布局图很容易在游戏里抓取,这对未来游戏或电影画面生产可能会有深刻影响”。

总结

作者们也剪辑了一个视频,集中展示了生成的画面效果。

这篇论文用精彩的方法生成了高分辨率、高真实度的图像,其中衡量真实度和提高生成图像丰富性的方法有很高的借鉴价值。所提的方法很好地完成了“从语义布局图像生成照片级图像”的任务,而且具有一定的泛化能力。我们期待论文中的技术在未来的研究中进一步得到发扬光大。

雷锋网 AI 科技评论编译。感谢陈启峰博士对本文的补充!

论文地址:https://arxiv.org/abs/1707.09405v1 

陈启峰个人主页:https://web.stanford.edu/~cqf/ 

项目地址:https://github.com/CQFIO/PhotographicImageSynthesis 

雷锋网

EMNLP 2017 最佳论文揭晓,「男人也爱逛商场」获最佳长论文

雷锋网 AI 科技评论按:2017年 EMNLP 自然语言处理实证方法会议(Conference on Empirical Methods in Natural Language Processing)将于2017年9月7-11日在丹麦哥本哈根市召开。EMNLP是自然语言处理领域的顶级会议,由ACL学会下属特殊兴趣小组 SIGDAT(ACL Special Interest Group on Linguistic data and Corpus-based Approachesto NLP)组织,每年召开一次。近几年的 EMNLP 会议都吸引了来自学术界和企业界的近千人参加,论文投稿数目也有上千篇。

今年 EMNLP 共接受论文323篇,其中216篇为长论文,107篇为短论文。EMNLP 2017 也于昨日公布了最佳论文获奖论文名单,四篇论文分获两个最佳长论文奖、一个最佳短论文奖和一个最佳资源论文奖。

最佳长论文两篇

「Men Also Like Shopping: Reducing Gender Bias Amplification using Corpus-level Constraints」

  • “用语料库级别的限制减少性别偏见的放大程度,其实男人也喜欢购物”

  • 论文作者:Jieyu Zhao, Tianlu Wang, Mark Yatskar, Vicente Ordonez and Kai-Wei Chang

  • 论文简介:在具有网络图像支持的富视觉识别问题定义上,语言的使用越来越多。结构化的预测模型也在这样的任务中得到使用,它们的好处是能够利用联合出现的标签和视觉输入之间的联系,随之而来的风险是把网络内容中的社会偏见也编码到了里面。在这篇论文中,作者们研究了与多标签物体识别和视觉语义角色标注相关的数据和模型,然后发现用于支持这些任务的数据集含有显著的性别偏见,用这样的数据集训练出的模型会进一步扩大已有的偏见。比如,在数据集中“做饭”这项活动有女性参加的比例比有男性参加的比例至少大33%,用这个数据集训练出的模型在测试中会把这种区别进一步扩大到68%,作者们提出了这样的方法:在模型中增加语料库级别的限制,以矫正现有的结构化预测模型的表现,并且设计了一个基于拉格朗日松弛法的算法用于各项推理。修改后的模型在文中的识别任务中几乎没有任何表现下降,但是在多标签分类和视觉语义角色标注任务中,把偏见的扩大程度相对减少了47.5%和40.5%。

  • 论文地址:https://arxiv.org/abs/1707.09457 

「Depression and Self-Harm Risk Assessment in Online Forums」

  • “在线论坛中的抑郁和自残风险评估”

  • 论文作者:Andrew Yates, Arman Cohan and Nazli Goharian

  • EMNLP暂时未公布这篇论文的更多细节

最佳短论文

「Natural Language Does Not Emerge 'Naturally' in Multi-Agent Dialog」

  • “多智能体对话中的自然语言不是真的‘自然地’产生的”

  • 论文简介:近期已经有一系列研究提出了在协作多智能体群体中做沟通协议学习的端到端方法,而且同时发现了这些智能体产生的沟通协议中出现了人类可以解释的实证语言,这些都是在无需人类监督的状况下学习到的。在这篇论文中,作者们以一项两个智能体间的任务描述推理游戏为测试环境,展示了从“负面”到“正面”的一系列结果,表明了虽然多数有智能体参与的语言是有效的(表现为取得了接近完美的任务回报),但是它们都自主选择成为了既不可解释、又不具有组合性的语言。究其根本,作者们发现自然语言并不是真的“自然地”产生的,尽管近期的文献中可以看到自然语言的产生很简单的表象。作者们探讨了如何如何引导这些新创作的语言,来让它们越来越像人类的语言、越来越具有组合性,方法就是对两个智能体可能的沟通方式中加入更多的限制。

  • 论文作者:Satwik Kottur, José Moura, Stefan Lee and Dhruv Batra. 

  • 论文地址:https://arxiv.org/abs/1706.08502 

最佳资源论文

「Bringing Structure into Summaries: Crowdsourcing a Benchmark Corpus of Concept Maps」

  • “给文档总结加上结构:众包得到的概念图语料库 benchmark”

  • 论文简介:概念图可以用来简明地表达重要信息以及给大型文档集合建立结构。所以,作者们研究了一系列概念图形式的多文档总结方式。然而,目前没有合适的数据集可以用在这项任务中。为了补上这个缺口,作者们介绍了一组新创造的概念图语料库,它对关于教育话题的各种各样的网络文档做了总结。在它的创立过程中使用了一种新的众包方法,让作者们能够高效地判定大规模文档集合中的重要元素。与这个语料库同时发布的还有一个基准系统和作者们提出的评估流程,以便未来的研究者更好地进行这一系列总结方式的研究。

  • 论文作者:Tobias Falke and Iryna Gurevych.

  • 论文地址:https://arxiv.org/abs/1704.04452 

EMNLP 2017会议期间,雷锋网 AI 科技评论也会派出记者带来全方位报道,敬请期待。同时欢迎阅读近期的更多学术会议报道。

雷锋网 AI 科技评论编译。

雷锋网

Data Science in China论坛:大牛云集,掀起产学结合新高潮 | KDD 2017

北京时间8月16日(美国当地时间8月15日),在加拿大哈利法克斯举行的第23届国际数据挖掘大会(KDD 2017)进入主会议程。KDD China在大会第一天的主会议程中组织“Data Science in China at KDD 2017”的分论坛,集中展现中国在数据挖掘领域的进展和华人在该领域的研究成果,雷锋网作为特约媒体参加论坛并进行了独家报道。

半壁江山,数据挖掘最强华人力量

前一天开幕式上显示的数据表示,在KDD 2017大会上,来自中国的参会者仅次于美国。在开幕式上的颁奖仪式中,不仅裴健教授、杨强教授分获KDD创新奖和KDD杰出服务奖两项分量最重的大奖,中国队伍还几乎包揽了KDD CUP两个竞赛题目的前十名。此外大会的“与大咖面对面”的现场交流活动中,五位嘉宾有三位是华人,大会的开场Keynote也由UC Berkeley的Bing Yu教授演讲,雷锋网再次感受到了数据挖掘领域崛起的华人力量。

在大会颁发的资料中,雷锋网还发现了这样一个有趣的统计:Microsoft Research对近5年KDD高影响力作者进行了一个评估,如下图所示,其中泡泡大小代表发表文章的数量,纵轴反映了论文作者在KDD发表的每篇文章引用数排名(代表文章的质量),横轴是把不同作者论文的引用关系连城一个异构网络,再用类似pagerank的方法计算每个作者的影响力,越靠近右上角排名越高。从图中我们可以看到多位华人学者名字,占到了图中高影响力作者的半壁江山。

(来源:大会资料 & Microsoft Research)

大牛云集:八位演讲嘉宾,37万引用

“Data Science in China at KDD 2017”论坛由China Chapter of ACM SIGKDD(KDD China)承办。KDD China秘书长郑宇表示,这是KDD大会上连续第三年举办中国主题的分论坛。论坛邀请了八位来自数据挖掘领域杰出的华人教授、科学家以及工业界精英进行了精彩的报告,ACM数据挖掘领域的三位Fellow韩建炜教授(2003)、刘兵教授(2015)、裴健教授(2015)也来到现场,其中刘兵教授主持了第一个议程,裴健教授进行了报告。

在微软亚洲研究院主任研究员、KDD China 秘书长郑宇博士的主持下,分论坛在下午1:30开始。杨强教授致开幕词并回顾了KDD在中国的发展历史。他说,AI在中国和数据库在中国都是热门领域,但KDD相对来说知道的人却没有那么多。回想1989年 KDD第一次在中国开workshop到现在,有很多先行者为KDD在中国的发展做出了贡献。现在KDD China已拥有800名会员,在KDD上也展示了自己的力量,与包括郑宇、周志华等在内的KDD China管理团队努力分不开。杨强教授同样对两位SIGKDD华人主席刘兵、裴健以及KDD 2017大会主席俞诗鹏对KDD China工作以及本次分论坛召开的支持表示了感谢。

随后的论坛分两个议程进行。第一个议程由刘兵教授主持,杨强教授首先做了《Feature Engineering and Transfer Learning》(特征工程与迁移学习)的报告。杨强教授介绍,特征工程就是一个把原始数据转变成特征的过程,在典型的数据挖掘过程中,特征工程是选择数据之后的第二步,处于承上启下的重要位置。杨强教授指出,特征比模型更为重要,因为特征对于模型来说是中性的,这也是迁移学习的基础。杨强教授还详细介绍了将迁移学习与机器学习结合的应用,如将用户微信小额交易数据挖掘用于购车等大额消费的例子,在演讲最后的“Big Data is useless unless it can deliver big feature space”的总结也得到了随后多位演讲者的赞同。

(香港科技大学杨强教授)

随后来自罗格斯-新泽西州立大学的熊辉教授带来了题目为“Talent Analytics:Prospects and Opptunities”的报告,介绍了数据挖掘在在人力资源及企业管理的应用,包括:利用数据对人才进行评价和意愿分析,以辅助升职考核、招聘等流程。熊辉教授称,企业人力资源的数据挖掘有三个层次,包括人、企业与文化层面,目前的主要研究工作集中在人的层面,下一阶段会继续对企业及文化层面进行研究。


(罗格斯-新泽西州立大学熊辉教授)

来自微软亚洲研究院主任研究员郑宇博士的报告题目为《Urban Computing——Urban Big Data Platfrom》。在报告中郑宇博士介绍了城市计算机城市大数据平台在市政规划工程中的应用,由于城市大数据存在大规模和变化性的特征,需要基于云的城市大数据平台进行处理,通过不断获取、整合和分析城市中多种异构大数据来解决城市所面临的挑战,通过人工智能来帮助改善公共交通。在报告中,郑教授还通过如流量预测、与贵阳市政府的合作、与基于共享自行车的自行车道规划及车辆管理等实际工作进行了详细介绍。

(微软亚洲研究院主任研究员郑宇博士)

论坛议程二由UCLA的王薇教授主持。今日头条科学家李磊博士介绍了今日头条的新闻机器人、写稿机器人等实际应用及在深度综合、语言生成、语言建模、深度学习QA系统CFO、面部识别方面的研究工作。

(今日头条科学家李磊博士)

滴滴研究院副院长叶杰平的演讲题目为《Intelligent Dispatch System》。叶杰平称,滴滴的核心是一个交易平台,匹配是滴滴业务中的关键问题,并介绍了滴滴在用户与司机的匹配从群发信息、定向推送、精确匹配的三个阶段,利用机器学习提高ETA准确率和预测目的地、推荐上车点等两个创新,以及大数据预测司机服务分值、提升用户体验等实践。

(滴滴研究院副院长叶杰平)

随后西蒙弗雷泽大学裴健教授带来了《Data Science & AI in China industry:some personal experience》的报告。报告从人工智能产业化以及将人工智能应用到传统行业出发,探讨如何解决供应链、制造业等等传统行业数据无法自动收集、复杂和非标准化的应用场景、技术问题难以转化成典型的AI问题等挑战,并结合了裴健教授与华为的合作为例进行详细介绍,包括基于华为内部供应链端到端优化,实现智慧化模型、风险控制、热线客服等,希望用AI改变整个生产流程等实践,并分享了作为学术研究者在最近一年来与华为合作的收获。另外,裴健教授也是本届KDD大会创新奖(2017 ACM SIGKDD Innovation Award)的获得者。

(西蒙弗雷泽大学裴健教授)

清华大学的唐杰博士介绍了AI和深度学习在慕课(MOOCs)教育中的应用。值得一提的是,KDD Cup 2015的竞赛题目“用大数据预测MOOCer是否会‘翘课’”就出自唐杰博士之手,这一报告也是其后续的相关研究,并展示了通过小木机器人做慕课助教与学员进行智能交互改善学习,以及利用LadFG提升预测准确率,提升慕课教育效果的实践。

(清华大学唐杰博士)

同样来自清华大学的崔鹏博士则带来了社会动力学中的建模问题的分享。由于人的行为机理的复杂性以及动态性,而传统机器学习方式类似黑盒,难以将社会动力学研究特征化,也难以做持续的预测,通过物理学模型及数据驱动相结合,已经可以构建一个关键统计指标和真实社交网络基本一致的社交网络,可以对社交网络信息传播进行准确的预测。

(清华大学崔鹏博士)

在第一个议程结束后,会议组织者与报告嘉宾合影留念。这张合影可谓珍贵:组织者和嘉宾中包含2位SIGKDD主席(刘兵@2013,裴健@2017)、2位KDD大会主席(杨强@2012,俞诗鹏@2017),三位KDD大会PC Chair(杨强@2010,王薇@2014,熊伟@2018),两位KDD创新奖获得者(韩建炜@2004,裴健@2017),三位KDD杰出服务奖获得者(裴健@2015,王薇@2016,杨强@2017) ,论文引用总数超过37万,可谓汇聚了华人数据挖掘领域的中坚力量。

照片后排左起: 清华大学副教授崔鹏、微软亚洲研究院主任研究员、KDD China秘书长郑宇、美国罗格斯-新泽西州立大学教授熊辉、美国亚利桑那州立大学教授刘欢、滴滴研究院副院长叶杰平、KDD 2017大会主席俞诗鹏、今日头条实验室科学家李磊、清华大学副教授唐杰;

前排左起:美国伊利诺伊大学芝加哥分校教授、SIGKDD前主席刘兵、美国伊利诺伊大学香槟分校教授韩家炜、香港科技大学教授、KDD China主席杨强、加拿大西蒙弗雷泽大学教授、SIGKDD现任主席裴健。

(雷锋网注:本次分论坛议程二的主持人,UCLA教授、本次KDD大会创新奖与KDD杰出服务奖提名主席、KDD 2016杰出服务奖得主王薇,因为在大会还有其他事务,在拍照后才赶到,因而不在本照片中)

大数据需要更多产学合作

随着大数据的不断积累以及计算能力的快速发展,与其相关的人工智能研究也得到了快速的发展。如同杨强教授在本次论坛上所言,数据挖掘的核心在于“挖掘”而非“数据”,在数据量暴增的同时,与之对应的数据选择、算法、特征工程也更重要,掌握学术前言趋势的学术界与掌握大量数据的产业界需要更紧密合作,推动数据挖掘与人工智能的发展。

雷锋网了解到,在诸多学术会议中,KDD属于学术与产业相结合较为紧密的会议之一。在本次分论坛上,多位嘉宾的报告内容均与产业紧密结合,让我们得以了解了学术界与产业界就大数据与人工智能话题技术的交流动向,以及大数据和人工智能的最新先锋应用。祝愿通过本次论坛的召开能够扩大华人在国际数据挖掘领域的影响力,推动国内数据挖掘领域的研究和在工业界的应用和发展。

雷锋网

Alex Smola论文详解:准确稀疏可解释,三大优点兼具的序列数据预测算法LLA| ICML 2017

雷锋网 AI 科技评论按:近日,ICML2017收录的一篇论文引起了雷锋网AI科技评论的注意。这篇关于序列数据预测的论文是 Alex Smola 和他在 CMU 时的两个博士生 Manzil Zaheer 和 Amr Ahmed 共同完成的,后者目前已经加入谷歌大脑。

Alex Smola是机器学习界的重要人物,他的主要研究领域是可拓展算法、核方法、统计模型和它们的应用,已经发表超过200篇论文并参与编写多本学术专著。他曾在NICTA、雅虎、谷歌从事研究工作,在2013到2016年间任CMU教授,之后来到亚马逊任AWS的机器学习总监。MXNet 在去年成为 Amazon AWS 的官方开源平台,而 MXNet 的主要作者李沐正是 Alex Smola 在 CMU 时的学生。

以下雷锋网 AI 科技评论就对这篇名为「Latent LSTM Allocation: Joint Clustering and Non-Linear Dynamic Modeling of Sequential Data」(潜LSTM分配:序列数据的联合聚类和非线性动态建模)的论文做具体的介绍。

研究背景

序列数据预测是机器学习领域的一个重要问题,这个问题在文本到用户行为的各种行为中都会出现。比如在统计学语言建模应用中,研究目标是在给定的语境下预测文本数据的下一个单词,这和用户行为建模应用中根据用户历史行为预测下一个行为非常类似。准确的用户行为建模就是提供用户相关的、个性化的、有用的内容的重要基础。

一个好的序列数据模型应当准确、稀疏、可解释,然而目前所有的用户模型或者文本模型都不能同时满足这三点要求。目前最先进的序列数据建模方法是使用 LSTM(Long-Short Term Memory)这样的 RNN 网络,已经有许多例子证明他们可以有效地捕捉数据中的长模式和短模式,比如捕捉语言中表征级别的语义,以及捕捉句法规律。但是,这些神经网络学到的表征总的来说不具有解释性,人类也无法访问。不仅如此,模型所含的参数的数量是和模型能够预测的单词类型或者动作类型成正比的,参数数量往往会达到千万级甚至亿级。值得注意的是,在用户建模任务中,字符级别的 RNN 是不可行的,因为描述用户行为的往往不是单词而是 hash 指数或者 URL。

从另一个角度看这个问题,以 LDA 和其它一些变种话题模型为代表的多任务学习潜变量模型,它们是严格的非序列数据模型,有潜力很好地从文本和用户数据中挖掘潜在结构,而且也已经取得了一些商业上的成果。话题模型很热门,因为它们能够在不同用户(或文档)之间共享统计强度,从而具有把数据组织为一小部分突出的主题(或话题)的能力。这样的话题表征总的来说可以供人类访问,也很容易解释。

LLA模型

在这篇论文中,作者们提出了 Latent LSTM Allocation(潜LSTM分配,LLA)模型,它把非序列LDA的优点嫁接到了序列RNN上面来。LLA借用了图模型中的技巧来指代话题(关于一组有关联的词语或者用户行为),方法是在不同用户(或文档)和循环神经网络之间共享统计强度,用来对整个(用户动作或者文档)序列中的话题进化变化建模,抛弃了从单个用户行为或者单词级别做建模的方法。

LLA 继承了 LDA 模型的稀疏性和可解释性,同时还具有 LSTM 的准确率。作者们在文中提供了多个 LLA 的变种,在保持解释性的前提下尝试在模型大小和准确率之间找到平衡。如图1所示,在基于Wikipedia数据集对语言建模的任务中,LLA 取得了接近 LSTM 的准确率,同时从模型大小的角度还保持了与 LDA 相同的稀疏性。作者们提供了一个高效的推理算法用于LLA的参数推理,并在多个数据集中展示了它的功效和解释性。

柱状图是参数数量,折线是复杂度。根据图中示意,在基于 Wikipedia 数据集的语言建模任务中,LLA 比 LDA 的复杂度更低,参数数量也比 LSTM 大大减少。

LLA 把分层贝叶斯模型和 LSTM 结合起来。LLA 会根据用户的行为序列数据对每个用户建模,模型还会同时把这些动作分为不同的话题,并且学到所分到的话题序列中的短期动态变化,而不是直接学习行为空间。这样的结果就是模型的可解释性非常高、非常简明,而且能够捕捉复杂的动态变化。作者们设计了一个生成式分解模型,先用 LSTM 对话题序列建模,然后用 Dirichlet 多项式对单词散播建模,这一步就和 LDA 很相似。

假设话题数目为K、单词库大小为V;有一个文档集D,其中单篇文档d由Nd个单词组成。生成式模型的完整流程就可以表示为(上图 a 的为例):

在这样的模型下,观察一篇指定的文档d的边际概率就可以表示为:

式中,就是文档中给定某个话题下的前几个词之后,对下一个次生成话题的概率;则是给定了话题之后生成单词的概率。这个公式就展现出了对基于 LSTM 和 LDA 的语言模型的简单改动。

这种修改的好处有两层,首先这样可以获得一个分解模型,参数的数量相比 RRLM 得到了大幅度减少。其次,这个模型的可解释性非常高。

另一方面,为了实现基于 LLA 的推理算法,作者们用随机 EM 方法对模型表示进行了近似,并设计了一些加速采样方法。模型伪码如下:

LLA变体

作者们认为,模型直接使用原始文本会比使用总结出的主题有更好的预测效果。所以在 Topic LLA之外,又提出了两个变体 Word LLA 和 Char LLA (前文 a、b、c 三个模型),分别能够直接处理原文本的单词和字符(Char LLA自己会对字符串做出转换,从而缓和 Word LLA 单词库过大的问题 )。

实验结果

在几个实验中,作者们把60%的数据用于训练模型,让模型预测其余40%作为任务目标。同步对比的模型有自动编码器(解码器)、单词级别LSTM、字符级别LSTM、LDA、Distance-dependent LDA。

柱状图部分的参数数量用来体现模型大小,折现的复杂度用于体现模型的准确率。可以看到,两个任务中 LDA 仍然保持了最小的模型大小,而单词级别LSTM表现出了最高的准确率,但模型大小要高出一个数量级;从单词级别LSTM到字符级别LSTM,模型大小基本减半,准确度也有所牺牲。

在这样的对比之下就体现出了 LLA 的特点,在保持了与 LDA 同等的解释性的状况下,能够在模型大小和准确度之间取得更好的平衡(目标并不是达到比LSTM更高的准确率)。

其它方面的对比如下:

收敛速度  LLA的收敛速度并没有什么劣势,比快速LDA采样也只慢了一点点。不过基于字符的LSTM和LLA都要比其它的变体训练起来慢一些,这是模型本质导致的,需要在单词和字符层面的LSTM都做反向传播。

特征效率  作者们做了尝试,只具有250个话题的三种 LLA 模型都比具有1000个话题的 LDA 模型有更高的准确率。这说明 LLA 的特征效率更高。从另一个角度说,LLA 的表现更好不是因为模型更大,而是因为它对数据中的顺序有更好的描述能力。

解释性  LLA和LDA都能对全局主题做出揭示,LLA 总结出的要更加明确。如下表,LDA 会总结出“Iowa”,仅仅因为它在不同的文档中都出现了;而 LLA 追踪短期动态的特性可以让它在句子的不同位置正确切换主题。 

联合训练  由于论文中的模型可以切分为 LDA 和 LSTM 两部分,作者们也对比了“联合训练”和“先训练 LDA,再在话题上训练 LSTM”两种不同训练方式的效果。结果表明,联合训练的效果要好很多,因为单独训练的 LDA 中产生的随机错误也会被之后训练的 LSTM 学到,LSTM 的学习表现就是由 LDA 的序列生成质量决定的。所以联合训练的状况下可以提高 LDA 的表现,从而提高了整个模型的表现。

论文地址:http://proceedings.mlr.press/v70/zaheer17a.html 

雷锋网 AI 科技评论编译整理。

雷锋网

世界头号黑客 Kevin Mitnick 演绎了三波攻击,现场还发了500份礼物!|CSS 2017

16岁时,他仅凭一台电脑和一部调制解调器就闯入了“北美空中防务指挥部”,

此后,他经常潜入全球各大的计算机系统,查看甚至任意更改数据。

美国国防部、五角大楼、美国国家税务局、纽约花旗银行……这些美国防守最严密的网络系统都曾是他闲庭信步的地方。

他就是 Kevin Mitnick ,被称为世界头号黑客。

由于窃取国家核心机密,他受到美国联邦调查局 FBI 的通缉,并于 1995 年被逮捕,受了五年牢狱之灾。

万万没想到,现在他却是 FBI 的高级安全顾问,并开设了安全公司,摇身一变成为一个网络安全守卫者。

关于他,还有几个“传说”

传说一:美国政府曾将他单独监禁?

是的,为了防止他“作妖”。

Kevin Mitnick 上中学时就开始搞一些黑客活动。比如,人家 16 岁就跑到麦当劳把点餐机给黑了,当然,他不是为了自己免费吃汉堡,而是为了恶作剧免费让别人吃汉堡!

美国网络安全的第一个相关法律的诞生是在 1984 年,但是,早在 70 年代, Kevin Mitnick 就在法外之地从事黑客活动。

也许是养成了“感觉没被法律控制的习惯”, Kevin Mitnick 第一次被捕时,被押到了联邦法庭,当时法官旁边站着一个公诉人。公诉人说:“他对国家安全产生了非常大的威胁,我们要确保这个人他不会用到任何的电话,甚至在监狱里也不会拿到电话。”

公诉人这么说是有原因的: 当时 Kevin Mitnick 几乎无所不骗。他可诱使人们泄露各种信息,包括密码,上网帐号,技术信息等,他还窃听技术人员的电话,秘密监控政府官员的电子邮件,利用员工的人性弱点瓦解“安全长城”等。

公诉人害怕,一旦 Kevin Mitnick 接触了电话,就会利用电话拨打调制解调器的号码,发起另外一个攻击,可能会启动“第三次世界大战”。

“我在法庭上就笑了,但是法官并没有笑。后来因为这样的原因,我在监狱里面单独监禁了一年的时间。”Kevin Mitnick “无奈”地说。

传说二: Kevin Mitnick 和其团队的渗透测试成功率是 100 %

“我们能够实现百分之百的成功率。”Kevin Mitnick笃定地说,“而且是在全球范围内,如果客户要求我们做这样一个测试的话。”

“社会工程学大师”不是白叫的。

Kevin Mitnick 称,只要他们使用社会工程学,就可以让公司里的员工打开一个附件,或者是打开一个超链。他在 CSS( 第三届中国互联网安全领袖峰会) 2017 的舞台上还淡淡地举例:最近我们有位员工解密了希拉里的一封邮件。

“对于攻击者来说,实际上有一些是很容易攻击的。”他轻描淡写。

花式演绎三波入侵

第一波:攻入银行门禁

攻破监控级别严格的银行大楼?Kevin Mitnick 从吊打门禁卡开始。

首先,你要“偷”到一张门禁卡。

Kevin Mitnick 演示,他先来到金融机构大楼的某一层,在工作时间要进入到另外一个门,需要一张可以通过 HID 门禁的卡。一般情况下,攻击者只能跟着别人进去。但是,Kevin Mitnick 想到,在这一层有一个门可能不需要任何卡——卫生间!所以,他等到有人进入卫生间,利用一个设备远程偷到门禁卡的密码。

他顺便在台上宣传了一下这种设备,300美元买不了吃亏,买不了上当,这个设备只要300美元哦亲!

通过这种设备,他可以复制智能门禁卡的信息,将信息拷贝到另一张空卡中。

不过这种设备需要距离被拷贝者比较近,所以,可以选择咖啡厅、吸烟室、卫生间等场所进行拷贝,并将上述设备用皮包等物体掩饰,找机会靠近目标人物,瞬间便可以复制对方门禁卡的信息。

如果人家不让你靠近怎么办?没事,他还有另外一个装备。这种装备可以在 3 英尺外复制你的卡的信息。

最夸张的是,Kevin Mitnick 曾在一个美国会议上演示,如何用这种设备同时拷走 150 张卡的信息!

这位顶级社会工程学大师又秀了一把社工技巧:再来一个方案!

他可以伪装成要租办公楼的人,先跑到人家楼里看场地,同时用一堆问题问晕租赁人:我们有好几十人要办公呢!你看看我们5年租约的话是多少钱,10年的话能有优惠吗?

趁着人家用心地算帐,他开始耍花招了:哎哟,我们有几十个人,难道要几十把钥匙?能看看你们门禁卡吗?

然后,人家就可能晕乎乎地把卡拿给他看,他的小设备藏在兜里,随便晃一晃,信息到手。然后,他还能顺便入侵到人家大楼的数据中心。

收工,走人!

第二波:分分钟破掉笔记本电脑的密码

进入到企业以后,假如不从数据中心入侵,而是要潜入一个重要岗位员工的电脑怎么办?因为一般的电脑都会有密码保护。

Kevin Mitnick 拿出了自己的 MacBook Air ,还原了破解电脑密码的方法。

当然,这次 Kevin Mitnick 又从自己的百宝箱掏出了一个装备:又是一种类似卡的装备,直接通过 USB 接入口,盗取内存,偷取用户的密码。

“   这是有一个 USB 接入口。运行一下这个工具。可以来激活袭击,重启后,它会进行到分析程序中,之后重启,这是一个退出的机器。有时这项攻击不会成功,因为不是每次都完美。测试时可能只有一次机会,如果没有重启的话,还是需要再重新登入。”Kevin Mitnick 说。

雷锋网编辑看到,有意思的是,第一次尝试在锁屏状态下获取自己电脑的开机密码时,Kevin Mitnick 失败了。

原来,在 Kevin Mitnick 演示前,他进行了多次排练,有时在演示前没有对设备进行重启。

Kevin Mitnick 第二次尝试时,成功了,经过一些简单的操作之后,现场大屏幕上显示出了他的 MacBook Air 的开机密码。

偷偷告诉你,他的开机密码是:httpseverywhere。

不过,你知道了也没用,Kevin Mitnick 说,回去他就改密码。

第三波:现场中一下 WannaCry 病毒吧!

收到什么邮件你可能会点击邮件内的链接?“你滴鹅几在我手上”这种勒索信早就不管用了。

Kevin Mitnick 似乎能猜透人心,他给出的这版邮件内容可能会让你的电脑染上 WannaCry 病毒。

比如,对于一个新客户、新厂商,在网上有这样一些会议邀请,他们并不会怀疑这种会议邀请的真实性。所以,很简单,先创建一个会议邀请邮件。

当然,在邮件内,你还要伪造一个 Go to meeting 的网页链接,需要用户确认参加会议。

让雷锋网编辑懵逼的是,这个网页看起来没有任何问题,版面、颜色也和真正的 Go to meeting 网站一样,需要用户复制粘贴与会 ID 进行验证。事实上,这是个虚假网站,验证后网页会诱导用户运行一个程序,该程序的号称是用来确认参加会议的,但其实是一个 WannaCry 的病毒程序。

BINGO!一点击,立刻中招!

这次,没去 CSS会议现场的同学可能要伤心了:你虽然很难拿到Kevin Mitnick 的亲笔签名,但是他为在场观众准备了 500 份小礼物。据Kevin Mitnick 介绍,这个小礼物看上去是一张卡,其实是个攻击工具。

这张卡长这样:

好气,下一项议程还没开始,大家就一窝蜂地排起了长队,你看,边上挤成一堆的人就是排队的人,雷锋网编辑赶着写文章,没有拿到……嘤嘤嘤。

雷锋网

论文详解:滴滴大数据预测用户目的地,准确率超90% | KDD 2017

雷锋网 AI科技评论按:在KDD 2017中滴滴研究院副院长叶杰平所带的滴滴团队关于出租车组合优化分单模型和目的地预测的论文《A Taxi Order Dispatch Model based On Combinatorial Optimization》被收录。雷锋网将对这篇论文进行详细解读。

论文解读

相比于在搜索引擎中找到一个想要的网页,在茫茫车潮中匹配到一辆载你去目的地的车辆会更加复杂。因为网页可以持续呈现一整天,甚至半个月;但车辆是高速移动的,乘客和司机的相对位置一直在实时变动。匹配的过程和方式也极其重要,在一个既定区域,乘客有很多,车辆也有很多,系统需要全局考虑区域内的需求、供给,以毫秒级的速度进行计算,实时地进行最合理的分单,最大化用户的出行效率和出行体验。

这篇论文中介绍在滴滴出租车中使用的基于组合优化的分单模型,该模型相较于别的分单模型,整体成交率得到了提升。此外为了进一步提高用户叫车时的体验,滴滴还开发了一个目的地预测模型,能在用户打开软件时,2毫秒为用户推荐出他最可能前往的地点。目前这一功能的预测准确率已经超过90%。

1、分单时优化整体成交率

早期,出租车打车软件的订单分配主要聚焦在每个订单与每个出租车司机的相关性算法上。当一个乘客发起一单需求,系统会尽量匹配调度最近距离的司机,力图让接驾时间最短。然而此时往往会忽略到这些司机是否更适合其他订单。

此前业界曾提出过一个基于多代理体系结构的新模型NTuCab,它的目的是最小化乘客的等待时间和接驾距离。这一模型会将每个代理视为一个计算单元,它会同时计算处理N个订单和司机的匹配,但一个订单只会匹配一个出租车司机。如果一个出租车司机拒绝该订单,系统才会转发给下一司机。

然而这些方法的调度时间往往偏长,成功率较低。对此,滴滴出行提出了新的组合优化方法。在这个模型中,一个订单会播报给几个出租车司机,当多个出租车司机收到相同的订单时,最先抢单的人会获得订单。如果订单未被应答,则进入下一轮播单,直到它被出租车司机应答或被乘客取消。而模型的目标则是最大化订单成交率,从而确保司机和乘客的出行体验。实验数据也显示,这一模型下打车的全局成功率比同类模型高出了4%。

在滴滴的模型中一个主要的改进是使用“整体”的概念,即会整体考虑当前时刻所有待分配司机和订单群体的多对多的匹配问题。以成交率为优化目标,通过整体分配司机与乘客,提升乘客订单的整体成交率。

模型的数学形式即:

 

其中,max(E) 为整个模型的优化目标,即成交率;g(a)≤0 为模型必须要满足的约束条件,在这里可能是一些业务规则,比如一个司机同一时刻只能分配一个订单等;a 为模型的解,即如何对整体的订单和整体的司机进行分配。

假设当前有n个待分配订单,m 个待分配出租车司机,那么整体的待分配订单与待分配司机的匹配结果可以定义为一个m*n的矩阵A_m*n,其元素a_ij的含义如下:

 

其中,下标i代表订单,j代表司机。考虑到每个出租车司机同一时刻只能播送1个订单,那么对每个司机,也就是每个j而言,其至多只能播送n个订单中的一个,表现在矩阵中,就是对每个j的一列,至多只能出现1个“1”,其余必须全部为“0”。即:

2、Logistics Regression模型计算司机接受概率

虽然对模型的目标和求解进行了定义,但这其中,还存在一个关键因素,需要考虑司机对订单的接受意愿。司机接受订单的概率往往取决于诸多因素,如订单的价值、接驾距离、方向夹角、行驶方向等。这些信息可以编码成特征向量x_ij。

作者用p_ij表示司机dj对订单oi的接受概率,关于这个概率的计算,作者借鉴了计算广告学中CTR预估的方法,采用logistics regression模型来进行计算。

 

作者采用日志中的数据对logistics regression进行训练,以司机是否接受为y,其余特征为向量x,训练得到sigmod函数 y = 1/(1+exp(-w*x)) 中的权重向量w。将司机对订单的接受概率与模型关联起来,第i个订单的成交概率即为:

这样整个组合优化模型即为:

研究人员在北京进行了严格的AB测试,将该模型与另外两种行业普遍运用的模型进行了比较,把成交率、平均接驾时长、订单应答时长、取消率等业务关键指标作为核心评价指标。实验结果显示,该模型有更好的表现效果,订单整体的成交率提高了4%。

3、预测目的地:循环正态分布下的概率计算

在寒风凛冽的冬天,让用户哆哆嗦嗦地输入目的地,这个体验并不算好。如果能够在用户发出订单前,率先为用户推荐他最可能前往的地点,往往可以大幅减少他自行操作软件时间。

基于滴滴平台海量的历史数据,研究人员发现,人们的出行往往存在一定的规律,用户往往倾向在类似的时间到达相同的目的地;而对订单的位置进行分析,也有助于精准推荐用户的实时目的地。

基于这一观察,研究人员使用了贝叶斯公式建立用户目标的概率分布模型:


其中,T代表当前时间,D表示日期,(lat, lng)表示经纬度,{y1,y2,…,yi,…,yn}表示目的地的可能性,X表示出发地的时间和经纬度。那么剩下的问题是估计出发时间和地点 (经度和纬度)的概率分布:


而历史数据分析显示,用户目的地的出发时刻的频率直方图往往呈现如下正态分布,于是研究人员采用正态分布对出发时刻T的条件分布进行估计。但如何估计这个分布的期望和标准差,这就成为一个需要思考的问题。

考虑到时间和经纬度的分布具有周期循环性,均值和方差不能用传统方法来估计。因此研究人员使用了循环正态分布,建成一个优化模型,通过求解,得到了期望的平均值和方差。


这样整个算法的流程变为:首先根据用户的历史订单,依次计算每个目的地对应的发单时刻的期望和方差;然后根据当前时间计算每个目的地概率的中间数据;第三步用贝叶斯框架计算每个目的地的概率;最后确定阈值,满足阈值的就是研究人员要的计算结果:

Step1:根据用户订单历史,估计每个目的地的发单时刻集合的平均值和方差;

Step2:根据当前时间,计算每个目的地的P(T|X_i)和频率P(X_i);

Setp3:计算每个目的地的概率P(X_i | T )

Step4:确定支持度阈值s和概率阈值p,对满足阈值的予以首屏展示。

实验数据显示,这一预测模型明显优于基线模型,这一模型下的预估准确率达93%,较基线模型高出了4个百分点。

雷锋网注:

论文下载地址:http://www.kdd.org/kdd2017/papers/view/a-taxi-order-dispatch-model-based-on-combinatorial-optimization



雷锋网

作为KDD 2017钻石赞助商,滴滴出行会场有哪些活动?| KDD 2017

雷锋网 AI 科技评论按:就在这个周末,每年一度的数据挖掘的顶级会议ACM SIGKDD在加拿大新斯科舍省省会哈利法克斯拉开了序幕,整个会议将从13号到17号为期5天。在异国他乡的顶尖国际会议上,我们发现不仅在收录论文列表里有数不胜数的中国人的名字,甚至连赞助商都有一系列的中国公司位列前排,其中“滴滴出行”则以钻石赞助商的身份排在首要位置。这就引起了我们对滴滴在此次会议中活动的特别注意。

通过查找,雷锋网发现滴滴在这次大会中共有4个活动:

  • 14日下午13:30-14:20,在“城市计算”研讨会中,滴滴的副总裁、滴滴出行研究院副院长叶杰平将做一个关于“滴滴出行中的大数据”的受邀报告。

  • 14日晚上19:00-22:00,一个论文报告“A Taxi Order Dispatch Model based On Combinatorial Optimization”。

  • 15日中午12:30-13:30,滴滴作为钻石赞助商将会有3个展位来招人。

  • 15日下午13:30-17:00,中国专场中滴滴副总裁叶杰平也将做一次报告。

关注点一: 滴滴出行中的大数据

目前滴滴平台拥有4亿用户,日订单量超过2000万。在中国滴滴现在每天新增数据量有70TB+,每日处理数据2000TB,每日路径规划90亿+。所以滴滴平台的大数据是毋庸置疑。滴滴如何把实时的交通信息整合在一块,通过背后庞大复杂的算法和计算平台做到实时、智能的决策,这将是非常值得关注的。通过叶杰平在之前的一些演讲,我们可以发现人工智能、机器学习算法在滴滴出行的大数据处理中占据着极为重要的地位。据了解,最近滴滴更新了一版深度学习,其效果如何或许将在这次会议中对外揭晓。

 

关注点二:论文报告

作为其研究成果的论文报道也是非常值得关注的。在KDD官网上这篇论文《A Taxi Order Dispatch Model based On Combinatorial Optimization》的摘要如下:

出租车的应用程序在世界各地非常受欢迎,因为它们为用户提供了快速的响应时间和便利性。出租车预订应用程序的关键组成部分是调度系统,该系统旨在提供驾驶员和车手之间的最佳匹配。传统的调度系统依次向乘客派出出租车,其目的是最大化每个独立订单的司机接受率。但这种调度系统不能保证全局的成功率,这就会降低用户在使用应用程序时的体验。在本文中,我们提出了一个新的调度系统来优化多个订单下的出租车调度。这个系统旨在最大化全局调度的成功率,从而优化整体的交通效率,给用户带来更好的体验。为了进一步提升用户体验,我们还提出了一种在开启出租车预约APP时预测用户目的地的方法。这种方法使用了贝叶斯结构来根据他/她的旅行历史来对用户的目的地的分布进行建模。

我们使用A/B测试比较了我们新的出租车调度方法与从北京收集的数据建立的最先进的模型。实验结果表明,该方法在全局成功率(从80%增加到84%)方面优于其他最先进的模型。此外我们还对其他指标(如用户的等待时间和接收距离)进行了显著改善。我们将表明,我们的目标预测算法优于基于KNN方法的基准模型,与精度排名前三的模型相比,我们的精度提升了89%
– 93%。这种新的出租车调度和目的地预测算法已经部署在我们的在线系统中,每天为数千万用户服务。

论文下载:A Taxi Order Dispatch Model based On Combinatorial Optimization

关注点三:论文报告

此外,还有一篇入选论文《The Simpler The Better: A Unified Approach to Predicting Original Taxi Demands based on Large­Scale Online Platforms》,虽然不在滴滴的活动列表中,但有滴滴副总裁叶杰平的参与研究。摘要如下:

出租车应用程序现在越来越受欢迎,因为它们能有效地为有需要的乘客派遣空闲的出租车。为了更精确地平衡出租车的供应和需求,在线出租车平台必须预测单元出租车需求(UOTD),也即单位时间(例如每小时)、单位面积(例如每POI)发起的出租车需求数。UOTD的预测对于大型在线出租车平台来说是没有意义的,因为对它们来说精确性和灵活性是至关重要的。复杂的非线性模型(如GBRT和深度学习)通常是精确的,但在情景变化(例如新的规定导致的额外限制)后就需要大量的工作来重新设计模型了。为了精确地预测UOTD,同时保持灵活的情景变化,我们提出了LinUOTD,这是一个具有超过200万维特征的统一线性回归模型。这个简单的模型结构消除了模型重设计的需要,而且高维特征有助于精确地预测UOTD。此外,我们设计了一系列优化技术用于高效的模型训练和更新。我们使用了两个来自在线出租车平台的大型数据集进行的评估证明了LinUOTD在精确性方面优于流行的非线性模型。我们认为我们在UOTD预测中使用地高维特征的简单的线性模型可以作为一个试点研究,它可以应用到深入了解其他工业大规模时空预测的问题当中。

论文下载:The Simpler The Better: A Unified Approach to Predicting Original Taxi Demands based on Large­Scale Online Platforms

滴滴研究院成立于2016年4月,其中人工智能科学家何晓飞教授任首届院长。目前其研究项目包括ETA、动态调价、智能分单、拼车、供需预测、运力调度、热力图等核心项目,研究方向则包括机器学习、计算机视觉、人工智能、数据挖掘、最优化理论、分布式计算等。

在今年3月滴滴出行又宣布在美国加州硅谷成立滴滴美国研究院,把挖人的触角直接伸到了美国硅谷。如果细心,你会发现原来去年SIGKDD的钻石赞助商也是滴滴出行,而微软、亚马逊这些科技巨头则只能位居铂金赞助商行列。从2012年微不足道,短短五年,就能与巨人并肩,其成长不可谓不迅猛,其背后有着怎样的艰辛或许只有DiDier们自己知道。

SIGKDD 2017大会将有哪些精彩呈现,雷锋网AI科技评论将从一线带来精彩报道及内容。


雷锋网

KDD 2017现场探营:务实、丰富,数据大爆炸的盛会即将开启 | KDD 2017

ACM SIGKDD(国际数据挖掘与知识发现大会,Conference on Knowledge Discovery and Data Mining,简称KDD大会)是世界数据挖掘领域的最高级别的国际会议,由ACM(Association of Computing Machinery,计算机学会)的数据挖掘及知识发现专委会(SIGKDD)负责协调筹办。随着大数据时代的到来,KDD大会影响力也与日俱增,为领域研究成果的展示和实践经验的交流提供了一个理想的平台。2017年8月13-17日,第23届KDD大会将在加拿大哈利法克斯举行,雷锋网记者也已赶到哈利法克斯,为大家带来KDD大会的最新报道。

哈利法克斯是加拿大新斯科舍省的省会和北部最大的深水天然港口,哈利法克斯的附近海域也是当年泰坦尼克号沉没的最后归宿。在KDD大会举办以来的23年中,这是KDD第四次离开美国(前三次分别是2009年巴黎,2012年北京,2015年悉尼)。本次大会会场World Trade and Convention Centre & Scotiabank Centre与哈利法克斯的标志性建筑钟楼和八角星形要塞(Halifax Citadel)相邻,风景优美。

(会场附近航拍图,图片来自KDD官网)

按照议程,大会从8月13日开始,8月12日下午4点起开放注册。当雷锋网下午3:45赶到会场时,被告知注册尚未正式开始;4点一到,注册台前迅速汇集起了不少提早赶来的参会者:

在注册处入口的宣传板上我们可以看到KDD 2017大会的赞助商名单,共有3家中国公司赞助了大会:滴滴出行(钻石赞助商)、阿里巴巴集团(白金赞助商+KDD CUP赞助商)、华为(铜牌赞助商)。这三家公司在KDD上均有论文发表,其中阿里巴巴(包含阿里巴巴集团、蚂蚁金服等)共有5篇论文;

与许多类似学术会议一样,大会也为赞助商提供了展区。KDD 2017展区位于World Trade and Convention Centre三楼,目前暂时并不允许参观者进入;而在一楼和二楼有诸多举办Tutorial和Workshop的中小会议室已经布置完毕,等待明天日程的展开。

(Room 200,明天将举办Tutorial的场地之一,有192个座位)

按大会日程,KDD共有3场大会报告(Keynote)演讲,11场应用数据特邀演讲(Applied Data Science Invited Talk),10个半天Workshop和10个全天Workshop,22场Coventional Tutorial和8场Hands-on Tutorial。从议程设计看,相比起去年的KDD大会,Workshop和Tutorial的数量均有较大增加(去年包括6场全天Workshop、10场半天Workshop、12场Tutorial和8场Hands-on torial),表明在数据研究领域的研究内容更加细分和具体化。

与2016年相比,大会的另一变化是来自工业界及应用学术研究领域的投稿数量继续增加。从2016年起,应用数据科学专题开始接受学术界论文投稿,使得当年的应用数据科学专题投稿论文增长近100%到331篇,最终录用66篇,第一次使得应用数据科学专题论文占到了录用论文的30%以上;而KDD2017年共收录研究专题投稿论文录用130篇,其中64篇Oral,66篇Poster;应用数据科学专题录用86篇,其中36篇Oral,50篇Poster,应用数据科学专题文章占到了40%。这也反映KDD作为一个学术会议务实主义的一面,在会议组织者看来,如何系统地解决现实工业界中的实际问题是值得大会关注的重点内容之一。

据雷锋网统计,在所有216篇录用论文中,包含来自中国大陆的作者的文章为31篇,占到所有文章的15%。在现场我们看到,由于路途遥远,不少中国参会者均选择13获14日赶到哈利法克斯,现场的中国人并不多,预计在明后两天,随着国内大部队的到来,哈利法克斯也将会卷起一股数据挖掘的“中国旋风”。

Tips:

  • 本次大会举办地哈利法克斯国际航班直达城市(机场)包括:伦敦、法兰克福、格拉斯哥、慕尼黑、都柏林、巴黎、雷克雅未克、波士顿、纽约、纽瓦克。中国参会者一般在美国三个机场波士顿、纽约、纽瓦克转机;

  • 机场到哈利法克斯市区约40公里,出租车约60加币+消费(可刷卡),耗时30分钟;机场大巴22加币/人,耗时约一小时;

  • 哈利法克斯人口约40万,由于大会举办,会场附近酒店已告罄。哈利法克斯拥有较完善的公共交通,如参会者住宿离会场较远,也可考虑通过公共交通前往会场,单程车票为2.50加币(只接受硬币),也可在连锁药店Shoppers Drug Mart刷卡购买公交车票,价格为20加币/10张;

  • 哈利法克斯气候宜人,气温最高的七月平均气温为19.1 °C,相比起美国大多数城市,治安好,民风淳朴,2011年,被FDI 杂志评为“北美生活品质之城”第一名,而且盛产海鲜,来哈利法克斯参会的同学一定不要错过。

雷锋网

SIGKDD明日召开,重点内容全概览|KDD 2017

ACM SIGKDD 2017(知识发现与数据挖掘会议)于 8 月 13 日至 17 日在加拿大哈利法克斯正式召开。雷锋网AI科技评论将从一线带来精彩报道及内容。

会议前一天下午,雷锋网AI科技评论来到现场签到时,发现主要的指示标志和前台接待设施已经布展完毕,也有不少与会人士陆续到现场签到。

大会主席 Stan Matwin 、Yu Shipeng 及副主席 Faisal Farooq 分享了本次大会的一些感想:

「我们希望 KDD 2017 能够让您了解新的技术趋势,从论文(包括 poster 及口头展示)中得到启示并在专业领域有所助益,发现新的工具、研究流程及实践工作;确定新的工作机会或是招聘到心仪的人选。」

「数据科学」、「数据挖掘」和「大数据」,在过去几年中已经从研究实验室走出,并出现于你我的日常生活中,甚至也出现在媒体领域和各级政府和企业的决策中。这些技术的影响涉及到每一个人。更重要的是,目前数据科学的快速发展得到了极大的推动——包括工业界人士及学术界人士。在过去,这些人一直是 KDD 会议的一道风景线,他们是理论与实践的桥梁,是双界交流的促进者和催化剂。在会议上,包括研究、应用数据科学及应用演讲嘉宾等三个平行议程将会同期展开,将工业界与学术界人士紧密联结在一起。

而这也正是 KDD 2017 的议程所具备的。雷锋网了解议程后发现,延续往年的惯例,KDD 将非常大的比重留给了 tutorial 和 workshop 环节(第一天和第二天)。22 个各具特色的 tutorial 将从深度学习、数据挖掘、IOT 实战应用等不同方面提供前沿观点,此外还将穿插 8 个半天的 hands-on tutorial;而 22 个 workshop 则将在第二天进行;正会则要等到第三天才开始。

Keynote内容及讲者介绍

每年会议的Keynote自然是最重要的一个部分,KDD邀请了三个 Keynote 嘉宾,分别从数据挖掘的不同角度分享了工业界和学术界的前沿和未来:

  • Cynthia Dwork,微软研究员杰出科学家/哈佛大学:《何谓公平?》

数据,算法和系统中都嵌入了偏见,它反映了设计师的明显和隐藏的选择,历史偏见和社会的优先等级。 它们在字面上就不可避免地形成了价值观的整理。 算法的“不公平”,例如从广告到再犯预测的不同任务,已经在大众媒体中引起了相当的关注。 这次演讲将讨论针对初期的数学严谨的分类和评分的公平性研究。

微软研究的杰出科学家Cynthia Dwork以数学严谨的基础为隐私保护数据分析而闻名。 这项工作的基石是差异隐私,强大的隐私保证通常可以获得高度准确的数据分析。 Dwork还在加密和分布式计算方面做出了突出贡献。 她是美国国家科学院和美国国家工程学院的成员,也是美国艺术与科学学院院士,美国哲学社会学者。 从2017年1月开始,Dwork将是哈佛保尔森工程学院计算机科学系的Gordon McKay教授,拉德克利夫高级研究所的Radcliffe Alumnae教授,以及哈佛法学院的教授。

  • Bin Yu,UC 伯克利大学教授:《数据科学的三原则:可预测性、稳定性与计算性》

在这个演讲中,我将讨论数据科学的三个原则在数据驱动决策中的重要性和联系。预测的最终重要性在于,未来是所有人类在商业,教育,研究和政府方面任何活动的独特而且可能是唯一的目的。机器学习以预测为中心,以计算为核心,已经实现了广泛的数据驱动方面的成功。预测是检查现实的有用途径。良好的预测暗示着过去和未来之间的稳定发展。稳定性(相对于数据和模型扰动)也是数据驱动结果的可解释性和可重复性的最低要求。它与不确定性评估密切相关。显然,如果在没有可行的计算算法的条件下,是不能采用预测和稳定性的原理,因此可见可计算性的重要性。这三个原则将由分析联系来表明,同时两个正在进行的项目中证明,“数据智慧”也是不可或缺的。具体来说,第一个项目采用深度学习网络(CNN)来了解难辨视觉皮层V4中神经元的模式选择性;第二个项目通过采用和比较不同潜变量模型和基于拉索的模型来预测政治电视广告的党派和语气。

Bin Yu是加州大学伯克利分校的统计学和电气工程与计算机科学系的校长教授,也是伯克利统计局前任主席。她是北大统计与信息技术大学微软联合实验室的创始人之一。她与基因组学,神经科学和医学科学家进行跨学科研究。为了解决这些领域的数据问题,她开发了统计学和机器学习方法/算法和理论,并结合领域知识和定量批判性思维进行整合。Bin Yu是美国国家科学院院士,美国艺术与科学学院研究员。她是2006年的古根海姆研究员,2011年ICIAM的邀请演讲人,2012年伯努利社会的图基纪念讲师,以及2016年立陶宛数学统计研究所讲师。她在2013 – 2014年担任IMS总裁,并且是IMS,ASA,AAAS和IEEE的研究员。

  • Renee J Miller,多伦多大学教授:《数据集成的未来》

数据集成时的形成的数据爆炸的价值。 在这次演讲中,我提出过去二十年来数据整合方面的一些重要创新。 这其中包括数据交换,其为推理转换数据的正确性以及在集成中使用声明映射提供了基础。 我还讨论了数据挖掘如何用于促进数据集成,并呈现数据科学中出现的一些重要的新数据集成方面的挑战。

RenéeJ. Miller是多伦多大学计算机科学系教授,加拿大贝尔信息系统主席。她是加拿大皇家学会,加拿大国家学院院士,ACM研究员。她获得了美国科学家和工程师的总统早期职业奖(PECASE),这是美国政府颁发的优秀科学家和工程师从事职业生涯的最高荣誉。她获得NSF职业荣誉奖,总理研究优秀奖和IBM教授奖。她的研究主要在数据集成和数据管理领域。她和共同作者因为2003年颇有影响力的建立了数据交换的基础的文章而获得了ICDT测试时间奖。她曾担任VLDB基金会董事会成员,并担任捐赠基金会主席。她的研究由NSERC,NSF,IBM,SAP和Bell Canada等资助。她从威斯康星大学麦迪逊分校获得计算机科学博士学位,并获得麻省理工学院数学和认知科学学士学位。

此外,有 11 位专家及教授将从应用数据科学的角度阐述他们在数据科学领域的研究心得,名单如下:

投稿结果

而至于一直以低收录率闻名的KDD,今年的投稿结果如何呢?官方统计数据如下:

今年的 KDD 研究领域的审核总论文数为 748 篇,收录 130 篇,包括 64 篇 oral,66 篇 poster,录用率分别占 8.6% 及 8.8%。

而应用数据科学领域共审核 390 篇论文,收录 86 篇,包括 36 篇 oral,50 篇 poster,录用率分别占 9.2% 和 12.6%。

论文详细收录名单如下:http://www.kdd.org/kdd2017/accepted-papers

赞助商一览

钻石赞助商:滴滴;

顶级赞助商:亚马逊、微软、阿里巴巴、facebook;

金牌赞助商:SAS、Captial One;

银牌赞助商:Criteo Research、谷歌、Element AI、西门子、Linkedin

铜牌赞助商:华为、Booking.com、Honenywell、American Express、Oracle、Western Digital。

其他赞助商详见官网页面:http://www.kdd.org/kdd2017/sponsorship

值得一提的是,为了让更多的学生和初创企业能够减轻经济负担来到现场,KDD 2017 提供了 14.5 万美元学生差旅经费和 25 万美金的初创企业经费。「我们希望 KDD 2017」将会成为能让研究者、实践者、投资者的聚集之地,创造出更多创新算法及商业化的产品。」

非常期待明天即将开始的KDD 2017,雷锋网AI科技评论也将从前线带来更多消息。

雷锋网

中科院计算所王永庆详解IJCAI 17录用论文:如何用注意力机制RNN进行信息传播建模?|IJCAI 2017

雷锋网AI科技评论:IJCAI 2017即将举行,为此,雷锋网特邀请了部分录用论文作者对自己的作品进行详细解读,以供有兴趣的老师同学们了解作者的研究思路。本文原载于王永庆个人公众号“KingsGarden”,授权雷锋网转载,雷锋网AI科技评论做了不改变原意的编辑。

另外,雷锋网即将在 8 月 12 日下午举行“GAIR大讲堂CVPR 上海交大专场”分享会,感兴趣的同学赶紧点击此链接了解活动详情。


王永庆,2017年中国科学院计算技术研究所工学博士毕业,现就职中国科学院计算技术研究所,任助理研究员。研究方向: 信息传播,社会计算,数据挖掘和机器学习。

论文题目:Cascade Dynamics Modeling with Attention-based Recurrent Neural Network

作者: Yongqing Wang, Huawei Shen, Shenghua Liu, Jinhua Gao and Xueqi Cheng

背景介绍

这篇文章是我们今年投稿于IJCAI并录用的文章,文章的背景是信息传播建模(Cascade Dynamics Modeling),切入点是如何将结构信息融合到序列建模(Sequence Modeling)中。

简单介绍下序列建模,这是一种挖掘序列内关联模式的技术手段,这种关联模式又可按序列内前后两元素间间距是否等长对应到两类具体的问题中:离散序列和时序序列建模。例如离散马尔科夫模型,连续时间马尔科夫模型等都是经典的序列建模模型。当然,这几年来受到神经网络的冲击,利用循环神经网络(RNN)处理序列建模问题也逐渐成为了这一领域的标杆。

为了能够产生迭代,提高序列建模的效率,一般认为,序列内部各元素的间的关系是顺序传递的。大家可以细想一下基于这种假设下序列建模所存在的问题:无法处理序列内各元素的结构信息。图1展示了传统序列建模中的这种假设与真实情况的矛盾。考虑结构信息后图1(a)中的事件(u3,t3)、(u4,t4)节点均不再顺序依赖于其前一个节点,如果继续采用传统序列建模的方式,那么建模势必会存在一定的偏差。在这里,我们将其称为序列建模中的跳跃依赖(Cross-dependence)问题。那么如何有效解决这一问题呢?

                                              

(a)    传统序列建模的传递依赖关系


(b)    考虑元素间结构信息后与传统序列建模假设的矛盾

图 1 传统序列建模假设与真实情况的矛盾

动机

让我们先来思考一下解决跳跃依赖问题的关键:如何在序列建模过程中加入对结构信息的考虑。但这种尝试至今没有真正成功过。例如,让我们来考虑下图1(a)中u4节点的可能依赖结构,一共存在∅, {u1}, {u2}, {u3}, {u1, u2}, {u1, u2}, {u1, u3}, {u2, u3}, {u1, u2, u3}这9种可能情况。假设目标节点的可能依赖节点数为K,那么这种可能的依赖结构一共是2K+1种。考虑结构信息后,会使得序列建模的计算复杂度呈几何级提升,而过大的计算开销又不会给最终的计算结果带来可观的效果提升。

那么是否存在一种既不会带来过多的计算开销,又能同时解决跳跃依赖问题的方法呢?有!我们提出了一种在循环神经网络框架下考虑序列中结构信息的建模方式—CYAN-RNN(Cascade dYnamics modeling with AttentioN based RNN)。简单介绍下循环神经网络:在循环神经网络中,序列元素顺序输入,通过激活函数变换成为对应输入的表示,并用于生成序列。一般地,我们认为所得的表示信息是对序列中对应输入的一种合理抽象。例如,在语言模型中,以单词作为输入,所得的即为单词语义的一种抽象。在信息传播中,以用户行为作为输入,所得的即为用户行为的一种合理抽象。那么如果我们将这些表示进行综合,共同作用于同一任务,所谓的结构,是否可以理解为当前任务对这些抽象表示的利用程度呢?

模型

基于上述的讨论,我们基本确定了一条解题思路:将当前所有可用的表示进行综合,通过对当前任务的理解,删选出合适的信息,并推理出可能的依赖结构。

图2给出了在RNN框架下综合所有可用表示进行序列建模的示意图。在考虑计算效率和有效性的前提下,我们决定采用注意力机制(Attention Mechanism)来实现这一架构。

  • 一方面因为注意力机制的实现及计算效率很高;

  • 另一方面,注意力机制也是目前在多个不同应用上被证明为能够较好地学习结构信息的一种机制。

图3给出了文中所实现的带注意力机制的循环神经网络结构图。注意力机制的关键是学习获得了注意力向量α。我们约束了向量中的所有元素之和∑i αi=1,这样所学得的注意力可用于表示对应表示的权重信息,进而反应可能的依赖结构。图3中的具体实现里还给出了一种基于覆盖机制(Coverage Mechanism)的架构图。这是考虑到在对序列顺序建模的过程中,可能会有部分的表示信息会被重复使用多次,进而忽略了序列中的其他表示信息。而覆盖机制在原有的注意力机制上额外添加了记忆信息,增加信息被重复使用的代价,进而在建模过程中提升所有表示信息的使用覆盖度。


图 2 在RNN框架下综合所有可用表示来做序列产生过程建模

 


图 3 CYAN-RNN的具体实现架构

实验结果

在实验部分我们列举三组实验用以表示CYAN-RNN框架的有效性。

  • 实验一:传播预测(预测下一激活用户和激活时间)

这组是标准的序列生成效果实验。输入为观测信息的传播记录,要求序列建模模型能够准确的还原观测信息。从图4的实验结果上来看,可以发现:CYAN-RNN在传播预测的实验效果上显著优于其他所有的对比方法。值得注意的是,在图4所示左部预测下一激活用户的任务上,传统的RNN模型(RMTPP)并不比一些简单的模型(不采用神经网络方式建模)效果要好(对比CT Bern和CT Jac),而引入结构信息的CYAN-RNN则对比传统方法在实验效果存在显著提升。

 


图 4 传播预测结果

  • 实验二:注意力机制和覆盖机制中的权值分配对比

这一部分实验主要用来验证覆盖机制中所添加的记忆信息是否能够有效提升所有表示信息的使用覆盖度。根据图5的实验结果对比可以发现,由于记忆信息的引入,在覆盖机制中(图5右)中的权值分配相较于注意力机制中(图5左)的权值分配更倾向于新出现的表示信息,因而所计算的权值也能够更为清晰的表示结构信息。

 


图 5 注意力机制和覆盖机制中的权值分配对比

  • 实验三:网络推断

这组实验主要用来验证我们从解题之初就存在的一个疑问:是否引入注意力和覆盖机制的循环神经网络架构就是对依赖结构的一种刻画呢?由于观测信息的产生过程限制我们很难精确到刻画具体的依赖关系,但我们可以利用推断所得的依赖结构去反推物理的关系网络结构,进而回答这一问题。

我们把从注意力机制和覆盖机制中学习所得的权重信息进行综合、删选,用于网络推断,并将错误的推断结果以红线标注于图6中。可以发现,无论是采用注意力机制的CYAN-RNN还是采用覆盖机制的CYAN-RNN(cov),其对关系网络的推断均存在一定的有效性,如此回答了我们这一疑问:注意力机制和覆盖机制能够刻画序列产生过程中的依赖结构。

 


图 6 网络推断结果

总结:这篇文章虽是以信息传播为背景的序列建模,但所提的跳跃依赖问题却普遍存在于序列建模的众多场景之中。在诸如语言模型的相关文中,我也有过一些尝试,发现这种采用注意力机制和覆盖机制的方式也同样有效。因此,读者若是有兴趣,可以到我的github上下载源码并在相关领域进行尝试:https://github.com/Allen517/cyanrnn_project。

另外,本工作的演示代码(IPython)详见: http://yongqwang.com/public/res_dat/UAI_demo.tar.gz 

雷锋网