Лемма Зауэра – Шелы

В комбинаторной математике и экстремальной теории множеств лемма Зауэра -Шела утверждает, что каждое семейство множеств с небольшой размерностью VC состоит из небольшого числа множеств. Он назван в честь Норберта Зауэра и Сахарона Шелаха , которые опубликовали его независимо друг от друга в 1972 году. ^{[ 1 ]}^{[ 2 ]} Тот же результат был опубликован немного ранее и снова независимо Владимиром Вапником и Алексеем Червоненкисом , в честь которых названо измерение венчурного капитала. ^{[ 3 ]} В своей статье, содержащей лемму, Шела также отдает должное Михе Перлесу , ^{[ 2 ]} и по этой причине лемму также назвали леммой Перлеса-Зауэра-Шела и леммой Зауэра-Шела-Перлеса . ^{[ 4 ]}^{[ 5 ]}

Бузагло и др. назовите эту лемму «одним из наиболее фундаментальных результатов о VC-размерности», ^{[ 4 ]} и он имеет применение во многих областях. Мотивацией Зауэра была комбинаторика систем множеств, Шелаха - теория моделей , а Вапника и Червоненкиса - статистика . Он также применялся в дискретной геометрии. ^{[ 6 ]} и теория графов . ^{[ 7 ]}

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

Если $\textstyle {\mathcal {F}}=\{S_{1},S_{2},\dots \}$ представляет собой семейство множеств и $T$ это набор, то $T$ говорят, что разбит он ${\mathcal {F}}$ если каждое подмножество $T$ (включая пустой набор и $T$ себя) можно получить как пересечение $T\cap S_{i}$ из $T$ с некоторым набором $S_{i}$ в семье. Размер венчурного капитала ${\mathcal {F}}$ — наибольшая мощность множества, разбитого ${\mathcal {F}}$ .

В терминах этих определений лемма Зауэра – Шелаха утверждает, что если ${\mathcal {F}}$ это семейство множеств, объединение которых имеет $n$ элементов, а если количество комплектов в семействе, $|{\mathcal {F}}|$ , подчиняется неравенству $|{\mathcal {F}}|>\sum _{i=0}^{k-1}{\binom {n}{i}},$ затем ${\mathcal {F}}$ разрушает набор размеров $k$ . Эквивалентно, если размерность VC ${\mathcal {F}}$ является $k,$ затем ${\mathcal {F}}$ может состоять максимум из $\sum _{i=0}^{k}{\binom {n}{i}}=O(n^{k})$ множества, как это выражается с использованием обозначения большого О.

Граница леммы жесткая: пусть семья ${\mathcal {F}}$ состоять из всех подмножеств $\{1,2,\dots ,n\}$ размером менее $k$ . Тогда размер ${\mathcal {F}}$ это точно ${\textstyle \sum _{i=0}^{k-1}{\binom {n}{i}}}$ но это не разрушает ни один набор размеров $k$ . ^{[ 8 ]}

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

Усиление леммы Зауэра-Шела, предложенное Паджором (1985) , утверждает, что каждое семейство конечных множеств ${\mathcal {F}}$ по крайней мере разобьется $|{\mathcal {F}}|$ наборы. ^{[ 9 ]} Отсюда немедленно следует лемма Зауэра–Шела, поскольку только ${\textstyle \sum _{i=0}^{k-1}{\tbinom {n}{i}}}$ подмножеств $n$ -вселенная элементов имеет мощность меньше, чем $k$ . Таким образом, когда $|{\mathcal {F}}|>\sum _{i=0}^{k-1}{\binom {n}{i}},$ не хватает маленьких множеств, которые можно разбить, поэтому одно из разбитых множеств должно иметь мощность не менее $k$ .

Для ограниченного типа разрушенного множества, называемого набором с нарушенным порядком, количество разрушенных множеств всегда равно мощности семейства множеств. ^{[ 10 ]}

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

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

База: Каждая семья, имеющая только один набор, разбивает пустой набор.
Шаг: Предположим, что лемма верна для всех семейств размером менее $|{\mathcal {F}}|$ и пусть ${\mathcal {F}}$ быть семьей из двух или более комплектов. Позволять $x$ быть элементом, принадлежащим некоторым, но не всем множествам в ${\mathcal {F}}$ . Расколоть ${\mathcal {F}}$ на два подсемейства множеств, содержащих $x$ и множества, не содержащие $x$ . По предположению индукции эти два подсемейства разделяют две коллекции множеств, размеры которых составляют как минимум $|{\mathcal {F}}|$ . Ни один из этих разбитых наборов не содержит $x$ , поскольку набор, содержащий $x$ не может быть разрушена семьей, в которой все множества содержат $x$ или все наборы не содержат $x$ . Некоторые из разбитых множеств могут быть разбиты обоими подсемействами. Когда набор $S$ разбито только одним из двух подсемейств, оно вносит одну единицу как в число разбитых множеств подсемейства, так и в число разбитых множеств подсемейства. ${\mathcal {F}}$ . Когда набор $S$ раздроблено обоими подсемействами, обоими $S$ и $S\cup \{x\}$ разбиты ${\mathcal {F}}$ , так $S$ вносит две единицы в число разбитых множеств подсемейств и ${\mathcal {F}}$ . Таким образом, количество разбитых комплектов ${\mathcal {F}}$ по крайней мере равно числу, разбитому двумя подсемействами ${\mathcal {F}}$ , что по крайней мере $|{\mathcal {F}}|$ .

Другое доказательство леммы Зауэра-Шела в ее первоначальной форме, предложенное Петером Франклом и Яношем Пахом , основано на линейной алгебре и принципе включения-исключения . ^{[ 6 ]}^{[ 8 ]} Это доказательство распространяется и на другие параметры, такие как семейства векторных пространств и, в более общем смысле, на геометрические решетки . ^{[ 5 ]}

Приложения

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

Вапник и Червоненкис использовали лемму, чтобы показать, что системы множеств размерности VC $d$ всегда иметь $\varepsilon$ -аппроксимации мощности $O({\tfrac {d}{\varepsilon ^{2}}}\log {\tfrac {d}{\varepsilon }}).$ Более поздние авторы, включая Хаусслера и Вельцля (1987). ^{[ 12 ]} и Комлос, Пач и Вегингер (1992) ^{[ 13 ]} аналогичным образом показал, что всегда существуют $\varepsilon$ -сети мощности $O({\tfrac {d}{\varepsilon }}\log {\tfrac {1}{\varepsilon }})$ , а точнее мощности не более ^{[ 6 ]} ${\tfrac {d}{\varepsilon }}\ln {\tfrac {1}{\varepsilon }}+{\tfrac {2d}{\varepsilon }}\ln \ln {\tfrac {1}{\varepsilon }}+{\tfrac {6d}{\varepsilon }}.$ Основная идея доказательства существования малых $\varepsilon$ -nets – это выбор случайной выборки $x$ мощности ${\textstyle O({\tfrac {d}{\varepsilon }}\log {\tfrac {1}{\varepsilon }})}$ и вторая независимая случайная выборка $y$ мощности ${\textstyle O({\tfrac {d}{\varepsilon }}\log ^{2}{\tfrac {1}{\varepsilon }})}$ , и ограничить вероятность того, что $x$ пропустил какое-то большое событие $E$ по вероятности того, что $x$ пропущено и одновременно пересечение $y$ с $E$ больше его медианного значения. Для любого конкретного $E$ , вероятность того, что $x$ пропущен, пока $y$ больше, чем его медиана, очень мала, и лемма Зауэра–Шела (применительно к $x\cup y$ ) показывает, что лишь небольшое количество различных событий $E$ необходимо учитывать, поэтому по объединению с ненулевой вероятностью $x$ это $\varepsilon$ -сеть. ^{[ 6 ]}

По очереди, $\varepsilon$ -сети и $\varepsilon$ -аппроксимации и вероятность того, что случайная выборка достаточно большой мощности обладает этими свойствами, имеют важные применения в машинном обучении , в области вероятно приблизительно правильного обучения . ^{[ 14 ]} В вычислительной геометрии они применялись для поиска диапазона . ^{[ 12 ]} дерандомизация , ^{[ 15 ]} и алгоритмы аппроксимации . ^{[ 16 ]}^{[ 17 ]}

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

См. также

Функция роста

Ссылки

^ Зауэр, Н. (1972), «О плотности семейств множеств», Журнал комбинаторной теории , серия A, 13 : 145–147, doi : 10.1016/0097-3165(72)90019-2 , MR 0307902 .
^ Jump up to: ^а ^б Шела, Сахарон (1972), «Комбинаторная проблема; стабильность и порядок моделей и теорий в бесконечных языках» , Pacific Journal of Mathematics , 41 : 247–261, doi : 10.2140/pjm.1972.41.247 , MR 0307903 , заархивировано из оригинал на 05.10.2013 .
^ Вапник, В.Н. ; Червоненкис, А.Я. (1971), "Равномерная сходимость частот появления событий к их вероятностям", Академия наук СССР , 16 : 264–279, МР 0288823 .
^ Jump up to: ^а ^б Бузагло, Сарит; Пинчаси, Ром; Роте, Гюнтер (2013), «Топологические гиперграфы», в Пач, Янош (редактор), «Тридцать эссе по геометрической теории графов » , Springer, стр. 71–81, doi : 10.1007/978-1-4614-0110-0_6 .
^ Jump up to: ^а ^б Камби, Стейн; Черномаз, Богдан; Двир, Зеев; Фильмус, Юваль; Моран, Шей (2020), «Лемма Зауэра-Шела-Перлеса для решеток» , Electronic Journal of Combinatorics , 27 (4): P4.19, arXiv : 1807.04957 , doi : 10.37236/9273 .
^ Jump up to: ^а ^б ^с ^д Пах, Янош ; Агарвал, Панкадж К. (1995), Комбинаторная геометрия , Серия Wiley-Interscience по дискретной математике и оптимизации, Нью-Йорк: John Wiley & Sons Inc., стр. 247 , номер домена : 10.1002/9781118033203 , ISBN 0-471-58890-3 , МР 1354145 .
^ Jump up to: ^а ^б Козма, Ласло; Моран, Шей (2013), «Разрушение, ориентации графов и связность» , Электронный журнал комбинаторики , 20 (3), P44, arXiv : 1211.1319 , Bibcode : 2012arXiv1211.1319K , MR 3118952 .
^ Jump up to: ^а ^б Гауэрс, Тимоти (31 июля 2008 г.), «Аргументы размерностей в комбинаторике» , Блог Гауэрса: обсуждения, связанные с математикой , Пример 3 .
^ Пажор, Ален (1985), Подпространства $l_{1}^{n}$ банаховых пространств , Travaux en Cours [Работы в процессе], vol. 16, Париж: Герман, ISBN 2-7056-6021-6 , МР 0903247 . Цитируется Ансти, Роньяи и Сали (2002) .
^ Jump up to: ^а ^б Ансти, РП; Роньяи, Лайош; Сали, Аттила (2002), «Потрясающие новости», Графики и комбинаторика , 18 (1): 59–73, doi : 10.1007/s003730200003 , MR 1892434 .
^ Калаи, Гил (28 сентября 2008 г.), «Экстремальная комбинаторика III: некоторые основные теоремы» , Комбинаторика и многое другое .
^ Jump up to: ^а ^б Хаусслер, Дэвид ; Вельцль, Эмо (1987), " $\varepsilon$ -сети и запросы симплексного диапазона», Discrete and Computational Geometry , 2 (2): 127–151, doi : 10.1007/BF02187876 , MR 0884223 .
^ Комлос, Янош ; Пах, Янош ; Воегингер, Герхард (1992), «Почти узкие границы для $\varepsilon$ -сети», Дискретная и вычислительная геометрия , 7 (2): 163–173, doi : 10.1007/BF02187833 , MR 1139078 .
^ Блюмер, Ансельм; Эренфойхт, Анджей; Хаусслер, Дэвид ; Вармут, Манфред К. (1989), «Обучаемость и измерение Вапника-Червоненкиса», Журнал ACM , 36 (4): 929–965, doi : 10.1145/76359.76371 , MR 1072253 .
^ Шазель, Б. ; Фридман Дж. (1990), «Детерминистический взгляд на случайную выборку и ее использование в геометрии», Combinatorica , 10 (3): 229–249, doi : 10.1007/BF02122778 , MR 1092541 .
^ Брённиманн, Х.; Гудрич, М.Т. (1995), «Покрытия почти оптимальных множеств в конечной VC-размерности», Дискретная и вычислительная геометрия , 14 (4): 463–479, doi : 10.1007/BF02570718 , MR 1360948 .
^ Хар-Пелед, Сариэль (2011), «О сложности, выборке и $\varepsilon$ -сети и $\varepsilon$ -выборки», Алгоритмы геометрической аппроксимации , Математические обзоры и монографии, т. 173, Провиденс, Род-Айленд: Американское математическое общество, стр. 61–85, ISBN 978-0-8218-4911-8 , МР 2760023 .

[sauer-1] Зауэр, Н. (1972), «О плотности семейств множеств», Журнал комбинаторной теории , серия A, 13 : 145–147, doi : 10.1016/0097-3165(72)90019-2 , MR 0307902 .

[shelah-2] Jump up to: ^а ^б Шела, Сахарон (1972), «Комбинаторная проблема; стабильность и порядок моделей и теорий в бесконечных языках» , Pacific Journal of Mathematics , 41 : 247–261, doi : 10.2140/pjm.1972.41.247 , MR 0307903 , заархивировано из оригинал на 05.10.2013 .

[vc-3] Вапник, В.Н. ; Червоненкис, А.Я. (1971), "Равномерная сходимость частот появления событий к их вероятностям", Академия наук СССР , 16 : 264–279, МР 0288823 .

[brr-4] Jump up to: ^а ^б Бузагло, Сарит; Пинчаси, Ром; Роте, Гюнтер (2013), «Топологические гиперграфы», в Пач, Янош (редактор), «Тридцать эссе по геометрической теории графов » , Springer, стр. 71–81, doi : 10.1007/978-1-4614-0110-0_6 .

[ccdfm-5] Jump up to: ^а ^б Камби, Стейн; Черномаз, Богдан; Двир, Зеев; Фильмус, Юваль; Моран, Шей (2020), «Лемма Зауэра-Шела-Перлеса для решеток» , Electronic Journal of Combinatorics , 27 (4): P4.19, arXiv : 1807.04957 , doi : 10.37236/9273 .

[pa95-6] Jump up to: ^а ^б ^с ^д Пах, Янош ; Агарвал, Панкадж К. (1995), Комбинаторная геометрия , Серия Wiley-Interscience по дискретной математике и оптимизации, Нью-Йорк: John Wiley & Sons Inc., стр. 247 , номер домена : 10.1002/9781118033203 , ISBN 0-471-58890-3 , МР 1354145 .

[km13-7] Jump up to: ^а ^б Козма, Ласло; Моран, Шей (2013), «Разрушение, ориентации графов и связность» , Электронный журнал комбинаторики , 20 (3), P44, arXiv : 1211.1319 , Bibcode : 2012arXiv1211.1319K , MR 3118952 .

[gowers-8] Jump up to: ^а ^б Гауэрс, Тимоти (31 июля 2008 г.), «Аргументы размерностей в комбинаторике» , Блог Гауэрса: обсуждения, связанные с математикой , Пример 3 .

[pajor-9] Пажор, Ален (1985), Подпространства $l_{1}^{n}$ банаховых пространств , Travaux en Cours [Работы в процессе], vol. 16, Париж: Герман, ISBN 2-7056-6021-6 , МР 0903247 . Цитируется Ансти, Роньяи и Сали (2002) .

[ars02-10] Jump up to: ^а ^б Ансти, РП; Роньяи, Лайош; Сали, Аттила (2002), «Потрясающие новости», Графики и комбинаторика , 18 (1): 59–73, doi : 10.1007/s003730200003 , MR 1892434 .

[kalai-11] Калаи, Гил (28 сентября 2008 г.), «Экстремальная комбинаторика III: некоторые основные теоремы» , Комбинаторика и многое другое .

[hw87-12] Jump up to: ^а ^б Хаусслер, Дэвид ; Вельцль, Эмо (1987), " $\varepsilon$ -сети и запросы симплексного диапазона», Discrete and Computational Geometry , 2 (2): 127–151, doi : 10.1007/BF02187876 , MR 0884223 .

[kpw-13] Комлос, Янош ; Пах, Янош ; Воегингер, Герхард (1992), «Почти узкие границы для $\varepsilon$ -сети», Дискретная и вычислительная геометрия , 7 (2): 163–173, doi : 10.1007/BF02187833 , MR 1139078 .

[behw-14] Блюмер, Ансельм; Эренфойхт, Анджей; Хаусслер, Дэвид ; Вармут, Манфред К. (1989), «Обучаемость и измерение Вапника-Червоненкиса», Журнал ACM , 36 (4): 929–965, doi : 10.1145/76359.76371 , MR 1072253 .

[cf-15] Шазель, Б. ; Фридман Дж. (1990), «Детерминистический взгляд на случайную выборку и ее использование в геометрии», Combinatorica , 10 (3): 229–249, doi : 10.1007/BF02122778 , MR 1092541 .

[bg-16] Брённиманн, Х.; Гудрич, М.Т. (1995), «Покрытия почти оптимальных множеств в конечной VC-размерности», Дискретная и вычислительная геометрия , 14 (4): 463–479, doi : 10.1007/BF02570718 , MR 1360948 .

[har-peled-17] Хар-Пелед, Сариэль (2011), «О сложности, выборке и $\varepsilon$ -сети и $\varepsilon$ -выборки», Алгоритмы геометрической аппроксимации , Математические обзоры и монографии, т. 173, Провиденс, Род-Айленд: Американское математическое общество, стр. 61–85, ISBN 978-0-8218-4911-8 , МР 2760023 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]