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

Частина з циклу
Машинне навчання та добування даних
Парадигми Кероване навчання Некероване навчання Інтерактивне навчання Пакетне навчання Метанавчання Напівкероване навчання Самокероване навчання Навчання з підкріпленням Навчання на основі правил Квантове машинне навчання
Задачі Класифікація Породжувальна модель Регресія Кластерування Знижування розмірності Оцінювання густини Виявляння аномалій Очищування даних АвтоМН Асоціативні правила Семантичний аналіз Структурове передбачування Конструювання ознак Навчання ознак Навчання ранжуванню Виведення граматик Навчання онтологій Мультимодальне навчання
Кероване навчання (класифікація • регресія) Ансамблі Випадковий ліс Бутстрепова агрегація Підсилювання Градієнтне підсилювання AdaBoost Дерева рішень MARS CART Доречно-векторна машина k-сусідів Лінійна регресія Логістична регресія Лінійний розділювальний аналіз Наївний баєсів класифікатор Перцептрон Підмайстрове навчання Опорно-векторна машина Штучні нейронні мережі
Кластерування BIRCH CURE Ієрархічне k-середніх Нечітке Очікування-максимізація DBSCAN OPTICS Спектральне Зсув середнього
Знижування розмірності Факторний аналіз Метод незалежних компонент Канонічна кореляція Дискримінантний аналіз Метод головних компонент Власний узагальнений розклад Розклад невід'ємних матриць t-розподілене вкладення стохастичної близькості Навчання розріджених словників
Структурове передбачування Графові моделі Баєсова мережа Прихована марковська модель Умовне випадкове поле
Виявляння аномалій RANSAC k-НС Коефіцієнт локального відхилення Відстань Кука Ізоляційний ліс
Штучна нейронна мережа Автокодувальник Когнітивні обчислення Глибоке навчання DeepDream Нейронна мережа прямого поширення Рекурентна нейронна мережа ДКЧП ВРВ МВС Резервуарне обчислення Обмежена машина Больцмана ГЗМ Дифузійна модель Самоорганізаційна карта Згорткова нейронна мережа U-Net Трансформер Зоровий Спайкова нейронна мережа Мемтранзистор Електрохімічна ПДД (ECRAM)
Навчання з підкріпленням Q-навчання SARSA Метод часових різниць Багатоагентне навчання з підкріпленням Гра проти себе
Навчання з людьми Активне навчання (машинне навчання) Краудсорсинг Людина-в-циклі
Діагностування моделей Крива спроможності навчатися
Математичні засади Ядрові машини Компроміс зсуву та дисперсії Ймовірнісно приблизно коректне навчання Мінімізація емпіричного ризику Оккамове навчання Регуляризація LASSO Тихонова Еластично-сіткова Статистичне навчання Теорія Вапника — Червоненкіса Теорія обчислювального навчання
Місця машинного навчання ECML PKDD NeurIPS ICML ICLR IJCAI ML JMLR
Пов'язані статті Глосарій штучного інтелекту Список наборів даних для досліджень з машинного навчання Перелік понять машинного навчання

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

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

Введення

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

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

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

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

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

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

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

$Qf=\int fdQ$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Наступна умова є версією славетної теореми Дадлі. Якщо ${\mathcal {F}}$ є таким класом функцій, що

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

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

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

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

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

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

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

Виявляється, що існує зв'язок між цим емпіричним, та наступним симетрованим процесом:

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

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

Лема (симетрування). Для будь-якої неспадної опуклої Φ: R → R та класу вимірних функцій ${\mathcal {F}}$,

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

Доведення леми симетрування покладається на введення незалежних копій первинних змінних $X_{i}$ (які іноді називають вибіркою-привидом) та заміну виразу під математичним сподіванням в лівій частині нерівності цими копіями. Після застосування нерівності Єнсена може бути введено інші знаки (звідси й назва — симетрування) без зміни математичного сподівання. Нижче наведено доведення, через його повчальний характер.

[Доведення]

Введімо «вибірку-привід» $Y_{1},\ldots ,Y_{n}$ як незалежні копії $X_{1},\ldots ,X_{n}$. Для фіксованих значень $X_{1},\ldots ,X_{n}$ маємо:

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

Отже, згідно нерівності Єнсена,

$\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)$

Взяття математичного сподівання по відношенню до $X$ дає

$\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)$

Зауважте, що додавання знаку мінусу перед членом $f(X_{i})-f(Y_{i})$ не змінює правої частини нерівності, оскільки вона є симетричною функцією від $X$ та $Y$. Отже, права частина нерівності залишається такою ж і за «збурення знаку»:

$\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)$

для будь-яких $(e_{1},e_{2},\ldots ,e_{n})\in \{-1,1\}^{n}$. Отже,

$\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)$

Нарешті, застосування першої нерівності трикутника, а потім опуклості $\Phi$, дає

$\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)$

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

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

ВЧ-зв'язок

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

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

Далі, лема Зауера стверджує, що число $\Delta _{n}({\mathcal {C}},x_{1},\ldots ,x_{n})$ підмножин, вихоплюваних ВЧ-класом ${\mathcal {C}}$, задовольняє

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

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

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

Розгляньмо множину індикаторних функцій ${\mathcal {I}}_{\mathcal {C}}=\{1_{C}:C\in {\mathcal {C}}\}$ в $L_{1}(Q)$ для дискретного емпіричного типу міри Q (або, рівнозначно, для будь-якої міри ймовірності Q). Тоді може бути показано, що, на диво, для $r\geq 1$

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

Далі розгляньмо симетричну опуклу оболонку множини ${\mathcal {F}}$: $\operatorname {sconv} {\mathcal {F}}$, яка є набором функцій вигляду $\sum _{i=1}^{m}\alpha _{i}f_{i}$ з $\sum _{i=1}^{m}|\alpha _{i}|\leq 1$. Тоді якщо

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

то наступне є вірним для опуклої оболонки ${\mathcal {F}}$:

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

Важливим наслідком цього факту є те, що

${\frac {2V}{V+2}}>2,$

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

Нарешті, розглядається приклад ВЧ-підграфікового класу. Будь-який векторний простір ${\mathcal {F}}$ вимірних функцій $f:{\mathcal {X}}\to \mathbf {R}$, який має скінченну розмірність, є ВЧ-підграфіком індексу, меншого або рівного $\dim({\mathcal {F}})+2$.

[Доведення]

Візьмімо $n=\dim({\mathcal {F}})+2$ точок $(x_{1},t_{1}),\ldots ,(x_{n},t_{n})$. Вектори

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

є векторами підпростору Rⁿ з розмірністю n − 1. Візьмімо a ≠ 0, вектор, ортогональний до цього підпростору. Тоді

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

Розгляньмо множину $S=\{(x_{i},t_{i}):a_{i}>0\}$. Цю множину не може бути вихоплено, оскільки, якби існувала якась функція $f$, така що $S=\{(x_{i},t_{i}):f(x_{i})>t_{i}\}$, то це означало би, що ліва частина рівності є строго додатною, а права — недодатною.

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

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

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

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

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

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

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

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

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

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

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

Для бінарної класифікації та функції втрат 0/1 ми маємо наступні обмеження узагальнення:

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

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

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

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

але не дивно, що ідеї є однаковими. Доведення (першої частини) ВЧ-нерівності спирається на симетрування, а потім здійснює доведення, обумовлене даними, із застосуванням концентричних нерівностей (зокрема, нерівності Хьофдинга). Зацікавлений читач може перевірити теореми 12.4 та 12.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. (англ.)
• Див. джерела у статтях Річард Дадлі, емпіричний процес, роздрібнена множина.
• ↑ 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. (рос.)