首个完全基于观测数据的马尔可夫链泛化界，无需预先知道数据生成过程。
Empirical PAC-Bayes Bounds for Markov Chains
- 用可实证的伪谱间隙替代依赖未知过程的混合系数
- 在有限状态空间下实现完全可计算的泛化界，模拟实验紧度接近理论值
- 适合关注非独立数据泛化理论的研究者，尤其机器学习中的序列建模
传统泛化理论主要针对独立观测。虽已有适用于具时间依赖性的数据的PAC和PAC-Bayes界，但其常数依赖于数据生成过程的性质，如混合系数、混合时间、谱隙等，实践中无法获知。本文提出一种新的马尔可夫链PAC-Bayes界，依赖于称为伪谱间隙的量。关键创新在于：当状态空间有限时，可对伪谱间隙给出经验上界。因此，我们首次获得完全经验的马尔可夫链PAC-Bayes界。该方法可拓展至无限情形，但需额外假设。在模拟实验中，经验版本的界几乎与非经验版本一样紧。
原文摘要 · Abstract (English)
The core of generalization theory was developed for independent observations. Some PAC and PAC-Bayes bounds are available for data that exhibit a temporal dependence. However, there are constants in these bounds that depend on properties of the data-generating process: mixing coefficients, mixing time, spectral gap... Such constants are unknown in practice. In this paper, we prove a new PAC-Bayes bound for Markov chains. This bound depends on a quantity called the pseudo-spectral gap. The main novelty is that we can provide an empirical bound on the pseudo-spectral gap when the state space is finite. Thus, we obtain the first fully empirical PAC-Bayes bound for Markov chains. This extends beyond the finite case, although this requires additional assumptions. On simulated experiments, the empirical version of the bound is essentially as tight as the non-empirical one.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。