第2章：可学性

文档摘要

第2章：可学性编辑：赵志民，王茂霖，李一飞，詹好本章前言本章的内容围绕学习理论中的可学性理论展开，主要讨论「事件是否能够通过机器学习来解决」这一问题。通过学习理论事先辨别某个问题是否能够被学习，将节省大量的时间与资源。在讨论学习算法的设计之前，首先要思考以下几个问题：这个问题是否能被解决（从模型的角度看是否可学习），哪些内容容易学习（如两个凸集），哪些内容难学习（如两个非凸集之间的划分），在可学习的情况下，所需的样本量以及通用的学习模型有哪些？在本章中，我们将通过介绍 "概率近似正确的"（PAC）学习框架，开始正式讨论这些问题。PAC 框架有助于根据实现近似解所需的样本点数量、样本复杂度以及学习算法的时间/空间复杂度（取决于概念的计算表示成本）来定义可学习的概念。