穩(wěn)健的算法設(shè)計是整個谷歌系統(tǒng)的基礎(chǔ)，特別是對于機器學習和人工智能模型來說，穩(wěn)健性顯得更加重要。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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