成長機能

させて${\displaystyle H}$集合族（集合の集合）であり、${\displaystyle C}$集合。それらの共通部分は、次の集合族として定義される。

${\displaystyle H\cap C:=\{h\cap C\mid h\in H\}}$

交差サイズ（インデックスとも呼ばれる）${\displaystyle H}$に関して${\displaystyle C}$は${\displaystyle |H\cap C|}$. セットの場合${\displaystyle C_{m}}$もっている${\displaystyle m}$要素の場合、インデックスは最大で$2m$インデックスがちょうど^2mの場合、セットは${\displaystyle C}$粉々に砕かれたと言われている${\displaystyle H}$、 なぜなら${\displaystyle H\cap C}$すべてのサブセットを含む${\displaystyle C}$つまり：

${\displaystyle |H\cap C|=2^{|C|},}$

成長関数は、${\displaystyle H\cap C}$関数として${\displaystyle |C|}$正式には：

${\displaystyle \operatorname {成長} (H,m):=\max _{C:|C|=m}|H\cap C|}$

同様に、${\displaystyle H}$仮説クラス（バイナリ関数の集合）であり、${\displaystyle C}$セット${\displaystyle m}$要素。制限${\displaystyle H}$に${\displaystyle C}$は、上のバイナリ関数の集合です。 ${\displaystyle C}$から導き出せる${\displaystyle H}$: ^{[ 3 ] : 45}

${\displaystyle H_{C}:=\{(h(x_{1}),\ldots ,h(x_{m}))\mid h\in H,x_{i}\in C\}}$

成長関数は、${\displaystyle H_{C}}$関数として${\displaystyle |C|}$: ^{[ 3 ] : 49}

${\displaystyle \operatorname {成長} (H,m):=\max _{C:|C|=m}|H_{C}|}$

任意の有限${\displaystyle H}$:

${\displaystyle \operatorname {成長} (H,m)\leq |H|}$

すべての${\displaystyle C}$要素の数${\displaystyle H\cap C}$最大で${\displaystyle |H|}$したがって、成長関数は主に次のような場合に興味深い。${\displaystyle H}$無限です。

空でない任意の${\displaystyle H}$:

${\displaystyle \operatorname {Growth} (H,m)\leq 2^{m}}$

つまり、成長関数には指数関数的な上限がある。

集合族は${\displaystyle H}$セットを打ち砕く${\displaystyle C}$それらの共通部分にすべての可能な部分集合が含まれる場合${\displaystyle C}$つまり${\displaystyle H\cap C=2^{C}}$。 もし${\displaystyle H}$粉々に砕ける${\displaystyle C}$サイズの${\displaystyle m}$、 それから${\displaystyle \operatorname {Growth} (H,C)=2^{m}}$これは上限値です。

2つの集合族のデカルト座標における交差を次のように定義する。

${\displaystyle H_{1}\bigotimes H_{2}:=\{h_{1}\cap h_{2}\mid h_{1}\in H_{1},h_{2}\in H_{2}\}}$。

そして：^{[ 2 ]： 57}

${\displaystyle \operatorname {Growth} (H_{1}\bigotimes H_{2},m)\leq \operatorname {Growth} (H_{1},m)\cdot \operatorname {Growth} (H_{2},m)}$

2つの集合族ごとに：^{[ 2 ]： 58}

${\displaystyle \operatorname {Growth} (H_{1}\cup H_{2},m)\leq \operatorname {Growth} (H_{1},m)+\operatorname {Growth} (H_{2},m)}$

VC次元​${\displaystyle H}$は、以下の2つのケースに基づいて定義されます。

• 多項式の場合、${\displaystyle \operatorname {VCDim} (H)=n-1}$= 最大の整数${\displaystyle d}$そのために${\displaystyle \operatorname {Growth} (H,d)=2^{d}}$。
• 指数関数的な場合${\displaystyle \operatorname {VCDim} (H)=\infty }$。

それで${\displaystyle \operatorname {VCDim} (H)\geq d}$条件付き条件${\displaystyle \operatorname {Growth} (H,d)=2^{d}}$。

成長関数は、VC次元の概念を洗練したものと考えることができます。VC次元は、${\displaystyle \operatorname {Growth} (H,d)}$等しいかそれ以下${\displaystyle 2^{d}}$成長関数は、${\displaystyle \operatorname {Growth} (H,m)}$関数として変化する${\displaystyle m}$。

成長関数とVC次元のもう1つの関係は、Sauer–Shelahの補題によって示される：^{[ 3 ]： 49}

もし${\displaystyle \operatorname {VCDim} (H)=d}$、 それから：

すべての人々のために${\displaystyle m}$:${\displaystyle \operatorname {Growth} (H,m)\leq \sum _{i=0}^{d}{m \choose i}}$

特に、

すべての人々のために${\displaystyle m>d+1}$:${\displaystyle \operatorname {Growth} (H,m)\leq (em/d)^{d}=O(m^{d})}$

したがって、VC次元が有限の場合、成長関数は多項式的に成長し、${\displaystyle m}$。

この上限はタイトである。すなわち、すべての${\displaystyle m>d}$存在する${\displaystyle H}$VC寸法付き${\displaystyle d}$したがって：^{[ 2 ]： 56}

${\displaystyle \operatorname {Growth} (H,m)=\sum _{i=0}^{d}{m \choose i}}$

成長関数は最大交差サイズに関係するが、エントロピーは平均交差サイズに関係する。 ^{[ 1 ]： 272-273}

${\displaystyle \operatorname {Entropy} (H,m)=E_{|C_{m}|=m}{\big [}\log _{2}(|H\cap C_{m}|){\big ]}}$

交差サイズには次の性質があります。すべての集合族に対して${\displaystyle H}$:

${\displaystyle |H\cap (C_{1}\cup C_{2})|\leq |H\cap C_{1}|\cdot |H\cap C_{2}|}$

したがって：

${\displaystyle \operatorname {Entropy} (H,m_{1}+m_{2})\leq \operatorname {Entropy} (H,m_{1})+\operatorname {Entropy} (H,m_{2})}$

さらに、シーケンス${\displaystyle \operatorname {Entropy} (H,m)/m}$定数に収束する${\displaystyle c\in [0,1]}$いつ${\displaystyle m\to \infty }$。

さらに、ランダム変数${\displaystyle \log _{2}{|H\cap C_{m}|/m}}$近くに集中している${\displaystyle c}$。