如何实现学术论文？

译者注：

本文译自 Implementing academic papers: lessons learned from Elasticsearch and Lucene ，作者：Julie Tibshirani 。本文主要讨论了如何将学术论文中的前沿研究成果引入到实际的软件系统中，讨论了在此过程中需要注意的一些问题。

译者：arcsin2

在开发 Elasticsearch 时，我们偶尔会遇到一些重要的问题，它们没有简单或既定的解决方法。这时，会很自然地会问：“有没有学术论文解决了这个问题？”。有时候，学术工作会成为灵感的来源。我们可能会看到一篇提出新算法或数据结构的论文，然后想：“这会非常有用！” 以下是 Elasticsearch 和 Apache Lucene 如何融入学术工作的几个例子：

• HyperLogLog++ for cardinality aggregations
• C3 algorithm for adaptive replica selection
• Hierarchical Navigable Small World Graphs (HNSW) for nearest vector search in Lucene
• MIC statistic to improve machine learning classification
• Block-max WAND for faster top-hits retrieval in Lucene
• ... and many more

对于开发数据密集型系统的工程师来说，学术论文是一种宝贵的资源。但实现这些论文可能会令人生畏且容易出错——算法描述通常很复杂，并且经常省略重要的实用细节。并且测试是一个真正的挑战，例如：我们如何彻底测试一个其输出紧密依赖于数据集的机器学习算法？

本文分享了在软件应用中实现学术论文的策略。它借鉴了 Elasticsearch 和 Lucene 的实例，希望帮助其他工程师从我们的经验中学习。阅读这些策略时，您可能会想：“但这不过是软件开发而已！” 确实如此：作为工程师，我们已经有了正确的实践和工具，只需要适应新的挑战。

1. 像评估软件依赖一样评估论文

添加新的软件依赖需要仔细评估：如果依赖的包不正确、运行缓慢或不安全，我们的项目也可能受到影响。在引入依赖之前，开发者要确保评估其质量。

当你考虑实现学术论文时，这同样适用。人们可能会认为发表在学术论文上的算法一定是正确且表现良好的。但是，即使通过了审查程序，学术论文也可能存在问题：

• 正确性证明依赖于不切实际的假设；
• “实验”部分显示了比基线更好的性能，但这只适用于特定的数据集；

即使论文质量很高，它的方法也可能不适合你的项目。

当考虑是否要“依赖”一篇学术论文时，提出我们对软件包会问的同样问题是很有帮助的：

• 这个库是否被广泛使用并且经过了“实战测试”？→ 是否有其他包实现了这篇论文，并且对它们来说运行良好吗？
• 是否有性能基准测试？这些基准看起来准确和公正吗？→ 论文中包含了现实世界的实验吗？这些实验设计得好吗？
• 是否有足够大的性能提升，以接受算法的复杂性？→ 论文是否与一个强大的基线方法进行了比较？它比基线方法表现好多少？
• 这种方法是否能很好地集成到我们的系统中？→ 算法的假设和权衡是否符合我们的用例？

不知何故，当一个软件包与其竞争对手发布性能比较时，该软件包总是最快的！如果由第三方设计基准，它们可能会更加公平。同样的现象也适用于学术论文。如果一种算法不仅在原始论文中表现良好，而且在其他论文中作为强基线出现，那么它很可能是可靠的。

2. 创造性地进行测试

学术论文中的算法通常比我们日常遇到的算法具有更复杂的行为。也许它是一个近似算法，为了提高速度而牺牲准确性。或者它是一种机器学习方法，它处理大量数据集，并产生（有时是意想不到的）输出。如果我们不能简单地描述这些算法的行为，我们该如何为它们编写测试呢？

2.1 关注不变性

在设计单元测试时，通常我们会以示例为基础进行思考：如果我们给算法这个示例输入，它应该产生那个输出。不幸的是，对于大多数数学算法来说，基于示例的测试并不能充分覆盖它们的行为。

让我们考虑一下 C3 算法，Elasticsearch 使用它来确定哪个节点应该处理搜索请求。它使用一个微妙的公式对每个节点进行排名，这个公式考虑了节点的先前服务和响应时间，以及它的队列大小。仅仅测试几个例子并不能真正验证我们是否正确理解了这个公式。退一步考虑测试不变性是有帮助的：如果服务时间增加，节点的排名会降低吗？如果队列大小为 0，那么排名是否如论文中所说的由响应时间决定?

关注不变性可以在许多常见情况下有所帮助：

• 方法是否应该是顺序无关的？如果是，那么以不同的顺序传递输入数据应该产生相同的输出。
• 算法中的某个步骤是否产生类别概率？如果是，那么这些概率应该加起来等于 1。
• 函数是否关于原点对称？如果是，那么改变输入的符号应该只是改变输出的符号。

当我们最初实现 C3 算法时，我们在公式中犯了一个错误，不小心用响应时间的倒数代替了响应时间。这意味着速度较慢的节点可能会被排名更高！在修复这个问题时，我们确保添加了不变性检查，以防止未来的错误。

2.2 与参考实现比较

作者可能随论文一起发布了算法的实现。（如果论文包含实验，这种情况尤其可能，因为许多期刊要求作者发布代码以便重现结果。）你可以将你的方法与这个参考实现进行对比测试，以确保你没有遗漏算法的重要细节。

在开发 Lucene 的 HNSW 实现用于最近邻搜索时，我们对比了论文作者提供的参考库进行了测试。我们让 Lucene 和这个库都运行在同一个数据集上，比较了它们的结果准确性以及它们执行的计算次数。当这些数字非常接近时，我们知道 Lucene 忠实地实现了该算法。

当将一个算法集成到系统中时，你通常需要进行修改或扩展，比如将其扩展到多个核心，或者添加启发式方法以提高性能。最好是首先实现一个“普通”版本，然后与参考实现进行对比测试，再进行增量式的更改。这样你可以确信在进行定制之前已经捕捉到了所有关键部分。

2.3 与现有算法对决

本小节提出了测试不变量的另一个想法：将算法的输出与更简单、更容易理解的算法的输出进行比较。以 Lucene 中的 block-max WAND 算法为例，该算法通过跳过不可能出现在顶部结果中的文档来加速文档检索。虽然很难精确描述 block-max WAND 在每种情况下应该如何表现，但我们确实知道应用它不应该改变顶部结果！因此，我们的测试可以生成几个随机搜索查询，然后分别在应用和不应用 WAND 优化的情况下运行它们，并检查它们的结果是否始终匹配。

这些测试的一个重要方面是它们生成随机输入来进行比较。这可以帮助测试到你可能没有想到的情况，并揭示出意外的问题。例如，Lucene 的 BM25F 评分的随机比较测试帮助捕捉到了微妙边缘情况下的错误。给算法提供随机输入的想法与模糊测试（fuzzing）的概念密切相关，这是计算机安全中常用的一种测试技术。

Elasticsearch 和 Lucene 经常使用这种测试方法。如果你看到一个测试提到了两种算法之间的“对决”（TestDuelingAnalyzers, testDuelTermsQuery...），那么你就知道这种策略正在发挥作用。

3. 使用论文的术语

当其他开发者使用你的代码时，他们需要查阅论文来理解其细节。Elasticsearch 的 HyperLogLog++ 实现中的注释很好地说明了这一点：“试图在没有阅读论文的情况下理解这个类的功能被认为是冒险的。” 这个方法注释也树立了一个好榜样。它包含了指向学术论文的链接，并突出显示了算法在原始描述中所做的修改。

由于开发者将基于论文来理解代码，因此使用与论文完全相同的术语是有帮助的。由于数学符号简洁，这可能导致一些通常不会被认为是“良好风格”的名称，但在论文的上下文中却非常清晰。学术论文中的公式是你在 Elasticsearch 中遇到像 rS 和 muBarSInverse 这样神秘变量名的少数情况之一。

4. 邮件联系论文作者

当你在研究一篇难懂的论文时，你可能会花费数小时去琢磨一个公式，不确定是自己理解错了还是论文中存在打字错误。如果是开源项目，你可以在GitHub或StackOverflow上提问。但对于学术论文，你可以向哪里求助呢？作者们似乎很忙，可能会被你的邮件惹恼。

相反，许多学者喜欢听到他们的想法被付诸实践，并乐于通过电子邮件回答问题。如果你在他们熟悉的产品上工作，他们甚至可能会在他们的网站上列出这个应用！

学术界也越来越多地使用软件开发中的许多相同工具来公开讨论论文。如果一篇论文附带了软件包，你可能会在 GitHub 上找到关于常见问题的解答。像“理论计算机科学”和“交叉验证”这样的 Stack Exchange 社区也包含了关于热门论文的详细讨论。一些会议也开始在线发布所有论文审稿意见。这些评审包含了与作者的来回讨论，可以揭示关于方法的有用见解。

5. 未完待续

本文聚焦于选择学术论文并正确实施的基本要点，但并未涵盖实际部署算法的所有方面。例如，如果算法只是复杂系统中的一个组件，我们如何确保对组件的更改导致端到端的改进？如果整合算法需要大量修改或扩展，而这是原始论文没有涉及到的呢？这些都是我们希望在以后的文章中做更多分享的重要话题。