MIRI研亚博体育官网究助理凡妮莎·科索伊开发了一种在逻辑不确定性下推理的新框架。最优多项式时间估计:近似算法的贝叶斯概念文摘:
“近似算法”的概念通常仅应用于优化问题,因为在优化问题中,算法对任何给定输入的性能是连续参数。我们介绍了适用于决策问题和功能的新近似概念,灵感来自贝叶斯概率。从贝叶斯推荐者的角度来看有限的计算资源,答案无法确定的问题是不确定的,因此应该由随机变量描述。因此,应该有意思谈这个随机变量的预期价值,我们通过引入“最优多项式估计器”的概念,我们以平均案例复杂性理论的语言形式化的想法。我们证明了一些存在定理和完整性结果,并表明最佳多项式估计器具有“经典”概率理论的许多平行。
Kosoy的最优估计器框架试图从不同的角度来建模在演绎限制下的通用推理,而不是Scott Garrabrant的逻辑电感器框架,更多地关注计算效率和可处理性。
该框架在博弈论(利用最优预测系统实现CDT亚博体育苹果app官方下载),并可能有助于形式化决策理论中的反可能条件(随机算法的逻辑反事实,用伪随机化稳定逻辑反事实),1但它似乎特别有趣,因为它与经典概率论有强烈的相似之处,以及它与复杂性理论中概念的协同作用。
最优估计器允许我们为确定性的量分配概率和期望值,但不能在多项式时间内进行评估。这是上下文相关的:与其给一个孤立的问题分配概率,不如给整个问题族同时分配概率。
结果在平均情况复杂性理论中被证明是非常自然的,这使得最优估计从纯计算复杂性的角度(不考虑应用)变得有趣。特别地,一组语言或函数能够接受某种类型的最优估计,这就是一个自然分布的复杂性类,这些类以有趣的方式与已知的复杂性类相关联。
对于理想化的AI系统,最优估计可以被认为是计算可行和计算不可行之间的桥梁。亚博体育苹果app官方下载通常情况下,我们可以找到一个数学对象来回答AI理论中的一个基本问题,但这个对象在计算上是不可行的,因此不能模拟现实世界的AI系统和子系统的一些关键特征。亚博体育苹果app官方下载在许多情况下,最优估计可以用来构造不可行的目标的最优可行近似,同时保留一些类似于不可行的目标的良好性质。
要使用评估器来构建实际的系统,我们首先需要知道如何构建正确的评估器,如果没亚博体育苹果app官方下载有相关的统一评估器,或者相关评估器本身不实际,这可能是不可能的。2由于实际的(一致的)最优估计量只在数学上存在于一些非常特殊的情况下,Kosoy考虑了需要存在的估计量建议字符串(粗略地说:具有无限长的源代码的程序)。这个假设意味着最优估计总是存在的,允许我们使用它们作为通用的理论工具来理解计算有界代理的性质。3.