业界 | 一文看懂谷歌 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 条评论
登录 后参与评论

相关文章

来自专栏视频咖

极速高清——给你带来全新的高清视野

很生气!!!我才刚落地,就因游戏界面糊了一下,阻止了我捡枪的步伐,就被不知道从哪蹿出来的家伙给打死了!!!瞬间落地成盒!!!

2333
来自专栏EAWorld

边缘计算与云计算的未来

Edge Computing and the Future of the Cloud

1434
来自专栏新智元

【CVPR智慧城市挑战赛】无监督交通异常检测,冠军团队技术分享

【新智元导读】“智能交通视频分析界的ImageNet竞赛”——英伟达城市挑战赛落下帷幕。新加坡松下研究院联合中科院自动化所,提出了一种双模态动静联合检测方案,在...

900
来自专栏人工智能快报

科学家研制出基于自旋电子的人工智能

日本东北大学(Tohoku University)的研究人员首次成功的演示了基于自旋电子的人工智能。 人工智能模拟了大脑快速执行复合任务和复杂任务(例如图像识别...

34310
来自专栏AI科技评论

专访FPGA 2017最佳论文得主深鉴科技: 深度学习的最大瓶颈是带宽问题而非计算

AI科技评论按:近日,深鉴科技的 ESE 语音识别引擎的论文在 FPGA 2017 获得了唯一的最佳论文 ESE: Efficient Speech Recog...

3119
来自专栏量子位

IBM实现了创纪录的深度学习性能:完败Facebook微软

陈桦 编译整理 量子位 出品 | 公众号 QbitAI 昨晚,外媒都在用夸张的标题报道IBM的人工智能又立功了,例如说IBM的速度快得很“抓马”云云。到底怎么回...

2833
来自专栏钱曙光的专栏

AI 重新定义 Web 安全

目前近 90% 的企业都已经开始使用云计算(包括公有云、私有云等),这说明大规模云化对于企业而言已经不只是趋势,更是确凿的既成事实,云化普及的同时也给安全带来很...

3620
来自专栏人工智能头条

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

2287
来自专栏专知

ACL 2018教程:关于语义和语用的100件事(附下载)

【导读】近日,ACL 2018 在澳大利亚墨尔本举办,举办地点为墨尔本会展中心。其tutorial 旨在帮助领域新手了解计算机语言学与自然语言处理的最新进展以及...

850
来自专栏安恒信息

安恒信息两篇核心AI异常检测论文入选IEEE DSC国际会议

6月18日-21日,“第三届IEEE网络空间数据科学国际会议”在广州召开。业界代表及专家齐聚一堂,并就网络空间数据科学的科研和前沿发展方向进行交流。而安恒信息的...

1254

扫码关注云+社区