考虑一个从训练集训练的机器学习算法，在 PAC 学习模型的帮助下，我们获得了所需训练样本大小的界限，因此错误受限（通过 epsilon）的概率是有界的（通过 delta）。
PAC 学习模型对计算（时间）复杂性有何看法。假设一个学习算法有更多的时间（比如更多的迭代），错误和错误被限制的概率如何变化
作为一种需要一小时训练的学习算法，在金融预测问题中没有实际用途。我需要性能如何随着给定算法的时间变化而变化，包括误差范围和误差有界的概率是多少
问问题
313 次
1 回答
4
PAC 模型只是告诉您需要多少数据才能以一定的概率出现一定程度的错误。通过查看您使用的实际机器学习算法，这可以转化为对运行时间的影响。
例如，如果您的算法在 O(2^n) 时间内运行，并且 PAC 模型说您需要 1000 个示例才能有 95% 的机会出现 0.05 错误，而 10,000 个示例有 0.005 错误的机会，那么您知道您应该期望为提高准确性而大幅放缓。而 O(log n) 算法的相同 PAC 信息可能会导致您继续前进并获得较低的错误。
顺便说一句，听起来您可能对大多数监督学习算法的工作方式感到困惑：
假设一个学习算法有更多的时间（比如更多的迭代），错误和错误被限制的概率如何变化
在大多数情况下，你真的不能只给同一个算法更多的时间并期望得到更好的结果，除非你对参数（例如学习率）或增加示例的数量有机会。也许“迭代”是指示例，在这种情况下，可以通过操纵用于 PAC 学习模型的方程组来找到示例数量对可能和错误率的影响；见维基文章。
于 2011-06-29T22:33:34.603 回答