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

Понятие в комбинаторике

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

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

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

Определения и утверждения

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

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

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

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

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

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

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

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

База

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

Шаг

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

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

Приложения

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

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

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

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

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

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

Ссылки

1. Зауэр, Н. (1972), «О плотности семейств множеств», Журнал комбинаторной теории , Серия A, 13 : 145–147, doi : 10.1016/0097-3165(72)90019-2, MR  0307902.
2. Shelah, Saharon (1972), «Комбинаторная проблема; устойчивость и порядок для моделей и теорий в бесконечных языках», Pacific Journal of Mathematics , 41 : 247–261, doi : 10.2140/pjm.1972.41.247 , MR  0307903, архивировано из оригинала 2013-10-05.
3. Вапник, В.Н .; Червоненкис, А.Я. (1971), «Равномерная сходимость частот появления событий к их вероятностям», Академия наук СССР , 16 : 264–279, MR  0288823.
4. Buzaglo, Sarit; Pinchasi, Rom; Rote, Günter (2013), «Топологические гиперграфы», в Pach, János (ред.), Thirty Essays on Geometric Graph Theory , Springer, стр. 71–81, doi :10.1007/978-1-4614-0110-0_6.
5. Камби, Стейн; Черномаз, Богдан; Двир, Зеев; Фильмус, Юваль; Моран, Шей (2020), «Лемма Зауэра-Шела-Перлеса для решеток», Electronic Journal of Combinatorics , 27 (4): P4.19, arXiv : 1807.04957 , doi : 10.37236/9273.
6. Pach, János ; Agarwal, Pankaj K. (1995), Комбинаторная геометрия, Wiley-Interscience Series in Discrete Mathematics and Optimization, Нью-Йорк: John Wiley & Sons Inc., стр. 247, doi : 10.1002/9781118033203, ISBN 0-471-58890-3, г-н  1354145.
7. Kozma, László; Moran, Shay (2013), "Разрушение, ориентация графов и связность", Electronic Journal of Combinatorics , 20 (3), P44, arXiv : 1211.1319 , Bibcode : 2012arXiv1211.1319K, MR  3118952.
8. Гауэрс, Тимоти (31 июля 2008 г.), «Аргументы размерности в комбинаторике», Веблог Гауэрса: обсуждения, связанные с математикой , Пример 3.
9. Пажор, Ален (1985), Sous-espaces des espaces de Banach , Travaux en Cours [Работы в стадии разработки], vol. 16, Париж: Герман, ISBN ${\displaystyle l_{1}^{n}}$ 2-7056-6021-6, МР  0903247. Как цитируют Anstee, Rónyai & Sali (2002).
10. Anstee, RP; Rónyai, Lajos; Sali, Attila (2002), «Shattering news», Graphs and Combinatorics , 18 (1): 59–73, doi :10.1007/s003730200003, MR  1892434.
11. Калай, Джил (28 сентября 2008 г.), «Экстремальная комбинаторика III: некоторые основные теоремы», Комбинаторика и многое другое.
12. Хаусслер, Дэвид ; Вельцль, Эмо (1987), " -сети и запросы симплексного диапазона", Дискретная и вычислительная геометрия , 2 (2): 127–151, doi : 10.1007/BF02187876 , MR  0884223 ${\displaystyle \varepsilon }$.
13. Комлос, Янош ; Пах, Янош ; Воегингер, Герхард (1992), «Почти узкие границы для -сетей», Дискретная и вычислительная геометрия , 7 (2): 163–173, doi : 10.1007/BF02187833 , MR  1139078 ${\displaystyle \varepsilon }$.
14. Блюмер, Ансельм; Эренфойхт, Анджей; Хаусслер, Дэвид ; Вармут, Манфред К. (1989), «Обучаемость и измерение Вапника – Червоненкиса», Журнал ACM , 36 (4): 929–965, doi : 10.1145/76359.76371 , MR  1072253.
15. Шазелл, Б.; Фридман, Дж. (1990), «Детерминированный взгляд на случайную выборку и ее использование в геометрии», Combinatorica , 10 (3): 229–249, doi :10.1007/BF02122778, MR  1092541.
16. Brönnimann, H.; Goodrich, MT (1995), «Почти оптимальные покрытия множеств в конечной размерности VC», Discrete and Computational Geometry , 14 (4): 463–479, doi : 10.1007/BF02570718 , MR  1360948.
17. Har-Peled, Sariel (2011), «О сложности, выборке и -сетях и -выборках», Геометрические алгоритмы аппроксимации , Математические обзоры и монографии, т. 173, Провиденс, Род-Айленд: Американское математическое общество, стр. 61–85, ISBN ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon }$ 978-0-8218-4911-8, МР  2760023.