Теорію Вапника — Червоненкіса (, відому також як ВЧ-теорія, ) було розроблено протягом 1960–1990 років Володимиром Вапником та . Ця теорія є різновидом теорії обчислювального навчання, яка намагається пояснювати процес навчання зі статистичної точки зору.
ВЧ-теорія пов'язана з теорією статистичного навчання та з . До ВЧ-теорію застосовували, серед інших, та Володимир Вапник.
Введення
ВЧ-теорія охоплює щонайменше чотири частини (як пояснено в «Природі теорії статистичного навчання»):
Теорію спроможності процесів навчання Якими є (необхідні та достатні) умови спроможності процесу навчання на основі принципу мінімізації емпіричного ризику? Неасимптотичну теорію темпу збіжності процесів навчання Наскільки швидким є темп збіжності процесу навчання? Теорію керування узагальнювальною спроможністю процесів навчання Як можна керувати темпом збіжності (узагальнювальною спроможністю) процесу навчання? Теорію побудови машин, які вчаться Як можна будувати алгоритми, які керують узагальнювальною спроможністю?
ВЧ-теорія є однією з основних підгалузей теорії статистичного навчання. Одним із її головних застосувань у теорії статистичного навчання є забезпечення умов узагальнення для алгоритмів навчання. З цієї точки зору ВЧ-теорія пов'язана зі , яка є альтернативним підходом для характеризування узагальнення.
Крім того, ВЧ-теорія та ВЧ-розмірність відіграють важливу роль у теорії у випадку процесів, індексованих за ВЧ-класами. Можливо, вони є найважливішими застосуваннями ВЧ-теорії, вони застосовуються в доведенні узагальнення. Буде представлено кілька методик, які широко використовуються в емпіричних процесах та ВЧ-теорії. Обговорення в основному ґрунтується на книзі «Слабка збіжність та емпіричні процеси: із застосуваннями до статистики».
Огляд ВЧ-теорії в емпіричних процесах
Довідка про емпіричні процеси
Нехай є випадковими елементами, визначеними на вимірному просторі . Для міри встановімо:
Питання вимірності тут ігноруватимуться, технічні деталі див. у . Покладімо, що є класом вимірних функцій , і визначмо
Визначмо емпіричну міру
де в даному випадку відповідає . Емпірична міра породжує відображення , що задається як
Тепер припустімо, що є справжнім розподілом, що лежить в основі даних, який є невідомим. Теорія емпіричних процесів спрямована на ідентифікацію класів , для яких виконуються такі твердження, як наступні:
рівномірний закон великих чисел:
рівномірна центральна гранична теорема:
В першому випадку називається (), а в другому (за припущення ) клас називається донскеровим (), або -донскеровим. Очевидно, що клас Донскера є класом Гливенка — Кантеллі в теорії ймовірностей, якщо застосувати теорему Слуцького.
Ці твердження справедливі для єдиної згідно стандартних доводів ЗВЧ та ЦГТ в умовах регулярності, а складність в емпіричних процесах виникає тому, що робляться спільні твердження для всіх . Тоді, інтуїтивно, множина не може бути занадто великою, і, як виявляється, дуже важливу роль відіграє геометрія .
Одним зі способі вимірювання того, наскільки великою є множина функцій , є застосування так званих . Число покриття
є мінімальним числом куль , необхідних для покриття множини (тут, очевидно, припускається існування норми на , на основі якої це робиться). Ентропія є логарифмом числа покриття.
Нижче наведено дві достатні умови, за яких можна довести, що множина є Гливенка — Кантеллі, або донскеровою.
Клас є -Гливенка — Кантеллі, якщо він є -вимірюваним такою обгорткою , що та виконується
Наступна умова є версією відомої . Якщо є таким класом функцій, що
то є -донскеровим для будь-якої такої міри ймовірності , що . В крайньому інтегралі цей запис означає
.
Симетрування
Більшість обґрунтувань того, як обмежувати емпіричні процеси, покладаються на симетрування, максимальні та концентричні нерівності, та зчеплювання. Симетрування зазвичай є першим кроком цих доведень, і оскільки воно використовується в багатьох доведеннях машинного навчання із обмеження функцій емпіричних втрат (включно із доведенням ВЧ-нерівності, що обговорюється в наступному розділі), його представлено тут.
Розгляньмо емпіричний процес
Виявляється, що існує зв'язок між цим емпіричним, та наступним симетрованим процесом:
Цей симетрований процес є процесом Радемахера, обумовленим даними . Отже, згідно , він є субґаусовим процесом.
Лема (симетрування). Для будь-якої неспадної опуклої та класу вимірних функцій ,
Доведення леми симетрування покладається на введення незалежних копій первинних змінних (які іноді називають вибіркою-привидом) та заміну виразу під математичним сподіванням в лівій частині нерівності цими копіями. Після застосування нерівності Єнсена може бути введено інші знаки (звідси й назва — симетрування) без зміни математичного сподівання. Нижче наведено доведення, через його повчальний характер.
Типовий спосіб доведення емпіричних ЦГТ спочатку застосовує симетрування для передачі емпіричного процесу до , а потім здійснює доведення обумовлено даними, використовуючи той факт, що процеси Радемахера є простими процесами з гарними властивостями.
ВЧ-зв'язок
Виявляється, існує чарівний зв'язок між деякими комбінаторними властивостями множини , та числами ентропії. Числа рівномірного покриття можуть контролюватися поняттям класів множин Вапника — Червоненкіса (), або, коротше, ВЧ-множин ().
Розгляньмо набір підмножин вибіркового простору . Кажуть, що вихоплює () певну підмножину скінченної множини , якщо для деякого . Кажуть, що роздрібнює () , якщо він вихоплює кожну з її підмножин. ВЧ-індекс (, подібний до ВЧ-розмірності + 1 для відповідним чином вибраної класифікаторної множини) набору — це найменше , для якого жодна множина розміру не роздрібнюється набором .
Далі, стверджує, що число підмножин, вихоплюваних ВЧ-класом , задовольняє
Що є поліноміальним числом підмножин, а не експоненційним. Інтуїтивно це означає, що зі скінченності ВЧ-індексу випливає, що має явно спрощену структуру.
Подібне обмеження може бути показано (з іншим сталим, незмінним співвідношенням) для так званих ВЧ-підграфікових класів (). Для функції є така підмножина , що . Набір називається ВЧ-підграфіковим класом, якщо всі підграфіки формують ВЧ-клас.
Розгляньмо множину індикаторних функцій в для дискретного емпіричного типу міри (або, рівнозначно, для будь-якої міри ймовірності ). Тоді може бути показано, що, на диво, для
Далі розгляньмо симетричну опуклу оболонку множини : , яка є набором функцій вигляду з . Тоді якщо
то наступне є вірним для опуклої оболонки :
Важливим наслідком цього факту є те, що
чого якраз достатньо для того, щоби інтеграл ентропії сходився, і відтак клас був -донскеровим.
Нарешті, розглядається приклад ВЧ-підграфікового класу. Будь-який векторний простір вимірних функцій , який має скінченну розмірність, є ВЧ-підграфіком індексу, меншого або рівного .
Існують узагальнення поняття ВЧ-підграфових класів, наприклад, існує поняття псевдорозмірності. Зацікавлені читачі можуть подивитися .
ВЧ-нерівність
Розглядається подібна постановка, звичніша для машинного навчання. Нехай є простором ознак, а . Функція називається класифікатором. Нехай є множиною класифікаторів. Подібно до попереднього розділу, визначмо коефіцієнт роздрібнювання (, відомий також як функція росту, ):
Зауважте, що існує взаємно однозначне відображення між кожною з функцій в , та множиною, на якій ця функція дорівнює 1. Отже, ми можемо визначити як набір підмножин, отриманий з наведеного вище відображення для кожної . Таким чином, з точки зору попереднього розділу, коефіцієнт роздрібнювання в точності дорівнює
.
З цієї рівності разом із випливає, що має бути поліноміальним в , для достатньо великого , за умови, що набір має скінченний ВЧ-індекс.
Нехай є спостережуваним набором даних. Припустімо, що ці дані породжено невідомим розподілом імовірності . Визначмо як очікувані втрати 0/1. Звісно, оскільки є загалом невідомим, ми не маємо доступу до . Проте емпіричний ризик (), заданий як
безумовно, може бути оцінено. Тоді маємо наступну теорему:
Теорема (ВЧ-нерівність)
Для бінарної класифікації та функції втрат 0/1 ми маємо наступні обмеження узагальнення:
Іншими словами, ВЧ-нерівність каже, що при збільшенні вибірки, за умови, що має скінченну ВЧ-розмірність, емпіричний ризик 0/1 стає добрим замінником очікуваного ризику 0/1. Зауважте, що обидві праві частини цих двох нерівностей збігатимуться до 0 за умови, що зростає поліноміально в .
Очевидним є зв'язок між цією системою та системою емпіричних процесів. Тут ми маємо справу з видозміненим емпіричним процесом
але не дивно, що ідеї є однаковими. Доведення (першої частини) ВЧ-нерівності спирається на симетрування, а потім здійснює доведення, обумовлене даними, із застосуванням концентричних нерівностей (зокрема, ). Зацікавлений читач може перевірити теореми 12.4 та 12.5 книги .
Джерела
Див. джерела у статтях , , роздрібнена множина.
Література
Посилання