ВЧ-розмірність

У теорії статистичного навчання та Шаблон:Нп, ВЧ-розмірність (розмірність Вапника — Червоненкіса, Шаблон:Lang-en) — це міра ємності (складності, виразної потужності, багатства або гнучкості, Шаблон:Lang-en) простору функцій, яких може бути навчено певним алгоритмом статистичної класифікації. Вона визначається як потужність найбільшої множини точок, яку цей алгоритм може роздрібнити. Вона є ключовим поняттям теорії Вапника — Червоненкіса, первинно її визначили Володимир Вапник та Шаблон:Нп.

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

Роздрібнювання

Кажуть, що класифікаційна модель $f$ із деяким вектором параметрів $\theta$ роздрібнює (Шаблон:Lang-en) множину точок даних $(x_1,x_2,\dots ,x_n)$, якщо для всіх призначень міток цим точкам існують такі $\theta$, що модель $f$ не робить помилок при оцінці цієї множини точок даних.

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

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

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

Застосування

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

ВЧ-розмірність може передбачувати ймовірнісну верхню межу похибки перевірки (Шаблон:Lang-en) класифікаційної моделі. ВапникШаблон:Sfn довів, що ймовірність відстані похибки перевірки від верхньої межі (на даних, які вибираються н. о. р. з одного й того ж розподілу як тренувальний набір) задається як

$\mathrm{Pr}(\text{test error}⩽\text{training error}+\sqrt{\frac{1}{N}[D(\log \left(\frac{2N}{D}\right)+1)-\log \left(\frac{\eta }{4}\right)]})=1-\eta ,$

де $D$ є ВЧ-розмірністю класифікаційної моделі, $0⩽\eta ⩽1$, а $N$ є розміром тренувального набору (обмеження: ця формула є чинною, коли $D\ll N$. Коли $D$ є більшим, похибка перевірки може бути набагато вищою за похибку тренування (Шаблон:Lang-en). Це пов'язано з перенавчанням).

ВЧ-розмірність з'являється також і в Шаблон:Нп. Простору двійкових функцій з ВЧ-розмірністю $D$ може бути навчено з

$N=\mathrm{\Theta }\left(\frac{D+\ln \frac{1}{\delta }}{ϵ}\right)$

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

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

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

Узагальнення

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

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

Див. також

• Шаблон:Нп, обмеження на число множин у множинній системі в термінах ВЧ-розмірності.
• Шаблон:Нпні,Шаблон:Sfn обмеження на ВЧ-розмірність загальних пфаффових формул.

Джерела

• Шаблон:Cite web Шаблон:Ref-en
• Шаблон:Cite book Шаблон:Ref-en
• Шаблон:Cite journal Шаблон:Ref-en
• Шаблон:Cite journalШаблон:Недоступне посилання Шаблон:Ref-en
• Шаблон:Cite web (containing information also for VC dimension) Шаблон:Ref-en
• Шаблон:Cite web Шаблон:Ref-en
• Шаблон:Cite journal Шаблон:Ref-en
• Шаблон:Cite conference Шаблон:Ref-en
• Шаблон:Cite book Шаблон:Ref-en
• Шаблон:Cite book Шаблон:Ref-en
• Шаблон:Cite conference Шаблон:Ref-en
• Шаблон:Cite journal Шаблон:Ref-en