把逻辑不确定性分为两个子问题的新论文

||文件

我很高兴地宣布相关的问题的两种新技术成果逻辑不确定性,或许是我们过去一年最重要的成果。简言之,这些结果将逻辑不确定性问题分解为两个不同的子问题,我们现在可以分别解决每个子问题。根据这些结果,剩下的问题是找到一套统一的方法同时解决这两个问题。

每个子问题的解决方案都可以在两篇新的论文中找到,这是基于Scott Garrabrant领导的工作:“归纳相干1个和“无限时滞在线学习的渐近收敛性“。2个

给出问题的一些背景:现代概率论模型推理者的经验不确定性,他们对物理环境状态的不确定性,例如,“这扇门后面是什么?”?“然而,它不能代表推理者”符合逻辑的不确定性,他们对像“这个图灵机暂停”或语句不确定性“孪生素数猜想有证据证明是小于一千兆字节长。”

Roughly speaking, if you give a classical probability distribution variables for statements that could be deduced in principle, then the axioms of probability theory force you to put probability either 0 or 1 on those statements, because you’re not allowed to assign positive probability to contradictions. In other words, modern probability theory assumes that all reasoners know all the consequences of all the things they know, even if deducing those consequences is intractable.

我们希望概率论,使我们能够有大约报表的不确定性,他们还没有评估模型推理的推广。此外,我们要了解如何分配“合理”的概率是评估过于昂贵的索赔。

设想一个代理正在考虑是使用quicksort还是mergesort对特定的数据集进行排序。他们可能知道快速排序通常比合并排序运行得快,但这并不一定适用于当前数据集。原则上,他们可以通过运行这两个数据集并进行比较,找出哪一个在这个数据集上使用更少的资源,但这样做会达不到目的。直觉上,他们对“quicksort比mergesort在这个数据集上运行得更快”的说法有相当的了解,但现代概率论无法告诉我们他们应该使用哪些信息以及如何使用。4个


对于一个推理者来说,把“合理的概率”分配给那些他们没有计算,但原则上可以计算的主张,这意味着什么?如果没有概率论来指导我们,我们就只能用直觉来识别那些似乎是可取的属性,然后研究哪些属性是可能的。直观地说,至少有两个我们希望逻辑上非全知推理者展示的属性:

一。他们应该能够注意到哪些模式是可以证明的索赔,甚至在他们能够证明或反驳索赔本身之前。例如,考虑在权利要求“这个图灵机输出一个奇数”和“这个图灵机输出一个偶数。”关于这些权利要求的良好的推理思考最终应该认识到,它们是相互排斥的,并将它们分配概率是总和至多1,甚至才可以运行相关的图灵机。

2。他们应该能够注意到那些真正具有一定的频率句子类的图案。例如,他们应该将大约10%的概率分配给100个π的第个数字是一个7“,在观察(但不证明)π的数字趋向于均匀分布后,代替了关于该数字的任何信息。

过去一年,MIRI在逻辑不确定性方面的工作可以简单地概括为“我们找到了如何分别获得这两个属性的方法,但是发现很难同时获得这两个属性。”

归纳相干归纳相干,这本书是我和加拉布兰特、本雅·费伦斯坦和亚布拉姆·德姆斯基合著的,展示了如何获得第一处房产。摘要如下:

虽然概率理论通常适用于外部环境,最近有在那些运行太贵计算的输出的概率模型的兴趣。由于数理逻辑是推理计算机程序的功能强大的工具,我们从整合的概率和逻辑的角度来考虑这个问题。

最近关于给数学报表分配概率的工作使用了连贯的分布,它满足逻辑约束,如句子的概率及其求和为1的否定。虽然有一些算法在极限内收敛到一个相干概率分布,但这只能得到这些分布有限逼近的弱保证。在我们的设置中,这是一个显著的限制:相干分布将概率1赋给特定逻辑理论中可证明的所有语句,例如Peano算术,它可以证明任何终止计算的输出是什么;因此,相干分布必须将概率1赋给任何终止计算的输出。

约的计算模型不确定性,我们建议用工作近似值相干分布。介绍归纳相干,相干性的加强,其提供有限近似适当的约束,并提出了一种算法,该算法满足这个标准。

给定一系列可证明互斥的句子,或一系列可证明隐含下一个的句子,一个归纳连贯的预测者的概率最终开始尊重这一模式。即使预测者还不能证明模式是成立的,这也是正确的;如果在原则上能够最终证明模式的每一个实例,那么归纳一致的预测者将“很快”开始识别它,在特定的技术意义上,即使证明本身很长。

渐近收敛无限时滞在线学习的渐近收敛性“,我合着用Garrabrant和杰西卡泰勒,描述了具有第二属性的算法。摘要如下:

我们研究预测,在运行过于昂贵的计算结果的问题,通过更小的计算结果的观察。我们这个模型作为在线学习问题,延迟反馈,其中延迟的长度是无界的,这是我们主要研究在随机设置。我们表明,在此设置,一致性是不可能在一般情况下,和最佳的预测可能不会有遗憾平均变为零。然而,它仍然有可能给该渐近趋于贝叶斯最佳预测,通过对具体的评估预测他们的预测稀疏独立的子序列算法。我们举一个算法,这样做,其渐近收敛于良好的行为,并给它取收敛多久非常弱边界。然后,我们与我们的结果反馈给在确定性环境预测大型计算的问题。

第一个属性是关于识别权利要求之间的逻辑关系的模式,即“权利要求A意味着权利要求B,因此我在B上的概率必须至少是我在A上的概率。”,第二个属性是识别类似索赔之间的频率模式,即“我缺乏判断这一索赔是否属实的资源,但90%的类似索赔是真实的,因此基准利率为90%”(问题的一部分是找出什么算是“类似索赔”)。

在本技术报告中,我们将后一个任务建模为一个在线学习问题,其中预测者观察许多小计算的行为,并且必须预测大计算的行为。我们给出了一个算法,在特定的技术意义上,最终将“正确”概率分配给每个可预测的观测子序列。


每篇论文是在自己的权利有趣,但对我们来说,令人激动的结果是,我们已经挑开,并正式什么罪名的两个独立的概念是“好理由”逻辑下的不确定性,这两者都是引人注目的。

此外,我们将这两个概念形式化的方法非常不同。“归纳一致性”在传统的“逻辑与概率统一”的框架下描述问题,而“无限时滞在线学习的渐近收敛性”更自然地适用于在线机器学习框架。我们发现的解决第一个问题的方法似乎对解决第二个问题没有帮助,反之亦然。事实上,这两个孤立的解决方案似乎很难调和。这两篇论文留下的问题是:我们能同时得到一个同时满足这两个性质的算法吗?


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

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


  1. 这项工作最初的标题是“一致连贯性”。这篇文章已经更新,以反映新的术语。
  2. Garrabrant的IAFF论坛帖子提供了这些结果最初是如何发展的记录,作为对Ray Solomonoff算法概率理论的回应。所罗门诺夫方法的具体失效纠缠本福德测试为奠定基础“渐进收敛......”的问题,这有限的早期版本被刊登在了“渐近逻辑不确定性和本福德测试”的报告。感应相干性在定义统一连贯2,并且归纳相干预测器的示例在改性Demski之前被均匀地相干.
  3. 这种不确定性被称为“逻辑不确定性”主要是出于历史原因。我认为它是这样的:我们关心代理人的能力,推理软件系统,例如,‘该程序将停止。’亚博体育苹果app官方下载这些权利要求可以以逻辑的句子来表示。这个问题:“什么概率确实代理分配到本机停止?”就变成了“什么的概率确实该代理分配给该特定逻辑的句子?”这些声明的真实性原则上可确定,但代理可能没有足够的资源来计算实际的答案。
  4. 有关逻辑不确定性的更多背景,见Gaifman的“关于一阶计算中的测度“加伯的”旧的证据和逻辑全知的贝叶斯理论的确认,”胡特,劳合社,吴和乌瑟尔的“表达逻辑中句子的概率,“和Aaronson的”哲学家为什么要关心计算复杂性“。