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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Введення[ред.ред. код]

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

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

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

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

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

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

Нехай є випадковими елементами, визначеними на вимірному просторі . Для міри Q встановімо:

Питання вимірності тут ігноруватимуться, технічні деталі див. у [3]. Покладімо, що є класом вимірних функцій , і визначмо

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

де δ в даному випадку відповідає мірі Дірака[en]. Емпірична міра породжує відображення , що задається як

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

В першому випадку називається класом Гливенка — Кантеллі[en] (англ. Glivenko-Cantelli class), а в другому (за припущення ) клас називається донскеровим (англ. Donsker class), або P-донскеровим. Очевидно, що клас Донскера є класом Гливенка — Кантеллі в теорії ймовірностей, якщо застосувати теорему Слуцького.

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

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

є мінімальним числом куль , необхідних для покриття множини (тут, очевидно, припускається існування норми на , на основі якої це робиться). Ентропія є логарифмом числа покриття.

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

Клас є P-Гливенка — Кантеллі, якщо він є P-мірним такою обгорткою F, що та виконується

Наступна умова є версією славетної теореми Дадлі[en]. Якщо є таким класом функцій, що

то є P-донскеровим для будь-якої такої міри ймовірності P, що . В крайньому інтегралі цей запис означає

.

Симетрування[ред.ред. код]

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

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

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

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

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

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

Типовий спосіб доведення емпіричних ЦГТ спочатку застосовує симетрування для передачі емпіричного процесу до , а потім здійснює доведення обумовлено даними, використовуючи той факт, що процеси Радемахера є простими процесами з гарними властивостями.

ВЧ-зв'язок[ред.ред. код]

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

Розгляньмо набір підмножин вибіркового простору . Кажуть, що вихоплює (англ. pick out) певну підмножину скінченної множини , якщо для деякого . Кажуть, що роздрібнює (англ. shatter) S, якщо він вихоплює кожну з її 2n підмножин. ВЧ-індекс (англ. VC-index, подібний до ВЧ-розмірності + 1 для відповідним чином вибраної класифікаторної множини) набору  — це найменше n, для якого жодна множина розміру n не роздрібнюється набором .

Далі, лема Зауера[en] стверджує, що число підмножин, вихоплюваних ВЧ-класом , задовольняє

Що є поліноміальним числом підмножин, а не експоненційним. Інтуїтивно це означає, що зі скінченності ВЧ-індексу випливає, що має явно спрощену структуру.

Подібне обмеження може бути показано (з іншим сталим, незмінним співвідношенням) для так званих ВЧ-підграфікових класів (англ. VC subgraph classes). Для функції підграфіком[en] є така підмножина , що . Набір називається ВЧ-підграфіковим класом, якщо всі підграфіки формують ВЧ-клас.

Розгляньмо множину індикаторних функцій в для дискретного емпіричного типу міри Q (або, рівнозначно, для будь-якої міри ймовірності Q). Тоді може бути показано, що, на диво, для

Далі розгляньмо симетричну опуклу оболонку множини : , яка є набором функцій вигляду з . Тоді якщо

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

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

чого якраз достатньо для того, щоби інтеграл ентропії сходився, і відтак клас був P-донскеровим.

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

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

ВЧ-нерівність[ред.ред. код]

Розглядається подібна постановка, звичніша для машинного навчання. Нехай є простором ознак, а . Функція називається класифікатором. Нехай є множиною класифікаторів. Подібно до попереднього розділу, визначмо коефіцієнт роздрібнювання (англ. shattering coefficient, відомий також як функція росту, англ. growth function):

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

.

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

Нехай є спостережуваним набором даних. Припустімо, що ці дані породжено невідомим розподілом імовірності . Визначмо як очікувані втрати 0/1. Звісно, оскільки є загалом невідомим, ми не маємо доступу до . Проте емпіричний ризик (англ. empirical risk), заданий як

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

Теорема (ВЧ-нерівність)[ред.ред. код]

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

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

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

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

Джерела[ред.ред. код]

Література[ред.ред. код]

Посилання[ред.ред. код]