生长函数的定义

定义 3.6（生长函数）

• 对于一个假设集 $\mathcal{H}$，
• 生长函数 ${\Pi }_{\mathcal{H}}:\mathbb{N}\to \mathbb{N}$ 定义为： $\forall m\in \mathbb{N}$ {\Pi }_{\mathcal{H}}\left( m\right) := \mathop{\max }\limits_{{\left\{ {{x}_{1},\ldots ,{x}_{m}}\right\} \subseteq X}}\left| \left\{ {\left( {h\left( {x}_{1}\right) ,\ldots ,h\left( {x}_{m}\right) }\right) : h \in \mathcal{H}}\right\} \right| . \tag{3.19}

• 换句话说，${\Pi }_{\mathcal{H}}\left(m\right)$ 是使用 $\mathcal{H}$ 中的假设对 $m$ 个点进行分类的最大不同方式的数量。
  • 这些不同的分类方式称为 二分法，因此生长函数计算了由假设实现的二分法的数量。
  • 这提供了另一个衡量假设集 $\mathcal{H}$ 丰富程度的指标。
• 然而，与 Rademacher 复杂度不同，这一指标 不依赖于分布，它纯粹是组合性质的。