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

Теорію Вапника — Червоненкіса (англ. 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}$ , і визначмо

{\displaystyle \|Q\|_{\mathcal {F}}=\sup\{\vert Qf\vert \

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

\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 \to 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 n$ підмножин. ВЧ-індекс (англ. 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$ з розмірністю $n - 1$ . Візьмімо $a \neq 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. (англ.)
↑ 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). Обзор современных исследований по проблеме качества обучения алгоритмов. Таврический вестник информатики и математики 1. (рос.)

Посилання

Теория Вапника-Червоненкиса. MachineLearning.ru. (рос.)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.