新智元报道
编辑：LRS
【新智元导读】在浮躁的机器学习领域，仍然有人致力于研究基础算法。
由Jeff Dean领衔的Google Research年终总结系列「Google Research, 2022 & beyond」第五期，本期的主题是算法上的进步（algorithmic advances），撰写作者是谷歌研究院的副总裁Vahab Mirrokni.
往期链接：
- 超详超硬Jeff Dean万字总结火热出炉！图解谷歌2022年AIGC、LLM、CV三大领域成就
- 谷歌2022年度回顾：让AI更负责任，主要做了4点微小的工作
- Jeff Dean发推：谷歌超硬年终总结「第三弹」来了！大力发展Jax
- 让大模型的训练和推理，比更快还更快！谷歌2022年终总结第四弹
稳健的算法设计是整个谷歌系统的基础，特别是对于机器学习和人工智能模型来说，稳健性显得更加重要。
因此，开发具有更高效率、更强性能以及更快速的算法仍然具有相当高的优先级，可以提升从搜索和广告到地图和 YouTube 等各种服务的能力。
Google Reserach一直走在该领域前沿，开发了许多创新性的算法，涉及的领域包括隐私安全的推荐系统、大规模机器学习的可扩展解决方案等。
下面介绍一些Google在2022年提出的最先进的技术包括可伸缩性、隐私、市场算法和算法基础等。
可伸缩算法: 图、聚类和优化
随着处理大规模数据集的需求增加，复杂算法的可伸缩性（scalability）和可靠性（reliability）在改进算法的可解释性、健壮性和速度上仍然具有较高优先级。
谷歌开发的新算法可用于处理各个领域的大型数据集，包括无监督和半监督学习、基于图的学习、聚类和大规模优化。
系统中的一个重要组成部分是建立一个相似图（similarity graph），节点为对象，边表示对象之间的相似度。为了提高可伸缩性和速度，邻接图应该是稀疏的。
谷歌提出了一种叫做 STAR 的两跳扩展技术（2-hop spanner technique），是一种高效的分布式图形生成策略，并展示了它如何在理论和实践上显著减少相似度计算的数量，在生成高质量的图形学习或聚类输出的同时生成更稀疏的图形。
论文链接：https://neurips.cc/Conferences/2022/ScheduleMultitrack?event=53141
比如说对于具有10T条边的图，在成对相似性比较和运行时间加速方面实现了约100倍的改进，而质量损失可以忽略不计，谷歌已经应用这个想法来开发用于度量和最小规模聚类的大规模并行处理算法。
论文链接：https://proceedings.mlr.press/v139/dhulipala21a.html
在广义的聚类背景下，谷歌开发了第一个具有线性时间层次聚集聚类(HAC)算法和第一个对数深度 HAC 并行算法 DBSCAN，该算法在100B 边图上实现了50倍的加速。
并且还针对不同类型的聚类问题设计了改进的次线性算法，如几何连接聚类、常数轮相关聚类和完全动态 k 聚类。
受到多核处理(例如 GBBS)成功的启发，研究人员开始着手开发能够在单个多核机器上处理具有100B 边的图的图挖掘算法，其中最大的难题是实现快速(例如，次线性)并行运行时间(例如，深度)。
在之前社区检测和相关聚类工作的基础上，谷歌开发了一个 HAC 算法叫做 ParHAC，具有可证明的多对数深度和近线性工作，并实现了50倍的加速。
论文链接：https://openreview.net/pdf?id=LpgG0C6Y75
例如，ParHAC 只需要约10分钟就可以在一个超过100B 边的图上找到一个近似的亲和层次结构，而在一台机器上找到完整的 HAC 则需要约3小时。
继之前在分布式 HAC 上的工作之后，使用这些多核算法作为分布式算法中的一个子例程来ter-scale的图。
2022年，谷歌在图形神经网络(GNN)方面也得到了一些进展。
论文链接：https://www.jmlr.org/papers/volume23/20-852/20-852.pdf
研究人员开发了一个基于模型的分类方法，统一了图学习方法，实验中还从数千个不同结构的图表中发现了对 GNN 模型的新思路，提出了一种新的混合体系结构，以克服现有 GNN 解决基本图问题(如最短路径和最小生成树)的深度要求。
此外，为了将这些成果带到更广泛的社区中，谷歌发布了用于在 TensorFlow (TF-GNN)中构建图形神经网络的旗舰建模库的三个版本，其中的亮点包括一个模型库和模型编排 API，这使得编写 GNN 解决方案变得更加容易。
在NeurIPS’20上的关于大规模图形挖掘和学习研讨会之后，谷歌在 ICML’22举办了一个关于基于图形的学习的研讨会，以及在 NeurIPS’22举办了一个关于 TensorFlow 中 GNN 的教程。
论文链接：https://dl.acm.org/doi/abs/10.1145/3474717.3483961
谷歌还提出了一个谷歌地图解决方案，可以有效地计算道路网络中的可选路线、持续故障(例如，道路关闭和突发事件等)。
文中还展示了该模型如何显著优于现实世界中的道路网络的最先进的plateau and penalty方法。
在优化方面，谷歌开源了 Vizier，一个强大的黑盒优化和超参数调优库。
研究人员还为线性规划(LP)解决方案开发了新的技术，解决了由于依赖矩阵分解而导致的可伸缩性限制，限制了并行性和分布式方法的发展。
代码链接：https://github.com/google/or-tools
为此，研究人员开源了一个称为原始-对偶线性规划(PDLP)的原始-对偶混合梯度(PDHG)解决方案，一个新的一阶求解器，可用于解决大规模 LP 问题。
PDLP 已经被用来解决现实世界中多达12B non-zeros的问题(内部分布式版本扩展到92B non-zeros)，PDLP 的有效性是理论发展和算法工程相结合的结果。
