A Limitation of the PAC-Bayes Framework
A Limitation of the PAC-Bayes Framework
复制标题
PAC-贝叶斯框架的局限性
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
S. Moran
中科院分区：
文献类型：
--
作者：
Roi Livni;S. Moran
PAC-Bayes是由McAllester(‘98)提出的一个用于导出泛化界的有用框架。该框架具有导出依赖于分布和算法的界的灵活性，这些界通常比VC相关的一致收敛界更紧密。在这篇手稿中，我们给出了PAC-Bayes框架的一个限制。我们展示了一个不适合于PAC-Bayes分析的简单的学习任务。
具体地说，我们考虑1D中的线性分类任务；众所周知，仅使用$O(\log(1/\Delta)/\epsilon)$示例即可学习此任务。另一方面，我们证明了这一事实不能用PAC-Bayes分析来证明：对于任何学习一维线性分类器的算法，都存在一个(可实现的)分布，其PAC-Bayes界是任意大的。
PAC-Bayes is a useful framework for deriving generalization bounds which was introduced by McAllester ('98). This framework has the flexibility of deriving distribution- and algorithm-dependent bounds, which are often tighter than VC-related uniform convergence bounds. In this manuscript we present a limitation for the PAC-Bayes framework. We demonstrate an easy learning task that is not amenable to a PAC-Bayes analysis.
Specifically, we consider the task of linear classification in 1D; it is well-known that this task is learnable using just $O(\log(1/\delta)/\epsilon)$ examples. On the other hand, we show that this fact can not be proved using a PAC-Bayes analysis: for any algorithm that learns 1-dimensional linear classifiers there exists a (realizable) distribution for which the PAC-Bayes bound is arbitrarily large.
影响因子：
4.1
作者：
Daker, Richard J.;Cortes, Robert A.;Green, Adam E.
通讯作者：
Green, Adam E.