Разрушенный набор - Shattered set

Концепция чего-либо разбитые наборы играет важную роль в Теория Вапника – Червоненкиса., также известная как VC-теория. Расщепление и теория ВК используются при изучении эмпирические процессы а также в статистических теория вычислительного обучения.

Определение

Предполагать А это набор и C это учебный класс наборов. Класс C разбивается набор А если для каждого подмножества а из А, есть элемент c из C такой, что

${ displaystyle a = c cap A.}$

Эквивалентно, C разбивается А когда их пересечение равно А 's набор мощности: п(А) = { c ∩ А | c ∈ C }.

Мы используем письмо C для обозначения «класса» или «коллекции» множеств, как в классе Вапника – Червоненкиса (VC-класс). Набор А часто считается конечный потому что в эмпирических процессах мы заинтересованы в разрушении конечных наборов точек данных.

Пример

Покажем, что класс всех диски в самолет (двумерное пространство) не разбивает каждый набор из четырех точек на единичный круг, но класс всех выпуклые множества на плоскости разрушает каждый конечный набор точек на единичный круг.

Позволять А - набор из четырех точек на единичной окружности, и пусть C быть классом всех дисков.

Набор А четырех конкретных точек на единичном круге (единичный круг показан фиолетовым цветом).

Чтобы проверить, где C разбивается А, мы пытаемся обвести кругом каждое подмножество точек в А. Сначала мы обводим кругом подмножества каждой изолированной точки. Затем мы пытаемся нарисовать диск вокруг каждого подмножества пар точек. Оказывается, это выполнимо для соседних точек, но невозможно для точек на противоположных сторонах круга. Как показано ниже:

• 

  Каждую отдельную точку можно выделить диском (показаны все четыре).

• 

  Каждое подмножество соседних точек можно изолировать с помощью диска (показывающего одну из четырех).

• 

  Подмножество точек на противоположных сторонах единичной окружности может нет быть изолированным диском.

Потому что есть подмножество, которое может нет быть изолированным любым диском в C, заключаем, что А не разрушен C. И, немного подумав, мы можем доказать, что ни один набор из четырех пунктов не нарушен этим C.

Однако, если мы переопределим C быть классом всех эллиптические диски, мы обнаруживаем, что все еще можем изолировать все подмножества сверху, а также точки, которые ранее были проблематичными. Таким образом, этот специфический набор из 4 точек уступает классу эллиптических дисков. Визуализируется ниже:

• 

  Противоположные точки А теперь можно разделить на какой-то эллипс (показан один из двух)

• 

  Каждое подмножество из трех точек в А также можно разделить на некоторый эллипс (показан один из четырех)

Немного подумав, мы могли бы обобщить, что любой набор конечных точек на единичной окружности может быть разрушен классом всех выпуклые множества (визуализируйте соединение точек).

Коэффициент разрушения

Чтобы количественно оценить богатство коллекции C наборов мы используем понятие коэффициенты дробления (также известный как функция роста). Для коллекции C наборов ${ displaystyle s subset Omega}$, ${ displaystyle Omega}$ быть любым пространством, часто пространство образца, мы определяем п^th коэффициент разрушения из C в качестве

${ displaystyle S_ {C} (n) = max _ { forall 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 x_ {1}, x_ {2}, dots, x_ {n} in Omega}$ любой набор п точки,.

${ Displaystyle S_ {C} (п)}$ - наибольшее количество подмножеств любого набора А из п точки, которые могут быть образованы пересечением А с наборами в коллекции C.

Вот несколько фактов о ${ Displaystyle S_ {C} (п)}$:

1. ${ Displaystyle S_ {C} (п) leq 2 ^ {п}}$ для всех п потому что ${ Displaystyle {s cap A | s in C } substeq P (A)}$ для любого ${ Displaystyle A substeq Omega}$.
2. Если ${ Displaystyle S_ {C} (п) = 2 ^ {п}}$, это означает, что существует набор мощности п, который может быть разрушен C.
3. Если ${ Displaystyle S_ {C} (N) <2 ^ {N}}$ для некоторых ${ displaystyle N> 1}$ тогда ${ Displaystyle S_ {C} (п) <2 ^ {п}}$ для всех ${ Displaystyle п 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.}$

Если для любого п есть набор мощности п который может быть разрушен C, тогда ${ Displaystyle S_ {C} (п) = 2 ^ {п}}$ для всех п и размер VC этого класса C бесконечно.

Класс с конечной размерностью ВК называется Вапник – Червоненкис класс или же VC класс. Класс C является равномерно Гливенко – Кантелли тогда и только тогда, когда это класс ВК.

Смотрите также

• Лемма Зауэра – Шелаха., связывая мощность семейство наборов размером с его самый большой разбитый набор

Рекомендации

• Wencour, R. S .; Дадли, Р. М. (1981), "Некоторые специальные классы Вапника – Червоненкиса", Дискретная математика, 33 (3): 313–318, Дои:10.1016 / 0012-365X (81) 90274-0.
• Стил, Дж. М. (1975), Комбинаторная энтропия и равномерные предельные законы, Кандидат наук. дипломная работа, Стэнфордский университет, математический факультет
• Стил, Дж. М. (1978), «Эмпирические расхождения и субаддитивные процессы», Анналы вероятности, 6 (1): 118–227, Дои:10.1214 / aop / 1176995615, JSTOR  2242865.

внешняя ссылка

• Происхождение терминологии «Расколотые множества», Дж. Стил