Разбитый набор

Понятие в вычислительном обучении

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

Определение

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

${\displaystyle a=c\cap A.}$

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Этот пример иллюстрирует некоторые свойства : ${\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. Если , это означает, что существует множество мощности n , которое может быть разрушено с помощью C . ${\displaystyle S_{C}(n)=2^{n}}$
3. Если для некоторых , то для всех . ${\displaystyle S_{C}(N)<2^{N}}$ ${\displaystyle N>1}$ ${\displaystyle S_{C}(n)<2^{n}}$ ${\displaystyle n\geq N}$

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

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

Если A не может быть разрушено C , то будет наименьшее значение n , которое сделает коэффициент разрушения (n) меньше, чем , потому что по мере того, как n становится больше, есть больше наборов, которые могут быть пропущены. В качестве альтернативы, есть также наибольшее значение n , для которого S_C(n) все еще равно , потому что по мере того , как n становится меньше, есть меньше наборов, которые могут быть пропущены. Крайним случаем этого является S_C(0) (коэффициент разрушения пустого набора), который всегда должен быть . Эти утверждения позволяют определить измерение VC класса C как: ${\displaystyle 2^{n}}$ ${\displaystyle 2^{n}}$ ${\displaystyle 2^{0}=1}$

${\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}\}.\,}$

Обратите внимание, что . Измерение VC обычно определяется как VC_0, наибольшая мощность выбранных точек, которая все еще разрушит A (т.е. n такое, что ). ${\displaystyle VC(C)=VC_{0}(C)+1.}$ ${\displaystyle S_{C}(n)=2^{n}}$

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

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

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

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

Ссылки

• Венкур, RS; Дадли, RM (1981), «Некоторые специальные классы Вапника–Червоненкиса», Дискретная математика , 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.

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

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