Braess 悖论

经济学上有个著名的悖论:Braess 悖论,是一个数学家 Braess 提出来的。他构造了一个精辟的例子指出,你给一个交通网络上增加一条路(并且保持别的路不变),有可能反而会使得整个路网的交通效率下降。

这个巧妙的例子是这样设计的。从起点到终点有两条路,一条经过A,一条经过B。

从起点到A是小路,通行时间和车流量成正比,等于车流量T除以带宽100。从起点到B是大路,固定要耗费45分钟。从A或B到终点也一样,只是顺序刚好反过来。

假定每天有4000辆车要从起点去终点。因为两条路本质上是一样的,很自然两条路就会各有2000辆车。最后每辆车花的时间都等于 2000/100+45=65分钟。

现在你在A和B之间修一个虫洞,带宽无限,耗时为0。会发生什么事呢?听起来这是净利好。

这时候起点的所有车,不管本来是要走A 还是B,都会选择走到A,因为即使所有人都挤在上面那条路,到A也最多需要4000/100=40分钟,然后从A到B需要0分钟,这还是比从起点直接去B要快。那直接走B无论如何都显得很蠢。

然后等所有车到了A点之后,又因为同样的原因都会选择先走到B再去终点,因为这样最多也只需要40分钟,还是比直接走到终点快。

但这样一来,最后所有车都花了4000/100+4000/100=80分钟。所有人都慢了15分钟。

为什么?

在这个例子里,多出来的这条路有可能会因为显得局部优势,从而诱导更多的司机选择这条他们本来未必会选的路,其结果是恶化了整体的最优交通分布。或者再确切一点说,这个捷径起到的作用是吸引大家选择了一系列局部上的最优解,但局部上的最优解联在一起并不等于全局最优解。每一步你都觉得自己赢了,但每一步都限缩了下一步的可能性。最终你在自己一直赢的路上花了更多的时间和成本。并且即使你看到了这一点也还是很难逃脱。

你最终陷在了自己的选择里。

这个悖论经常被用来解释交通网络里(以及一切复杂性社会现象里都可能出现的)诱导需求现象:某个地方因为交通拥堵,所以花大力气高成本把高速拓宽了一倍,结果交通还是照样拥堵。这并不是因为修路造成经济发展(经济发展没那么快跟上来),而是纯粹的数学效应。一百年前的纽约传奇规划师 Robert Moses 用了一辈子终于发现了这个痛苦的事实:

他修了 Triborough Bridge 缓解 Queensborough Bridge 的拥堵,又修了 Bronx-Whitestone Bridge 缓解 Triborough Bridge 上的拥堵,然后观察所有三座桥上的交通流量,直到所有三座桥都像以前一样拥挤。为缓解拥堵而修建的高速公路越多,就会有越多的汽车涌入其中并造成拥堵,从而迫使建设更多的高速公路——这将产生更多的交通量,成为一个不断扩大的螺旋。

当你往一个社会问题上扔进去无穷无尽的资源然后发现问题似乎永远存在的时候都应该想想自己是不是掉进了这个坑里。

关于 AlphaGo 论文的阅读笔记

2016 年 1 月 28 日,Deepmind 公司在 Nature 杂志发表论文 Mastering the game of Go with deep neural networks and tree search,介绍了 AlphaGo 程序的细节。本文是对这篇论文的阅读笔记,以及关于人工智能和围棋进一步的一些想法。

声明:我是数学 PhD 和软件工程师,但不是人工智能领域的专家。我也不会下围棋。

一、

AlphaGo 总体上由两个神经网络构成,以下我把它们简单称为「两个大脑」,这并非原文中的提法,只是我的一个比喻。

第一个大脑(Policy Network)的作用是在当前局面下判断下一步可以在哪里走子。它有两种学习模式:

一个是简单模式,它通过观察 KGS(一个围棋对弈服务器)上的对局数据来训练。粗略地说:这可以理解为让大脑学习「定式」,也就是在一个给定的局面下人类一般会怎么走,这种学习不涉及对优劣的判断。

另一个是自我强化学习模式,它通过自己和自己的海量对局的最终胜负来学习评价每一步走子的优劣。因为是自我对局,数据量可以无限增长。

第二个大脑(Value Network)的作用是学习评估整体盘面的优劣。它也是通过海量自我对局来训练的(因为采用人类对局会因为数据太少而失败)。

在对弈时,这两个大脑是这样协同工作的:

第一个大脑的简单模式会判断出在当前局面下有哪些走法值得考虑。

第一个大脑的复杂模式通过蒙特卡洛树来展开各种走法,即所谓的「算棋」,以判断每种走法的优劣。在这个计算过程中,第二个大脑会协助第一个大脑通过判断局面来砍掉大量不值得深入考虑的分岔树,从而大大提高计算效率。

与此同时,第二个大脑本身通过下一步棋导致的新局面的优劣本身也能给出关于下一步棋的建议。

最终,两个大脑的建议被平均加权,做出最终的决定。

在论文中一个有趣的结论是:两个大脑取平均的结果比依赖两者各自得出的结果都要好很多。这应当是让 AlphaGo 表现出和人类相似性的关键所在。

二、

如果我是这篇论文的审稿人,我会对论文提出下面这些问题和评论:

首先,这些神经网络训练在很大程度上是通过自我对局来实现的。这既是某种优势(按照 Facebook 人工智能研究员田渊栋的说法,几千万自我对局这种规模是相当惊人的数据量),某种程度上来说也是不得已而为之,因为人类对局的总数实在太少,会导致机器学习中常见的过度拟合问题。

但是这样是否有可能造成自我设限乃至画地为牢的后果?这同时牵涉到人们对神经网络学习过程的理解和对围棋本身的理解。一方面,神经网络本身是否包容一定程度的「think out of the box」的能力,这固然取决于具体的神经网络算法,但也确实是人们对神经网络方法的一个本质困惑。另一方面,因为 AlphaGo 最基础的定式仍然是来源于人类对局,因此,这个问题依赖于人类棋手本身是否已经穷尽了围棋中所有有意义的基本定式。

(作为一个案例,在 AlphaGo 和樊麾的第二盘对局中,很多人都注意到 AlphaGo 走了一个不标准的大雪崩定式,这是说明 AI 学错了呢,还是它发现这是更好的走法?)

其次,这两个大脑的工作方式确实和人类很相似,一个判断细部,一个纵览全局。但 AlphaGo 最终的结合两者的方式相当简单粗暴:让两者各自评估一下每种可能的优劣,然后取一个平均数。这可绝不是人类的思维方式。

对人类来说,这两种思考问题的方式的结合要复杂的多(不仅仅是在围棋中是这样)。人们并不是总是同时对事态做出宏观和微观的判断,而是有时候侧重于大局,有时候侧重于细部。具体的精力分配取决于事态本身,也取决于人在当时的情绪、心理和潜意识应激反应。这当然是人类不完美之处,但也是人类行为丰富性的源泉。

而 AlphaGo 固然体现出一定的大局观,但从具体算法看来,它在为了宏观优势做出局部牺牲这方面的能力和人类完全不能相提并论。AlphaGo 引入整体盘面评估确实是它胜于许多别的围棋 AI 的地方,但从根本上来说,这只是人们让 AI 具有「战略思维」的尝试的第一步,还有太多可以改进的可能性。

最后,和很多别的围棋 AI 一样,当 AlphaGo 学习盘面判断的时候,采用的是图像处理的技术,也就是把围棋棋盘当做一张照片来对待。这当然在技术上是很自然的选择,但是围棋棋局究竟不是一般意义上的图案,它是否具有某些特质是常见的图像处理方法本身并不擅长处理的呢?

三、

为什么要让人工智能去下围棋?有很多理由。但在我看来最重要的一个,是能够让我们更深入地理解智能这件事的本质。

神经网络和机器学习在过去十年里跃进式的发展,确实让 AI 做到了许多之前只有人脑才能做到的事。但这并不意味着 AI 的思维方式接近了人类。而且吊诡的是,AI 在计算能力上的巨大进步,反而掩盖了它在学习人类思维方式上的短板。

以 AlphaGo 为例。和国际象棋中的深蓝系统相比,AlphaGo 已经和人类接近了许多。深蓝仍然依赖于人类外部定义的价值函数,所以本质上只是个高效计算器,但 AlphaGo 的价值判断是自我习得的,这就有了人的影子。然而如前所述,AlphaGo 的进步依赖于海量的自我对局数目,这当然是它的长处,但也恰好说明它并未真正掌握人类的学习能力。一个人类棋手一生至多下几千局棋,就能掌握 AlphaGo 在几百万局棋中所训练出的判断力,这足以说明,人类学习过程中还有某种本质是暂时还无法用当前的神经网络程序来刻画的。

(顺便提一句,很多评论认为 AlphaGo 能够通过观察一个特定棋手的对局来了解他的棋风以做出相应的对策。至少从论文来看,这几乎确定是不可能的事。一个棋手的对局数对 AlphaGo 来说实在太少,无从对神经网络构成有效的训练。观察和总结一个人的「棋风」这件事仍然是人类具有完全优势的能力,对电脑来说,这恐怕比赢棋本身还更难一些。)

这当然不是说,AlphaGo 应该试图去复刻一个人类棋手的大脑。但是 AlphaGo 的意义当然也不应该仅仅反映在它最终的棋力上。它是如何成长的?成长曲线具有什么规律?它的不同参数设置如何影响它的综合能力?这些不同参数是否就对应了不同的棋风和性格?如果有另一个不同但水平相当的 AI 和它反复对弈,它能否从对方身上「学到」和自我对弈不同的能力?对这些问题的研究和回答,恐怕比单纯观察它是否有朝一日能够超越人类要告诉我们多得多的知识。

因此,即使 AlphaGo 在三月份战胜了李世乭,在我看来也是另一扇大门的开启而非关闭。事实上,即使就围棋发展本身而论,如果把 AlphaGo 的两个大脑以如此简单的方式线性耦合起来就能胜过人类,那只能说明人们对围棋的规律还有太多值得探索的空间。

而对人工智能领域来说,AlphaGo 和一切神经网络一样,本质上还只是个大黑盒,我们能观察到它表现出的巨大能力,但对它究竟是如何「思考」的这件事依然所知甚少。在工程上,这是个伟大的胜利。在科学上,这只是万里长征的第一步而已。


AlphaGo 项目主页:http://www.deepmind.com/alpha-go.html

Nature 论文:http://www.nature.com/nature/journal/v529/n7587/full/nature16961.html

Nature 报道:http://www.nature.com/news/google-ai-algorithm-masters-ancient-game-of-go-1.19234

Dan Maas 对论文的浅显总结:http://www.dcine.com/2016/01/28/alphago/

关于相邻素数之差的笔记(张益唐及其他)

\{d_n\} 为第 n+1 个素数和第 n 个素数之差。数列 \{d_n\} 和素数数列一样有很多有趣的性质和猜想。其中最古老的一个是:

猜想:2\{d_n\} 中出现过无穷次。

这是孪生素数猜想的另一种表述形式。1849 年,Polignac 把这个猜想推广为:

猜想:任意偶数都在 \{d_n\} 中出现过无穷次。

如果记所有在 \{d_n\} 中出现过无穷次的偶数的集合为 S,则上述两则猜想可以分别表述为 S 包含 2 以及 S 包含所有偶数。但长期以来人们甚至不知道 S 是否空集。直到今年张益唐第一次证明了:

定理:S 不是空集,且其最小值不大于 7\times 10^7

事实上,7\times 10^7 这一下界只是个粗略的估计。在张的论文发表后的一个月内,它就已经被迅速改进为 4\times 10^5,下降了一百倍还多。

Pintz 指出,在张益唐的结论和他所用的工具的基础上,人们实际上可以立刻得到更强的结论:

定理:存在一个常数 C 使得每 C 个连续偶数中就有一个属于 S。即 S 不但非空,且其在自然数中的密度是正的。

容易看出,如果 Polignac 的猜想是对的,则意味着 \{d_n\} 是一个震荡非常剧烈的数列,不断交替出现很大的数和很小的数。这令人自然猜想这是否也能归纳为一则定理。事实上,Erdős 和 Turán 在 1948 年确实证明了:

定理:\{d_n\} 中上升和下降的相邻项都出现过无穷次。

但这只说明 \{d_n\} 确实在震荡,关于震荡的幅度,Erdős 在 1955 年猜测它会非常大:\{d_{n+1}/d_n\} 的下界趋于 0,上界趋于 \infty。同样是在张益唐的结论和他所用的工具的基础上,Pintz 证明了这个猜想不但是对的,而且很强:

定理:\{d_{n+1}/d_n\} 的下界趋于 0 的速度快于 \log^{-1}n,上界趋于 \infty 的速度快于 \log n

用 Pintz 本人的话说:在刚刚过去的几个月里,一系列十年前会被认为是科幻小说的定理都被证明了。