Jump to content

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

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

Определение

[ редактировать ]

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

Эквивалентно, 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 точек разбивается на класс эллиптических дисков. Визуализировано ниже:

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

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

[ редактировать ]

Чтобы количественно оценить богатство коллекции C множеств, мы используем концепцию коэффициентов разрушения (также известную как функция роста ). Для коллекции C множеств , будучи любым пространством, часто пространством выборки , мы определяем затем й разрушения 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-точечных наборов.

Этот пример иллюстрирует некоторые свойства :

  1. для всех n, потому что для любого .
  2. Если что существует набор мощности n , который может быть разрушен C. , это означает ,
  3. Если для некоторых затем для всех .

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

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

[ редактировать ]

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

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

Обратите внимание, что . Размерность VC обычно определяется как VC_0, наибольшая мощность выбранных точек, которая все равно разрушит A (т. е. n такое, что ).

Альтернативно, если для любого n существует набор мощности n , который может быть разрушен C , то для всех 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 .
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 2d68a71a552ea3f93514b781f400b331__1722881340
URL1:https://arc.ask3.ru/arc/aa/2d/31/2d68a71a552ea3f93514b781f400b331.html
Заголовок, (Title) документа по адресу, URL1:
Shattered set - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)