基于PAC-learning框架的计算学习理论
考虑一种从训练集进行训练的机器学习算法，在 PAC 学习模型的帮助下，我们得到了所需训练样本大小的界限，因此误差受限的概率（通过 epsilon）是有界的（通过 delta）。
PAC 学习模型对计算（时间）复杂性有何看法。 假设给一个学习算法更多的时间（比如更多的迭代），误差和误差有限的概率会如何变化，
因为需要一小时训练的学习算法在金融预测问题中没有实际用途。我需要随着算法时间的变化，性能如何变化，包括误差范围和误差有界的概率是多少
Consider a Machine Learning Algorithm which train from a training set, with the help of PAC learning model we get bounds on training sample size needed so the probability that error is limited(by epsilon) is bounded(by delta).
What does PAC learning model say about computational(time) complexity.
Suppose a Learning Algorithm is given more time(like more iterations) how the error and probability that error is limited changes
As an learning algorithm which takes one hour to train is of no practical use in financial prediction problems. I need how the performance changes as time given to algorithm changes both in terms of error bounds and what is the probability that error is bounded
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
PAC 模型只是告诉您需要多少数据才能以某种概率获得一定程度的错误。通过查看您使用的实际机器学习算法，这可以转化为对运行时间的影响。
例如，如果您的算法运行时间为 O(2^n)，并且 PAC 模型表示您需要 1000 个示例才能有 95% 的机会出现 0.05 的错误，需要 10,000 个示例才能出现 0.005 的错误，那么您知道您应该期望准确性的提高会大幅减慢。而 O(log n) 算法的相同 PAC 信息可能会引导您继续并获得较低的错误。
顺便说一句，听起来您可能对大多数监督学习算法的工作原理感到困惑：
在大多数情况下，你不能真的只是给相同的算法更多的时间并期望更好的结果，除非你机会参数（例如学习率）或增加示例数量。也许你所说的“迭代”指的是示例，在这种情况下，可以通过操纵用于 PAC 学习模型的方程组来找到示例数量对可能性和错误率的影响；请参阅 wiki 文章。
The PAC model simply tells you how many pieces of data you need to get a certain level of error with some probability. This can be translated into the impact on the run time by looking at the actual machine learning algorithm your using.
For example, if your algorithm runs in time O(2^n), and the PAC model says you need 1000 examples to have a 95% chance of having .05 error and 10,000 example for .005 error, then you know you should expect a HUGE slowdown for the increased accuracy. Whereas the same PAC information for a O(log n) algorithm would probably lead you to go ahead and get the lower error.
On a side note, it sounds like you might be confused about how most supervised learning algorithms work:
In most cases you can't really just give the same algorithm more time and expect better results, unless you chance the parameters (e.g. learning rate) or increase the number of examples. Perhaps by 'iterations' you meant examples, in which case the impact of the number of examples on the probably and error rate can be found by manipulating the system of equations used for the PAC learning model; see the wiki article.