形式化学习理论 learning theory, formal (Oliver Schulte)

首次发表于 2002 年 2 月 2 日，实质性修订于 2022 年 3 月 23 日。

形式化学习理论是规范认识论的数学体现。它涉及一个代理如何利用对其环境的观察来得出正确和有信息量的结论的问题。像普特南、格莱默和凯利这样的哲学家已经将学习理论发展为科学推理和归纳推理的规范框架。

术语。认知科学和相关领域通常使用“学习”一词来表示通过观察获得信息的过程，因此称之为“学习理论”。对于大多数认知科学家来说，“学习理论”一词暗示了源自心理学行为主义范式的人类和动物学习的经验研究。形容词“形式化”将本条目的主题与行为主义学习理论区分开来。学习论认识论的哲学术语包括“逻辑可靠性”（凯利 [1996]，格莱默 [1991]）和“目的手段认识论”（舒尔特 [1999]）。

由于形式化学习理论的许多发展和应用来自计算机科学，因此“计算学习理论”这个术语也很常见。计算机科学中关于学习理论的许多结果涉及到 Valiant 和 Vapnik 关于学习一般化的概念，即可能近似正确的学习（PAC 学习）（Valiant [1984]）。这种经验成功的概念是由 Gilbert Harman 在他的 Nicod 讲座中引入哲学家，并在随后的一本书中详细阐述的 [Harman and Kulkarni 2007]。Valiant 本人在最近的一本书中提供了关于 PAC 学习及其与归纳问题的关系的易于理解的描述（Valiant [2013, Ch. 5]）。本文描述了一种非统计学传统的学习理论，源自 Hilary Putnam [1963] 和 Mark E. Gold [1967] 的开创性工作。最近的研究将可靠主义的手段-目的方法扩展到了一个统计学的环境中，其中归纳方法从随机样本中为统计假设分配概率。这种新的统计框架在本条目的最后部分，即可靠统计调查部分进行了描述。

哲学特点。与归纳推理的其他哲学方法相比，学习理论不旨在描述一种普遍的归纳方法或阐明归纳合理性的一般公理。相反，学习理论追求一种依赖于上下文的手段-目的分析 [Steele 2010]：对于给定的经验问题和一组认知目标，什么是实现这些目标的最佳方法？大部分学习理论研究的是哪些调查策略能够可靠且高效地导致对世界的正确信念。

文章概述。与传统的归纳推理哲学讨论相比，学习理论提供了一种根本性的新思考归纳和科学方法的方式。本文的主要目的是通过示例来解释该理论的主要概念。运行示例在整个条目中重复出现；同时，各节应尽可能独立。我们使用这些示例来说明一些具有哲学意义的定理，并突出学习理论背后的关键哲学思想和洞见。

对于对学习理论的数学实质感兴趣的读者，可以在参考文献中找到一些参考资料，并在补充文件中找到基本定义的摘要。Jain 等人的一本书收集了许多主要的定义和定理 [1999 年]。新的结果出现在年度会议的论文集中，例如学习理论会议（COLT）和算法学习理论会议（ALT）。与学习理论认识论相关的哲学问题和动机在哲学家普特南（Putnam）、格莱默（Glymour）和凯利（Kelly）的著作中得到了广泛讨论（Putnam [1963]，Glymour [1991]，Glymour and Kelly [1992]，Kelly [1996]）。

1. 趋向真理，只有真理

形式化学习理论对形成信念的倾向进行了评估。在哲学中，有几个用于信念获取过程的术语常被使用；我将使用“归纳策略”、“推理方法”和最常用的“归纳方法”来表示同一概念。了解学习理论如何评估归纳方法的最佳方式是通过一些例子进行实际操作。以下介绍从一些非常简单的归纳问题开始，逐渐过渡到更复杂和更现实的情境。

1.1 简单的普遍概括

让我们重新思考一个经典问题，即所有乌鸦是否都是黑色的。想象一个鸟类学家通过逐个观察乌鸦来解决这个问题。存在一种观察序列，其中只有黑色乌鸦被发现；其他所有序列中至少有一只非黑色乌鸦。下图说明了可能的观察序列。图中的点表示可以进行观察的点。点左侧的黑鸟表示在这个阶段观察到了一只黑色乌鸦。同样，点右侧的白鸟表示观察到了一只非黑色乌鸦。给定完整的观察序列，观察到的乌鸦要么全部是黑色的，要么全部是非黑色的；图中标记了完整观察序列的陈述是关于它们的真实陈述。灰色的扇形表示在观察到一只白色乌鸦后，关于不是所有乌鸦都是黑色的主张在所有由进一步观察导致的观察序列中成立。

图 1 [图 1 的详细描述在附录中。]

如果世界上只有黑乌鸦存在，我们希望鸟类学家能够确定这个概括。（可能有一些非黑乌鸦永远隐藏在视线之外，但即使如此，“所有乌鸦都是黑色的”这个概括至少是符合观察结果的。）如果世界上最终发现了一只非黑乌鸦，那么我们希望鸟类学家得出结论：并非所有乌鸦都是黑色的。这确定了一组研究的目标。对于可能代表鸟类学家在证据面前采纳猜想的任何归纳方法，我们可以问这个方法是否达到了这些目标。有无数种可能的方法可以考虑；我们将只看两种方法，一种是怀疑论的方法，另一种是大胆概括的方法。大胆的方法在看到第一只乌鸦是黑色的后，猜想所有乌鸦都是黑色的。除非出现了一只非黑乌鸦，否则它会坚持这个猜想。怀疑论的方法不超越证据所蕴含的内容。因此，如果发现了一只非黑乌鸦，怀疑论的方法会得出结论：并非所有乌鸦都是黑色的，但在其他情况下，该方法不会做出任何猜想。下图说明了大胆方法和怀疑论方法。

图 2 [图 2 的详细描述在附录中。]

这些方法是否达到了我们设定的目标？考虑一下大胆的方法。有两种可能性：要么所有观察到的乌鸦都是黑色的，要么找到了一只非黑色的乌鸦。在第一种情况下，该方法推测所有乌鸦都是黑色的，并且从不放弃这个推测。在第二种情况下，一旦找到第一只非黑色的乌鸦，该方法就会得出结论，即并非所有乌鸦都是黑色的。因此，无论证据如何，最终该方法都能给出关于所有乌鸦是否都是黑色的正确答案，并坚持这个答案。学习理论家将这样的方法称为可靠的，因为它们无论世界提供了什么观察结果，都能得出正确答案。

怀疑论方法并不那么成功。如果出现一只非黑色的乌鸦，那么该方法确实得出了正确的结论，即并非所有乌鸦都是黑色的。但是，如果所有乌鸦都是黑色的，怀疑论者从不进行“归纳性跳跃”来采用这个概括。因此，在这种情况下，怀疑论者未能给出关于所有乌鸦是否都是黑色的正确答案。

这说明了手段-目的分析如何评估方法：大胆的方法实现了可靠地得出正确答案的目标，而怀疑论方法则没有。请注意，这种针对怀疑论者的论证的特点：在这种观点中，问题不在于怀疑论者违反了某种合理性准则，或者未能理解“自然的一致性”。学习理论分析承认怀疑论者的观点，即无论过去观察到多少只黑色乌鸦，下一只可能是白色的。问题在于，如果所有观察到的乌鸦确实都是黑色的，那么怀疑论者从未回答过“所有乌鸦都是黑色的吗？”这个问题。要得出这个问题的正确答案，需要从证据中进行概括，即使这个概括可能是错误的。

就于粗体方法而言，明确其所能及所不能达到的目标是很重要的。该方法最终会得出正确答案，但我们（或者说它）可能永远无法确定是否已经做到了这一点。正如威廉·詹姆斯所说，“当科学找到正确答案时，没有钟声响起”。我们确信该方法最终会得出正确答案，但我们可能永远无法确定当前的答案是否正确。这是一个微妙的观点；下一个例子将进一步说明这一点。

1.2 归纳的新谜题

尼尔森·古德曼提出了一个关于归纳推理的著名难题，被称为（新的）归纳之谜（[Goodman 1983]）。我们的下一个例子受到他的难题的启发。古德曼考虑了关于翡翠的概括，涉及到熟悉的绿色和蓝色，以及某些不寻常的颜色：

假设在某个时间 t 之前检查的所有翡翠都是绿色的... 我们的证据陈述声称翡翠 a 是绿色的，翡翠 b 是绿色的，等等...
现在让我们引入一个比“绿色”更不常见的谓词。它是“grue”，它适用于在时间 t 之前检查的所有事物，只有当它们是绿色的时候才适用，而对于其他事物，只有当它们是蓝色的时候才适用。那么在时间 t，对于每个声称给定的翡翠是绿色的证据陈述，都有一个相应的声称该翡翠是 grue 的证据陈述。问题是，当我们获得在时间 t 之前检查的绿色翡翠样本时，我们是否应该推测所有翡翠都是绿色的，而不是所有翡翠都是 grue 的，如果是的话，为什么。

显然，在这个问题中我们有一系列的 grue 谓词，每个不同的“关键时间”t 都有一个；让我们用 grue(t)来表示这些 grue 谓词。按照 Goodman 的说法，在讨论这个例子时，让我们将方法称为投射规则。投射规则在一个世界中成功，只有在它确定了一个在该世界中正确的概括。因此，在一个所有检查过的翡翠都被发现是绿色的世界中，我们希望我们的投射规则收敛到所有翡翠都是绿色的命题。如果所有检查过的翡翠都是 grue(t)，我们希望我们的投射规则收敛到所有翡翠都是 grue(t)的命题。请注意，这个规定完全平等地对待绿色和 grue 谓词，没有任何偏向。与之前一样，让我们考虑两个规则：自然投射规则，只要发现的都是绿色的翡翠，就猜测所有的翡翠都是绿色的；可怕的规则，它不断投射下一个与现有证据一致的 grue 谓词。用绿蓝词汇表达，可怕的投射规则猜测在观察到一些数量为 n 的绿色翡翠后，所有未来的翡翠都将是蓝色的。下面的图示了可能的观察序列、自然投射规则和可怕的投射规则。

图 3 [图 3 的详细描述在附录中。]

下图显示了可怕的投射规则。

图 4 [图 4 的详细描述在附录中。]

这些规则如何符合达到真正概括的目标？为了举例说明，假设只有两种严肃考虑的可能性：（1）要么所有的翡翠都是绿色的，要么（2）所有的翡翠在某个关键时间 t 上都是 grue(t)。然后，无论正确的概括是什么，自然投射规则都会得出正确的概括。因为如果所有的翡翠都是绿色的，自然投射规则从一开始就断言了这个事实。假设所有的翡翠在某个关键时间 t 上都是 grue(t)。那么在时间 t，会观察到一个蓝色的翡翠。此时，自然投射规则会得出所有的翡翠都是 grue(t)的猜想，根据我们对可能的观察序列的假设，这一猜想必须是正确的。因此，无论在探究过程中获得了什么证据（与我们的背景假设一致），自然投射规则最终都会得出关于翡翠颜色的正确概括。

可怕的规则表现不佳。因为如果所有的翡翠都是绿色的，该规则将永远不会猜测到这个事实，因为它一直在投射 grue 谓词。因此，存在一种可能的观察序列，即所有的翡翠都是绿色的观察序列，在这个序列上，可怕的规则无法收敛到正确的概括。因此，手段-目的分析会推荐自然投射规则而不是可怕的规则。

1.3 讨论

归纳之谜的目标-手段分析展示了一些在学习理论分析中普遍适用的哲学上重要的观点。

对所有假设的平等对待。与前面的例子一样，这个论证并不依赖于某些可能性不被事先认真对待的论证。特别是，论证中没有说使用 grue 谓词的概括是不合法的、不合理的，或以某种其他方式在先验上劣于“所有的翡翠都是绿色”的观点。
语言不变性。分析不依赖于证据和概括所使用的词汇。为了便于阐述，我主要使用了绿蓝参考框架。然而，grue-bleen 说话者会同意，可靠地确定正确的概括需要自然投射规则，而不是可怕的规则，即使他们希望用他们的 grue-bleen 语言来表达自然规则的猜想，而不是迄今为止我们所使用的蓝绿语言。
上下文依赖性。尽管分析不依赖于语言，但它确实依赖于对可能的观察序列的假设。上述描述的示例似乎包括了 Goodman 自己讨论的颜色谓词所对应的可能性。但是，目的手段分析同样适用于其他一些可能的谓词集合。Schulte [1999] 和 Chart [2000] 讨论了许多其他版本的归纳之谜，在其中目的手段分析倾向于投射所有绿宝石都是 grue，基于所有绿宝石的样本。

1.4 验证主义和带有例外的概括

我们的前两个例子涉及简单的普遍概括。如果我们考虑允许例外的概括，特别是与伪证主义的关系，那么对于长期可靠性概念的一些微妙方面就会变得明显起来。为了说明这一点，让我们考虑另一个鸟类学的例子。正在调查两个竞争的假设。

除了有限多只天鹅是白色的。也就是说，基本上所有的天鹅都是白色的，除了有限数量的例外。
除了有限多只天鹅是黑色的。也就是说，基本上所有的天鹅都是黑色的，除了有限数量的例外。

假设这些假设中的一个是正确的，是否存在一种归纳方法可以可靠地确定正确的假设？使这个问题比我们前面两个问题更困难的是，每个正在调查的假设都与任何有限数量的证据一致。如果找到了 100 只白天鹅和 50 只黑天鹅，那么这 50 只黑天鹅或者这 100 只白天鹅可能是例外。用卡尔·波普尔的工作所熟悉的术语来说，我们可以说这两个假设都不可证伪。因此，前两个例子中的归纳策略在这里不起作用。这个策略基本上是采用“大胆”的普遍概括，比如“所有乌鸦都是黑色的”或者“所有翡翠都是绿色的”，并且只要这个猜想“通过检验”，就坚持这个猜想。然而，当调查的规则中存在可能的例外时，这个策略是不可靠的。例如，假设一个调查者首先采纳了“除了有限多只天鹅是白色的”这个假设。可能的情况是，从那时起，只有黑天鹅被发现。但是，每一个这样的反例都可以被“解释掉”作为一个例外。如果调查者遵循坚持她的猜想，直到证据在逻辑上与猜想不一致的原则，她将永远不会放弃她错误的信念，即除了有限多只天鹅是白色的，更不会得出正确的信念，即除了有限多只天鹅是黑色的。

可靠的调查需要更微妙的调查策略。这里是其中之一（众多中的一个）。以竞争性假设之一开始调查，比如说“除了有限数量的天鹅是黑色的”。选择一些截断比例来代表“明显的多数”；为了明确起见，我们假设是 70%。如果当前的猜想是除了有限数量的天鹅是黑色的，那么只有当观察到的天鹅中有超过 70%是白色的时候，才改变你的想法，猜想除了有限数量的天鹅是白色的。同样地，如果当前的猜想是除了有限数量的天鹅是白色的，当观察到的天鹅中有超过 70%是黑色的时候，也要按照同样的方式进行。

稍加思考就可以发现，这个规则能够可靠地在长期内识别出正确的假设，无论这两个竞争性假设中的哪一个是正确的。因为如果除了有限数量的天鹅是黑色的，最终违反这个规则的非黑色天鹅将会耗尽，观察到的天鹅中将会有任意大的多数是黑色的。同样地，如果除了有限数量的天鹅是白色的。

具有例外的概括说明了波普尔的证伪主义与学习理论中可靠收敛于真理的思想之间的关系。在某些研究环境中，尤其是涉及普遍概括的情况下，一种天真的波普尔式的“猜测与反驳”方法，即坚持猜测直到证据证伪它们，确实可以产生可靠的归纳方法。但在其他问题中，比如当前的例子中，这种方法并不适用。依赖于证伪有时是研究进行的最佳方式，但并非总是如此。学习理论提供了数学定理，阐明了猜测与反驳方法与可靠研究之间的关系。具体细节在第 3 节（研究的限制和经验问题的复杂性）中进行了讨论。一般来说，用不可证伪的假设解决学习问题的方法可以表示为使用一个经过改进的假设空间，其中原始假设被可证伪的加强假设所取代。

2. 科学实践中的案例研究

本节提供了进一步的例子来说明学习理论分析。本节中的例子更加现实，并涉及科学实践中出现的方法论问题。它们不是概率性的；统计假设在第 6 节中进行了讨论。本条目提供了完整分析的概要；下面有更详细讨论的参考资料。更多案例研究可参考 [Kelly 1996, Ch. 7.7, Harrell 2000]。希望进一步发展手段-目的认识论的理论和哲学的读者可以跳过本节而不会失去连贯性。

2.1 粒子物理学中的守恒定律

粒子物理学的一个标志性特点是发现了仅适用于亚原子领域的新的守恒定律 [Ford 1963, Ne’eman and Kirsh 1983, Feynman 1965]。（费曼将其中之一，即重子数守恒定律，与能量、电荷和动量的其他“伟大守恒定律”归为一类。）简化一些，守恒原理用于解释为什么某些涉及亚原子粒子的过程不会发生：解释是某个守恒原理被违反了（参见 Omnes [1971, Ch.2] 和 Ford [1963]）。因此，粒子研究的目标是找到一组守恒原理，对于每个根据（已知的）物理定律可能发生但在实验中未被观察到的过程，都有某个守恒原理排除了该过程。而如果一个过程实际上被观察到发生，那么它应该满足我们引入的所有守恒定律。

这构成了一个推理问题，我们可以应用手段-目的分析。推理方法根据观察到的过程报告产生一组守恒原理。手段-目的分析询问哪些方法能够保证确定一组解释所有观察结果的守恒原理，即排除未观察到的过程并允许观察到的过程。Schulte [2008] 描述了一种能够实现这一目标的归纳方法。非正式地说，该方法可以描述如下。

假设我们观察到了一组基本粒子之间的反应。
推测一组允许观察到的反应并排除尽可能多的未观察到的反应的守恒定律。

守恒定律的逻辑是，观察到一些反应就意味着可能存在其他未观察到的反应。学习理论方法排除了所有不成立的反应。事实证明，根据目前可用的证据，这种方法所确定的守恒原则与物理学家引入的原则在经验上是等效的。具体而言，它们的预测与电荷守恒、重子数守恒、缪子数守恒、τ 子数守恒和轻子数守恒完全一致，这些是粒子物理学标准模型的一部分。

对于一些物理过程来说，获得经验上充分的守恒原理的唯一方法是假设一些隐藏的粒子未被探测到。Schulte [2009] 扩展了这个分析，使归纳方法不仅可以引入守恒定律，还可以假设看不见的粒子。基本原则仍然是以这样的方式假设看不见的粒子，以排除尽可能多的未观察到的反应。当这种方法应用于已知的粒子数据时，它重新发现了电子反中微子的存在。这是当前粒子物理学中关注的重要粒子之一。

2.2 因果关系

对于学习因果关系的研究已经有了实质性的成果，这些成果以因果图的形式表示 [Spirtes et al. 2000]。Kelly 提出了一种学习理论分析的方法，用于推断因果关系，其中证据以所观察到的感兴趣变量之间的显著相关性的形式提供（这是休谟的“恒常联结”的现代版本）。以下归纳方法保证在观察到越来越多的相关性时收敛到一个经验上充分的因果图 [Schulte, Luo and Greiner 2007]。

假设我们观察到一组感兴趣的变量之间的一组相关性或关联。
选择一个能用最少数量的直接因果关系解释观察到的相关性的因果图。

2.3 认知架构模型

一些心灵哲学家认为，心灵由相当独立的模块组成。每个模块都有来自其他模块的“输入”，并向其他模块发送“输出”。例如，“听觉分析系统”模块可能以听到的单词作为输入，并将音素分析发送到“听觉输入词典”。模块化组织的概念引发了一个实证问题，即有哪些心理模块以及它们如何相互关联。认知神经科学研究的一个重要传统试图通过研究正常和异常受试者对各种刺激的反应来发展这种心理结构模型。其想法是将正常反应与异常反应进行比较，通常是由于脑损伤引起的，以便推断出哪些心理能力彼此依赖以及如何依赖。

Glymour [1994] 提出了可靠主义问题，即是否存在一些推理方法，可以保证最终确定心理组织的真实理论，只要有关正常和异常能力和反应的详尽证据。他认为，对于某些可能的心理结构，无论刺激-反应类别的证据有多少，都无法区分它们。由于可用证据决定了归纳方法的猜测，因此不能保证方法会确定认知结构的真实模型。Glymour 还探讨了更丰富的证据在解决心理结构的不确定性方面的程度。（更丰富的证据的一个例子是双重解离。双重解离的一个例子是一对患者，一个患者对理解口语单词具有正常能力，但无法理解书面单词，另一个患者则理解书面单词但不理解口语单词。）

在进一步的讨论中，Bub [1994] 表明，如果我们对心理模块的连接方式做出一些限制性假设，那么一组完整的行为观察将使神经心理学家能够确定（正常）心智的模块结构。事实上，在 Bub 的假设下，存在一种可靠的方法来识别模块化结构。该过程的高层思想如下。

每个假设的模块化结构可以用一个图 G 来表示，其中如果模块 M1 调用模块 M2，则存在一条从模块 M1 到模块 M2 的边。
每个模块图 G 与一组可能的模块路径一致。如果图 G 的路径是图 G'的路径的子集，则称图 G 比图 G'更受限制。
假设任何最大限度受限的模块图 G，即没有比 G 更受限的图 G'。

2.4 讨论

这些研究展示了学习理论的一些普遍特征：

普遍性。该理论的基本概念非常普遍。实质上，只要有一个引发探究的问题、一些候选答案以及一些用于决定答案的证据，该理论就可以应用。因此，手段-目的分析可以应用于任何旨在获得经验知识的学科，例如物理学或心理学。
上下文依赖性。学习理论是纯粹的规范性先验认识论，因为它涉及评估可能的探究环境中的方法的标准。但这种方法并不追求普遍的、无上下文的方法论准则。方法论建议取决于偶然因素，例如操作性方法论规范、研究的问题、主体在探究中带入的背景假设、她可利用的观察手段、她的认知能力和她的认识目标。因此，要评估特定领域中的具体方法，如所提到的案例研究，就必须研究所讨论案例的细节。手段-目的分析通常通过指出给定科学企业的关键方法特征，并解释为什么以及如何这些特征与企业实现其认识目标的成功相关联，从而回报这种研究。
折衷。从手段-目的论的角度来看，探究涉及到与困难选择的持续斗争，而不是执行普遍的“科学方法”。探究者必须平衡冲突的价值观，并可能考虑各种策略，比如在短期内接受困难，希望能在长期解决它们。例如，在守恒定律问题中，理论的简洁性（即提出更少的守恒定律）和本体论的简洁性（即引入更少的隐藏粒子）之间可能存在冲突。再举一个例子，粒子理论家可能会接受假设存在未被探测到的粒子，希望随着科学的进展，它们最终会被观察到。寻找希格斯玻色子就是这种策略的例证。一个重要的学习理论项目是研究这种折衷何时出现以及解决它们的选择是什么。第 4 节将学习理论分析扩展到考虑除了长期可靠性之外的目标。

3. 探究的限制和经验问题的复杂性

在看到了上述几个例子之后，人们开始思考其中的规律。一个经验问题有什么特点使得探究能够可靠地得出正确答案？我们能从可靠方法如何测试假设中获得哪些一般性的见解？学习理论家通过表征定理来回答这些问题。表征定理通常具有以下形式：“如果一个归纳问题满足以下条件，那么在给定的归纳问题中可以达到这种经验成功的标准”。

首先，我们先讨论在背景知识的基础上，查询能否确定一个经验假设是否正确的情况。然后，我们考虑查询何时以及如何能够收敛到一个正确的假设，而不需要得出确定的结论，正如第 1 节所述。我们将引入足够的定义和形式概念来准确陈述结果；补充文件提供了完整的形式化。

一个学习问题由一组有限或可数无限的可能假设 H=H1,H2,…,Hn,…来定义。这些假设是互斥的，并共同涵盖了与查询者的背景假设一致的所有可能性。

举例说明

在第 1.1 节的乌鸦颜色问题中，有两个假设 H1=“所有（观察到的）乌鸦都是黑色”和 H2=“某些（观察到的）乌鸦不是黑色”。
在第 1.2 节的归纳新谜题中，有无限多个备选假设：我们有 Hgreen=“所有（观察到的）翡翠都是绿色”，以及形式为 Ht=“所有（观察到的）翡翠都是 grue(t)”的可数个备选假设，其中 t 是一个自然数。

本节定义了决定观察推断是否能指示其正确性的假设属性。这些属性不是绝对的，而是相对于一组备选假设 H，其中任何一个都可能在调查者所知道的情况下成立。最基本的相对属性是相对蕴涵。

如果假设 H 对于某个扩展有限观测的完整数据序列是正确的，那么假设 H 与有限观测一致。
如果假设 H 与观测不一致，那么有限观测可以证伪假设 H。
如果假设 H 是与观测一致的唯一假设，那么有限观测相对于假设集 H 蕴含假设 H。

注意，由于逻辑蕴涵不依赖于我们用来构建证据和假设的语言，一致性、蕴涵和证伪的概念也不依赖于我们用来构建证据和假设的语言。

例子。回想一下第 1.1 节中的乌鸦场景（为方便起见，图表重复）。

图 1【图 1 的详细描述在附录中】。

第一个乌鸦是黑色的这一观察结果与两个假设 H1=“所有（观察到的）乌鸦都是黑色的”和 H2=“某些（观察到的）乌鸦不是黑色的”都是一致的。第一个乌鸦，或者任何乌鸦，是白色的这一观察结果证伪了假设 H1，并蕴含了假设 H2。这种蕴含关系可以通过灰色的扇形结构来说明，这意味着在观察到任何白色乌鸦之后，假设 H1 对于记录了所有进一步观察到的乌鸦颜色的完整数据序列是正确的。

3.1 可验证和可证伪的假设

我们需要理解可通过可靠调查解决的假设结构的概念集合是可验证和可证伪的假设。关于主张的可验证性和可证伪性已在认识论和科学哲学中进行了广泛讨论，特别是由关注逻辑经验主义问题的哲学家。本小节描述了这些概念在学习理论中的应用，并将学习理论概念与更广泛的认识论讨论进行了比较。

如果一个假设 H 是可验证的，那么只要 H 是正确的，最终会观察到证据表明 H 是正确的。更正式地说：对于一个假设集 H，如果对于每个 H 是正确的完整数据序列，存在有限数量的观察结果，可以证明所有来自 H 的备选假设 H'都是错误的。
如果一个假设 H 是可反驳的，那么只要 H 是正确的，最终会观察到证据证明 H 是错误的。更正式地说：对于一个假设集 H，如果对于每个 H 不正确（但 H 中的其他假设是正确的）的完整数据序列，存在有限数量的观察结果，可以证明 H 是错误的。

例子

假设 H2 =“一些（观察到的）乌鸦不是黑色”是可验证但不可证伪的。它是可验证的，因为对于任何使其正确的数据序列，在某个有限的时间内都会出现非黑色的乌鸦。观察到的非黑色乌鸦随附 H2。假设 H2 是不可证伪的，因为如果永远只观察到黑色乌鸦，那么 H2 是不正确的，但没有有限数量的观察可以证伪 H2。
假设 H1 =“所有（观察到的）乌鸦都是黑色”是可证伪但不可验证的。它是可证伪的，因为对于任何使其不正确的数据序列，在某个有限的时间内都会出现非黑色的乌鸦。观察到的非黑色乌鸦证伪了 H1。H1 是不可验证的，因为如果永远只观察到黑色乌鸦，那么 H1 是正确的，但没有有限数量的观察可以随附 H1。
在第 1.2 节的新归纳之谜中（为方便起见，下图重复），假设“所有（观察到的）翡翠都是绿色”是可证伪但不可验证的，原因与“所有（观察到的）乌鸦都是黑色”是可证伪但不可验证的原因相同。
任何一个绿蓝假设 Ht =“所有（观察到的）翡翠都是绿蓝的(t)”都是可验证和可证伪的。Ht 是可证伪的，因为对于任何一个完整的数据序列，如果可怕的概括是不正确的，那么就会有一个反例来证明它是错误的。Ht 是可验证的，因为如果它是正确的，时间 t 的第一个蓝色翡翠的观察结果将证明假设“所有（观察到的）翡翠都是绿色的”是错误的，并且也会证明所有其他的 Ht 假设是错误的。

可怕假设的例子表明经验假设既可以是可验证的，也可以是可证伪的（有时在类比于计算理论中称为“可决定的”）。其他典型的可决定经验性断言的例子包括单个观察，例如“第一个乌鸦是黑色的”，以及单个观察的布尔组合。

图 4 [图 4 的详细描述在附录中。]

我们将简要讨论与认识论和科学哲学相关概念的相似之处和差异。

验证主义是逻辑经验主义哲学的一部分。其核心思想是，为了一个主张具有意义，它必须经验上可验证。我们的概念与之主要的区别在于哲学目标：学习理论的目标不是将有意义的主张与无意义的主张分开，而是为了表征我们可以期望从对一组假设的探究中获得的经验成功的标准。根据上述定义，一个可验证的假设允许探究提供积极的测试：当假设正确时，探究将最终以确定性地指示其正确性（在给定背景知识的情况下）。逻辑经验主义者提供的“可验证性”的具体定义与学习理论意义上的可验证性并不等同。例如，严格的验证主义认为“为了具有意义，一个主张必须由有限数量的观察句子所蕴涵”。没有有限数量的观察句子等同于假设 H2 =“某个（被观察到的）乌鸦不是黑色”，因为这个假设等同于无限析取的观察句子（即，在时间 1 有一个非黑色的乌鸦，在时间 2 有一个非黑色的乌鸦，...）。

Falsificationism 是科学哲学中一个著名的观点。其核心思想是，为了使一个假设成为科学的，而不是伪科学或形而上学的，它必须具有可证伪性，即“陈述...为了被视为科学，必须能够与可能的或可想象的观察相冲突”（Popper 1962, 39）。我们的发展与之主要的区别在于哲学目标：学习理论的目标不是划分科学假设和伪科学理论，而是为了表征我们可以期望从一组给定的假设进行的研究中获得的经验成功的标准。根据上述定义，一个可被证伪的假设允许研究提供一个负面测试：当假设是不正确的时候，研究将最终以确定性地指示其不正确（在给定的背景知识下）。在 Popper 的引用中，“可证伪性”的具体定义与学习理论意义上的可反驳性并不等同 [Schulte and Juhl 1996]。例如，假设 H=“第一个乌鸦是黑色的，还有其他一些乌鸦是非黑色的”与第一个乌鸦是白色的可能观察相冲突。然而，如果事实上所有观察到的乌鸦都是黑色的，那么 H 是不正确的，但不会被任何有限数量的观察所证伪，因此不符合学习理论定义中的可反驳性。有关 Popperian 证伪和学习理论之间关系的进一步讨论，请参见 [Genin 2018]。

3.2 点集拓扑与可验证性公理

为了进一步阐明学习理论中可验证性和可反驳性的概念，我们注意到它们满足以下基本属性。我们给出非正式但严格的证明。

可验证假设的析取也是可验证的。

证明：设 H=H1 或 H2，…或 Hn 或…是可验证假设 Hi 的析取（该析取可能是无限的）。假设 H 对于一个完整的数据序列是正确的。那么对于该数据序列，一些 Hi 是正确的。由于 Hi 是可验证的，存在有限数量的观察结果可以推导出 Hi，进而推导出 H。因此，如果 H 对于任何完整的数据序列都是正确的，那么存在有限数量的观察结果来推导出 H，这是可验证性所要求的。例如，设 Hi 是可验证的假设，即在时间 i 存在一个非黑色的乌鸦。那么假设 H=“某个（观察到的）乌鸦不是黑色”等价于析取 H1 或 H2，…或 Hn 或…。由于每个假设 Hi 都是可验证的，因此 H 也是可验证的。

可验证假设的有限合取也是可验证的。

证明：设 H=H1 和 H2，...，Hn 是可验证假设 Hi 的有限合取。假设 H 对于完整的数据序列是正确的。那么每个 Hi 对于数据序列都是正确的。由于 Hi 是可验证的，存在有限数量的观察结果可以推导出 Hi。因为只有有限多个假设 Hi，最终每个假设都将被有限数量的观察结果验证，这推导出它们的合取 H。因此，如果 H 对于任何完整的数据序列是正确的，那么存在来自序列的有限数量的观察结果可以推导出 H，这是可验证性所要求的。例如，设 H1 是可验证的假设，即第一个乌鸦是非黑色的，H2 是可验证的假设，即第二个乌鸦是非黑色的。如果合取 H=H1 和 H2 对于数据序列是正确的，那么前两只乌鸦不是黑色的。因此，对于第一和第二只乌鸦的观察结果推导出 H。

一个重言式和一个矛盾（显然）是可验证的。

证明：一个重言式（例如“第一个观察到的乌鸦是黑色或不是黑色”）对于任何数据序列都是正确的，并且被任何证据序列所推导。一个矛盾（例如“第一个观察到的乌鸦是黑色且不是黑色”）如果是正确的话，就是显然可验证的，因为它从来不正确。

如果且仅当其否定可以被证伪时，一个假设才是可验证的。

证明：我们考虑充分性；逆命题类似。假设一个假设的否定 not H 是可证伪的。考虑任意一个完整的数据序列，其中假设 H 是正确的。那么 not H 是不正确的，并且将被有限次观察证伪，因为它是可证伪的。这个有限的观察集合蕴含了 H。因此，如果 H 对于任何完整的数据序列都是正确的，那么存在一个有限次观察的子序列，蕴含了 H，这是可验证性所要求的。例如，H = "一些（观察到的）乌鸦不是黑色" 是可证伪假设 not H = "所有（观察到的）乌鸦都是黑色" 的否定。如果 not H 对于一个完整的数据序列是不正确的，它将最终被观察到的一只非黑色的乌鸦所证伪。这个观察蕴含了 H。

引人注目的是，列出的属性恰好是一种重要的数学分支——点集拓扑学的基本公理 [Abramsky 1987，Vickers 1986]。一个拓扑空间由一组称为开集或邻域的集合定义，这些集合满足可验证假设的公理属性（任意并集和有限析取的闭包，空集和整个空间都是开集）。开集的集合论补集称为闭集，因此可证伪的假设与闭集完全对应。点集拓扑学的发明是为了支持一种不涉及数字（更准确地说，不涉及距离）的广义函数分析。令人惊讶的是，拓扑学的基础公理在经验假设的属性方面有一个确切的认识论解释，这些属性允许以确定性进行验证或证伪。当前的学习理论的数学发展通常从取满足列出属性的可验证假设集合作为基本概念开始。这种方法有两个优点。

形式化学习理论可以借鉴并为现代数学中最发达的分支之一提供丰富的概念和结果 [Kelly 1996，Baltag et al. 2015，de Brecht and Yamamoto 2008]。
将证据项的概念适应到应用的背景中，使得在不同领域中应用这一通用理论更加容易。例如，考虑获取某个感兴趣量（例如物理中的光速）的逐渐精确的测量问题。我们可以将可验证的基本假设集合定义为（真实值周围的）开区间的并集 [Baltag et al. 2015，MONIST，Genin and Kelly 2017]。另一个例子是下面第 6 节中涵盖的统计可验证性的概念。

为了具体起见，本条目描述了基本可验证假设为有限证据项序列的析取的示例。我们将以一种只假设列出的公理性质的方式来描述定义和结果，以便在其他环境中容易应用。

3.3 在查询极限中的可识别性

一个基本结果描述了一种方法在可数无限或有限数量的互斥假设 H 中可靠地找到正确假设的条件，这些假设共同涵盖了与询问者的背景假设一致的所有可能性。H 的学习者将有限的观察序列映射到 H 中的一个假设。例如，在归纳新谜题中，自然投影是一个假设集 H 的学习者，该集合包括“所有翡翠都是绿色”，H1=“所有翡翠都是绿色(1)”，H2=“所有翡翠都是绿色(2)”，等等，对于所有关键时刻 t。如果对于每个完整的数据序列，学习者猜测的假设 H 对于与数据序列一致的任何进一步观察都是正确的，则学习者可靠地识别或简单地识别 H 中的正确假设。泛化方法和自然投影规则是其假设集的可靠学习者的示例。

定理。如果每个假设 H 是可证伪假设的有限或可数析取，那么存在一个学习者，它可靠地从 H 中识别出一个正确的假设。
证明请参见 Kelly [1996, Ch. 3.3]。

例子。为了说明问题，让我们回到鸟类学的例子，有两个备选假设：（1）除了有限多只天鹅是白色的，和（2）除了有限多只天鹅是黑色的。正如我们所见，从长远来看，可以可靠地确定这两个假设中哪一个是正确的。因此，根据表征定理，这两个假设必须是可证伪的经验性主张的析取。为了看到这一点，观察到“除了有限多只天鹅是白色的”在逻辑上等价于析取

最多有 1 只天鹅是黑色的，或者最多有 2 只天鹅是黑色的...或者最多有 n 只天鹅是黑色的...或者...，

同样地，“除了有限多只天鹅是黑色的”也是如此。析取命题中的每个命题都是可反驳的。例如，假设“最多有 3 只天鹅是黑色的”。如果这个命题是假的，那么会发现超过 3 只黑天鹅，这时命题就被彻底证伪了。下图说明了可辨识假设是如何构建成可反驳假设的析取形式的。

图 5 [图 5 的详细描述在附录中。]

表征定理意味着我们可以将可靠方法看作是采用了原始研究假设的内部加强版本，这些版本是可反驳的。正如上面的例子所示，该定理并不意味着加强的假设是互斥的（例如，“最多有 3 只天鹅是黑色的”与“最多有 2 只天鹅是黑色的”是一致的）。Baltag、Gierasimczuk 和 Smets [2015] 提出了一个最近的替代表征定理，该定理提供了一个替代的结构分析方法，将可辨识假设分解为互斥的组成部分，如下所示。

如果一个假设 H 等同于一个可验证的假设和一个可反驳的假设的合取（在给定的背景知识下），那么假设 H 是可验证可反驳的：H =（V 和 R），其中 V 是可验证的，R 是可反驳的。例如，假设“恰好有 2 只天鹅是黑色的”是可验证可反驳的，因为它等同于可验证的假设“至少有 2 只天鹅是白色的”和可反驳的假设“至多有 2 只天鹅是白色的”的合取。术语“可验证可反驳的”是由 [Genin 和 Kelly 2015] 提出的；它表示当一个可验证可反驳的假设为真时，存在某个初始条件，在该条件之后，假设是可反驳的，也就是说，如果假设为假，则数据将证明其为假。Baltag 等人将可验证可反驳的假设称为局部封闭的。他们为可靠学习建立了以下表征定理 [Baltag 等人 2015]。

定理。如果每个假设 H 等同于有限或可数个互斥的可验证可反驳的假设的析取，那么存在一个学习者可以可靠地从 H 中识别出一个正确的假设。

由于可验证可反驳的假设是互斥的，它们构成了一个有效的细化假设空间，其成员推导出原始假设中的一个。表征定理表明，在不损失学习能力的情况下，归纳方法可以将原始假设空间转化为可验证可反驳的假设空间。下图说明了转化为可验证可反驳假设的分解过程。

图 6 [图 6 的扩展描述在附录中。]

有几点可以帮助解释特征定理的重要性。

可靠方法的结构。特征定理告诉我们可靠方法的结构如何与正在调查的假设的结构相协调。例如，所提到的定理建立了可证伪性和可测试性之间的联系，但这种联系比天真的波普尔主义者所设想的要弱：被测试的假设不一定直接可证伪；相反，必须有一些加强每个假设的方法，从而产生可反驳的“子假设”的可数数量。我们可以将这些可反驳的子假设看作是主要假设可能为真的不同方式。（例如，“除了有限多只天鹅是白色”为真的一种方式是如果有最多 10 只黑天鹅；另一种方式是如果有最多 100 只黑天鹅，等等）。加强原始假设使其成为经验上可证伪的做法与拉卡托斯的方法论精神相匹配，其中一个通用的科学范式与辅助假设相结合，以定义可测试（即可证伪）的主张。
背景假设的引入。表征结果在可解和不可解问题之间划定了一条界线。背景知识降低了问题的归纳复杂性；有足够的背景知识，问题就跨越了不可解和可解之间的门槛。在许多经验研究领域中，关键的背景假设是使可靠研究成为可能的那些假设。（库恩 [1970] 在“范式”中体现了背景假设的重要性）。
语言不变性。学习理论的表征定理涉及凯利所称的各种观察序列的“时间纠缠”[凯利 2000]。最终，它们依赖于给定证据、背景假设和经验性主张之间的蕴涵关系。由于逻辑蕴涵不依赖于我们用来构建证据和假设的语言，表征定理所确定的经验问题的归纳复杂性是语言不变的。

4. 短期内的长期：可靠和稳定的信念

长期以来，将真理收敛作为探究的目标的批评之一是，虽然本身不错，但这个目标与短期内的任何疯狂行为都是一致的 [Salmon 1991]。例如，我们在归纳的新谜题中看到，一个可靠的投射规则可以猜测下一个翡翠将是蓝色的，无论找到多少绿色的翡翠，只要最终规则投射“所有的翡翠都是绿色”。对此的一个回应是，如果手段-目的分析除了长期收敛外还考虑其他认识目标，那么它可以为短期内的猜测提供强有力的指导。

为了说明这一点，让我们回到古德曼的归纳之谜。自从柏拉图以来，哲学家们一直认为稳定的真实信念比不稳定的真实信念更好，而像斯克拉尔 [1975] 这样的认识论者则提倡“认识论保守主义”的类似原则。库恩告诉我们，在范式辩论中保守主义的一个主要原因是改变科学信念的代价 [Kuhn 1970]。本着这种精神，学习理论家们研究了在最终猜测之前最小化改变理论次数的方法 [Putnam 1965，Kelly 1996，Jain 1999]。这样的方法被称为最小化思维变化。

4.1 例子：归纳的新谜题

归纳新谜题事实上是这个观点的一个很好的例证。考虑自然投影规则（猜测所有翡翠都是绿色的绿翡翠样本）。如果所有的翡翠都是绿色的，这个规则永远不会改变它的猜测。如果在某个关键时间 t，所有的翡翠都是蓝绿色的，那么自然投影规则会在时间 t 放弃它的猜测“所有的翡翠都是绿色的”——一次心智改变——然后正确地投影“所有的翡翠都是蓝绿色的”。值得注意的是，投影蓝绿色而不是绿色的规则效果不好。例如，考虑一个规则，在观察到一个绿色翡翠后，猜测所有的翡翠都是蓝绿色的（3）。如果观察到另外两个绿色翡翠，该规则的猜测就被证伪了，它必须最终改变主意，比如猜测所有的翡翠都是绿色的（假设绿色翡翠继续被发现）。但是在那个时候，可能会出现一个蓝色翡翠，迫使进行第二次心智改变。这个论证可以推广，以表明最小化心智改变的目标只允许在所有绿色翡翠样本上投影绿色谓词 [Schulte 1999]。我们在上面的 1.2 节中看到，自然投影规则最多只改变一次主意；下面的图例说明了在典型情况下，一个不自然的投影规则可能需要改变两次或更多次主意。

图 7 [图 7 的详细描述在附录中。]

4.2 更多例子

同样的推理也适用于关于所有乌鸦是否都是黑色的问题。在观察到仅有黑色乌鸦样本后，大胆的概括者猜测所有乌鸦都是黑色的，最多只需要一次心智改变：如果确实所有乌鸦都是黑色的，那么这个概括者根本不会改变主意。如果存在一只非黑色的乌鸦，那么反驳会引起一次心智改变，但之后问题就解决了。

与之相反的方法是在观察到全部黑色乌鸦样本后断言存在一只非黑色的乌鸦。如果只观察到黑色乌鸦，相反的方法必须最终改变主意并断言“所有乌鸦都是黑色”，否则它无法得出正确的概括。但是在那一点上，可能会出现一只非黑色的乌鸦，迫使进行第二次心智改变。因此，稳定信念的目标对于一个方法在短期内可能假设的内容有着强大的限制：在仅观察到黑色乌鸦的情况下，选项是“所有乌鸦都是黑色”或“尚无意见”，而不是“存在一只非黑色的乌鸦”。

在守恒定律问题中，第 2.1 节中描述的限制性方法是唯一能够最小化心智改变的方法。回想一下，限制性方法采用了一组尽可能排除未观察到的反应的守恒定律。可以证明，如果有 n 个已知的基本粒子其反应被观察到，这个方法最多需要 n 次心智改变。（标准模型中的基本粒子数量大约为 n=200）。

对于学习因果图，以下是在第 2.2 节中描述的方法的变体，它最小化了思维变化的次数。

假设我们观察到了一组感兴趣变量之间的相关性或关联。
如果存在一个唯一的因果图，它用最少的直接因果链接解释了观察到的相关性，请选择该图。
如果存在多个因果图可以用最少数量的直接因果链接解释观察到的相关性，则输出“尚无意见”（或者推测最小边缘图的析取）。

这个例子说明有时候最小化思维变化需要保留信念。直观地说，当数据有两个或更多同样简单的解释时，询问者必须等待进一步的观察来决定这些可能性之间的选择。如果立即得出一个简单的结论，可能会导致不必要的思维变化，因为另一个同样简单的解释可能是正确的。在这种情况下，稳定信念的目标与迅速确定真实信念之间存在权衡 [Sculpte 1999]。我们在下一节关于简单性的部分讨论简单性和稳定信念之间的联系。

4.3 退行性思维变化

Genin 和 Kelly [2015] 通过区分不同类型的心智变化来完善心智变化方法。

放弃一个真实的假设，而选择一个错误的假设。这是一种不可取的回归性心智变化。
放弃一个错误的假设，而选择一个真实的假设。这是一种可取的进步性心智变化。
放弃一个错误的假设，转而支持另一个错误的假设。

下表说明了归纳推理的新谜题和乌鸦例子中的这些区别。Genin 和 Kelly 研究了归纳方法应该最小化回归性思维变化的原则，即新证据导致该方法放弃一个真实的假设，转而支持一个错误的假设的次数。回归性思维变化是认识失败的标志的观念与认识论中的长期传统相吻合。知识的可推翻性理论（请参见下面的其他互联网资源部分的链接）认为，为了使一个代理人的真实信念被视为知识，它必须是不可推翻的，即接受进一步的命题不应该导致代理人放弃她的信念。用思维变化的语言来表达，这意味着只有当调查者的真实当前猜想没有进一步的证据会导致她改变主意并采纳另一个错误的猜想时，她的猜想才能被视为知识。柏拉图的《美诺篇》生动地传达了这一点。

现在这是真实观念的本质的一个例证：当它们与我们同在时，它们是美丽和富饶的，但它们逃离了人类的灵魂，不久就不再存在，因此它们的价值不大...但是当它们被束缚时，首先，它们具有知识的本质；其次，它们是持久的。

阐述回归和进步的心智变化

尽管最小化回归性心智变化比一般避免心智变化更重要，但它会对归纳学习施加较弱的限制。与此同时，任何从中得出的限制都具有更多的规范力。上述表格说明了归纳新谜题和乌鸦问题中这两个原则之间的差异。在归纳新谜题中，如果只观察到绿色的翡翠，投射规则可以继续投射任意数量的可怕谓词而不产生回归性心智变化：它只是放弃一个错误的可怕谓词，换成另一个错误的可怕谓词。因此，即使是不自然的投射规则也不会产生回归性心智变化，前提是它们一旦采用了“全绿假设”就不会放弃它。

形式化学习理论中，最小化回归性思维变化的后果对于所有乌鸦是否都是黑色的问题是不同的。再次考虑相反的方法，即在观察到一组黑色乌鸦后断言存在一只非黑色乌鸦。如上表所示，并且如上所讨论的，相反的方法在看到更多黑色乌鸦后必须最终改变其假设，推测所有乌鸦都是黑色的，然后，在观察到一只白色乌鸦后，返回其真实的初始假设，即存在一只非黑色乌鸦。因此，在最坏的情况下，相反的方法至少经历一次回归性思维变化。另一方面，一般化方法在观察到一组黑色乌鸦后断言所有乌鸦都是黑色的，只有在观察到一只非黑色乌鸦时才改变其推测——从错误的假设到正确的假设的一次进步性思维变化。因此，避免回归性思维变化的原则将一般化方法与相反方法区分开来。

如示例所示，回归性思维变化与推测循环相关。这是因为可靠的方法必须在采用错误的假设后最终返回一个正确的假设，因此回归性思维变化导致至少一个循环的正确推测-错误推测-正确推测。避免回归性思维变化的方法因此在无循环学习 [Genin 和 Kelly 2015] 或最小化 U 型转弯 [Carlucci 等人 2005] 的标题下进行研究。Genin 和 Kelly [2015, 2019] 提供了一个概括性结果，阐明了避免回归性思维变化和推测循环的一般方法论重要性（在第 5.4 节中描述）。他们的结果属于一系列定理的家族，这些定理在避免思维变化和奥卡姆剃刀之间建立了一个引人注目的联系，我们将在下一节中讨论。

5. 简洁性、稳定信念和奥卡姆剃刀

对归纳推理和科学方法的一个强烈直觉是，我们应该更喜欢简单的假设而不是复杂的假设；参见有关简单性的条目。统计学家、计算机科学家和其他关注从观察中学习的研究人员广泛使用了对简单性的偏好来解决实际的归纳问题 [Domingos 1999]。从基础的角度来看，简单性至少有两个问题。

正当性问题：为什么采用简单的假设？一个显而易见的答案是，世界是简单的，因此复杂的理论是错误的。然而，关于世界是简单的这个先验性主张是非常有争议的—参见有关简单性的条目。从学习理论的角度来看，摒弃复杂的假设会损害归纳方法的可靠性。在凯利的隐喻中，固定的偏见就像一只停止的手表：我们可能碰巧在手表指向正确时间时使用它，但手表不是一个可靠的测时工具 [Kelly 2007a, 2010]。
描述问题：认识论家担心简单性不是一个假设的客观特征，而是“取决于表达方式”，如诺齐克所说。古德曼的谜题说明了这一点。如果概括用蓝绿色的术语来表述，“所有的翡翠都是绿色的”看起来比“所有的翡翠先是绿色然后是蓝色”更简单。但在一个蓝绿色的语言中，“所有的翡翠都是蓝绿色的”看起来比“所有的翡翠先是蓝绿色然后是蓝色”更简单。

形式化学习理论家最近和持续努力将目的手段认识论应用于发展一种关于简洁性和归纳之间联系的理论，以解决这些问题 [凯利 2010 年，哈曼和库尔卡尼 2007 年，罗和舒尔特 2006 年，斯蒂尔 2009 年]。事实证明，一个有益的视角是研究假设空间的结构与相应归纳问题的心智变化复杂性之间的关系。基本思想是，虽然简洁性与真理没有先验联系，但选择简单的假设可以帮助调查者更有效地找到真理，即避免心智变化。凯利的道路隐喻说明了这个思想。考虑到达目的地的两条路线，一条是通过一条笔直的高速公路，另一条是通过小路。两条路线最终都会到达同一个点，但小路会有更多的曲折和转弯 [凯利 2007a，2010 年]。

这个思想的形式化采用了奥卡姆定理的形式：一个定理（在适当的限制条件下）表明，如果一个归纳方法选择了与数据一致的最简单的假设，那么该方法将以尽可能高效的方式找到给定问题的真理。奥卡姆定理为奥卡姆的归纳剃刀提供了一种达到认识论目标的手段。

奥卡姆定理的真实性取决于奥卡姆方法的描述，即对一组假设的简洁性的确切定义。有一系列数学结果证明了使用语言不变的简洁性度量的奥卡姆定理，我们将在下面解释。

5.1 定义简单性

假设从可能的假设背景集合 H 中选择一个假设 H，如果存在一个证据序列，使得 H 是与该证据序列一致的唯一假设，则称 H 是可验证的。例如，在上述黑乌鸦问题中，假设“存在一个非黑乌鸦”是可验证的，因为它是由观察到的非黑乌鸦所蕴含的。假设“所有乌鸦都是黑色的”是不可验证的，因为它不是由任何有限的证据序列所蕴含的。下面的过程为来自假设集合 H 的每个假设 H 分配一个简单性等级 [Apsitis 1994, Luo and Schulte 2006]。

将所有可验证的假设分配简单性等级 0。
从假设空间中删除可验证的假设，形成一个新的假设空间 H1。
对于在 H1 给定的可验证的假设，分配简单性等级 1。
从假设空间中删除具有简单性等级 1 的新可验证假设，形成一个新的假设空间 H2。
继续删除假设，直到在当前假设空间中没有新的可验证的假设。
每个假设 H 的简单性等级是通过该过程首次将其删除的阶段。换句话说，它是使 H 可验证的第一个受限假设空间的索引。

具有较高简单性等级的假设被认为比较低等级的假设更简单。简单性等级是根据逻辑蕴涵关系定义的，因此是语言无关的。所定义的简单性等级可以被看作是以下意义上的可伪造程度。考虑一个简单性等级为 1 的假设。这样的假设是可伪造的，因为验证等级为 0 的替代假设的证据序列会使其伪造。此外，简单性等级为 1 的假设在观察到与其一致的任何证据序列时仍然是持续可伪造的。简单性等级为 n+1 的假设可以被等级为 n 的假设持续地伪造。让我们通过我们的运行示例来说明这个定义。

5.2 例子

在归纳之谜中，可验证的假设是具有临界时间 t 的绿蓝假设：任何一系列 t 个绿色翡翠后面跟着蓝色翡翠都会导致相应的 grue(t)概括。因此，grue 假设的简单性等级为 0。在消除了 grue 假设之后，唯一剩下的假设是“所有的翡翠都是绿色”。鉴于它是在受限假设空间中唯一的可能性，“所有的翡翠都是绿色”被任何一系列绿色翡翠所包含。因此，“所有的翡翠都是绿色”具有简单性等级 1。在移除了所有绿色假设之后，没有剩下任何假设。
在乌鸦颜色问题中，可验证的假设是“会观察到一只非黑色的乌鸦”，它的简单性等级为 0。在移除了观察到一只非黑色乌鸦的假设之后，唯一剩下的可能性是只会观察到黑色乌鸦，因此这个假设在受限假设空间中是可验证的，并且具有简单性等级 1。
因果图的简易等级由图中不包含的直接链接数量给出。因此，因果模型所假设的直接链接越少，其简易等级越高。
保守定律集合的简易等级由独立定律的数量给出。（独立性是指线性代数中的独立性。）因此，理论引入的非冗余定律越多，其简易等级越高。每个定律都排除了一些反应，因此在给定观察到的反应的情况下，最大化独立定律的数量等效于尽可能排除尽可能多的未观察到的反应。

5.3 稳定信念和简易性：奥卡姆定理

以下定理显示了归纳问题的心智变化复杂性与定义的简单性排名之间的联系。

定理。设 H 是一组经验性假设。那么，如果上述定义的消除过程在 n 个阶段后以一个空的假设集终止，那么存在一种方法，在极限中可靠地从 H 中识别出一个正确的假设，最多需要 n 次心智变化。

因此，对于一个归纳问题来说，要在最多 n 次心智变化中可解决，任何可能假设的最大简单性排名是 n。在归纳之谜中，最大简单性排名为 1，因此这个问题最多可以在 1 次心智变化中解决。下一个结果提供了一条奥卡姆定理，连接了简单性和心智变化性能。

奥卡姆定理。设 H 是具有最佳心智变化界限 n 的经验假设集合。那么，如果归纳方法满足以下条件，则它是心智变化最佳的。
每当该方法采用 H 中的一个假设时，该假设是与证据一致的唯一最简单的假设。
如果该方法在查询时间 t+1 改变主意，则时间 t 的唯一最简单假设在时间 t+1 被证伪。

这个定理表明，一个思维变化最优的方法可能会像怀疑论者一样保留一个猜想，但如果它确实采用了一个明确的假设，那么这个假设必须是最简单的，即具有最大简单性等级。因此，在第 4 节讨论的思维变化最优方法都是奥卡姆方法，它们采用了与数据一致的最简单的假设。奥卡姆定理显示了一个令人惊讶的逆转，即长期可靠性对短期猜想施加的约束太少的长期反对意见：如果我们在追求长期收敛于真理的同时，还追求稳定的信念，那么实际上存在一种唯一的归纳方法，可以在给定的经验问题中实现这个目标。因此，方法论分析从不提供短期处方转变为提供完整的处方。

5.4 退行思维变化和简单性：另一个奥卡姆定理

前一小节为每个正在调查的假设定义了一个完整的简单性排序。这意味着任何假设都可以与另一个假设进行比较，看哪个更简单或者是否一样简单。一个要求较低的概念是偏序，它允许一些假设可能根本无法比较，就像苹果和橙子一样。Genin 和 Kelly [2015] 表明，以下偏序导致了一个避免退行思维变化的奥卡姆原则（见第 4.3 节）。

如果观察序列与假设 H1 一致并证伪了假设 H2（在给定的背景知识下），则观察序列将 H1 与 H2 分开。
如果没有观察序列将 H1 与 H2 分开，则假设 H1 与 H2 是不可分的，记作 H1<H2。等价地，当任何与 H1 一致的证据也与 H2 一致时，H1<H2。

分离术语是由 Smets 等人提出的，他们将其与点集拓扑中的分离原则联系起来。根据第 3.2 节中对点集拓扑的认识论解释，我们有 H1<H2 当且仅当 H1 的每个完整数据序列都是 H2 的数据序列的边界点。Genin 和 Kelly 用一个认识论共鸣的说法表达，称假设 H1“面临归纳问题”相对于 H2，每当 H1<H2 时。这是因为每当 H1 是正确的时候，可靠的学习者将不得不进行“归纳跃迁”并猜测 H1，尽管任何有限数量的证据也与 H2 一致。

例子

在乌鸦问题中，H1=“所有乌鸦都是黑色” <H2=“有些乌鸦不是黑色”。但是，“有些乌鸦不是黑色” <“所有乌鸦都是黑色”并不成立，因为观察到一只白色乌鸦将 H2 与 H1 分开。
在因果图学习中，如果图 G1 包含了备选图 G2 中的一部分边（直接因果链接），那么 G1<G2。这是因为 G1 能够解释的任何相关性也可以被更大的图 G2 解释。
在曲线拟合中，L<Q，其中 L 是线性函数的集合，Q 是二次函数的集合。这是因为任何可以由线性函数拟合的点集也可以由二次函数拟合。

这些例子表明，偏序关系对应于我们对经验假设的直观简单性判断；Genin 和 Kelly [2019] 对这一观点进行了广泛的辩护。可以证明，偏序关系与前一小节中定义的简单性等级一致，即如果 H1<H2 但不是 H2<H1，则 H1 的简单性等级小于 H2 的等级。这些观察结果激发了奥卡姆原理：对于可分离性，归纳方法满足奥卡姆原理，如果它总是假设与证据一致的最简单的假设 H。在我们的符号表示中，如果奥卡姆方法在给定有限观察序列的情况下采用假设 H，则不存在其他更简单的假设 H'，使得 H'<H。也就是说，如果 H'为真，则每个备选假设 H'最终都会被证据与 H 分离。在乌鸦的例子中，概括方法满足奥卡姆原理，但相反的方法不满足，因为它采用了 H2=“一些乌鸦不是黑色”。以下定理表明奥卡姆原理与回归性思维变化之间的联系是普遍的。

定理。如果归纳方法避免了猜测循环（因此避免了回归性思维变化），它就满足了可分离性的奥卡姆原理。

有关证明，请参阅 Genin 和 Kelly [2015; 定理 10]。Genin 和 Kelly 还提供了避免猜想循环的充分条件。

尽管本节中的结果建立了简洁性和心智变化最优性之间的有益联系，但该方法的局限性在于它要求某些假设必须被某些证据序列明确地蕴含或证伪。对于统计模型来说，通常情况下并非如此，因为假设的概率可能变得任意小，但通常不会为 0。例如，考虑一个抛硬币的问题和假设“正面的概率为 90%”。如果我们观察到一百万个反面，那么这个假设的概率确实非常小，但它并不为 0，因为任何数量的反面都与高概率的正面是逻辑一致的。下一节将讨论如何将可靠主义方法应用于统计假设。

6. 统计假设的可靠学习

在实际的数据驱动决策中，统计假设是最常见的，例如在科学和工程领域。因此，对于归纳推理的哲学框架来说，包括统计假设是非常重要的。统计假设与我们迄今考虑过的假设集之间存在两个关键差异 [Sober 2015]。

观察和假设之间的关系是概率性的，而不是演绎性的：统计假设为观察序列分配一个概率，通常在 0 到 1 之间。演绎性假设要么与观察序列一致，要么被证伪。
统计假设的分析通常假设观察值构成一个随机样本：连续的观察值彼此独立，并且遵循相同的分布。虽然可能分析后续观察值依赖于当前观察值的统计方法，但归纳方法的数学复杂性要比独立数据大得多。

由于这些特性，非统计方法的学习理论比传统哲学中的统计学更直接。例如，关于合理的真实信念的认识论讨论涉及到一种演绎概念的信念，即询问者接受一个命题，而不是为数据分配概率。科学理论通常从过去的观察（初始条件）中对未来数据进行确定性预测，因此独立性要求使得将方法论框架应用于理解科学探究变得更加困难（参见我们的案例研究）。

规范的目的-手段认识论既可以应用于统计假设，也可以应用于演绎假设。特别是，我们将讨论如何将可靠收敛于真理和最小化回归性思维变化的思想适应于统计设置。关键思想是转变分析单位：以前我们考虑了特定数据序列的归纳方法的行为，而在统计分析中，我们考虑它在一组相同长度的数据序列上的总体行为。特别地，我们考虑一个方法对于给定观察次数 n 猜测假设 H 的概率。

统计假设的初步说明

我们将用一个经典的简单例子来阐述主要思想，观察硬币的翻转，并说明如何将其推广到更复杂的假设。更多细节请参见 [Genin 和 Kelly 2017，Genin 2018]。假设调查员对硬币的未知偏倚 p 有一个问题，其中 p 表示单次翻转出现“正面”的机会。不同的可能假设对应于偏倚 p 的不同范围，即 [0,1] 的偏倚范围的划分。假设调查员提出一个简单的点假设：硬币是否公平？那么我们有

H1=“p=0.5”
H2=“不是 p=0.5”。也就是说，要么 p <0.5，要么 p> 0.5。

扩展我们之前的术语，我们将说，如果真实的偏差值 p 位于 H 指定的集合内，则假设 H 的真实偏差值 p 是正确的。在我们的例子中，如果且仅当 p=0.5 时，偏差值 p 对于 H1 是正确的；否则，偏差值 p 对于 H2 是正确的。给定真实的偏差值 p，并假设独立性，我们可以计算任何有限观测序列的概率。这个概率被称为样本分布。例如，对于一个偏差值 p=0.5 的公平硬币，观测到 3 个正面的概率是 0.5×0.5×0.5=0.125。如果正面的概率是 0.7，观测到 3 个正面的概率是 0.7×0.7×0.7=0.343。请注意，独立性假设使我们能够将观测序列的概率计算为单个观测概率的乘积。没有独立性假设，我们无法从单个观测的概率推断出多个观测的概率，样本分布也无法定义。

如往常一样，在这个条目中，归纳方法在观察有限序列后猜测一个假设。猜测统计假设的方法被称为统计检验（请参见下面的其他互联网资源部分的链接）。统计文献提供了一系列计算效率高的统计检验，用于不同类型的统计假设。在下面的讨论中，我们考虑这些方法的一般学习性能，即可靠地收敛到真实假设并避免思维变化。考虑一个固定的观察长度 n，称为样本大小。对于样本大小 n，存在一组长度为 n 的样本，使得该方法在给定样本的情况下猜测假设 H。例如，对于 n=3，该方法在观察到 3 个正面后可能猜测 H2=“硬币不公平”。该方法在给定长度为 n 的样本的情况下猜测假设 H 的样本概率之和，称为方法输出假设 H 的聚合概率。在补充中，我们给出了聚合概率的示例计算。因为这个聚合概率是统计假设方法论的关键数量，我们引入以下符号表示它。

Pn,p(H)=给定 n 次观察后，归纳方法猜测假设 H 的概率，假设单次观察的真实概率为 p

在非统计学习中，我们需要一种可靠的方法，在足够多的观察之后最终确定真实的假设。这个标准的统计版本是，在足够多的观察之后，猜测真实假设的机会应该接近 100%。更具体地说，假设一个方法在机会中识别出真实的统计假设，如果对于每个偏差值 p，以及每个阈值 0 <t<1，存在一个样本大小 n，使得对于所有更大的样本大小，该方法猜测的假设 H 对于 p 至少以概率 t 为真。用符号表示，我们有对于所有样本大小 n′> n，Pn′,p(H)>t，其中 H 是对于 p 为真的假设。下图说明了随着样本大小的增加，猜测真实假设的机会增加，而猜测错误假设的机会随着样本大小的增加而减少。这个定义可以通过用参数列表替换真实偏差值 p 来推广到更复杂的统计假设。

图 8 [图 8 的详细描述在附录中。]

在机会中，限制识别的概念类似于 Reichenbach 的实用辩护中概率估计的极限收敛概念。将其转化为我们的例子，Reichenbach 考虑了输出真实偏差值 p 估计的归纳规则，并要求这样的规则在某种意义上收敛于真实值，即对于每个偏差值 p 和每个阈值 0<t<1，存在一个样本大小 n，使得对于所有更大的样本大小，规则以概率 1 输出一个估计值，该估计值与真实值 p 之间的差异最多为 t。在统计学中，如果随着样本大小的增加，方法猜测正确答案的机会收敛于 100%，则称该方法是一致的（请参见下面的其他互联网资源部分的链接）。这个术语不幸地暗示了与形式证明系统的一致性有关的哲学读者的联系。实际上，统计学中的一致性概念与演绎逻辑无关，而是对本条目的主要主题——在查询的极限中的识别概念的概率类比。

Genin 和 Kelly 提供了一个表征定理，为一组统计假设提供了在机会中可识别的必要和充分条件，类似于我们在第 3.3 节中讨论的结构条件 [2017; 定理 4.3]。Genin [2018] 讨论了最小化思维变化要求的统计类比。回想一下，在第 4.3 节中，当调查者放弃一个真实的假设而选择一个错误的假设时，会发生回归性思维变化。概率类比是机会逆转，当样本量增加时，猜测真实假设的机会减少。例如，考虑一个关于疫苗是否对传染病有效的问题。假设疫苗制造商进行了一项试验，有 1000 名患者，并设计了一种统计方法，当疫苗确实有效时，正确指示的机会为 90%。现在另一项试验使用相同的统计方法进行，有 1500 名患者。如果该方法正确指示疫苗有效的机会降至 80%，则发生了机会逆转。正如这个例子所示，机会逆转对应于无法复制真实结果。上图中显示了一个机会逆转，其中对于 2 个样本而言，猜测真实假设的机会较小，而对于 3 个样本而言，机会较大。尽管机会逆转显然是不可取的，但很难避免，事实上常用的统计方法容易发生这种逆转 [Genin 2018]。一个更可行的目标是通过阈值 t 来限制逆转，即如果随着样本量增加，猜测真实性的机会减少，那么减少的幅度最多为 t。（符号上，对于所有样本量 n 和真实偏差值 p，Pn，p（H）-Pn+1，p（H）<t，其中 H 是对于 p 正确的假设）。) Genin [2018] 表明在许多情况下，有界的机会逆转是可行的，并提供了一种奥卡姆定理，阐明了有界机会逆转对统计假设学习的约束。

7. 其他方法：范畴性与假设性命题

康德区分了无论个人目标和环境如何，都应该遵循的范畴性命题和指导我们将手段用于已选择目标的假设性命题。学习理论可以被看作是对经验探究的假设性命题的研究。许多认识论学家提出了各种范畴性命题用于归纳探究，例如“归纳逻辑”或“认识合理性”的规范。原则上，对于经验探究，假设性命题和范畴性命题之间有三种可能的关系。

范畴命令将引导一个探究者达到他的认知目标。在这种情况下，手段-目的分析证明了范畴命令的正确性。例如，当面对一个简单的普遍概括，比如“所有乌鸦都是黑色的”，我们可以看到，遵循波普尔的方法，采用可证伪的概括并坚持到出现反例的方法是一种可靠的方法。
范畴命令可能会阻止一个探究者实现他的目标。在这种情况下，范畴命令限制了探究的范围。例如，在存在例外的两种替代概括的情况下，坚持维持一个普遍概括直到被证伪的原则会导致一种不可靠的方法（参见 [凯利 1996 年，第 9.4 章]）。
有些方法既符合范畴命令又符合探究的目标，而其他方法则不符合。那么我们可以兼顾两者，选择那些既能达到探究目标又满足范畴命令的方法。（详见本节的进一步讨论。）

对于一个提出的研究规范，我们可以应用手段-目标分析来询问这个规范是否有助于或阻碍了研究的目标。这正是普特南对卡纳普的证实函数的批评的精神 [Putnam 1963]：他的文章的要点是卡纳普的方法在检测一般模式方面不如其他方法可靠。最近，学习理论家们研究了贝叶斯条件概率的能力（详见贝叶斯认识论条目）。约翰·厄尔曼猜测，如果对于一个给定的问题存在任何可靠的方法，那么一定存在一种通过贝叶斯更新进行的可靠方法 [Earman 1992，第 9 章，第 6 节]。科里·朱尔 [1997] 部分证实了厄尔曼的猜测：他证明了当只有两个潜在证据项目时（例如，“翡翠是绿色的”与“翡翠是蓝色的”），该猜测成立。一般情况仍然未解决。

认识保守主义是一种方法论规范，至少自奎恩提出“我们信念的最小毁损”概念 [1951] 以来，在哲学中占据重要地位。认识保守主义的一个版本，正如我们上面所看到的，认为研究应该寻求稳定的信念。更接近奎恩观点的另一种表述是信念在新证据的光照下的变化应该是最小的一种普遍原则。哲学逻辑的最近研究提出了一些关于最小信念变化的标准，被称为 AGM 公理 [Gärdenfors 1988]。学习理论家们已经证明，每当有一种可靠的方法来研究一个经验问题时，就会有一种通过最小变化进行的方法（由 AGM 公理定义）。关于具有最小信念变化的可靠研究的性质已在 [Martin and Osherson 1998，Kelly 1999，Baltag et al. 2011，Baltag et al. 2015] 中进行了研究。

形式化学习理论的大部分关注点在于具有有限理性的探究者，即具有认知限制，如有限记忆或有限计算能力的智能体。许多不干扰逻辑全知智能体的经验成功的范畴规范仍然限制了认知有限智能体的范围。例如，考虑一致性规范：一旦证据与假设在逻辑上不一致，就相信该假设是错误的。一致性原则是贝叶斯证实理论和 AGM 信念修正的一部分。Kelly 和 Schulte [1995] 表明，一致性甚至阻止具有无限不可计算认知能力的智能体可靠地评估某些假设。这告诉我们，如果一个理论足够复杂，那些不具备逻辑全知的智能体可能无法立即确定某个证据是否与该理论一致，并且需要收集更多数据来检测不一致性。但是一致性原则，更不用说贝叶斯更新和 AGM 信念修正，不承认“等待并观察更多”的科学策略的有用性。

在对这些以及其他哲学问题进行更深入的思考时，可以在以下来源中找到有关目的论认识论的更多信息，例如 Huber [2018]，[Glymour 1991]，[Kelly 1996，第 2、3 章]，[Glymour and Kelly 1992]，[Kelly et al. 1997]，[Glymour 1994]，[Bub 1994]。在科学哲学中特别感兴趣的可能是学习理论模型，这些模型能够适应历史主义和相对主义的研究观念，主要是通过扩展归纳方法的概念，使方法能够主动选择研究范式；有关此主题的更多详细信息，请参阅 [Kelly 2000，Kelly 1996，第 13 章]。关于学习理论数学的书籍介绍有 [Kelly 1996，Martin and Osherson 1998，Jain et al. 1999]。《归纳、算法学习理论与哲学》是一本关于学习理论的最新文集 [Friend et al. 2007]。其中包括入门论文（Harizanov，Schulte），数学进展（Martin，Sharma，Stephan，Kalantari），对学习理论的优势和影响的哲学思考（Glymour，Larvor，Friend），将该理论应用于哲学问题的讨论（Kelly），以及对哲学史中学习理论思维的讨论（Goethe）。

Supplementary Document: Basic Formal Definitions

Bibliography

Abramsky, S., 1987. Domain Theory and the Logic of Observable Properties, Ph.D. Dissertation, University of London.
Apsitis, K., 1994. “Derived sets and inductive inference”, in Proceedings of the 5th International Work on Algorithmic Learning Theory, S. Arikawa, K.P. Jantke (eds.), Berlin, Heidelberg: Springer, pp. 26–39.
Baltag, A. and Smets, S., 2011. “Keep changing your beliefs, aiming for the truth”, Erkenntnis, 75(2): 255–270.
Baltag, A., Gierasimczuk, N., Smets, S., 2015. “On the Solvability of Inductive Problems: A Study in Epistemic Topology”, Proceedings of the 15th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2015), , pp. 65–74. Electronic Proceedings in Theoretical Computer Science available online.
Bub, J., 1994. “Testing Models of Cognition Through the Analysis of Brain-Damaged Performance”, British Journal for the Philosophy of Science, 45: 837–55.
Carlucci, L., Case, J., Jain, S. and Stephan, F., 2005. “Non U-shaped vacillatory and team learning”, in International Conference on Algorithmic Learning Theory, Berlin, Heidelberg: Springer, pp. 241–255.
Chart, D., 2000. “Schulte and Goodman’s Riddle”, British Journal for the Philosophy of Science, 51: 837–55.
de Brecht, M. and Yamamoto, A., 2008. “Topological properties of concept spaces”, in International Conference on Algorithmic Learning Theory, Berlin, Heidelberg: Springer, pp. 374–388.
Domingos, P., 1999. “The role of Occam’s razor in knowledge discovery”, Data mining and Knowledge discovery, 3(4): 409–425.
Earman, J., 1992. Bayes or Bust?, Cambridge, Mass.: MIT Press.
Feynman, R., 1965. The Character of Physical Law, Cambridge, Mass.: MIT Press; 19th edition, 1990.
Friend, M. and N. Goethe and V. Harazinov (eds.), 2007. Induction, Algorithmic Learning Theory, and Philosophy, Dordrecht: Springer, pp. 111–144.
Ford, K., 1963. The World of Elementary Particles, New York: Blaisdell Publishing.
Gärdenfors, P., 1988. Knowledge In Flux: modeling the dynamics of epistemic states, Cambridge, Mass.: MIT Press.
Genin, K., 2018. “The Topology of Statistical Inquiry”, Ph.D. Dissertation, Department of Philosophy, Carnegie Mellon University, Genin 2018 available online.
Genin, K. and Kelly, K., 2015. “Theory Choice, Theory Change, and Inductive Truth-Conduciveness”, Proceedings of the 15th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2015). Publisher: Electronic Proceedings in Theoretical Computer Science. Extended Abstract, Genin & Kelly 2015 available online.
–––, 2017. “The Topology of Statistical Verifiability”, Proceedings of the 17th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2017). Electronic Proceedings in Theoretical Computer Science, preprint available online .
–––, 2019. “Theory Choice, Theory Change, and Inductive Truth-Conduciveness”, Studia Logica, 107: 949–989.
Glymour, C., 1991. “The Hierarchies of Knowledge and the Mathematics of Discovery”, Minds and Machines, 1: 75–95.
–––, 1994. “On the Methods of Cognitive Neuropsychology”, British Journal for the Philosophy of Science, 45: 815–35.
Glymour, C. and Kelly, K., 1992. “Thoroughly Modern Meno”, in Inference, Explanation and Other Frustrations, John Earman (ed.), Berkeley: University of California Press.
Gold, E., 1967. “Language Identification in the Limit”, Information and Control, 10: 447–474.
Goodman, N., 1983. Fact, Fiction and Forecast, Cambridge, MA: Harvard University Press.
Harrell, M., 2000. Chaos and Reliable Knowledge, Ph.D. Dissertation, University of California at San Diego.
Harman, G. and Kulkarni, S., 2007. Reliable Reasoning: Induction and Statistical Learning Theory, Cambridge, MA: The MIT Press.
Huber, F., 2018. A Logical Introduction to Probability and Induction, Oxford: Oxford University Press.
Jain, S., et al., 1999. Systems That Learn, 2nd edition, Cambridge, MA: MIT Press.
James, W., 1982. “The Will To Believe”, in Pragmatism, H.S. Thayer (ed.), Indianapolis: Hackett.
Juhl, C., 1997. “Objectively Reliable Subjective Probabilities”, Synthese, 109: 293–309.
Kelly, K., 1996. The Logic of Reliable Inquiry, Oxford: Oxford University Press.
–––, 1999. “ Iterated Belief Revision, Reliability, and Inductive Amnesia”, Erkenntnis, 50: 11–58.
–––, 2000. “The Logic of Success”, British Journal for the Philosophy of Science, 51(4): 639–660.
–––, 2007a. “How Simplicity Helps You Find the Truth Without Pointing at it”, in Induction, Algorithmic Learning Theory, and Philosophy, M. Friend, N. Goethe and V. Harazinov (eds.), Dordrecht: Springer, pp. 111–144.
–––, 2008. ‘Ockham’s Razor, Truth, and Information’, in Handbook of the Philosophy of Information, J. van Behthem and P. Adriaans (eds.), Dordrecht: Elsevier.
–––, 2010. “Simplicity, Truth, and Probability”, in Handbook for the Philosophy of Statistics, Prasanta S. Bandyopadhyay and Malcolm Forster (eds.), Dordrecht: Elsevier.
Kelly, K., and Schulte, O., 1995. “The Computable Testability of Theories Making Uncomputable Predictions”, Erkenntnis, 43: 29–66.
Kelly, K., Schulte, O. and Juhl, C., 1997. “Learning Theory and the Philosophy of Science”, Philosophy of Science, 64: 245–67.
Kuhn, T., 1970. The Structure of Scientific Revolutions. Chicago: University of Chicago Press.
Luo, W. and Schulte O., 2006. “Mind Change Efficient Learning”, in Logic and Computation, 204: 989–1011.
Martin, E. and Osherson, D., 1998. Elements of Scientific Inquiry, Cambridge, MA: MIT Press.
Ne’eman, Y. and Kirsh, Y., 1983. The Particle Hunters, Cambridge: Cambridge University Press.
Omnes, R., 1971. Introduction to Particle Physics, London, New York: Wiley Interscience.
Popper, Karl, 1962. Conjectures and refutations. The growth of scientific knowledge, New York: Basic Books.
Putnam, H., 1963. “Degree of Confirmation and Inductive Logic”, in The Philosophy of Rudolf Carnap, P.A. Schilpp (ed.), La Salle, Ill: Open Court.
Putnam, H., 1965. “Trial and Error Predicates and the Solution to a Problem of Mostowski”, Journal of Symbolic Logic, 30(1): 49–57.
Quine, W., 1951. “Two Dogmas of Empiricism”, Philosophical Review, 60: 20–43.
Salmon, W., 1991. “Hans Reichenbach’s Vindication of Induction”, Erkenntnis, 35: 99–122.
Schulte, O., 1999. “Means-Ends Epistemology”, The British Journal for the Philosophy of Science, 50: 1–31.
–––, 2008. “The Co-Discovery of Conservation Laws and Particle Families”, Studies in History and Philosophy of Modern Physics, 39(2): 288–314.
–––, 2009. “Simultaneous Discovery of Conservation Laws and Hidden Particles With Smith Matrix Decomposition”, in Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence (IJCAI-09), Palo Alto: AAAI Press pp. 1481-1487.
Schulte, O., Luo, W., and Greiner, R., 2007. “Mind Change Optimal Learning of Bayes Net Structure”, in Proceedings of the 20th Annual Conference on Learning Theory (COLT’07, San Diego, CA, June 12–15), N. Bshouti and C. Gentile (eds.), Berlin, Heidelberg: Springer, pp. 187–202.
Schulte, O., and Cory Juhl, 1996. “Topology as Epistemology”, The Monist, 79(1): 141–147.
Sklar, L., 1975. “Methodological Conservatism”, Philosophical Review, 84: 374–400.
Sober, E., 2015. Ockham’s Razors, Cambridge: Cambridge University Press.
Spirtes, P., Glymour, C., Scheines, R., 2000. Causation, prediction, and search, Cambridge, MA: MIT Press.
Steel, D., 2009. “Testability and Ockham’s Razor: How Formal and Statistical Learning Theory Converge in the New Riddle of Induction,” Journal of Philosophical Logic, 38: 471–489.
–––, 2010. “What if the principle of induction is normative? Formal learning theory and Hume’s problem”, International Studies in the Philosophy of Science, 24(2): 171–185.
Valiant, L. G., 1984. “A theory of the learnable”, Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing (STOC 84), New York: ACM Press, pp. 436–445.
Vickers, S., 1996. Topology Via Logic, Cambridge: Cambridge University Press.