论文标题
重新审视异常定理
The Outlier Theorem Revisited
论文作者
论文摘要
离群值是与样本总体区分开的数据点。算法信息理论中的异常定理指出，给定可计算的采样方法，必须出现异常值。我们向异常定理提供了一个简单的证明，并具有指数级的改进界限。我们将离群定理扩展到千古动力学系统，这些动力系统可以保证以减少的措施击中越来越大的异常情况。我们展示了如何从随机的函数（即函数降低）中构造确定函数。我们还证明，所有具有较大均匀度量的Cantor空间的开放式集合都将具有简单的可计算成员或与停止序列的高相互信息。
An outlier is a datapoint that is set apart from a sample population. The outlier theorem in algorithmic information theory states that given a computable sampling method, outliers must appear. We present a simple proof to the outlier theorem, with exponentially improved bounds. We extend the outlier theorem to ergodic dynamical systems which are guaranteed to hit ever larger outlier states with diminishing measures. We show how to construct deterministic functions from random ones, i.e. function derandomization. We also prove that all open sets of the Cantor space with large uniform measure will either have a simple computable member or high mutual information with the halting sequence.
