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

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

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

Введення

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

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

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

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

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

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

Нехай $X_1,\dots ,X_n$ є випадковими елементами, визначеними на вимірному просторі $(𝒳,𝒜)$. Для міри Шаблон:Mvar встановімо:

$Qf=\int fdQ$

Питання вимірності тут ігноруватимуться, технічні деталі див. у Шаблон:Ref. Покладімо, що $ℱ$ є класом вимірних функцій $f:𝒳\to 𝐑$, і визначмо

$\Vert Q{\Vert }_{ℱ}=\sup \{|Qf|:f\in ℱ\}.$

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

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

де Шаблон:Mvar в даному випадку відповідає Шаблон:Нп. Емпірична міра породжує відображення $ℱ\to 𝐑$, що задається як

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

Тепер припустімо, що Шаблон:Mvar є справжнім розподілом, що лежить в основі даних, який є невідомим. Теорія емпіричних процесів спрямована на ідентифікацію класів $ℱ$, для яких виконуються такі твердження, як наступні:

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

$\Vert {\mathbb{P}}_n-P{\Vert }_{ℱ}\to 0,$

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

${𝔾}_n=\sqrt{n}({\mathbb{P}}_n-P)⇝𝔾,\text{in }{\ell }^{\mathrm{\infty }}(ℱ)$

В першому випадку $ℱ$ називається Шаблон:Нп (Шаблон:Lang-en), а в другому (за припущення $\mathrm{\forall }x,\sup {\mathrm{\backslash nolimits}}_{f\in ℱ}|f(x)-Pf|<\mathrm{\infty }$) клас $ℱ$ називається донскеровим (Шаблон:Lang-en), або Шаблон:Mvar-донскеровим. Очевидно, що клас Донскера є класом Гливенка — Кантеллі в теорії ймовірностей, якщо застосувати теорему Слуцького.

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

Одним зі способі вимірювання того, наскільки великою є множина функцій $ℱ$, є застосування так званих Шаблон:Нп. Число покриття

$N(\epsilon ,ℱ,\Vert \cdot \Vert )$

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

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

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

$\mathrm{\forall }\epsilon >0\sup {\mathrm{\backslash nolimits}}_{Q}N(\epsilon \Vert F{\Vert }_Q,ℱ,L_1(Q))<\mathrm{\infty }.$

Наступна умова є версією славетної Шаблон:Нп. Якщо $ℱ$ є таким класом функцій, що

$\underset{0}{\overset{\mathrm{\infty }}{\int }}\sup {\mathrm{\backslash nolimits}}_Q\sqrt{\log N(\epsilon \Vert F{\Vert }_{Q,2},ℱ,L_2(Q))}d\epsilon <\mathrm{\infty }$

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

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

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

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

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

$f\mapsto ({\mathbb{P}}_n-P)f=\frac{1}{n}\sum _{i=1}^n(f(X_i)-Pf)$

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

$f\mapsto {\mathbb{P}}_n^0=\frac{1}{n}\sum _{i=1}^n{\epsilon }_{i}f(X_i)$

Цей симетрований процес є процесом Радемахера, обумовленим даними $X_i$. Отже, згідно Шаблон:Нп, він є субґаусовим процесом.

Лема (симетрування). Для будь-якої неспадної опуклої Шаблон:Math та класу вимірних функцій $ℱ$,

$𝔼\mathrm{\Phi }(\Vert {\mathbb{P}}_n-P{\Vert }_{ℱ})\le 𝔼\mathrm{\Phi }\left(2{\Vert {\mathbb{P}}_n^0\Vert }_{ℱ}\right)$

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

[Доведення]

Введімо «вибірку-привід» $Y_1,\dots ,Y_n$ як незалежні копії $X_1,\dots ,X_n$. Для фіксованих значень $X_1,\dots ,X_n$ маємо:

$\Vert {\mathbb{P}}_n-P{\Vert }_{ℱ}=\underset{f\in ℱ}{\sup }\frac{1}{n}|\sum _{i=1}^{n}f(X_i)-𝔼f(Y_i)|\le {𝔼}_Y\underset{f\in ℱ}{\sup }\frac{1}{n}|\sum _{i=1}^{n}f(X_i)-f(Y_i)|$

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

$\mathrm{\Phi }(\Vert {\mathbb{P}}_n-P{\Vert }_{ℱ})\le {𝔼}_Y\mathrm{\Phi }\left({\Vert \frac{1}{n}\sum _{i=1}^{n}f(X_i)-f(Y_i)\Vert }_{ℱ}\right)$

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

$𝔼\mathrm{\Phi }(\Vert {\mathbb{P}}_n-P{\Vert }_{ℱ})\le {𝔼}_X{𝔼}_Y\mathrm{\Phi }\left({\Vert \frac{1}{n}\sum _{i=1}^{n}f(X_i)-f(Y_i)\Vert }_{ℱ}\right)$

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

$𝔼\mathrm{\Phi }\left({\Vert \frac{1}{n}\sum _{i=1}^n{e}_i(f(X_i)-f(Y_i))\Vert }_{ℱ}\right)$

для будь-яких $(e_1,e_2,\dots ,e_n)\in \{-1,1{\}}^n$. Отже,

$𝔼\mathrm{\Phi }(\Vert {\mathbb{P}}_n-P{\Vert }_{ℱ})\le {𝔼}_{\epsilon }𝔼\mathrm{\Phi }\left({\Vert \frac{1}{n}\sum _{i=1}^n{\epsilon }_i(f(X_i)-f(Y_i))\Vert }_{ℱ}\right)$

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

$𝔼\mathrm{\Phi }(\Vert {\mathbb{P}}_n-P{\Vert }_{ℱ})\le \frac{1}{2}{𝔼}_{\epsilon }𝔼\mathrm{\Phi }\left(2{\Vert \frac{1}{n}\sum _{i=1}^n{\epsilon }_{i}f(X_i)\Vert }_{ℱ}\right)+\frac{1}{2}{𝔼}_{\epsilon }𝔼\mathrm{\Phi }\left(2{\Vert \frac{1}{n}\sum _{i=1}^n{\epsilon }_{i}f(Y_i)\Vert }_{ℱ}\right)$

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

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

ВЧ-зв'язок

Виявляється, існує чарівний зв'язок між деякими комбінаторними властивостями множини $ℱ$, та числами ентропії. Числа рівномірного покриття можуть контролюватися поняттям класів множин Вапника — Червоненкіса (Шаблон:Lang-en), або, коротше, ВЧ-множин (Шаблон:Lang-en).

Розгляньмо набір $𝒞$ підмножин вибіркового простору $𝒳$. Кажуть, що $𝒞$ вихоплює (Шаблон:Lang-en) певну підмножину $W$ скінченної множини $S=\{x_1,\dots ,x_n\}\subset 𝒳$, якщо $W=S\cap C$ для деякого $C\in 𝒞$. Кажуть, що $𝒞$ роздрібнює (Шаблон:Lang-en) Шаблон:Mvar, якщо він вихоплює кожну з її Шаблон:Math підмножин. ВЧ-індекс (Шаблон:Lang-en, подібний до ВЧ-розмірності + 1 для відповідним чином вибраної класифікаторної множини) $V(𝒞)$ набору $𝒞$ — це найменше Шаблон:Mvar, для якого жодна множина розміру Шаблон:Mvar не роздрібнюється набором $𝒞$.

Далі, Шаблон:Нп стверджує, що число ${\mathrm{\Delta }}_n(𝒞,x_1,\dots ,x_n)$ підмножин, вихоплюваних ВЧ-класом $𝒞$, задовольняє

$\underset{x_1,\dots ,x_n}{\max }{\mathrm{\Delta }}_n(𝒞,x_1,\dots ,x_n)\le \sum _{j=0}^{V(𝒞)-1}(\genfrac{}{}{0ex}{}{n}{j})\le {\left(\frac{ne}{V(𝒞)-1}\right)}^{V(𝒞)-1}$

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

Подібне обмеження може бути показано (з іншим сталим, незмінним співвідношенням) для так званих ВЧ-підграфікових класів (Шаблон:Lang-en). Для функції $f:𝒳\to 𝐑$ Шаблон:Нп є така підмножина $𝒳\times 𝐑$, що $\{(x,t):t<f(x)\}$. Набір $ℱ$ називається ВЧ-підграфіковим класом, якщо всі підграфіки формують ВЧ-клас.

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

$N(\epsilon ,{ℐ}_{𝒞},L_r(Q))\le KV(𝒞)(4e{)}^{V(𝒞)}{\epsilon }^{-r(V(𝒞)-1)}$

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

$N(\epsilon \Vert F{\Vert }_{Q,2},ℱ,L_2(Q))\le C{\epsilon }^{-V}$

то наступне є вірним для опуклої оболонки $ℱ$:

$\log N(\epsilon \Vert F{\Vert }_{Q,2},\mathrm{sconv}ℱ,L_2(Q))\le K{\epsilon }^{-\frac{2V}{V+2}}$

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

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

чого якраз достатньо для того, щоби інтеграл ентропії сходився, і відтак клас $\mathrm{sconv}ℱ$ був Шаблон:Mvar-донскеровим.

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

[Доведення]

Візьмімо $n=\dim (ℱ)+2$ точок $(x_1,t_1),\dots ,(x_n,t_n)$. Вектори

$(f(x_1),\dots ,f(x_n))-(t_1,\dots ,t_n)$

є векторами підпростору Шаблон:Math з розмірністю Шаблон:Math. Візьмімо Шаблон:Math, вектор, ортогональний до цього підпростору. Тоді

$\sum _{a_i>0}{a}_i(f(x_i)-t_i)=\sum _{a_i<0}(-a_i)(f(x_i)-t_i),\mathrm{\forall }f\in ℱ$

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

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

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

Розглядається подібна постановка, звичніша для машинного навчання. Нехай $𝒳$ є простором ознак, а $𝒴=\{0,1\}$. Функція $f:𝒳\to 𝒴$ називається класифікатором. Нехай $ℱ$ є множиною класифікаторів. Подібно до попереднього розділу, визначмо коефіцієнт роздрібнювання (Шаблон:Lang-en, відомий також як функція росту, Шаблон:Lang-en):

$S(ℱ,n)=\underset{x_1,\dots ,x_n}{\max }|\{(f(x_1),\dots ,f(x_n)),f\in ℱ\}|$

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

$\underset{x_1,\dots ,x_n}{\max }{\mathrm{\Delta }}_n(𝒞,x_1,\dots ,x_n)$.

З цієї рівності разом із Шаблон:Нп випливає, що $S(ℱ,n)$ має бути поліноміальним в Шаблон:Mvar, для достатньо великого Шаблон:Mvar, за умови, що набір $𝒞$ має скінченний ВЧ-індекс.

Нехай $D_n=\{(X_1,Y_1),\dots ,(X_n,Y_m)\}$ є спостережуваним набором даних. Припустімо, що ці дані породжено невідомим розподілом імовірності $P_{XY}$. Визначмо $R(f)=P(f(X)\ne Y)$ як очікувані втрати 0/1. Звісно, оскільки $P_{XY}$ є загалом невідомим, ми не маємо доступу до $R(f)$. Проте емпіричний ризик (Шаблон:Lang-en), заданий як

${\hat{R}}_n(f)=\frac{1}{n}\sum _{i=1}^n𝕀(f(X_i)\ne Y_i)$

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

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

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

$\begin{array}{cc}P(\underset{f\in ℱ}{\sup }|{\hat{R}}_n(f)-R(f)|>\epsilon )& \le 8S(ℱ,n)e^{-n{\epsilon }^2/32}\\ 𝔼\left[\underset{f\in ℱ}{\sup }|{\hat{R}}_n(f)-R(f)|\right]& \le 2\sqrt{\frac{\log S(ℱ,n)+\log 2}{n}}\end{array}$

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

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

${|{\hat{R}}_n-R|}_{ℱ}$

але не дивно, що ідеї є однаковими. Доведення (першої частини) ВЧ-нерівності спирається на симетрування, а потім здійснює доведення, обумовлене даними, із застосуванням концентричних нерівностей (зокрема, Шаблон:Нп). Зацікавлений читач може перевірити теореми 12.4 та 12.5 книги Шаблон:Ref.

Джерела

• Шаблон:NoteШаблон:Cite book Шаблон:Ref-en
• Шаблон:Cite book Шаблон:Ref-en
• Шаблон:Note Шаблон:Cite book Шаблон:Ref-en
• Шаблон:NoteШаблон:Cite book Шаблон:Ref-en
• Див. джерела у статтях Шаблон:Нп, Шаблон:Нп, роздрібнена множина.
• Шаблон:NoteШаблон:Cite book Шаблон:Ref-en
• Шаблон:Cite paper Шаблон:Ref-en
• Шаблон:Cite paper Шаблон:Ref-en

Література

• Шаблон:Cite journal Шаблон:Ref-ru

Посилання

• Шаблон:Cite web Шаблон:Ref-ru