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

Question

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

PAC 学习模型对计算(时间)复杂性有何看法。假设给学习算法更多的时间(比如更多的迭代)，误差和误差有限的概率如何变化

作为一种需要一小时训练的学习算法，在金融预测问题中没有实际用途。我需要随着算法时间的变化，性能如何变化，包括误差范围和误差有界的概率

Answer 1

PAC 模型只是告诉您需要多少数据才能以某种概率获得一定程度的错误。通过查看您使用的实际机器学习算法，这可以转化为对运行时间的影响。

例如，如果您的算法运行时间为 O(2^n)，并且 PAC 模型表示您需要 1000 个示例才能有 95% 的机会出现 0.05 的错误，并且需要 10,000 个示例才能出现 0.005 的错误，那么您就知道您应该预料到准确性的提高会大幅放缓。而 O(log n) 算法的相同 PAC 信息可能会引导您继续并获得较低的错误。

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

Suppose a Learning Algorithm is given more time(like more iterations) how the error and probability that error is limited changes

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