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

Припустімо, що 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 є рівномірно Гливенка — Кантеллі, якщо і лише якщо він є ВЧ-класом.

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

• 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. JSTOR 2242865. doi:10.1214/aop/1176995615. (англ.)

• Походження термінології «роздрібнених множин» від Джона Стіла (англ.)