ComputationOfLearning

学习问题的计算复杂度

在PAC那一篇中，我们提到VC维只对样本复杂度有刻画，但没有对计算复杂度作描述。在这一篇中，我们探讨有效的可能近似正确的学习（Efficient PAC Learning），就是不仅可学习，而且能有效学习。换句话，我们尝试回答什么时候可以有效学习？什么时候可以有效优化？

其中的关键点是多项式运行时（polynomial runtime），这还是与样本数目有关。这个定义的真正要求是“polynomial in the size of the problem“。 因而，我们可以给出一个近似等同的定义：

达成有效学习是有条件的，达成恰当的有效学习（Proper efficient PAC learning）是很难的，限于通俗度的考量这里不做展开。