理论文章要实验结果吗？（150914）

闵应骅

    本月的《美国计算机学会通讯》（CACM）发表一篇文章，讨论理论文章要不要实验数据，对我们颇有启发，特别是对追求论文的研究生和青年教师应该很有帮助。

    这故事是这样的。哈佛大学计算机科学系教授，ACM Fellow，Michael Mitzenmacher，他是搞算法的，投了一篇文章给一个理论方面的会议。这文章被送给斯坦福大学计算机系的Jeffrey Ullman去审。大家知道，Ullman是ACM Fellow，美国工程院院士，数据库方面绝对是大牛，我听过他关于数据结构的课。他建议作者去掉实验结果，那文章里包括了若干模拟结果。该文在研究动机里和演示结果中都有模拟结果。Ullman认为，模拟结果没有必要，而且降低了论文的档次。Mitzenmacher认为，实验数据对于说清他们的想法非常必要。但是，理论与实验之间存在隔阂。实验可能掩盖真实的想法，丢失了建造系统的框架。Mitzenmacher说，可是，当我给理论戴上帽子以后，除了改变了一些符号以外感觉也差不多。在许多理论的会议上，论文很少出现实验数据。它们不是说禁止用实验，而是许多评审人对加入实验数据表示怀疑，即使是关于算法的文章也是这样。我觉得，这有些过分。适当的实验可以说明这个工作和哪些实际相关联，而其他不关联。当然，不是所有的理论文章都需要实验结果。譬如提供某一个问题解的下界、纯粹数学的文章都不需要。下面是需要实验结果的一些原因。

1．实验数据表现对实际潜在的用处

   理想地说，任何理论成果都应该直接或间接地应用到计算机科学。实验结果使实际工作者更容易理解。理论工作者不一定是最高明的编程者，最短运行时间和最佳结果可以以后再说，但是，说明这想法可以实现，而且在合理时间内可以完成，对系统建设者是一种鼓励。

   改进计算机应用并不是理论计算机科学唯一的目的，但是一个主要目的。否则，计算机科学就变成了纯数学。计算机科学的活跃就是因为它与现实世界紧密相联。

2．实验数据提供对你的工作的验证

   搞数学的人不喜欢用实验结果来验证理论，实验数据验证不了理论，定理证明才是良药。但是，证明可能包含微妙的错误。Mitzenmacher曾经要一个学生做一篇关于马尔科夫链文章的模拟。那篇文章作者证明了一个静态平衡点是0.212….。而这个学生的模拟结果却是0.106….，正好差2倍。造成这个错误的原因是作者忽略了因子2，评审人也没看出来。从上下文来看，这不算一个严重错误。但这个例子表明模拟实验可以揭出错误。计算并不能完全验证理论结果是否正确，但是可以表明结果没有明显错误，而且读者希望看到这些模拟，使之更加具体。

3．实验结果常常能看出理论结果是否严密

   许多算法研究的文章中理论上估计了算法运行时间的上界和下界，它们一般不在一个数量级上。实例运行结果虽然不是最好或最坏的情况，但能提供一些实际运行的猜想。即使上下界很逼近，理论分析总是宽打的，一些常数因子的假设可能使你觉得该算法根本不实际，但它实际上是可用的。常数因子取10或者100，对理论证明没有影响，但实际算法应用并不会差一个数量级。近似算法提供最优结果的近似。理论分析告诉你这结果离真值差多远。实验结果能说明该近似算法在实际中有多大用。

4．实验数据分析促进对下一步问题的深刻理解

实验结果可以启发你进入新方向的想象。实验结果常常启发读者去想与之相关的重要的或新的问题。写下实验可以帮助读者理解理论结果是怎么出来的、实验是怎么做的，他们就可以开始他们自己的扩展和研究。理论研究不一定是从实际中提出来的，但实际意义仍然非常重要。现今的理论计算机科学低估了有实际背景的理论工作的意义。

理论家有志于在实际工作的会议上发表有实际意义的文章。譬如WWW会议，机器学习会议，计算与通信会议（INFOCOM）等等，发表一些既有理论也有实验结果的文章，产生了较大效果。这种会议能够提供连接理论和实践更直接的桥梁。许多信息表明理论工作者希望联系实际。研讨会一直在做这种努力。随着计算机科学领域的成熟，专门化在增长，理论与实践的联系更加困难，但是，理论认识和精心设计的实验之间的结合将有力地促进对计算的深入理解。

对于一般的科技论文，毫无疑问，没有实验数据的新方法说明不了你方法的有效性；没有实验数据的改进与推广说明不了是不是真改进了、真推广了。而对理论文章，按我的理解，没有定理的定义没有意义；没有定理的概念是空中楼阁，不叫理论。一个定理，从假设出发证明达到结论，读起来很过瘾，这就很具体。就是那些从概念到概念的议论和发挥，抽象得不得了，怎么理解都行，对实践没有任何意义，对理论也没有贡献。这个毛病在中国的科研人员中比较多，值得警惕，实验数据也许是克服这个毛病的方法。