基于PAC学习框架的计算学习理论

Question

考虑一个从训练集中训练的机器学习算法，在PAC学习模型的帮助下，我们得到了所需训练样本大小的界限，因此误差受到限制的概率(由epsilon)是有界的(由Δ)。

关于计算(时间)复杂性，PAC学习模型说了些什么。假设一个学习算法有更多的时间(比如更多的迭代)，那么误差和误差有限的概率是如何变化的

作为一种需要一小时训练的学习算法，在金融预测问题中没有实际意义。我需要的是性能如何随着算法时间的变化而变化，无论是在误差界和误差有界的概率方面。

Answer 1

PAC模型简单地告诉您需要多少条数据才能以一定的概率获得一定程度的错误。这可以通过查看您使用的实际机器学习算法来转换为对运行时的影响。

例如，如果你的算法在O(2^n)时间内运行，PAC模型说你需要1000个例子才有95%的.05错误和10,000个.005错误的机会，那么你就知道你应该预料到准确率的提高会有很大的减慢。然而，对于O(log )算法，相同的PAC信息可能会导致您继续前进，并获得较低的误差。

顺便说一句，听起来你可能对大多数监督学习算法的工作原理感到困惑：

假设一个学习算法被给予更多的时间(比如更多的迭代)，那么误差和误差有限的概率是如何变化的

在大多数情况下，你不能真的只是给相同的算法更多的时间和期望更好的结果，除非你随机选择参数(例如学习率)或增加例子的数量。也许你所谓的“迭代”指的是例子，在这种情况下，通过操纵用于PAC学习模型的方程系统，可以找到例子数量对概率和错误率的影响；请参阅维基article。