編輯：LRS
由Jeff Dean 主導(dǎo)的Google Research 年終總結(jié)系列《Google Research，2022 Beyond》第五期。本期的主題是算法的進(jìn)步。作者是谷歌研究院副總裁Vahab Mirrokni。
【資料圖】
過(guò)去的鏈接：
超詳細(xì)、超強(qiáng)悍的杰夫·迪恩（Jeff Dean）的一萬(wàn)字總結(jié)出爐了！谷歌2022年在AIGC、LLM、CV三大領(lǐng)域取得的成就圖解谷歌2022年度回顧：為了讓AI更有責(zé)任感，主要做了4個(gè)小任務(wù)Jeff Dean推文：谷歌超硬年終的“第三顆子彈”總結(jié)就到這里啦！大力開(kāi)發(fā)Jax，讓大型模型的訓(xùn)練和推理更快！谷歌2022年年終總結(jié)第四次
魯棒的算法設(shè)計(jì)是整個(gè)Google系統(tǒng)的基礎(chǔ)。尤其是對(duì)于機(jī)器學(xué)習(xí)和人工智能模型來(lái)說(shuō)，魯棒性就顯得更加重要。
因此，開(kāi)發(fā)更高效、更強(qiáng)大、更快的算法仍然是提高搜索、廣告、地圖和YouTube 等服務(wù)能力的當(dāng)務(wù)之急。
Google Reserach 始終走在該領(lǐng)域的前沿，開(kāi)發(fā)了許多創(chuàng)新算法，涵蓋隱私安全推薦系統(tǒng)和大規(guī)模機(jī)器學(xué)習(xí)的可擴(kuò)展解決方案等領(lǐng)域。
下面介紹谷歌在2022年提出的一些最先進(jìn)的技術(shù)，包括可擴(kuò)展性、隱私、市場(chǎng)算法和算法基礎(chǔ)。
隨著處理大規(guī)模數(shù)據(jù)集的需求增加，復(fù)雜算法的可擴(kuò)展性和可靠性仍然比提高算法的可解釋性、魯棒性和速度具有更高的優(yōu)先級(jí)。
谷歌開(kāi)發(fā)的新算法可用于處理各個(gè)領(lǐng)域的大型數(shù)據(jù)集，包括無(wú)監(jiān)督和半監(jiān)督學(xué)習(xí)、基于圖的學(xué)習(xí)、聚類和大規(guī)模優(yōu)化。
該系統(tǒng)的一個(gè)重要部分是構(gòu)建相似度圖，其中節(jié)點(diǎn)是對(duì)象，邊代表對(duì)象之間的相似度。為了提高可擴(kuò)展性和速度，鄰接圖應(yīng)該是稀疏的。
Google 提出了一種名為STAR 的2-hop Spanner 技術(shù)，這是一種高效的分布式圖生成策略，并在理論和實(shí)踐中演示了它如何顯著減少相似性計(jì)算的次數(shù)。生成高質(zhì)量的圖學(xué)習(xí)或聚類輸出，同時(shí)生成稀疏圖。
論文鏈接：https://neurips.cc/Conferences/2022/ScheduleMultitrack?event=53141
例如，對(duì)于具有10T 邊的圖，成對(duì)相似性比較和運(yùn)行時(shí)加速提高了約100 倍，而質(zhì)量損失可以忽略不計(jì)。谷歌已經(jīng)應(yīng)用這個(gè)想法來(lái)開(kāi)發(fā)度量和最小規(guī)模聚合的算法。一類大規(guī)模并行處理算法。
論文鏈接：https://proceedings.mlr.press/v139/dhulipala21a.html
在廣義聚類的背景下，Google開(kāi)發(fā)了第一個(gè)線性時(shí)間層次聚類（HAC）算法和第一個(gè)對(duì)數(shù)深度HAC并行算法DBSCAN，在100B邊緣圖上實(shí)現(xiàn)了50倍的加速。
針對(duì)不同類型的聚類問(wèn)題，還設(shè)計(jì)了改進(jìn)的次線性算法，例如幾何鏈接聚類、常輪相關(guān)聚類和全動(dòng)態(tài)k聚類。
受到多核處理（例如GBBS）成功的啟發(fā)，研究人員著手開(kāi)發(fā)能夠在單個(gè)多核機(jī)器上處理具有100B邊的圖的圖挖掘算法，其中最大的挑戰(zhàn)是實(shí)現(xiàn)快速（例如次線性）并行運(yùn)行時(shí)間（例如深度）。
在之前社區(qū)檢測(cè)和相關(guān)聚類工作的基礎(chǔ)上，Google 開(kāi)發(fā)了一種名為ParHAC 的HAC 算法，具有可證明的多對(duì)數(shù)深度和近線性工作，并實(shí)現(xiàn)了50 倍的加速。
論文鏈接：https://openreview.net/pdf?id=LpgG0C6Y75
例如，ParHAC 只需要大約10 分鐘即可在具有超過(guò)100B 條邊的圖上找到近似的親和力層次結(jié)構(gòu)，而在單臺(tái)機(jī)器上找到完整的HAC 則需要大約3 小時(shí)。
繼之前關(guān)于分布式HAC 的工作之后，我們使用這些多核算法作為分布式算法中的子例程來(lái)擴(kuò)展圖。
2022年，谷歌在圖神經(jīng)網(wǎng)絡(luò)（GNN）方面也取得了一些進(jìn)展。
論文鏈接：https://www.jmlr.org/papers/volume23/20-852/20-852.pdf
研究人員開(kāi)發(fā)了一種基于模型的分類方法，統(tǒng)一了圖學(xué)習(xí)方法。在實(shí)驗(yàn)中，他們還從數(shù)千個(gè)不同結(jié)構(gòu)的圖中發(fā)現(xiàn)了GNN模型的新思路，并提出了一種新的混合架構(gòu)來(lái)克服現(xiàn)有的GNN解決最短路徑和最小生成樹(shù)等基本圖問(wèn)題的深度要求。
此外，為了將這些結(jié)果帶給更廣泛的社區(qū)，Google 發(fā)布了三個(gè)版本的旗艦建模庫(kù)，用于在TensorFlow (TF-GNN) 中構(gòu)建圖神經(jīng)網(wǎng)絡(luò)。亮點(diǎn)包括模型庫(kù)和模型Orchestration API，這使得編寫(xiě)GNN 解決方案變得更加容易。
繼NeurIPS’20 上的大規(guī)模圖挖掘和學(xué)習(xí)研討會(huì)之后，Google 在ICML’22 上舉辦了基于圖的學(xué)習(xí)研討會(huì)，并在NeurIPS’22 上舉辦了關(guān)于TensorFlow 中的GNN 的教程。
論文鏈接：https://dl.acm.org/doi/abs/10.1145/3474717.3483961
谷歌還提出了谷歌地圖解決方案，可以有效計(jì)算路網(wǎng)中的替代路線、持續(xù)發(fā)生的故障（例如道路封閉和緊急情況等）。
我們還展示了該模型如何在現(xiàn)實(shí)世界的道路網(wǎng)絡(luò)上顯著優(yōu)于最先進(jìn)的平臺(tái)和懲罰方法。
在優(yōu)化方面，Google開(kāi)源了Vizier，一個(gè)強(qiáng)大的黑盒優(yōu)化和超參數(shù)調(diào)優(yōu)庫(kù)。
研究人員還開(kāi)發(fā)了線性編程（LP）解決方案的新技術(shù)，解決了由于依賴矩陣分解而導(dǎo)致的可擴(kuò)展性限制，限制了并行性和分布式方法的發(fā)展。
代碼鏈接：https://github.com/google/or-tools
為此，研究人員開(kāi)源了一種名為原對(duì)偶線性規(guī)劃（PDLP）的原對(duì)偶混合梯度（PDHG）解決方案，這是一種新的一階求解器，可用于解決大規(guī)模LP問(wèn)題。
PDLP已被用于解決具有高達(dá)12B非零數(shù)的現(xiàn)實(shí)世界問(wèn)題（內(nèi)部分布式版本擴(kuò)展到92B非零數(shù)），PDLP的有效性是理論發(fā)展和算法工程相結(jié)合的結(jié)果。
在提供高質(zhì)量服務(wù)的同時(shí)尊重用戶隱私仍然是所有Google 系統(tǒng)的首要任務(wù)，該領(lǐng)域的研究涵蓋許多產(chǎn)品，并使用差分隱私(DP) 和聯(lián)邦學(xué)習(xí)的原理。
首先，為了解決用DP訓(xùn)練大型神經(jīng)網(wǎng)絡(luò)的問(wèn)題，研究人員在算法上取得了一些進(jìn)展。
在前期工作的基礎(chǔ)上，我們繼續(xù)開(kāi)發(fā)基于DP-FTRL算法的DP神經(jīng)網(wǎng)絡(luò)用于矩陣分解。
論文鏈接：https://arxiv.org/pdf/2103.00039.pdf
這項(xiàng)工作表明，人們可以設(shè)計(jì)一個(gè)數(shù)學(xué)程序來(lái)優(yōu)化大量可能的DP 機(jī)制，以找到最適合特定學(xué)習(xí)問(wèn)題的機(jī)制。
在神經(jīng)網(wǎng)絡(luò)和核方法的DP學(xué)習(xí)中，研究人員還建立了與輸入特征維度無(wú)關(guān)的邊界保證，并將這一概念進(jìn)一步擴(kuò)展到更廣泛的機(jī)器學(xué)習(xí)任務(wù)，其計(jì)算量還不到原來(lái)的1/300?？梢云ヅ浠€的性能。
對(duì)于大型模型的微調(diào)，研究人員認(rèn)為，一旦經(jīng)過(guò)預(yù)訓(xùn)練，這些模型（即使使用DP）本質(zhì)上也在低維子空間中運(yùn)行，從而繞過(guò)了DP 帶來(lái)的維數(shù)災(zāi)難。
在算法上，為了估計(jì)高維分布的熵，可以使用局部DP 機(jī)制（即使每個(gè)樣本只有一位可用）和高效的shuffle DP 機(jī)制。
論文鏈接：https://arxiv.org/abs/2210.15178
研究人員提出了一種更精確的方法來(lái)同時(shí)、私密地估計(jì)數(shù)據(jù)庫(kù)中最受歡迎的項(xiàng)目，并將該方法應(yīng)用于Plume 庫(kù)。
此外，近似算術(shù)計(jì)算（MPC）模型中演示了接近最優(yōu)的DP集群大規(guī)模并行處理器，進(jìn)一步改進(jìn)了可擴(kuò)展和分布式設(shè)置中的先前工作。
論文鏈接：https://arxiv.org/abs/2107.14527
另一個(gè)有前途的研究方向是隱私和流媒體的交叉。研究人員提出了一種近乎最優(yōu)的私有頻率矩的近似空間權(quán)衡，以及一種用于滑動(dòng)窗口流模型中不同元素的私有計(jì)數(shù)的新算法。他們還提出了一項(xiàng)研究用于對(duì)抗性流媒體的通用混合框架。
對(duì)于安全和隱私交叉的應(yīng)用程序，Google 開(kāi)發(fā)了新的安全、私密和通信高效的算法，用于測(cè)量跨發(fā)布商的覆蓋范圍和頻率。
世界廣告商聯(lián)合會(huì)已采用這些算法作為其衡量系統(tǒng)的一部分。在后續(xù)工作中，研究人員還開(kāi)發(fā)了用于DP 的安全且私密的新協(xié)議。在兩臺(tái)服務(wù)器模型中計(jì)算稀疏直方圖。
論文鏈接：https://dl.acm.org/doi/10.1145/3548606.3559383
這些協(xié)議從計(jì)算和通信的角度來(lái)看是高效的，比標(biāo)準(zhǔn)方法要好得多，并且結(jié)合了草圖、密碼學(xué)、多方計(jì)算以及DP等工具和技術(shù)。
雖然BERT 和Transformers 到目前為止已經(jīng)使用DP 進(jìn)行了訓(xùn)練，但了解大型語(yǔ)言模型(LLM) 中訓(xùn)練示例的記憶是評(píng)估其隱私的啟發(fā)式方法。
論文鏈接：https://arxiv.org/abs/2207.00099
特別是，我們檢查了LLM 在訓(xùn)練期間忘記（潛在地記住）訓(xùn)練示例的時(shí)間和原因，研究結(jié)果表明，可以通過(guò)犧牲后來(lái)看到的示例來(lái)觀察到先前看到的示例的隱私優(yōu)勢(shì)。
論文鏈接：https://arxiv.org/abs/2202.07646
研究人員還量化了法學(xué)碩士發(fā)出記憶訓(xùn)練數(shù)據(jù)的效果。
Google 繼續(xù)研究如何在2022 年改善在線市場(chǎng)。
例如，最近廣告拍賣研究的一個(gè)重要領(lǐng)域是在線廣告自動(dòng)競(jìng)價(jià)的研究，其中大多數(shù)競(jìng)價(jià)是通過(guò)代理競(jìng)價(jià)者代表廣告商優(yōu)化更高級(jí)別的目標(biāo)。用戶、廣告商、競(jìng)價(jià)者和廣告平臺(tái)導(dǎo)致了這一領(lǐng)域的一些問(wèn)題。
繼之前分析和改進(jìn)自動(dòng)競(jìng)價(jià)拍賣機(jī)制的工作之后，谷歌繼續(xù)研究如何在自動(dòng)化背景下改進(jìn)在線市場(chǎng)，同時(shí)考慮到用戶體驗(yàn)和廣告預(yù)算等不同方面。
論文鏈接：https://arxiv.org/abs/2207.03630
結(jié)果表明，即使在非現(xiàn)實(shí)拍賣中，機(jī)器學(xué)習(xí)推薦和隨機(jī)化技術(shù)的適當(dāng)組合也可以有力地提高均衡自動(dòng)出價(jià)算法的整體福利。
除了自動(dòng)出價(jià)系統(tǒng)之外，谷歌還致力于復(fù)雜環(huán)境中的拍賣改進(jìn)，例如買家由中介機(jī)構(gòu)和多種廣告格式代表的情況，其中每個(gè)廣告可以以幾種可能的變體形式顯示。在最近的一項(xiàng)調(diào)查中，谷歌總結(jié)了相關(guān)工作。
論文鏈接：https://www.sigecom.org/exchanges/volume_20/2/BHAWALKAR.pdf
除了拍賣之外，谷歌還研究了合約在多代理和對(duì)抗環(huán)境中的使用。在線隨機(jī)優(yōu)化仍然是在線廣告系統(tǒng)的重要組成部分，在最佳出價(jià)和預(yù)算節(jié)奏方面有著廣泛的應(yīng)用。
基于在線作業(yè)研究的悠久歷史，研究人員最近發(fā)表了對(duì)雙鏡像下降的介紹，這是一種用于在線作業(yè)問(wèn)題的新算法，該算法簡(jiǎn)單、穩(wěn)健、靈活，并且能夠抵抗各種對(duì)抗性和隨機(jī)輸入分布，并且可以優(yōu)化經(jīng)濟(jì)效率之外的重要目標(biāo)，例如公平。
結(jié)果還表明，可以通過(guò)將支出約束調(diào)整為日益流行的特殊結(jié)構(gòu)回報(bào)來(lái)優(yōu)化廣告商價(jià)值，該結(jié)構(gòu)具有廣泛的應(yīng)用范圍，并且隨著時(shí)間的推移已被用于幫助廣告商通過(guò)更好的算法決策獲得更多價(jià)值。
論文鏈接：https://arxiv.org/abs/2109.03173
此外，谷歌基于在機(jī)器學(xué)習(xí)、機(jī)制設(shè)計(jì)和市場(chǎng)互動(dòng)方面的工作，研究了為非對(duì)稱拍賣設(shè)計(jì)的變形金剛，為無(wú)悔學(xué)習(xí)的買家設(shè)計(jì)了效用最大化策略，并開(kāi)發(fā)了新的學(xué)習(xí)算法來(lái)在拍賣中出價(jià)或定價(jià)。
復(fù)雜在線服務(wù)的一個(gè)關(guān)鍵組成部分是能夠通過(guò)實(shí)驗(yàn)測(cè)量用戶和其他參與者對(duì)新干預(yù)措施的反應(yīng)。準(zhǔn)確估計(jì)這些因果效應(yīng)的一個(gè)主要挑戰(zhàn)是處理這些實(shí)驗(yàn)的控制單元和治療單元之間復(fù)雜的相互作用。效應(yīng)（或干擾）。
論文鏈接：https://openreview.net/pdf?id=hqtSdpAK39W
結(jié)合圖聚類和因果推理方面的專業(yè)知識(shí)，擴(kuò)展了該領(lǐng)域之前的工作，改進(jìn)了靈活響應(yīng)模型和新實(shí)驗(yàn)設(shè)計(jì)下的結(jié)果。
論文鏈接：https://proceedings.neurips.cc/paper/2021/file/48d23e87eb98cc2227b5a8c33fa00680-Paper.pdf
當(dāng)處理任務(wù)和度量測(cè)量發(fā)生在雙向平臺(tái)的同一側(cè)時(shí)，可以更有效地減少這些交互。我們還展示了如何結(jié)合綜合控制和優(yōu)化技術(shù)來(lái)設(shè)計(jì)更強(qiáng)大的實(shí)驗(yàn)，特別是在小數(shù)據(jù)的情況下。向下。
Google 還通過(guò)解決長(zhǎng)期存在的“開(kāi)放問(wèn)題”來(lái)繼續(xù)基礎(chǔ)算法研究。
論文鏈接：https://dl.acm.org/doi/pdf/10.1145/3519935.3520054
一篇簡(jiǎn)明的論文解決了一個(gè)有40 年歷史的懸而未決的問(wèn)題：是否存在一種機(jī)制，可以在買方價(jià)值弱于賣方成本時(shí)保證交易收益的恒定部分。
論文鏈接：https://dl.acm.org/doi/pdf/10.1145/3519935.3520011
另一篇論文獲得了經(jīng)典且經(jīng)過(guò)深入研究的k 均值問(wèn)題的最先進(jìn)的近似，并且還改進(jìn)了相關(guān)聚類的最佳近似，打破了2 的障礙近似因子。
他在動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)方面的工作解決了最小成本和其他網(wǎng)絡(luò)流量問(wèn)題，并且在利用連續(xù)優(yōu)化技術(shù)解決經(jīng)典離散優(yōu)化問(wèn)題方面取得了突破性進(jìn)展。
設(shè)計(jì)高效的算法和機(jī)制是Google 大型系統(tǒng)的關(guān)鍵組成部分，需要在考慮隱私和安全的情況下穩(wěn)健地處理大規(guī)模數(shù)據(jù)。
指導(dǎo)思想是開(kāi)發(fā)具有堅(jiān)實(shí)理論基礎(chǔ)的算法，可以有效地部署在生產(chǎn)系統(tǒng)中，此外，通過(guò)開(kāi)放一些最新穎的開(kāi)發(fā)并發(fā)布背后的先進(jìn)算法，將其中的許多進(jìn)步帶到更廣泛的社區(qū)他們。
在這篇博客中，谷歌研究人員討論了隱私、市場(chǎng)算法、可擴(kuò)展算法、基于圖的學(xué)習(xí)和優(yōu)化方面的算法進(jìn)步。
隨著我們邁向人工智能優(yōu)先、更加自動(dòng)化的谷歌，開(kāi)發(fā)強(qiáng)大、可擴(kuò)展和保護(hù)隱私的機(jī)器學(xué)習(xí)算法仍然是首要任務(wù)，保持開(kāi)發(fā)新算法并更廣泛部署它們的熱情。
參考：
https://ai.googleblog.com/2023/02/google-research-2022-beyond-algorithmic.html
