基礎算法才是王道！真正的「算法工程師」都在研究啥？

穩健的算法設計是整個(gè)谷歌系統的基礎，特別是對于機器學(xué)習和人工智能模型來(lái)說(shuō)，穩健性顯得更加重要。

因此，開(kāi)發(fā)具有更高效率、更強性能以及更快速的算法仍然具有相當高的優(yōu)先級，可以提升從搜索和廣告到地圖和 YouTube 等各種服務(wù)的能力。
Google Reserach一直走在該領(lǐng)域前沿，開(kāi)發(fā)了許多創(chuàng )新性的算法，涉及的領(lǐng)域包括隱私安全的推薦系統、大規模機器學(xué)習的可擴展解決方案等。
下面介紹一些Google在2022年提出的最先進(jìn)的技術(shù)包括可伸縮性、隱私、市場(chǎng)算法和算法基礎等。
可伸縮算法: 圖、聚類(lèi)和優(yōu)化
隨著(zhù)處理大規模數據集的需求增加，復雜算法的可伸縮性（scalability）和可靠性（reliability）在改進(jìn)算法的可解釋性、健壯性和速度上仍然具有較高優(yōu)先級。
谷歌開(kāi)發(fā)的新算法可用于處理各個(gè)領(lǐng)域的大型數據集，包括無(wú)監督和半監督學(xué)習、基于圖的學(xué)習、聚類(lèi)和大規模優(yōu)化。
系統中的一個(gè)重要組成部分是建立一個(gè)相似圖（similarity graph），節點(diǎn)為對象，邊表示對象之間的相似度。為了提高可伸縮性和速度，鄰接圖應該是稀疏的。
谷歌提出了一種叫做 STAR 的兩跳擴展技術(shù)（2-hop spanner technique），是一種高效的分布式圖形生成策略，并展示了它如何在理論和實(shí)踐上顯著(zhù)減少相似度計算的數量，在生成高質(zhì)量的圖形學(xué)習或聚類(lèi)輸出的同時(shí)生成更稀疏的圖形。

論文鏈接：https://neurips.cc/Conferences/2022/ScheduleMultitrack?event=53141
比如說(shuō)對于具有10T條邊的圖，在成對相似性比較和運行時(shí)間加速方面實(shí)現了約100倍的改進(jìn)，而質(zhì)量損失可以忽略不計，谷歌已經(jīng)應用這個(gè)想法來(lái)開(kāi)發(fā)用于度量和最小規模聚類(lèi)的大規模并行處理算法。

論文鏈接：https://proceedings.mlr.press/v139/dhulipala21a.html
在廣義的聚類(lèi)背景下，谷歌開(kāi)發(fā)了第一個(gè)具有線(xiàn)性時(shí)間層次聚集聚類(lèi)(HAC)算法和第一個(gè)對數深度 HAC 并行算法 DBSCAN，該算法在100B 邊圖上實(shí)現了50倍的加速。
并且還針對不同類(lèi)型的聚類(lèi)問(wèn)題設計了改進(jìn)的次線(xiàn)性算法，如幾何連接聚類(lèi)、常數輪相關(guān)聚類(lèi)和完全動(dòng)態(tài) k 聚類(lèi)。
受到多核處理(例如 GBBS)成功的啟發(fā)，研究人員開(kāi)始著(zhù)手開(kāi)發(fā)能夠在單個(gè)多核機器上處理具有100B 邊的圖的圖挖掘算法，其中最大的難題是實(shí)現快速(例如，次線(xiàn)性)并行運行時(shí)間(例如，深度)。
在之前社區檢測和相關(guān)聚類(lèi)工作的基礎上，谷歌開(kāi)發(fā)了一個(gè) HAC 算法叫做 ParHAC，具有可證明的多對數深度和近線(xiàn)性工作，并實(shí)現了50倍的加速。

論文鏈接：https://openreview.net/pdf?id=LpgG0C6Y75
例如，ParHAC 只需要約10分鐘就可以在一個(gè)超過(guò)100B 邊的圖上找到一個(gè)近似的親和層次結構，而在一臺機器上找到完整的 HAC 則需要約3小時(shí)。
繼之前在分布式 HAC 上的工作之后，使用這些多核算法作為分布式算法中的一個(gè)子例程來(lái)ter-scale的圖。
2022年，谷歌在圖形神經(jīng)網(wǎng)絡(luò )(GNN)方面也得到了一些進(jìn)展。

論文鏈接：https://www.jmlr.org/papers/volume23/20-852/20-852.pdf
研究人員開(kāi)發(fā)了一個(gè)基于模型的分類(lèi)方法，統一了圖學(xué)習方法，實(shí)驗中還從數千個(gè)不同結構的圖表中發(fā)現了對 GNN 模型的新思路，提出了一種新的混合體系結構，以克服現有 GNN 解決基本圖問(wèn)題(如最短路徑和最小生成樹(shù))的深度要求。

此外，為了將這些成果帶到更廣泛的社區中，谷歌發(fā)布了用于在 TensorFlow (TF-GNN)中構建圖形神經(jīng)網(wǎng)絡(luò )的旗艦建模庫的三個(gè)版本，其中的亮點(diǎn)包括一個(gè)模型庫和模型編排 API，這使得編寫(xiě) GNN 解決方案變得更加容易。
在NeurIPS’20上的關(guān)于大規模圖形挖掘和學(xué)習研討會(huì )之后，谷歌在 ICML’22舉辦了一個(gè)關(guān)于基于圖形的學(xué)習的研討會(huì )，以及在 NeurIPS’22舉辦了一個(gè)關(guān)于 TensorFlow 中 GNN 的教程。

論文鏈接：https://dl.acm.org/doi/abs/10.1145/3474717.3483961
谷歌還提出了一個(gè)谷歌地圖解決方案，可以有效地計算道路網(wǎng)絡(luò )中的可選路線(xiàn)、持續故障(例如，道路關(guān)閉和突發(fā)事件等)。
文中還展示了該模型如何顯著(zhù)優(yōu)于現實(shí)世界中的道路網(wǎng)絡(luò )的最先進(jìn)的plateau and penalty方法。

在優(yōu)化方面，谷歌開(kāi)源了 Vizier，一個(gè)強大的黑盒優(yōu)化和超參數調優(yōu)庫。
研究人員還為線(xiàn)性規劃(LP)解決方案開(kāi)發(fā)了新的技術(shù)，解決了由于依賴(lài)矩陣分解而導致的可伸縮性限制，限制了并行性和分布式方法的發(fā)展。

代碼鏈接：https://github.com/google/or-tools
為此，研究人員開(kāi)源了一個(gè)稱(chēng)為原始-對偶線(xiàn)性規劃(PDLP)的原始-對偶混合梯度(PDHG)解決方案，一個(gè)新的一階求解器，可用于解決大規模 LP 問(wèn)題。

PDLP 已經(jīng)被用來(lái)解決現實(shí)世界中多達12B non-zeros的問(wèn)題(內部分布式版本擴展到92B non-zeros)，PDLP 的有效性是理論發(fā)展和算法工程相結合的結果。
隱私和聯(lián)邦學(xué)習
在提供高質(zhì)量服務(wù)的同時(shí)尊重用戶(hù)隱私仍然是所有 Google 系統的首要任務(wù)，該領(lǐng)域的研究涉及許多產(chǎn)品，并使用了來(lái)自差分隱私(differential privacy，DP)和聯(lián)邦學(xué)習的原則。
首先，為了解決用 DP 訓練大型神經(jīng)網(wǎng)絡(luò )的問(wèn)題，研究人員在算法上取得了一些進(jìn)展。
在早期工作的基礎上，繼續開(kāi)發(fā)了一個(gè)基于 DP-FTRL 算法的 DP 神經(jīng)網(wǎng)絡(luò )，用于矩陣分解的算法DP-FTRL。

論文鏈接：https://arxiv.org/pdf/2103.00039.pdf
這項工作表明，人們可以設計一個(gè)數學(xué)程序，以?xún)?yōu)化超過(guò)一個(gè)可能的 DP 機制的大集，以找到那些最適合特定的學(xué)習問(wèn)題。
在神經(jīng)網(wǎng)絡(luò )和核方法的 DP 學(xué)習中，研究人員還建立了與輸入特征維數無(wú)關(guān)的邊界保證，并且進(jìn)一步將這個(gè)概念擴展到更廣泛的機器學(xué)習任務(wù)，以不到原來(lái)1/300的計算量就可以匹敵基線(xiàn)的性能。
對于大型模型的微調，研究人員認為，一旦預訓練后，這些模型(甚至與 DP)基本上操作在一個(gè)低維子空間，從而繞過(guò)了 DP 強加的維數災難。

在算法方面，為了估計一個(gè)高維分布的熵，可以得到局部 DP 機制（即使每個(gè)樣本只有一個(gè)比特可用也能工作）和有效的shuffle DP 機制。

論文鏈接：https://arxiv.org/abs/2210.15178
研究人員提出了一種更加精確的方法來(lái)同時(shí)以私密的方式估計數據庫中最受歡迎的項目，并在 Plume 庫中應用了這種方法。
此外，在近似演算法計算(MPC)模型中展示了接近最佳的 DP 集群大規模并行處理機，進(jìn)一步改進(jìn)了以前在可伸縮和分布式設置方面的工作。

論文鏈接：https://arxiv.org/abs/2107.14527
另一個(gè)有前景的研究方向是隱私和流媒體的交叉，研究人員提出了一個(gè)近似最優(yōu)的近似空間權衡私有頻率矩和一個(gè)新的算法私有計數不同的元素在滑動(dòng)窗口流模型，還提出了一個(gè)研究對抗流（adversarial streaming）的通用混合框架。
針對安全性和隱私性交叉的應用程序，谷歌開(kāi)發(fā)了安全、私有和通信效率高的新算法，用于測量交叉出版商的覆蓋范圍和頻率。
世界廣告商聯(lián)合會(huì )（World Federation of Advertisers）已經(jīng)采用這些算法作為他們測量系統的一部分，在后續的工作中，研究人員還開(kāi)發(fā)了新的協(xié)議，是保證安全的且私有的，用于在 DP 的兩服務(wù)器模型中計算稀疏直方圖。

論文鏈接：https://dl.acm.org/doi/10.1145/3548606.3559383
從計算和通信的角度來(lái)看，這些協(xié)議都是高效的，比標準方法要好得多，并且結合了草圖、密碼學(xué)和多方計算以及 DP 等工具和技術(shù)。
雖然目前已經(jīng)用 DP 訓練了 BERT 和變壓器，但理解大語(yǔ)言模型(LLM)中的訓練樣例記憶是評估其隱私性的一種啟發(fā)式方法。

論文鏈接：https://arxiv.org/abs/2207.00099
特別是研究了 LLM 在訓練中忘記(潛在記憶)訓練例子的時(shí)間和原因，研究結果表明，以前看到的例子可能會(huì )以后看到的例子為代價(jià)來(lái)觀(guān)察隱私的好處。

論文鏈接：https://arxiv.org/abs/2202.07646
研究人員還量化了 LLM 發(fā)出記憶訓練數據的程度。
市場(chǎng)算法與因果推理
谷歌在2022年繼續研究如何改善在線(xiàn)市場(chǎng)（online marketplaces）。
例如，最近廣告拍賣(mài)研究的一個(gè)重要領(lǐng)域是自動(dòng)投標在線(xiàn)廣告的研究，其中大多數投標是通過(guò)代理投標人，代表廣告商優(yōu)化更高層次的目標。用戶(hù)、廣告商、投標人和廣告平臺，導致這個(gè)領(lǐng)域存在一些問(wèn)題。
繼之前分析和改進(jìn)自動(dòng)競價(jià)拍賣(mài)機制的工作之后，谷歌繼續研究如何在自動(dòng)化背景下改進(jìn)在線(xiàn)市場(chǎng)，同時(shí)考慮到了不同方面，如用戶(hù)體驗和廣告預算。

論文鏈接：https://arxiv.org/abs/2207.03630
研究結果表明，適當結合機器學(xué)習的建議和隨機化技術(shù)，即使在非真實(shí)的拍賣(mài)，可以有力地改善整體福利在均衡的自動(dòng)競價(jià)算法。

除了自動(dòng)競價(jià)系統，谷歌還研究了復雜環(huán)境下的拍賣(mài)改進(jìn)措施，例如，買(mǎi)家由中介代表，多種告形式，每個(gè)廣告可以顯示在幾個(gè)可能的變體。在最近的一篇survey中，谷歌總結了相關(guān)工作。

論文鏈接：https://www.sigecom.org/exchanges/volume_20/2/BHAWALKAR.pdf
除了拍賣(mài)，谷歌還研究了合同在多代理人和對抗性環(huán)境中的使用，在線(xiàn)隨機優(yōu)化仍然是在線(xiàn)廣告系統的重要組成部分，在最優(yōu)投標和預算節奏方面有著(zhù)廣泛的應用。

在長(cháng)期的在線(xiàn)分配研究的基礎上，研究人員最近發(fā)表了關(guān)于雙鏡像下降（dual mirror descent）的介紹，一種簡(jiǎn)單、健壯和靈活的在線(xiàn)分配問(wèn)題的新算法，可以抵抗廣泛的對抗性和隨機輸入分布，并且可以?xún)?yōu)化經(jīng)濟效率之外的重要目標，如公平性。
結果還表明，通過(guò)裁剪雙鏡下降到日益流行的特殊結構回報的支出約束，可以?xún)?yōu)化廣告客戶(hù)的價(jià)值，其有著(zhù)廣泛的應用，并且隨著(zhù)時(shí)間的推移已經(jīng)被用來(lái)幫助廣告商通過(guò)更好的算法決策獲得更多的價(jià)值。

論文鏈接：https://arxiv.org/abs/2109.03173
此外，根據在機器學(xué)習、機制設計和市場(chǎng)相互作用方面的工作，谷歌研究了非對稱(chēng)拍賣(mài)設計的Transformer，為no-regret學(xué)習的買(mǎi)家設計了效用最大化策略，并開(kāi)發(fā)了新的學(xué)習算法來(lái)出價(jià)或在拍賣(mài)中定價(jià)。

復雜的在線(xiàn)服務(wù)的一個(gè)關(guān)鍵組成部分是能夠通過(guò)實(shí)驗測量用戶(hù)和其他參與者對新干預措施的反應，準確估計這些因果效應的一個(gè)主要挑戰是處理這些實(shí)驗的控制單元和治療單元之間的復雜相互作用(或干擾)。

論文鏈接：https://openreview.net/pdf?id=hqtSdpAK39W
將圖形聚類(lèi)和因果推理專(zhuān)業(yè)知識結合起來(lái)，擴展了之前在這個(gè)領(lǐng)域的工作成果，在靈活的響應模型和新的實(shí)驗設計下改進(jìn)了結果。

論文鏈接：https://proceedings.neurips.cc/paper/2021/file/48d23e87eb98cc2227b5a8c33fa00680-Paper.pdf
當treatment 任務(wù)和度量測量發(fā)生在二分平臺的同一側時(shí)，可以更有效地減少這些相互作用，文中還展示了如何將綜合控制和優(yōu)化技術(shù)相結合來(lái)設計更強大的實(shí)驗，特別是在小數據情況下。
算法基礎和理論
谷歌還通過(guò)解決長(cháng)期存在的「開(kāi)放問(wèn)題」來(lái)繼續基礎算法研究。

論文鏈接：https://dl.acm.org/doi/pdf/10.1145/3519935.3520054
一篇簡(jiǎn)明扼要的論文解決了一個(gè)40年前的懸而未決的問(wèn)題: 是否存在一種機制，在買(mǎi)方價(jià)值弱于賣(mài)方成本的情況下，保證交易收益的一部分不變。

論文鏈接：https://dl.acm.org/doi/pdf/10.1145/3519935.3520011
另一篇論文得到了經(jīng)典的和高度研究的 k- 均值問(wèn)題的最新近似，還改進(jìn)了相關(guān)聚類(lèi)的最佳逼近，突破了2的障礙逼近因子。
并且在動(dòng)態(tài)數據結構方面的工作解決了最小成本和其他網(wǎng)絡(luò )流量問(wèn)題，在采用連續優(yōu)化技術(shù)解決經(jīng)典的離散優(yōu)化問(wèn)題方面取得了突破性進(jìn)展。
總結
設計有效的算法和機制是谷歌大規模系統的關(guān)鍵組成部分，這些系統需要以關(guān)鍵的隱私和安全考慮來(lái)穩健地處理大規模數據。
指導思想是開(kāi)發(fā)具有堅實(shí)理論基礎的算法，這些算法可以有效地部署在產(chǎn)品系統中，此外，通過(guò)開(kāi)放一些最新穎的開(kāi)發(fā)和發(fā)布它們背后的高級算法，將許多這些進(jìn)步帶給了更廣泛的社區。
在這篇博客中，谷歌的研究人員討論了算法在隱私、市場(chǎng)算法、可擴展算法、基于圖表的學(xué)習和優(yōu)化方面的進(jìn)步。
隨著(zhù)朝著(zhù)人工智能優(yōu)先、自動(dòng)化程度更高的谷歌邁進(jìn)，開(kāi)發(fā)健壯、可擴展和保護隱私的機器學(xué)習算法仍然是當務(wù)之急，對開(kāi)發(fā)新的算法和更廣泛地部署保持熱情。
參考資料：https://ai.googleblog.com/2023/02/google-research-2022-beyond-algorithmic.html