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

Говорят, что класс множеств разрушает другой набор, если можно «выбрать» любой элемент этого набора с помощью пересечения . Концепция разрушенных множеств играет важную роль в теории Вапника–Червоненкиса , также известной как VC-теория. Shattering и VC-теория используются при изучении эмпирических процессов , а также в статистической теории вычислительного обучения .

Определение

Предположим, что A — множество , а C — класс множеств. Класс C разрушает множество A , если для каждого подмножества a из A существует некоторый элемент c из C такой, что

a=c\cap A.

Эквивалентно, C разрушает A , когда их пересечение равно : A множеству степеней P ( A ) = { c ∩ A | с € С }.

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

Пример

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

Пусть A — набор из четырех точек единичной окружности, а C — класс всех дисков.

Множество A из четырех конкретных точек единичной окружности (единичная окружность показана фиолетовым цветом).

Чтобы проверить, где разрушает A , мы пытаемся нарисовать диск вокруг каждого подмножества точек в A. C Сначала мы рисуем диск вокруг подмножеств каждой изолированной точки. Далее мы пытаемся нарисовать диск вокруг каждого подмножества пар точек. Это оказывается выполнимым для соседних точек, но невозможным для точек на противоположных сторонах круга. Любая попытка включить эти точки на противоположную сторону обязательно будет включать в себя другие точки, не входящие в эту пару. Следовательно, любая пара противоположных точек не может быть изолирована от A с помощью пересечений с классом C , и поэтому C не разрушает A .

Как показано ниже:

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

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

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

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

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

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

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

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

где $\operatorname {card}$ обозначает мощность множества и $x_{1},x_{2},\dots ,x_{n}\in \Omega$ – это любой набор из n точек.

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

Например, если набор A содержит 3 точки, его набор мощности $P(A)$ , содержит $2^{3}=8$ элементы. Если C разрушит A , его коэффициент разрушения (3) будет равен 8, а S_C(2) будет равен $2^{2}=4$ . Однако если один из них $P(A)$ невозможно получить через пересечения в c , тогда S_C(3) будет только 7. Если ни один из этих наборов не может быть получен, S_C(3) будет 0. Кроме того, если S_C(2)=3, например, тогда — элемент множества всех 2-точечных множеств из A , который не может быть получен пересечением с C . Из этого следует, что S_C(3) также будет меньше 8 (т.е. C не разрушит A ), поскольку мы уже обнаружили «недостающий» набор в меньшем степенном наборе 2-точечных наборов.

Этот пример иллюстрирует некоторые свойства $S_{C}(n)$ :

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

Третье свойство означает, что если C не может разрушить какое-либо множество мощности N , то он не может разрушить и множества большей мощности.

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

Если A не может быть разрушен C , будет наименьшее значение n , при котором коэффициент разрушения (n) будет меньше, чем $2^{n}$ потому что по мере увеличения n появляется больше наборов, которые можно пропустить. Альтернативно, существует также наибольшее значение n , для которого S_C(n) все еще равно. $2^{n}$ , потому что чем меньше n , тем меньше наборов можно пропустить. Крайним показателем является S_C(0) (коэффициент разрушения пустого множества), который всегда должен быть равен $2^{0}=1$ . Эти утверждения позволяют определить измерение VC класса 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.$ . Размерность VC обычно определяется как VC_0, наибольшая мощность выбранных точек, которая все равно разрушит A (т. е. n такое, что $S_{C}(n)=2^{n}$ ).

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

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

См. также

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

Ссылки

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

Внешние ссылки

Происхождение терминологии Дж. Стила «Разрушенные множества».