引言
年前花了几个晚上读了 Steven Pinker 的 The Language Instinct1，本想整理出一篇读书笔记，但又觉得该书后半部分内容不是那么高分，所以写一篇笔记有点鸡肋。这两日又无事翻了翻 Scott Aaronson 的 Quantum Computing since Democritus2。两位也算是各自领域（Pinker 在语言学和实验心理学，Aaronson 在量子计算和复杂度理论）的大佬和“网红”了，没想到这两部书有些例子竟然有点关联，这里算是一个简短的笔记和思考。这篇文字可能混杂了哲学思辨，语言习得，机器学习，概率统计等方面的知识，不过门槛都比较低。
语言本能与奔跑的兔子
在平克的世界观里，语言是一种与生俱来的能力，这也是语言本能这一书题目的由来。其主要观察包括，世界各国语言的高度相似性，几乎相同的语法 parse tree 和词性分类，语言的克里奥尔化现象，语言精细程度与社会发展程度无关等事实。其中还有一个主要证据就是学习的不可能性。似乎只有先天基因搭好了大脑网络的链接框架，只预留出一些参数的自由度，通过后天输入来优化，才有可能学会语言。否则，如果没有充分的先天信息，仅靠后天的语料输入是无法学会语言的。这一学习的不可能性的例子就是所谓的 gavagai 难题，这一例子巧合的同时被 Pinker 和 Aaronson 在书中列举（虽然例子中的动物似乎不一样）。
Gavagai 难题的表述是这样的。假设你到了一个土著部落，你并不懂他们的语言，这时跑过去一只兔子，土著指着兔子大喊 gavagai。那么几乎所有人都会自然的推断出，这一土著语言中 gavagai 指的是兔子。但是 gavagai 为什么不能指的是跑着的兔子，白色的兔子，跑，周二的兔子，这只兔子自己的名字，被惊吓的出现在周二的奔跑的兔子或者只是站住的意思？事实上，这一词有无限的可能，如果大脑没有对语言通性的大量预设，是无法靠接受语料输入来习得语言的，甚至可以推论即使有无限长的时间和该部落互动，我们也无法习得该语言。这就是所谓的学习的不可能性。但事实显然不是这样的，不然那些做 field study 的语言学家和人类学家就都要失业了。事实就是，人类可以靠有限的语料输入来理解另一门语言，这也是平克坚持语言是一种本能，大部分语言的共性是先天的这一信念的主要证据之一。
牛顿的信念：从贝叶斯到奥卡姆
上面这一论证是有弱点的，gavagai 难题揭示的似乎不只是语言学习的不可能性，而是学习本身的不可能性。如果把这作为先天预设的证据，那么我们提前写在大脑的逻辑和本能数量就是非常巨大的（当然事实也可能是这样的）。另一个充分暴露这一点的例子来自 Aaronson。假设我们观察了500只乌鸦，并且他们都是黑色的。那么我们能总结出一条规律下一只乌鸦也是黑色吗？这一例子和我之前关于太阳升起问题写的贝叶斯推断小议异曲同工。我们已经观察到了10000天太阳照常升起了，那么按理论说可以根据贝叶斯学派的观点，给出明天太阳升起的概率，虽然不同的流派给出的明天太阳升起的概率略有不同，但基本上都是接近1的数值。不过如果有另一条规律是说“太阳只会连续升起10000天”，那么同样的我们之前10000天的观察都符合这一假设。根据完全相同的贝叶斯推断的分析，可以得出结论明天也极大概率符合这一假设，也就是太阳将不会升起。至此，就揭示出了概率分析对于学习的帮助是依赖于信念的。一定程度上，这就是奥卡姆剃刀原理，“同样可以解释所有现象的几个理论，需要假设最少的（最简洁的）那个最可能是对的”。因此支持明天太阳会照常升起的并不是贝叶斯，而是奥卡姆，因为太阳只会连续升起10000天比起太阳每天都升起是一个更复杂的理论。（你可能会说支持明天太阳升起的是牛顿，但事实是“万有引力定律”明天会照常起作用吗？这本质上总是一个问题，所以还是奥卡姆给出了明天太阳照常升起的终极裁定，巧合的是奥卡姆的威廉是个中世纪神学家）。物理定律不随时间变化只能是基于信念的，而非实验的，因为没有人可以做实验验证“明天”的事情。
不过真的是越简洁的理论就越接近真相吗，一定程度上我们不知道，我们只能说秉承这种信念我们没怎么吃过大亏。但这也不算什么证据，这正如 Aaronson 书里的这个细思恐极的笑话：
有一个星球的人相信反归纳推理：既然以前每天太阳都升起，那么明天太阳肯定不升起。毫无疑问，该星球上的人过的很惨，因为相信明天没有太阳，谁也不去种粮食，忍饥挨饿。有一天，一个人类到达他们星球，于是劝他们：“你们为什么会使用反归纳推理作为逻辑呢，看看你们过得有多惨！这逻辑根本就不成功啊。”
外星人回答：“就是因为反归纳推理从来没成功过啊！”
如果没看懂上面笑话的笑点和细思恐极之处，可以再读两遍，要是真没有这个慧根，这篇偏哲学的思考的文章就不需要看下去了。一定程度上，也许我们的逻辑体系，我们的一些看起来无法再 trivial 的原则和信念，就是那个星球上的反归纳推理罢了。或者我们也可以借助于人则原理来安慰自己，奥卡姆剃刀原理应该是没问题的。当然还有一个现在烂大街的名词也构成对奥卡姆的冲击，那就是黑天鹅，这和农场的火鸡，反归纳的外星人其本质上都是类似的想法，只不过问题根植的思维的深度不同。
一些关于学习的数学
让我们从另一个更务实的视角，对上面的学习过程进行重新的思考，来尝试理解我们究竟是怎么在似乎无穷无尽的可能规律中，通过少量样本，快速找到“正确”的那一个的。下面的数学理论，也可视为统计机器学习的滥觞之一。
假设我们大脑本来有非常多的概念，这些概念的集合记为 \(C\)。\(C\) 可以被看做婴儿先天带来的语言备选。每个概念是一个从句子到真值的映射，用来标记每个句子是否是符合语法的。比如 \(g\in C\)，那么 \(g\) 就代表了一种语言候选。\(g(x)=1\)，就说明 \(x\) 这句话在语言 \(g\) 中是正确，符合语法的。反之 \(g(x)=0\)。那么究竟 \(C\) 中的哪个语言候选对应了真实的语言呢，这就取决于语料输入。语料输入也是类似一个概念 \(S\)，是从句子映射到真值，这对应了父母谈话里符合语法的部分，和向婴儿强调的说的不对的部分。只不过其定义域不可能是全部句子，而只是句子的一个取样。我们想做的自然是通过 \(S\) 来找到 \(C\) 中可能性最大的语言候选，作为语言的近似，从而学到了这门语言。注意到 \(S\) 中的自变量句子是从某个分布 \(D\) 中独立取样的，这代表了该语言的人可能说出的话的一个分布（无论是对的还是错的，因为有些语法错误的话说出的概率也比其他错误出现频率高）。我们想做的就是找到一个概念 \(h\in C\), 使得
\[Pr_{x\sim D}(h(x)=f(x))\geq 1-\epsilon \label{1}\]其中 \(f(x)\) 就表达了语言真实的真值映射（句子 x 是否符合语法）。而 \(h(x)\) 是我们大脑预设的可能规律之一，也即 \(h\in C\)。我们有以下定理，想要 (1) 在至少 \(1-\delta\) 比例 \(x\sim D\) 的 sample 中成立，则需要学习的样本大小 \(m=\vert S\vert\) 为
\[m\geq \frac{1}{\epsilon}\log (\frac{\vert C\vert}{\delta}) \label{2}\]可以发现达到一定的预言精度情况下，我们需要学习的样本数目只是候选可能假设的对数数量级。这也一定程度上解释了为什么多项式数量的参数的神经网络可以识别指数数量级的图片。这一数学和重整化理论的看法也不谋而合，二者都可以对 why machine learning is so cheap 作出一定的解释。当然，如果大脑不预设一些 \(C\) 概念作为候选的话，那么假设 500 个 bit 作为句子的最大截断（考虑到一个字母就占据8bit，事实要大于这个值），那么 \(\{0,1\}^{500}\rightarrow\{0,1\}\), 一共有 \(\vert C\vert =2^{2^{500}}\) 个概念，即使取了对数，所要求的输入样本还是指数数量级。这侧面证明了，如果大脑没有一定的预设，(一些候选 \(C\))，我们是无法学会语言的，即使统计上学会语言的语料输入仅是候选概念的对数数量级。
这里的计算学习理论，是对平克的语言本能说的一个数学上的有力支持。其定量地刻画出了如果没有预设，语言学习的不可能性，和如果有了大脑预设之后，语言学习的可行性。你不需要接触过所有语料，也可以很精确的掌握一门语言，奥秘就在 (2) 里的对数。某种程度上，也可以从贝叶斯学派的视角来理解语言本能，只有有一个关于语言预设较好的先验分布，才可以通过少量样本，从无穷的可能中得出正确的后验。
最后注意到定理 (2) 的证明几乎是 trivial 的，只需考虑选出的候选概念 \(h\in C\)，可以在 \(m\) 个学习样本 \(S\) 给出正确的真值，但在总体的正确率小于 \(1-\epsilon\) 的情况的概率即可，这一概率恰好是 \(\delta\)，也即我们所能允许的错误范围。
这一学习的数学框架还有面向连续数据和量子数据的推广，因为这里想探讨的是两本书的交叉点，这里就不多讨论了，感兴趣的可以参考2和其中的相关文献。