У теорії статистичного навчання та теорії обчислювального навчання[en], ВЧ-розмірність (розмірність Вапника — Червоненкіса, англ. VC dimension, Vapnik–Chervonenkis dimension) — це міра ємності (складності, виразної потужності, багатства або гнучкості, англ. capacity) простору функцій, яких може бути навчено певним алгоритмом статистичної класифікації. Вона визначається як потужність найбільшої множини точок, яку цей алгоритм може роздрібнити. Вона є ключовим поняттям теорії Вапника — Червоненкіса, первинно її визначили Володимир Вапник та Олексій Червоненкіс[en].

Неформально ємність класифікаційної моделі пов'язана з тим, наскільки складною ця модель може бути. Наприклад, розгляньмо порівняння з порогом многочлену високого степеню: якщо многочлен у результаті обчислення дає додатне значення, то ця точка класифікується як позитивна, а інакше — як негативна. Многочлен високого степеню може бути хвилястим, тому він може добре допасовуватися до заданого набору тренувальних точок. Але можна очікувати, що цей класифікатор робитиме помилки на інших точках, бо він хвилястий занадто. Такий многочлен має високу ємність. Набагато простішою альтернативою є порівняння з порогом лінійної функції. Ця функція може не допасовуватися до тренувального набору добре, оскільки вона має низьку ємність. Нижче це поняття ємності зроблено строгим.

РоздрібнюванняРедагувати

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

ВЧ-розмірність моделі   — це максимальне число точок, які може бути впорядковано таким чином, що   роздрібнює їх. Формальніше, це таке максимальне ціле число  , що деяку множину точок даних потужністю   може бути роздрібнено моделлю  .

Наприклад, розгляньмо як класифікаційну модель пряму лінію, — модель, яку використовує перцептрон. Ця лінія повинна розділяти позитивні й негативні точки даних. Існують множини з 3 точок, які й насправді може бути роздрібнено із застосуванням цієї моделі (роздрібнено може бути будь-які три точки, які не лежать на одній прямій). Проте множини з 4 точок може бути роздрібнено не всі: згідно теореми Радона, будь-які чотири точки може бути розбито на дві підмножини з опуклими оболонками, які перетинаються, так, що неможливо буде відділити одну з цих двох підмножин від іншої. Таким чином, ВЧ-розмірністю цього конкретного класифікатора є 3. Важливо пам'ятати, що хоча й можна обирати будь-яке впорядкування точок, це впорядкування не може змінюватися при спробі роздрібнення для певного призначення міток. Зауважте, що для цих трьох точок показано лише 3 з 23 = 8 можливих призначень міток.

       
роздрібнені 3 точки для 4 точок неможливо

ЗастосуванняРедагувати

У теорії статистичного навчанняРедагувати

ВЧ-розмірність може передбачувати ймовірнісну верхню межу похибки перевірки (англ. test error) класифікаційної моделі. Вапник[1] довів, що ймовірність відстані похибки перевірки від верхньої межі (на даних, які вибираються н. о. р. з одного й того ж розподілу як тренувальний набір) задається як

 

де   є ВЧ-розмірністю класифікаційної моделі,  , а   є розміром тренувального набору (обмеження: ця формула є чинною, коли  . Коли   є більшим, похибка перевірки може бути набагато вищою за похибку тренування (англ. training error). Це пов'язано з перенавчанням).

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

 

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

В обчислювальній геометріїРедагувати

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

УзагальненняРедагувати

ВЧ-розмірність визначено для просторів бінарних функцій (функцій в {0,1}). Було запропоновано декілька узагальнень для просторів не бінарних функцій.

  • Для багатозначних функцій (функцій в {0,...,n}) може застосовуватися розмірність Натараджана.[2] Бен-Девід та ін.[3] представили узагальнення цього поняття.
  • Для дійснозначних функцій (наприклад, функцій у дійсний проміжок, [0,1]) може застосовуватися псевдо-розмірність Полларда.[4][5][6]
  • Складність Радемахера[en] пропонує межі, подібні до ВЧ, і може іноді забезпечувати глибше розуміння, ніж розрахунки ВЧ-розмірності, таких статистичних методів, як ті, що використовують ядра.

Див. такожРедагувати

ПриміткиРедагувати

ДжерелаРедагувати