一文看懂谷歌 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 算法及優化團隊于近日公布的網站主頁，自然能夠更好地從全局讓大家了解谷歌算法優化的過往和未來，并且從這一研究組的系統整理中得到做研究的啟迪。
雷鋒網原創文章，未經授權禁止轉載。詳情見轉載須知。
總結
以上是生活随笔為你收集整理的一文看懂谷歌 NYC 算法与优化业务全景：三大项目组12个子领域详解（附重点论文下载）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Hinton's Dark Knowle
- 下一篇： 干货 | 算法工程师入门第一期——罗恒讲