查看“︁紹爾-謝拉赫引理”︁的源代码

[[File:Sauer–Shelah lemma.svg|thumb|upright=1.35|紹爾-謝拉赫引理，經帕约尔推廣的版本：對於每個有限族（綠色），都存在同樣多個集合組成的另一族（藍色），使得藍色族中每個集合，都被綠色族「{{le|碎裂集|shattered set|打碎}}」。]]
[[组合数学]]和{{link-en|極值集合論|extremal set theory}}中，'''紹爾-謝拉赫引理'''（{{lang-en|Sauer–Shelah lemma}}）斷言，若[[集合族]]的[[VC维]]低，則該族不能有太多個集合。引理得名於諾貝特·紹爾<!--似乎是德國/奧地利數學家，姓名按《世界人名翻译大辞典》譯法--><ref>{{cite journal
 | last = Sauer | first = N.
 | journal = {{link-en|Journal of Combinatorial Theory}}
 | mr = 0307902
 | pages = 145–147
 | series = Series A
 | title = On the density of families of sets 
 | volume = 13
 | year = 1972
 | doi=10.1016/0097-3165(72)90019-2
 | doi-access=free
 | language = en}}</ref>和{{link-en|薩哈龍·謝拉赫|Saharon Shelah}}<!--按[[WP:外語譯音表/希伯來語]]--><ref>{{cite journal
 |last    = Shelah
 |first   = Saharon
 |journal = Pacific Journal of Mathematics
 |mr      = 0307903
 |pages   = 247–261
 |title   = A combinatorial problem; stability and order for models and theories in infinitary languages
 |url     = http://projecteuclid.org/getRecord?id=euclid.pjm/1102968432
 |archive-url = https://archive.today/20131005003706/http://projecteuclid.org/getRecord?id=euclid.pjm/1102968432
 |url-status = dead
 |archive-date = 2013-10-05
 |volume  = 41
 |year    = 1972
 |doi     = 10.2140/pjm.1972.41.247
 |doi-access= free
 |language = en
 }}</ref>，兩人分別獨立於1972年發表此結果。{{註|多個來源斷言此處（以及與下文VC二氏的發現）的獨立性<ref>{{cite web |url = https://leon.bottou.org/news/vapnik-chervonenkis_sauer |first = Leon |last = Bottou |title = On the Vapnik-Chevonenkis-Sauer lemma |language = en |access-date = 2022-03-07 |archive-date = 2022-03-19 |archive-url = https://web.archive.org/web/20220319012352/https://leon.bottou.org/news/vapnik-chervonenkis_sauer }}</ref>，如<ref>{{ 
cite journal|title = Defect Sauer results|first1 = Béla|last1 = Bollobás|first2 = A.J. |last2 = Radcliff |doi = 10.1016/0097-3165(95)90060-8 | journal = Journal of Combinatorial Theory, Series A|volume = 72|year = 1995|pages = 189-208|language = en}}</ref><ref>{{cite book|first1 = Alexander J. |last1 = Smola|first2 =  Shahar|last2 = Mendelson| title = Advanced Lectures on Machine Learning | publisher = Springer|isbn = 9783540364344|year = 2003|page = [https://www.google.co.uk/books/edition/Advanced_Lectures_on_Machine_Learning/YTVsCQAAQBAJ?hl=en&gbpv=1&pg=PA12&printsec=frontcover 12]|language = en}}</ref>。}}較之略早，在1971年，[[弗拉基米尔·瓦普尼克]]和[[亞歷克塞·澤范蘭傑斯]]合著的論文<ref>{{cite journal
 | last1 = Vapnik | first1 = V. N. | author1-link = Vladimir Vapnik
 | last2 = Červonenkis | first2 = A. Ja. | author2-link = Alexey Chervonenkis
 | journal = Akademija Nauk SSSR
 | mr = 0288823
 | pages = 264–279
 | title = The uniform convergence of frequencies of the appearance of events to their probabilities
 | volume = 16
 | year = 1971 
 | language = en}}</ref>已有此結果（「VC維」即以兩人為名）。謝拉赫發表引理時，亦歸功於{{link-en|米哈·佩爾萊斯|Micha Perles}}<!--按[[WP:外語譯音表/希伯來語]]-->，故引理又稱為'''佩爾萊斯-紹爾-謝拉赫引理'''。<ref name="brr">{{cite book
 | last1 = Buzaglo | first1 = Sarit
 | last2 = Pinchasi | first2 = Rom
 | last3 = Rote | first3 = Günter
 | editor-last = Pach | editor-first = János | editor-link = János Pach
 | contribution = Topological hypergraphs
 | doi = 10.1007/978-1-4614-0110-0_6 | doi-access=free
 | pages = [https://archive.org/details/thirtyessaysonge00pach/page/n84 71]–81
 | publisher = Springer
 | title = Thirty Essays on Geometric Graph Theory
 | url = https://archive.org/details/thirtyessaysonge00pach | year = 2013
 | language = en}}</ref>

布萨格洛等人稱其為「關於VC維的最根本結論之一」<ref name="brr"/>。引理在若干方面有應用，就各發現者的研究動機而言，紹爾是研究集族的[[組合學]]，謝拉赫研究[[模型论]]，VC二氏則研究[[统计学]]。後來，引理亦用於[[离散几何]]<ref name="pa95">{{cite journal
 | last1 = Pach
 | first1 = János
 | author1-link = János Pach
 | last2 = Agarwal
 | first2 = Pankaj K.
 | author2-link = Pankaj K. Agarwal
 | doi = 10.1002/9781118033203
 | isbn = 0-471-58890-3
 | location = New York
 | mr = 1354145
 | page = [https://archive.org/details/combinatorialgeo0000pach/page/247 247]–251
 | publisher = John Wiley & Sons Inc.
 | series = Wiley-Interscience Series in Discrete Mathematics and Optimization
 | title = Combinatorial geometry
 | year = 1995
 | url = https://archive.org/details/combinatorialgeo0000pach/page/247
 | doi-access = free
 |language = en
 }}</ref>和[[图论]]<ref name="km13">{{cite journal
 | last1 = Kozma
 | first1 = László
 | last2 = Moran
 | first2 = Shay
 | arxiv = 1211.1319
 | journal = {{link-en|Electronic Journal of Combinatorics}}
 | volume = 20
 | issue = 3
 | at = P44
 | title = Shattering, Graph Orientations, and Connectivity
 | url = http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i3p44
 | year = 2013
 | bibcode = 2012arXiv1211.1319K
 | language = en
 | access-date = 2022-03-06
 | archive-date = 2022-05-25
 | archive-url = https://web.archive.org/web/20220525201840/https://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i3p44
 | ref = harv
 | mr = 3118952
 }}</ref>。

==定義及敍述==
設<math> \textstyle \mathcal{F}=\{S_1,S_2,\dots\}</math>為一族集合，<math>T</math>為另一集，此時所謂<math>T</math>為<math>\mathcal{F}</math>的{{le|碎裂集|shattered set}}，意思是<math>T</math>的每個子集（包括[[空集]]和<math>T</math>本身），皆可表示成<math>T</math>與該族某集之交<math>T\cap S_i</math>。<math>\mathcal{F}</math>的VC維是其打碎的最大集的[[势 (数学)|大小]]。

利用以上術語，紹爾-謝拉赫引理可以寫成：
<blockquote>
若<math>\mathcal{F}</math>是一族集合，且各集合中，合共衹有<math>n</math>個不同元素，但
<math> \textstyle |\mathcal{F}| > \sum_{i=0}^{k-1} {\binom{n}{i}}</math>，則<math>\mathcal{F}</math>打碎某個<math>k</math>元集合。
</blockquote>

所以，若<math>\mathcal{F}</math>的VC維為<math>k</math>（故不打碎任何<math>k + 1</math>元集），則<math>\mathcal{F}</math>中至多衹有<math>\textstyle \sum_{i=0}^{k} {\binom{n}{i}} =O(n^k)</math>個集合。

引理所給的界已是最優：考慮<math>n</math>元集<math>\{1,2,\dots, n\}</math>中，所有小於<math>k</math>個元素的子集，所成的族<math>\mathcal{F}</math>。該族的大小恰為<math>\textstyle \sum_{i=0}^{k-1} {\binom{n}{i}}</math>，但是不打碎任何<math>k</math>元集。<ref name="gowers">{{cite web|title=Dimension arguments in combinatorics|at=Example 3|first=Timothy|last=Gowers|authorlink=Timothy Gowers|work=Gowers's Weblog: Mathematics related discussions|url=http://gowers.wordpress.com/2008/07/31/dimension-arguments-in-combinatorics/|date=2008-07-31|language=en|access-date=2022-03-12|archive-date=2022-07-09|archive-url=https://web.archive.org/web/20220709043635/https://gowers.wordpress.com/2008/07/31/dimension-arguments-in-combinatorics/}}</ref>

==打碎多少集合==
帕约尔將紹爾-謝拉赫引理加強為：{{refn|{{cite journal
 | last = Pajor | first = Alain
 | isbn = 2-7056-6021-6
 | location = Paris
 | mr = 903247
 | publisher = Hermann
 | series = Travaux en Cours
 | title = Sous-espaces <math>l^n_1</math> des espaces de Banach
 | volume = 16
 | year = 1985
 |language = fr}} 由<ref name = "ars02"/>引述。}}

<blockquote>
有限族<math>\mathcal{F}</math>必打碎至少<math>|\mathcal{F}|</math>個集合。
</blockquote>
紹爾-謝拉赫引理為其直接推論，因為<math>n</math>元全集的子集中，衹有<math>\textstyle \sum_{i=0}^{k-1} {\binom{n}{i}} </math>個的元素個數小於<math>k</math>。故<math>\textstyle |\mathcal{F}|>\sum_{i=0}^{k-1} {\binom{n}{i}}</math>時，即使全部小集皆已打碎，仍不足<math>|\mathcal{F}|</math>個，故必有打碎某個不少於<math>k</math>元的集合。

亦可將「碎裂」的概念加以限縮，變成「順序碎裂」（{{lang|en|order-shattered}}）。此時，任意集族順序打碎的集合數，必恰好等於該族的大小。<ref name="ars02">{{cite journal
 | last1 = Anstee | first1 = R. P.
 | last2 = Rónyai | first2 = Lajos
 | last3 = Sali | first3 = Attila
 | doi = 10.1007/s003730200003 | doi-access=free
 | issue = 1
 | journal = {{le|Graphs and Combinatorics}}
 | mr = 1892434
 | pages = 59–73
 | title = Shattering news
 | volume = 18
 | year = 2002
 | ref = harv
 | language = en
}}</ref> 
== 證 ==
紹爾-謝拉赫引理的帕約爾變式可使用[[数学归纳法]]證明，此證法一說出自[[諾加·阿隆]]<ref>{{cite web|url=http://gilkalai.wordpress.com/2008/09/28/extremal-combinatorics-iii-some-basic-theorems/|first=Gil|last=Kalai|authorlink=Gil Kalai|title=Extremal Combinatorics III: Some Basic Theorems|work=Combinatorics and More|date=2008-09-28|language=en|access-date=2022-03-13|archive-date=2022-03-13|archive-url=https://web.archive.org/web/20220313040534/https://gilkalai.wordpress.com/2008/09/28/extremal-combinatorics-iii-some-basic-theorems/}}</ref>，一說出自{{link-en|朗·阿哈羅尼|Ron Aharoni}}及朗·霍爾茲曼（{{lang|en|Ron Holzman}}）<ref name="ars02"/>。

作為歸納法的起始步驟，單一個集合組成的族<math>\mathcal F</math>，能打碎[[空集]]，已足<math>|\mathcal F|</math>個。

至於遞推步驟，可假設引理對任意少於<math>|\mathcal F|</math>個集合組成的族皆成立，且族<math>\mathcal{F}</math>有至少兩個集合，故可選取元素<math>x</math>為其一的元素，但不屬於另一集。如此便可將<math>\mathcal{F}</math>的集合分成兩類：包含<math>x</math>的集合歸入子族<math>\mathcal F_1</math>，不含<math>x</math>的則歸入<math>\mathcal F_0</math>。

由歸納假設，兩子族各自打碎的集合數，其和至少為<math>|\mathcal F_0| + |\mathcal F_1| = |\mathcal{F}|</math>。 

該些碎裂集不能有元素<math>x</math>，因為若要打碎某個有<math>x</math>的集合<math>A</math>，則族中需要有含<math>x</math>的集合，也需要有不含<math>x</math>的集合，纔能使該族各集與<math>A</math>的交集出齊<math>A</math>的全體子集。

若集<math>S</math>衹被一個子族打碎，則數算兩子族打碎的集合時，<math>S</math>計為一個，數<math>\mathcal{F}</math>打碎的集合時亦計為一個。但<math>S</math>也可能同時被兩子族打碎，如此，數算兩子族打碎的集合時，會將<math>S</math>計兩次；不過<math>\mathcal F</math>既打碎<math>S</math>，也打碎<math>S\cup\{x\}</math>，所以<math>S</math>（和<math>S\cup\{x\}</math>）在數<math>\mathcal{F}</math>打碎的集合時，也計為兩次。由此，<math>\mathcal F</math>打碎的集合數，不小於兩子族各自打碎集合數之和，從而不小於<math>|\mathcal{F}|</math>。

紹爾-謝拉赫引理的原始形式還有另一種證明，利用[[线性代数]]及[[容斥原理]]，該證法由{{link-en|弗龍克爾·彼得|Péter Frankl}}<!--沿用[[圖蘭·帕爾]]一文的譯名-->和{{link-en|保奇·亞諾什|János Pach}}<!--沿用[[塞邁雷迪－特羅特定理]]的譯名-->給出。<ref name="pa95"/><ref name="gowers"/>

== 應用 ==
VC二氏原先將引理應用於證明，若考慮一族VC維固定的事件，則衹需有限多個取樣點，即可近似任意的概率分佈（使取樣所得的事件概率近似該分佈下的事件概率），且取樣點的個數衹取決於VC維數。具體而言，有兩種意義下的近似，各由參數<math>\varepsilon</math>定義：

#取樣集<math>S</math>上的概率分佈定義為原分佈的「<math>\varepsilon</math>近似」（{{lang-en|<math>\varepsilon</math>-approximation}}），意思是每個事件被<math>S</math>以該分佈取樣的概率，與原概率所差不過<math>\varepsilon</math>。
#取樣集<math>S</math>（不設權重）定義為「{{link-en|ε網 (計算幾何)|ε-net (computational geometry)|''ε''網}}」，意思是概率不小於<math>\varepsilon</math>的任一事件中，必含<math>S</math>中至少一點。

由定義，<math>\varepsilon</math>近似必為<math>\varepsilon</math>網，反之則不一定。

VC二氏以此引理證明，若某集族的VC維為<math>d</math>，則必有大小不過<math>O(\tfrac{d}{\varepsilon^2}\log\tfrac{d}{\varepsilon})</math>的<math>\varepsilon</math>近似。其後，{{harvtxt|Haussler|Welzl|1987}}<ref name="hw87">{{cite journal
 | last1 = Haussler | first1 = David | author1-link = David Haussler
 | last2 = Welzl | first2 = Emo | author2-link = Emo Welzl
 | doi = 10.1007/BF02187876
 | issue = 2
 | journal = {{link-en|離散與計算幾何|Discrete and Computational Geometry|Discrete and Computational Geometry}}
 | mr = 884223
 | pages = 127–151
 | title = ε-nets and simplex range queries
 | volume = 2
 | year = 1987| doi-access = free
 }}</ref>和{{harvtxt|Komlós|Pach|Woeginger|1992}}<ref>{{cite journal
 | last1 = Komlós | first1 = János | author1-link = János Komlós (mathematician)
 | last2 = Pach | first2 = János | author2-link = János Pach
 | last3 = Woeginger | first3 = Gerhard | author3-link = Gerhard J. Woeginger
 | doi = 10.1007/BF02187833
 | issue = 2
 | journal = {{link-en|離散與計算幾何|Discrete and Computational Geometry|Discrete and Computational Geometry}}
 | mr = 1139078
 | pages = 163–173
 | title = Almost tight bounds for ε-nets
 | volume = 7
 | year = 1992| doi-access = free
 }}.</ref>等發表了類似的結果，證明必存在大小為<math>O(\tfrac{d}{\varepsilon}\log\tfrac{1}{\varepsilon})</math>的<math>\varepsilon</math>網，具體上界為<math>\tfrac{d}{\varepsilon}\ln\tfrac{1}{\varepsilon}+\tfrac{2d}{\varepsilon}\ln\ln\tfrac{1}{\varepsilon}+\tfrac{6d}{\varepsilon}</math>。<ref name="pa95"/>證明存在小<math>\varepsilon</math>網的主要方法是，先揀選<math>O(\tfrac{d}{\varepsilon}\log\tfrac{1}{\varepsilon})</math>個點的隨機樣本<math>x</math>，再獨立揀選另<math>O(\tfrac{d}{\varepsilon}\log^2\tfrac{1}{\varepsilon})</math>個點的隨機樣本<math>y</math>，然後證明以下的不等式：存在某個較大事件<math>E</math>與<math>x</math>不交的概率<math>p_1</math>，與存在同樣的事件，且該事件與<math>y</math>相交點數大於中位值的概率<math>p_2</math>，兩概率之比至多為<math>2</math>。若固定<math>E</math>和<math>x \cup y</math>，則<math>x</math>不交<math>E</math>而<math>y</math>與<math>E</math>相交點數多於中位值的概率很小。由紹爾-謝拉赫引理，<math>E</math>與<math>x \cup y</math>的交集的可能情況並不太多，計算「存在<math>E</math>滿足條件」的概率時，衹需對每種交集的可能性考慮一個<math>E</math>，因此由[[布尔不等式|併集上界]]，可得<math>p_1 \le 2p_2 < 1</math>，故<math>x</math>有非零概率為<math>\varepsilon</math>網。<ref name="pa95"/>

以上論證說明隨機取樣足夠多個點就可能是<math>\varepsilon</math>網。此性質以及<math>\varepsilon</math>網、<math>\varepsilon</math>近似兩概念本身，皆在[[机器学习]]和{{link-en|概率近似正確學習|probably approximately correct learning}}方面有應用。<ref>{{cite journal
 | last1 = Blumer | first1 = Anselm
 | last2 = Ehrenfeucht | first2 = Andrzej
 | last3 = Haussler | first3 = David | author3-link = David Haussler
 | last4 = Warmuth | first4 = Manfred K.
 | doi = 10.1145/76359.76371
 | issue = 4
 | journal = [[ACM期刊|Journal of the ACM]]
 | mr = 1072253
 | pages = 929–965
 | title = Learnability and the Vapnik–Chervonenkis dimension
 | volume = 36
 | year = 1989}}</ref>[[计算几何]]方面的應用則有{{link-en|範圍搜索|range searching}}<ref name="hw87"/>、{{le|去随机化|derandomization}}<ref>{{cite journal 
 | last1 = Chazelle | first1 = B. | author1-link = Bernard Chazelle
 | last2 = Friedman | first2 = J.
 | doi = 10.1007/BF02122778 | doi-access=free
 | issue = 3
 | journal = {{link-en|Combinatorica}}
 | mr = 1092541
 | pages = 229–249
 | title = A deterministic view of random sampling and its use in geometry
 | volume = 10
 | year = 1990}}</ref>、[[近似算法]]<ref>{{cite journal
 | last1 = Brönnimann | first1 = H.
 | last2 = Goodrich | first2 = M. T. | author2-link = Michael T. Goodrich
 | doi = 10.1007/BF02570718
 | issue = 4
 | journal = {{link-en|離散與計算幾何|Discrete and Computational Geometry|Discrete and Computational Geometry}}
 | mr = 1360948
 | pages = 463–479
 | title = Almost optimal set covers in finite VC-dimension
 | volume = 14
 | year = 1995| doi-access = free
 }}</ref><ref>{{cite book
 | last = Har-Peled | first = Sariel | authorlink = Sariel Har-Peled
 | contribution = On complexity, sampling, and ε-nets and ε-samples
 | isbn = 978-0-8218-4911-8
 | location = Providence, RI
 | mr = 2760023
 | pages = 61–85
 | publisher = American Mathematical Society
 | series = Mathematical Surveys and Monographs
 | title = Geometric approximation algorithms
 | volume = 173
 | year = 2011}}</ref>。

{{harvtxt|Kozma|Moran|2013}}利用紹爾-謝拉赫引理的推廣，證明若干[[圖論]]結果，例如：圖的{{link-en|強定向|strong orientation}}{{註|為每條邊選定一方向，使全幅圖[[強連通]]。}}方案數介於其[[连通性 (图论)|連通]]子圖數與{{le|邊k連通|k-edge-connected graph|邊雙連通}}子圖數之間。<ref name="km13"/>

== 註 ==
{{備註表}}

== 參考文獻 ==
{{reflist|30em}}

[[Category:集合族]]
[[Category:引理]]