新论文:“逻辑归纳”

||文件

逻辑归纳MIRI正在发布一篇论文,介绍了一个新的减扣限制推理模型:“逻辑归纳作者:Scott Garrabrant、Tsvi Benson-Tilsen、Andrew Critch、我自己和Jessica Taylor。读者可能希望从简版

考虑这样一个设置,其中一个推理者正在观察一个演绎过程(比如数学家和计算机程序员社区),并等待各种逻辑声明的证明(比如ABC猜测,或者“这个计算机程序有一个错误”),同时猜测哪些说法会被证明是正确的。粗略地说,我们的论文提出了一种可计算(尽管效率低下)的算法,它超过了演绎的速度,将高主观概率分配给可证明的猜想,而将低概率分配给可证明的猜想,在证明产生之前很久。

该算法具有大量良好的理论性质。粗略地说,该算法学会了以相应的方式为句子分配概率任何逻辑或统计模式这可以用多项式时间来描述。此外,它学会对自己的信念进行很好的推理,并相信自己未来的信念,同时避免悖论。摘自摘要:

这些属性和许多其他属性都是单一属性的结果逻辑归纳的标准,其动机是一系列股票交易类比。大致说来,每个逻辑句φ.与每股1美元的股票有关,如果φ.是真的,没有别的,我们将逻辑上不确定的推理者的信念状态解释为一组市场价格,ℙNφ.(50%意味着在那天N,股φ.可以以50美分的价格从推理者那里购买或出售。逻辑归纳标准(非常粗略地)认为,不应该存在任何具有有限风险容忍度的多项式时间可计算的交易策略,从而在一段时间内在该市场上赚取无限利润。

该准则类似于“没有荷兰书”准则,用于支持其他理想推理理论,如贝叶斯概率论和期望效用理论。我们相信,逻辑归纳标准可以为有演绎限制的推理者提供类似的作用,捕捉我们在这些情况下所谓的“良好推理”的一些含义。

我们提供的逻辑归纳算法是理论而非实用的。它可以被认为是射线Solomonoff的归纳推理理论的对应物,这为理想管理提供了无明显的方法经验不确定性,但没有相应的方法对不确定性下的逻辑或数学句子进行推理。1逻辑归纳缩小了这个差距。

任何满足逻辑归纳标准的算法都具有以下特性:

1.限制融合限制一致性:逻辑电感器的信仰在极限中完全一致。(每种可怕的真正句子最终得到概率1,每种可怕的假句最终都会得到概率0,如果φ.证明地暗示ψ那么概率是φ.收敛到不高于的概率ψ, 等等。)

2.只是感应:逻辑电感学会识别任何模式的定理(或矛盾),可以识别在多项式时间。

◦考虑一系列由辉煌的数学家产生的猜想,例如ramanujan,这很难证明,但不断变成真实。逻辑电感器将识别此模式并开始为ramanujan的猜想高概率分配好,然后才能验证它们。

◦作为另一个例子,考虑在输入上的索赔顺序N,这个长时间运行的计算输出一个介于0到9之间的自然数。”如果这些说法都是正确的,那么(粗略地说)逻辑电感器就会在它们产生的最快时间内为它们分配高概率。如果它们都是假的,一个逻辑电感器就会学习在它们产生的最快时间内为它们分配低概率。在这个意义上,它学习归纳预测计算机程序将如何行为。

◦同样,给任何多项式时间的方法写下来的计算机程序,停止,逻辑电感学会相信,他们将停止大致一样快的源代码可以生成。此外,给出任何多项式时间方法来编写计算机程序可删除如果不能停止,逻辑电感器就会相信,它们停止的速度和源代码生成的速度一样快。计算机程序时无法停止,但没有证明这个事实,逻辑电感将学习不是预测,项目将很快停止,即使他们无法分辨该项目将停止从长远来看。通过这种方式,逻辑电感器为许多计算机科学家的直觉提供了某种形式上的支持,即当中止问题在完全普遍的情况下是无法确定的,这很少干扰对计算机程序的实际推理。2

3.仿射一致性:逻辑电感器学会尊重不同句子的真实值之间的逻辑关系,通常在可以证明句子之前很久。(例如,他们将学习“该计划输出3”和“该程序输出4”的任意程序是互斥的,通常在他们能够评估所讨论的程序之前。)

4.学习伪随机频率:面对足够的伪随机序列,逻辑电感器学会使用适当的统计摘要。例如,如果Ackermann(NNπ的十进制展开式的第1位数字是很难预测的N,逻辑电感将学会为索赔(Ackermann)分配约10%的主观概率(NNπ的十进制展开数的第7位是7。”

5。校准无偏见:对于一个逻辑电感分配到~30%概率的序列,如果真理的平均频率收敛,那么它收敛到~30%。事实上,在真理的平均频率收敛的任何子序列上,没有有效的方法来寻找逻辑电感的信念的偏差。

6。科学归纳逻辑电感器可以用来做序列预测,当这样做时,它们支配着通用半测度。

7.关闭条件下:该框架中的条件概率是明确定义的,并且有条件化的逻辑电感器也是逻辑电感器。3.

8.自省:逻辑电感器以避免自我参考标准悖论的方式对自己的信仰有准确的信念。

◦例如,在一个序列上的概率说“我有低于50%的概率在。N这一天“走极接近50%,振荡伪随机,以至于没有多项式时间方法来判断是否N这个略高于或略低于50%。

9.自信:逻辑感应者学会相信他们未来的信念,而不是他们现在的信念。这为现实世界的概率代理在实践中经常对其未来的推理有合理的信心这一直觉提供了一些正式的支持,尽管Gödel的不完备定理在完全一般性上对反思推理有很强的限制。4

上述索赔一切都含糊不清;对于确切的陈述,请参阅这篇论文

逻辑归纳法是由Scott Garrabrant发明的用来解决一个我们谈到六个月前。粗略地说,我们在逻辑不确定性下进行了两种不同的探索,以便在逻辑不确定性下进行良好的推理:识别模式中的模式(例如关于计算机程序的权利要求之间的互排差关系),以及识别逻辑索赔序列中的统计模式的能力(例如识别出π似乎漂亮伪随机的小数位)。既难以孤立也不太难以实现,但我们感到惊讶地发现,我们的简单算法与实现另一个实现另一个的简单算法相当不相容。逻辑电感器诞生于斯科特试图同时实现两者。5

我认为这一框架将有一个很好的机会,在元素,决策理论,博弈论和长期难以应变的难题问题中开辟了新的研究途径。我也谨慎乐观,他们将改善我们对决策理论和反事工程的理解,以及与AI相关的其他问题价值对齐6

我们在网上发布了一个演讲,为我们的逻辑归纳工作提供了更多的背景:7

编辑关于逻辑归纳的更多技术细节,请参阅这里

逻辑归纳是一项很大的工作,毫无疑问仍然存在一些bug。我们非常感谢反馈:发送打印错误,错误和其他评论errata@www.hdjkn.com.8

注册获取MIRI新技术成果的更新

每次有新的技术论文发表时都得到通知。


  1. 虽然不切实际,所罗门组织的诱导产生了在实践中表现良好的许多技术(集成方法)。新集合方法方向算法与所罗门组织诱导点的差异,这对于管理逻辑不确定性有用,以与现代集合方法相同的方式对于管理经验不确定性是有用的。
  2. 参见Calude and Stay’s(2006)”大多数程序都停止快速或永不停止。
  3. 因此,例如,可以通过在空理论上拍摄逻辑电感并在PEANO公理上调节逻辑电感来使PEANO算术中的逻辑电感器进行逻辑电感。
  4. 作为一个例子,想象一下,一个人问逻辑电感,“你的概率是多少φ.,考虑到将来你会想φ.有可能吗?”非常粗略地说,电感器会回答,“在这种情况下φ.很可能"即使它现在这么想φ.是不可能的。此外,逻辑电感可以避免悖论的方式做到这一点。如果φ.是“未来我将思考?φ.小于50%的可能性,”现在你问,“你的概率是多少φ.,假设未来你认为它有≥50%的可能性?那么答案就会是“非常低”。但是如果你问“你的概率是多少?φ.鉴于未来您的概率将是非常接近到50%?“然后它会回答,“非常接近50%”。
  5. 可以在此结果的早期工作智能代理基础论坛
  6. 考虑一下设计一个能够学习人类偏好的AI系统的任务(例如,亚博体育苹果app官方下载合作逆钢筋学习).通常的方法是将人类建模为试图最大化某些奖励功能的贝叶斯推理者,但这严重限制了我们模拟人类非理性和误判的能力,即使是在简化的环境中。逻辑归纳可以帮助我们解决这个问题,它为有限的推理者提供了一个理想化的形式模型,这些推理者不知道(但最终可以学习)他们所有信念的逻辑含义。

    例如,假设人类代理人使得(未裁量)失去象棋活动。一个AI系统亚博体育苹果app官方下载编程,以了解人类从观察到的行为的偏好可能不应该得出结论想要损失。相反,我们关于这种困境的玩具模型应该允许人类可能是资源有限的,可能无法推断出他们行动的全部含义;我们的模型应该允许AI系统也意识到这一点,或者能够了解它。亚博体育苹果app官方下载

  7. 幻灯片来自于非技术性的部分幻灯片从技术部分.对于想要跳过技术内容的观众,我们将谈话的中间部分上传作为一个较短的独立视频:关联
  8. www.hdjkn.com版本一般会比arXiv版本