función de crecimiento

La función de crecimiento , también llamada coeficiente de fragmentación o número de fragmentación , mide la riqueza de una familia o clase de funciones. Se utiliza especialmente en el contexto de la teoría del aprendizaje estadístico , donde se emplea para estudiar las propiedades de los métodos de aprendizaje estadístico. El término «función de crecimiento» fue acuñado por Vapnik y Chervonenkis en su artículo de 1968, donde también demostraron muchas de sus propiedades. ^{[ 1 ]} Es un concepto fundamental en el aprendizaje automático . ^{[ 2 ] [ 3 ]}

1. El dominio es la recta real.${\displaystyle \mathbb {R} }$. La familia de conjuntos${\displaystyle H}$contiene todas las semirrectas (rayos) desde un número dado hasta el infinito positivo, es decir, todos los conjuntos de la forma${\displaystyle \{x>x_{0}\mid x\in \mathbb {R} \}}$para algunos${\displaystyle x_{0}\in \mathbb {R} }$. Para cualquier conjunto${\displaystyle C}$de${\displaystyle m}$números reales, la intersección${\displaystyle H\cap C}$contiene${\displaystyle m+1}$conjuntos: el conjunto vacío , el conjunto que contiene el elemento más grande de${\displaystyle C}$, el conjunto que contiene los dos elementos más grandes de${\displaystyle C}$y así sucesivamente. Por lo tanto:${\displaystyle \operatorname {Crecimiento} (H,m)=m+1}$. ^{[ 1 ] : Ej.1} Lo mismo es cierto si${\displaystyle H}$Contiene semirrectas abiertas, semirrectas cerradas o ambas.

2. El dominio es el segmento${\displaystyle [0,1]}$. La familia de conjuntos${\displaystyle H}$contiene todos los conjuntos abiertos. Para cualquier conjunto finito${\displaystyle C}$de${\displaystyle m}$números reales, la intersección${\displaystyle H\cap C}$contiene todos los subconjuntos posibles de${\displaystyle C}$. Hay${\displaystyle 2^{m}}$tales subconjuntos, por lo tanto${\displaystyle \operatorname {Crecimiento} (H,m)=2^{m}}$. ^{[ 1 ] : Ej.2}

3. El dominio es el espacio euclidiano.${\displaystyle \mathbb {R} ^{n}}$. La familia de conjuntos${\displaystyle H}$contiene todos los semiespacios de la forma:${\displaystyle x\cdot \phi \geq 1}$, dónde${\displaystyle \phi }$es un vector fijo. Entonces${\displaystyle \operatorname {Crecimiento} (H,m)=\operatorname {Comp} (n,m)}$donde Comp es el número de componentes en una partición de un espacio n-dimensional mediante m hiperplanos . ^{[ 1 ] : Ejemplo 3}

4. El dominio es la recta real.${\displaystyle \mathbb {R} }$. La familia de conjuntos${\displaystyle H}$contiene todos los intervalos reales, es decir, todos los conjuntos de la forma${\displaystyle \{x\in [x_{0},x_{1}]|x\in \mathbb {R} \}}$para algunos${\displaystyle x_{0},x_{1}\in \mathbb {R} }$. Para cualquier conjunto${\displaystyle C}$de${\displaystyle m}$números reales, la intersección${\displaystyle H\cap C}$contiene todas las secuencias de entre 0 y${\displaystyle m}$elementos consecutivos de${\displaystyle C}$. El número de tales carreras es${\displaystyle {m+1 \choose 2}+1}$, entonces${\displaystyle \operatorname {Crecimiento} (H,m)={m+1 \choose 2}+1}$.

La principal propiedad que hace interesante la función de crecimiento es que puede ser polinómica o exponencial; no hay término medio.

La siguiente es una propiedad del tamaño de la intersección: ^{[ 1 ] : Lem.1}

• Si, para algún conjunto${\displaystyle C_{m}}$de tamaño${\displaystyle m}$y para algún número${\displaystyle n\leq m}$,${\displaystyle |H\cap C_{m}|\geq \operatorname {Comp} (n,m)}$-
• entonces, existe un subconjunto${\displaystyle C_{n}\subsetequ C_{m}}$de tamaño${\displaystyle n}$de tal manera que${\displaystyle |H\cap C_{n}|=2^{n}}$.

Esto implica la siguiente propiedad de la función de crecimiento. ^{[ 1 ] : Teorema 1} Para cada familia${\displaystyle H}$Hay dos casos:

• El caso exponencial :${\displaystyle \operatorname {Crecimiento} (H,m)=2^{m}}$idénticamente.
• El caso polinómico :${\displaystyle \operatorname {Crecimiento} (H,m)}$está mayoritariamente por${\displaystyle \operatorname {Comp} (n,m)\leq m^{n}+1}$, dónde${\displaystyle n}$es el entero más pequeño para el cual${\displaystyle \operatorname {Crecimiento} (H,n)<2^{n}}$.

Dejar${\displaystyle \Omega }$ser un conjunto sobre el cual una medida de probabilidad${\displaystyle \Pr }$está definido. Sea${\displaystyle H}$ser familia de subconjuntos de${\displaystyle \Omega }$(= una serie de eventos).

Supongamos que elegimos un conjunto${\displaystyle C_{m}}$que contiene${\displaystyle m}$elementos de${\displaystyle \Omega }$donde cada elemento se elige al azar según la medida de probabilidad.${\displaystyle P}$, independientemente de los demás (es decir, con reemplazos). Para cada evento${\displaystyle h\in H}$, comparamos las dos cantidades siguientes:

• Su frecuencia relativa en${\displaystyle C_{m}}$, es decir,${\displaystyle |h\cap C_{m}|/m}$;
• Su probabilidad${\displaystyle \Pr[h]}$.

Estamos interesados ​​en la diferencia,${\displaystyle D(h,C_{m}):={\big |}|h\cap C_{m}|/m-\Pr[h]{\big |}}$Esta diferencia satisface el siguiente límite superior:

${\displaystyle \Pr \left[\forall h\in H:D(h,C_{m})\leq {\sqrt {8(\ln \operatorname {Growth} (H,2m)+\ln(4/\delta )) \over m}}\right]~~~~>~~~~1-\delta }$

lo cual es equivalente a: ^{[ 1 ] : Th.2}

${\displaystyle \Pr {\big [}\forall h\in H:D(h,C_{m})\leq \varepsilon {\big ]}~~~~>~~~~1-4\cdot \operatorname {Growth} (H,2m)\cdot \exp(-\varepsilon ^{2}\cdot m/8)}$

En palabras: la probabilidad de que para todos los eventos en${\displaystyle H}$, la frecuencia relativa está cerca de la probabilidad, está limitada inferiormente por una expresión que depende de la función de crecimiento de${\displaystyle H}$.

Una consecuencia de esto es que, si la función de crecimiento es polinómica en${\displaystyle m}$(es decir, existe algún${\displaystyle n}$de tal manera que${\displaystyle \operatorname {Growth} (H,m)\leq m^{n}+1}$), entonces la probabilidad anterior se aproxima a 1 como${\displaystyle m\to \infty }$. Es decir, la familia${\displaystyle H}$goza de convergencia uniforme en probabilidad .