新论文:《逻辑归纳》

MIRI发表了一篇论文，介绍了一种新的演绎有限推理模型:逻辑归纳“斯科特·格拉拉贝兰，Tsvi Benson-Tilsen，Andrew Critch，Surfle和Jessica Taylor撰写。读者可能希望从中开始简版．

考虑一个推理员观察演绎过程（例如数学家和计算机程序员社区）的环境，并等待各种逻辑索赔的证明（例如美国广播公司猜想或“这台计算机程序有一个错误”），同时猜测哪些声明将结果是真的。粗略地说，我们的论文提出了一种可计算（尽管效率低下）算法，其拆除扣除，以在可以生产上证明之前，将高主观概率分配给可提供的猜想和低概率来控制猜想。

该算法具有大量良好的理论属性。仍然粗略地说，该算法学会以尊重的方式分配对句子的概率任何逻辑或统计模式这可以在多项式时间中描述。此外，它还学会了解自己的信仰，并在避免悖论时相信其未来的信念。从摘要引用：

这些属性和许多其他属性都从一个单一的遵循逻辑归纳的标准，这是一系列股票交易类比的动机。粗略地说，每个逻辑句子φ是否与每股价值1美元的股票有关φ是真实的，没有其他事实，我们将逻辑上不确定的推理的信念解释为一系列市场价格，其中ℙ_n（φ)=50%表示每天n，股票φ可以从推理中购买或销售50¢。逻辑归纳标准说（非常大致），不应该有任何多项式可计算的交易策略，具有有限的风险公差，这些交易策略在该市场上赚取了无限性的利润。

这一标准类似于用于支持其他理想推理理论的“no Dutch book”标准，如贝叶斯概率论和期望效用理论。我们认为，逻辑归纳标准可能为具有演绎限制的推理者提供类似的作用，在这些情况下捕捉我们所说的“良好推理”的一些意思。

我们提供的逻辑归纳算法是理论的而不是实际的。它可以被认为是与Ray Solomonoff的归纳推理理论相对应的，后者为理想管理提供了一种不可计算的方法经验不确定性但没有对逻辑或数学句子的不确定性的推理方法。¹逻辑诱导关闭了这种差距。

任何满足逻辑归纳准则的算法都会表现出以下特性:

1。极限收敛和限制一致性逻辑感应器的信念在极限中是完全一致的。(如果，每个可证明正确的句子最终的概率为1，每个可证明错误的句子最终的概率为0φ证明地暗示ψ然后是概率φ收敛到一些不高于概率的值ψ，等等。)

2。可加速诱导：逻辑电感器学习识别可以在多项式时间中识别的定理（或矛盾）中的任何模式。

◦考虑由杰出的数学家(如Ramanujan)产生的一系列猜想，这些猜想很难被证明，但却不断被证明是正确的。逻辑感应器会识别出这种模式，并在有足够的资源来验证Ramanujan的猜想之前，就开始为其分配高概率。

◦作为另一个例子，考虑要求的顺序“输入n，这个长时间运行的计算输出一个0到9之间的自然数。”如果这些断言都是正确的，那么(粗略地说)一个逻辑感应器就会在它们产生的速度尽可能快的情况下为它们分配高概率。如果它们都是假的，一个逻辑感应器就会在它们产生的速度越快的时候，将它们的概率分配得越低。在这个意义上，它学习归纳预测计算机程序的行为。

同样地，给定任何用于编写停止的计算机程序的多项式时间方法，逻辑电感器学会相信它们将粗略地快速停止，因为可以生成源代码。此外，给定任何用于写下计算机程序的多项式方法证明地未能停止，逻辑电感器学会相信，由于可以生成源代码，它们将无法快速停止。When it comes to computer programs that fail to halt but for which there is no proof of this fact, logical inductors will learn not to anticipate that the program is going to halt anytime soon, even though they can’t tell whether the program is going to halt in the long run. In this way, logical inductors give some formal backing to the intuition of many computer scientists that while the halting problem is undecidable in full generality, this rarely interferes with reasoning about computer programs in practice.²

3。仿射一致性逻辑感应器学会尊重不同句子真值之间的逻辑关系，通常在句子被证明之前很长时间。(例如，对于任意的程序，他们会知道“这个程序输出3”和“这个程序输出4”是互斥的，通常在他们能够评估这个程序之前很久。)

4.学习伪随机频率当面对一个充分的伪随机序列时，逻辑感应器学会使用适当的统计摘要。例如，如果Ackermann(n那nπ的小数展开的第0位是很难预测的n，逻辑感应器将学习分配~10%的主观概率的主张“Ackermann(n那n）π的十进制扩展中的数字是7.“

5.校准和无偏性:在逻辑感应器分配~30%概率的序列上，如果真值的平均频率收敛，则它收敛到~30%。事实上，在任何平均真理频率收敛的子序列上，都没有有效的方法来发现逻辑感应器信念中的偏差。

6.科学归纳：可以使用逻辑电感器来进行序列预测，并且在这样做时，它们占主导地位通用半释放。

7.在调理下关闭:这个框架中的条件概率被定义得很好，条件化的逻辑电感器也是逻辑电感器。^3.

8.内省逻辑感应器对自己的信念有准确的信念，以一种避免自我参照的标准悖论的方式。

例如，在序列上的概率表示“我的概率小于50％n天天“靠近50％，振荡伪装，因此没有多项式时间方法来判断是否n一个略高于或略低于50％。

9。自信：逻辑电感学会学会相信他们未来的信念，而不是目前的信仰。这给予了一种正式支持，即使现实世界的概率代理经常在其未来的实践中的推理中经常相当自信，即使哥德尔的不完整定理在全普遍普遍上的反思推理的强烈限制。^4.

上述说法都很模糊;具体说明请参见本文．

逻辑归纳法是Scott Garrabrant为了解决一个开放的问题而开发的谈到六个月前。粗略地说，我们已经形式化了两种不同的逻辑不确定性下的良好推理需求:识别可证明的模式的能力(比如计算机程序声明之间的互斥关系)，以及识别逻辑声明序列中的统计模式的能力(比如识别π的十进制数字看起来相当随机)。这两个目标都很难单独实现，但我们惊讶地发现，实现其中一个目标的简单算法似乎与实现另一个目标的简单算法非常不兼容。斯科特试图同时实现这两个目标，因此产生了逻辑感应器。^5.

我认为这个框架很有可能在元数学、决策理论、博弈论和计算反射等问题上开辟新的研究途径，这些问题长期以来似乎很难解决。我也谨慎乐观地认为，它们将提高我们对决策理论、反事实推理和其他与人工智能有关的问题的理解价值定位．^6.

我们在线发布了一个谈话，有助于为我们的逻辑归纳提供更多背景：^7.

编辑：对于更新的逻辑归纳，进入更多技术细节，请参阅在这里．

“逻辑归纳是一项很大的工作，毫无疑问仍然有一些bug。我们将非常感激反馈:发送错别字，错误，和其他评论errata@www.hdjkn.com．^8.

1. 虽然不实用，但Solomonoff归纳产生了许多在实践中表现良好的技术(集合方法)。我们的算法和Solomonoff归纳法之间的差异指向了新集成方法的方向，这些新集成方法可以证明对管理逻辑不确定性是有用的，就像现代集成方法对管理经验不确定性是有用的一样。↩
2. 另见Calude和Stay's（2006）“大多数程序要么快速停止，要么永不停止。“↩
3. 因此，例如，我们可以通过在一个空理论上取一个逻辑感应器，并将其设置在皮亚诺公理上，从而在皮亚诺算法上制造一个逻辑感应器。↩
4. 举个例子，假设有人问一个逻辑感应器，“你的概率是多少?φ鉴于将来，您将要思考φ可能？”非常粗略地说，电感会回答，“在这种情况下φ很可能，“即使它目前认为这一点φ是不太可能的。此外，逻辑电感器以避免悖论的方式执行此操作。如果φ是“在未来，我会思考φ小于50%的可能性”，而现在你要问，“你的概率是多少?φ假设在未来你会相信它≥50%的可能性?那么答案就是“很低”。但如果你问"你的概率是多少φ，假设在未来你的概率是极其密切的到50%呢?那么它会回答:“非常接近50%。”↩
5. 这个结果的早期工作可以在智能代理基金会论坛．↩
6. 假设设计一个人工智能系统来学习人类的偏好(例如，亚博体育苹果app官方下载合作反强化学习)．通常的方法是将人类建模为一个试图最大化某些奖励函数的贝叶斯推理者，但这严重限制了我们建模人类非理性和错误计算的能力，即使是在简化的设置中。逻辑归纳可以通过提供一个有限推理者的理想化的正式模型来帮助我们解决这个问题，这些推理者不知道(但最终可以学习)他们所有信念的逻辑含义。

   举个例子，假设一个人做出了一个(非被迫的)失败的棋步。一个通过观察亚博体育苹果app官方下载人类行为来学习人类偏好的人工智能系统可能不应该得出人类的结论通缉损失。相反，我们关于这个困境的玩具模型应该允许人类可能是资源有限的，可能无法推断出他们行动的全部含义;我们的模型应该允许人工智能系统也意识到这一点，或者可以了解到这一点。亚博体育苹果app官方下载↩

7. 这是相对非技术部分的幻灯片;从技术部分滑动．对于想要跳过技术内容的观众，我们将演讲的中间部分作为一个较短的独立视频上传:链接．↩
8. 这Intelligence.org版本通常会比ARXIV版本．↩