论文标题
在有限设置中PAC学习样本复杂性的样本复杂性的可决定性
Decidability of Sample Complexity of PAC Learning in finite setting
论文作者
论文摘要
在此简短的说明中，我们观察到，当考虑到模型满足A-Priori结合的概率措施时，可以精确确定各种概念的PAC机器学习的样本复杂性，包括学习最大值（EMX）。该结果与ZFC中最近发现的EMX在有限支持的概率（没有先验结合的情况下）的不可证明的形成对比。不幸的是，目前的决策过程至少在统一限制在支撑大小的范围的次数次数中至少达到了指数。
In this short note we observe that the sample complexity of PAC machine learning of various concepts, including learning the maximum (EMX), can be exactly determined when the support of the probability measures considered as models satisfies an a-priori bound. This result contrasts with the recently discovered undecidability of EMX within ZFC for finitely supported probabilities (with no a priori bound). Unfortunately, the decision procedure is at present, at least doubly exponential in the number of points times the uniform bound on the support size.
