У теорії статистичного навчання та [en], ВЧ-розмірність (розмірність Вапника — Червоненкіса, англ. VC dimension, Vapnik–Chervonenkis dimension) — це міра ємності (складності, виразної потужності, багатства або гнучкості, англ. capacity) простору функцій, яких може бути навчено певним алгоритмом статистичної класифікації. Вона визначається як потужність найбільшої множини точок, яку цей алгоритм може роздрібнити. Вона є ключовим поняттям теорії Вапника — Червоненкіса, первинно її визначили Володимир Вапник та [en].
Неформально ємність класифікаційної моделі пов'язана з тим, наскільки складною ця модель може бути. Наприклад, розгляньмо порівняння з порогом многочлену високого степеню: якщо многочлен у результаті обчислення дає додатне значення, то ця точка класифікується як позитивна, а інакше — як негативна. Многочлен високого степеню може бути хвилястим, тому він може добре допасовуватися до заданого набору тренувальних точок. Але можна очікувати, що цей класифікатор робитиме помилки на інших точках, бо він хвилястий занадто. Такий многочлен має високу ємність. Набагато простішою альтернативою є порівняння з порогом лінійної функції. Ця функція може не допасовуватися до тренувального набору добре, оскільки вона має низьку ємність. Нижче це поняття ємності зроблено строгим.
Роздрібнювання
Кажуть, що класифікаційна модель із деяким вектором параметрів роздрібнює (англ. shatter) множину точок даних , якщо для всіх призначень міток цим точкам існують такі , що модель не робить помилок при оцінці цієї множини точок даних.
ВЧ-розмірність моделі — це максимальне число точок, які може бути впорядковано таким чином, що роздрібнює їх. Формальніше, це таке максимальне ціле число , що деяку множину точок даних потужністю може бути роздрібнено моделлю .
Наприклад, розгляньмо як класифікаційну модель пряму лінію, — модель, яку використовує перцептрон. Ця лінія повинна розділяти позитивні й негативні точки даних. Існують множини з 3 точок, які й насправді може бути роздрібнено із застосуванням цієї моделі (роздрібнено може бути будь-які три точки, які не лежать на одній прямій). Проте множини з 4 точок може бути роздрібнено не всі: згідно теореми Радона, будь-які чотири точки може бути розбито на дві підмножини з опуклими оболонками, які перетинаються, так, що неможливо буде відділити одну з цих двох підмножин від іншої. Таким чином, ВЧ-розмірністю цього конкретного класифікатора є 3. Важливо пам'ятати, що хоча й можна обирати будь-яке впорядкування точок, це впорядкування не може змінюватися при спробі роздрібнення для певного призначення міток. Зауважте, що для цих трьох точок показано лише 3 з 23 = 8 можливих призначень міток.
роздрібнені 3 точки | для 4 точок неможливо |
Застосування
У теорії статистичного навчання
ВЧ-розмірність може передбачувати ймовірнісну верхню межу похибки перевірки (англ. test error) класифікаційної моделі. Вапник довів, що ймовірність відстані похибки перевірки від верхньої межі (на даних, які вибираються н. о. р. з одного й того ж розподілу як тренувальний набір) задається як
де є ВЧ-розмірністю класифікаційної моделі, , а є розміром тренувального набору (обмеження: ця формула є чинною, коли . Коли є більшим, похибка перевірки може бути набагато вищою за похибку тренування (англ. training error). Це пов'язано з перенавчанням).
ВЧ-розмірність з'являється також і в [en]. Простору двійкових функцій з ВЧ-розмірністю може бути навчено з
зразків, де є похибкою навчання, а є ймовірністю збою. Таким чином, вибіркова складність є лінійною функцією від ВЧ-розмірності простору гіпотез.
ВЧ-розмірність є одним із критичних параметрів розміру [en], який визначає складність алгоритмів наближення на їхній основі; множини покриття без скінченної ВЧ-розмірності не можуть мати ε-мереж взагалі.
Узагальнення
ВЧ-розмірність визначено для просторів бінарних функцій (функцій в {0,1}). Було запропоновано декілька узагальнень для просторів не бінарних функцій.
- Для багатозначних функцій (функцій в {0,...,n}) може застосовуватися . Бен-Девід та ін. представили узагальнення цього поняття.
- Для дійснозначних функцій (наприклад, функцій у дійсний проміжок, [0,1]) може застосовуватися псевдо-розмірність Полларда.
- [en] пропонує межі, подібні до ВЧ, і може іноді забезпечувати глибше розуміння, ніж розрахунки ВЧ-розмірності, таких статистичних методів, як ті, що використовують ядра.
Див. також
Вікісховище має мультимедійні дані за темою: ВЧ-розмірність |
- [en], обмеження на число множин у множинній системі в термінах ВЧ-розмірності.
- , обмеження на ВЧ-розмірність загальних пфаффових формул.
Примітки
Джерела
- Moore, Andrew. . Архів оригіналу за 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.; (1989). Learnability and the Vapnik–Chervonenkis dimension (PDF). Journal of the ACM. 36 (4): 929—865.[недоступне посилання з березня 2019] (англ.)
- Burges, Christopher. (PDF). Архів оригіналу (PDF) за 30 листопада 2016. Процитовано 21 листопада 2016. (containing information also for VC dimension) (англ.)
- . . Архів оригіналу за 20 грудня 2016. Процитовано 21 листопада 2016. (англ.)
- Natarajan, B.K. (1989). . 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 . (англ.)
- Pollard, D. (1984). Convergence of Stochastic Processes. Springer. ISBN . (англ.)
- Anthony, Martin; Bartlett, Peter L. (2009). Neural Network Learning: Theoretical Foundations. ISBN . (англ.)
- 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. (англ.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U teoriyi statistichnogo navchannya ta en VCh rozmirnist rozmirnist Vapnika Chervonenkisa angl VC dimension Vapnik Chervonenkis dimension ce mira yemnosti skladnosti viraznoyi potuzhnosti bagatstva abo gnuchkosti angl capacity prostoru funkcij yakih mozhe buti navcheno pevnim algoritmom statistichnoyi klasifikaciyi Vona viznachayetsya yak potuzhnist najbilshoyi mnozhini tochok yaku cej algoritm mozhe rozdribniti Vona ye klyuchovim ponyattyam teoriyi Vapnika Chervonenkisa pervinno yiyi viznachili Volodimir Vapnik ta en Neformalno yemnist klasifikacijnoyi modeli pov yazana z tim naskilki skladnoyu cya model mozhe buti Napriklad rozglyanmo porivnyannya z porogom mnogochlenu visokogo stepenyu yaksho mnogochlen u rezultati obchislennya daye dodatne znachennya to cya tochka klasifikuyetsya yak pozitivna a inakshe yak negativna Mnogochlen visokogo stepenyu mozhe buti hvilyastim tomu vin mozhe dobre dopasovuvatisya do zadanogo naboru trenuvalnih tochok Ale mozhna ochikuvati sho cej klasifikator robitime pomilki na inshih tochkah bo vin hvilyastij zanadto Takij mnogochlen maye visoku yemnist Nabagato prostishoyu alternativoyu ye porivnyannya z porogom linijnoyi funkciyi Cya funkciya mozhe ne dopasovuvatisya do trenuvalnogo naboru dobre oskilki vona maye nizku yemnist Nizhche ce ponyattya yemnosti zrobleno strogim RozdribnyuvannyaKazhut sho klasifikacijna model f displaystyle f iz deyakim vektorom parametriv 8 displaystyle theta rozdribnyuye angl shatter mnozhinu tochok danih x 1 x 2 x n displaystyle x 1 x 2 ldots x n yaksho dlya vsih priznachen mitok cim tochkam isnuyut taki 8 displaystyle theta sho model f displaystyle f ne robit pomilok pri ocinci ciyeyi mnozhini tochok danih VCh rozmirnist modeli f displaystyle f ce maksimalne chislo tochok yaki mozhe buti vporyadkovano takim chinom sho f displaystyle f rozdribnyuye yih Formalnishe ce take maksimalne cile chislo D displaystyle D sho deyaku mnozhinu tochok danih potuzhnistyu D displaystyle D mozhe buti rozdribneno modellyu f displaystyle f Napriklad rozglyanmo yak klasifikacijnu model pryamu liniyu model yaku vikoristovuye perceptron Cya liniya povinna rozdilyati pozitivni j negativni tochki danih Isnuyut mnozhini z 3 tochok yaki j naspravdi mozhe buti rozdribneno iz zastosuvannyam ciyeyi modeli rozdribneno mozhe buti bud yaki tri tochki yaki ne lezhat na odnij pryamij Prote mnozhini z 4 tochok mozhe buti rozdribneno ne vsi zgidno teoremi Radona bud yaki chotiri tochki mozhe buti rozbito na dvi pidmnozhini z opuklimi obolonkami yaki peretinayutsya tak sho nemozhlivo bude viddiliti odnu z cih dvoh pidmnozhin vid inshoyi Takim chinom VCh rozmirnistyu cogo konkretnogo klasifikatora ye 3 Vazhlivo pam yatati sho hocha j mozhna obirati bud yake vporyadkuvannya tochok ce vporyadkuvannya ne mozhe zminyuvatisya pri sprobi rozdribnennya dlya pevnogo priznachennya mitok Zauvazhte sho dlya cih troh tochok pokazano lishe 3 z 23 8 mozhlivih priznachen mitok rozdribneni 3 tochki dlya 4 tochok nemozhlivoZastosuvannyaU teoriyi statistichnogo navchannya VCh rozmirnist mozhe peredbachuvati jmovirnisnu verhnyu mezhu pohibki perevirki angl test error klasifikacijnoyi modeli Vapnik doviv sho jmovirnist vidstani pohibki perevirki vid verhnoyi mezhi na danih yaki vibirayutsya n o r z odnogo j togo zh rozpodilu yak trenuvalnij nabir zadayetsya yak Pr test error training error 1 N D log 2 N D 1 log h 4 1 h displaystyle 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 de D displaystyle D ye VCh rozmirnistyu klasifikacijnoyi modeli 0 h 1 displaystyle 0 leqslant eta leqslant 1 a N displaystyle N ye rozmirom trenuvalnogo naboru obmezhennya cya formula ye chinnoyu koli D N displaystyle D ll N Koli D displaystyle D ye bilshim pohibka perevirki mozhe buti nabagato vishoyu za pohibku trenuvannya angl training error Ce pov yazano z perenavchannyam VCh rozmirnist z yavlyayetsya takozh i v en Prostoru dvijkovih funkcij z VCh rozmirnistyu D displaystyle D mozhe buti navcheno z N 8 D ln 1 d ϵ displaystyle N Theta left frac D ln 1 over delta epsilon right zrazkiv de ϵ displaystyle epsilon ye pohibkoyu navchannya a d displaystyle delta ye jmovirnistyu zboyu Takim chinom vibirkova skladnist ye linijnoyu funkciyeyu vid VCh rozmirnosti prostoru gipotez V obchislyuvalnij geometriyi VCh rozmirnist ye odnim iz kritichnih parametriv rozmiru en yakij viznachaye skladnist algoritmiv nablizhennya na yihnij osnovi mnozhini pokrittya bez skinchennoyi VCh rozmirnosti ne mozhut mati e merezh vzagali UzagalnennyaVCh rozmirnist viznacheno dlya prostoriv binarnih funkcij funkcij v 0 1 Bulo zaproponovano dekilka uzagalnen dlya prostoriv ne binarnih funkcij Dlya bagatoznachnih funkcij funkcij v 0 n mozhe zastosovuvatisya Ben Devid ta in predstavili uzagalnennya cogo ponyattya Dlya dijsnoznachnih funkcij napriklad funkcij u dijsnij promizhok 0 1 mozhe zastosovuvatisya psevdo rozmirnist Pollarda en proponuye mezhi podibni do VCh i mozhe inodi zabezpechuvati glibshe rozuminnya nizh rozrahunki VCh rozmirnosti takih statistichnih metodiv yak ti sho vikoristovuyut yadra Div takozhVikishovishe maye multimedijni dani za temoyu VCh rozmirnist en obmezhennya na chislo mnozhin u mnozhinnij sistemi v terminah VCh rozmirnosti obmezhennya na VCh rozmirnist zagalnih pfaffovih formul PrimitkiVapnik 2000 Natarajan 1989 Ben David Cesa Bianchi ta Long 1992 Pollard 1984 Anthony ta Bartlett 2009 Morgenstern ta Roughgarden 2015 Karpinski ta Macintyre 1997 DzherelaMoore Andrew Arhiv originalu za 11 travnya 2005 Procitovano 21 listopada 2016 angl Vapnik Vladimir 2000 The nature of statistical learning theory Springer angl 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 angl Blumer A Ehrenfeucht A Haussler D 1989 Learnability and the Vapnik Chervonenkis dimension PDF Journal of the ACM 36 4 929 865 nedostupne posilannya z bereznya 2019 angl Burges Christopher PDF Arhiv originalu PDF za 30 listopada 2016 Procitovano 21 listopada 2016 containing information also for VC dimension angl Arhiv originalu za 20 grudnya 2016 Procitovano 21 listopada 2016 angl Natarajan B K 1989 Machine Learning 4 67 97 Arhiv originalu za 22 listopada 2016 Procitovano 21 listopada 2016 angl Ben David Shai Cesa Bianchi Nicolo 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 s 333 doi 10 1145 130385 130423 ISBN 089791497X angl Pollard D 1984 Convergence of Stochastic Processes Springer ISBN 9781461252542 angl Anthony Martin Bartlett Peter L 2009 Neural Network Learning Theoretical Foundations ISBN 9780521118620 angl Morgenstern Jamie H Roughgarden Tim 2015 On the Pseudo Dimension of Nearly Optimal Auctions NIPS arXiv 1506 03684 angl 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 angl