第3章：复杂性分析

文档摘要

第3章：复杂性分析 Edit: 王茂霖，李一飞，詹好，赵志民本章前言在机器学习理论中，复杂性分析与计算理论中的算法复杂度类似，是衡量模型和假设空间能力的关键指标。复杂性越高，模型的表达能力越强，但同时也意味着过拟合的风险增加。因此，研究假设空间的复杂性有助于理解模型的泛化能力，并为模型选择和正则化提供理论依据。 3.1 【概念解释】VC维 VC维（Vapnik-Chervonenkis 维度）是衡量二元分类假设空间 $\mathcal{H}$ 复杂性的重要工具。它表示假设空间能够打散（shatter）的最大样本集的大小，是描述二元分类问题下假设空间复杂度的核心指标。