El concepto de conjuntos destrozados juega un papel importante en la teoría de Vapnik-Chervonenkis , también conocida como teoría de VC. La rotura y la teoría de VC se utilizan en el estudio de procesos empíricos, así como en la teoría del aprendizaje computacional estadístico .
Definición
Suponga que A es un conjunto y C es una clase de conjuntos. La clase C rompe el conjunto A si para cada subconjunto a de A , hay algún elemento c de C tal que
De manera equivalente, C se rompe A cuando su intersección es igual a A' s conjunto potencia : P ( A ) = { c ∩ A | c ∈ C }.
Empleamos la letra C para referirnos a una "clase" o "colección" de conjuntos, como en una clase Vapnik-Chervonenkis (clase VC). A menudo se supone que el conjunto A es finito porque, en los procesos empíricos, nos interesa la destrucción de conjuntos finitos de puntos de datos.
Ejemplo
Demostraremos que la clase de todos los discos en el plano (espacio bidimensional) no rompe cada conjunto de cuatro puntos en el círculo unitario , sin embargo, la clase de todos los conjuntos convexos en el plano sí rompe cada conjunto finito de puntos en el círculo . círculo unitario .
Sea A un conjunto de cuatro puntos en el círculo unitario y sea C la clase de todos los discos.
A prueba en la que C se rompe A , intentamos dibujar un disco alrededor de cada subconjunto de puntos en una . Primero, dibujamos un disco alrededor de los subconjuntos de cada punto aislado. A continuación, intentamos dibujar un disco alrededor de cada subconjunto de pares de puntos. Esto resulta factible para puntos adyacentes, pero imposible para puntos en lados opuestos del círculo. Como se visualiza a continuación:
Cada punto individual se puede aislar con un disco (mostrando los cuatro).
Cada subconjunto de puntos adyacentes se puede aislar con un disco (mostrando uno de cuatro).
Un subconjunto de puntos en lados opuestos del círculo unitario no se puede aislar con un disco.
Debido a que existe un subconjunto que puede no ser aislado por cualquier disco en C , se concluye entonces que A no es destrozado por C . Y, con un poco de pensamiento, podemos probar que esta C no rompe ningún conjunto de cuatro puntos .
Sin embargo, si redefinimos C para que sea la clase de todos los discos elípticos , encontramos que aún podemos aislar todos los subconjuntos de arriba, así como los puntos que antes eran problemáticos. Por lo tanto, este conjunto específico de 4 puntos es destrozado por la clase de discos elípticos. Visualizado a continuación:
Los puntos opuestos de A ahora son separables por alguna elipse (mostrando uno de dos)
Cada subconjunto de tres puntos en A también es separable por alguna elipse (mostrando uno de cuatro)
Con un poco de pensamiento, podríamos generalizar que cualquier conjunto de puntos finitos en un círculo unitario podría ser destrozado por la clase de todos los conjuntos convexos (visualice conectando los puntos).
Coeficiente de rotura
Para cuantificar la riqueza de una colección C de conjuntos, utilizamos el concepto de coeficientes de ruptura (también conocido como función de crecimiento ). Para una colección C de juegos, siendo cualquier espacio, a menudo un espacio de muestra , definimos el n º rompiendo coeficiente de C como
dónde denota la cardinalidad del conjunto yes cualquier conjunto de n puntos.
es el mayor número de subconjuntos de cualquier conjunto A de n puntos que se puede formar por la intersección de A con los conjuntos de la colección C .
Aquí hay algunos datos sobre :
- para todos n porque para cualquier .
- Si , Que significa que hay un conjunto de cardinalidad n , que puede ser roto por C .
- Si para algunos luego para todos .
La tercera propiedad significa que si C no puede romper ningún conjunto de cardinalidades N, entonces no puede romper conjuntos de cardinalidades más grandes.
Clase Vapnik – Chervonenkis
La dimensión VC de una clase C se define como
o, alternativamente, como
Tenga en cuenta que
Si para cualquier n hay un conjunto de cardinalidad n que puede ser destruido por C , entoncespara todo n y la dimensión VC de esta clase C es infinita.
Una clase con dimensión VC finita se denomina clase Vapnik-Chervonenkis o clase VC . Una clase C es uniformemente Glivenko-Cantelli si y solo si es una clase VC.
Ver también
- Lema de Sauer-Shelah , que relaciona la cardinalidad de una familia de conjuntos con el tamaño de su conjunto destrozado más grande
Referencias
- Wencour, RS; Dudley, RM (1981), "Algunas clases especiales de Vapnik-Chervonenkis", Matemáticas discretas , 33 (3): 313–318, doi : 10.1016 / 0012-365X (81) 90274-0.
- Steele, JM (1975), Entropía combinatoria y leyes de límites uniformes , Ph.D. tesis, Universidad de Stanford, Departamento de Matemáticas
- Steele, JM (1978), "Discrepancias empíricas y procesos subaditivos", Annals of Probability , 6 (1): 118-227, doi : 10.1214 / aop / 1176995615 , JSTOR 2242865.
enlaces externos
- Origen de la terminología de "conjuntos destrozados" , por J. Steele