一文看懂谷歌 NYC 演算法與優化業務全景：三大項目組12個子領域詳解（附重點論文下載）

雷鋒網 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 演算法及優化團隊於近日公布的網站主頁，自然能夠更好地從全局讓大家了解谷歌演算法優化的過往和未來，並且從這一研究組的系統整理中得到做研究的啟迪。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！