跳至內容

紹爾-謝拉赫引理

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

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

布薩格洛等人稱其為「關於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.