紹爾-謝拉赫引理

若集合族的VC維低,則不能有太多個集合

组合数学極值集合論英语extremal set theory中,紹爾-謝拉赫引理(英語:Sauer–Shelah lemma)斷言,若集合族VC维低,則該族不能有太多個集合。引理得名於諾貝特·紹爾[1]薩哈龍·謝拉赫英语Saharon Shelah[2],兩人分別獨立於1972年發表此結果。[註 1]較之略早,在1971年,弗拉基米尔·瓦普尼克亞歷克塞·澤范蘭傑斯合著的論文[6]已有此結果(「VC維」即以兩人為名)。謝拉赫發表引理時,亦歸功於米哈·佩爾萊斯英语Micha Perles,故引理又稱為佩爾萊斯-紹爾-謝拉赫引理[7]

紹爾-謝拉赫引理,經帕约尔推廣的版本:對於每個有限族(綠色),都存在同樣多個集合組成的另一族(藍色),使得藍色族中每個集合,都被綠色族「打碎英语shattered set」。

布萨格洛等人稱其為「關於VC維的最根本結論之一」[7]。引理在若干方面有應用,就各發現者的研究動機而言,紹爾是研究集族的組合學,謝拉赫研究模型论,VC二氏則研究统计学。後來,引理亦用於离散几何[8]图论[9]

定義及敍述

 為一族集合, 為另一集,此時所謂  碎裂集英语shattered set,意思是 的每個子集(包括空集 本身),皆可表示成 與該族某集之交  的VC維是其打碎的最大集的大小

利用以上術語,紹爾-謝拉赫引理可以寫成:

 是一族集合,且各集合中,合共衹有 個不同元素,但  ,則 打碎某個 元集合。

所以,若 的VC維為 (故不打碎任何 元集),則 中至多衹有 個集合。

引理所給的界已是最優:考慮 元集 中,所有小於 個元素的子集,所成的族 。該族的大小恰為 ,但是不打碎任何 元集。[10]

打碎多少集合

帕约尔將紹爾-謝拉赫引理加強為:[12]

有限族 必打碎至少 個集合。

紹爾-謝拉赫引理為其直接推論,因為 元全集的子集中,衹有 個的元素個數小於 。故 時,即使全部小集皆已打碎,仍不足 個,故必有打碎某個不少於 元的集合。

亦可將「碎裂」的概念加以限縮,變成「順序碎裂」(order-shattered)。此時,任意集族順序打碎的集合數,必恰好等於該族的大小。[11]

紹爾-謝拉赫引理的帕約爾變式可使用数学归纳法證明,此證法一說出自諾加·阿隆[13],一說出自朗·阿哈羅尼英语Ron Aharoni及朗·霍爾茲曼(Ron Holzman[11]

作為歸納法的起始步驟,單一個集合組成的族 ,能打碎空集,已足 個。

至於遞推步驟,可假設引理對任意少於 個集合組成的族皆成立,且族 有至少兩個集合,故可選取元素 為其一的元素,但不屬於另一集。如此便可將 的集合分成兩類:包含 的集合歸入子族 ,不含 的則歸入 

由歸納假設,兩子族各自打碎的集合數,其和至少為 

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

若集 衹被一個子族打碎,則數算兩子族打碎的集合時, 計為一個,數 打碎的集合時亦計為一個。但 也可能同時被兩子族打碎,如此,數算兩子族打碎的集合時,會將 計兩次;不過 既打碎 ,也打碎 ,所以 (和 )在數 打碎的集合時,也計為兩次。由此, 打碎的集合數,不小於兩子族各自打碎集合數之和,從而不小於 

紹爾-謝拉赫引理的原始形式還有另一種證明,利用线性代数容斥原理,該證法由弗龍克爾·彼得英语Péter Frankl保奇·亞諾什英语János Pach給出。[8][10]

應用

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

  1. 取樣集 上的概率分佈定義為原分佈的「 近似」(英語: -approximation),意思是每個事件被 以該分佈取樣的概率,與原概率所差不過 
  2. 取樣集 (不設權重)定義為「ε英语ε-net (computational geometry)」,意思是概率不小於 的任一事件中,必含 中至少一點。

由定義, 近似必為 網,反之則不一定。

VC二氏以此引理證明,若某集族的VC維為 ,則必有大小不過  近似。其後,Haussler & Welzl (1987)[14]Komlós, Pach & Woeginger (1992)[15]等發表了類似的結果,證明必存在大小為  網,具體上界為 [8]證明存在小 網的主要方法是,先揀選 個點的隨機樣本 ,再獨立揀選另 個點的隨機樣本 ,然後證明以下的不等式:存在某個較大事件  不交的概率 ,與存在同樣的事件,且該事件與 相交點數大於中位值的概率 ,兩概率之比至多為 。若固定  ,則 不交   相交點數多於中位值的概率很小。由紹爾-謝拉赫引理,  的交集的可能情況並不太多,計算「存在 滿足條件」的概率時,衹需對每種交集的可能性考慮一個 ,因此由併集上界,可得 ,故 有非零概率為 網。[8]

以上論證說明隨機取樣足夠多個點就可能是 網。此性質以及 網、 近似兩概念本身,皆在机器学习概率近似正確學習英语probably approximately correct learning方面有應用。[16]计算几何方面的應用則有範圍搜索英语range searching[14]去随机化英语derandomization[17]近似算法[18][19]

Kozma & Moran (2013)利用紹爾-謝拉赫引理的推廣,證明若干圖論結果,例如:圖的強定向英语strong orientation[註 2]方案數介於其連通子圖數與邊雙連通英语k-edge-connected graph子圖數之間。[9]

  1. ^ 多個來源斷言此處(以及與下文VC二氏的發現)的獨立性[3],如[4][5]
  2. ^ 為每條邊選定一方向,使全幅圖強連通

參考文獻

  1. ^ Sauer, N. On the density of families of sets. Journal of Combinatorial Theory英语Journal of Combinatorial Theory. Series A. 1972, 13: 145–147. MR 0307902. doi:10.1016/0097-3165(72)90019-2  (英语). 
  2. ^ Shelah, Saharon. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics. 1972, 41: 247–261. MR 0307903. doi:10.2140/pjm.1972.41.247 . (原始内容存档于2013-10-05) (英语). 
  3. ^ Bottou, Leon. On the Vapnik-Chevonenkis-Sauer lemma. [2022-03-07]. (原始内容存档于2022-03-19) (英语). 
  4. ^ Bollobás, Béla; Radcliff, A.J. Defect Sauer results. Journal of Combinatorial Theory, Series A. 1995, 72: 189–208. doi:10.1016/0097-3165(95)90060-8 (英语). 
  5. ^ Smola, Alexander J.; Mendelson, Shahar. Advanced Lectures on Machine Learning. Springer. 2003: 12. ISBN 9783540364344 (英语). 
  6. ^ Vapnik, V. N.; Červonenkis, A. Ja. The uniform convergence of frequencies of the appearance of events to their probabilities. Akademija Nauk SSSR. 1971, 16: 264–279. MR 0288823 (英语). 
  7. ^ 7.0 7.1 Buzaglo, Sarit; Pinchasi, Rom; Rote, Günter. Topological hypergraphs. Pach, János (编). Thirty Essays on Geometric Graph Theory. Springer. 2013: 71–81. doi:10.1007/978-1-4614-0110-0_6  (英语). 
  8. ^ 8.0 8.1 8.2 8.3 Pach, János; Agarwal, Pankaj K. Combinatorial geometry. Wiley-Interscience Series in Discrete Mathematics and Optimization. New York: John Wiley & Sons Inc.: 247–251. 1995. ISBN 0-471-58890-3. MR 1354145. doi:10.1002/9781118033203  (英语). 
  9. ^ 9.0 9.1 Kozma, László; Moran, Shay. Shattering, Graph Orientations, and Connectivity. Electronic Journal of Combinatorics英语Electronic Journal of Combinatorics. 2013, 20 (3). P44 [2022-03-06]. Bibcode:2012arXiv1211.1319K. MR 3118952. arXiv:1211.1319 . (原始内容存档于2022-05-25) (英语). 
  10. ^ 10.0 10.1 Gowers, Timothy. Dimension arguments in combinatorics. Gowers's Weblog: Mathematics related discussions. Example 3. 2008-07-31 [2022-03-12]. (原始内容存档于2022-07-09) (英语). 
  11. ^ 11.0 11.1 11.2 Anstee, R. P.; Rónyai, Lajos; Sali, Attila. Shattering news. Graphs and Combinatorics英语Graphs and Combinatorics. 2002, 18 (1): 59–73. MR 1892434. doi:10.1007/s003730200003  (英语). 
  12. ^ Pajor, Alain. Sous-espaces   des espaces de Banach. Travaux en Cours 16. Paris: Hermann. 1985. ISBN 2-7056-6021-6. MR 0903247 (法语). [11]引述。
  13. ^ Kalai, Gil. Extremal Combinatorics III: Some Basic Theorems. Combinatorics and More. 2008-09-28 [2022-03-13]. (原始内容存档于2022-03-13) (英语). 
  14. ^ 14.0 14.1 Haussler, David; Welzl, Emo. ε-nets and simplex range queries. Discrete and Computational Geometry英语Discrete and Computational Geometry. 1987, 2 (2): 127–151. MR 0884223. doi:10.1007/BF02187876 . 
  15. ^ Komlós, János; Pach, János; Woeginger, Gerhard. Almost tight bounds for ε-nets. Discrete and Computational Geometry英语Discrete and Computational Geometry. 1992, 7 (2): 163–173. MR 1139078. doi:10.1007/BF02187833 . .
  16. ^ Blumer, Anselm; Ehrenfeucht, Andrzej; Haussler, David; Warmuth, Manfred K. Learnability and the Vapnik–Chervonenkis dimension. Journal of the ACM. 1989, 36 (4): 929–965. MR 1072253. doi:10.1145/76359.76371. 
  17. ^ Chazelle, B.; Friedman, J. A deterministic view of random sampling and its use in geometry. Combinatorica英语Combinatorica. 1990, 10 (3): 229–249. MR 1092541. doi:10.1007/BF02122778 . 
  18. ^ Brönnimann, H.; Goodrich, M. T. Almost optimal set covers in finite VC-dimension. Discrete and Computational Geometry英语Discrete and Computational Geometry. 1995, 14 (4): 463–479. MR 1360948. doi:10.1007/BF02570718 . 
  19. ^ Har-Peled, Sariel. On complexity, sampling, and ε-nets and ε-samples. Geometric approximation algorithms. Mathematical Surveys and Monographs 173. Providence, RI: American Mathematical Society. 2011: 61–85. ISBN 978-0-8218-4911-8. MR 2760023.