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

相关文章

来自专栏CreateAMind

软件2.0-Andrej Karpathy

https://medium.com/@karpathy/software-2-0-a64152b37c35

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

如何将深度学习与你正在做的事情相结合?

作者 | 李嘉璇 文章来源Gitchat,AI科技大本营合作发布,点击「阅读原文」查看交流实录 前言 人工智能是目前各行各业最火热的技术,如果说前两年是『互联...

32811
来自专栏AI科技评论

专访蓝光辉教授:在随机优化算法的世界里徜徉

AI 科技评论按:在大规模机器学习问题的求解中,随机优化算法占据着不可替代的地位。大数据在提供海量信息的同时,也暴露了传统计算方法效率低的问题。举例来说,从最初...

1083
来自专栏人工智能的秘密

人工智能芯片是什么?有什么用?

2018年1月9日,全球规模最大的2018北美消费电子产品展在美国拉斯维加斯拉开帷幕。本次参展的科技企业超过4000家,包括高通、英伟达、英特尔、L...

2267
来自专栏AI科技评论

业界 | 英伟达的新GPU来了,FPGA和ASIC要扔掉吗?

AI科技评论消息,美国时间5月10日,NVIDIA CEO黄仁勋在开发者大会GTC2017上发布新一代GPU架构Volta,首款核心为GV100,采用台积电12...

3488
来自专栏喔家ArchiSelf

神经网络加速器的兴起

自从投身智能硬件以来,又开始重新关注嵌入式领域的相关技术。这是“2018嵌入式处理器报告: 神经网络加速器的兴起”(http://www.embedded-co...

572
来自专栏新智元

【支撑20亿人的机器学习】Jeff Dean、贾扬清等ScaledML大会演讲

1416
来自专栏人工智能头条

【微信分享】李滔:搜狐基于Spark的新闻和广告推荐实战

1172
来自专栏人工智能头条

如何将深度学习与你正在做的事情相结合?

1742
来自专栏数据派THU

【独家】微软郑宇:大数据驱动智能城市讲座精华(附PPT)

[导读]本文整理自微软亚洲研究院“城市计算”领域负责人郑宇博士近期在清华大数据讲座上的分享内容。郑宇主持研发的Urban Air首次利用大数据来监测和预报细粒度...

2198

扫描关注云+社区