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

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

Визначення

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

$a=c\cap A.$

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

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

Приклад

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

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

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

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

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

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

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

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

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

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

Для кількісної оцінки багатства набору множин C ми використовуємо поняття коефіцієнтів роздрібнювання (відомих також як коефіцієнти роздрібнення або функція росту, Шаблон:Lang-en). Для набору C множин s⊂Ω, де Ω є будь-яким простором, часто ймовірнісним простором, а $x_1,x_2,\dots ,x_n\in \mathrm{\Omega }$ є будь-якою множиною з n точок, ми визначаємо n-тий коефіцієнт роздрібнювання набору C як

$S_C(n)=\underset{x_1,x_2,\dots ,x_n\in \mathrm{\Omega }}{\max }\mathrm{card}\{\{x_1,x_2,\dots ,x_n\}\cap s,s\in C\}$

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

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

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

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

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

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

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

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

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

$V{C}_0(C)=\underset{n}{\max }\{n:S_C(n)=2^n\}.$

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

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

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

Див. також

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

Джерела

• Шаблон:Citation Шаблон:Ref-en
• Шаблон:Citation Шаблон:Ref-en
• Шаблон:Citation Шаблон:Ref-en

Посилання

• Походження термінології «роздрібнених множин» Шаблон:Webarchive від Шаблон:Нп Шаблон:Ref-en