Розмірність Вапника-Червоненкіса
Матеріал із MachineLearning.
такожметодичні вказівкищодо використання РесурсуMachineLearning.ruу навчальному процесі.
Розмірність Вапника-Червоненкіса(ємність, VC-dimension) - це характеристика сімейства алгоритмів (або класифікуючих функцій) для вирішення задачі класифікації, що характеризує складність або ємність цього сімейства. Є одним із ключових понять у теорії Вапника-Червоненкіса про статистичне машинне навчання, названа на честь В. Н. Вапника та А. Я. Червоненкіса.
Зміст
Визначення
Якщо існує число таке, що функція зростання і , то воно називаєтьсяємністюаборозмірністю Вапника-Червоненкіса(VC-dimension) сімейства алгоритмів . Якщо такої кількості немає, то кажуть, що сімейство має нескінченну ємність.
Інше формулювання визначення (через розмаїтість): Нехай задано безліч об'єктів та деяке сімейство функцій (алгоритмів класифікації, вирішальних правил), які зіставляють кожному об'єкту множини один із двох заданих класів. Ємністю сімейства називається найбільше число , таке, що існує підмножина з об'єктів у множині , яке функції можуть розбити на два класи всіма можливими способами. Якщо ж такі підмножини існують для будь-якого великого, то ємність належить рівної нескінченності.
Якщо сімейство алгоритмів має кінцеву розмірність Вапника-Червоненкіса, таке сімейство називають класом Вапника-Червоненкіса.
Лінійний класифікатор
Як приклад, розглянемо завдання про розбиття точок на площині на два класи прямою лінією – це так званий лінійний класифікатор. Безліч будь-яких трьох точок, що не лежать на одній прямій, може бути розділена прямою лінією на двакласу всіма можливими способами (2 ³ = 8 способами, на малюнку нижче показано два з них), але безлічі з чотирьох і більше точок вже немає. Тому розмірність Вапника-Червоненкіса лінійного класифікатора на площині дорівнює трьом.
Загалом, розмірність Вапника-Червоненкіса сімейства лінійних класифікаторів у n-мірному просторі дорівнює n+1.
Відрізки на дійсній прямій
Клас алгоритмів - безліч відрізків на дійсній прямій. Крапка, що лежить усередині відрізка, класифікується позитивно, що лежить поза відрізком - негативно.
Очевидно, що існує безліч, що складається з двох елементів, що розбивається класом алгоритмів: будь-які дві різні точки на прямій можна покрити будь-яким із чотирьох можливих випадків (покриття лише першої точки, покриття тільки другої точки, покриття двох точок, покриття порожньої множини точок).
Не існує безлічі з трьох точок, які можна розбити, використовуючи безліч відрізків на прямій. Нехай точки впорядковані за значенням. Будь-який відрізок, що покриває точки і покриває також і точку .
Таким чином, розмірність Вапника-Червоненкіса множини відрізків на дійсній прямій дорівнює 2.
Випуклі d-кутники на площині
Клас алгоритмів - опуклі багатокутники з сторонами d на площині. Крапка, що лежить всередині багатокутника, класифікується позитивно, що лежить поза багатокутником - негативно.
Спочатку покажемо, що існує безліч 2d + 1 точок, які можуть бути розбиті за допомогою обраного класу алгоритмів. Розташуємо 2d + 1 точок рівномірно по колу. Для будь-якого маркування цих точок можна знайти d-кутник, що відповідає маркуванню. Якщо негативних точок більше ніж позитивних, використовуємо позитивні точки яквершини вершини d-кутника. Якщо буде більше позитивних точок, використовуємо дотичні до негативних точок як сторони d-кутника.
Не існує безлічі з 2d + 2 точок, які можна розбити, використовуючи клас опуклих багатокутників з сторонами d. Очевидно, що для точок, які не розташовані на колі, всілякі розбиття отримати не вдасться. Для точок, розташованих на колі, зробимо позначки, чергуючи позитивні та негативні. Така множина не можна розбити будь-яким d-кутником.
Таким чином, розмірність Вапника-Червоненкіса класу опуклих d-кутників на площині дорівнює 2d + 1. Якщо розглянути клас усіляких опуклих багатокутників на площині, то отримаємо розмірність Вапника-Червоненкіса, що дорівнює нескінченності.
Деякі співвідношення для розмірності Вапника-Червоненкіса
Передбачається, що всі класи алгоритмів містять алгоритми класифікації на два класи та діють на одній множині об'єктів.