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

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

Визначення

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

$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⊂Ω, де Ω є будь-яким простором, часто ймовірнісним простором, а $x_{1},x_{2},\dots ,x_{n}\in \Omega$ є будь-якою множиною з n точок, ми визначаємо n-тий коефіцієнт роздрібнювання набору C як

$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\}$

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

• Лема Зауера — Шелаха, яка ставить у відповідність потужність сімейства множин розмірові його найбільшої роздрібненої множини

Джерела

• 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 (англ.)
• Steele, J. M. (1975), Combinatorial Entropy and Uniform Limit Laws, Ph.D. thesis, Stanford University, Mathematics Department (англ.)
• Steele, J. M. (1978), Empirical discrepancies and subadditive processes, Annals of Probability, 6 (1): 118—227, doi:10.1214/aop/1176995615, JSTOR 2242865 (англ.)

Посилання

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