业界 | 一文看懂谷歌 NYC 算法与优化业务全景(附重点论文下载)

AI 科技评论消息,众所周知,谷歌的研究团队遍布世界各地,而纽约自然也是非常重要的一个地点,尤其是多个谷歌算法研究小组的孕育地。目前,谷歌算法优化团队为谷歌产品的顺利诞生提供了非常多的算法支持,解决了诸多挑战,包括基础优化、隐私保护、提升好友推荐度等多重挑战。

为了让大家更能第一时间了解到谷歌算法及优化的最新进展,谷歌研究院博客于今天更新了消息,谷歌 NYC 算法优化团队公布了主页。而从这个主页中,AI 科技评论也将和大家一窥谷歌算法优化团队的全貌。

目前,团队与谷歌内部的多个团队有着紧密联系,包括广告、搜索、YouTube、Play、基础架构、地理、社交、图像搜索与云服务等,并针对包括机器学习、分布式优化、经济、数据挖掘及数据驱动优化等多个研究领域进行研究。

算法优化与产品技术是紧密结合的,因此也存在诸多的交叉,NYC 算法优化团队的产品经理 Vahab Mirrokni 在更新的博客中指出,网站将从大规模图形挖掘、大规模优化及市场算法等三个子领域进行覆盖,涉及长短期的基础研究及应用研究。

大规模图形挖掘

这一项目组负责为图形算法及分析构建最大规模的数据库,并应用于大量的谷歌产品中。通过数据挖掘及机器学习等方法,研究者将解决图形算法问题,并在顶级期刊或会议上引领基础研究成果。

目前这一项目组有四个子任务,包括:

  • 大规模相似性排序(Large-scale Similarity Ranking):在 WWW、ICML、VLDB 等顶级期刊/会议上,团队目前基于相似性排序已经提出了一些行之有效的方法,包括 ego-networks和在大规模多分类二分图中计算相似性排名等。 相关论文: Improved Friend Suggestion using Ego-Net Analysis,VLDB 2016. 论文地址:https://research.google.com/pubs/pub44265.html Reduce and aggregate: similarity ranking in multi-categorical bipartite graphs,WWW 2014. 论文地址:https://research.google.com/pubs/pub42479.html
  • 分区平衡(Balanced Partitioning):对于大规模图形优化问题而言,分区平衡自然是首要的难题。而在去年 WSDM 2016 上,谷歌所投递的一篇名为《Distributed Balanced Partitioning via Linear Embedding》的论文比起目前最顶尖算法实现了 15%-25% 的分区尺寸缩减。 相关论文: Distributed Balanced Partitioning via Linear Embedding,WSDM 2016 论文地址:https://research.google.com/pubs/pub44315.html
  • 集群与连接组件(Clustering and Connected Components):谷歌团队表示他们目前已经拥有包括分层聚类,重叠聚类,局部聚类,频谱聚类和连通分量等多种顶尖的应用算法,与此同时,算法比以前研究的最佳算法快 10 到 30 倍,且能够扩展到数十亿图形中。 相关论文: A Local Algorithm for Finding Well-Connected Clusters,ICML 2013 论文地址:https://research.google.com/pubs/pub41596.html Connected Components in MapReduce and Beyond,SOCC 2014 论文地址:https://research.google.com/pubs/pub43122.html
  • 公有/私有图形计算化(Public-private Graph Computation):谷歌在基于个人隐私数据的保护上,对创新模型颇有研究。 相关论文: Efficient Algorithms for Public-Private Social Networks,KDD 2015 论文地址:http://dl.acm.org/citation.cfm?doid=2783258.2783354

大规模优化

这一项目组旨在开发大规模优化技术,并且提升谷歌基础技术的效率与鲁棒性。谷歌目前将这一技术广泛应用于组合优化、在线算法及控制理论等领域,使谷歌得以在大范围计算化基础设施上达成最高的投入产出比。不论是离线或是在线优化,该项目组都秉承增加吞吐量、减少延迟、最大限度地减少资源挤占、最大化高速缓存,并尽可能减少分布式系统中的冗余工作。核心产品包括:

  • 一致性哈希(Consistent Hashing):谷歌设计了一种无记忆平衡分配算法,能够将动态客户端集合分配给动态服务器集合,使得每个服务器的负载是有界的(bounded),并且每次更新操作的分配不致变化太大。这种技术目前能够用于解决包括 Google Cloud Pub / Sub 的内部项目,及开源的 haproxy 等外部项目。 相关论文: Consistent Hashing with Bounded Loads,CoRR 2016 论文地址:https://research.google.com/pubs/pub45756.html
  • 基于核心集的分布式优化(Distributed Optimization Based on Core-sets):可组合的核心集提供了解决大规模数据集优化问题的有效方法,此外,该技术可用于分布式均衡聚类和分布式子模块最大化等问题。 相关论文: Composable core-sets for diversity and coverage maximization,PODS 2014 论文地址:https://research.google.com/pubs/pub44219.html Distributed Balanced Clustering via Mapping Coresets,NIPS 2014 论文地址:https://research.google.com/pubs/pub42964.html Randomized Composable Core-sets for Distributed Submodular Maximization,STOC 2015 论文地址:https://research.google.com/pubs/pub44222.html
  • 谷歌搜索基础架构优化(Google Search Infrastructure Optimization):算法优化团队通过与谷歌搜索基础架构团队,构建分布式反馈控制循环。此外,团队还通过增加任意单机的机器查询流,以提升缓存效率。

市场算法(Market Algorithms)

这一项目组对谷歌的整体市场进行分析和设计,并从经济和计算两方面有效提升谷歌业务。所做的研究主要包括优化 DoubleClick 的展示广告,以及赞助的搜索及移动广告。

在过去的几年内,该项目组主要涵盖的业务如下:

  • 展示广告研究(Display Ads Research):展示广告生态系统为在线随机优化和计算经济学中的各种研究问题提供了绝佳的平台,如全页优化和最优契约设计。这个研究领域的重要组成部分还包括广告交易的竞价优化,通过处理中介参与的竞价活动,优化定价策略,实现预订契约和广告交易的最佳收益管理。 相关论文: Whole-page optimization and submodular welfare maximization with online bidders,ACM Conference on Electronic Commerce (EC) 2013 论文地址:https://research.google.com/pubs/pub41755.html Auctions with intermediaries: extended abstract,ACM Conference on Electronic Commerce (EC) 2010 论文地址:https://research.google.com/pubs/pub36634.html Yield Optimization of Display Advertising with Ad Exchange,ACM Conference on Electronic Commerce (EC) 2011 论文地址:https://research.google.com/pubs/pub36975.html
  • 在线随机匹配(Online Stochastic Matching):团队已经开发各类新算法,用于在线随机匹配、预算分配及处理流量高峰等任务,此外还包括名为「子模块福利最大化」的通用性问题。 相关论文: Online Stochastic Matching: Beating 1-1/e,FOCS 2009 论文地址:https://research.google.com/pubs/pub35487.html Simultaneous Approximations for Adversarial and Stochastic Online Budgeted Allocation,ACM SIAM 2012 论文地址:https://research.google.com/pubs/pub37475.html Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models,EC 2015 论文地址:https://research.google.com/pubs/pub44231.html Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order,STOC 2015 论文地址:https://research.google.com/pubs/pub44224.html
  • 鲁棒随机分配(Robust Stochastic Allocation):在一篇名为《Simultaneous Approximations for Adversarial and Stochastic Online Budgeted Allocation》的论文中,研究者探究了能在对抗和随机到达模型中实现良好性能的在线算法。在另一篇论文《Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models》中,团队开发了一个混合模型和算法,其近似因子能够随着预测的准确性而变化。 Simultaneous Approximations for Adversarial and Stochastic Online Budgeted Allocation,ACM/SIAM 2012 论文地址:https://research.google.com/pubs/pub37475.html Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models,EC 2015 论文地址:https://research.google.com/pubs/pub44231.html
  • 优化广告客户活动(Optimizing Advertiser Campaigns):团队对算法问题进行研究,包括积极结转效应,基于搜索竞价的预算优化,以及具有多个预算限制的简要出价优化策略。 相关论文: Budget Optimization for Online Campaigns with Positive Carryover Effects,WINE 2012 论文地址:https://research.google.com/pubs/pub40688.html Budget Optimization in Search-Based Advertising Auctions,ACM Conference on Electronic Commerce 2007 论文地址:https://research.google.com/pubs/pub32834.html Concise Bid Optimization Strategies with Multiple Budget Constraints,WINE 2014 论文地址:https://research.google.com/pubs/pub42963.html
  • 动态机制设计(Dynamic Mechanism Design):团队已经开发有效机制用于互联网广告中的复杂设置,包括在线设置和多面体约束。此外,研究者还设计了一个新的动态机制系列,称为银行账户机制(bank account mechanisms),在设计非 CLairvoyant 动态机制上具有有效性,适用于不依赖预测未来步骤的情况。 相关论文: Dynamic Auctions with Bank Accounts,IJCAI 2016 论文地址:https://research.google.com/pubs/pub45750.html Oblivious Dynamic Mechanism Design,SSRN 2016 论文地址:https://research.google.com/pubs/pub45751.html

官网页面:https://research.googleblog.com/

AI 科技评论小结:NYC 算法及优化团队存在已久,但由于其具有交叉性性强、基础研究明显等多种特点,一直没有一个「主阵营」能够为算法及优化团队提供分享最新研究成果的平台。而在包括谷歌大脑团队、自然语言理解团队、欧洲研究团队、安全隐私团队等诸多团队都建立自己的博客和子站后,NYC 算法及优化团队于近日公布的网站主页,自然能够更好地从全局让大家了解谷歌算法优化的过往和未来,并且从这一研究组的系统整理中得到做研究的启迪。

原文发布于微信公众号 - AI科技评论(aitechtalk)

原文发表时间:2017-08-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

资源 | 《Deep Learning》中文印前版开放下载,让我们向译者致敬

选自GitHub 机器之心整理 参与:蒋思源 《Deep Learning》中文版(印前版)正式发布。这本书适合于各类读者,尤其是学习机器学习的本科或研究生、深...

3737
来自专栏AI科技大本营的专栏

实战干货 | 这位成功转型机器学习的老炮,想把他多年的经验分享给你

这个年代,不怕你是大牛,就怕大牛还会写文章。 作为AI100智库专家,智亮总是能在口若悬河中,让人深入浅出地学到一堆堆干货,掏心窝子的干货。 多年的实战经验...

38910
来自专栏CVer

免费资源 | 机器学习 新手快速入门

昨天正式开启了CVer免费赠书:送7本实体书(包邮) 活动,其中、有 4种赠书方式,Amusi也觉得赠的书不多,反而赠书方式多了,甚至觉得自己往营销方面跑了。因...

2062
来自专栏机器之心

17岁高中生都发AI论文了!OpenAI实习生提出分层强化学习新算法

38712
来自专栏ATYUN订阅号

Nvidia用合成数据集训练机器人拾取物体,胜过用真实数据训练的机器人

Nvidia的研究人员已经找到了一种方法,可以使用在虚拟环境中创建的数据来训练机器人在现实世界中拾取物体。用合成数据训练的卷积神经网络系统可以使用Baxter机...

862
来自专栏AI科技评论

开发 | 分布式机器学习时代即将来临?谷歌推出“Federated Learning”

传统机器学习方法,需要把训练数据集中于某一台机器或是单个数据中心里。谷歌等云服务巨头还建设了规模庞大的云计算基础设施,来对数据进行处理。现在,为利用移动设备上的...

40310
来自专栏人工智能头条

聊天机器人中的深度学习技术(引言)

2497
来自专栏人人都是极客

AI 芯片和传统芯片的区别

比如,自动驾驶需要识别道路行人红绿灯等状况,但是如果是当前的CPU去算,那么估计车翻到河里了还没发现前方是河,这是速度慢,时间就是生命。如果用GPU,的确速度要...

1123
来自专栏大数据文摘

【译】统计学教会我们的10件事

1979
来自专栏机器之心

前沿 | 硼酸钡钠,一种因机器学习而诞生的LED荧光粉

10 月 22 日,化学系助理教授 Jakoah Brgoch 及其实验室成员在 Nature Communications 期刊上发表了关于该研究的论文。

1071

扫码关注云+社区