新论文:《逻辑归纳》

||论文

逻辑归纳MIRI发表了一篇论文,介绍了一种新的演绎有限推理模型:逻辑归纳,作者斯科特·加拉布兰特、茨维·本森·蒂尔森、安德鲁·克里奇、我和杰西卡·泰勒。读者不妨从删节本

考虑这样一种情况:推理者正在观察一个演绎过程(例如数学家和计算机程序员的社区),并等待各种逻辑主张的证明(例如美国广播公司猜测,或者说“这个计算机程序有一个错误”,同时猜测哪些说法是正确的。粗略地说,我们的论文提出了一个可计算(虽然效率不高)的算法,该算法的运算速度超过了推导速度,在证明产生之前,就将高主观概率分配给可证明猜想,而将低概率分配给不可证明猜想。

该算法具有许多优良的理论性能。粗略地说,这个算法学会了以这样的方式给句子分配概率任何逻辑或统计模式可以用多项式时间来描述的。此外,它学会了理性地思考自己的信仰,相信自己未来的信仰,同时避免悖论。引自摘要:

这些属性和许多其他属性都来自于逻辑归纳准则,这是由一系列股票交易类比所推动的。粗略地说,每个逻辑句子φ与每股价值1美元的股票相关,如果φ是真的,没有别的,我们把逻辑上不确定的推理者的信念状态解释为一组市场价格,其中n(φ)=50%表示当天n,股份φ可从推理机以50美分的价格购买或出售。逻辑归纳标准(非常粗略地)说,不应该有任何具有有限风险容忍度的多项式时间可计算的交易策略,随着时间的推移在该市场上赚取无限利润。

这个标准类似于“无荷兰书”标准,用于支持其他理想推理理论,如贝叶斯概率理论和期望效用理论。我们相信,逻辑归纳标准可能对推理者起到类似的作用,具有演绎的局限性,捕捉到我们在这些情况下所说的“良好推理”的一些含义。

我们提供的逻辑归纳算法是理论的,而不是实际的。它与索罗门诺夫的归纳推理理论相对应,为理想的管理提供了一种无法计算的方法经验主义的逻辑或数学句子的不确定性,但没有相应的推理方法。1个逻辑归纳法弥补了这一差距。

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

一。极限收敛极限相干逻辑感应器的信念在极限内是完全一致的。(每个可证明为真句子的概率最终为1,每个可证明为假句子的概率最终为0,如果φ可证明的暗示ψ那么φ收敛到不高于ψ等等。)

2。可证性归纳:逻辑感应器学习识别定理(或矛盾)中的任何模式,这些模式可以在多项式时间内识别。

◦考虑由一个杰出的数学家产生的一系列猜想,如拉马努詹,这很难证明,但不断证明是真的。逻辑感应器会识别出这个模式,并在有足够的资源来验证它们之前,就开始为Ramanujan的猜想分配高概率。

◦是另一个例子,考虑索赔的顺序“投入”n,这个长时间运行的计算会输出一个介于0到9之间的自然数。“如果这些断言都是真的,那么(大致上说)逻辑感应器会学习尽可能快地将高概率分配给它们。如果它们都是错误的,逻辑感应器就会学习尽可能快地给它们分配低概率。从这个意义上讲,它学习归纳地预测计算机程序将如何运行。

类似地,给出任何多项式时间方法来记录停止的计算机程序,逻辑感应器学会相信它们将以尽可能快的速度停止。此外,给出任何多项式时间方法来写下证明地如果不能停止,逻辑感应器就会学会相信,它们将不能像生成源代码那样快地停止。当计算机程序无法停止,但没有证据证明这一点时,逻辑感应器将学会不预测程序将很快停止,即使他们无法判断程序是否会在长期内停止。通过这种方式,逻辑感应器给许多计算机科学家的直觉提供了一些形式上的支持,他们的直觉是,虽然停止问题在完全普遍性上是不可判定的,但这在实践中很少干扰对计算机程序的推理。2个

三。仿射相干:逻辑诱导者学会尊重不同句子的真值之间的逻辑关系,往往远在句子被证明之前。(例如,对于任意的程序,他们会知道“这个程序输出3”和“这个程序输出4”是互斥的,通常在他们能够评估所讨论的程序之前很久。)

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

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

6.科学归纳法:逻辑电感可用于进行序列预测,当这样做时,它们支配通用半测度。

7号。调节关闭:在这个框架中,条件概率是定义良好的,条件化逻辑电感器也是逻辑电感器。

8个。反省逻辑感应者对他们自己的信念有准确的信念,以避免标准的自相矛盾的自我参照。

·例如,序列上的概率表示“我在n第天“非常接近50%并且伪随机振荡,因此没有多项式时间方法来判断n这个略高于或略低于50%。

9号。自信:逻辑感应器学会相信自己未来的信念,而不是现在的信念。这为直觉提供了一些形式上的支持,即现实世界中的概率代理在实践中通常可以对其未来的推理有合理的信心,尽管哥德尔的不完全性定理对完全普遍的反思性推理有很强的限制。4个

上述说法都相当模糊;有关精确的声明,请参阅报纸

逻辑归纳法是由Scott Garrabrant开发的,旨在解决一个开放的问题谈到六个月前。粗略地说,我们有正式的两个不同的站好的推理在逻辑的不确定性:识别模式的能力可证明的是什么(如相互排他性关于计算机程序)之间的关系,和序列的统计模式识别能力的逻辑要求(如认识到π的小数位数似乎相当伪随机)。两者都不是很难单独实现的,但是我们惊讶地发现,实现其中一个的简单算法似乎与实现另一个的简单算法不兼容。逻辑电感器是斯科特试图同时实现这两者的产物。5个

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

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

编辑:有关更多技术细节中的逻辑归纳的最新讨论,请参见在这里

逻辑归纳“这是一个很大的工作,毫无疑问还有很多漏洞。我们非常感谢您的反馈:发送打字错误和其他评论到errata@www.jayrazon.com

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

每次发布新的技术论文时都会收到通知。


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

    例如,假设一个人在国际象棋中走了一个(非被迫的)败下阵来。一个通过观察亚博体育苹果app官方下载人类行为来学习人类偏好的人工智能系统可能不应该得出这样的结论通缉犯输了。相反,我们这个两难困境的玩具模型应该允许人类可能是资源有限的,可能无法推断出他们行动的全部含义;我们的模型应该允许人工智能系统也意识到这一点,或者可以了解这一点。亚博体育苹果app官方下载

  7. 从那时起相对非技术性的部分;技术部分的幻灯片。对于想要跳过技术内容的观众,我们已经上传了演讲的中间部分作为一个较短的独立视频:链接
  8. 这个情报.org版本通常会比arXiv版本