ヴァプニク・チェルヴォネンキス理論

Branch of statistical computational learning theory

ヴァプニク・チェルヴォネンキス理論（ VC理論とも呼ばれる）は、1960年から1990年にかけてウラジミール・ヴァプニクとアレクセイ・チェルヴォネンキスによって提唱された。この理論は計算学習理論の一種であり、学習プロセスを統計的観点から説明しようとするものである。

導入

VC理論は少なくとも4つの部分をカバーしています（統計学習理論の性質^[1]で説明されているように）。

• 学習プロセスの一貫性理論
  • 経験的リスク最小化原則に基づく学習プロセスの一貫性のための（必要かつ十分な）条件は何ですか？
• 学習過程の収束速度の非漸近理論
  • 学習プロセスの収束速度はどれくらい速いでしょうか?
• 学習プロセスの一般化能力を制御する理論
  • 学習プロセスの収束率（一般化能力）をどのように制御できるでしょうか?
• 学習機械の構築理論
  • 一般化能力を制御できるアルゴリズムをどのように構築すればよいでしょうか?

VC理論は統計学習理論の主要なサブブランチです。統計学習理論におけるその主要な応用の一つは、学習アルゴリズムの一般化条件を提供することです。この観点から、VC理論は一般化を特徴付けるための代替アプローチである安定性と関連しています。

さらに、VC理論とVC次元は、VCクラスでインデックス付けされたプロセスの場合、経験的プロセス理論において重要な役割を果たします。これらはVC理論の最も重要な応用と言えるでしょう。また、一般化を証明する際にも用いられます。経験的プロセスとVC理論で広く用いられているいくつかの手法を紹介します。本稿の議論は主に『弱収束と経験的プロセス：統計への応用』^[2]に基づいています。

経験的プロセスにおけるVC理論の概要

経験的プロセスの背景

を可測空間とする。上の任意の測度と任意の可測関数 に対して、を定義する。 ${\displaystyle ({\mathcal {X}},{\mathcal {A}})}$ ${\displaystyle Q}$ ${\displaystyle ({\mathcal {X}},{\mathcal {A}})}$ ${\displaystyle f:{\mathcal {X}}\to \mathbf {R} }$

${\displaystyle Qf=\int fdQ}$

測定可能性の問題はここでは無視します。より技術的な詳細については^[1]を参照してください。測定可能な関数のクラスを次のように定義します。 ${\displaystyle {\mathcal {F}}}$ ${\displaystyle f:{\mathcal {X}}\to \mathbf {R} }$

${\displaystyle \|Q\|_{\mathcal {F}}=\sup\{\vert Qf\vert \ :\ f\in {\mathcal {F}}\}.}$

を の独立かつ同一分布に従う乱数要素とする。そして経験的測度を定義する。 ${\displaystyle X_{1},\ldots ,X_{n}}$ ${\displaystyle ({\mathcal {X}},{\mathcal {A}})}$

${\displaystyle \mathbb {P} _{n}=n^{-1}\sum _{i=1}^{n}\delta _{X_{i}},}$

ここでδはディラック測度を表す。経験的測度は次式で表される写像を導く。 ${\displaystyle {\mathcal {F}}\to \mathbf {R} }$

${\displaystyle f\mapsto \mathbb {P} _{n}f={\frac {1}{n}}(f(X_{1})+...+f(X_{n}))}$

ここで、P がデータの真の分布であると仮定します。これは未知です。経験的プロセス理論は、次のような命題が成り立つクラスを特定することを目的としています。 ${\displaystyle {\mathcal {F}}}$

• 大数の均一法則：

  ${\displaystyle \|\mathbb {P} _{n}-P\|_{\mathcal {F}}{\underset {n}{\to }}0,}$

つまり、 ${\displaystyle n\to \infty }$

${\displaystyle \left|{\frac {1}{n}}(f(X_{1})+...+f(X_{n}))-\int fdP\right|\to 0}$

すべてに対して均一に。 ${\displaystyle f\in {\mathcal {F}}}$

• 均一中心極限定理：

${\displaystyle \mathbb {G} _{n}={\sqrt {n}}(\mathbb {P} _{n}-P)\rightsquigarrow \mathbb {G} ,\quad {\text{in }}\ell ^{\infty }({\mathcal {F}})}$

前者の場合、グリヴェンコ・カンテリ類と呼ばれ、後者の場合（仮定）はドンスカー類またはP-ドンスカー類と呼ばれる。ドンスカー類は、スルツキーの定理を適用することにより、確率的にグリヴェンコ・カンテリ類となる。 ${\displaystyle {\mathcal {F}}}$ ${\displaystyle \forall x,\sup \nolimits _{f\in {\mathcal {F}}}\vert f(x)-Pf\vert <\infty }$ ${\displaystyle {\mathcal {F}}}$

これらの命題は、標準的なLLN、正則性条件下のCLTの議論によれば、単一の に対して真であり、経験的過程における難しさは、すべての に対して共同命題が立てられていることに起因する。したがって、直感的に、集合は大きすぎることはあり得ず、 の幾何学が非常に重要な役割を果たすことがわかる。 ${\displaystyle f}$ ${\displaystyle f\in {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$

関数集合の大きさを測る一つの方法は、いわゆる被覆数を使うことである。被覆数とは ${\displaystyle {\mathcal {F}}}$

${\displaystyle N(\varepsilon ,{\mathcal {F}},\|\cdot \|)}$

は、集合を覆うのに必要なボールの最小数です（ここでは、明らかに に基礎ノルムが存在すると仮定しています）。エントロピーは、被覆数の対数です。 ${\displaystyle \{g:\|g-f\|<\varepsilon \}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {F}}}$

以下に、集合がGlivenko–Cantelli 集合または Donsker 集合であることを証明するための十分な条件が 2 つ示されています。 ${\displaystyle {\mathcal {F}}}$

クラスがP -グリヴェンコ–カンテリであるとは、包絡線Fに対してP -可測であり、次を満たす場合である。 ${\displaystyle {\mathcal {F}}}$ ${\displaystyle P^{\ast }F<\infty }$

${\displaystyle \forall \varepsilon >0\quad \sup \nolimits _{Q}N(\varepsilon \|F\|_{Q},{\mathcal {F}},L_{1}(Q))<\infty .}$

次の条件は、有名なダドリーの定理の一種である。が関数のクラスであり、 ${\displaystyle {\mathcal {F}}}$

${\displaystyle \int _{0}^{\infty }\sup \nolimits _{Q}{\sqrt {\log N\left(\varepsilon \|F\|_{Q,2},{\mathcal {F}},L_{2}(Q)\right)}}d\varepsilon <\infty }$

となる任意の確率測度Pに対してP-ドンスカーとなる。最後の積分において、表記は ${\displaystyle {\mathcal {F}}}$ ${\displaystyle P^{\ast }F^{2}<\infty }$

${\displaystyle \|f\|_{Q,2}=\left(\int |f|^{2}dQ\right)^{\frac {1}{2}}}$。

対称化

経験的過程をどのように制限するかについての議論の大部分は、対称化、最大不等式と集中不等式、そして連鎖に依存しています。対称化は通常、証明の最初のステップであり、多くの機械学習における経験的損失関数の制限に関する証明（次のセクションで議論するVC不等式の証明を含む）で使用されているため、ここでは対称化について示します。

経験的なプロセスを考えてみましょう。

${\displaystyle f\mapsto (\mathbb {P} _{n}-P)f={\dfrac {1}{n}}\sum _{i=1}^{n}(f(X_{i})-Pf)}$

経験的なプロセスと次の対称化されたプロセスの間には関連があることがわかります。

${\displaystyle f\mapsto \mathbb {P} _{n}^{0}f={\dfrac {1}{n}}\sum _{i=1}^{n}\varepsilon _{i}f(X_{i})}$

対称化された過程は、データ の条件付きで、ラーデマッハ過程である。したがって、ヘフディングの不等式より、これは劣ガウス過程である。 ${\displaystyle X_{i}}$

補題（対称化）。任意の非減少凸Φ: R → Rと測定可能な関数のクラスに対して、 ${\displaystyle {\mathcal {F}}}$

${\displaystyle \mathbb {E} \Phi (\|\mathbb {P} _{n}-P\|_{\mathcal {F}})\leq \mathbb {E} \Phi \left(2\left\|\mathbb {P} _{n}^{0}\right\|_{\mathcal {F}}\right)}$

対称化補題の証明は、元の変数の独立したコピー（ゴーストサンプルと呼ばれることもある）を導入し、左辺の内部期待値をこれらのコピーで置き換えることに依存する。イェンセンの不等式を適用することで、期待値を変えることなく異なる符号を導入することができる（そのため対称化と呼ばれる）。証明は教育的な性質を持つため、以下に示す。同じ証明方法は、グリヴェンコ・カンテリ定理の証明にも使用できる。^[3] ${\displaystyle X_{i}}$

証拠

の独立したコピーとして「ゴーストサンプル」を導入する。 の値が固定されている場合、は次式を持つ。 ${\displaystyle Y_{1},\ldots ,Y_{n}}$ ${\displaystyle X_{1},\ldots ,X_{n}}$ ${\displaystyle X_{1},\ldots ,X_{n}}$

${\displaystyle \|\mathbb {P} _{n}-P\|_{\mathcal {F}}=\sup _{f\in {\mathcal {F}}}{\dfrac {1}{n}}\left|\sum _{i=1}^{n}f(X_{i})-\mathbb {E} f(Y_{i})\right|\leq \mathbb {E} _{Y}\sup _{f\in {\mathcal {F}}}{\dfrac {1}{n}}\left|\sum _{i=1}^{n}f(X_{i})-f(Y_{i})\right|}$

したがって、ジェンセンの不等式により、

${\displaystyle \Phi (\|\mathbb {P} _{n}-P\|_{\mathcal {F}})\leq \mathbb {E} _{Y}\Phi \left(\left\|{\dfrac {1}{n}}\sum _{i=1}^{n}f(X_{i})-f(Y_{i})\right\|_{\mathcal {F}}\right)}$

に対する期待値を取ると次のようになります。 ${\displaystyle X}$

${\displaystyle \mathbb {E} \Phi (\|\mathbb {P} _{n}-P\|_{\mathcal {F}})\leq \mathbb {E} _{X}\mathbb {E} _{Y}\Phi \left(\left\|{\dfrac {1}{n}}\sum _{i=1}^{n}f(X_{i})-f(Y_{i})\right\|_{\mathcal {F}}\right)}$

項の前にマイナス記号を付けても右辺は変化しないことに注意してください。これは と の対称関数だからです。したがって、「符号摂動」の下でも右辺は変化しません。 ${\displaystyle f(X_{i})-f(Y_{i})}$ ${\displaystyle X}$ ${\displaystyle Y}$

${\displaystyle \mathbb {E} \Phi \left(\left\|{\dfrac {1}{n}}\sum _{i=1}^{n}e_{i}\left(f(X_{i})-f(Y_{i})\right)\right\|_{\mathcal {F}}\right)}$

任意の について。したがって、 ${\displaystyle (e_{1},e_{2},\ldots ,e_{n})\in \{-1,1\}^{n}}$

${\displaystyle \mathbb {E} \Phi (\|\mathbb {P} _{n}-P\|_{\mathcal {F}})\leq \mathbb {E} _{\varepsilon }\mathbb {E} \Phi \left(\left\|{\dfrac {1}{n}}\sum _{i=1}^{n}\varepsilon _{i}\left(f(X_{i})-f(Y_{i})\right)\right\|_{\mathcal {F}}\right)}$

最後に、まず三角不等式を使用し、次に凸性を使用すると次のようになります。 ${\displaystyle \Phi }$

${\displaystyle \mathbb {E} \Phi (\|\mathbb {P} _{n}-P\|_{\mathcal {F}})\leq {\dfrac {1}{2}}\mathbb {E} _{\varepsilon }\mathbb {E} \Phi \left(2\left\|{\dfrac {1}{n}}\sum _{i=1}^{n}\varepsilon _{i}f(X_{i})\right\|_{\mathcal {F}}\right)+{\dfrac {1}{2}}\mathbb {E} _{\varepsilon }\mathbb {E} \Phi \left(2\left\|{\dfrac {1}{n}}\sum _{i=1}^{n}\varepsilon _{i}f(Y_{i})\right\|_{\mathcal {F}}\right)}$

ここで、右辺の最後の 2 つの式は同じであり、これで証明は完了です。

経験的 CLT を証明する一般的な方法は、最初に対称化を使用して経験的プロセスを渡し、次にラーデマッハ プロセスが優れた特性を持つ単純なプロセスであるという事実を使用して、データに対して条件付きで議論することです。 ${\displaystyle \mathbb {P} _{n}^{0}}$

VC接続

集合の特定の組み合わせ的性質とエントロピー数の間には、興味深い関連性があることが判明しました。一様被覆数は、ヴァプニク・チェルヴォネンキス集合類、あるいは略してVC集合という概念によって制御できます。 ${\displaystyle {\mathcal {F}}}$

標本空間 の部分集合の集合を考えます 。が有限集合 の特定の部分集合を取り出すとは、ある に対して が成り立つ場合です。が S の2 ⁿ個の部分集合のそれぞれを取り出す場合、 がSを破砕するといいます。 のVC インデックス（適切に選択された分類器集合のVC 次元+ 1に相当）は、サイズnの集合が によって破砕されない最小のnです。 ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle W}$ ${\displaystyle S=\{x_{1},\ldots ,x_{n}\}\subset {\mathcal {X}}}$ ${\displaystyle W=S\cap C}$ ${\displaystyle C\in {\mathcal {C}}}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle V({\mathcal {C}})}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {C}}}$

ザウアーの補題によれば、 VC クラスによって選択されたサブセットの数は次式を満たす。 ${\displaystyle \Delta _{n}({\mathcal {C}},x_{1},\ldots ,x_{n})}$ ${\displaystyle {\mathcal {C}}}$

${\displaystyle \max _{x_{1},\ldots ,x_{n}}\Delta _{n}({\mathcal {C}},x_{1},\ldots ,x_{n})\leq \sum _{j=0}^{V({\mathcal {C}})-1}{n \choose j}\leq \left({\frac {ne}{V({\mathcal {C}})-1}}\right)^{V({\mathcal {C}})-1}}$

これは指数関数ではなく、部分集合の多項式数です。直感的に言えば、有限のVCインデックスは、一見単純な構造を持つことを意味します。 ${\displaystyle O(n^{V({\mathcal {C}})-1})}$ ${\displaystyle {\mathcal {C}}}$

同様の境界は、いわゆるVCサブグラフクラスに対しても（異なる定数、同じレートで）示されます。関数 に対して、サブグラフはのサブセットであり、次のようになります。 の集合は、すべてのサブグラフがVCクラスを形成する場合、VCサブグラフクラスと呼ばれます。 ${\displaystyle f:{\mathcal {X}}\to \mathbf {R} }$ ${\displaystyle {\mathcal {X}}\times \mathbf {R} }$ ${\displaystyle \{(x,t):t<f(x)\}}$ ${\displaystyle {\mathcal {F}}}$

離散経験的測度Q（あるいは任意の確率測度Q ）に対する指示関数の集合を考える。すると、驚くべきことに、 に対して次のことが示される。 ${\displaystyle {\mathcal {I}}_{\mathcal {C}}=\{1_{C}:C\in {\mathcal {C}}\}}$ ${\displaystyle L_{1}(Q)}$ ${\displaystyle r\geq 1}$

${\displaystyle N(\varepsilon ,{\mathcal {I}}_{\mathcal {C}},L_{r}(Q))\leq KV({\mathcal {C}})(4e)^{V({\mathcal {C}})}\varepsilon ^{-r(V({\mathcal {C}})-1)}}$

さらに、集合 の対称凸包を考えてみましょう。これはの形の関数の集合です。このとき、 ${\displaystyle {\mathcal {F}}}$ ${\displaystyle \operatorname {sconv} {\mathcal {F}}}$ ${\displaystyle \sum _{i=1}^{m}\alpha _{i}f_{i}}$ ${\displaystyle \sum _{i=1}^{m}|\alpha _{i}|\leq 1}$

${\displaystyle N\left(\varepsilon \|F\|_{Q,2},{\mathcal {F}},L_{2}(Q)\right)\leq C\varepsilon ^{-V}}$

の凸包に対して次が成り立ちます。 ${\displaystyle {\mathcal {F}}}$

${\displaystyle \log N\left(\varepsilon \|F\|_{Q,2},\operatorname {sconv} {\mathcal {F}},L_{2}(Q)\right)\leq K\varepsilon ^{-{\frac {2V}{V+2}}}}$

この事実の重要な帰結は、

${\displaystyle {\frac {2V}{V+2}}<2,}$

これはエントロピー積分が収束するのにちょうど十分であり、したがってクラスはP -Donskerになります。 ${\displaystyle \operatorname {sconv} {\mathcal {F}}}$

最後に、VC-部分グラフクラスの例を考察する。測定可能な関数の有限次元ベクトル空間は、指数が 以下である VC-部分グラフである。 ${\displaystyle {\mathcal {F}}}$ ${\displaystyle f:{\mathcal {X}}\to \mathbf {R} }$ ${\displaystyle \dim({\mathcal {F}})+2}$

証明:点を取る。ベクトル: ${\displaystyle n=\dim({\mathcal {F}})+2}$ ${\displaystyle (x_{1},t_{1}),\ldots ,(x_{n},t_{n})}$

${\displaystyle (f(x_{1}),\ldots ,f(x_{n}))-(t_{1},\ldots ,t_{n})}$

はR ⁿのn − 1次元部分空間に存在する。この部分空間に直交するベクトルをa ≠ 0とする。したがって、

${\displaystyle \sum _{a_{i}>0}a_{i}(f(x_{i})-t_{i})=\sum _{a_{i}<0}(-a_{i})(f(x_{i})-t_{i}),\quad \forall f\in {\mathcal {F}}}$

集合 を考えてみましょう。この集合 は、 が存在する場合、左辺が正であるが右辺が非正であることを意味するため、選択できません。 ${\displaystyle S=\{(x_{i},t_{i}):a_{i}>0\}}$ ${\displaystyle f}$ ${\displaystyle S=\{(x_{i},t_{i}):f(x_{i})>t_{i}\}}$

VCサブグラフクラスの概念には一般化があり、例えば擬似次元の概念がある。^[4]

VC不平等

機械学習でより一般的な、同様の設定について考察する。 を特徴空間とし、 とする。関数は分類器と呼ばれる。 を分類器の集合とする。前のセクションと同様に、破砕係数（成長関数とも呼ばれる）を定義する。 ${\displaystyle {\mathcal {X}}}$ ${\displaystyle {\mathcal {Y}}=\{0,1\}}$ ${\displaystyle f:{\mathcal {X}}\to {\mathcal {Y}}}$ ${\displaystyle {\mathcal {F}}}$

${\displaystyle S({\mathcal {F}},n)=\max _{x_{1},\ldots ,x_{n}}|\{(f(x_{1}),\ldots ,f(x_{n})),f\in {\mathcal {F}}\}|}$

ここで、関数のそれぞれと、関数が1である集合との間には1:1の対応関係があることに注意する。したがって、任意の に対して上記の写像から得られる部分集合の集合を と定義することができる。したがって、前の節の用語​​を用いると、破砕係数は正確に ${\displaystyle {\mathcal {F}}}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle f\in {\mathcal {F}}}$

${\displaystyle \max _{x_{1},\ldots ,x_{n}}\Delta _{n}({\mathcal {C}},x_{1},\ldots ,x_{n})}$。

この同値性とザウアーの補題を合わせると、集合が有限の VC インデックスを持つ 限り、 nが十分に大きい場合、nの多項式になることがわかります。 ${\displaystyle S({\mathcal {F}},n)}$ ${\displaystyle {\mathcal {C}}}$

を観測データセットとします。データは未知の確率分布 によって生成されたと仮定します。を期待される0/1損失と定義します。もちろん、は一般に未知であるため、 を知ることはできません。しかし、経験的リスクは次のように与えられます。 ${\displaystyle D_{n}=\{(X_{1},Y_{1}),\ldots ,(X_{n},Y_{m})\}}$ ${\displaystyle P_{XY}}$ ${\displaystyle R(f)=P(f(X)\neq Y)}$ ${\displaystyle P_{XY}}$ ${\displaystyle R(f)}$

${\displaystyle {\hat {R}}_{n}(f)={\dfrac {1}{n}}\sum _{i=1}^{n}\mathbb {I} (f(X_{i})\neq Y_{i})}$

確かに評価できる。すると、次の定理が成立する。

定理（VC不等式）

バイナリ分類と 0/1 損失関数の場合、一般化境界は次のようになります。

${\displaystyle {\begin{aligned}P\left(\sup _{f\in {\mathcal {F}}}\left|{\hat {R}}_{n}(f)-R(f)\right|>\varepsilon \right)&\leq 8S({\mathcal {F}},n)e^{-n\varepsilon ^{2}/32}\\\mathbb {E} \left[\sup _{f\in {\mathcal {F}}}\left|{\hat {R}}_{n}(f)-R(f)\right|\right]&\leq 2{\sqrt {\dfrac {\log S({\mathcal {F}},n)+\log 2}{n}}}\end{aligned}}}$

VC不等式は、サンプル数が増加するにつれて、VC次元が有限であれば、経験的0/1リスクが期待0/1リスクの良い代理変数になることを示しています。ただし、 nが多項式的に増加する限り、2つの不等式の右辺は両方とも0に収束することに注意してください。 ${\displaystyle {\mathcal {F}}}$ ${\displaystyle S({\mathcal {F}},n)}$

この枠組みと経験的プロセス枠組みとの関連性は明らかである。ここでは、修正された経験的プロセスを扱っている。

${\displaystyle \left|{\hat {R}}_{n}-R\right|_{\mathcal {F}}}$

しかし、当然ながら考え方は同じです。VC不等式の（最初の部分の）証明は対称化に依存しており、その後、濃度不等式（特にヘフディングの不等式）を用いてデータに基づいて条件付きで論じます。興味のある読者は、書籍^[5]の定理12.4と12.5を参照してください。

参考文献

1. Vapnik, Vladimir N. (2000).統計学習理論の本質. 情報科学と統計. Springer-Verlag . ISBN 978-0-387-98780-4。
2. van der Vaart, Aad W. ; Wellner, Jon A. (2000). 弱収束と経験的プロセス：統計への応用（第2版）. Springer. ISBN 978-0-387-94640-5。
3. Devroye, L., Gyorfi, L. & Lugosi, G. パターン認識の確率理論離散応用数学 73 , 192–194 (1997).
4. ポラード、デイヴィッド（1990年）。経験的プロセス：理論と応用NSF-CBMS確率統計地域会議シリーズ第2巻。ISBN 978-0-940600-16-4。
5. ギョルフィ、L.;デブロイ、L.ルゴシ、G. (1996)。パターン認識の確率理論(第 1 版)。スプリンガー。ISBN 978-0387946184。

• 記事内の参考文献を参照：Richard M. Dudley、empirical processes、Shattered set。^{[循環参照]}
• Vapnik, VN; Chervonenkis, A. Ya. (1968). 「事象の相対頻度とその確率の一様収束について」『ソビエト数学』9 : 915–918 .これは 1968 年のメモを B. Seckler が翻訳したものです。
  • Vapnik , VN; Chervonenkis, A. Ya. (2015), Vovk, Vladimir; Papadopoulos, Harris; Gammerman, Alexander (eds.), "On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities" , Measures of Complexity , Cham: Springer International Publishing, pp.  11– 30, doi :10.1007/978-3-319-21852-6_3, ISBNに転載 978-3-319-21851-9
  • 彼らは1966年7月に草案の形で結果を得て、1968年にVapnik, VN; Chervonenkis, A.Ya. (1968).「事象の相対頻度とその確率の一様収束について」『SSSR国立科学アカデミー紀要』（ロシア語）181 (4): 781– 783. という論文で発表した。
  • この論文は最初にロシア語でVapnik, VN として正式に出版されました。チェルボネンキス、A.Ya. （1971年）。 「О равномерноЙ сходимости частот появления событиЙ к их вероятностям」[事象の発生頻度とその確率の一様な収束について]。Теория вероятностеЙ и ее применения [確率論とその応用] (ロシア語)。16 (2): 264–279。
• Bousquet, Olivier; Elisseeff, Andr´e (2002年3月1日). 「安定性と一般化」. The Journal of Machine Learning Research . 2 : 499–526 . doi : 10.1162/153244302760200704 . S2CID  1157797.
• カンピ、マルコ；ガラッティ、シモーネ (2023). 「圧縮、一般化、そして学習」(PDF) .機械学習研究ジャーナル. 24 : 1– 74.
• Vapnik, V.; Chervonenkis, A. (2004). 「事象の相対頻度とその確率の一様収束について」.確率理論応用. 16 ( 2): 264– 280. doi :10.1137/1116025.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Vapnik–Chervonenkis_theory&oldid=1320556594"