广达杂志；资料来源：antoniart/Shutterstock
算法——允许程序对数据进行排序、过滤和组合等的代码块——是现代计算的标准工具。就像手表里的小齿轮一样，算法在更复杂的程序中执行定义明确的任务。
它们无处不在，部分正因为如此，它们随着时间的推移经过精心优化。例如，当程序员需要对列表进行排序时，他们会使用一种已经使用了几十年的标准“排序”算法。
现在，研究人员正在使用称为机器学习的人工智能分支重新审视传统算法。他们的方法被称为具有预测的算法，它利用了机器学习工具可以为传统算法处理的数据提供的洞察力。这些工具以一种真正的方式重新激发了对基本算法的研究。
麻省理工学院计算机科学家Piotr Indyk说，机器学习和传统算法是“两种截然不同的计算方式，而带有预测的算法是连接两者的一种方式”。 “这是一种将这两个完全不同的线程结合起来的方法。”
最近对这种方法的兴趣激增始于 2018 年，当时麻省理工学院计算机科学家Tim Kraska和谷歌研究人员团队发表了一篇论文。在其中，作者建议机器学习可以改进一种经过充分研究的传统算法，称为布隆过滤器，它解决了一个简单但令人生畏的问题。
想象一下，您管理公司的 IT 部门，您需要检查您的员工是否会访问存在安全风险的网站。天真地，您可能认为您需要根据已知站点的黑名单检查他们访问的每个站点。如果列表很大（互联网上不受欢迎的网站可能就是这种情况），问题就会变得难以处理——您无法在网页加载之前的很短的时间内对照庞大的列表检查每个网站。
布隆过滤器提供了一种解决方案，使您可以快速准确地检查任何特定站点的地址或 URL 是否在黑名单上。它通过本质上将巨大的列表压缩成一个较小的列表来提供一些特定的保证来做到这一点。
布隆过滤器永远不会产生误报——如果他们说网站不好，那就是坏的。但是，它们可能会产生误报，因此您的员工可能无法访问他们应该有权访问的某些站点。那是因为他们用一些准确性来换取大量的数据压缩——一种叫做“有损压缩”的技巧。 Bloom 过滤器对原始数据的压缩越多，精度越低，但节省的空间越多。
对于一个简单的布隆过滤器，每个网站都同样可疑，直到它被确认不在列表中。但并非所有网站都是平等的：有些网站比其他网站更有可能进入黑名单，这仅仅是因为他们的域名或 URL 中的单词等细节。人们直观地理解这一点，这就是为什么您可能会在单击 URL 之前阅读它们以确保它们是安全的。
Kraska 的团队开发了一种算法，也可以应用这种逻辑。他们称其为“学习型 Bloom 过滤器”，它将小型 Bloom 过滤器与循环神经网络 (RNN) 结合在一起——一种机器学习模型，可以了解恶意 URL 在暴露于数十万个安全和不安全网站后的样子。
当学习到的布隆过滤器检查一个网站时，RNN 首先行动并使用其训练来确定该网站是否在黑名单上。如果 RNN 说它在列表中，则学习的 Bloom 过滤器会拒绝它。但是，如果 RNN 说该站点不在列表中，那么小型 Bloom 过滤器就会转向，准确但不假思索地搜索其压缩网站。
通过将 Bloom 过滤器放在流程的最后并给予最终决定权，研究人员确保学习的 Bloom 过滤器仍然可以保证没有误报。但是因为 RNN 使用它所学到的东西对真阳性进行预过滤，所以小型 Bloom 过滤器更多地充当备份，也将其误报保持在最低限度。本来可以被更大的布隆过滤器阻止的良性网站现在可以通过更准确的学习布隆过滤器。实际上，Kraska 和他的团队找到了一种方法，可以利用两种经过验证但传统上相互独立的方法来解决同一问题，从而获得更快、更准确的结果。
Kraska 的团队表明新方法有效，但他们没有正式说明原因。这项任务落到了哈佛大学 Bloom 过滤器专家Michael Mitzenmacher的肩上，他认为 Kraska 的论文“创新且令人兴奋”，但从根本上来说也并不令人满意。 “他们进行实验说他们的算法效果更好。但这究竟是什么意思？”他问。 “我们怎么知道？”
2019 年，Mitzenmacher 提出了学习布隆过滤器的正式定义，并分析了它的数学特性，提供了一个准确解释其工作原理的理论。虽然 Kraska 和他的团队证明它可以在一种情况下工作，但 Mitzenmacher 证明它总是可以工作。
Mitzenmacher 还改进了学习到的 Bloom 过滤器。他展示了在流程中添加另一个标准 Bloom 过滤器，这一次是在 RNN 之前，可以预先过滤否定案例，并使分类器的工作更容易。然后，他使用他开发的理论证明了这是一种改进。
早期的预测算法沿着这条循环轨道前进——创新的想法，比如学习过的布隆过滤器，激发了严谨的数学结果和理解，这反过来又带来了更多的新想法。在过去的几年里，研究人员已经展示了如何将具有预测的算法整合到调度算法、芯片设计和DNA 序列搜索中。
除了性能提升之外，该领域还推进了一种越来越受欢迎的计算机科学方法：通过为典型用途设计算法来提高算法的效率。
目前，计算机科学家经常设计他们的算法以在最困难的情况下取得成功——一种由对手设计的试图难倒他们的情况。例如，想象一下试图检查一个网站关于计算机病毒的安全性。该网站可能是良性的，但它在 URL 和页面标题中包含“计算机病毒”。即使是复杂的算法也足以令人困惑。
Indyk 称这是一种偏执的方法。 “在现实生活中，”他说，“输入通常不是由对手产生的。”例如，员工访问的大多数网站并不像我们假设的病毒页面那么棘手，因此算法更容易对其进行分类。通过忽略最坏的情况，研究人员可以设计适合他们可能遇到的情况的算法。例如，虽然数据库目前平等对待所有数据，但具有预测的算法可能会导致数据库根据其内容和用途来构建其数据存储。
而这仍然只是开始，因为使用机器学习来增强其算法的程序通常只会以有限的方式这样做。与学习的布隆过滤器一样，这些新结构中的大多数只包含一个机器学习元素。 Kraska 设想一个完整的系统由几个独立的部分组成，每个部分都依赖于具有预测的算法，并且它们的交互由预测增强组件调节。
“利用这一点将影响许多不同的领域，”克拉斯卡说。