Перегляд вихідного коду сторінки ВЧ-розмірність

У [[Теорія Вапника — Червоненкіса|теорії статистичного навчання]] та {{нп|Теорія обчислювального навчання|теорії обчислювального навчання||Computational learning theory}}, '''ВЧ-розмірність''' ('''розмірність Вапника&nbsp;— Червоненкіса''', {{lang-en|VC dimension, Vapnik–Chervonenkis dimension}})&nbsp;— це міра '''ємності''' (складності, виразної потужності, багатства або гнучкості, {{lang-en|capacity}}) простору функцій, яких може бути навчено певним [[алгоритм]]ом [[Статистична класифікація|статистичної класифікації]]. Вона визначається як [[Потужність множини|потужність]] найбільшої множини точок, яку цей алгоритм може [[Роздрібнювання (машинне навчання)|роздрібнити]]. Вона є ключовим поняттям [[Теорія Вапника — Червоненкіса|теорії Вапника&nbsp;— Червоненкіса]], первинно її визначили [[Вапник Володимир Наумович|Володимир Вапник]] та {{нп|Олексій Якович Червоненкіс|Олексій Червоненкіс||Alexey Chervonenkis}}.

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

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

Кажуть, що класифікаційна модель <math>f</math> із деяким вектором параметрів <math>\theta</math> ''роздрібнює'' ({{lang-en|shatter}}) множину точок даних <math>(x_1,x_2,\ldots,x_n)</math>, якщо для всіх призначень міток цим точкам існують такі <math>\theta</math>, що модель <math>f</math> не робить помилок при оцінці цієї множини точок даних.

ВЧ-розмірність моделі <math>f</math>&nbsp;— це максимальне число точок, які може бути впорядковано таким чином, що <math>f</math> роздрібнює їх. Формальніше, це таке максимальне ціле число <math>D</math>, що деяку множину точок даних [[Потужність множини|потужністю]] <math>D</math> може бути роздрібнено моделлю <math>f</math>.

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

{| border="0" cellpadding="4" cellspacing="0"
|- style="text-align:center;"
|  style="background:#dfd;"| [[File:VC1.svg]]
|  style="background:#dfd;"| [[File:VC2.svg]]
|  style="background:#dfd;"| [[File:VC3.svg]]
|  style="background:#fdd;"| [[File:VC4.svg]]
|- style="text-align:center;"
| colspan="3"  style="background:#dfd;"| '''роздрібнені 3 точки'''
|  style="background:#fdd;"| '''для 4 точок неможливо'''
|}

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

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

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

: <math> \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,</math>

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

ВЧ-розмірність з'являється також і в {{нп|Межі вибіркової складності|межах вибіркової складності||Sample-complexity bounds}}. Простору двійкових функцій з ВЧ-розмірністю <math>D</math> може бути навчено з

: <math> N = \Theta\left(\frac{D + \ln{1\over \delta}}{\epsilon}\right)</math>

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

=== В [[Обчислювальна геометрія|обчислювальній геометрії]] ===

ВЧ-розмірність є одним із критичних параметрів розміру {{нп|ε-мережа (обчислювальна геометрія)|ε-мереж||ε-net (computational geometry)}}, який визначає складність алгоритмів наближення на їхній основі; множини покриття без скінченної ВЧ-розмірності не можуть мати ε-мереж взагалі.

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

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

* Для багатозначних функцій (функцій в {0,...,n}) може застосовуватися {{нпні|розмірність Натараджана|||Natarajan dimension}}.{{sfn|Natarajan|1989}} Бен-Девід та ін.{{sfn|Ben-David|Cesa-Bianchi|Long|1992}} представили узагальнення цього поняття.
* Для дійснозначних функцій (наприклад, функцій у [[Дійсні числа|дійсний]] проміжок, [0,1]) може застосовуватися псевдо-розмірність Полларда.{{sfn|Pollard|1984}}{{sfn|Anthony|Bartlett|2009}}{{sfn|Morgenstern|Roughgarden|2015}}
* {{нп|Складність Радемахера|||Rademacher complexity}} пропонує межі, подібні до ВЧ, і може іноді забезпечувати глибше розуміння, ніж розрахунки ВЧ-розмірності, таких статистичних методів, як ті, що використовують [[Ядрові методи|ядра]].

== Див. також ==
{{commons category|Vapnik-Chervonenkis dimension}}
* {{нп|Лема Зауера — Шелаха|Лема Зауера&nbsp;— Шелаха||Sauer–Shelah lemma}}, обмеження на число множин у множинній системі в термінах ВЧ-розмірності.
* {{нпні|Теорема Карпинського — Макінтайра|Теорема Карпинського&nbsp;— Макінтайра||Karpinski-Macintyre theorem}},{{sfn|Karpinski|Macintyre|1997}} обмеження на ВЧ-розмірність загальних пфаффових формул.

== Примітки ==
{{Примітки}}

== Джерела ==

* {{cite web|first=Andrew|last=Moore|url=http://www-2.cs.cmu.edu/~awm/tutorials/vcdim.html|title=VC dimension tutorial|accessdate=21 листопада 2016|archiveurl=https://web.archive.org/web/20050511031259/http://www-2.cs.cmu.edu/~awm/tutorials/vcdim.html|archivedate=11 травня 2005|deadurl=yes}} {{ref-en}}
* {{cite book|last=Vapnik|first=Vladimir|title=The nature of statistical learning theory|publisher=Springer|year=2000|ref=harv}} {{ref-en}}
* {{cite journal|first1=V.|last1=Vapnik|first2=A.|last2=Chervonenkis|title=On the uniform convergence of relative frequencies of events to their probabilities|journal=Theory of Probability and its Applications|volume=16|issue=2|pages=264–280|year=1971}} {{ref-en}}
* {{cite journal|first1=A.|last1=Blumer|first2=A.|last2=Ehrenfeucht|first3=D.|last3=Haussler|authorlink4=Манфред Клаус Вармут|first4=M. K.|last4=Warmuth|title=Learnability and the Vapnik–Chervonenkis dimension|journal=Journal of the ACM|volume=36|issue=4|pages=929–865|year=1989|url=http://l2r.cs.uiuc.edu/~danr/Teaching/CS446-16/Papers/p929-blumer.pdf}}{{Недоступне посилання|date=березень 2019 |bot=InternetArchiveBot }} {{ref-en}}
* {{cite web|first=Christopher|last=Burges|title=Tutorial on SVMs for Pattern Recognition|url=http://research.microsoft.com/en-us/um/people/cburges/papers/svmtutorial.pdf|accessdate=21 листопада 2016|archive-date=30 листопада 2016|archive-url=https://web.archive.org/web/20161130181730/http://research.microsoft.com/en-us/um/people/cburges/papers/svmtutorial.pdf}} (containing information also for VC dimension) {{ref-en}}
* {{cite web|first=Bernard|last=Chazelle|authorlink=Бернар Шазель|title=The Discrepancy Method|url=http://www.cs.princeton.edu/~chazelle/book.html|accessdate=21 листопада 2016|archive-date=20 грудня 2016|archive-url=https://web.archive.org/web/20161220030558/http://www.cs.princeton.edu/~chazelle/book.html}} {{ref-en}}
* {{cite journal|first=B.K.|last=Natarajan|title=On Learning sets and functions|journal=Machine Learning|volume=4|pages=67-97|year=1989|url=http://link.springer.com/article/10.1007%2FBF00114804#page-1|ref=harv|accessdate=21 листопада 2016|archive-date=22 листопада 2016|archive-url=https://web.archive.org/web/20161122153233/http://link.springer.com/article/10.1007%2FBF00114804#page-1}} {{ref-en}}
* {{cite conference|doi=10.1145/130385.130423|chapter=Characterizations of learnability for classes of {O, …, n}-valued functions|title=Proceedings of the fifth annual workshop on Computational learning theory  - COLT '92|pages=333|year=1992|last1=Ben-David|first1=Shai|last2=Cesa-Bianchi|first2=Nicolò|last3=Long|first3=Philip M.|isbn=089791497X|ref=harv}} {{ref-en}}
* {{cite book|last=Pollard|first=D.|title=Convergence of Stochastic Processes|year=1984|publisher=Springer|isbn=9781461252542|ref=harv}} {{ref-en}}
* {{cite book|first1=Martin|last1=Anthony|first2=Peter L.|last2=Bartlett|title=Neural Network Learning: Theoretical Foundations|year=2009|isbn=9780521118620|ref=harv}} {{ref-en}}
* {{cite conference|title=On the Pseudo-Dimension of Nearly Optimal Auctions|year=2015|conference=NIPS|url=http://papers.nips.cc/paper/5766-on-the-pseudo-dimension-of-nearly-optimal-auctions|arxiv=1506.03684|first1=Jamie H.|last1=Morgenstern|first2=Tim|last2=Roughgarden|ref=harv}} {{ref-en}}
* {{cite journal|first1=Marek|last1=Karpinski|first2=Angus|last2=Macintyre|title=Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks |journal=Journal of Computer and System Sciences|volume=54|issue=1|year=1997|date=February 1997|pages=169-176|url=http://www.sciencedirect.com/science/article/pii/S002200009791477X|doi=10.1006/jcss.1997.1477|ref=harv}} {{ref-en}}

[[Категорія:Розмірність]]
[[Категорія:Статистична класифікація]]
[[Категорія:Теорія обчислювального навчання]]
[[Категорія:Машинне навчання]] <!-- Поки відсутня [[:Категорія:Теорія обчислювального навчання]] -->
[[Категорія:Міри складності]]