谷歌2022年终总结第五弹真正的算法工程师都在研究啥？

　　编辑：LRS【新智元导读】在浮躁的机器学习领域，仍然有人致力于研究基础算法。
　　由JeffDean领衔的GoogleResearch年终总结系列GoogleResearch，2022beyond第五期，本期的主题是算法上的进步（algorithmicadvances），撰写作者是谷歌研究院的副总裁VahabMirrokni。
　　往期链接：超详超硬JeffDean万字总结火热出炉！图解谷歌2022年AIGC、LLM、CV三大领域成就谷歌2022年度回顾：让AI更负责任，主要做了4点微小的工作JeffDean发推：谷歌超硬年终总结第三弹来了！大力发展Jax让大模型的训练和推理，比更快还更快！谷歌2022年终总结第四弹
　　稳健的算法设计是整个谷歌系统的基础，特别是对于机器学习和人工智能模型来说，稳健性显得更加重要。
　　因此，开发具有更高效率、更强性能以及更快速的算法仍然具有相当高的优先级，可以提升从搜索和广告到地图和YouTube等各种服务的能力。
　　GoogleReserach一直走在该领域前沿，开发了许多创新性的算法，涉及的领域包括隐私安全的推荐系统、大规模机器学习的可扩展解决方案等。
　　下面介绍一些Google在2022年提出的最先进的技术包括可伸缩性、隐私、市场算法和算法基础等。
　　可伸缩算法：图、聚类和优化
　　随着处理大规模数据集的需求增加，复杂算法的可伸缩性（scalability）和可靠性（reliability）在改进算法的可解释性、健壮性和速度上仍然具有较高优先级。
　　谷歌开发的新算法可用于处理各个领域的大型数据集，包括无监督和半监督学习、基于图的学习、聚类和大规模优化。
　　系统中的一个重要组成部分是建立一个相似图（similaritygraph），节点为对象，边表示对象之间的相似度。为了提高可伸缩性和速度，邻接图应该是稀疏的。
　　谷歌提出了一种叫做STAR的两跳扩展技术（2hopspannertechnique），是一种高效的分布式图形生成策略，并展示了它如何在理论和实践上显著减少相似度计算的数量，在生成高质量的图形学习或聚类输出的同时生成更稀疏的图形。
　　论文链接：https：neurips。ccConferences2022ScheduleMultitrack？event53141
　　比如说对于具有10T条边的图，在成对相似性比较和运行时间加速方面实现了约100倍的改进，而质量损失可以忽略不计，谷歌已经应用这个想法来开发用于度量和最小规模聚类的大规模并行处理算法。
　　论文链接：https：proceedings。mlr。pressv139dhulipala21a。html
　　在广义的聚类背景下，谷歌开发了第一个具有线性时间层次聚集聚类（HAC）算法和第一个对数深度HAC并行算法DBSCAN，该算法在100B边图上实现了50倍的加速。
　　并且还针对不同类型的聚类问题设计了改进的次线性算法，如几何连接聚类、常数轮相关聚类和完全动态k聚类。
　　受到多核处理（例如GBBS）成功的启发，研究人员开始着手开发能够在单个多核机器上处理具有100B边的图的图挖掘算法，其中最大的难题是实现快速（例如，次线性）并行运行时间（例如，深度）。
　　在之前社区检测和相关聚类工作的基础上，谷歌开发了一个HAC算法叫做ParHAC，具有可证明的多对数深度和近线性工作，并实现了50倍的加速。
　　论文链接：https：openreview。netpdf？idLpgG0C6Y75
　　例如，ParHAC只需要约10分钟就可以在一个超过100B边的图上找到一个近似的亲和层次结构，而在一台机器上找到完整的HAC则需要约3小时。
　　继之前在分布式HAC上的工作之后，使用这些多核算法作为分布式算法中的一个子例程来terscale的图。
　　2022年，谷歌在图形神经网络（GNN）方面也得到了一些进展。
　　论文链接：https：www。jmlr。orgpapersvolume232085220852。pdf
　　研究人员开发了一个基于模型的分类方法，统一了图学习方法，实验中还从数千个不同结构的图表中发现了对GNN模型的新思路，提出了一种新的混合体系结构，以克服现有GNN解决基本图问题（如最短路径和最小生成树）的深度要求。
　　此外，为了将这些成果带到更广泛的社区中，谷歌发布了用于在TensorFlow（TFGNN）中构建图形神经网络的旗舰建模库的三个版本，其中的亮点包括一个模型库和模型编排API，这使得编写GNN解决方案变得更加容易。
　　在NeurIPS’20上的关于大规模图形挖掘和学习研讨会之后，谷歌在ICML’22举办了一个关于基于图形的学习的研讨会，以及在NeurIPS’22举办了一个关于TensorFlow中GNN的教程。
　　论文链接：https：dl。acm。orgdoiabs10。11453474717。3483961
　　谷歌还提出了一个谷歌地图解决方案，可以有效地计算道路网络中的可选路线、持续故障（例如，道路关闭和突发事件等）。
　　文中还展示了该模型如何显著优于现实世界中的道路网络的最先进的plateauandpenalty方法。
　　在优化方面，谷歌开源了Vizier，一个强大的黑盒优化和超参数调优库。
　　研究人员还为线性规划（LP）解决方案开发了新的技术，解决了由于依赖矩阵分解而导致的可伸缩性限制，限制了并行性和分布式方法的发展。
　　代码链接：https：github。comgoogleortools
　　为此，研究人员开源了一个称为原始对偶线性规划（PDLP）的原始对偶混合梯度（PDHG）解决方案，一个新的一阶求解器，可用于解决大规模LP问题。
　　PDLP已经被用来解决现实世界中多达12Bnonzeros的问题（内部分布式版本扩展到92Bnonzeros），PDLP的有效性是理论发展和算法工程相结合的结果。
　　隐私和联邦学习
　　在提供高质量服务的同时尊重用户隐私仍然是所有Google系统的首要任务，该领域的研究涉及许多产品，并使用了来自差分隐私（differentialprivacy，DP）和联邦学习的原则。
　　首先，为了解决用DP训练大型神经网络的问题，研究人员在算法上取得了一些进展。
　　在早期工作的基础上，继续开发了一个基于DPFTRL算法的DP神经网络，用于矩阵分解的算法DPFTRL。
　　论文链接：https：arxiv。orgpdf2103。00039。pdf
　　这项工作表明，人们可以设计一个数学程序，以优化超过一个可能的DP机制的大集，以找到那些最适合特定的学习问题。
　　在神经网络和核方法的DP学习中，研究人员还建立了与输入特征维数无关的边界保证，并且进一步将这个概念扩展到更广泛的机器学习任务，以不到原来1300的计算量就可以匹敌基线的性能。
　　对于大型模型的微调，研究人员认为，一旦预训练后，这些模型（甚至与DP）基本上操作在一个低维子空间，从而绕过了DP强加的维数灾难。
　　在算法方面，为了估计一个高维分布的熵，可以得到局部DP机制（即使每个样本只有一个比特可用也能工作）和有效的shuffleDP机制。
　　论文链接：https：arxiv。orgabs2210。15178
　　研究人员提出了一种更加精确的方法来同时以私密的方式估计数据库中最受欢迎的项目，并在Plume库中应用了这种方法。
　　此外，在近似演算法计算（MPC）模型中展示了接近最佳的DP集群大规模并行处理机，进一步改进了以前在可伸缩和分布式设置方面的工作。
　　论文链接：https：arxiv。orgabs2107。14527
　　另一个有前景的研究方向是隐私和流媒体的交叉，研究人员提出了一个近似最优的近似空间权衡私有频率矩和一个新的算法私有计数不同的元素在滑动窗口流模型，还提出了一个研究对抗流（adversarialstreaming）的通用混合框架。
　　针对安全性和隐私性交叉的应用程序，谷歌开发了安全、私有和通信效率高的新算法，用于测量交叉出版商的覆盖范围和频率。
　　世界广告商联合会（WorldFederationofAdvertisers）已经采用这些算法作为他们测量系统的一部分，在后续的工作中，研究人员还开发了新的协议，是保证安全的且私有的，用于在DP的两服务器模型中计算稀疏直方图。
　　论文链接：https：dl。acm。orgdoi10。11453548606。3559383
　　从计算和通信的角度来看，这些协议都是高效的，比标准方法要好得多，并且结合了草图、密码学和多方计算以及DP等工具和技术。
　　虽然目前已经用DP训练了BERT和变压器，但理解大语言模型（LLM）中的训练样例记忆是评估其隐私性的一种启发式方法。
　　论文链接：https：arxiv。orgabs2207。00099
　　特别是研究了LLM在训练中忘记（潜在记忆）训练例子的时间和原因，研究结果表明，以前看到的例子可能会以后看到的例子为代价来观察隐私的好处。
　　论文链接：https：arxiv。orgabs2202。07646
　　研究人员还量化了LLM发出记忆训练数据的程度。
　　市场算法与因果推理
　　谷歌在2022年继续研究如何改善在线市场（onlinemarketplaces）。
　　例如，最近广告拍卖研究的一个重要领域是自动投标在线广告的研究，其中大多数投标是通过代理投标人，代表广告商优化更高层次的目标。用户、广告商、投标人和广告平台，导致这个领域存在一些问题。
　　继之前分析和改进自动竞价拍卖机制的工作之后，谷歌继续研究如何在自动化背景下改进在线市场，同时考虑到了不同方面，如用户体验和广告预算。
　　论文链接：https：arxiv。orgabs2207。03630
　　研究结果表明，适当结合机器学习的建议和随机化技术，即使在非真实的拍卖，可以有力地改善整体福利在均衡的自动竞价算法。
　　除了自动竞价系统，谷歌还研究了复杂环境下的拍卖改进措施，例如，买家由中介代表，多种告形式，每个广告可以显示在几个可能的变体。在最近的一篇survey中，谷歌总结了相关工作。
　　论文链接：https：www。sigecom。orgexchangesvolume202BHAWALKAR。pdf
　　除了拍卖，谷歌还研究了合同在多代理人和对抗性环境中的使用，在线随机优化仍然是在线广告系统的重要组成部分，在最优投标和预算节奏方面有着广泛的应用。
　　在长期的在线分配研究的基础上，研究人员最近发表了关于双镜像下降（dualmirrordescent）的介绍，一种简单、健壮和灵活的在线分配问题的新算法，可以抵抗广泛的对抗性和随机输入分布，并且可以优化经济效率之外的重要目标，如公平性。
　　结果还表明，通过裁剪双镜下降到日益流行的特殊结构回报的支出约束，可以优化广告客户的价值，其有着广泛的应用，并且随着时间的推移已经被用来帮助广告商通过更好的算法决策获得更多的价值。
　　论文链接：https：arxiv。orgabs2109。03173
　　此外，根据在机器学习、机制设计和市场相互作用方面的工作，谷歌研究了非对称拍卖设计的Transformer，为noregret学习的买家设计了效用最大化策略，并开发了新的学习算法来出价或在拍卖中定价。
　　复杂的在线服务的一个关键组成部分是能够通过实验测量用户和其他参与者对新干预措施的反应，准确估计这些因果效应的一个主要挑战是处理这些实验的控制单元和治疗单元之间的复杂相互作用（或干扰）。
　　论文链接：https：openreview。netpdf？idhqtSdpAK39W
　　将图形聚类和因果推理专业知识结合起来，扩展了之前在这个领域的工作成果，在灵活的响应模型和新的实验设计下改进了结果。
　　论文链接：https：proceedings。neurips。ccpaper2021file48d23e87eb98cc2227b5a8c33fa00680Paper。pdf
　　当treatment任务和度量测量发生在二分平台的同一侧时，可以更有效地减少这些相互作用，文中还展示了如何将综合控制和优化技术相结合来设计更强大的实验，特别是在小数据情况下。
　　算法基础和理论
　　谷歌还通过解决长期存在的开放问题来继续基础算法研究。
　　论文链接：https：dl。acm。orgdoipdf10。11453519935。3520054
　　一篇简明扼要的论文解决了一个40年前的悬而未决的问题：是否存在一种机制，在买方价值弱于卖方成本的情况下，保证交易收益的一部分不变。
　　论文链接：https：dl。acm。orgdoipdf10。11453519935。3520011
　　另一篇论文得到了经典的和高度研究的k均值问题的最新近似，还改进了相关聚类的最佳逼近，突破了2的障碍逼近因子。
　　并且在动态数据结构方面的工作解决了最小成本和其他网络流量问题，在采用连续优化技术解决经典的离散优化问题方面取得了突破性进展。
　　总结
　　设计有效的算法和机制是谷歌大规模系统的关键组成部分，这些系统需要以关键的隐私和安全考虑来稳健地处理大规模数据。
　　指导思想是开发具有坚实理论基础的算法，这些算法可以有效地部署在产品系统中，此外，通过开放一些最新颖的开发和发布它们背后的高级算法，将许多这些进步带给了更广泛的社区。
　　在这篇博客中，谷歌的研究人员讨论了算法在隐私、市场算法、可扩展算法、基于图表的学习和优化方面的进步。
　　随着朝着人工智能优先、自动化程度更高的谷歌迈进，开发健壮、可扩展和保护隐私的机器学习算法仍然是当务之急，对开发新的算法和更广泛地部署保持热情。
　　参考资料：
　　https：ai。googleblog。com202302googleresearch2022beyondalgorithmic。html