ヴァプニク – チェルボネンキス次元

ヴァプニク・チェルヴォネンキス理論において、ヴァプニク・チェルヴォネンキス（VC）次元は、集合のクラスのサイズ（容量、複雑さ、表現力、豊かさ、柔軟性）の尺度である。この概念は、バイナリ関数のクラスに拡張することができる。これは、アルゴリズムが破ることができる最大の点集合の濃度として定義され、つまり、アルゴリズムは常に、それらのデータポイントの少なくとも1つの構成の任意のラベル付けに対して完璧な分類器を学習できることを意味する。これはもともと、ウラジミール・ヴァプニクとアレクセイ・チェルヴォネンキスによって定義されました。^[1]

非公式には、分類モデルの容量は、それがどれだけ複雑になるかに関係しています。たとえば、高次多項式のしきい値設定を考えてみましょう。多項式がゼロより大きく評価された場合、その点は正として分類され、そうでない場合は負として分類されます。高次 多項式は波打つことができるため、特定のトレーニング ポイントのセットにうまく適合できます。ただし、波打つことが多すぎるため、分類器が他のポイントでエラーを起こすことが予想されます。このような多項式は容量が高くなります。はるかに単純な代替手段は、線形関数をしきい値設定することです。この関数は容量が低いため、トレーニング セットにうまく適合しない可能性があります。この容量の概念は、以下で厳密に説明します。

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

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

集合が によって分割されるとは、のすべての部分集合が含まれる場合を指します。つまり、 ${\displaystyle C}$${\displaystyle H}$${\displaystyle H\cap C}$${\displaystyle C}$

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

のVC次元 は、 によって分割される最大の集合の濃度です。 任意の大きさの集合を分割できる場合、 VC 次元は です。 ${\displaystyle D}$${\displaystyle H}$${\displaystyle H}$${\displaystyle \infty}$

あるパラメータベクトルを持つバイナリ分類モデルは、ラベルをそれらのポイントに割り当てるたびに、そのデータポイントのセットを評価するときにモデルがエラーを起こさないようなものが存在する場合、一般的な位置にあるデータポイントのセットを粉砕すると言われます^{[引用が必要]}。 ${\displaystyle f}$${\displaystyle \theta}$${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$${\displaystyle \theta}$${\displaystyle f}$

モデルの VC 次元は、 によって粉砕されるように配置できるポイントの最大数です。より正式には、によって粉砕できる基数の一般的な配置データ ポイント セットが存在するような最大の基数です。 ${\displaystyle f}$${\displaystyle f}$${\displaystyle D}$ ${\displaystyle D}$${\displaystyle f}$

1. ${\displaystyle f}$は定数分類器（パラメータなし）です。1 つのポイントも粉砕できないため、VC 次元は 0 です。一般に、最大で 個の異なる分類器を返すことができる有限分類モデルの VC 次元は最大で です（これは VC 次元の上限であり、Sauer-Shelah の補題は次元の下限を示します）。${\displaystyle 2^{d}}$${\displaystyle d}$
2. ${\displaystyle f}$は、実数に対する単一パラメータしきい値分類器です。つまり、特定のしきい値 に対して、分類器は入力数が より大きい場合に 1 を返し、それ以外の場合は 0 を返します。 の VC 次元 が 1 であるのは、次の理由によるものです。(a) 単一の点を粉砕できます。すべての点 について、分類器はの場合は 0 とラベル付けし、 の場合は 1 とラベル付けします。(b) 2 つの点を含むすべてのセットを粉砕できるわけではありません。2 つの数値のすべてのセットについて、小さい方に 1 のラベルが付けられている場合は、大きい方にも 1 のラベルが付けられる必要があるため、すべてのラベル付けが可能であるわけではありません。${\displaystyle \theta}$${\displaystyle f_{\theta}}$${\displaystyle \theta}$${\displaystyle f}$${\displaystyle x}$${\displaystyle f_{\theta}}$${\displaystyle \theta >x}$${\displaystyle \theta <x}$
3. ${\displaystyle f}$は、実数に対するシングル パラメータの区間分類器です。つまり、特定のパラメータ について、入力数が区間内にある場合は分類器は1 を返し、それ以外の場合は 0 を返します。 の VC 次元が 2 である理由は、(a) いくつかの 2 点集合を分解できるためです。たとえば、すべての集合 について、分類器は、または の場合は(0,0) 、 の場合は (1,0) 、 の場合は (1,1)、 の場合は(0,1) とラベル付けします。(b) 3 点集合は分解できません。すべての 3 点集合について、最小値と最大値に 1 のラベルが付けられている場合、中央の数値にも 1 のラベルが付けられる必要があるため、すべてのラベル付けが可能であるわけではありません。${\displaystyle \theta}$${\displaystyle f_{\theta}}$${\displaystyle [\theta ,\theta +4]}$${\displaystyle f}$${\displaystyle \{x,x+2\}}$${\displaystyle f_{\theta}}$${\displaystyle \theta <x-4}$${\displaystyle \theta >x+2}$${\displaystyle \theta \in [x-4,x-2)}$${\displaystyle \theta \in [x-2,x]}$${\displaystyle \theta \in (x,x+2]}$
4. ${\displaystyle f}$は、2 次元平面上の点の分類モデルとしての直線です(これは、パーセプトロンで使用されるモデルです)。この線は、正のデータ ポイントを負のデータ ポイントから分離する必要があります。このモデルを使用して、実際に分割できる 3 点の集合が存在します (同一直線上にない任意の 3 点を分割できます)。ただし、4 点の集合は分割できません。ラドンの定理により、任意の 4 点は交差する凸包を持つ 2 つのサブセットに分割できるため、これらの 2 つのサブセットのいずれかを他のサブセットから分離することはできません。したがって、この特定の分類器の VC 次元は 3 です。点の配置は自由に選択できますが、ラベル割り当てのために分割しようとすると、それらの点の配置は変更できないことを覚えておくことが重要です。3 つの点に対して、2 ³  = 8 通りの可能なラベル割り当てのうち 3 つだけが示されていることに注意してください。
5. ${\displaystyle f}$は単一パラメータ正弦分類器である。つまり、あるパラメータに対して、入力数が であれば分類器は1を返し、そうでなければ0を返す。 のVC次元は無限大である。なぜなら、 の有限部分集合を破壊できるからである。^{[2] : 57}${\displaystyle \theta}$${\displaystyle f_{\theta}}$${\displaystyle x}$${\displaystyle \sin(\theta x)>0}$${\displaystyle f}$${\displaystyle \{2^{-m}\mid m\in \mathbb {N} \}}$

VC次元は、分類モデルのテストエラーの確率的な 上限を予測することができます。Vapnik ^{[3]は、テストエラー（つまり、0-1損失関数のリスク）の確率が上限（トレーニングセットと同じ分布から}iidで抽出されたデータ上）からどれだけ離れているかが次のように表されることを証明しました。

${\displaystyle \Pr \left({\text{テスト誤差}}\leqslant {\text{トレーニング誤差}}+{\sqrt {{\frac {1}{N}}\left[D\left(\log \left({\tfrac {2N}{D}}\right)+1\right)-\log \left({\tfrac {\eta }{4}}\right)\right]}}\,\right)=1-\eta ,}$

ここで、は分類モデルの VC 次元、 はトレーニング セットのサイズです (制限: この式は のときに有効です。 が大きい場合、テスト エラーがトレーニング エラーよりもはるかに高くなる可能性があります。 これは、 の過剰適合によるものです)。 ${\displaystyle D}$${\displaystyle 0<\eta \leqslant 1}$${\displaystyle N}$${\displaystyle D\llN}$${\displaystyle D}$

VC次元はサンプル複雑度の境界にも現れる。VC次元を持つバイナリ関数の空間は次のように学習できる: ^{[4] : 73}${\displaystyle D}$

${\displaystyle N=\Theta \left({\frac {D+\ln {1 \over \delta }}{\varepsilon ^{2}}}\right)}$

サンプル、ここで は学習誤差、 は失敗確率です。したがって、サンプル複雑度は仮説空間の VC 次元の線形関数です。 ${\displaystyle \epsilon }$${\displaystyle \delta}$

VC 次元はε-ネットのサイズにおける重要なパラメータの 1 つであり、 VC 次元に基づく近似アルゴリズムの複雑さを決定します。有限の VC 次元を持たない範囲セットには有限の ε-ネットがまったく存在しない可能性があります。

0. の双対集合族の VC 次元はより小さく、これが最良です。${\displaystyle {\mathcal {F}}}$${\displaystyle 2^{\operatorname {vc} ({\mathcal {F}})+1}}$
1. 有限集合族のVC次元は最大でも である。^{[2] : 56}これは定義により となる。${\displaystyle H}$${\displaystyle \log_{2}|H|}$${\displaystyle |H\cap C|\leq |H|}$
2. 集合族 が与えられたとき、を の要素のすべての交差を含む集合族 として定義します。すると、次のようになります。^{[2] : 57}${\displaystyle H}$${\displaystyle H_{s}}$${\displaystyle s}$${\displaystyle H}$ $${\displaystyle \operatorname {VCDim} (H_{s})\leq \operatorname {VCDim} (H)\cdot (2s\log _{2}(3s))}$$
3. 集合族と要素が与えられたとき、対称集合差を表すを定義する。すると、次のようになる。^{[2] : 58}${\displaystyle H}$${\displaystyle h_{0}\in H}$${\displaystyle H\,\Delta h_{0}:=\{h\,\Delta h_{0}\mid h\in H\}}$${\displaystyle \Delta }$ $${\displaystyle \operatorname {VCDim} (H\,\Delta h_{0})=\operatorname {VCDim} (H)}$$

次数nの有限射影平面は、n ² + n + 1 個の要素 (「点」と呼ばれる) 上のn ² + n + 1 個の集合(「線」と呼ばれる) の集合であり、次のようになります。

• 各行には正確にn + 1 個の点が含まれます。
• 各線は他のすべての線と正確に 1 つの点で交差します。
• 各点は正確にn + 1 行に含まれます。
• 各点は、他のすべての点と正確に 1 本の線上に共通しています。
• 少なくとも 4 つの点が共通の直線上にありません。

有限射影平面のVC次元は2である。^[5]

証明: (a) 異なる点の各ペアについて、両方を含む直線、一方のみを含む直線、どちらも含まない直線が存在するため、サイズ 2 のセットはすべて分割されます。 (b) 異なる 3 点の 3 つ組について、3 つすべてを含む直線xが存在する場合、2 つだけを含む直線yは存在しません(その場合、xとy は2 つの点で交差することになり、射影平面の定義に反するため)。したがって、サイズ 3 のセットは分割されません。

VC 次元が である単純な分類子の基本クラスがあるとします。 ${\displaystyle B}$${\displaystyle D}$

からのいくつかの異なる分類器を組み合わせることで、より強力な分類器を構築できます。この手法はブースティングと呼ばれます。正式には、分類器と重みベクトルが与えられた場合、次の分類器を定義できます。 ${\displaystyle B}$${\displaystyle T}$${\displaystyle h_{1},\ldots ,h_{T}\in B}$${\displaystyle w\in \mathbb {R} ^{T}}$

${\displaystyle f(x)=\operatorname {sign} \left(\sum _{t=1}^{T}w_{t}\cdot h_{t}(x)\right)}$

（からの分類器のすべての選択と からの重みベクトルに対して）そのような分類器すべての集合のVC次元は、 と仮定すると、最大で次のようになる：^{[4] : 108–109}${\displaystyle T}$${\displaystyle B}$${\displaystyle \mathbb {R} ^{T}}$${\displaystyle T,D\geq 3}$

${\displaystyle T\cdot (D+1)\cdot (3\log(T\cdot (D+1))+2)}$

ニューラルネットワークは有向非巡回グラフ G ( V , E )で記述されます。ここで、

• V はノードの集合です。各ノードは単純な計算セルです。
• E はエッジの集合であり、各エッジには重みがあります。
• ネットワークへの入力は、グラフのソース、つまり入力エッジのないノードによって表されます。
• ネットワークの出力は、グラフのシンク、つまり出力エッジのないノードによって表されます。
• 各中間ノードは、入力として、その入力エッジにあるノードの出力の加重合計を受け取ります。ここで、重みはエッジの重みです。
• 各中間ノードは、符号関数やシグモイド関数など、入力の増加関数を出力します。この関数は活性化関数と呼ばれます。

ニューラルネットワークのVC次元は次のように制限される: ^{[4] : 234–235}

• 活性化関数が符号関数であり、重みが一般的な場合、VC 次元は最大で になります。${\displaystyle O(|E|\cdot \log(|E|))}$
• 活性化関数がシグモイド関数で重みが一般的な場合、VC 次元は少なくともで最大 になります。${\displaystyle \Omega (|E|^{2})}$${\displaystyle O(|E|^{2}\cdot |V|^{2})}$
• 重みが有限族から来ている場合（例えば、重みはコンピュータで最大 32 ビットで表現できる実数である）、両方の活性化関数について、VC 次元は最大 になります。${\displaystyle O(|E|)}$

VC 次元は、バイナリ関数 ({0,1} への関数) の空間に対して定義されます。非バイナリ関数の空間に対しては、いくつかの一般化が提案されています。

• 多クラス関数（例えば、{0,..., n-1 }への関数）の場合、ナタラジャン次元[ ^6]とその一般化であるDS次元^[7]を使用することができる。
• 実数値関数（例えば実区間[0,1]への関数）の場合、グラフ次元^[6]またはポラードの擬似次元^{[8] [9] [10]}を使用することができる。
• ラデマッハ複雑度はVCと同様の境界を提供し、カーネルを使用するような統計的手法に対してVC次元計算よりも多くの洞察を提供できる場合があります^{[引用が必要]}。
• メモリ容量 (メモリ等価容量と呼ばれることもあります) は、上限ではなく下限の容量を示します (例:人工ニューラル ネットワーク#容量を参照)。そのため、潜在的なオーバーフィッティングのポイントを示します。

ウィキメディア・コモンズには、ヴァプニク＝チェルヴォネンキス次元に関連するメディアがあります。

• 成長関数
• Sauer-Shelah の補題、VC 次元の観点から見た集合システム内の集合の数の上限。
• Karpinski–Macintyre の定理、^[11]一般的なパフィアン公式の VC 次元の限界。

• ムーア、アンドリュー。「VC ディメンション チュートリアル」(PDF)。
• Vapnik, Vladimir (2000)。統計学習理論の性質。Springer。
• Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Warmuth, MK (1989). 「学習可能性と Vapnik–Chervonenkis 次元」(PDF) . Journal of the ACM . 36 (4): 929–865. doi :10.1145/76359.76371. S2CID  1138467.
• Burges , Christopher. 「パターン認識のための SVM に関するチュートリアル」(PDF)。Microsoft 。（VCディメンションの情報も含む）
• チャゼル、バーナード。「不一致法」。
• Natarajan, BK (1989). 「集合と関数の学習について」.機械学習. 4 : 67–97. doi : 10.1007/BF00114804 .
• Ben-David, Shai; Cesa-Bianchi, Nicolò; Long, Philip M. (1992)。「{O, …, n } 値関数のクラスの学習可能性の特性」。計算学習理論に関する第 5 回年次ワークショップの議事録 - COLT '92。p. 333。doi : 10.1145 / 130385.130423。ISBN 089791497X。
• Brukhim, Nataly; Carmon, Daniel; Dinur, Irit; Moran, Shay; Yehudayoff, Amir (2022). 「マルチクラス学習可能性の特性評価」。2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)。arXiv : 2203.01550。
• ポラード、D. (1984)。確率過程の収束。シュプリンガー。ISBN 9781461252542。
• アンソニー、マーティン、バートレット、ピーターL. (2009)。ニューラルネットワーク学習: 理論的基礎。ISBN 9780521118620。
• Morgenstern , Jamie H.; Roughgarden, Tim (2015). ほぼ最適なオークションの疑似次元について。NIPS。arXiv : 1506.03684。Bibcode : 2015arXiv150603684M。
• Karpinski, Marek; Macintyre , Angus (1997 年 2 月)。「シグモイド型および一般 Pfaffian ニューラル ネットワークの VC 次元の多項式境界」。Journal of Computer and System Sciences。54 ( 1): 169–176。doi : 10.1006/ jcss.1997.1477。