贝叶斯认知模型  逆向工程思维19

贝叶斯认知模型 逆向工程思维

Bayesian Models of CognitionReverse Engineering the Mind

19 作为程序的贝叶斯推断学习

https://dokumen.pub/bayesian-models-of-cognition-reverse-engineering-the-mind-1nbsped-9780262049412-9780262381048-9780262381055.html

第19章题为“ 作为程序的贝叶斯推断学习 ”（Learning as Bayesian Inference over Programs），其核心在于将人类认知建模为在 程序空间 中进行贝叶斯推理的过程。本章重点可概括如下：

1. 核心主张：认知即程序归纳

• 人类学习不仅是对统计规律的拟合，更是对 生成性程序 （generative programs）的发现。

• 程序能简洁、组合式地表达复杂知识（如计数、逻辑、语言、因果等），契合人类认知的 组合性 （compositionality）和 系统性 。

• 使用 上下文无关文法 （CFG）或 概率文法 定义合法程序的结构。

• 引入 类型系统 （如简单类型、多态类型、依赖类型）确保语义一致性，并作为强大的 归纳偏置 ，大幅缩小搜索空间。

• 支持 变量、抽象、递归、条件分支 等编程构造，使模型能表达丰富认知操作。

• 先验 P(h) ：偏好短小、简洁的程序（奥卡姆剃刀），通常由文法生成概率或程序长度决定。
• 似然 P(d | h)：处理程序确定性与数据噪声之间的张力，例如：

• • 在列表任务中引入编辑距离或末尾扰动噪声；

  • 在语义任务中采用“规模原则”（size principle）避免平凡解。

• 使用 Metropolis-Hastings MCMC 在程序空间中采样，通过 子树替换 等结构保持操作实现局部搜索。

• 强调程序空间的 离散性 与 多峰性 ：学习表现为在不同“行为模式”间的跳跃，而非连续微调。

• 采用 并行退火 （parallel tempering）等技巧克服局部最优。

• 证据积累观 ：学习是随数据增加而更新后验信念的过程，早期非成人行为是数据不足下的理性推断。
• 搜索限制观 ：发展受限于探索假设空间的能力，质性转变源于发现新程序结构。

• 学习可复用组件 （子程序/函数库）：如 DreamCoder，通过压缩重复结构实现跨任务迁移。
• 邱奇编码（Church encodings）：在极简逻辑系统（如 λ 演算）中“涌现”数字、布尔逻辑等高层概念，无需预设语义原语。
• 类黑客学习 （Hacker-like learning）：通过观察输入-输出关系，逆向推导变换规则，显著提升搜索效率。
• 项重写系统 （Term rewriting）：将知识表示为符号重写规则，支持真正的

概念变化 （conceptual change）和任意结构操作。

总结

第19章论证：贝叶斯程序学习为理解人类如何从有限数据中获得丰富、系统、可泛化的知识提供了一个统一且计算上可行的框架。它不仅解释了认知发展的阶段性、创造性与灵活性，还架起了认知科学与形式化计算理论（如可计算性、类型论、程序语言）之间的桥梁。

19 作为程序上贝叶斯推理的学习

本书前几章表明，贝叶斯模型为理解认知过程提供了一种强大的方法，并说明了它们如何能使用包括连续空间、图、逻辑公式和语法在内的多样化表征。本章涵盖程序上贝叶斯推断的基础概念。人们考虑算法上丰富的假设空间这一想法，被发现与人类在学习任务上的表现相吻合。程序学习理论还提出了一种可能的途径，说明人类认知如何在个体一生中（发展层面）以及跨代际（文化层面）实现扩展。人们在程序上进行推断的想法，可以由人类儿童所获得的广泛心智表征来推动——从学习游戏、社会规则，到像逻辑和编程语言这样的新形式系统。我们与外部动态或计算系统（如汽车引擎、宠物或收银机）互动的能力，很可能要求我们为这些对象构建心智模型。我们在各种不同系统中的成功表明，我们能够学习那些计算能力强大（或许实际上是所有计算的空间，但受我们有限记忆约束）的假设空间。

如果 H 是一个计算机程序的空间，h 是该空间中的一个程序，可被假定用于解释某些观测数据 d（通常是程序的输入和输出），那么本章将概述如何通常定义先验概率 P(h) 和似然函数 P(d | h)，以及定义这两者时需要考虑的一些因素。然后我们讨论针对程序的典型统计推断方案，主要聚焦于马尔可夫链蒙特卡洛（MCMC）方法。最后，我们以讨论学习子程序、利用丰富推理家族、并学会编码根本性新逻辑结构的高级方法作结。

19.1 背景

艾伦·图灵（Alan Turing）在20世纪中期为建立计算的数学模型所做的工作（Turing, 1936, 1950）被广泛认为是计算机科学的奠基性贡献。这项工作同样应被视为认知心理学领域的一项深刻发现。在图灵所处的时代，“computer”（计算机）一词指的是执行计算的人。因此，图灵对计算的形式化（即图灵机）实际上是对人类仅凭若干基本能力所能完成之事的一种抽象建模。图灵的发现令人震惊：通过有条件地更新内部状态，并将其与记忆交互，这样的人类“计算机”便能够模拟任何其他逻辑机器。只要拥有合适的程序，一个人——或一台机械/电子计算机——就能通过以新方式组合基本操作，来模拟从物理学到股票市场的各种系统。

这种普适能力体现在丘奇-图灵论题（Church-Turing thesis）中，该论题认为：凡是可以被计算的东西，都可以在图灵机上计算，或等价地编写进一台标准计算机中。关键在于，基本操作可以组合起来产生更复杂的行为，正如一部复杂的小说仅由几十个字符组合而成。在计算机科学早期，逻辑学家提出了看似不同的计算模型（例如图灵机、λ演算、组合子逻辑、波斯特系统和项重写系统），随后发现这些系统在计算能力上是等价的，因为每个系统都能模拟其他所有系统。如今，人们发现许多截然不同的系统——例如根据邻近单元行为而开关的细胞阵列、弹跳的台球、简单的重写规则系统，以及神经网络（Wolfram, 2002；Abelson, Sussman & Sussman, 1996；Fredkin & Toffoli, 1982；Pérez, Marinković & Barceló, 2019）——都具备通用计算能力。这意味着，存在多种可能的系统，可以作为人类类计算能力的基础。

人类在认知上所展现出的通用计算能力，在动物认知中似乎是独一无二的。唯有人类能够发现全新类型的心智表征，内化复杂的程序，并修订和改进复杂的算法。其中一些过程正是认知心理学研究的核心内容：人类能够学会计数、阅读、推理，以及理解物理系统。但人类的能力远不止于此：我们还能学会驾驶航天飞机、演奏大提琴、完成四周跳（quadruple Lutz），甚至修理手风琴。我们能学会操作全新的逻辑系统，如微积分、魔方，以及法律体系的规则。我们能对社会实体进行推理，并战略性地思考竞争对手。与其他物种相比，我们建模世界并将这些模型用于实现目标的能力几乎是无限的。

这促使许多研究者提出假设：认知系统必须具备推断或内化新颖算法过程（即程序）的能力。事实上，大量人类知识都可以用程序来很好地描述（见图19.1）。相应地，程序归纳（program induction）模型已被用于建模众多领域中的学习现象。例如，Amalric 等人（2017）开发了一个数学推理模型，将几何图案描述为从步骤编号（如第1步、第2步）到空间位置的函数。其他研究者则利用模型研究人类对逻辑概念的归纳（Goodman, Tenenbaum 等，2008b；Kemp，2009，2012；Piantadosi, Tenenbaum & Goodman，2016），这些模型以对象的特征描述为输入，输出判断每个对象是否属于该概念的真/假规则。Lake、Salakhutdinov 和 Tenenbaum（2015）提出了一个分层动作规划模型，该模型接收手写字符的图像，推断出最可能生成这些字符的概率性计划或程序，并生成同一字符的新样例。

还有许多模型学习能以关系数据为输入、预测新关系为输出的理论，应用领域包括磁学、亲属关系、因果关系、生物分类学，甚至球面几何（Kemp & Tenenbaum，2008；Kemp, Tenenbaum, Niyogi & Griffiths，2010；Goodman, Ullman & Tenenbaum，2011；Ullman, Goodman & Tenenbaum，2012；Mollica & Piantadosi，2021）。Piantadosi 等人（2012a）以及 Piantadosi（2023）将计数程序的习得建模为发现一种将对象集合映射为数词标签的程序。

此外，还有若干模型处理更抽象的数学关系，包括二进制序列（Planton 等，2021）、诸如“偶数”和“奇数”之类的数值概念（Tenenbaum & Griffiths，2001a）、分形（Lake & Piantadosi，2020），以及自然数列表上的函数（Rule 等，即将发表）。Siskind（1996）对词汇语义进行了建模，其他模型则探讨了语言的更多方面，包括量词语义（Piantadosi，2011）、形态学（Ellis，2020）、句法（Yang & Piantadosi，2022）、问答系统（Rothe, Lake & Gureckis，2017），以及语用学（Goodman & Lassiter，2015；Goodman & Frank，2016）。还有一些模型处理对视觉表征的视觉推理（Ellis, Morales, Sablé-Meyer, Solar-Lezama & Tenenbaum，2018）、三维（3D）图形（Overlan, Jacobs & Piantadosi，2017），甚至邦加德问题（Bongard problems）（Depeweg, Rothkopf & Jäkel，2024）。

19.2 假设空间
大多数程序学习模型并不直接使用图灵机（参见 Graves, Wayne, & Danihelka, 2014；Kim & Bassett, 2022），因为认知科学中的行为研究有力地表明，人类认知具有组合性（compositional）。正如第18章所述，阿隆佐·邱奇（Alonzo Church）提出λ演算，旨在将计算形式化为函数的组合。在他的框架中，复杂程序通过将一个函数的输出连接到另一个函数的输入而产生——例如，将函数 f 和 g 组合形成复合函数 f ◦ g。这种基于组合的计算方式至今仍存在于 Haskell 和 Lisp 等函数式编程语言中，这些语言将程序表达为基本函数的组合，而非一系列步骤的序列。

类似的组合性方法在自然语言语义的形式化中也占据主导地位（Heim & Kratzer, 1998；Steedman, 2000；Blackburn & Bos, 2005）。例如，句子“我找到了彼得罗掉落的手风琴”（I found the concertina that Pietro dropped）的语义，可以通过组合句中每个词所对应的函数来捕捉。语言中的组合性很可能与思维中的组合性密切相关，这促使许多学者主张存在一种“思维语言”（language of thought）（Fodor & Pylyshyn, 1988；Fodor, 1975；Piantadosi & Jacobs, 2016；Goodman, Tenenbaum, & Gerstenberg, 2014），在这种语言中，思想本身由若干组成部分构成，形成类似句子的结构。

这种组合性方法也被应用于学习模型中，这些模型在所有可能的函数组合构成的空间中进行操作。例如，Siskind（1996）提出了一个词汇习得模型，在该模型中，像“lift”（举起）这样的词会被赋予如下含义：

这里，CAUSE（致使）、GO（移动）和 UP（向上）是基本操作，它们通过组合来表达“lift”（举起）的含义。公式（19.1）中的表达式意为：“x 举起 y”当且仅当 x 致使 y 向上移动。

这类模型与另一种模型形成对比：在后者中，“lift”本身被视为一个概念原语（conceptual primitive），学习者唯一需要解决的问题只是确定词语与预先给定意义之间的映射关系。而在组合性模型中，学习者面临的是一个困难得多的任务——他们必须从组成部分出发，构建出正确的意义，并在庞大（常常是无限的）可能性空间中找到正确的组合方式。

19.2.1 基于类型的假设语法

与公式（19.1）中的例子类似，我们通常将程序视为将输入映射到输出的函数。例如，公式（19.1）中的 lift 接受两个对象 x 和 y 作为输入，并返回一个布尔值，表示 x 是否举起了 y。在构建程序学习模型时，我们的任务是选择合适的输入和输出，这通常决定了我们所要学习的函数形式，以及所需的基本操作（primitives）有哪些。

在典型的程序学习模型中，假设空间由所有语义上合理的、由一组预设基本操作组合而成的方式构成。学习者甚至无法评估像 lift(x, y) = CAUSE(CAUSE, CAUSE) 或 lift(x, y) = GO(CAUSE, y) 这样的假设，因为这些表达式毫无意义。

我们确保程序语义一致性的主要方法，是将每个基本操作赋予固定的输入和输出类型。举例来说，lift 可能接受两个类型为 object（对象）的参数。这意味着参数 x 和 y 必须是具体对象：你可以举起一个土豆，但不能举起一个抽象事物（比如一个笑话）；你也不能举起一个完整的句子或命题，例如“吸烟会致死”。基本操作 GO 可能接受一个对象和一个方向作为参数，因此 GO 可以让一个土豆向左、向右、向上或向下移动。重要的是，它不能让一个土豆“go carrot”（向胡萝卜移动），因为它的第二个参数不能是对象类型。

基本操作 CAUSE 则更有趣一些：它接受一个对象（致动者）x 和一个事件，并断言 x 导致了该事件的发生。因此，CAUSE(x, GO(y, up)) 表示“x 致使 y 向上移动”；只有当这种因果关系成立时，该组合才会求值为真。

我们可以使用上下文无关文法（context-free grammar，参见第16章）来强制执行这些预设的类型约束，从而生成完整的程序组合。该文法的非终结符（nonterminals）规定了每个基本函数的输入和输出类型。例如，如果 GO 接受一个对象和一个方向，并返回一个布尔真值，我们可以在文法中将其写作：

BOOL → GO(OBJECT, DIRECTION)

这意味着，在编写程序时，每当遇到一个 BOOL 符号，我们就可以用对函数 GO 的一次调用（其参数分别为某个 OBJECT 和某个 DIRECTION，二者也由该文法生成）来替换它。为该文法写出更多规则后，可得到如下形式：

该文法规定了一个庞大的假设空间。即使在这个简化的示例中，也已包含 24 种可能的 GO 动作（4 个对象各自朝 6 个方向移动），这些动作还可进一步与合取（and）、析取（or）和否定（not）组合。事实上，这种组合爆炸（combinatorial explosion）是刻意设计的。我们构建程序学习模型的核心设计目标之一，就是让少量内置的基本操作能够组合出极其丰富的概念。正如前文所述，这种表达能力正是受人类能够习得如此多样化的概念这一事实所启发。例如，使用该系统的学习者可能会提出如下假设：x 举起 y，当且仅当一辆汽车使 x 向右移动，或者一辆汽车使 y 向左移动：

这一假设虽然不正确，却是可以构想且可能的——这正是我们希望文法将其包含在内的原因。话虽如此，公式（19.2）显得有些不自然，很可能是因为它过于复杂。该假设使用了11个基本操作，相较于更简单的选项（包括正确的那个），它在先验上或许应被赋予较低的偏好度。我们可以通过将文法转换为概率文法（probabilistic grammar）来在模型中引入对简洁性的偏好。这要求我们为每条规则的展开分配一个概率（参见第16章）。然后，我们可以通过将一个完整表达式所用的每条规则展开的概率相乘，来计算该表达式的概率。这样的概率文法随后可用于定义程序学习模型的先验分布。由于先验通常偏好较短的程序，贝叶斯程序学习模型通常会倾向于选择那些能将观测数据压缩为简洁描述的程序。这种压缩效应，正是贝叶斯学习者典型的泛化能力（generalization effect）的体现（参见第3章）。

19.2.2 一个简单的列表函数文法
我们可以在列表函数领域观察到许多贝叶斯推断效应的运作，其中学习者观察到一个未知函数 F，该函数将一个数字列表转换为另一个数字列表（Rule 等，即将发表）。例如，我们可能仅被告知一个单一的数据点：

其中左侧的列表被未知函数 F 转换为右侧的列表。从这个例子中，我们很容易猜出 F 是将列表按降序排序。一旦学会这一点，我们就能轻松地将 F 应用于一个新的列表。其他数据集则会导致对 F 功能的不同猜测，从而产生不同的泛化结果：

这与学习者可能提出的若干种泛化假设是一致的：（1）移除奇数；（2）只保留数字6和2；（3）保留列表中的第二个和第六个元素；（4）只保留从前往后数第二个和从后往前数第二个元素；等等。这些选项凸显了概率模型的一个优势，即它们能够将置信度分配到多个假设上。这些置信度会随着数据的数量和内容而变化。例如，如果我们接下来观察到两个数据点：

尽管此时我们可能感觉已经锁定了某个单一假设，但请记住，在所有可能计算构成的空间中，与任何给定数据集一致的假设都有无穷多个。然而，先验会将最高的概率赋予那些与数据一致且最短、最简单的假设，这可能会使我们对“正确答案”形成强烈的信念。

对这一例子的内省促使我们思考：在一个关于列表领域的形式化模型中，我们可能需要一些基本操作，包括用于操纵和从列表中选取元素的操作：

这里，lst 是提供给函数 F 的参数；□ 表示空列表；pair 通过将一个数字前置到现有列表上来构建新列表；first 返回列表的第一个元素，而 rest 返回除第一个元素之外的所有元素；filter 遍历一个列表，仅保留满足其谓词（predicate）的元素；reverse 将列表反转；此外，我们还内置了若干谓词，对应于学习 F 的成年人可能已掌握的操作。这些谓词本身是可应用于数字的函数（例如，它们将 NUMBER 映射为 BOOL）。

这些操作与为人类使用而设计的列表处理编程语言（如 Abelson 等人，1996）中的操作颇为相似，这或许并不令人意外。利用这些操作，我们可以将前述假设（1）形式化为：

与用于 lift 的文法类似，这一文法也允许我们表达许多其他假设。例如，F(lst) = pair(9, rest(lst)) 会将列表的第一个元素替换为 9。

19.2.3 变量与抽象

到目前为止，我们讨论的操作都可以纳入一个概率性的上下文无关文法中，但大多数编程语言的文法并非上下文无关的。其中一个原因是：引入变量会改变哪些程序是合法的——表达式 first(foo) 只有在 foo 之前已被声明为变量的情况下才是有效的。如果我们向认知程序中引入显式的变量，就会遇到这一问题。例如，我们可能希望根据一个数字是否“为偶数或为质数”来过滤列表，这时就必须引入布尔析取（or），并用它来定义一个子程序：

之所以需要这个子程序，是因为类型限制：or(is-even(y), is-prime(y)) 返回的是一个 BOOL（布尔值），而不是一个 PREDICATE（谓词），因此不能作为 filter 的第一个参数。
如果我们直接写成 filter(or(is-even(y), is-prime(y)), lst)，就无法明确表达我们希望 y 是一个遍历 lst 中每个元素的变量。
通过定义函数 even-or-prime，这些问题就得到了解决，于是我们可以写成：

如果一个函数（比如 even-or-prime）只使用一次，却要为其专门定义一个完整的函数，这显得笨拙而不便，尤其是因为学习过程意味着我们无法事先知道哪些函数是必需的。λ演算在此非常有用，因为它允许我们定义函数而无需为其命名，这类函数通常被称为匿名函数（anonymous functions）。使用λ演算，我们可以将公式（19.9）写作：

公式（19.9）和（19.12）都引入了变量 y，而该变量并不在文法之内。只有“λ y”（或“even-or-prime(y) = ...”）这一部分将 y 引入为一个变量并作为一个新符号，而且它本可以被称为 z 或 symbol1244，而不会改变程序所计算的内容。变量如何动态地改变底层文法，是一个令人烦恼的技术问题，在不同认知模型的实现中会以多种方式处理。最简单的解决方案是预设一组变量，并允许学习模型自行决定哪些变量用在哪里，同时假设存在某种适当的方法来评估未定义的变量。一种更通用、同时保持文法上下文无关性的方法是引入高阶函数（higher-order functions），Fleet 软件包就采用了这种方法。例如，我们可以引入一个析取函数（我们称其为 disj），它接受两个 PREDICATE（谓词），并返回一个新的 PREDICATE，该谓词作用于参数 x：

这里，disj 被称为高阶函数，因为它不以列表或数字作为参数，而是以完整的函数（PREDICATES）作为参数。然后，我们可以构造如下表达式：

这种做法的一个缺点是，它要求我们在文法中添加概念上与其他现有基本操作相近的高阶函数。例如，disj 在功能上几乎与 or 完全相同，唯一的区别在于它们的类型。第三种方法是实际修改文法，一旦引入变量，便为其增加相应的规则——早期 LOTlib3 软件包即采用此方法。模型必须确保变量被赋予唯一名称，但存在一种标准方案可实现这一点，即所谓的“德布鲁因索引”（De Bruijn indexing）。虽然显式修改文法具有灵活性，但它也增加了类型系统的复杂性。这类工程上的选择通常远远超出了我们对捕捉人类认知能力的目标范围——事实上，不同方法的先验分布往往可以设置得相似甚至完全相同。

许多编程语言并非上下文无关的另一个原因是：类型系统本身可能就不是上下文无关的。为了理解为何会出现这种情况，请考虑我们当前的文法。具有 NUMBER 类型的表达式总是会被求值为数字，而 LIST 类型的表达式总是会被归约为数字列表。然而，假设我们还希望包含“数字列表的列表”。若不扩展我们的语言和文法，则无法容纳这种类型：

该文法同时包含列表（LISTₙ）和列表的列表（LISTₑ），但也引入了许多几乎冗余的基本操作——这与我们之前在 even-or-prime 例子中遇到的问题相同。例如，LISTₑ 和 LISTₙ 版本的 filter 操作行为几乎完全一致：它们都对列表中的每个元素应用一个谓词，并仅保留满足该谓词的元素。如果我们还希望支持字符列表、列表的列表、谓词列表、列表的列表的列表等等，这个问题只会变得更加严重。因此，若能有一个单一的 filter 原语，可适用于所有类型的列表，那将非常方便。

到目前为止，我们所讨论的都是所谓的“简单类型”（simple types）（Pierce, 2002）。像 Hindley-Milner 类型系统这样的多态类型系统通过向类型系统本身添加变量来解决这一问题。我们不再需要区分 LISTₙ 和 LISTₑ，而是拥有一个单一的列表类型：LIST x。这里的 x 是一个变量，会被具体类型（如 NUMBER）填充。这种方法允许我们提供一个通用版本的 filter，例如，它接受一个从 x 到 BOOL 的函数作为谓词，并以 LIST x 作为输入。如果 x 是 NUMBER，它将过滤一个数字列表；如果 x 是 LIST NUM，它将过滤一个数字列表的列表。

类型之所以有用，原因之一是它们允许我们编码关于程序行为的信息。当我们拥有一个 NUMBER 类型的程序时，我们知道它最终会求值为一个数字。随着类型系统变得更为复杂，它们允许我们将更多信息打包进类型之中。例如，考虑基本操作 last（返回列表的最后一个元素）和 length（返回列表长度）。在简单类型系统下，两者都接受一个 LIST 并返回一个 NUMBER。然而，在多态类型系统下，我们看到 length 接受一个 LIST x 并返回一个 NUMBER，而 last 接受一个 LIST x 并返回一个 x。多态类型包含了更多信息，从而能够区分 last 和 length：它们告诉我们，无论我们提供何种类型的列表作为输入，length 总是返回一个 NUMBER，而 last 总是返回输入列表中所含元素的类型。将更多信息打包进类型是有用的，因为它允许我们对潜在解决方案给出更完整的描述。更完整的描述之所以有用，是因为它加强了学习者的归纳偏置（inductive bias），使其能够排除原本必须考虑的大批程序。

其他类型的类型系统甚至可以比多态类型系统包含更多信息。例如，带有类型类（type classes）的类型系统允许人们声明某个基本操作适用于任何类型（即使用类型变量），但随后将其限制在某类特定类型上，这些类型保证实现了某些特定的基本操作。例如，你可能会说 LIST x 可以被排序，只要类型 x 具备比较运算符。依赖类型（Dependent types）走得更远，它可以将整个一阶逻辑表达式编码进类型中。例如，一个作用于 LIST x 的排序函数的依赖类型不仅可以要求 x 具备比较运算符，还可以声明输出列表将是输入列表的一个排列，且每个后续元素大于或等于其前驱元素。程序学习领域的文献描述了许多利用复杂类型系统的技术，以提供高效学习复杂程序所需的归纳偏置。（Polikarpova, Kuraj, & Solar-Lezama, 2016; Osera & Zdancewic, 2015; Chlipala, 2022）

19.2.4 递归与条件语句

我们通常也对建模人类如何学习递归函数感兴趣。递归被假定为人类思维与语言的核心操作之一（Hauser, Chomsky & Fitch, 2002；Corballis, 2014）。它在计算机科学中也至关重要，因为它允许用简洁而优雅的方法解决复杂问题——即将一个问题分解为更简单的子问题。例如，如果我们要在列表示例中包含递归排序算法，就需要具备在新输入上调用当前正在定义的函数 F 的能力。

我们定义一个基本操作 recurse，它会调用其所在函数自身。从这个意义上说，recurse 有些特殊，因为它的返回值并非由某个预先定义好的基本操作所确定，而是必须根据 F 当前的定义在运行时动态计算得出，这意味着它的值依赖于使用时的具体上下文。在此设定下，recurse 的输入和输出类型始终与 F 相同。在我们的例子中，recurse 接受一个列表并返回一个列表，因此我们可以写出如下函数：

这个函数的意图是在每隔一个位置插入一个 1，例如将 [5, 6, 7] 映射为 [5, 1, 6, 1, 7, 1]。但它实际上并不是一个正确的实现，因为递归没有终止条件：即使输入为空列表，公式（19.14）中的函数仍会尝试对 rest(lst) 调用 recurse，而 rest(lst) 仍然是一个空列表。这种递归永远不会终止，因此程序永远无法返回一个值。

一种解决方案是引入一个 if 语句，仅在满足特定条件时才进行递归。这样我们就可以写出：

该函数仅在 lst 非空时才进行递归。实际上，if 的行为相当微妙。在大多数编程语言中调用一个函数时，我们会先对其所有参数求值，例如 filter(is-even, reverse(lst)) 会先调用 reverse(lst)，再将该表达式的值作为第二个参数传递给 filter。但如果我们在公式（19.15）中对 if 也采用这种求值方式，就会先调用 recurse(rest(lst))，从而再次陷入无限递归。

编程语言为此发展出的解决方案是：将 if 视为一种特殊函数——与大多数其他函数不同，它在被调用前不会对其所有参数进行求值。相反，它首先对布尔条件求值，然后仅根据该布尔结果选择性地求值其中一个分支参数。正因如此，if 在大多数编程语言中是一个特殊关键字。

19.2.5 随机操作

在建模“思维语言”（language of thought）时，随机性基本操作（stochastic primitives）通常很有用，因为有时我们希望对这样一类学习者进行建模：他们自己就认为世界具有某种程度的随机性。例如，学习者可能会观察一个非常长的序列，比如：

当他们无法在序列中找到规律时，会将其视为“随机”，无论该序列实际上是否存在某种模式（例如 π 的二进制数字）。因此，这样的序列可能对应一个非常简洁的假设（“连接随机数字”），即使其底层数据本身很复杂或看似不可压缩。

将随机函数引入表征语言的一种简便方法是添加一个名为 flip 的函数，它“抛硬币”来决定返回“真”或“假”。这里，flip 与之前列出的操作类型截然不同，因为现在程序不再必然只有一个确定的输出。例如，简单程序

将返回一个关于两个不同列表的概率分布：一半时间是在 lst 前面附加一个 1，另一半时间则附加一个 2。实际上，我们可以从几个角度理解表达式 (19.16)。我们可以将其视为每次运行时都采样一个随机答案的程序；也可以将其视为隐式地指定或表示某个特定的概率分布。类似地，不同的实现方式会以不同方式处理像 flip 这样的随机操作。例如，一些实现可能会将程序的部分求值结果及其关联概率存储起来，遇到 flip 时，会把两种结果都推入一个不完整执行轨迹的队列，以便稍后继续求值。其他随机操作的例子可能包括从离散集合（如字母表）或连续集合（如分布）中采样元素。

重要的是，一旦随机操作与递归等操作交互，事情就会变得更加复杂。例如，

将接收一个像 [1, 2, 3, 4] 这样的列表，并抛硬币决定每个元素是否应被替换为 1。因此，输出结果的分布会赋予诸如 [1, 2, 3, 4]、[1, 1, 3, 4]、[1, 2, 1, 4]、[1, 2, 3, 1]、[1, 1, 1, 4]、[1, 1, 1, 1] 等序列非零概率。在这种模型中，数据的概率取决于程序在求值过程中所采取的特定路径的概率。例如，如果程序映射

[1, 2, 3, 4] →ℱ [1, 2, 1, 4], (19.18)

那么该数据的概率将是 (1/2)³，因为第一个硬币翻转的结果无关紧要（无论正反都会在列表开头放一个 1），但剩下的三次翻转必须以特定的方式出现才能生成各种输出。

许多包含随机操作的语言——包括 Church 语言（Goodman et al., 2012）——还包含“记忆化”（memoization）功能，它允许函数记住特定硬币翻转或其他随机选择的结果。举例说明，假设我们想将列表中的所有 2 替换为 3 或 4（但随机选择其中一个）。你可能会想象编写一个类似这样的函数：

然而，这个函数并不正确，因为每次调用 recurse 时，都会重新计算一个不同的 flip 值。这会导致在每一步递归中做出新的随机选择，可能每次都选到不同的值。一种解决方案是引入一个名为 mem 的函数，它“记住”了曾经做过的随机选择。例如，mem(flip) 是一个函数，它在第一次被调用时选择一个值，并在之后每次被调用时（即使跨越递归调用）都记住并返回该值。在这种情况下，我们可以写成：

19.3 程序模型的似然函数

要使用贝叶斯模型进行程序学习，我们不仅需要由假设空间中的程序文法所定义的先验概率，还需要指定一个似然函数 P(d | h)，该函数描述了如果数据 d 是由程序 h 生成的，其发生的可能性有多大。在搜索确定性程序的空间时，会遇到一个基本挑战：每个程序对于给定输入仅返回一个单一输出。因此，大多数程序都会产生错误的输出。例如，我们从先验中采样到一个假设并正确预测公式（19.3）的概率会非常低。解决这一问题的一个常见方法是通过向 P(d | h) 引入噪声来平滑似然函数——即，假设输出是在先运行程序 h 的基础上，再以某种方式随机修改而得到的。添加此类噪声是有用的，因为那些近似正确的假设可以获得部分认可，从而获得部分信用。这反过来又提供了一个信号，帮助搜索算法在程序空间中更有效地移动，以改进对数据的拟合。事实上，选择一个有用的似然函数通常是实现高效推断最重要的决策之一。

噪声可以通过多种方式添加到似然函数中。例如，在列表函数领域，我们可以假设输出列表中的每个元素都以某个较小的概率（例如 0.05）被随机地从集合 {0, 1, 2, ..., 9} 中采样而发生“污染”。在这种情况下，如果观测到的数据列表输出是 [9, 7, 6, 3, 3, 2, 1]，而程序预测的是 [9, 7, 5, 3, 3, 2, 1]，那么该数据将具有如下概率：

因为七个数据点中有六个可能在噪声中保持不变（概率为 0.95），或通过噪声被改变为它们自身的值（概率为 0.05/10），而有一个值——5——必须被改变为其目标值。这一计算说明，在计算含噪数据的概率时，我们必须同时考虑数据由假设生成的概率以及数据由噪声生成的概率。

这种似然函数中的噪声无法改变列表的长度。因此，如果假设预测的是 [9, 7, 6, 3, 3, 2] 或 [9, 7, 6, 3, 3, 2, 1, 8]，那么它将被赋予零概率。这种情况是有问题的，因为它意味着假设必须在每一个输出上都准确预测出正确的长度——而这几乎不可能偶然发生；否则，整个数据集都将被赋予零概率。然而，我们可以定义其他能够改变长度的似然函数。例如，Kashyap 和 Oommen (1984) 定义了一种概率性编辑似然函数，允许人们根据一系列插入、删除和修改操作来计算一个列表被“污染”成另一个列表的概率，这本质上是字符串编辑距离（Levenshtein 距离）的一种概率化且连贯的版本。另一种更快但类似的选项，见于 Yang 和 Piantadosi (2022)，是考虑一种噪声模型：该模型首先从假设所生成序列的末尾开始随机删除元素，然后再在末尾随机追加元素。请注意，与之前一样，任何字符串都可以通过删除所有内容而来自其他任何字符串，但那些与数据共享前缀的假设需要更少的删除操作，因此会被赋予更高的似然概率。这种似然函数不仅能够被高效计算，还会引导模型倾向于获得列表开头部分正确的假设。这种排序偏置很可能有助于随机搜索找到与递归计算初始阶段相匹配的假设。

在列表或字符串以外的场景中，似然函数会采取不同的形式。例如，Piantadosi (2011) 研究了诸如“every”（所有）和“most”（大多数）等量词术语的学习，并表明程序学习模型可以习得这些术语对应的程序。量词术语通常被形式化为集合上的函数：“most A are B”（即 most(A, B)）为真，当且仅当

换句话说，“大多数理发师是快乐的”（most barbers are happy），当且仅当“快乐理发师”的集合（即快乐人群与理发师的交集）的基数大于“不快乐理发师”的集合（即理发师与快乐人群的差集）的基数。因此，我们构建了一个相当标准的假设空间，其中包含对集合和基数的操作。当我们最初考虑如何为该模型设定似然函数时，似乎使用一种给予最常为真的语句高概率的似然函数是合理的——例如，对于给定的数据点（在特定语境下的语句），如果假设判断其为真，则赋予高概率；否则赋予低概率。但我们发现这种方法注定失败，因为模型总会习得那些平凡为真的意义。例如，模型可能不是学习像公式（19.21）那样的意义，而是学会将 most(A, B) 定义为恒为 true。

尽管试图在文法中以某种方式排除这些平凡意义很有吸引力，但这行不通，因为模型总能写出复杂但平凡为真的表达式（例如，|A ∪ B| ≥ |A|）。这个例子说明，似然函数通常必须是一个真正的概率分布。我们最初的似然函数并未在任何意义上量化数据的概率。该问题通过使用一种似然函数得到了解决：该函数在每个语境下评估所有可能的量词，并以高概率从那些为真的量词中均匀选择。这种“规模原则”似然函数（Tenenbaum 2000；Tenenbaum & Griffiths, 2001a；另见第3章）鼓励模型在所有可能的情境中使量词为真，

但在它们不可能发生的情境中则会对其施加惩罚。

19.4 可计算性问题

当图灵首次使用图灵机定义可计算性时，他也证明了不存在任何算法能够决定一个给定的图灵机是否会停止运行并终止（Turing, 1936）。然而，还存在一种更强大的不可计算性版本，称为里士满定理（Rice’s theorem）（Rice, 1953），该定理指出，关于程序功能的几乎所有非平凡问题都是不可判定的（更技术性地说，程序的非平凡“语义属性”是不可判定的）。例如，没有任何算法可以取任意程序作为输入，并始终确定该程序是否曾输出数字 5。也没有任何算法可以判断一个程序是否仅输出递增的数字，或是否计算函数 f(x) = x²。这并不妨碍我们通过某种方式收集关于程序的证据——例如，我们可以运行一个程序很长时间，观察它的行为——但里士满定理确立了一个事实：不存在任何程序能最终确定地回答所有这类关于程序输出的问题。

对于程序上的贝叶斯推断而言，这些定理似乎预示着不祥。当我们假设某个程序 h 时，我们无法确定 h 是否会输出观测到的数据，因为这个问题通常无法被回答。因此，似乎我们无法计算似然函数，因为甚至没有算法能够计算出输出！但值得注意的是，从心理学角度讲，人们在学习程序时可能并不会在所有领域都面临相同的可计算性挑战。例如，如果某人通过观察他人系鞋带或计算导数来学习一个程序，那么他们的任务显然比试图归纳一个从未见过的算法要容易得多。知识的文化传播允许更复杂的表征——包括程序（Thompson, Opheusden, Sumers, & Griffiths, 2022）——以更低的学习难度传递下去，从而导致不同形式的学习（分别来自他人与自然）（Chater & Christiansen, 2010）。

在那些从数据中发现程序的学习模型中，有几种方法可以绕过可计算性问题。一种方法是精心构建假设空间，确保所有程序都能保证终止，但这在实践中很难正确实现。在这一传统中，有许多计算或逻辑系统，其关键问题是可以被计算的——尽管这些系统必然比图灵机的能力弱。然而，最常见的解决方案只是忽略这个问题。虽然没有任何算法可以为所有程序计算似然函数，但在实践中，许多近似方法似乎效果良好，很可能是因为所涉及的程序相对简单。如果程序允许递归或循环，那么通常当我们运行一个程序时，它会在合理的时间内终止。例如，如果一个程序在 1,024 步后仍未终止，我们就简单地将其视为输出空字符串或空值。或者，我们可以通过使用一个依赖于其时间和空间资源消耗的先验概率来更优雅地解决这个问题。为了说明这个想法，如果程序 h 在 halt(h) 时间内终止，我们可能会选择一个与 2⁻ʰᵃˡᵗ⁽ʰ⁾ 成正比的先验。这倾向于选择那些评估速度较快的程序，并赋予非终止程序（halt(h) = ∞）零先验概率。在贝叶斯推断中——特别是 MCMC 采样中——我们可以利用这一点拒绝非终止程序，因为随着它们的运行，其先验概率最终会降至可接受阈值以下。

存在几种围绕该思想的形式化版本，其核心在于对程序进行最优高效的搜索（Levin, 1973; Schmidhuber, 2002; Hutter, 2002）。一个简单的直觉是考虑莱文搜索（Levin Search）（Levin, 1973），其中所有程序的计算过程是交错进行的。通过在所有可能的程序之间分配运行时间资源，非终止程序不会阻止终止程序的计算。尽管这些想法在理论上很优雅，但我们尚未找到一个领域，能在实证上通过人类实验区分基于速度的先验和基于文法的先验。

19.5 用于程序的马尔可夫链蒙特卡洛方法

Metropolis-Hastings 算法是一种 MCMC 算法（参见第6章），是认知科学中贝叶斯程序学习最常用的推断算法。Metropolis-Hastings 需要我们指定如何从当前样本生成一个新的候选样本。最简单的方法是从底层文法中重新随机采样，但这样做会丢失关于当前假设的所有信息。这意味着这些提议会丢失迄今为止哪些部分表现良好的信息。我们可以通过使提议以现有程序为条件来保留这些信息。一种标准做法是只选择当前程序的一个子表达式，并从文法中重新生成一个同类型的子树（Goodman et al., 2008b）。如果将程序视为一棵树，那么该技术首先选择一个子树，然后用从文法中采样生成的、类型相同的新子树替换它。这种方法通常能保留现有程序的大部分内容（希望是其中有用的部分），并只修改一小部分（希望这部分是可以改进的）。

考虑一个复制输入列表第一个元素的程序：

在公式（19.25）中，rest(lst) 被保留自初始假设，而我们插入了 pair(2, LIST)。“删除”（delete）操作则执行一种镜像变换：将一个子树替换为其自身的一个类型匹配的子子树。其他能够保留结构的提议操作还包括交换参数（例如，交换 if 语句的两个分支），或在保持参数不变的情况下交换函数（例如，将 and 替换为 or）。在这些操作中，确保被交换的部分具有合适的类型尤为重要。还有一种重要的提议操作是从现有程序中提取子程序（subroutines），但这类操作实现起来较为困难。

19.6 示例模型运行

图19.2展示了在Piantadosi等人（2012a）提出的数字学习模型的一个版本上，对程序进行MCMC采样的25次运行示例。该模型捕捉了儿童在学习计数过程中的大致发展阶段：他们需经历几个中间知识和行为能力层级，才能最终展现出完全掌握的能力——即能准确说出与给定对象集合相对应的词语。模型将儿童在这些中间知识状态之间的过渡，解释为获取更多数据的结果。当数据量较少时，贝叶斯推断仅能支持那些简短、简单且仅部分有效的程序；但随着数据积累，模型会逐步习得完整的计数程序。模型中的假设被设定为从对象集合映射到词语的函数，正如计数本身一样，最终模型发现了一个递归的计数程序：

该程序规定：对于包含一个元素的集合，输出词语“one”；否则，它通过计算“下一个”（next）词语来得到结果——即，对集合 s（待计数的集合）中的所有元素减去一个元素（setminus(s, select(s))）后进行计数所得到的词语。这强调了儿童在学习计数时，必须理解如何通过递归或迭代过程更新集合 s，从而沿着他们已知的数字词序列前进。

图19.2展示了使用MCMC和树再生技术在25个不同模型运行（子面板）中学习的动态过程，每个运行均使用Fleet软件包执行10秒。这些图中的横轴表示样本编号（按1000倍稀疏化），纵轴表示当前样本假设 h 的后验得分 log(P(h)P(d | h))。链的颜色根据其表现出的行为模式或正确识别的数字而定。该图展示了多个运行，以帮助读者理解程序空间上的MCMC采样大致是什么样子。

粗略而言，在单次运行中，MCMC链倾向于停留在某个“模式”上——通常是一个行为方式特定的程序（同一颜色）。图中上下抖动的线条即代表此现象：它们通常是针对程序的小幅、中性提议，可能略微改变程序的复杂度，但往往不影响似然值，或仅对似然值产生微小影响（例如，仅影响某个罕见数据点的表现）。但有时，链会提出一个导致先验（复杂度）或拟合度（简洁性）显著提升的变更。当这种情况发生时，后验得分会大幅向上跳跃，同时模型的行为（颜色）也常常随之改变。

一个有助于理解的画面是：在抽象的“程序空间”中，存在若干性能近似相等的程序“模式”，模型通过从一个模式跳跃到另一个更好的模式来实现改进。这种跳跃通常是离散的，因为程序本身是离散的，因此不同的性能水平（后验得分，即纵轴）也是离散的。正因如此，在程序空间上采样时发生的大多数有趣变化往往是大的、跳跃式的改变，而非人们在实数值函数的MCMC采样中熟悉的那种小幅度、渐进式更新。需要注意的是，性能或似然值的巨大变化实际上可能对应程序本身的微小改动。例如，我们可能将 rest(lst) 替换为 recurse(rest(lst))，从而将一个完全错误的程序转变为一个实现了正确递归的程序。因此，正确的理解是：在性能或似然值上的“模式”彼此之间，在程序编辑/提议空间中可能接近，也可能相距甚远。两者之间的映射关系很可能是——甚至必然——“脆弱的”，即对程序的微小改动就足以使其成功或失败。

在这种设定下，随机采样之所以有效，是因为采样器按定义会在每个假设上花费与其后验概率成比例的时间。这意味着它会更多地从表现更好的假设中提出新样本。事实上，MCMC相对于穷举法的优势程度，恰恰告诉我们：程序间的提议概率中确实编码了一些关于性能的信息。

图19.3展示了该数字模型的一个更复杂的版本，源自Piantadosi（2023）。这个版本包含了更多基本操作，例如用于处理近似数量和名词类型的操作。由于该模型从更基础的操作（如一对一匹配）推导出对小集合的操作（例如，检查一个集合是否仅含一个元素），因此它能够学习更复杂的程序。尽管假设空间更大，该模型仍能理清计数所涉及的计算过程，包括学习到数字并非近似的，且数字并不指向特定对象（例如，“two”并不意味着“两只袜子”）。

为了可视化这个更丰富的假设空间，图19.3展示了一个散点图，其中每个点代表一个不同的假设，其横坐标为负对数先验概率（negative log prior），纵坐标为负对数似然值（negative log likelihood）。最佳程序位于原点附近，对应着高先验概率和高似然值。图中各假设根据其总后验得分着色，这形象地说明了随着数据点不断积累，概率质量如何移动。最初，最佳假设主要沿横轴（先验）靠近原点；当数据量适中时，人们可能希望这些点沿对角线方向靠近原点，以同时最小化先验和似然值；而当数据量很大时，关键在于纵轴上的值是否接近零。因此，可以预期学习者会随着数据的积累，沿着这些图的左侧边缘向下移动。

然而，重要的是要记住，这些图所呈现的几何结构本身是学习者无法直接感知的。也就是说，从某个假设 h 出发，很难判断其他哪些假设在似然值上大致相同，因为那些在似然值上相近的假设，可能需要对底层程序进行大幅度的修改才能实现。

19.6.1 学习的两种含义

这些图例说明了MCMC采样如何逐步搜索假设空间。这种搜索至少可以通过两种不同的方式映射到人类学习过程。

在某些研究中，程序学习模型被视为一个理想观察者（ideal observer），即在决定学习者应选择哪个假设时，提供一种统计上理性的解决方案。这种方法将学习解释为证据的积累：当获得更多数据时，学习者会更换假设（如图19.3所示）。在这种观点下，人们在每个数据量水平上都执行近似的统计推断；早期学习者所持有的非成人样式的假设，之所以被选择，是因为它们是在已有数据条件下所能获得的最佳解决方案。若干发展现象已通过这种方式建模，例如概念发展中从特征性特征（characteristic features）向定义性特征（defining features）的转变（Mollica & Piantadosi, 2021）。这种数据驱动的观点还能预测学习的其他细节。例如，如果学习主要依赖于等待足够数据的到来，那么这就预测了特定发展转变发生年龄的均值与方差之间存在某种特定关系（Hidaka, 2013；Mollica & Piantadosi, 2017）。

另一种可能互补的观点将学习视为搜索过程。在此观点下，发展的主要限制因素在于学习者能够探索多少假设空间。这一想法似乎能解释图19.2：在该图中，采样模型随着学习者找到问题的新解法，而在离散假设之间发生转换。Ullman 等人（2012）支持这一观点，指出搜索过程中经常出现剧烈变化和重组，即使没有额外证据，也与儿童发展中的质性现象相呼应。很可能，数据积累和搜索过程两者对于刻画儿童如何随时间学习并修正其理论都至关重要。

19.6.2 推断技巧

图19.2展示了每条链10秒内的采样结果。在此时间内，对于该模型，Fleet通常会生成40万至60万个样本。样本数量的差异源于较大程序需要更长时间求值：采样最多的链往往是那些未能获得高后验得分的链。在此情况下，低后验得分的假设通常更简单（例如，不涉及递归），因此求值速度更快。

假设空间的离散性既有优势也有劣势。一个主要劣势是，单条采样链常常无法跳出局部极小值，因而找不到最优程序。这在图19.2中表现为某些链长期停留在低后验得分区域。对于程序学习而言，目前效果最好的方案似乎是并行退火（parallel tempering）方法：同时运行多条处于不同“温度”的马尔可夫链，并允许链之间交换状态（参见，例如，Vousden, Farr & Mandel, 2016；Earl & Deem, 2005）。这些方法易于实现、开销低，并能让MCMC采样在不同模式之间有效混合，而无需人为决定每条链应运行多久或何时重启。

离散空间的一个优势在于，可以通过存储所找到的最佳假设，直接在这些假设上显式计算后验分布的汇总统计量。例如，如果 h₁, h₂, …, h₁₀₀ 是找到的前100个最佳程序，我们可以通过在这有限假设集上重新归一化后验得分，来估计某个量，比如某个基本操作是否被使用。

其中，第一项的分母是一个归一化项，在所有假设 hi中为常数。分子是某个假设的后验得分，用于加权 Irecurse（或等价地，对所有满足 Irecurse为真的假设的后验概率求和）。从最佳假设中进行估计之所以有效，是因为通常情况下，几乎所有的后验概率质量都将由这些得分最高的假设占据。相比之下，

连续空间没有“100个最高后验概率假设”的概念，必须直接使用样本。

一种已被证明有效的通用方法是在程序上运行并行退火（parallel tempering），并存储任意一条链所找到的一组离散的最佳假设。当我们计算学习曲线或做出预测时，我们会遵循贝叶斯法则，但将这些最佳假设视为一个固定、有限的假设空间。如果我们感兴趣的是将发展变化建模为证据的积累过程，我们将在不同数量的数据下运行并行退火，并将固定的假设空间计算为在任意数据量下所找到的最佳假设的并集。其结果通常是数千或数万量级的假设。这些数字作为离散、有限的空间来处理对于贝叶斯推断而言是微不足道的——例如，绘制学习曲线或计算后验预测分布——但对于该集合采样出良好假设仍然是一个困难的推断问题。换句话说，空间的离散性使我们能够部分地将我们想要从后验分布中计算的内容与用有限假设集近似后验分布的任务分离开来。重要的是，当我们考虑拥有数万个假设的学习模型时，我们并不一定意味着学习者会代表所有这些假设。拥有智能推断技术的学习者（如下文讨论）可能只代表少数几个假设。通常，作为建模者，我们希望确保没有遗漏任何可能的假设，因此找到一大组合理的假设代表的是一种理想观察者模型，而非学习者实际经验的过程模型。

19.7 未来方向

本章回顾了若干关键思想，它们构成了我们将发展过程建模为程序学习的基础。现在，我们将简要介绍这些思想如何被扩展和结合，并转向近期研究中已探索的一些方式。

19.7.1 学习可复用组件

此处发展的程序学习图景侧重于获取单个程序，通常是一个单一函数。这一思想的一个重要扩展是学习一个函数库，这些函数可以被称为子程序（subroutines）（Ellis 等, 2021; 2020; Dechter, Malmaud, Adams, & Tenenbaum, 2013; Talton 等, 2012; Cheyette & Piantadosi, 2017; Bowers 等, 2023）。直观上，定义子程序的能力扩展了可用基本操作的集合，这显著影响了大多数程序学习者的归纳偏置。例如，我们可能希望将“列表中的每个其他元素”这样的概念表示如下：

拥有这个基本操作后，我们便可以轻松地学习像“所有奇数位置的元素后跟所有偶数位置的元素”这样的程序，如下所示：

ℱ(lst) = append(every-other(lst), every-other(rest(lst)))。 (19.29)

如果没有 every-other，函数 ℱ 的描述长度会更长（大约相当于公式 (19.29) 的长度加上公式 (19.28) 长度的两倍）。因此，在多任务设置中（即学习者试图获取多个程序时），学习子程序尤其有用。例如，设想一个程序学习者试图解决30个不同的问题，这些问题都涉及从列表中挑选子集。假设初始文法与前文讨论的文法不同，不包含任何 filter 操作。在这种情况下，定义一个共享库（包括 filter 以及可能的一组常用谓词）将非常有用。

学习库（library learning）提出了一个有趣的统计学问题：学习者应如何决定在库中包含哪些内容？对此问题的一个直观解决方案是使总描述长度最小化（即，所有已学习程序的长度加上每个子程序的长度）。这种方案在存储子程序的成本与其被多次复用的潜力之间取得了平衡。许多数学模型形式化了这一直觉（例如，O’Donnell, 2015；Goodman 等, 2008b；Ziv & Lempel, 1978），但由于需要考虑的可能库数量庞大，这些方案在实践中往往难以应用。一种在简单场景下效果良好的近似技术是运行多个 MCMC 链，每个链被限制在一个固定的库结构内（例如，一条链可能有一个包含三个子程序的库，并要求每个子程序都被调用，而另一条链可能只有一个子程序）（Yang & Piantadosi, 2022）。

程序归纳领域中被称为“归纳逻辑编程”（inductive logic programming）的分支，已发展出若干其他基于规则的方法来获取子程序，这被称为谓词发明（predicate invention）（例如，Muggleton, Lin, & Tamaddoni-Nezhad, 2015）。

另一种对多任务学习者特别有用的方法是随时间逐步扩展库。例如，学习者可以从一个初始文法开始，用它解决分配问题的10%。它可以检查这些解法，找出重复的代码段，将这些重复部分提取为子程序，并将其添加到自己的文法中。这个新扩展的文法现在可能允许它解决20%的问题，此时它可以寻找新的重复代码块并重复该过程。通过多次迭代这种方式，学习者可以发展出一个越来越有用的子程序库，并最终解决那些使用原始文法几乎不可能解决的难题。DreamCoder 算法（Ellis 等, 2020, 2021）应用了这一思想的精炼版本，或许是目前最成功的库学习模型。

19.7.2 学习邱奇编码

在某种重要意义上，程序学习模型能够创造出全新的知识体系，而这很可能正是理解人类学习所必需的。

Piantadosi（2021）研究了在邱奇编码（Church encodings）的逻辑系统上进行程序学习的问题（Pierce, 2002）。邱奇编码是逻辑学与计算机科学中的一个思想，指在一个逻辑系统中构造某些对象，以模拟另一个系统的动态行为（需注意，这里的“邱奇编码”不同于第18章讨论的“Church 编程语言”）。这项工作展示了如何通过将诸如数字、布尔逻辑、量词、支配等级结构（dominance hierarchies）和列表等表征编码到一个极简的底层逻辑中，从而实现对它们的学习。

为说明这在 λ 演算中如何运作，考虑将布尔逻辑中的项（true、false、and、or、not）映射到纯 λ 演算（即仅包含 λ 项的 λ 演算）中的表达式：

公式（19.30）中的定义应被理解为对布尔逻辑中每个符号所对应的程序进行编码。但重要的是，这些程序并非用具有内在语义内容的基本操作（如 CAUSE 或 GO）来定义的。这些符号被映射为 λ 演算中本质上仅具语法结构的表达式。然而，它们使我们能够遵循 λ 演算的规则来计算问题的答案，例如：“or(true, false) 的结果是什么？”为此，我们将相应的 λ 项代入该表达式，并依据 λ 演算的规则对其进行求值：

结果正确地得到了 false。这些计算过程虽然繁琐，却意义深远：λ 表达式的求值机制成功地计算出了布尔逻辑表达式的正确结果。这一性质对所有可在布尔逻辑中计算的命题都成立；例如，当将对应的 λ 项代入 and、or、not、true 和 false 后，表达式 and(not(or(true, false)), not(true)) 也会求值得到正确答案。

尽管布尔逻辑并未显式“内建”于 λ 演算的语法之中，上述结果依然成立。换言之，公式（19.30）提供了一种将布尔逻辑编码进 λ 演算的方式，从而“诱导”λ 演算固有的求值机制去表征另一个逻辑系统。这是极简编程系统得以表达更丰富知识体系的一种途径。事实上，让 λ 演算（或数十种其他等价系统中的任意一种）编码一个新领域，几乎总是可行的：λ 演算是一种图灵完备（Turing-complete）系统，因此我们想要的任何计算或计算机程序，都可以被编译为仅由 λ 演算组合而成的表达式，而无需引入任何其他基本操作。

因此，学习邱奇编码程序的学习者，能够在不依赖除 λ 演算语法之外任何基本原语的情况下，创造出全新的逻辑系统。Piantadosi（2021）将此类学习者视为一种发展模型，并使用了比 λ 演算更简单的系统——组合子逻辑（combinatory logic）——后者能以更直接的方式编码进神经网络。邱奇编码可能回答了关于认知发展的深层问题，因为它展示了如何在不预设人类婴儿可能尚未具备的原始概念（如数字、布尔逻辑、家谱结构等）的前提下，构建出一个图灵完备的系统。所有这些结构都可以作为有组织的计算被发现，使学习者能够构建逻辑与计算系统，用以解释他们对世界的观察。

19.7.3 像黑客一样学习

Rule 等人（2020）提出的“类黑客”（Hacker-like, HL）模型也探索了除简单采样和搜索之外，学习者在推断过程中可能利用的其他资源。其基本直觉是：当我们观察到如下数据时：

我们可能会注意到输入与输出之间存在一些可疑的关联。例如，两者长度相同，这暗示像 map 这样的操作可能是可行的。其次，我们可能注意到，当输出数字与输入不同时，它们仅相差 1。接着，我们还可能发现，只有列表中每隔一个元素才发生变化。

学习模型可以使用“推理步骤的文法”（而非基本操作的文法）来形式化这些推断。Rule 等人的模型不仅维护一个假设的程序，还维护一系列将输入转换为输出的变换步骤。例如，其中一种变换可能仅仅是记住正确的输出；另一种变换则可能抽象出一个 λ 函数，将 +1 映射到列表中适当的位置上。Rule 等人证明，与随机采样相比，这种学习模型在必须主动考虑的假设数量上表现显著更优——通常只需考虑大约 50 到 100 个假设，使其在搜索需求上更接近人类的实际规模。值得注意的是，该模型在大规模人类列表函数实验中的拟合效果也明显优于其他替代模型。

19.7.4 基于项重写的程序学习

除了上述搜索策略之外，类黑客（HL）模型还采用了一种不同于标准程序基本操作或 λ 演算的表征方式进行学习。它在项重写系统（term rewriting systems）上学习程序，这使学习者能够明确陈述结构化计算如何进行的规则。

为说明项重写的思想，考虑儿童在代数课上学习的一个基本变换，例如：

项重写将这一系列步骤视为对计算过程本身的正式刻画，其中所使用的规则系统即为程序。这种计算可能在某个时刻终止（当无法再应用任何变换规则时），也可能无限循环，正如程序的行为一样。通常，这类系统允许非确定性（nondeterminism），即在每一步可能有多个规则可以应用，因此求值过程需要探索所有可能的推导路径（这与引入 flip 操作后需要探索所有执行路径的情形类似）。重要的是，项重写系统具备与图灵机同等的计算能力。

类黑客（HL）模型考虑的学习者拥有一种用于编写此类变换规则的文法，并需要找到一组规则，以捕捉特定领域所需的知识。例如，你可以在该框架下构建一个关于数字的理论，用以解释数字在数理逻辑中是如何被形式化的（例如皮亚诺公理（Peano axioms；Peano, 1889）和罗宾逊公理（Robinson axioms；Robinson, 1949））：

这些规则描述了由符号构成的结构所进行的纯语法变换。就其本身而言，没有任何单个符号具有内在意义。例如，“+”之所以表示加法，并非因为它本身象征加法，而仅仅是因为它在上述规则中所扮演的角色。然而，学习者也可能习得其他规则，使“+”扮演不同的角色。例如，如果我们交换这些规则中的“·”和“+”，该系统仍然描述了一个数的理论，只不过此时用“·”表示加法，而“+”表示乘法。相反，如果我们引入诸如 a+a=S(a)或 S(S(a))=S(a)这样的规则，我们将得到一个有趣的计算系统，但它不再能刻画自然数理论。因此，学习者的挑战在于找到一组与某个领域动态一致的规则（例如，能够解释该领域中的数据）。当这种情况发生时，项重写系统便同时定义了该领域中的关键结构与过程。

项重写系统能够完成邱奇编码模型所能做的一切，因为 λ 表达式（或等价系统）本身就可以通过项重写规则进行求值。但项重写所学到的理论和表征通常更直观，因为其动态行为是通过项如何重写而透明地定义的，而不是像 λ 演算那样，通过另一套系统的动态机制进行晦涩的编码。这些理论的一个理想目标是，使程序学习模型能够习得真正的知识体系——例如在不同领域中进行推理、操作任意复杂结构所需的知识体系。

项重写系统的另一个有用特性是，很容易更改其所定义变换的符号集合。与邱奇编码不同，符号在使用前无需在某个基础系统中被预先定义。只需添加使用新符号的规则，该符号便开始成为系统所描述的计算网络的一部分；类似地，从规则中移除某个符号，也就将其从系统中移除了。从这个意义上说，在项重写系统集合上定义的假设空间能够实现真正的概念变化（conceptual change）。

由此产生的知识体系最终更像丰富的认知理论。正如人工智能（AI）领域曾长期认为的那样，在大量命题规则上进行程序学习，可能是通向类人知识的一条有效路径。例如，编程语言 Prolog 的工作方式与本文讨论的大多数程序有根本不同：Prolog 程序是对逻辑关系的声明，其行为由一种回溯搜索（backtracking search）决定，该搜索本质上是在探索初始陈述的逻辑推论。项重写和类 Prolog 的表征方式，或许能帮助程序学习超越单一程序，迈向更丰富的知识体系。事实上，Prolog 表征已在归纳推理领域被广泛研究（Muggleton, 1995；Muggleton & De Raedt, 1994）。

19.8 结论

本章讨论了将学习建模为编程这一方法背后的核心思想。该方法解释了人类似乎能够轻松内化的广泛概念结构，并将人类学习研究与人工智能、机器学习和概率推断领域的理论紧密联系起来。我们所概述的计算思想——包括程序上的文法、随机采样和邱奇编码——为澄清那些传统上仅依赖非正式哲学概念的学习与发展争论，提供了一套极具说服力的工具。这些方法也具有实证有效性：程序学习模型在众多不同领域中解释了学习的诸多方面。综合来看，这些成果表明，在程序空间上进行贝叶斯推断是理解人类学习的一种强大工具。