Роздрібнена множина

Поняття роздрі́бнених множи́н (англ. shattered sets) відіграє важливу роль в теорії Вапника — Червоненкіса, відомій також як ВЧ-теорія. Роздрібнювання та ВЧ-теорія використовуються в дослідженні ^[en], а також у статистичній ^[en].

Визначення

Припустімо, що A є множиною, а C — класом множин. Клас C роздрі́бнює множину A, якщо для кожної підмножини a множини A існує такий елемент c класу C, що

${\displaystyle a=c\cap A.}$

Рівнозначно, C роздрібнює A, якщо булеан P(A) = { c ∩ A | c ∈ C }.

Ми застосовуємо літеру C для позначення «класу» (англ. class) або «набору» (англ. collection) множин, як у класі Вапника — Червоненкіса (ВЧ-клас). Множина A часто вважається скінченною, оскільки в емпіричних процесах нас цікавить роздрібнювання скінченних множин точок даних.

Приклад

Ми покажемо, що клас усіх кругів на площині (у двовимірному просторі) не роздрібнює будь-яку множину з чотирьох точок на одиничному колі, але клас усіх опуклих множин на площині роздрібнює будь-яку скінченну множину точок на одиничному колі.

Нехай A є множиною з чотирьох точок на одиничному колі, а C є класом усіх кругів.

Множина A з чотирьох конкретних точок на одиничному колі (одиничне коло показано рожевим).

Щоби перевірити, чи C роздрібнює A, ми намагаємося намалювати круг навколо кожної з підмножин точок множини A. По-перше, ми малюємо круг навколо підмножин з кожної ізольованої точки. Потім ми намагаємося намалювати круг навколо кожної з підмножин із пар точок. Це виявляється здійсненним для сусідніх точок, але неможливим для точок на протилежних сторонах кола. Як унаочнено нижче:

• Кожну окрему точку може бути ізольовано кругом (показано всі чотири).
• Кожну з підмножин із сусідніх точок може бути ізольовано кругом (показано один із чотирьох).
• Підмножину з точок на протилежних сторонах одиничного кола не може бути ізольовано кругом.

Оскільки існує підмножина, яку не може бути ізольовано жодним кругом із C, то ми робимо висновок, що A не роздрібнюється класом C. І, трохи поміркувавши, ми можемо довести, що жодна множина з чотирьох точок не роздрібнюється цим C.

Проте, якщо ми перевизначимо C як клас усіх еліпсів, ми виявимо, що ми все ще можемо ізолювати всі підмножини, як і вище, але також і точки, які раніше були проблемними. Таким чином, ця конкретна множина з 4 точок роздрібнюється класом еліпсів. Унаочнено нижче:

• Протилежні точки A є тепер віддільними деяким еліпсом (показано один із двох)
• Кожна з підмножин із трьох точок з A також є віддільною деяким еліпсом (показано один із чотирьох)

Трошки поміркувавши, ми можемо зробити узагальнення, що будь-яку множину скінченних точок на одиничному колі може бути роздрібнено класом усіх опуклих множин (унаочніть з'єднанням точок).

Коефіцієнт роздрібнювання

Для кількісної оцінки багатства набору множин C ми використовуємо поняття коефіцієнтів роздрібнювання (відомих також як коефіцієнти роздрібнення або функція росту, англ. shattering coefficients, shatter coefficients, growth function). Для набору C множин s⊂Ω, де Ω є будь-яким простором, часто ймовірнісним простором, а ${\displaystyle x_{1},x_{2},\dots ,x_{n}\in \Omega }$ є будь-якою множиною з n точок, ми визначаємо n-тий коефіцієнт роздрібнювання набору C як

${\displaystyle S_{C}(n)=\max _{x_{1},x_{2},\dots ,x_{n}\in \Omega }\operatorname {card} \{\,\{\,x_{1},x_{2},\dots ,x_{n}\}\cap s,s\in C\}}$

де ${\displaystyle \operatorname {card} }$ позначає потужність множини.

${\displaystyle S_{C}(n)}$ — це найбільше число підмножин будь-якої множини A з n точок, які може бути сформовано перетином A з множинами з набору C.

Ось деякі факти про ${\displaystyle S_{C}(n)}$:

1. ${\displaystyle S_{C}(n)\leq 2^{n}}$ для всіх n, оскільки ${\displaystyle \{s\cap A|s\in C\}\subseteq P(A)}$ для будь-якої ${\displaystyle A\subseteq \Omega }$.
2. Якщо ${\displaystyle S_{C}(n)=2^{n}}$, то це означає, що існує множина потужності n, яку може бути роздрібнено набором C.
3. Якщо ${\displaystyle S_{C}(N)<2^{N}}$ для деякого ${\displaystyle N>1}$, то ${\displaystyle S_{C}(n)<2^{n}}$ для всіх ${\displaystyle n\geq N}$.

Третя властивість означає, що якщо C не може роздрібнити будь-яку множину потужності N, то він не може роздрібнювати множини й вищих потужностей.

Клас Вапника — Червоненкіса

ВЧ-розмірність класу C визначається як

${\displaystyle VC(C)={\underset {n}{\min }}\{n:S_{C}(n)<2^{n}\}\,}$

або, альтернативно, як

${\displaystyle VC_{0}(C)={\underset {n}{\max }}\{n:S_{C}(n)=2^{n}\}.\,}$

Зауважте, що ${\displaystyle VC(C)=VC_{0}(C)+1.}$

Якщо для будь-якого n існує множина потужності n, яку може бути роздрібнено класом C, то ${\displaystyle S_{C}(n)=2^{n}}$ для всіх n, а ВЧ-розмірність цього класу C є нескінченною.

Клас зі скінченною ВЧ-розмірністю називається класом Вапника — Червоненкіса або ВЧ-класом. Клас C є ^[en], якщо і лише якщо він є ВЧ-класом.

Див. також

• ^[en], яка ставить у відповідність потужність сімейства множин розмірові його найбільшої роздрібненої множини

Джерела

• Wencour, R. S.; Dudley, R. M. (1981), Some special Vapnik–Chervonenkis classes, Discrete Mathematics, 33 (3): 313—318, doi:10.1016/0012-365X(81)90274-0 (англ.)
• (1975), Combinatorial Entropy and Uniform Limit Laws, Ph.D. thesis, Stanford University, Mathematics Department (англ.)
• (1978), Empirical discrepancies and subadditive processes, Annals of Probability, 6 (1): 118—227, doi:10.1214/aop/1176995615, JSTOR 2242865 (англ.)

Посилання

• Походження термінології «роздрібнених множин» [Архівовано 25 березня 2017 у Wayback Machine.] від ^[en] (англ.)