Теорія Вапника — Червоненкіса

Теорію Вапника — Червоненкіса (англ. Vapnik–Chervonenkis theory, відому також як ВЧ-теорія, англ. VC theory) було розроблено протягом 1960–1990 років Володимиром Вапником та Олександром Червоненкісом^[en]. Ця теорія є різновидом теорії обчислювального навчання^[en], яка намагається пояснювати процес навчання зі статистичної точки зору.

ВЧ-теорія пов'язана з теорією статистичного навчання та з емпіричними процесами^[en]. До емпіричних процесів^[en] ВЧ-теорію застосовували, серед інших, Річард Дадлі^[en] та Володимир Вапник.

Введення

ВЧ-теорія охоплює щонайменше чотири частини (як пояснено в «Природі теорії статистичного навчання»^[1]):

• Теорію узгодженості^[en] процесів навчання
  • Якими є (необхідні та достатні) умови узгодженості процесу навчання на основі принципу мінімізації емпіричного ризику?
• Неасимптотичну теорію темпу збіжності процесів навчання
  • Наскільки швидким є темп збіжності процесу навчання?
• Теорію керування узагальнювальною спроможністю процесів навчання
  • Як можна керувати темпом збіжності (узагальнювальною спроможністю) процесу навчання?
• Теорію побудови машин, які вчаться
  • Як можна будувати алгоритми, які керують узагальнювальною спроможністю?

ВЧ-теорія є однією з основних підгалузей теорії статистичного навчання. Одним із її головних застосувань у теорії статистичного навчання є забезпечення умов узагальнення для алгоритмів навчання. З цієї точки зору ВЧ-теорія пов'язана зі стійкістю^[en], яка є альтернативним підходом для характеризування узагальнення.

Крім того, ВЧ-теорія та ВЧ-розмірність відіграють важливу роль у теорії емпіричних процесів^[en] у випадку процесів, індексованих за ВЧ-класами. Можливо, вони є найважливішими застосуваннями ВЧ-теорії, вони застосовуються в доведенні узагальнення. Буде представлено кілька методик, які широко використовуються в емпіричних процесах та ВЧ-теорії. Обговорення в основному ґрунтується на книзі «Слабка збіжність та емпіричні процеси: із застосуваннями до статистики».^[2]

Огляд ВЧ-теорії в емпіричних процесах

Довідка про емпіричні процеси

Нехай ${\displaystyle X_{1},\ldots ,X_{n}}$ є випадковими елементами, визначеними на вимірному просторі ${\displaystyle ({\mathcal {X}},{\mathcal {A}})}$. Для міри Q встановімо:

${\displaystyle Qf=\int fdQ}$

Питання вимірності тут ігноруватимуться, технічні деталі див. у ^[3]. Покладімо, що ${\displaystyle {\mathcal {F}}}$ є класом вимірних функцій ${\displaystyle f:{\mathcal {X}}\to \mathbf {R} }$, і визначмо

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

Визначмо емпіричну міру

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

де δ в даному випадку відповідає мірі Дірака^[en]. Емпірична міра породжує відображення ${\displaystyle {\mathcal {F}}\to \mathbf {R} }$, що задається як

${\displaystyle f\mapsto \mathbb {P} _{n}f}$

Тепер припустімо, що P є справжнім розподілом, що лежить в основі даних, який є невідомим. Теорія емпіричних процесів спрямована на ідентифікацію класів ${\displaystyle {\mathcal {F}}}$, для яких виконуються такі твердження, як наступні:

• рівномірний закон великих чисел:

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

• рівномірна центральна гранична теорема:

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

В першому випадку ${\displaystyle {\mathcal {F}}}$ називається класом Гливенка — Кантеллі^[en] (англ. Glivenko-Cantelli class), а в другому (за припущення ${\displaystyle \forall x,\sup \nolimits _{f\in {\mathcal {F}}}\vert f(x)-Pf\vert <\infty }$) клас ${\displaystyle {\mathcal {F}}}$ називається донскеровим (англ. Donsker class), або P-донскеровим. Очевидно, що клас Донскера є класом Гливенка — Кантеллі в теорії ймовірностей, якщо застосувати теорему Слуцького.

Ці твердження справедливі для єдиної ${\displaystyle f}$ згідно стандартних доводів ЗВЧ та ЦГТ в умовах регулярності, а складність в емпіричних процесах виникає тому, що робляться спільні твердження для всіх ${\displaystyle f\in {\mathcal {F}}}$. Тоді, інтуїтивно, множина ${\displaystyle {\mathcal {F}}}$ не може бути занадто великою, і, як виявляється, дуже важливу роль відіграє геометрія ${\displaystyle {\mathcal {F}}}$.

Одним зі способі вимірювання того, наскільки великою є множина функцій ${\displaystyle {\mathcal {F}}}$, є застосування так званих чисел покриття^[en]. Число покриття

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

є мінімальним числом куль ${\displaystyle \{g:\|g-f\|<\varepsilon \}}$, необхідних для покриття множини ${\displaystyle {\mathcal {F}}}$ (тут, очевидно, припускається існування норми на ${\displaystyle {\mathcal {F}}}$, на основі якої це робиться). Ентропія є логарифмом числа покриття.

Нижче наведено дві достатні умови, за яких може бути доведено, що множина ${\displaystyle {\mathcal {F}}}$ є Гливенка — Кантеллі, або донскеровою.

Клас ${\displaystyle {\mathcal {F}}}$ є P-Гливенка — Кантеллі, якщо він є P-мірним такою обгорткою F, що ${\displaystyle P^{\ast }F<\infty }$ та виконується

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

Наступна умова є версією славетної теореми Дадлі^[en]. Якщо ${\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 }$

то ${\displaystyle {\mathcal {F}}}$ є P-донскеровим для будь-якої такої міри ймовірності P, що ${\displaystyle P^{\ast }F^{2}<\infty }$. В крайньому інтегралі цей запис означає

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

Симетрування

Більшість обґрунтувань того, як обмежувати емпіричні процеси, покладаються на симетрування, максимальні та концентричні нерівності, та зчеплювання. Симетрування зазвичай є першим кроком цих доведень, і оскільки воно використовується в багатьох доведеннях машинного навчання із обмеження функцій емпіричних втрат (включно із доведенням ВЧ-нерівності, що обговорюється в наступному розділі), його представлено тут.

Розгляньмо емпіричний процес

${\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}={\dfrac {1}{n}}\sum _{i=1}^{n}\varepsilon _{i}f(X_{i})}$

Цей симетрований процес є процесом Радемахера, обумовленим даними ${\displaystyle X_{i}}$. Отже, згідно нерівності Хьофдинга^[en], він є субґаусовим процесом.

Лема (симетрування). Для будь-якої неспадної опуклої Φ: 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)}$

Доведення леми симетрування покладається на введення незалежних копій первинних змінних ${\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)}$

Де два крайні вирази в правій частині нерівності є однаковими, що завершує доведення.

Типовий спосіб доведення емпіричних ЦГТ спочатку застосовує симетрування для передачі емпіричного процесу до ${\displaystyle \mathbb {P} _{n}^{0}}$, а потім здійснює доведення обумовлено даними, використовуючи той факт, що процеси Радемахера є простими процесами з гарними властивостями.

ВЧ-зв'язок

Виявляється, існує чарівний зв'язок між деякими комбінаторними властивостями множини ${\displaystyle {\mathcal {F}}}$, та числами ентропії. Числа рівномірного покриття можуть контролюватися поняттям класів множин Вапника — Червоненкіса (англ. Vapnik-Chervonenkis classes of sets), або, коротше, ВЧ-множин (англ. VC sets).

Розгляньмо набір ${\displaystyle {\mathcal {C}}}$ підмножин вибіркового простору ${\displaystyle {\mathcal {X}}}$. Кажуть, що ${\displaystyle {\mathcal {C}}}$ вихоплює (англ. pick out) певну підмножину ${\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}}}$ роздрібнює (англ. shatter) S, якщо він вихоплює кожну з її 2ⁿ підмножин. ВЧ-індекс (англ. VC-index, подібний до ВЧ-розмірності + 1 для відповідним чином вибраної класифікаторної множини) ${\displaystyle V({\mathcal {C}})}$ набору ${\displaystyle {\mathcal {C}}}$ — це найменше n, для якого жодна множина розміру n не роздрібнюється набором ${\displaystyle {\mathcal {C}}}$.

Далі, лема Зауера^[en] стверджує, що число ${\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}}$

Що є поліноміальним числом ${\displaystyle O(n^{V({\mathcal {C}})-1})}$ підмножин, а не експоненційним. Інтуїтивно це означає, що зі скінченності ВЧ-індексу випливає, що ${\displaystyle {\mathcal {C}}}$ має явно спрощену структуру.

Подібне обмеження може бути показано (з іншим сталим, незмінним співвідношенням) для так званих ВЧ-підграфікових класів (англ. VC subgraph classes). Для функції ${\displaystyle f:{\mathcal {X}}\to \mathbf {R} }$ підграфіком^[en] є така підмножина ${\displaystyle {\mathcal {X}}\times \mathbf {R} }$, що ${\displaystyle \{(x,t):t<f(x)\}}$. Набір ${\displaystyle {\mathcal {F}}}$ називається ВЧ-підграфіковим класом, якщо всі підграфіки формують ВЧ-клас.

Розгляньмо множину індикаторних функцій ${\displaystyle {\mathcal {I}}_{\mathcal {C}}=\{1_{C}:C\in {\mathcal {C}}\}}$ в ${\displaystyle L_{1}(Q)}$ для дискретного емпіричного типу міри Q (або, рівнозначно, для будь-якої міри ймовірності 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,}$

чого якраз достатньо для того, щоби інтеграл ентропії сходився, і відтак клас ${\displaystyle \operatorname {sconv} {\mathcal {F}}}$ був P-донскеровим.

Нарешті, розглядається приклад ВЧ-підграфікового класу. Будь-який векторний простір ${\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}\}}$, то це означало би, що ліва частина рівності є строго додатною, а права — недодатною.

Існують узагальнення поняття ВЧ-підграфових класів, наприклад, існує поняття псевдорозмірності. Зацікавлені читачі можуть подивитися ^[4].

ВЧ-нерівність

Розглядається подібна постановка, звичніша для машинного навчання. Нехай ${\displaystyle {\mathcal {X}}}$ є простором ознак, а ${\displaystyle {\mathcal {Y}}=\{0,1\}}$. Функція ${\displaystyle f:{\mathcal {X}}\to {\mathcal {Y}}}$ називається класифікатором. Нехай ${\displaystyle {\mathcal {F}}}$ є множиною класифікаторів. Подібно до попереднього розділу, визначмо коефіцієнт роздрібнювання (англ. shattering coefficient, відомий також як функція росту, англ. growth function):

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

Зауважте, що існує взаємно однозначне відображення між кожною з функцій в ${\displaystyle {\mathcal {F}}}$, та множиною, на якій ця функція дорівнює 1. Отже, ми можемо визначити ${\displaystyle {\mathcal {C}}}$ як набір підмножин, отриманий з наведеного вище відображення для кожної ${\displaystyle f\in {\mathcal {F}}}$. Таким чином, з точки зору попереднього розділу, коефіцієнт роздрібнювання в точності дорівнює

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

З цієї рівності разом із лемою Зауера^[en] випливає, що ${\displaystyle S({\mathcal {F}},n)}$ має бути поліноміальним в n, для достатньо великого n, за умови, що набір ${\displaystyle {\mathcal {C}}}$ має скінченний ВЧ-індекс.

Нехай ${\displaystyle D_{n}=\{(X_{1},Y_{1}),\ldots ,(X_{n},Y_{m})\}}$ є спостережуваним набором даних. Припустімо, що ці дані породжено невідомим розподілом імовірності ${\displaystyle P_{XY}}$. Визначмо ${\displaystyle R(f)=P(f(X)\neq Y)}$ як очікувані втрати 0/1. Звісно, оскільки ${\displaystyle P_{XY}}$ є загалом невідомим, ми не маємо доступу до ${\displaystyle R(f)}$. Проте емпіричний ризик (англ. empirical risk), заданий як

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

безумовно, може бути оцінено. Тоді маємо наступну теорему:

Теорема (ВЧ-нерівність)

Для бінарної класифікації та функції втрат 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}}}$

Іншими словами, ВЧ-нерівність каже, що при збільшенні вибірки, за умови, що ${\displaystyle {\mathcal {F}}}$ має скінченну ВЧ-розмірність, емпіричний ризик 0/1 стає добрим замінником очікуваного ризику 0/1. Зауважте, що обидві праві частини цих двох нерівностей збігатимуться до 0 за умови, що ${\displaystyle S({\mathcal {F}},n)}$ зростає поліноміально в n.

Очевидним є зв'язок між цією системою та системою емпіричних процесів. Тут ми маємо справу з видозміненим емпіричним процесом

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

але не дивно, що ідеї є однаковими. Доведення (першої частини) ВЧ-нерівності спирається на симетрування, а потім здійснює доведення, обумовлене даними, із застосуванням концентричних нерівностей (зокрема, нерівності Хьофдинга^[en]). Зацікавлений читач може перевірити теореми 12.4 та 12.5 книги ^[5].

Джерела

• ↑ Vapnik, Vladimir N (2000). The Nature of Statistical Learning Theory. Information Science and Statistics. Springer-Verlag. ISBN 978-0-387-98780-4. (англ.)
• Vapnik, Vladimir N (1989). Statistical Learning Theory. Wiley-Interscience. ISBN 0-471-03003-1. (англ.)
• ↑  van der Vaart, Aad W.; Wellner, Jon A. (2000). Weak Convergence and Empirical Processes: With Applications to Statistics (вид. 2nd). Springer. ISBN 978-0-387-94640-5. Архів оригіналу за 20 листопада 2016. Процитовано 20 листопада 2016. (англ.)
• ↑ Gyorfi, L.; Devroye, L.; Lugosi, G. (1996). A probabilistic theory of pattern recognition (вид. 1st). Springer. ISBN 978-0387946184. (англ.)
• Див. джерела у статтях Річард Дадлі^[en], емпіричний процес^[en], роздрібнена множина.
• ↑ Pollard, David (1990). Empirical Processes: Theory and Applications. NSF-CBMS Regional Conference Series in Probability and Statistics Volume 2. ISBN 0-940600-16-1. (англ.)
• Introduction to Statistical Learning Theory // Advanced Lectures on Machine Learning Lecture Notes in Artificial Intelligence 3176, 169-207. (Eds.) Bousquet, O., U. von Luxburg and G. Ratsch, Springer. — 2004. (англ.)
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities // Theory Probab. Appl., 16(2), 264–280.. — 2004. (англ.)

Література

• Воронцов, К. В. (2004). Обзор современных исследований по проблеме качества обучения алгоритмов (PDF). Таврический вестник информатики и математики. 1. Архів оригіналу (PDF) за 20 листопада 2016. Процитовано 20 листопада 2016. (рос.)

Посилання

• Теория Вапника-Червоненкиса. MachineLearning.ru. Архів оригіналу за 13 березня 2022. Процитовано 2 квітня 2022. (рос.)