Теорію Вапника — Червоненкіса (англ. Vapnik–Chervonenkis theory, відому також як ВЧ-теорія, англ. VC theory) було розроблено протягом 1960–1990 років Володимиром Вапником та [en]. Ця теорія є різновидом [en], яка намагається пояснювати процес навчання зі статистичної точки зору.
ВЧ-теорія пов'язана з теорією статистичного навчання та з [en]. До [en] ВЧ-теорію застосовували, серед інших, [en] та Володимир Вапник.
Введення
ВЧ-теорія охоплює щонайменше чотири частини (як пояснено в «Природі теорії статистичного навчання»[1]):
- Теорію [en] процесів навчання
- Якими є (необхідні та достатні) умови узгодженості процесу навчання на основі принципу мінімізації емпіричного ризику?
- Неасимптотичну теорію темпу збіжності процесів навчання
- Наскільки швидким є темп збіжності процесу навчання?
- Теорію керування узагальнювальною спроможністю процесів навчання
- Як можна керувати темпом збіжності ((узагальнювальною) спроможністю) процесу навчання?
- Теорію побудови машин, які вчаться
- Як можна будувати алгоритми, які керують узагальнювальною спроможністю?
ВЧ-теорія є однією з основних підгалузей теорії статистичного навчання. Одним із її головних застосувань у теорії статистичного навчання є забезпечення умов (узагальнення) для алгоритмів навчання. З цієї точки зору ВЧ-теорія пов'язана зі [en], яка є альтернативним підходом для характеризування узагальнення.
Крім того, ВЧ-теорія та ВЧ-розмірність відіграють важливу роль у теорії [en] у випадку процесів, індексованих за ВЧ-класами. Можливо, вони є найважливішими застосуваннями ВЧ-теорії, вони застосовуються в доведенні узагальнення. Буде представлено кілька методик, які широко використовуються в емпіричних процесах та ВЧ-теорії. Обговорення в основному ґрунтується на книзі «Слабка збіжність та емпіричні процеси: із застосуваннями до статистики».[2]
Огляд ВЧ-теорії в емпіричних процесах
Довідка про емпіричні процеси
Нехай є випадковими елементами, визначеними на вимірному просторі . Для міри Q встановімо:
Питання вимірності тут ігноруватимуться, технічні деталі див. у [3]. Покладімо, що є класом вимірних функцій , і визначмо
Визначмо емпіричну міру
де δ в даному випадку відповідає [en]. Емпірична міра породжує відображення , що задається як
Тепер припустімо, що P є справжнім розподілом, що лежить в основі даних, який є невідомим. Теорія емпіричних процесів спрямована на ідентифікацію класів , для яких виконуються такі твердження, як наступні:
- рівномірний закон великих чисел:
- рівномірна центральна гранична теорема:
В першому випадку називається [en] (англ. Glivenko-Cantelli class), а в другому (за припущення ) клас називається донскеровим (англ. Donsker class), або P-донскеровим. Очевидно, що клас Донскера є класом Гливенка — Кантеллі в теорії ймовірностей, якщо застосувати теорему Слуцького.
Ці твердження справедливі для єдиної згідно стандартних доводів ЗВЧ та ЦГТ в умовах регулярності, а складність в емпіричних процесах виникає тому, що робляться спільні твердження для всіх . Тоді, інтуїтивно, множина не може бути занадто великою, і, як виявляється, дуже важливу роль відіграє геометрія .
Одним зі способі вимірювання того, наскільки великою є множина функцій , є застосування так званих [en]. Число покриття
є мінімальним числом куль , необхідних для покриття множини (тут, очевидно, припускається існування норми на , на основі якої це робиться). Ентропія є логарифмом числа покриття.
Нижче наведено дві достатні умови, за яких може бути доведено, що множина є Гливенка — Кантеллі, або донскеровою.
Клас є P-Гливенка — Кантеллі, якщо він є P-мірним такою обгорткою F, що та виконується
Наступна умова є версією славетної [en]. Якщо є таким класом функцій, що
то є P-донскеровим для будь-якої такої міри ймовірності P, що . В крайньому інтегралі цей запис означає
- .
Симетрування
Більшість обґрунтувань того, як обмежувати емпіричні процеси, покладаються на симетрування, максимальні та концентричні нерівності, та зчеплювання. Симетрування зазвичай є першим кроком цих доведень, і оскільки воно використовується в багатьох доведеннях машинного навчання із обмеження функцій емпіричних втрат (включно із доведенням ВЧ-нерівності, що обговорюється в наступному розділі), його представлено тут.
Розгляньмо емпіричний процес
Виявляється, що існує зв'язок між цим емпіричним, та наступним симетрованим процесом:
Цей симетрований процес є процесом Радемахера, обумовленим даними . Отже, згідно [en], він є субґаусовим процесом.
Лема (симетрування). Для будь-якої неспадної опуклої Φ: R → R та класу вимірних функцій ,
Доведення леми симетрування покладається на введення незалежних копій первинних змінних (які іноді називають вибіркою-привидом) та заміну виразу під математичним сподіванням в лівій частині нерівності цими копіями. Після застосування нерівності Єнсена може бути введено інші знаки (звідси й назва — симетрування) без зміни математичного сподівання. Нижче наведено доведення, через його повчальний характер.
Введімо «вибірку-привід» як незалежні копії . Для фіксованих значень маємо:
Отже, згідно нерівності Єнсена,
Взяття математичного сподівання по відношенню до дає
Зауважте, що додавання знаку мінусу перед членом не змінює правої частини нерівності, оскільки вона є симетричною функцією від та . Отже, права частина нерівності залишається такою ж і за «збурення знаку»:
для будь-яких . Отже,
Нарешті, застосування першої нерівності трикутника, а потім опуклості , дає
Де два крайні вирази в правій частині нерівності є однаковими, що завершує доведення.
Типовий спосіб доведення емпіричних ЦГТ спочатку застосовує симетрування для передачі емпіричного процесу до , а потім здійснює доведення обумовлено даними, використовуючи той факт, що процеси Радемахера є простими процесами з гарними властивостями.
ВЧ-зв'язок
Виявляється, існує чарівний зв'язок між деякими комбінаторними властивостями множини , та числами ентропії. Числа рівномірного покриття можуть контролюватися поняттям класів множин Вапника — Червоненкіса (англ. Vapnik-Chervonenkis classes of sets), або, коротше, ВЧ-множин (англ. VC sets).
Розгляньмо набір підмножин вибіркового простору . Кажуть, що вихоплює (англ. pick out) певну підмножину скінченної множини , якщо для деякого . Кажуть, що роздрібнює (англ. shatter) S, якщо він вихоплює кожну з її 2n підмножин. ВЧ-індекс (англ. VC-index, подібний до ВЧ-розмірності + 1 для відповідним чином вибраної класифікаторної множини) набору — це найменше n, для якого жодна множина розміру n не роздрібнюється набором .
Далі, [en] стверджує, що число підмножин, вихоплюваних ВЧ-класом , задовольняє
Що є поліноміальним числом підмножин, а не експоненційним. Інтуїтивно це означає, що зі скінченності ВЧ-індексу випливає, що має явно спрощену структуру.
Подібне обмеження може бути показано (з іншим сталим, незмінним співвідношенням) для так званих ВЧ-підграфікових класів (англ. VC subgraph classes). Для функції [en] є така підмножина , що . Набір називається ВЧ-підграфіковим класом, якщо всі підграфіки формують ВЧ-клас.
Розгляньмо множину індикаторних функцій в для дискретного емпіричного типу міри Q (або, рівнозначно, для будь-якої міри ймовірності Q). Тоді може бути показано, що, на диво, для
Далі розгляньмо симетричну опуклу оболонку множини : , яка є набором функцій вигляду з . Тоді якщо
то наступне є вірним для опуклої оболонки :
Важливим наслідком цього факту є те, що
чого якраз достатньо для того, щоби інтеграл ентропії сходився, і відтак клас був P-донскеровим.
Нарешті, розглядається приклад ВЧ-підграфікового класу. Будь-який векторний простір вимірних функцій , який має скінченну розмірність, є ВЧ-підграфіком індексу, меншого або рівного .
Візьмімо точок . Вектори
є векторами підпростору Rn з розмірністю n − 1. Візьмімо a ≠ 0, вектор, ортогональний до цього підпростору. Тоді
Розгляньмо множину . Цю множину не може бути вихоплено, оскільки, якби існувала якась функція , така що , то це означало би, що ліва частина рівності є строго додатною, а права — недодатною.
Існують узагальнення поняття ВЧ-підграфових класів, наприклад, існує поняття псевдорозмірності. Зацікавлені читачі можуть подивитися [4].
ВЧ-нерівність
Розглядається подібна постановка, звичніша для машинного навчання. Нехай є простором ознак, а . Функція називається класифікатором. Нехай є множиною класифікаторів. Подібно до попереднього розділу, визначмо коефіцієнт роздрібнювання (англ. shattering coefficient, відомий також як функція росту, англ. growth function):
Зауважте, що існує взаємно однозначне відображення між кожною з функцій в , та множиною, на якій ця функція дорівнює 1. Отже, ми можемо визначити як набір підмножин, отриманий з наведеного вище відображення для кожної . Таким чином, з точки зору попереднього розділу, коефіцієнт роздрібнювання в точності дорівнює
- .
З цієї рівності разом із [en] випливає, що має бути поліноміальним в n, для достатньо великого n, за умови, що набір має скінченний ВЧ-індекс.
Нехай є спостережуваним набором даних. Припустімо, що ці дані породжено невідомим розподілом імовірності . Визначмо як очікувані втрати 0/1. Звісно, оскільки є загалом невідомим, ми не маємо доступу до . Проте емпіричний ризик (англ. empirical risk), заданий як
безумовно, може бути оцінено. Тоді маємо наступну теорему:
Теорема (ВЧ-нерівність)
Для бінарної класифікації та функції втрат 0/1 ми маємо наступні обмеження узагальнення:
Іншими словами, ВЧ-нерівність каже, що при збільшенні вибірки, за умови, що має скінченну ВЧ-розмірність, емпіричний ризик 0/1 стає добрим замінником очікуваного ризику 0/1. Зауважте, що обидві праві частини цих двох нерівностей збігатимуться до 0 за умови, що зростає поліноміально в n.
Очевидним є зв'язок між цією системою та системою емпіричних процесів. Тут ми маємо справу з видозміненим емпіричним процесом
але не дивно, що ідеї є однаковими. Доведення (першої частини) ВЧ-нерівності спирається на симетрування, а потім здійснює доведення, обумовлене даними, із застосуванням концентричних нерівностей (зокрема, [en]). Зацікавлений читач може перевірити теореми 12.4 та 12.5 книги [5].
Джерела
- ↑ Vapnik, Vladimir N (2000). The Nature of Statistical Learning Theory. Information Science and Statistics. Springer-Verlag. ISBN . (англ.)
- Vapnik, Vladimir N (1989). Statistical Learning Theory. . ISBN . (англ.)
- ↑ ; Wellner, Jon A. (2000). (вид. 2nd). Springer. ISBN . Архів оригіналу за 20 листопада 2016. Процитовано 20 листопада 2016. (англ.)
- ↑ Gyorfi, L.; Devroye, L.; Lugosi, G. (1996). A probabilistic theory of pattern recognition (вид. 1st). Springer. ISBN . (англ.)
- Див. джерела у статтях [en], [en], роздрібнена множина.
- ↑ Pollard, David (1990). Empirical Processes: Theory and Applications. NSF-CBMS Regional Conference Series in Probability and Statistics Volume 2. ISBN . (англ.)
- Introduction to Statistical Learning Theory // Advanced Lectures on Machine Learning Lecture Notes in Artificial Intelligence 3176, 169-207. (Eds.) Bousquet, O., U. von Luxburg and G. Ratsch, Springer. — 2004. (англ.)
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities // Theory Probab. Appl., 16(2), 264–280.. — 2004. (англ.)
Література
- Воронцов, К. В. (2004). (PDF). Таврический вестник информатики и математики. 1. Архів оригіналу (PDF) за 20 листопада 2016. Процитовано 20 листопада 2016. (рос.)
Посилання
- . MachineLearning.ru. Архів оригіналу за 13 березня 2022. Процитовано 2 квітня 2022. (рос.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Teoriyu Vapnika Chervonenkisa angl Vapnik Chervonenkis theory vidomu takozh yak VCh teoriya angl VC theory bulo rozrobleno protyagom 1960 1990 rokiv Volodimirom Vapnikom ta en Cya teoriya ye riznovidom en yaka namagayetsya poyasnyuvati proces navchannya zi statistichnoyi tochki zoru VCh teoriya pov yazana z teoriyeyu statistichnogo navchannya ta z en Do en VCh teoriyu zastosovuvali sered inshih en ta Volodimir Vapnik VvedennyaVCh teoriya ohoplyuye shonajmenshe chotiri chastini yak poyasneno v Prirodi teoriyi statistichnogo navchannya 1 Teoriyu en procesiv navchannya Yakimi ye neobhidni ta dostatni umovi uzgodzhenosti procesu navchannya na osnovi principu minimizaciyi empirichnogo riziku Neasimptotichnu teoriyu tempu zbizhnosti procesiv navchannya Naskilki shvidkim ye temp zbizhnosti procesu navchannya Teoriyu keruvannya uzagalnyuvalnoyu spromozhnistyu procesiv navchannya Yak mozhna keruvati tempom zbizhnosti uzagalnyuvalnoyu spromozhnistyu procesu navchannya Teoriyu pobudovi mashin yaki vchatsya Yak mozhna buduvati algoritmi yaki keruyut uzagalnyuvalnoyu spromozhnistyu VCh teoriya ye odniyeyu z osnovnih pidgaluzej teoriyi statistichnogo navchannya Odnim iz yiyi golovnih zastosuvan u teoriyi statistichnogo navchannya ye zabezpechennya umov uzagalnennya dlya algoritmiv navchannya Z ciyeyi tochki zoru VCh teoriya pov yazana zi en yaka ye alternativnim pidhodom dlya harakterizuvannya uzagalnennya Krim togo VCh teoriya ta VCh rozmirnist vidigrayut vazhlivu rol u teoriyi en u vipadku procesiv indeksovanih za VCh klasami Mozhlivo voni ye najvazhlivishimi zastosuvannyami VCh teoriyi voni zastosovuyutsya v dovedenni uzagalnennya Bude predstavleno kilka metodik yaki shiroko vikoristovuyutsya v empirichnih procesah ta VCh teoriyi Obgovorennya v osnovnomu gruntuyetsya na knizi Slabka zbizhnist ta empirichni procesi iz zastosuvannyami do statistiki 2 Oglyad VCh teoriyi v empirichnih procesahDovidka pro empirichni procesi Nehaj X1 Xn displaystyle X 1 ldots X n ye vipadkovimi elementami viznachenimi na vimirnomu prostori X A displaystyle mathcal X mathcal A Dlya miri Q vstanovimo Qf fdQ displaystyle Qf int fdQ Pitannya vimirnosti tut ignoruvatimutsya tehnichni detali div u 3 Pokladimo sho F displaystyle mathcal F ye klasom vimirnih funkcij f X R displaystyle f mathcal X to mathbf R i viznachmo Q F sup Qf f F displaystyle Q mathcal F sup vert Qf vert f in mathcal F Viznachmo empirichnu miru Pn n 1 i 1ndXi displaystyle mathbb P n n 1 sum i 1 n delta X i de d v danomu vipadku vidpovidaye en Empirichna mira porodzhuye vidobrazhennya F R displaystyle mathcal F to mathbf R sho zadayetsya yak f Pnf displaystyle f mapsto mathbb P n f Teper pripustimo sho P ye spravzhnim rozpodilom sho lezhit v osnovi danih yakij ye nevidomim Teoriya empirichnih procesiv spryamovana na identifikaciyu klasiv F displaystyle mathcal F dlya yakih vikonuyutsya taki tverdzhennya yak nastupni rivnomirnij zakon velikih chisel Pn P F 0 displaystyle mathbb P n P mathcal F to 0 dd rivnomirna centralna granichna teorema Gn n Pn P G in ℓ F displaystyle mathbb G n sqrt n mathbb P n P rightsquigarrow mathbb G quad text in ell infty mathcal F dd V pershomu vipadku F displaystyle mathcal F nazivayetsya en angl Glivenko Cantelli class a v drugomu za pripushennya x supf F f x Pf lt displaystyle forall x sup nolimits f in mathcal F vert f x Pf vert lt infty klas F displaystyle mathcal F nazivayetsya donskerovim angl Donsker class abo P donskerovim Ochevidno sho klas Donskera ye klasom Glivenka Kantelli v teoriyi jmovirnostej yaksho zastosuvati teoremu Sluckogo Ci tverdzhennya spravedlivi dlya yedinoyi f displaystyle f zgidno standartnih dovodiv ZVCh ta CGT v umovah regulyarnosti a skladnist v empirichnih procesah vinikaye tomu sho roblyatsya spilni tverdzhennya dlya vsih f F displaystyle f in mathcal F Todi intuyitivno mnozhina F displaystyle mathcal F ne mozhe buti zanadto velikoyu i yak viyavlyayetsya duzhe vazhlivu rol vidigraye geometriya F displaystyle mathcal F Odnim zi sposobi vimiryuvannya togo naskilki velikoyu ye mnozhina funkcij F displaystyle mathcal F ye zastosuvannya tak zvanih en Chislo pokrittya N e F displaystyle N varepsilon mathcal F cdot ye minimalnim chislom kul g g f lt e displaystyle g g f lt varepsilon neobhidnih dlya pokrittya mnozhini F displaystyle mathcal F tut ochevidno pripuskayetsya isnuvannya normi na F displaystyle mathcal F na osnovi yakoyi ce robitsya Entropiya ye logarifmom chisla pokrittya Nizhche navedeno dvi dostatni umovi za yakih mozhe buti dovedeno sho mnozhina F displaystyle mathcal F ye Glivenka Kantelli abo donskerovoyu Klas F displaystyle mathcal F ye P Glivenka Kantelli yaksho vin ye P mirnim takoyu obgortkoyu F sho P F lt displaystyle P ast F lt infty ta vikonuyetsya e gt 0supQN e F Q F L1 Q lt displaystyle forall varepsilon gt 0 quad sup nolimits Q N varepsilon F Q mathcal F L 1 Q lt infty Nastupna umova ye versiyeyu slavetnoyi en Yaksho F displaystyle mathcal F ye takim klasom funkcij sho 0 supQlog N e F Q 2 F L2 Q de lt displaystyle int 0 infty sup nolimits Q sqrt log N left varepsilon F Q 2 mathcal F L 2 Q right d varepsilon lt infty to F displaystyle mathcal F ye P donskerovim dlya bud yakoyi takoyi miri jmovirnosti P sho P F2 lt displaystyle P ast F 2 lt infty V krajnomu integrali cej zapis oznachaye f Q 2 f 2dQ 12 displaystyle f Q 2 left int f 2 dQ right frac 1 2 Simetruvannya Bilshist obgruntuvan togo yak obmezhuvati empirichni procesi pokladayutsya na simetruvannya maksimalni ta koncentrichni nerivnosti ta zcheplyuvannya Simetruvannya zazvichaj ye pershim krokom cih doveden i oskilki vono vikoristovuyetsya v bagatoh dovedennyah mashinnogo navchannya iz obmezhennya funkcij empirichnih vtrat vklyuchno iz dovedennyam VCh nerivnosti sho obgovoryuyetsya v nastupnomu rozdili jogo predstavleno tut Rozglyanmo empirichnij proces f Pn P f 1n i 1n f Xi Pf displaystyle f mapsto mathbb P n P f dfrac 1 n sum i 1 n f X i Pf Viyavlyayetsya sho isnuye zv yazok mizh cim empirichnim ta nastupnim simetrovanim procesom f Pn0 1n i 1neif Xi displaystyle f mapsto mathbb P n 0 dfrac 1 n sum i 1 n varepsilon i f X i Cej simetrovanij proces ye procesom Rademahera obumovlenim danimi Xi displaystyle X i Otzhe zgidno en vin ye subgausovim procesom Lema simetruvannya Dlya bud yakoyi nespadnoyi opukloyi F R R ta klasu vimirnih funkcij F displaystyle mathcal F EF Pn P F EF 2 Pn0 F displaystyle mathbb E Phi mathbb P n P mathcal F leq mathbb E Phi left 2 left mathbb P n 0 right mathcal F right Dovedennya lemi simetruvannya pokladayetsya na vvedennya nezalezhnih kopij pervinnih zminnih Xi displaystyle X i yaki inodi nazivayut vibirkoyu prividom ta zaminu virazu pid matematichnim spodivannyam v livij chastini nerivnosti cimi kopiyami Pislya zastosuvannya nerivnosti Yensena mozhe buti vvedeno inshi znaki zvidsi j nazva simetruvannya bez zmini matematichnogo spodivannya Nizhche navedeno dovedennya cherez jogo povchalnij harakter Dovedennya Vvedimo vibirku privid Y1 Yn displaystyle Y 1 ldots Y n yak nezalezhni kopiyi X1 Xn displaystyle X 1 ldots X n Dlya fiksovanih znachen X1 Xn displaystyle X 1 ldots X n mayemo Pn P F supf F1n i 1nf Xi Ef Yi EYsupf F1n i 1nf Xi f Yi displaystyle mathbb P n P mathcal F sup f in mathcal F dfrac 1 n left sum i 1 n f X i mathbb E f Y i right leq mathbb E Y sup f in mathcal F dfrac 1 n left sum i 1 n f X i f Y i right Otzhe zgidno nerivnosti Yensena F Pn P F EYF 1n i 1nf Xi f Yi F displaystyle Phi mathbb P n P mathcal F leq mathbb E Y Phi left left dfrac 1 n sum i 1 n f X i f Y i right mathcal F right Vzyattya matematichnogo spodivannya po vidnoshennyu do X displaystyle X daye EF Pn P F EXEYF 1n i 1nf Xi f Yi F displaystyle mathbb E Phi mathbb P n P mathcal F leq mathbb E X mathbb E Y Phi left left dfrac 1 n sum i 1 n f X i f Y i right mathcal F right Zauvazhte sho dodavannya znaku minusu pered chlenom f Xi f Yi displaystyle f X i f Y i ne zminyuye pravoyi chastini nerivnosti oskilki vona ye simetrichnoyu funkciyeyu vid X displaystyle X ta Y displaystyle Y Otzhe prava chastina nerivnosti zalishayetsya takoyu zh i za zburennya znaku EF 1n i 1nei f Xi f Yi F displaystyle mathbb E Phi left left dfrac 1 n sum i 1 n e i left f X i f Y i right right mathcal F right dlya bud yakih e1 e2 en 1 1 n displaystyle e 1 e 2 ldots e n in 1 1 n Otzhe EF Pn P F EeEF 1n i 1nei f Xi f Yi F displaystyle mathbb E Phi mathbb P n P mathcal F leq mathbb E varepsilon mathbb E Phi left left dfrac 1 n sum i 1 n varepsilon i left f X i f Y i right right mathcal F right Nareshti zastosuvannya pershoyi nerivnosti trikutnika a potim opuklosti F displaystyle Phi daye EF Pn P F 12EeEF 2 1n i 1neif Xi F 12EeEF 2 1n i 1neif Yi F displaystyle mathbb E Phi mathbb P n P mathcal F leq dfrac 1 2 mathbb E varepsilon mathbb E Phi left 2 left dfrac 1 n sum i 1 n varepsilon i f X i right mathcal F right dfrac 1 2 mathbb E varepsilon mathbb E Phi left 2 left dfrac 1 n sum i 1 n varepsilon i f Y i right mathcal F right De dva krajni virazi v pravij chastini nerivnosti ye odnakovimi sho zavershuye dovedennya Tipovij sposib dovedennya empirichnih CGT spochatku zastosovuye simetruvannya dlya peredachi empirichnogo procesu do Pn0 displaystyle mathbb P n 0 a potim zdijsnyuye dovedennya obumovleno danimi vikoristovuyuchi toj fakt sho procesi Rademahera ye prostimi procesami z garnimi vlastivostyami VCh zv yazok Viyavlyayetsya isnuye charivnij zv yazok mizh deyakimi kombinatornimi vlastivostyami mnozhini F displaystyle mathcal F ta chislami entropiyi Chisla rivnomirnogo pokrittya mozhut kontrolyuvatisya ponyattyam klasiv mnozhin Vapnika Chervonenkisa angl Vapnik Chervonenkis classes of sets abo korotshe VCh mnozhin angl VC sets Rozglyanmo nabir C displaystyle mathcal C pidmnozhin vibirkovogo prostoru X displaystyle mathcal X Kazhut sho C displaystyle mathcal C vihoplyuye angl pick out pevnu pidmnozhinu W displaystyle W skinchennoyi mnozhini S x1 xn X displaystyle S x 1 ldots x n subset mathcal X yaksho W S C displaystyle W S cap C dlya deyakogo C C displaystyle C in mathcal C Kazhut sho C displaystyle mathcal C rozdribnyuye angl shatter S yaksho vin vihoplyuye kozhnu z yiyi 2n pidmnozhin VCh indeks angl VC index podibnij do VCh rozmirnosti 1 dlya vidpovidnim chinom vibranoyi klasifikatornoyi mnozhini V C displaystyle V mathcal C naboru C displaystyle mathcal C ce najmenshe n dlya yakogo zhodna mnozhina rozmiru n ne rozdribnyuyetsya naborom C displaystyle mathcal C Dali en stverdzhuye sho chislo Dn C x1 xn displaystyle Delta n mathcal C x 1 ldots x n pidmnozhin vihoplyuvanih VCh klasom C displaystyle mathcal C zadovolnyaye maxx1 xnDn C x1 xn j 0V C 1 nj neV C 1 V C 1 displaystyle max x 1 ldots x n Delta n mathcal C x 1 ldots x n leq sum j 0 V mathcal C 1 n choose j leq left frac ne V mathcal C 1 right V mathcal C 1 Sho ye polinomialnim chislom O nV C 1 displaystyle O n V mathcal C 1 pidmnozhin a ne eksponencijnim Intuyitivno ce oznachaye sho zi skinchennosti VCh indeksu viplivaye sho C displaystyle mathcal C maye yavno sproshenu strukturu Podibne obmezhennya mozhe buti pokazano z inshim stalim nezminnim spivvidnoshennyam dlya tak zvanih VCh pidgrafikovih klasiv angl VC subgraph classes Dlya funkciyi f X R displaystyle f mathcal X to mathbf R en ye taka pidmnozhina X R displaystyle mathcal X times mathbf R sho x t t lt f x displaystyle x t t lt f x Nabir F displaystyle mathcal F nazivayetsya VCh pidgrafikovim klasom yaksho vsi pidgrafiki formuyut VCh klas Rozglyanmo mnozhinu indikatornih funkcij IC 1C C C displaystyle mathcal I mathcal C 1 C C in mathcal C v L1 Q displaystyle L 1 Q dlya diskretnogo empirichnogo tipu miri Q abo rivnoznachno dlya bud yakoyi miri jmovirnosti Q Todi mozhe buti pokazano sho na divo dlya r 1 displaystyle r geq 1 N e IC Lr Q KV C 4e V C e r V C 1 displaystyle N varepsilon mathcal I mathcal C L r Q leq KV mathcal C 4e V mathcal C varepsilon r V mathcal C 1 Dali rozglyanmo simetrichnu opuklu obolonku mnozhini F displaystyle mathcal F sconv F displaystyle operatorname sconv mathcal F yaka ye naborom funkcij viglyadu i 1maifi displaystyle sum i 1 m alpha i f i z i 1m ai 1 displaystyle sum i 1 m alpha i leq 1 Todi yaksho N e F Q 2 F L2 Q Ce V displaystyle N left varepsilon F Q 2 mathcal F L 2 Q right leq C varepsilon V to nastupne ye virnim dlya opukloyi obolonki F displaystyle mathcal F log N e F Q 2 sconv F L2 Q Ke 2VV 2 displaystyle log N left varepsilon F Q 2 operatorname sconv mathcal F L 2 Q right leq K varepsilon frac 2V V 2 Vazhlivim naslidkom cogo faktu ye te sho 2VV 2 gt 2 displaystyle frac 2V V 2 gt 2 chogo yakraz dostatno dlya togo shobi integral entropiyi shodivsya i vidtak klas sconv F displaystyle operatorname sconv mathcal F buv P donskerovim Nareshti rozglyadayetsya priklad VCh pidgrafikovogo klasu Bud yakij vektornij prostir F displaystyle mathcal F vimirnih funkcij f X R displaystyle f mathcal X to mathbf R yakij maye skinchennu rozmirnist ye VCh pidgrafikom indeksu menshogo abo rivnogo dim F 2 displaystyle dim mathcal F 2 Dovedennya Vizmimo n dim F 2 displaystyle n dim mathcal F 2 tochok x1 t1 xn tn displaystyle x 1 t 1 ldots x n t n Vektori f x1 f xn t1 tn displaystyle f x 1 ldots f x n t 1 ldots t n ye vektorami pidprostoru Rn z rozmirnistyu n 1 Vizmimo a 0 vektor ortogonalnij do cogo pidprostoru Todi ai gt 0ai f xi ti ai lt 0 ai f xi ti f F displaystyle sum a i gt 0 a i f x i t i sum a i lt 0 a i f x i t i quad forall f in mathcal F Rozglyanmo mnozhinu S xi ti ai gt 0 displaystyle S x i t i a i gt 0 Cyu mnozhinu ne mozhe buti vihopleno oskilki yakbi isnuvala yakas funkciya f displaystyle f taka sho S xi ti f xi gt ti displaystyle S x i t i f x i gt t i to ce oznachalo bi sho liva chastina rivnosti ye strogo dodatnoyu a prava nedodatnoyu Isnuyut uzagalnennya ponyattya VCh pidgrafovih klasiv napriklad isnuye ponyattya psevdorozmirnosti Zacikavleni chitachi mozhut podivitisya 4 VCh nerivnistRozglyadayetsya podibna postanovka zvichnisha dlya mashinnogo navchannya Nehaj X displaystyle mathcal X ye prostorom oznak a Y 0 1 displaystyle mathcal Y 0 1 Funkciya f X Y displaystyle f mathcal X to mathcal Y nazivayetsya klasifikatorom Nehaj F displaystyle mathcal F ye mnozhinoyu klasifikatoriv Podibno do poperednogo rozdilu viznachmo koeficiyent rozdribnyuvannya angl shattering coefficient vidomij takozh yak funkciya rostu angl growth function S F n maxx1 xn f x1 f xn f F displaystyle S mathcal F n max x 1 ldots x n f x 1 ldots f x n f in mathcal F Zauvazhte sho isnuye vzayemno odnoznachne vidobrazhennya mizh kozhnoyu z funkcij v F displaystyle mathcal F ta mnozhinoyu na yakij cya funkciya dorivnyuye 1 Otzhe mi mozhemo viznachiti C displaystyle mathcal C yak nabir pidmnozhin otrimanij z navedenogo vishe vidobrazhennya dlya kozhnoyi f F displaystyle f in mathcal F Takim chinom z tochki zoru poperednogo rozdilu koeficiyent rozdribnyuvannya v tochnosti dorivnyuye maxx1 xnDn C x1 xn displaystyle max x 1 ldots x n Delta n mathcal C x 1 ldots x n Z ciyeyi rivnosti razom iz en viplivaye sho S F n displaystyle S mathcal F n maye buti polinomialnim v n dlya dostatno velikogo n za umovi sho nabir C displaystyle mathcal C maye skinchennij VCh indeks Nehaj Dn X1 Y1 Xn Ym displaystyle D n X 1 Y 1 ldots X n Y m ye sposterezhuvanim naborom danih Pripustimo sho ci dani porodzheno nevidomim rozpodilom imovirnosti PXY displaystyle P XY Viznachmo R f P f X Y displaystyle R f P f X neq Y yak ochikuvani vtrati 0 1 Zvisno oskilki PXY displaystyle P XY ye zagalom nevidomim mi ne mayemo dostupu do R f displaystyle R f Prote empirichnij rizik angl empirical risk zadanij yak R n f 1n i 1nI f Xi Yi displaystyle hat R n f dfrac 1 n sum i 1 n mathbb I f X i neq Y i bezumovno mozhe buti ocineno Todi mayemo nastupnu teoremu Teorema VCh nerivnist Dlya binarnoyi klasifikaciyi ta funkciyi vtrat 0 1 mi mayemo nastupni obmezhennya uzagalnennya P supf F R n f R f gt e 8S F n e ne2 32E supf F R n f R f 2log S F n log 2n displaystyle begin aligned P left sup f in mathcal F left hat R n f R f right gt varepsilon right amp leq 8S mathcal F n e n varepsilon 2 32 mathbb E left sup f in mathcal F left hat R n f R f right right amp leq 2 sqrt dfrac log S mathcal F n log 2 n end aligned Inshimi slovami VCh nerivnist kazhe sho pri zbilshenni vibirki za umovi sho F displaystyle mathcal F maye skinchennu VCh rozmirnist empirichnij rizik 0 1 staye dobrim zaminnikom ochikuvanogo riziku 0 1 Zauvazhte sho obidvi pravi chastini cih dvoh nerivnostej zbigatimutsya do 0 za umovi sho S F n displaystyle S mathcal F n zrostaye polinomialno v n Ochevidnim ye zv yazok mizh ciyeyu sistemoyu ta sistemoyu empirichnih procesiv Tut mi mayemo spravu z vidozminenim empirichnim procesom R n R F displaystyle left hat R n R right mathcal F ale ne divno sho ideyi ye odnakovimi Dovedennya pershoyi chastini VCh nerivnosti spirayetsya na simetruvannya a potim zdijsnyuye dovedennya obumovlene danimi iz zastosuvannyam koncentrichnih nerivnostej zokrema en Zacikavlenij chitach mozhe pereviriti teoremi 12 4 ta 12 5 knigi 5 Dzherela Vapnik Vladimir N 2000 The Nature of Statistical Learning Theory Information Science and Statistics Springer Verlag ISBN 978 0 387 98780 4 angl Vapnik Vladimir N 1989 Statistical Learning Theory Wiley Interscience ISBN 0 471 03003 1 angl Wellner Jon A 2000 vid 2nd Springer ISBN 978 0 387 94640 5 Arhiv originalu za 20 listopada 2016 Procitovano 20 listopada 2016 angl Gyorfi L Devroye L Lugosi G 1996 A probabilistic theory of pattern recognition vid 1st Springer ISBN 978 0387946184 angl Div dzherela u stattyah en en rozdribnena mnozhina Pollard David 1990 Empirical Processes Theory and Applications NSF CBMS Regional Conference Series in Probability and Statistics Volume 2 ISBN 0 940600 16 1 angl Introduction to Statistical Learning Theory Advanced Lectures on Machine Learning Lecture Notes in Artificial Intelligence 3176 169 207 Eds Bousquet O U von Luxburg and G Ratsch Springer 2004 angl On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities Theory Probab Appl 16 2 264 280 2004 angl LiteraturaVoroncov K V 2004 PDF Tavricheskij vestnik informatiki i matematiki 1 Arhiv originalu PDF za 20 listopada 2016 Procitovano 20 listopada 2016 ros Posilannya MachineLearning ru Arhiv originalu za 13 bereznya 2022 Procitovano 2 kvitnya 2022 ros