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

||文件

我很高兴地宣布两个与问题有关的新技术结果逻辑不确定性,也许是过去一年中最重要的结果。简而言之,这些结果将逻辑不确定性的问题分为两个不同的子问题,每个子问题都可以孤立地解决。鉴于这些结果,剩下的问题是找到一次解决统一的方法集。

每个子问题的解决方案都有两个新论文,基于Scott Garrabrant的矛头的工作:“归纳连贯1和 ”与无限延迟的在线学习中的渐近融合。“2

给出一些问题的背景:现代概率理论模型推理的经验不确定性,他们对物理环境状态的不确定性,例如“这扇门后面是什么?”但是,它不能代表推理师逻辑不确定性,他们对“这款图灵机停止”或“双原稿猜想”等陈述的不确定性具有小于千兆字节的证据。“3.

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或Mergeort来对特定数据集进行排序的代理。他们可能知道Quicksort通常比合并从合并速度运行,但这并不一定适用于当前数据集。他们原则上可以确定哪一个在这个数据集上使用更少的资源,通过运行它们并进行比较,但这会破坏目的。直观地,他们有一个公平的知识,即索赔“Quicksort比这个数据集上的合并速度快,”但现代概率理论不能告诉我们他们应该使用哪些信息以及如何使用。4.


对于一个推理者来说,为他们没有计算,但原则上可以计算的索赔分配“合理的概率”是什么意思?如果没有概率论的指导,我们只能用直觉来确定那些似乎是理想的属性,然后研究哪些是可能的。直觉上,我们希望逻辑上非无所不知的推理者能展示出至少两个特性:

1。他们应该能够在可以证明或反驳索赔自己之前,请注意可证明的索赔的模式。例如,考虑“这个图灵机输出奇数”和“这个图灵机输出偶数”的权利要求。良好的理性思考这些索赔应该最终认识到它们是互斥的,并将其总和的概率分配到最多1,即使在它们可以运行相关的图灵机之前也是如此。

2。他们应该能够在句子类中注意到具有特定频率的句子类的模式。例如,它们应该分配大约10%的概率到“10One hundred.PI的数量是一个7“代替有关数字的任何信息,在观察(但不是证明)PI的数字往往是均匀分布的。

Miri在过去一年的逻辑不确定性上的工作可以非常简单地概括为“我们弄清楚如何单独获得这两个物业,但发现很难立即获得。”

归纳连贯归纳连贯“我共同撰写的Garrabrant,Benya Fallenstein和Abram Demski,展示了如何获得第一个财产。摘要读:

虽然概率理论通常应用于外部环境,但是近来有一些近来对运行过昂的计算输出的概率建模的兴趣。由于数学逻辑是一个强大的工具,用于推理计算机程序,我们从集成概率和逻辑的角度来看,考虑这个问题。

最近对数学陈述分配概率的工作已经使用了概念相干分布,满足逻辑约束,例如句子的概率及其否定总结到一个。虽然存在算法,但是在极限中收敛到相干概率分布,但这仅产生了关于这些分布的有限近似的弱保证。在我们的环境中,这是一个显着的限制:相干分发将概率1分配给特定逻辑理论中可证明的所有陈述,例如PEANO算术,这可以证明任何终端计算的输出是什么;因此,相干分布必须将概率1分配给任何终端计算的输出。

为了模拟计算的不确定性,我们建议使用近似值相干分布。我们介绍归纳连贯,加强相干性,在有限近似下提供适当的约束,并提出满足该标准的算法。

给定一系列可怕的相互独家句子,或者一系列句子,其中每个句子都可以意味着接下来,感应相干的预测因素的概率最终开始尊重这种模式。即使预测器尚未证明模式持有,这也是如此;如果原则上是可能的,最终可以证明每个图案实例,那么感应相干的预测器将开始识别它的“在太长”之前,在特定的技术意义上,即使证据本身很长。

渐近收敛与无限延迟的在线学习中的渐近融合“我共同撰写的Garrabrant和Jessica Taylor,描述了一种具有第二个属性的算法。摘要读:

我们通过观察较小计算的结果来研究预测运行太昂贵的计算结果的问题。我们将其塑造为具有延迟反馈的在线学习问题,其中延迟的长度是无限的,我们主要在随机设置中学。我们展示在此设置中,一般不可能是不可能的,并且最佳预测员可能不会有平均遗憾。但是,仍然可以通过评估预测员对其预测的特定稀疏独立子序列的预测,提供算法算法到贝叶斯 - 最佳预测。我们给出了一种算法,这会融合到良好的行为上渐近的,并为收敛需要提供非常弱的界限。然后,我们将结果与在确定性设置中预测大计算的问题相关。

第一属性是关于识别关于索赔之间的逻辑关系的模式 - 说“索赔A意义声称索赔B,因此我对B的概率必须至少是我的概率。”相比之下,第二属性是识别类似索赔之间的频率模式 - 说“我缺乏资源来判断这一索赔是真实的,但90%的类似索赔已经是正确的,因此基本率为90%”(其中部分问题在于弄清楚是什么是“类似索赔”)。

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


每篇论文都很有趣,但对我们来说,令人兴奋的结果是,我们在逻辑不确定性下戏弄并将两种单独的概念正式化为“良好的推理”,这两者都是引人注目的。

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


注册以获取新的Miri技术结果的更新

每次发布新技术文件时都会通知。


  1. 这项工作最初的标题是“统一的连贯性”。这篇文章已经更新以反映新的术语。
  2. Garrabrant的IAFF论坛帖子提供了最初开发的结果,作为对Ray Solomonoff的算法概率理论的回应。Solomonoff方法的具体失败纠缠的Benford测试为“渐近融合......”问题,有限的早期版本在“渐近逻辑不确定性和Benford测试“ 报告。归纳相干性定义均匀连贯2,并且识别出电感相干预测器的示例改进的DEMSKI之前是均匀连贯的
  3. 这种不确定性主要是出于历史原因的“逻辑不确定性”。我认为这是这样的:我们关心代理商的理解能力,例如,“这个程序将停止”。金宝博官方这些权利要求可以用逻辑句中表达。问题“代理分配给这台机器停止是什么概率?”然后变成“此代理将此特定逻辑句子分配有什么概率?”这些陈述的真实性可以原则上确定,但代理商可能没有资源来计算实践中的答案。
  4. 有关逻辑不确定性的更多背景,请参阅Gaifman的“关于一阶Calculi的措施,“加尔伯的”贝叶斯确认理论的旧证据和逻辑不可用,“Hutter,Lloyd,Ng和Uther's”表达逻辑中句子的概率,“和Aaronson的”为什么哲学家应该关心计算复杂性。“