Conjunto destrozado

Noción en el aprendizaje computacional

Se dice que una clase de conjuntos fragmenta otro conjunto si es posible "seleccionar" cualquier elemento de ese conjunto utilizando la intersección . El concepto de conjuntos fragmentados desempeña un papel importante en la teoría de Vapnik-Chervonenkis , también conocida como teoría VC. La fragmentación y la teoría VC se utilizan en el estudio de procesos empíricos , así como en la teoría del aprendizaje computacional estadístico .

Definición

Supongamos que A es un conjunto y C es una clase de conjuntos. La clase C desintegra el conjunto A si para cada subconjunto a de A hay algún elemento c de C tal que

${\displaystyle a=c\cap A.}$

De manera equivalente, C destruye a A cuando su intersección es igual al conjunto de potencias de A : P ( A ) = { c ∩ A | c ∈ C }.

Utilizamos la letra C para referirnos a una "clase" o "colección" de conjuntos, como en una clase de Vapnik-Chervonenkis (clase VC). A menudo se supone que el conjunto A es finito porque, en los procesos empíricos, nos interesa la fragmentación de conjuntos finitos de puntos de datos.

Ejemplo

Demostraremos que la clase de todos los discos en el plano (espacio bidimensional) no destruye cada conjunto de cuatro puntos en el círculo unitario , pero la clase de todos los conjuntos convexos en el plano sí destruye cada conjunto finito de puntos en el círculo unitario .

Sea A un conjunto de cuatro puntos en el círculo unitario y sea C la clase de todos los discos.

El conjunto A de cuatro puntos particulares del círculo unitario (el círculo unitario se muestra en violeta).

Para comprobar dónde C destroza a A , intentamos dibujar un disco alrededor de cada subconjunto de puntos de A. 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. Cualquier intento de incluir esos puntos en el lado opuesto incluirá necesariamente otros puntos que no estén en ese par. Por lo tanto, cualquier par de puntos opuestos no se puede aislar de A utilizando intersecciones con la clase C y, por lo tanto, C no destroza a A.

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.

Como hay algún subconjunto que no puede aislarse mediante ningún disco en C , concluimos entonces que A no se fragmenta con C . Y, con un poco de reflexión, podemos demostrar que ningún conjunto de cuatro puntos se fragmenta con este C .

Sin embargo, si redefinimos C como la clase de todos los discos elípticos , descubrimos que todavía podemos aislar todos los subconjuntos anteriores, así como los puntos que antes eran problemáticos. Por lo tanto, este conjunto específico de 4 puntos se ve 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 reflexión, podríamos generalizar que cualquier conjunto de puntos finitos en un círculo unitario podría ser fragmentado por la clase de todos los conjuntos convexos (visualicemos la conexión de los puntos).

Coeficiente de fragmentación

Para cuantificar la riqueza de una colección C de conjuntos, utilizamos el concepto de coeficientes de fragmentación (también conocido como función de crecimiento ). Para una colección C de conjuntos , que es cualquier espacio, a menudo un espacio muestral , definimos el n- ^ésimo coeficiente de fragmentación de C como ${\displaystyle s\subset \Omega }$ ${\displaystyle \Omega }$

${\displaystyle S_{C}(n)=\max _{\forall x_{1},x_{2},\dots ,x_{n}\in \Omega }\operatorname {card} \{\,\{\,x_{1},x_{2},\dots ,x_{n}\}\cap s,s\in C\}}$

donde denota la cardinalidad del conjunto y es cualquier conjunto de n puntos. ${\displaystyle \operatorname {card} }$ ${\displaystyle x_{1},x_{2},\dots ,x_{n}\in \Omega }$

${\displaystyle S_{C}(n)}$es el mayor número de subconjuntos de cualquier conjunto A de n puntos que se puede formar al intersecar A con los conjuntos de la colección C.

Por ejemplo, si el conjunto A contiene 3 puntos, su conjunto potencia, , contiene elementos. Si C destroza A , su coeficiente de destrozo (3) sería 8 y S_C(2) sería . Sin embargo, si uno de esos conjuntos en no se puede obtener a través de intersecciones en c , entonces S_C(3) solo sería 7. Si no se puede obtener ninguno de esos conjuntos, S_C(3) sería 0. Además, si S_C(2)=3, por ejemplo, entonces hay un elemento en el conjunto de todos los conjuntos de 2 puntos de A que no se puede obtener a partir de intersecciones con C . De esto se deduce que S_C(3) también sería menor que 8 (es decir, C no destrozaría A ) porque ya hemos localizado un conjunto "faltante" en el conjunto potencia más pequeño de conjuntos de 2 puntos. ${\displaystyle P(A)}$ ${\displaystyle 2^{3}=8}$ ${\displaystyle 2^{2}=4}$ ${\displaystyle P(A)}$

Este ejemplo ilustra algunas propiedades de : ${\displaystyle S_{C}(n)}$

1. ${\displaystyle S_{C}(n)\leq 2^{n}}$para todo n porque para cualquier . ${\displaystyle \{s\cap A|s\in C\}\subseteq P(A)}$ ${\displaystyle A\subseteq \Omega }$
2. Si , eso significa que hay un conjunto de cardinalidad n , que puede ser destrozado por C . ${\displaystyle S_{C}(n)=2^{n}}$
3. Si es para algunos entonces es para todos . ${\displaystyle S_{C}(N)<2^{N}}$ ${\displaystyle N>1}$ ${\displaystyle S_{C}(n)<2^{n}}$ ${\displaystyle n\geq N}$

La tercera propiedad significa que si C no puede romper ningún conjunto de cardinalidad N , entonces no puede romper conjuntos de cardinalidades mayores.

Clase Vapnik-Chervonenkis

Si A no puede ser fragmentado por C , habrá un valor mínimo de n que hace que el coeficiente de fragmentación(n) sea menor que porque a medida que n se hace más grande, hay más conjuntos que podrían omitirse. Alternativamente, también hay un valor máximo de n para el cual S_C(n) sigue siendo , porque a medida que n se hace más pequeño, hay menos conjuntos que podrían omitirse. El extremo de esto es S_C(0) (el coeficiente de fragmentación del conjunto vacío), que siempre debe ser . Estas afirmaciones se prestan a definir la dimensión VC de una clase C como: ${\displaystyle 2^{n}}$ ${\displaystyle 2^{n}}$ ${\displaystyle 2^{0}=1}$

${\displaystyle VC(C)={\underset {n}{\min }}\{n:S_{C}(n)<2^{n}\}\,}$

o, alternativamente, como

${\displaystyle VC_{0}(C)={\underset {n}{\max }}\{n:S_{C}(n)=2^{n}\}.\,}$

Tenga en cuenta que . La dimensión VC generalmente se define como VC_0, la cardinalidad más grande de puntos elegidos que aún fragmentarán A (es decir, n tal que ). ${\displaystyle VC(C)=VC_{0}(C)+1.}$ ${\displaystyle S_{C}(n)=2^{n}}$

Alternativamente, si para cualquier n existe un conjunto de cardinalidad n que puede ser fragmentado por C , entonces para todo n y la dimensión VC de esta clase C es infinita. ${\displaystyle S_{C}(n)=2^{n}}$

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.

Véase también

• Lema de Sauer-Shelah , que relaciona la cardinalidad de una familia de conjuntos con el tamaño de su conjunto fragmentado más grande

Referencias

• Wencour, RS; Dudley, RM (1981), "Algunas clases especiales de Vapnik-Chervonenkis", Discrete Mathematics , 33 (3): 313–318, doi : 10.1016/0012-365X(81)90274-0.
• Steele, JM (1975), Entropía combinatoria y leyes límite uniformes , tesis doctoral, 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 fragmentados", por J. Steele