Jun, 2022

Solomonoff 预测的困境

PDF
TL;DRSolomonoff 预测的框架将先验概率指派到假设上，这些假设与其 Kolmogorov 复杂度成反比。然而，Solomonoff 先验相对于通用图灵机的选择是有问题的，同时，Solomonoff 先验也是不可计算的。不过，对这两个问题有回应。同样的 Solomonoff 先验会随着越来越多的数据收敛。此外，对于 Solomonoff 先验也有可计算的近似值，但是作者认为在这两类问题的回应之间存在着紧张关系，因为可计算的 Solomonoff 预测近似并不总是能收敛。
solomonoff predictionprior probabilitykolmogorov complexityuniversal turing machinecomputable approximations
发现论文，激发创造
  • 算法信息论的电路复杂度表述

    研究基于电路复杂度的先验模型，并使用它们来学习部分信息中的布尔函数。该模型假设，布尔函数或布尔字符串由一些电路的贝叶斯混合生成。在电路复杂度方面表现良好。

    Jun, 2023

  • 关于通用预测和贝叶斯确认

    通过 Solomonoff 的模型来解决贝叶斯框架的一些问题，该模型拥有众多优势，包括强的总体和弱瞬时界限，可证明它是不可知、再参数化和重新组合不变的。

    Sep, 2007

  • 不良通用先验和最优性概念

    讨论了算法信息论中普适图灵机的选择对于 AIXI 的影响，研究结果表明，没有普遍不变定理。各种不幸或者对抗性的选择 UTM 的情况都会极大地干扰 AIXI 的行为，这意味着 AIXI 是一种相对论，完全取决于 UTM 的选择。

    Oct, 2015

  • 无免费午餐定理，科尔莫戈洛夫复杂度，以及归纳偏见在机器学习中的作用

    本文研究了在监督学习中 “没有免费午餐定理” 的适用性，进一步证明了神经网络在数据压缩和处理上也有低复杂性的偏好，从而证明了深度学习中统一问题的趋势。

    Apr, 2023

  • 关于条件概率的可计算性

    研究概率论基础中的条件概率可计算性，并证明了存在无法计算的条件概率分布，从而排除了概率推断的通用算法存在的可能性，但在许多常见建模情况下仍然可以进行概率推断。

    May, 2010

  • 监督学习中的无免费午餐和奥卡姆剃刀原则

    应用算法信息理论证明普适偏好是成功算法的关键，提出以索洛蒙诺夫归纳为灵感的新离线分类算法，证明随机选择训练数据可有效降低误分类率。

    Nov, 2011

  • 通过重播组合问题的解来学习蒙特卡洛搜索的先验知识

    蒙特卡罗搜索在多个困难的组合问题中表现出色。使用先验值执行非均匀放样比均匀放样获得更好的结果。通常使用针对组合问题定制的手工启发式算法作为先验值。我们提出了一种通过统计已解决问题来自动计算先验值的方法。这是一种简单而通用的方法，在放样时不会增加计算成本，而且可以带来很大的性能改进。该方法应用于三个困难的组合问题： 拉丁方阵的完成、Kakuro 和反向 RNA 折叠。

    Jan, 2024

  • 深度学习模型的描述长度

    通过实验证明，即使考虑到参数编码，深度神经网络仍能够压缩训练数据，而这种压缩视角最初激励了神经网络中变分方法的使用。我们发现，这些变分方法提供了惊人的较差压缩界限，这可能解释了变分方法在深度学习中相对较差的实际性能。另一方面，简单的增量编码方法在深度网络上产生了出色的压缩效果，从而证明了 Solomonoff 的方法。

    Feb, 2018

  • 优化器的可计算性

    分析了在图灵机和数字计算机上求解最优化问题的基本局限性，并在各种不同领域中证明了这些问题都不是 Banach-Mazur 可计算的。

    Jan, 2023

  • 复杂高维模型的贝叶斯分析：可以使用 CODA 吗？

    本研究考虑针对复杂的高维模型的贝叶斯分析，并表明直觉上的先验分布选择对模型和参数的微小细节不加区分，导致在某些情况下表现较差，而简单的频率学派估计量存在良好的表现。

    Mar, 2012