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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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