I’m happy to announce two new technical results related to the problem of逻辑不确定性，也许是过去一年中最重要的结果。简而言之，这些结果将逻辑不确定性的问题分为两个不同的子问题，每个子问题现在都可以隔离地解决。鉴于这些结果，其余问题是找到一组一次解决这两个方法的统一方法。
每个子问题的解决方案都在两篇新论文中获得，基于斯科特·加拉布兰特（Scott Garrabrant）的工作：“”电感连贯性透明1and “无限延迟的在线学习中的渐近融合。透明2
为问题提供一些背景：现代概率理论对推理者的经验不确定性进行了模型，他们对物理环境状态的不确定性，例如“这扇门背后是什么？”但是，它不能代表推理者的逻辑uncertainty, their uncertainty about statements like “this Turing machine halts” or “the twin prime conjecture has a proof that is less than a gigabyte long.”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.
We want a generalization of probability theory that allows us to model reasoners that have uncertainty about statements that they have not yet evaluated. Furthermore, we want to understand how to assign “reasonable” probabilities to claims that are too expensive to evaluate.
想象一下，要考虑使用QuickSort还是Mergesort对特定数据集进行分类的代理。他们可能知道，QuickSort的运行速度通常比Mergesort快，但这不一定适用于当前数据集。他们可以原则上弄清楚哪个数据集上的资源较少，通过运行它们并进行比较，但这将破坏目的。从直觉上讲，它们具有相当多的知识，这些知识“ QuickSort运行的速度比此数据集上的Mergesort更快”，但是现代概率理论无法告诉我们他们应该使用哪些信息以及如何使用。4
这是什么意思reasoner分配”的原因able probabilities” to claims that they haven’t computed, but could compute in principle? Without probability theory to guide us, we’re reduced to using intuition to identify properties that seem desirable, and then investigating which ones are possible. Intuitively, there are at least two properties we would want logically non-omniscient reasoners to exhibit:
1。他们应该能够注意到有关索赔的模式，甚至在他们证明或反驳索赔本身之前。For example, consider the claims “this Turing machine outputs an odd number” and “this Turing machine outputs an even number.” A good reasoner thinking about those claims should eventually recognize that they are mutually exclusive, and assign them probabilities that sum to at most 1, even before they can run the relevant Turing machine.
2。They should be able to notice patterns in sentence classes that are true with a certain frequency.例如，他们应将大约10％的概率分配给“ 10100在观察（但未证明）PI的数字倾向于均匀分布之后，PI的数字是7英寸代替有关数字的任何信息。
Miri在过去的一年中的逻辑不确定性工作可以简短地总结，因为“我们弄清楚了如何单独获得这两个属性，但发现很难同时获得这两个属性。”
“电感连贯性”，我与Garrabrant，Benya Fallenstein和Abram Demski合着，展示了如何获得第一个财产。摘要读取：
While probability theory is normally applied to external environments, there has been some recent interest in probabilistic modeling of the outputs of computations that are too expensive to run. Since mathematical logic is a powerful tool for reasoning about computer programs, we consider this problem from the perspective of integrating probability and logic.
关于将概率分配给数学陈述的最新工作已经使用了相干分布，满足逻辑约束，例如句子的概率及其否定概括。尽管有一些算法会收敛到极限中的相干概率分布，但这仅能在这些分布的有限近似值中获得较弱的保证。在我们的环境中，这是一个重要的局限性：连贯分布将概率一个分配给特定逻辑理论中证明的所有语句，例如Peano算术，这可以证明任何终止计算的输出是什么；因此，连贯的分布必须将概率一个分配给任何终止计算的输出。
To model uncertainty about computations, we propose to work with近似值to coherent distributions. We introduce电感连贯性, a strengthening of coherence that provides appropriate constraints on finite approximations, and propose an algorithm which satisfies this criterion.
考虑到一系列可证明的相互排斥的句子，或一系列句子，每个句子都暗示着下一个句子，归纳一致的预测指标的概率最终开始尊重这种模式。即使预测变量尚未证明该模式成立，也是如此。如果原则上有可能最终证明该模式的每个实例，那么在特定的技术意义上，即使证明本身很长，电感连贯的预测器也会开始“太久”就开始识别它。
“无限延迟的在线学习中的渐近融合,” which I co-authored with Garrabrant and Jessica Taylor, describes an algorithm with the second property. The abstract reads:
We study the problem of predicting the results of computations that are too expensive to run, via the observation of the results of smaller computations. We model this as an online learning problem with delayed feedback, where the length of the delay is unbounded, which we study mainly in a stochastic setting. We show that in this setting, consistency is not possible in general, and that optimal forecasters might not have average regret going to zero. However, it is still possible to give algorithms that converge asymptotically to Bayes-optimal predictions, by evaluating forecasters on specific sparse independent subsequences of their predictions. We give an algorithm that does this, which converges asymptotically on good behavior, and give very weak bounds on how long it takes to converge. We then relate our results back to the problem of predicting large computations in a deterministic setting.
第一个属性是关于识别有关主张之间逻辑关系的模式 - 说“主张A表示索赔B，因此我对B的可能性至少必须是我对A的可能性。”相比之下，第二个财产是关于认识类似主张之间的频率模式 - 说“我缺乏判断该主张是否正确的资源，但是类似索赔中有90％是正确的，因此基本利率为90％”（其中一部分部分问题是弄清楚什么是“类似的主张”）。
In this technical report, we model the latter task as an online learning problem, where a predictor observes the behavior of many small computations and has to predict the behavior of large computations. We give an algorithm that eventually assigns the “right” probabilities to every predictable subsequence of observations, in a specific technical sense.
Each paper is interesting in its own right, but for us, the exciting result is that we have teased apart and formalized two separate notions of what counts as “good reasoning” under logical uncertainty, both of which are compelling.
Furthermore, our approaches to formalizing these two notions are very different. “Inductive coherence” frames the problem in the traditional “unify logic with probability” setting, whereas “Asymptotic convergence in online learning with unbounded delays” fits more naturally into the online machine learning framework. The methods we found for solving the first problem don’t appear to help with the second problem, and vice versa. In fact, the two isolated solutions appear quite difficult to reconcile. The problem that these two papers leave open is: Can we get one algorithm that satisfies both properties at once?
注册以获取有关新的Miri技术结果的最新信息
每次发布新技术论文时，都会通知。
- This work was originally titled “Uniform coherence”. This post has been updated to reflect the new terminology.↩
- Garrabrant的IAFF论坛帖子提供了记录这些结果如何最初开发的，以回应Ray Solomonoff的算法概率理论。所罗门诺夫方法的混凝土故障andThe Entangled Benford Testlay groundwork for the “Asymptotic convergence…” problem, a limited early version of which was featured in the “Asymptotic logical uncertainty and the Benford test透明report. Inductive coherence is defined inUniform Coherence 2，以及在The Modified Demski Prior is Uniformly Coherent。↩
- This type of uncertainty is called “logical uncertainty” mainly for historical reasons. I think of it like this: We care about agents’ ability to reason about software systems, e.g., “this program will halt.” Those claims can be expressed in sentences of logic. The question “what probability does the agent assign to this machine halting?” then becomes “what probability does this agent assign to this particular logical sentence?” The truth of these statements could be determined in principle, but the agent may not have the resources to compute the answers in practice.↩
- 关于逻辑的更多背景不确定性,看到Gaifman’s “关于一阶微弦的度量，” Garber的“Old evidence and logical omniscience in Bayesian confirmation theory,” Hutter, Lloyd, Ng, and Uther’s “Probabilities on sentences in an expressive logic，”和亚伦森的“为什么哲学家应该关心计算复杂性。透明↩
