PAC 可学习性和 VC 维度的效用/意义是什么?

机器算法验证 机器学习 vc-维度 pac学习
2022-03-21 07:16:00

我一直在阅读 Shalev-Shwartz 和 Ben-David 的书《理解机器学习》,它在第一部分中介绍了 PAC 理论。虽然 PAC 可学习性理论对我来说确实非常优雅和非凡,但我并不是这样确定它对实际机器学习问题的影响。PAC 可学习性和 VC 维度的主要效用(或效用)是什么?

PAC 可学习性理论是否告诉我们假设类H在可以以高概率使测试误差变小的意义上,是经过精心选择的吗?换句话说,如果HPAC 是可学习的,那么我们就可以保证不会发生过拟合?那么,PAC 理论的主要价值是为选择假设类和训练集大小提供指导吗?此外,PAC 理论之所以引人注目,是因为上述断言在不知道学习任务的输入和输出字母表上的分布的情况下成立?

我是机器学习的新手。我很感激任何可以帮助我了解 PAC 理论如何帮助解决实际机器学习问题的更正/评论/答案。

1个回答

我不确定这个答案是否解决了你上面的所有问题,但这是我回答你关于为什么 PAC 可学习性在 ML 中有用的主要问题的机会:

假设您有一个属于某些假设空间 H 的假设 h。您想找出您的假设需要多少训练示例才能学习到某个最低性能水平。样本复杂性(学习者学习某些最低性能所需的训练示例数量)由 PAC 可学习性驱动。基本上,我们希望 h 近似正确(错误目标使得错误概率 (epsilon) 有界:0<= epsion <= 1/2)并且我们还希望确保 h 在大多数情况下都是正确的时间(确定性目标,使得确定性概率(delta)至少在某个指定范围内:0<=delta<=1/2)。我们希望在多项式时间内完成所有这些。当然,PAC 可学习性取决于样本大小和维度。