成長関数

成長関数は、破砕係数または破砕数とも呼ばれ、関数の集合族またはクラスの豊かさを測定します。特に統計学習理論の文脈で使用され、統計学習法の特性を研究するために使用されます。「成長関数」という用語は、1968年の論文でVapnikとChervonenkisによって造られ、その多くの特性も証明されました。^[1]これは機械学習 の基本概念です。^{[2] [3]}

を集合族（集合の集合）と集合とします。それらの共通部分は次の集合族として定義されます。 ${\displaystyle H}$${\displaystyle C}$

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

に対するの交差サイズ（インデックスとも呼ばれる）は です。集合に要素がある場合、インデックスは最大 です。インデックスがちょうど 2 ^mの場合、集合はによって分割されていると言われます。これは、には のすべての部分集合が含まれるためです。つまり、 ${\displaystyle H}$${\displaystyle C}$${\displaystyle |H\cap C|}$${\displaystyle C_{m}}$${\displaystyle m}$${\displaystyle 2^{m}}$${\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|}$

同様に、を仮説クラス（二項関数の集合）とし、を要素とする集合とする。に対する制約は、から導出できる二項関数の集合である ：^{[3] ：45}${\displaystyle H}$${\displaystyle C}$${\displaystyle m}$${\displaystyle H}$${\displaystyle C}$${\displaystyle C}$${\displaystyle H}$

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

成長関数は、の大きさを関数として測定します。^{[3] : 49}${\displaystyle H_{C}}$${\displaystyle |C|}$

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

1.定義域は実数直線 です。集合族には、与えられた数から正の無限大までのすべての半直線（半直線）が含まれます。つまり、ある に対して の形のすべての集合が含まれます。任意の実数集合に対して、共通部分には、空集合、 の最大要素を含む集合、 の最大 2 つの要素を含む集合などの集合が含まれます。したがって、です。^{[1] : 例 1}に開いた半直線、閉じた半直線、またはその両方が含まれている かどうかに関係なく、同じことが当てはまります。${\displaystyle \mathbb {R} }$${\displaystyle H}$${\displaystyle \{x>x_{0}\mid x\in \mathbb {R} \}}$${\displaystyle x_{0}\in \mathbb {R} }$${\displaystyle C}$${\displaystyle m}$${\displaystyle H\cap C}$${\displaystyle m+1}$${\displaystyle C}$${\displaystyle C}$${\displaystyle \operatorname {成長} (H,m)=m+1}$${\displaystyle H}$

2.定義域は線分 である。集合族はすべての開集合を含む。任意の有限実数集合について、共通部分は のすべての可能な部分集合を含む。そのような部分集合が存在するので である。 ^{[1] : 例 2}${\displaystyle [0,1]}$${\displaystyle H}$${\displaystyle C}$${\displaystyle m}$${\displaystyle H\cap C}$${\displaystyle C}$${\displaystyle 2^{m}}$${\displaystyle \operatorname {Growth} (H,m)=2^{m}}$

3.定義域はユークリッド空間 である。集合族には、という形式の半空間がすべて含まれる。ここで は固定ベクトルである。次に であり、Comp はn 次元空間を m 個の超平面で分割した際の成分の数である。^{[1] : 例 3}${\displaystyle \mathbb {R} ^{n}}$${\displaystyle H}$${\displaystyle x\cdot \phi \geq 1}$${\displaystyle \phi }$${\displaystyle \operatorname {Growth} (H,m)=\operatorname {Comp} (n,m)}$

4.定義域は実数直線 です。集合族にはすべての実区間、つまり、ある に対して の形式のすべての集合が含まれます。任意の実数集合に対して、共通部分には 0 から の連続する要素までのすべての連続が含まれます。このような連続の数は なので、 となります。 ${\displaystyle \mathbb {R} }$${\displaystyle H}$${\displaystyle \{x\in [x_{0},x_{1}]|x\in \mathbb {R} \}}$${\displaystyle x_{0},x_{1}\in \mathbb {R} }$${\displaystyle C}$${\displaystyle m}$${\displaystyle H\cap C}$${\displaystyle m}$${\displaystyle C}$${\displaystyle {m+1 \choose 2}+1}$${\displaystyle \operatorname {Growth} (H,m)={m+1 \choose 2}+1}$

成長関数を興味深いものにする主な特性は、それが多項式または指数のいずれかであり、その中間がないことです。

以下は交差サイズの特性である: ^{[1] : Lem.1}

• ある大きさの集合とある数 に対して、-${\displaystyle C_{m}}$${\displaystyle m}$${\displaystyle n\leq m}$${\displaystyle |H\cap C_{m}|\geq \operatorname {Comp} (n,m)}$
• すると、となるサイズのサブセットが存在します。${\displaystyle C_{n}\subseteq C_{m}}$${\displaystyle n}$${\displaystyle |H\cap C_{n}|=2^{n}}$

これは成長関数の次の性質を意味します。^{[1] : Th.1} すべての家族には2つのケースがあります。 ${\displaystyle H}$

• 指数関数の場合も同様です。${\displaystyle \operatorname {Growth} (H,m)=2^{m}}$
• 多項式の場合 はによって主要化され、 はとなる最小の整数です。${\displaystyle \operatorname {Growth} (H,m)}$${\displaystyle \operatorname {Comp} (n,m)\leq m^{n}+1}$${\displaystyle n}$${\displaystyle \operatorname {Growth} (H,n)<2^{n}}$

任意の有限に対して: ${\displaystyle H}$

${\displaystyle \operatorname {Growth} (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次元は、次の 2 つのケースに従って定義されます。 ${\displaystyle H}$

• 多項式の場合、 =となる最大の整数。${\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次元のもう一つの関係は、ザウアー・シェラの補題によって与えられる：^{[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}$

この上限は厳密であり、すなわち、VC次元を持つものすべてに対して、次のものが存在する：^{[2] ：56}${\displaystyle m>d}$${\displaystyle H}$${\displaystyle d}$

${\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}$

確率測度が定義されている集合を とします。をのサブセットの族(= イベントの族) とします。 ${\displaystyle \Omega }$ ${\displaystyle \Pr }$${\displaystyle H}$${\displaystyle \Omega }$

の要素を含むセットを選択し、各要素が他の要素とは独立して（つまり、置換によって）確率測度 に従ってランダムに選択されるものとします。各イベント について、次の 2 つの量を比較します。 ${\displaystyle C_{m}}$${\displaystyle m}$${\displaystyle \Omega }$${\displaystyle P}$${\displaystyle h\in H}$

• におけるその相対頻度、すなわち、${\displaystyle C_{m}}$${\displaystyle |h\cap C_{m}|/m}$
• その確率。${\displaystyle \Pr[h]}$

差に関心があります。この差は次の上限を満たします。 ${\displaystyle D(h,C_{m}):={\big |}|h\cap C_{m}|/m-\Pr[h]{\big |}}$

${\displaystyle \Pr \left[\forall h\in H:D(h,C_{m})\leq {\sqrt {8(\ln \operatorname {Growth} (H,2m)+\ln(4/\delta )) \over m}}\right]~~~~>~~~~1-\delta }$

これは次と同等である: ^{[1] : Th.2}

${\displaystyle \Pr {\big [}\forall h\in H:D(h,C_{m})\leq \varepsilon {\big ]}~~~~>~~~~1-4\cdot \operatorname {Growth} (H,2m)\cdot \exp(-\varepsilon ^{2}\cdot m/8)}$

言葉で言えば、 内のすべてのイベントについて、相対頻度が確率に近くなる確率は、 の成長関数に依存する式によって下限が定められます。 ${\displaystyle H}$${\displaystyle H}$

このことから導かれる帰結は、成長関数が の多項式である場合（つまり、となるような関数が存在する場合）、上記の確率は のときに 1 に近づくということです。つまり、この族は確率 で一様収束します。 ${\displaystyle m}$${\displaystyle n}$${\displaystyle \operatorname {Growth} (H,m)\leq m^{n}+1}$${\displaystyle m\to \infty }$${\displaystyle H}$