编辑：LRS
由Jeff Dean 主导的Google Research 年终总结系列《Google Research，2022 Beyond》第五期。本期的主题是算法的进步。作者是谷歌研究院副总裁Vahab Mirrokni。
【资料图】
过去的链接：
超详细、超强悍的杰夫·迪恩（Jeff Dean）的一万字总结出炉了！谷歌2022年在AIGC、LLM、CV三大领域取得的成就图解谷歌2022年度回顾：为了让AI更有责任感，主要做了4个小任务Jeff Dean推文：谷歌超硬年终的“第三颗子弹”总结就到这里啦！大力开发Jax，让大型模型的训练和推理更快！谷歌2022年年终总结第四次
鲁棒的算法设计是整个Google系统的基础。尤其是对于机器学习和人工智能模型来说，鲁棒性就显得更加重要。
因此，开发更高效、更强大、更快的算法仍然是提高搜索、广告、地图和YouTube 等服务能力的当务之急。
Google Reserach 始终走在该领域的前沿，开发了许多创新算法，涵盖隐私安全推荐系统和大规模机器学习的可扩展解决方案等领域。
下面介绍谷歌在2022年提出的一些最先进的技术，包括可扩展性、隐私、市场算法和算法基础。
随着处理大规模数据集的需求增加，复杂算法的可扩展性和可靠性仍然比提高算法的可解释性、鲁棒性和速度具有更高的优先级。
谷歌开发的新算法可用于处理各个领域的大型数据集，包括无监督和半监督学习、基于图的学习、聚类和大规模优化。
该系统的一个重要部分是构建相似度图，其中节点是对象，边代表对象之间的相似度。为了提高可扩展性和速度，邻接图应该是稀疏的。
Google 提出了一种名为STAR 的2-hop Spanner 技术，这是一种高效的分布式图生成策略，并在理论和实践中演示了它如何显着减少相似性计算的次数。生成高质量的图学习或聚类输出，同时生成稀疏图。
论文链接：https://neurips.cc/Conferences/2022/ScheduleMultitrack?event=53141
例如，对于具有10T 边的图，成对相似性比较和运行时加速提高了约100 倍，而质量损失可以忽略不计。谷歌已经应用这个想法来开发度量和最小规模聚合的算法。一类大规模并行处理算法。
论文链接：https://proceedings.mlr.press/v139/dhulipala21a.html
在广义聚类的背景下，Google开发了第一个线性时间层次聚类（HAC）算法和第一个对数深度HAC并行算法DBSCAN，在100B边缘图上实现了50倍的加速。
针对不同类型的聚类问题，还设计了改进的次线性算法，例如几何链接聚类、常轮相关聚类和全动态k聚类。
受到多核处理（例如GBBS）成功的启发，研究人员着手开发能够在单个多核机器上处理具有100B边的图的图挖掘算法，其中最大的挑战是实现快速（例如次线性）并行运行时间（例如深度）。
在之前社区检测和相关聚类工作的基础上，Google 开发了一种名为ParHAC 的HAC 算法，具有可证明的多对数深度和近线性工作，并实现了50 倍的加速。
论文链接：https://openreview.net/pdf?id=LpgG0C6Y75
例如，ParHAC 只需要大约10 分钟即可在具有超过100B 条边的图上找到近似的亲和力层次结构，而在单台机器上找到完整的HAC 则需要大约3 小时。
继之前关于分布式HAC 的工作之后，我们使用这些多核算法作为分布式算法中的子例程来扩展图。
2022年，谷歌在图神经网络（GNN）方面也取得了一些进展。
论文链接：https://www.jmlr.org/papers/volume23/20-852/20-852.pdf
研究人员开发了一种基于模型的分类方法，统一了图学习方法。在实验中，他们还从数千个不同结构的图中发现了GNN模型的新思路，并提出了一种新的混合架构来克服现有的GNN解决最短路径和最小生成树等基本图问题的深度要求。
此外，为了将这些结果带给更广泛的社区，Google 发布了三个版本的旗舰建模库，用于在TensorFlow (TF-GNN) 中构建图神经网络。亮点包括模型库和模型Orchestration API，这使得编写GNN 解决方案变得更加容易。
继NeurIPS’20 上的大规模图挖掘和学习研讨会之后，Google 在ICML’22 上举办了基于图的学习研讨会，并在NeurIPS’22 上举办了关于TensorFlow 中的GNN 的教程。
论文链接：https://dl.acm.org/doi/abs/10.1145/3474717.3483961
谷歌还提出了谷歌地图解决方案，可以有效计算路网中的替代路线、持续发生的故障（例如道路封闭和紧急情况等）。
我们还展示了该模型如何在现实世界的道路网络上显着优于最先进的平台和惩罚方法。
在优化方面，Google开源了Vizier，一个强大的黑盒优化和超参数调优库。
研究人员还开发了线性编程（LP）解决方案的新技术，解决了由于依赖矩阵分解而导致的可扩展性限制，限制了并行性和分布式方法的发展。
代码链接：https://github.com/google/or-tools
为此，研究人员开源了一种名为原对偶线性规划（PDLP）的原对偶混合梯度（PDHG）解决方案，这是一种新的一阶求解器，可用于解决大规模LP问题。
PDLP已被用于解决具有高达12B非零数的现实世界问题（内部分布式版本扩展到92B非零数），PDLP的有效性是理论发展和算法工程相结合的结果。
在提供高质量服务的同时尊重用户隐私仍然是所有Google 系统的首要任务，该领域的研究涵盖许多产品，并使用差分隐私(DP) 和联邦学习的原理。
首先，为了解决用DP训练大型神经网络的问题，研究人员在算法上取得了一些进展。
在前期工作的基础上，我们继续开发基于DP-FTRL算法的DP神经网络用于矩阵分解。
论文链接：https://arxiv.org/pdf/2103.00039.pdf
这项工作表明，人们可以设计一个数学程序来优化大量可能的DP 机制，以找到最适合特定学习问题的机制。
在神经网络和核方法的DP学习中，研究人员还建立了与输入特征维度无关的边界保证，并将这一概念进一步扩展到更广泛的机器学习任务，其计算量还不到原来的1/300。可以匹配基线的性能。
对于大型模型的微调，研究人员认为，一旦经过预训练，这些模型（即使使用DP）本质上也在低维子空间中运行，从而绕过了DP 带来的维数灾难。
在算法上，为了估计高维分布的熵，可以使用局部DP 机制（即使每个样本只有一位可用）和高效的shuffle DP 机制。
论文链接：https://arxiv.org/abs/2210.15178
研究人员提出了一种更精确的方法来同时、私密地估计数据库中最受欢迎的项目，并将该方法应用于Plume 库。
此外，近似算术计算（MPC）模型中演示了接近最优的DP集群大规模并行处理器，进一步改进了可扩展和分布式设置中的先前工作。
论文链接：https://arxiv.org/abs/2107.14527
另一个有前途的研究方向是隐私和流媒体的交叉。研究人员提出了一种近乎最优的私有频率矩的近似空间权衡，以及一种用于滑动窗口流模型中不同元素的私有计数的新算法。他们还提出了一项研究用于对抗性流媒体的通用混合框架。
对于安全和隐私交叉的应用程序，Google 开发了新的安全、私密和通信高效的算法，用于测量跨发布商的覆盖范围和频率。
世界广告商联合会已采用这些算法作为其衡量系统的一部分。在后续工作中，研究人员还开发了用于DP 的安全且私密的新协议。在两台服务器模型中计算稀疏直方图。
论文链接：https://dl.acm.org/doi/10.1145/3548606.3559383
这些协议从计算和通信的角度来看是高效的，比标准方法要好得多，并且结合了草图、密码学、多方计算以及DP等工具和技术。
虽然BERT 和Transformers 到目前为止已经使用DP 进行了训练，但了解大型语言模型(LLM) 中训练示例的记忆是评估其隐私的启发式方法。
论文链接：https://arxiv.org/abs/2207.00099
特别是，我们检查了LLM 在训练期间忘记（潜在地记住）训练示例的时间和原因，研究结果表明，可以通过牺牲后来看到的示例来观察到先前看到的示例的隐私优势。
论文链接：https://arxiv.org/abs/2202.07646
研究人员还量化了法学硕士发出记忆训练数据的效果。
Google 继续研究如何在2022 年改善在线市场。
例如，最近广告拍卖研究的一个重要领域是在线广告自动竞价的研究，其中大多数竞价是通过代理竞价者代表广告商优化更高级别的目标。用户、广告商、竞价者和广告平台导致了这一领域的一些问题。
继之前分析和改进自动竞价拍卖机制的工作之后，谷歌继续研究如何在自动化背景下改进在线市场，同时考虑到用户体验和广告预算等不同方面。
论文链接：https://arxiv.org/abs/2207.03630
结果表明，即使在非现实拍卖中，机器学习推荐和随机化技术的适当组合也可以有力地提高均衡自动出价算法的整体福利。
除了自动出价系统之外，谷歌还致力于复杂环境中的拍卖改进，例如买家由中介机构和多种广告格式代表的情况，其中每个广告可以以几种可能的变体形式显示。在最近的一项调查中，谷歌总结了相关工作。
论文链接：https://www.sigecom.org/exchanges/volume_20/2/BHAWALKAR.pdf
除了拍卖之外，谷歌还研究了合约在多代理和对抗环境中的使用。在线随机优化仍然是在线广告系统的重要组成部分，在最佳出价和预算节奏方面有着广泛的应用。
基于在线作业研究的悠久历史，研究人员最近发表了对双镜像下降的介绍，这是一种用于在线作业问题的新算法，该算法简单、稳健、灵活，并且能够抵抗各种对抗性和随机输入分布，并且可以优化经济效率之外的重要目标，例如公平。
结果还表明，可以通过将支出约束调整为日益流行的特殊结构回报来优化广告商价值，该结构具有广泛的应用范围，并且随着时间的推移已被用于帮助广告商通过更好的算法决策获得更多价值。
论文链接：https://arxiv.org/abs/2109.03173
此外，谷歌基于在机器学习、机制设计和市场互动方面的工作，研究了为非对称拍卖设计的变形金刚，为无悔学习的买家设计了效用最大化策略，并开发了新的学习算法来在拍卖中出价或定价。
复杂在线服务的一个关键组成部分是能够通过实验测量用户和其他参与者对新干预措施的反应。准确估计这些因果效应的一个主要挑战是处理这些实验的控制单元和治疗单元之间复杂的相互作用。效应（或干扰）。
论文链接：https://openreview.net/pdf?id=hqtSdpAK39W
结合图聚类和因果推理方面的专业知识，扩展了该领域之前的工作，改进了灵活响应模型和新实验设计下的结果。
论文链接：https://proceedings.neurips.cc/paper/2021/file/48d23e87eb98cc2227b5a8c33fa00680-Paper.pdf
当处理任务和度量测量发生在双向平台的同一侧时，可以更有效地减少这些交互。我们还展示了如何结合综合控制和优化技术来设计更强大的实验，特别是在小数据的情况下。向下。
Google 还通过解决长期存在的“开放问题”来继续基础算法研究。
论文链接：https://dl.acm.org/doi/pdf/10.1145/3519935.3520054
一篇简明的论文解决了一个有40 年历史的悬而未决的问题：是否存在一种机制，可以在买方价值弱于卖方成本时保证交易收益的恒定部分。
论文链接：https://dl.acm.org/doi/pdf/10.1145/3519935.3520011
另一篇论文获得了经典且经过深入研究的k 均值问题的最先进的近似，并且还改进了相关聚类的最佳近似，打破了2 的障碍近似因子。
他在动态数据结构方面的工作解决了最小成本和其他网络流量问题，并且在利用连续优化技术解决经典离散优化问题方面取得了突破性进展。
设计高效的算法和机制是Google 大型系统的关键组成部分，需要在考虑隐私和安全的情况下稳健地处理大规模数据。
指导思想是开发具有坚实理论基础的算法，可以有效地部署在生产系统中，此外，通过开放一些最新颖的开发并发布背后的先进算法，将其中的许多进步带到更广泛的社区他们。
在这篇博客中，谷歌研究人员讨论了隐私、市场算法、可扩展算法、基于图的学习和优化方面的算法进步。
随着我们迈向人工智能优先、更加自动化的谷歌，开发强大、可扩展和保护隐私的机器学习算法仍然是首要任务，保持开发新算法并更广泛部署它们的热情。
参考：
https://ai.googleblog.com/2023/02/google-research-2022-beyond-algorithmic.html
