跳转到内容

绍尔-谢拉赫引理

维基百科,自由的百科全书
绍尔-谢拉赫引理,经帕约尔推广的版本:对于每个有限族(绿色),都存在同样多个集合组成的另一族(蓝色),使得蓝色族中每个集合,都被绿色族“打碎英语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.