We consider the fundamental question of learnability of a hypotheses class in the supervised learning setting and in the general learning setting introduced by Vladimir Vapnik. We survey classic results characterizing learnability in term of suitable notions of complexity, as well as more recent results that establish the connection between learnability and stability of a learning algorithm.
翻译:我们考虑了在弗拉基米尔·瓦普尼克的监督下学习环境和在弗拉基米尔·瓦普尼克提出的一般学习环境中,一个假设班的可学习性这一根本问题。 我们调查了典型的结果,从适当的复杂概念的角度来说明学习的可学习性,以及确定学习算法的可学习性和稳定性之间的联系的最新结果。