En matemáticas combinatorias y teoría de conjuntos extremos , el lema de Sauer-Shelah establece que cada familia de conjuntos con una pequeña dimensión de VC consta de un pequeño número de conjuntos. Lleva el nombre de Norbert Sauer y Saharon Shelah , quienes lo publicaron de forma independiente en 1972. [1] [2] El mismo resultado también fue publicado un poco antes y nuevamente de forma independiente, por Vladimir Vapnik y Alexey Chervonenkis , después de quienes la dimensión VC es nombrado. [3] En su artículo que contiene el lema, Shelah le da crédito también a Micha Perles, y por esta razón el lema también se ha denominado lema de Perles-Sauer-Shelah . [4]
Buzaglo y col. llamar a este lema "uno de los resultados más fundamentales en la dimensión VC", [4] y tiene aplicaciones en muchas áreas. La motivación de Sauer estaba en la combinatoria de sistemas de conjuntos, mientras que la de Shelah estaba en la teoría de modelos y la de Vapnik y Chervonenkis estaba en las estadísticas . También se ha aplicado en geometría discreta [5] y teoría de grafos . [6]
Definiciones y declaración
Si es una familia de conjuntos, y es otro conjunto, entonces se dice que está destrozado por si cada subconjunto de (incluido el conjunto vacío y sí mismo) se puede obtener como una intersección Entre y un conjunto en la familia. La dimensión VC dees la cardinalidad más grande de un conjunto destrozado por.
En términos de estas definiciones, el lema Sauer-Shelah establece que si es una familia de conjuntos con elementos distintos tales que , luego rompe un conjunto de tamaño . De manera equivalente, si la dimensión VC de es luego puede consistir en como máximo conjuntos.
El límite del lema es estrecho: deje que la familia estar compuesto por todos los subconjuntos de con un tamaño menor que . Entonces el tamaño de es exactamente pero no rompe ningún conjunto de tamaño . [7]
El número de conjuntos destrozados
Un fortalecimiento del lema de Sauer-Shelah, debido a Pajor (1985) , establece que cada familia de conjuntos finitosse rompe al menos conjuntos. [8] Esto implica inmediatamente el lema Sauer-Shelah, porque solo de los subconjuntos de un -el universo de elementos tiene cardinalidad menor que . Por lo tanto, cuando, no hay suficientes conjuntos pequeños para ser destrozados, por lo que uno de los conjuntos destrozados debe tener cardinalidad al menos .
Para un tipo restringido de conjunto destrozado, llamado conjunto de orden destrozado, el número de conjuntos destrozados siempre es igual a la cardinalidad de la familia de conjuntos. [9]
Prueba
La variante de Pajor del lema Sauer-Shelah puede demostrarse por inducción matemática ; la prueba se ha atribuido a Noga Alon [10] oa Ron Aharoni y Ron Holzman. [9]
Base: cada familia de un solo conjunto rompe el conjunto vacío.
Paso: Suponga que el lema es verdadero para todas las familias de tamaño inferior a y deja ser una familia de dos o más conjuntos. Dejar ser un elemento que pertenece a algunos pero no a todos los conjuntos en . Separar en dos subfamilias, de los conjuntos que contienen y los conjuntos que no contienen .
Por el supuesto de inducción, estas dos subfamilias rompen dos colecciones de conjuntos cuyos tamaños se suman al menos a .
Ninguno de estos conjuntos destrozados contiene , ya que un conjunto que contiene no puede ser destrozado por una familia en la que todos los conjuntos contienen o todos los conjuntos no contienen .
Algunos de los conjuntos destrozados pueden ser destrozados por ambas subfamilias. Cuando un set está destrozada por sólo una de las dos subfamilias, aporta una unidad tanto al número de conjuntos destrozados de la subfamilia como al número de conjuntos destrozados de . Cuando un set es destrozada por ambas subfamilias, ambas y son destrozados por , entonces contribuye dos unidades al número de conjuntos destrozados de las subfamilias y de . Por lo tanto, el nmero de conjuntos destrozados de es al menos igual al número destrozado por las dos subfamilias de , que es al menos .
Una prueba diferente del lema de Sauer-Shelah en su forma original, por Péter Frankl y János Pach , se basa en el álgebra lineal y el principio de inclusión-exclusión . [5] [7]
Aplicaciones
La aplicación original del lema, por Vapnik y Chervonenkis, fue mostrar que toda distribución de probabilidad se puede aproximar (con respecto a una familia de eventos de una dimensión de VC dada) por un conjunto finito de puntos muestrales cuya cardinalidad depende sólo de la VC. dimensión de la familia de eventos. En este contexto, hay dos nociones importantes de aproximación, ambas parametrizadas por un número ε: un conjunto S de muestras y una distribución de probabilidad en S , se dice que es una aproximación ε de la distribución original si la probabilidad de cada evento con respecto a S difiere de su probabilidad original en como máximo ε. Un conjunto S de muestras (no ponderado) se dice que es un ε-net si cada evento con una probabilidad de al menos ε incluye al menos un punto de S . Una aproximación ε también debe ser una ε-net, pero no necesariamente al revés.
Vapnik y Chervonenkis usaron el lema para mostrar que los sistemas de conjuntos de dimensión d de VC siempre tienen aproximaciones ε de cardinalidad. Autores posteriores, incluidos Haussler y Welzl (1987) [11] y Komlós, Pach y Woeginger (1992) [12], mostraron de manera similar que siempre existen redes ε de cardinalidad, y más precisamente de cardinalidad a lo sumo . [5] La idea principal de la prueba de la existencia de redes ε pequeñas es elegir una muestra aleatoria x de cardinalidady una segunda muestra aleatoria independiente y de cardinalidad, y unir la probabilidad de que x se pase por alto por algún evento grande E por la probabilidad de que x se pase por alto y, simultáneamente, la intersección de y con E sea mayor que su valor mediano. Para cualquier E en particular , la probabilidad de que se pase por alto x mientras que y es mayor que su mediana es muy pequeña, y el lema de Sauer-Shelah (aplicado a) muestra que solo es necesario considerar un pequeño número de eventos distintos E , por lo que por el límite de unión , con probabilidad distinta de cero, x es una red ε. [5]
A su vez, las redes ε y las aproximaciones ε, y la probabilidad de que una muestra aleatoria de cardinalidad suficientemente grande tenga estas propiedades, tienen aplicaciones importantes en el aprendizaje automático , en el área del aprendizaje probablemente aproximadamente correcto . [13] En geometría computacional , se han aplicado a la búsqueda de rango , [11] desaleatorización , [14] y algoritmos de aproximación . [15] [16]
Kozma y Moran (2013) utilizan generalizaciones del lema de Sauer-Shelah para demostrar resultados en la teoría de grafos , como que el número de orientaciones fuertes de un gráfico dado se intercala entre sus números de subgrafos conectados y de 2 bordes conectados . [6]
Ver también
- Función de crecimiento
Referencias
- ^ Sauer, N. (1972), "Sobre la densidad de familias de conjuntos", Journal of Combinatorial Theory , Serie A, 13 : 145-147, doi : 10.1016 / 0097-3165 (72) 90019-2 , MR 0307902.
- ^ Shelah, Saharon (1972), "Un problema combinatorio; estabilidad y orden para modelos y teorías en lenguajes infinitarios" , Pacific Journal of Mathematics , 41 : 247-261, doi : 10.2140 / pjm.1972.41.247 , MR 0307903 , archivado de el original el 2013-10-05.
- ^ Vapnik, VN ; Červonenkis, A. Ja. (1971), "La convergencia uniforme de frecuencias de aparición de eventos a sus probabilidades", Akademija Nauk SSSR , 16 : 264-279, MR 0288823.
- ^ a b Buzaglo, Sarit; Pinchasi, Rom; Rote, Günter (2013), "Topological hypergraphs", en Pach, János (ed.), Thirty Essays on Geometric Graph Theory , Springer, págs. 71–81, doi : 10.1007 / 978-1-4614-0110-0_6.
- ^ a b c d Pach, János ; Agarwal, Pankaj K. (1995), Geometría combinatoria , Serie Wiley-Interscience en Matemáticas discretas y optimización, Nueva York: John Wiley & Sons Inc., p. 247 , doi : 10.1002 / 9781118033203 , ISBN 0-471-58890-3, MR 1354145.
- ^ a b Kozma, László; Moran, Shay (2013), "Destrucción, orientaciones gráficas y conectividad" , Electronic Journal of Combinatorics , 20 (3), P44, arXiv : 1211.1319 , Bibcode : 2012arXiv1211.1319K.
- ^ a b Gowers, Timothy (31 de julio de 2008), "Argumentos de dimensión en combinatoria" , Weblog de Gowers: Discusiones relacionadas con las matemáticas , Ejemplo 3.
- ^ Pajor, Alain (1985), Sous-espacesdes espaces de Banach , Travaux en Cours [Obras en curso], 16 , París: Hermann, ISBN 2-7056-6021-6, MR 0903247. Según lo citado por Anstee, Rónyai & Sali (2002) .
- ^ a b Anstee, RP; Rónyai, Lajos; Sali, Attila (2002), "Shattering news", Graphs and Combinatorics , 18 (1): 59–73, doi : 10.1007 / s003730200003 , MR 1892434.
- ^ Kalai, Gil (28 de septiembre de 2008), "Combinatoria extrema III: algunos teoremas básicos" , combinatoria y más.
- ^ a b Haussler, David ; Welzl, Emo (1987), "ε-nets and simplex range queries", Discrete and Computational Geometry , 2 (2): 127-151, doi : 10.1007 / BF02187876 , MR 0884223.
- ^ Komlós, János ; Pach, János ; Woeginger, Gerhard (1992), " Límites casi estrechos para redes ε", Geometría discreta y computacional , 7 (2): 163-173, doi : 10.1007 / BF02187833 , MR 1139078.
- ^ Blumer, Anselm; Ehrenfeucht, Andrzej; Haussler, David ; Warmuth, Manfred K. (1989), "Capacidad de aprendizaje y la dimensión de Vapnik-Chervonenkis", Journal of the ACM , 36 (4): 929-965, doi : 10.1145 / 76359.76371 , MR 1072253.
- ^ Chazelle, B .; Friedman, J. (1990), "Una visión determinista del muestreo aleatorio y su uso en geometría", Combinatorica , 10 (3): 229–249, doi : 10.1007 / BF02122778 , MR 1092541.
- ^ Brönnimann, H .; Goodrich, MT (1995), "Cubiertas de conjuntos casi óptimos en dimensión VC finita", Geometría discreta y computacional , 14 (4): 463–479, doi : 10.1007 / BF02570718 , MR 1360948.
- ^ Har-Peled, Sariel (2011), "Sobre complejidad, muestreo y redes ε y muestras ε", algoritmos de aproximación geométrica , encuestas y monografías matemáticas, 173 , Providence, RI: American Mathematical Society, págs. 61–85, ISBN 978-0-8218-4911-8, MR 2760023.