Sauer – Shelahovo lemma - Sauer–Shelah lemma

Pajorova formulace Sauer-Shelahova lematu: pro každou konečnou rodinu množin (zelená) existuje další rodina stejně mnoha sad (modré obrysy), takže každá sada ve druhé rodině je rozbitá první rodinou

v kombinatorická matematika a teorie extrémních množin, Sauer – Shelahovo lemma uvádí, že každý rodina sad s malými VC rozměr sestává z malého počtu sad. Je pojmenován po Norbert Sauer a Saharon Shelah, který jej publikoval nezávisle na sobě v roce 1972.^[1][2] Stejný výsledek byl také zveřejněn o něco dříve a znovu nezávisle, autorem Vladimír Vapnik a Alexey Chervonenkis, po kterém je pojmenována dimenze VC.^[3] Shelah ve svém příspěvku obsahujícím lemma připisuje zásluhu také Micha Perles, Z tohoto důvodu bylo lemma také nazýváno Perles – Sauer – Shelah lemma.^[4]

Buzaglo a kol. nazvat toto lemma „jedním z nejzásadnějších výsledků v dimenzi VC“,^[4] a má aplikace v mnoha oblastech. Sauerova motivace byla v kombinatorika nastavených systémů, zatímco byl Shelah teorie modelů a Vapnik a Chervonenkis byli v statistika. Bylo také použito v diskrétní geometrie^[5] a teorie grafů.^[6]

Definice a prohlášení

Li ${ displaystyle textstyle { mathcal {F}} = {S_ {1}, S_ {2}, tečky }}$ je rodina souprav a ${ displaystyle T}$ je tedy další sada ${ displaystyle T}$ se říká, že je rozbila podle ${ displaystyle { mathcal {F}}}$ pokud každá podmnožina ${ displaystyle T}$ (včetně prázdná sada a ${ displaystyle T}$ sám) lze získat jako křižovatku ${ displaystyle T cap S_ {i}}$ mezi ${ displaystyle T}$ a sada v rodině. VC rozměr ${ displaystyle { mathcal {F}}}$ je největší mohutnost sady rozbité ${ displaystyle { mathcal {F}}}$.

Pokud jde o tyto definice, lemma Sauer-Shelah uvádí, že pokud ${ displaystyle { mathcal {F}}}$ je rodina sad s ${ displaystyle n}$ odlišné prvky, jako je ten${ displaystyle textstyle | { mathcal {F}} |> sum _ {i = 0} ^ {k-1} { binom {n} {i}}}$, pak ${ displaystyle { mathcal {F}}}$ rozbije sadu velikostí ${ displaystyle k}$. Ekvivalentně, pokud je dimenze VC ${ displaystyle { mathcal {F}}}$ je ${ displaystyle k,}$ pak ${ displaystyle { mathcal {F}}}$ může sestávat maximálně ${ displaystyle textstyle sum _ {i = 0} ^ {k} { binom {n} {i}} = O (n ^ {k})}$ sady.

Hranice lemmatu je pevná: Nechte rodinu ${ displaystyle { mathcal {F}}}$ být složen ze všech podskupin ${ displaystyle {1,2, tečky n }}$ s velikostí menší než ${ displaystyle k}$. Pak velikost ${ displaystyle { mathcal {F}}}$ je přesně ${ displaystyle textstyle sum _ {i = 0} ^ {k-1} { binom {n} {i}}}$ ale nerozbije žádnou velikost ${ displaystyle k}$.^[7]

Počet rozbitých sad

Zesílení lemmatu Sauer-Shelah kvůli Pajor (1985), uvádí, že každá rodina konečných množin ${ displaystyle { mathcal {F}}}$rozbije se přinejmenším ${ displaystyle | { mathcal {F}} |}$ sady.^[8] To okamžitě implikuje Sauer – Shelahovo lemma, protože pouze ${ displaystyle sum _ {i = 0} ^ {k-1} { tbinom {n} {i}}}$ z podmnožin an ${ displaystyle n}$-témový vesmír má mohutnost menší než ${ displaystyle k}$. Takže kdy ${ displaystyle | { mathcal {F}} |> sum _ {i = 0} ^ {k-1} { tbinom {n} {i}}}$, není dost malých setů na rozbití, takže jeden z rozbitých setů musí mít alespoň mohutnost ${ displaystyle k}$.

U omezeného typu roztříštěné množiny, nazývané řádově rozbitá množina, se počet rozbitých množin vždy rovná mohutnosti rodiny množin.^[9]

Důkaz

Pajorovu variantu Sauer-Shelahova lema lze prokázat matematická indukce; důkaz byl různě připsán Noga Alon^[10] nebo do Ron Aharoni a Ron Holzman.^[9]

Základna: každá rodina pouze jedné sady rozbije prázdnou sadu.

Krok: Předpokládejme, že lemma platí pro všechny rodiny o velikosti menší než ${ displaystyle | { mathcal {F}} |}$ a nechte ${ displaystyle { mathcal {F}}}$ být rodina dvou nebo více sad. Nechat ${ displaystyle x}$ být prvkem, který patří do některých, ale ne do všech sad ${ displaystyle { mathcal {F}}}$. Rozdělit ${ displaystyle { mathcal {F}}}$ do dvou podskupin ze sad, které obsahují ${ displaystyle x}$ a sady, které neobsahují ${ displaystyle x}$.

Podle indukčního předpokladu tyto dvě podskupiny rozbijí dvě kolekce sad, jejichž velikosti přinejmenším přidávají ${ displaystyle | { mathcal {F}} |}$.

Žádná z těchto rozbitých sad neobsahuje ${ displaystyle x}$, protože sada, která obsahuje ${ displaystyle x}$ nelze rozbít rodinou, ve které všechny sady obsahují ${ displaystyle x}$ nebo všechny sady neobsahují ${ displaystyle x}$.

Některé z rozbitých sad mohou být rozbity oběma podskupinami. Když sada ${ displaystyle S}$ je rozbit pouze jednou ze dvou podskupin, přispívá jednou jednotkou jak k počtu rozbitých sad podrodiny, tak k počtu rozbitých sad ${ displaystyle { mathcal {F}}}$. Když sada ${ displaystyle S}$ je rozbita oběma podskupinami, oběma ${ displaystyle S}$ a ${ displaystyle S pohár {x }}$ jsou rozbiti ${ displaystyle { mathcal {F}}}$, tak ${ displaystyle S}$ přispívá dvěma jednotkami k počtu rozbitých sad podskupin a ${ displaystyle { mathcal {F}}}$. Proto počet rozbitých sad ${ displaystyle { mathcal {F}}}$ je přinejmenším rovné počtu rozbitých dvěma podskupinami ${ displaystyle { mathcal {F}}}$, což je minimálně ${ displaystyle | { mathcal {F}} |}$.

Jiný důkaz lemmatu Sauer-Shelah v jeho původní podobě, autor Péter Frankl a János Pach, je založeno na lineární algebra a zásada začlenění - vyloučení.^[5][7]

Aplikace

Původní aplikace lemmatu, kterou napsali Vapnik a Chervonenkis, byla v tom, že každé rozdělení pravděpodobnosti lze aproximovat (s ohledem na rodinu událostí dané dimenze VC) pomocí konečné sady vzorkovacích bodů, jejichž mohutnost záleží pouze na VC dimenzi rodiny událostí. V této souvislosti existují dva důležité pojmy aproximace, oba parametrizované číslem ε: množina S vzorků a rozdělení pravděpodobnosti na S, se říká, že je ε-aproximace původního rozdělení, pokud je pravděpodobnost každé události s ohledem na S se liší od své původní pravděpodobnosti maximálně ε. Sada S z (nevážených) vzorků se říká, že ε-net pokud každá událost s pravděpodobností alespoň ε zahrnuje alespoň jeden bod S. Ε-aproximace musí být také e-sítí, ale nemusí to být nutně naopak.

Vapnik a Chervonenkis pomocí lemmatu ukázali, že množinové systémy dimenze VC d vždy mají ε-aproximace mohutnosti ${ displaystyle O ({ tfrac {d} { epsilon ^ {2}}} log { tfrac {d} { epsilon}}}}$. Pozdější autoři včetně Haussler & Welzl (1987)^[11] a Komlós, Pach & Woeginger (1992)^[12] podobně ukázal, že vždy existují ε-sítě mohutnosti ${ displaystyle O ({ tfrac {d} { epsilon}} log { tfrac {1} { epsilon}})}$, a přesněji maximálně mohutnosti ${ displaystyle { tfrac {d} { epsilon}} ln { tfrac {1} { epsilon}} + { tfrac {2d} { epsilon}} ln ln { tfrac {1} { epsilon}} + { tfrac {6d} { epsilon}}}$.^[5] Hlavní myšlenkou důkazu existence malých ε-sítí je výběr náhodného vzorku X mohutnosti ${ displaystyle O ({ tfrac {d} { epsilon}} log { tfrac {1} { epsilon}})}$ a druhý nezávislý náhodný vzorek y mohutnosti ${ displaystyle O ({ tfrac {d} { epsilon}} log ^ {2} { tfrac {1} { epsilon}}}}$a omezit pravděpodobnost, že X chybí velká událost E pravděpodobností, že X je zmeškán a současně průsečík y s E je větší než jeho střední hodnota. Pro konkrétní E, pravděpodobnost, že X chybí y je větší než jeho medián je velmi malý a lemma Sauer – Shelah (platí pro ${ displaystyle x cup y}$) ukazuje, že pouze malý počet odlišných událostí E je třeba vzít v úvahu, takže odborově vázán, s nenulovou pravděpodobností, X je síť ε.^[5]

Ε-sítě a ε-aproximace a pravděpodobnost, že náhodný vzorek dostatečně velké mohutnosti má tyto vlastnosti, mají důležité aplikace v strojové učení, v oblasti pravděpodobně přibližně správné učení.^[13] v výpočetní geometrie, byly použity vyhledávání rozsahu,^[11] derandomizace,^[14] a aproximační algoritmy.^[15][16]

Kozma & Moran (2013) použít zevšeobecnění Sauer-Shelahova lematu k prokázání výsledků teorie grafů například počet silné orientace daného grafu je vloženo mezi jeho počty připojeno a 2-hrana připojena podgrafy.^[6]

Viz také

• Funkce růstu

Reference