WikiDer > Лемма Зауэра – Шелаха.

Sauer–Shelah lemma
Формулировка Паджора леммы Зауэра – Шелаха: для каждого конечного семейства множеств (зеленый) существует другое семейство из равного количества множеств (синие контуры), такое что каждое множество во втором семействе разрушается первым семейством

В комбинаторная математика и теория экстремальных множеств, то Лемма Зауэра – Шелаха. заявляет, что каждый семейство наборов с маленьким Размер ВК состоит из небольшого количества наборов. Он назван в честь Норберт Зауэр и Сахарон Шелах, которые опубликовали его независимо друг от друга в 1972 году.[1][2] Тот же результат был опубликован несколько ранее и снова независимо от Владимир Вапник и Алексей Червоненкис, в честь которого названо измерение ВК.[3] В своей статье, содержащей лемму, Шелах также отдает должное Миха Перлес, и по этой причине лемму также назвали Лемма Перлеса – Зауэра – Шелаха..[4]

Buzaglo et al. называем эту лемму "одним из самых фундаментальных результатов о VC-размерности",[4] и он имеет приложения во многих областях. Мотивация Зауэра заключалась в комбинаторика установленных систем, в то время как Шела была в теория моделей а то Вапника и Червоненкиса было в статистика. Он также применялся в дискретная геометрия[5] и теория графов.[6]

Определения и заявление

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

В терминах этих определений лемма Зауэра – Шелаха утверждает, что если это семейство наборов с различные элементы, такие что, тогда разбивает множество размеров . Эквивалентно, если размер VC является тогда может состоять не более чем из наборы.

Оценка леммы точна: пусть семейство состоять из всех подмножеств с размером меньше чем . Тогда размер точно но он не разбивает ни один набор размеров .[7]

Количество разбитых сетов

Усиление леммы Зауэра – Шелаха в силу Пайор (1985), утверждает, что каждое конечное семейство множеств разбивает по крайней мере наборы.[8] Отсюда сразу следует лемма Зауэра – Шелаха, поскольку только подмножеств -item universe имеет мощность меньше, чем . Таким образом, когда , недостаточно маленьких наборов, которые можно разбить, поэтому одно из разбитых наборов должно иметь мощность не менее .

Для ограниченного типа разбитого набора, называемого набором с разбитым порядком, количество разбитых наборов всегда равно мощности семейства наборов.[9]

Доказательство

Вариант Паджора леммы Зауэра – Шелаха может быть доказан математическая индукция; доказательство по-разному приписывалось Нога Алон[10] или чтобы Рон Ахарони и Рон Хольцман.[9]

Основание: каждая семья, состоящая только из одного набора, разбивает пустой набор.

Шаг: Предположим, что лемма верна для всех семейств размером меньше и разреши быть семьей из двух или более наборов. Позволять быть элементом, который принадлежит некоторым, но не всем множествам в . Расколоть на два подсемейства, из наборов, содержащих и множества, не содержащие .

По предположению индукции эти два подсемейства разрушают два набора множеств, размеры которых прибавляют не менее .

Ни один из этих разбитых наборов не содержит , так как набор, содержащий не может быть разрушен семьей, в которой все наборы содержат или все наборы не содержат .

Некоторые из разрушенных множеств могут быть разрушены обоими подсемействами. Когда набор разрушается только одним из двух подсемейств, он вносит вклад в одну единицу как в число разрушенных наборов подсемейства, так и в число разрушенных наборов . Когда набор разрушается обоими подсемействами, оба и разбиты , так вносит две единицы в число разрушенных наборов подсемейств и . Следовательно, количество разрушенных наборов по крайней мере равно количеству разделенных на два подсемейства , что не менее .

Другое доказательство леммы Зауэра – Шелаха в его первоначальной форме: Петер Франкл и Янош Пах, основан на линейная алгебра и принцип включения-исключения.[5][7]

Приложения

Первоначальное применение леммы Вапником и Червоненкисом состояло в том, чтобы показать, что каждое распределение вероятностей может быть аппроксимировано (по отношению к семейству событий данной размерности ВК) конечным набором выборочных точек, чьи мощность зависит только от размерности VC семейства событий. В этом контексте есть два важных понятия приближения, оба параметризованные числом ε: множество S выборок, и распределение вероятностей на S, называется ε-приближением исходного распределения, если вероятность каждого события относительно S отличается от исходной вероятности не более чем на ε. Множество S (невзвешенных) образцов считается ε-сеть если каждое событие с вероятностью не менее ε включает хотя бы одну точку S. Ε-приближение также должно быть ε-сеткой, но не обязательно наоборот.

Вапник и Червоненкис использовали лемму, чтобы показать, что системы множеств размерности ВК d всегда имеют ε-приближения мощности . Более поздние авторы, в том числе Хаусслер и Вельцль (1987)[11] и Комлос, Пах и Вегингер (1992)[12] аналогично показал, что всегда существуют ε-сети мощности , а точнее мощности не более .[5] Основная идея доказательства существования малых ε-сетей состоит в выборе случайной выборки Икс мощности и вторая независимая случайная выборка у мощности , и ограничить вероятность того, что Икс пропущено какое-то большое событие E вероятностью того, что Икс пропущено и одновременно пересечение у с E больше медианного значения. Для любого конкретного E, вероятность того, что Икс пропущено пока у больше, чем его медиана, очень мала, и лемма Зауэра – Шелаха (примененная к ) показывает, что лишь небольшое количество отдельных событий E необходимо учитывать, поэтому связанный союз, с ненулевой вероятностью, Икс является ε-сетью.[5]

В свою очередь, ε-сети и ε-приближения, а также вероятность того, что случайная выборка достаточно большой мощности обладает этими свойствами, имеют важные приложения в машинное обучение, в районе наверное приблизительно правильное обучение.[13] В вычислительная геометрия, они были применены к поиск диапазона,[11] дерандомизация,[14] и аппроксимационные алгоритмы.[15][16]

Козьма и Моран (2013) использовать обобщения леммы Зауэра – Шелаха, чтобы доказать результаты в теория графов например, количество сильные ориентации данного графа зажат между его числами связаны и 2-кромочно-соединенные подграфы.[6]

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

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

  1. ^ Зауэр, Н. (1972), "О плотности семейств множеств", Журнал комбинаторной теории, Серия А, 13: 145–147, Дои:10.1016/0097-3165(72)90019-2, МИСТЕР 0307902.
  2. ^ Шелах, Сахарон (1972), «Комбинаторная проблема; устойчивость и порядок для моделей и теорий на бесконечных языках», Тихоокеанский математический журнал, 41: 247–261, Дои:10.2140 / pjm.1972.41.247, МИСТЕР 0307903, заархивировано из оригинал на 2013-10-05.
  3. ^ Вапник, В.; Červonenkis, A. Ja. (1971), «Равномерная сходимость частот появления событий к их вероятностям», Академия Наук СССР, 16: 264–279, МИСТЕР 0288823.
  4. ^ а б Бузагло, Сарит; Пинчаси, Рим; Роте, Гюнтер (2013), «Топологические гиперграфы», в Пах, Янош (ред.), Тридцать очерков по теории геометрических графов, Springer, стр. 71–81, Дои:10.1007/978-1-4614-0110-0_6.
  5. ^ а б c d Пах, Янош; Агарвал, Панкадж К. (1995), Комбинаторная геометрия, Серия Wiley-Interscience по дискретной математике и оптимизации, Нью-Йорк: John Wiley & Sons Inc., стр.247, Дои:10.1002/9781118033203, ISBN 0-471-58890-3, МИСТЕР 1354145.
  6. ^ а б Козьма, Ласло; Моран, Шэй (2013), «Разрушение, ориентация графиков и взаимосвязь», Электронный журнал комбинаторики, 20 (3), P44, arXiv:1211.1319, Bibcode:2012arXiv1211.1319K.
  7. ^ а б Гауэрс, Тимоти (31 июля 2008 г.), «Аргументы размерности в комбинаторике», Журнал Гауэрса: обсуждения, связанные с математикой, Пример 3.
  8. ^ Pajor, Ален (1985), Sous-espaces des espaces de Banach, Travaux en Cours [Работа в процессе], 16, Париж: Герман, ISBN 2-7056-6021-6, МИСТЕР 0903247. Как цитирует Ансти, Роньяи и Сали (2002).
  9. ^ а б Anstee, R.P .; Роньяи, Лайош; Сали, Аттила (2002), «Разрушительные новости», Графы и комбинаторика, 18 (1): 59–73, Дои:10.1007 / s003730200003, МИСТЕР 1892434.
  10. ^ Калаи, Гил (28 сентября 2008 г.), «Экстремальная комбинаторика III: некоторые основные теоремы», Комбинаторика и многое другое.
  11. ^ а б Хаусслер, Дэвид; Вельцль, Эмо (1987), "ε-сети и симплексные запросы диапазона", Дискретная и вычислительная геометрия, 2 (2): 127–151, Дои:10.1007 / BF02187876, МИСТЕР 0884223.
  12. ^ Комлош, Янош; Пах, Янош; Woeginger, Герхард (1992), "Почти точные оценки для ε-сетей", Дискретная и вычислительная геометрия, 7 (2): 163–173, Дои:10.1007 / BF02187833, МИСТЕР 1139078.
  13. ^ Блумер, Ансельм; Эренфойхт, Анджей; Хаусслер, Дэвид; Вармут, Манфред К. (1989), «Обучаемость и измерение Вапника – Червоненкиса», Журнал ACM, 36 (4): 929–965, Дои:10.1145/76359.76371, МИСТЕР 1072253.
  14. ^ Шазель, Б.; Фридман Дж. (1990), "Детерминированный взгляд на случайную выборку и ее использование в геометрии", Комбинаторика, 10 (3): 229–249, Дои:10.1007 / BF02122778, МИСТЕР 1092541.
  15. ^ Brönnimann, H .; Гудрич, М. Т. (1995), "Почти оптимальные покрытия множеств в конечной VC-размерности", Дискретная и вычислительная геометрия, 14 (4): 463–479, Дои:10.1007 / BF02570718, МИСТЕР 1360948.
  16. ^ Хар-Пелед, Сариэль (2011), «О сложности, выборке, ε-сетях и ε-выборках», Алгоритмы геометрической аппроксимации, Математические обзоры и монографии, 173, Провиденс, Род-Айленд: Американское математическое общество, стр. 61–85, ISBN 978-0-8218-4911-8, МИСТЕР 2760023.