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

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

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

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

Кажуть, що класифікаційна модель $f$ із деяким вектором параметрів $\theta$ роздрібнює (англ. shatter) множину точок даних $(x_{1},x_{2},\ldots ,x_{n})$, якщо для всіх призначень міток цим точкам існують такі $\theta$, що модель $f$ не робить помилок при оцінці цієї множини точок даних.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

• Лема Зауера — Шелаха, обмеження на число множин у множинній системі в термінах ВЧ-розмірності.
• Теорема Карпинського — Макінтайра, обмеження на ВЧ-розмірність загальних пфаффових формул.

Джерела

• Moore, Andrew. VC dimension tutorial. Архів оригіналу за 11 травня 2005. Процитовано 21 листопада 2016. (англ.)
• Vapnik, Vladimir (2000). The nature of statistical learning theory. Springer. (англ.)
• Vapnik, V.; Chervonenkis, A. (1971). On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications. 16 (2): 264—280. (англ.)
• Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Warmuth, M. K. (1989). Learnability and the Vapnik–Chervonenkis dimension (PDF). Journal of the ACM. 36 (4): 929—865.^{[недоступне посилання з березня 2019]} (англ.)
• Burges, Christopher. Tutorial on SVMs for Pattern Recognition (PDF). Архів оригіналу (PDF) за 30 листопада 2016. Процитовано 21 листопада 2016. (containing information also for VC dimension) (англ.)
• Chazelle, Bernard. The Discrepancy Method. Архів оригіналу за 20 грудня 2016. Процитовано 21 листопада 2016. (англ.)
• Natarajan, B.K. (1989). On Learning sets and functions. Machine Learning. 4: 67—97. Архів оригіналу за 22 листопада 2016. Процитовано 21 листопада 2016. (англ.)
• Ben-David, Shai; Cesa-Bianchi, Nicolò; Long, Philip M. (1992). Characterizations of learnability for classes of {O, …, n}-valued functions. Proceedings of the fifth annual workshop on Computational learning theory - COLT '92. с. 333. doi:10.1145/130385.130423. ISBN 089791497X. (англ.)
• Pollard, D. (1984). Convergence of Stochastic Processes. Springer. ISBN 9781461252542. (англ.)
• Anthony, Martin; Bartlett, Peter L. (2009). Neural Network Learning: Theoretical Foundations. ISBN 9780521118620. (англ.)
• Morgenstern, Jamie H.; Roughgarden, Tim (2015). On the Pseudo-Dimension of Nearly Optimal Auctions. NIPS. arXiv:1506.03684. (англ.)
• Karpinski, Marek; Macintyre, Angus (February 1997). Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks. Journal of Computer and System Sciences. 54 (1): 169—176. doi:10.1006/jcss.1997.1477. (англ.)