2016年，Bill Cook和他的同事决定挑战一个问题，就是如何以最短的距离访问英国的每一家酒吧。他们列出了已知的24727家酒吧，并且迈开腿，真的去走遍这些酒吧。这是一次跨越45495239米，大概28269英里的步行之旅，比绕地球一圈还要长。其实Cook做了个弊，他没有真的走去每一家酒吧，他忽略了其中一些酒吧来让这次步行没那么夸张。这个事情在英国的媒体中宣传了之后，很多人在底下留言说：你没有来我家旁边的这个酒吧呀。于是，Cook和他的公司重新开始计划，将酒吧的名单增加到49687个，整体的旅行长度就达到了惊人的63739687米，也就是39606英里。但其实，相对于之前的那个旅行，这趟新的寻酒之旅其实只需要多走40%的距离就能达到两倍多数量的酒吧。
文章插图
这种酒吧遍历之旅在某种程度上就是旅行商问题的变种，也就是最著名的NP完全问题之一。通过所有49687家酒吧的可能游览次数约等于3加上后面211761个零这个量级。当然了，Cook的计算机不会搜索整个集合，而是使用了多种优化的技术。更令人印象深刻的是，这次旅行带有基于线性程序对偶性的最优性证明。除了旅行商问题之外，我们还看到了求解可满足性和混合整数规划方面的重大进步，也就是线性规划的一种变体，其中一些变量的解要求是整数。当我们使用高精度的启发式算法，使用快速的处理器、专用的硬件系统和分布式的云计算进行辅助的时候，人们通常可以解决实际中出现的具有好几万个变量和几十上百万个约束的问题。面对NP问题时，人们通常可以将NP问题表述为可满足性或混合整数规划问题，并将其扔给目前最好的求解器来借助计算机的力量，自动找到答案。这些工具已经成功用于电路和代码的验证、自动化测试、计算生物学、系统安全、产品和包装设计、金融交易，甚至是一些困难的数学问题求解之中了。人们通常无法忽视机器学习在近些年带来的革命性影响，尤其是神经网络。人工神经网络建模的概念基础，基本上是计算加权阈值函数。这种思想起源于1940年代Warren Mcculloch和Walter Pitts的工作。在1990年代，Yoshua Bengio、Geoffrey Hinton和Yann Lecun开发了反向传播算法，来将深度神经网络的层数加深，并得到非凡的结果。与此同时计算机硬件计算、存储等方面出现突破，那些更快、更加分布式的计算单元，那些专用的硬件和海量的数据有助于推动机器学习完成很多类似人类的功能。ACM认识到Bengio 、Hinton和LeCun的贡献，并在2018年为他们颁发了图灵奖。有的同学可能会问，机器学习怎么和P、NP问题相联系呢？奥卡姆剃刀说：如无必要，勿增实体。如果P=NP，我们可以用这个思想来创造强大的学习算法：找到与数据一致的最小电路。即便P≠NP，机器学习也可以学习并且近似这种思想，这就赋予它强大的能力。尽管如此，神经网络也可能不是真正的“最小”的电路，当然或许可能是尽量小的。今天我们所使用的深度学习方法通常是结构固定的，能够变动的都是神经元连接上的权重。为了能够实现足够泛化的表达能力，这些网络通常有几百上千的权重数量。这就限制了深度网络的能力（也就是不够简单）。它们可以在人脸识别上做的很好，但是无法根据示例学习乘法。让我们考虑二进制字符串的无限集上的分布场景。我们虽然不能拥有均匀分布，但是可以创建一种每个长度相同的字符串都有相同概率的分布。但是，有些字符比其他字符更重要。比如π的前一百万位数字比随机生成的一百万位数字更有意义。我们可能希望将更高的概率放在更有意义的字符上。现在我们有很多方法能够做到这点。实际上，已经有人发现了一种接近任何其他可计算分布的通用分布，这种分布与学习有很大的联系——例如，任何能够以小错误率学习这个分布的算法，将可以学习所有的可计算分布。
