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 de conjuntos o clase de funciones. Se utiliza especialmente en el contexto de la teoría del aprendizaje estadístico , donde se utiliza 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 básico en el aprendizaje automático . ^{[2] [3]}

Definiciones

Definición de familia de conjuntos

Sean una familia de conjuntos (un conjunto de conjuntos) y un conjunto. Su intersección se define como la siguiente familia de conjuntos: ${\displaystyle H}$ ${\displaystyle C}$

${\displaystyle H\cap C:=\{h\cap C\mid h\in H\}}$

El tamaño de la intersección (también llamado índice ) de con respecto a es . Si un conjunto tiene elementos, entonces el índice es como máximo . Si el índice es exactamente 2 ^m, entonces se dice que el conjunto está fragmentado por , porque contiene todos los subconjuntos de , es decir: ${\displaystyle H}$ ${\displaystyle C}$ ${\displaystyle |H\cap C|}$ ${\displaystyle C_{m}}$ ${\displaystyle m}$ ${\displaystyle 2^{m}}$ ${\displaystyle C}$ ${\displaystyle H}$ ${\displaystyle H\cap C}$ ${\displaystyle C}$

${\displaystyle |H\cap C|=2^{|C|},}$

La función de crecimiento mide el tamaño de como función de . Formalmente: ${\displaystyle H\cap C}$ ${\displaystyle |C|}$

${\displaystyle \operatorname {Growth} (H,m):=\max _{C:|C|=m}|H\cap C|}$

Definición de clase de hipótesis

De manera equivalente, sea una clase de hipótesis (un conjunto de funciones binarias) y un conjunto con elementos. La restricción de to es el conjunto de funciones binarias en que se puede derivar de : ^{[3] : 45} ${\displaystyle H}$ ${\displaystyle C}$ ${\displaystyle m}$ ${\displaystyle H}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle H}$

${\displaystyle H_{C}:=\{(h(x_{1}),\ldots ,h(x_{m}))\mid h\in H,x_{i}\in C\}}$

La función de crecimiento mide el tamaño de en función de : ^{[3] : 49} ${\displaystyle H_{C}}$ ${\displaystyle |C|}$

${\displaystyle \operatorname {Growth} (H,m):=\max _{C:|C|=m}|H_{C}|}$

Ejemplos

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

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

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

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

Polinomio o exponencial

La propiedad principal que hace que la función de crecimiento sea interesante es que puede ser polinómica o exponencial (nada intermedio).

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

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

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

• El caso exponencial : idénticamente. ${\displaystyle \operatorname {Growth} (H,m)=2^{m}}$
• El caso del polinomio : está mayorizado por , donde es el entero más pequeño para el cual . ${\displaystyle \operatorname {Growth} (H,m)}$ ${\displaystyle \operatorname {Comp} (n,m)\leq m^{n}+1}$ ${\displaystyle n}$ ${\displaystyle \operatorname {Growth} (H,n)<2^{n}}$

Otras propiedades

Límite superior trivial

Para cualquier finito : ${\displaystyle H}$

${\displaystyle \operatorname {Growth} (H,m)\leq |H|}$

ya que para cada , el número de elementos en es como máximo . Por lo tanto, la función de crecimiento es principalmente interesante cuando es infinito. ${\displaystyle C}$ ${\displaystyle H\cap C}$ ${\displaystyle |H|}$ ${\displaystyle H}$

Límite superior exponencial

Para cualquier valor no vacío : ${\displaystyle H}$

${\displaystyle \operatorname {Growth} (H,m)\leq 2^{m}}$

Es decir, la función de crecimiento tiene un límite superior exponencial.

Decimos que una familia de conjuntos fragmenta un conjunto si su intersección contiene todos los subconjuntos posibles de , es decir . Si fragmenta de tamaño , entonces , que es el límite superior. ${\displaystyle H}$ ${\displaystyle C}$ ${\displaystyle C}$ ${\displaystyle H\cap C=2^{C}}$ ${\displaystyle H}$ ${\displaystyle C}$ ${\displaystyle m}$ ${\displaystyle \operatorname {Growth} (H,C)=2^{m}}$

intersección cartesiana

Defina la intersección cartesiana de dos familias de conjuntos como:

${\displaystyle H_{1}\bigotimes H_{2}:=\{h_{1}\cap h_{2}\mid h_{1}\in H_{1},h_{2}\in H_{2}\}}$.

Entonces: ^{[2] : 57}

${\displaystyle \operatorname {Growth} (H_{1}\bigotimes H_{2},m)\leq \operatorname {Growth} (H_{1},m)\cdot \operatorname {Growth} (H_{2},m)}$

Unión

Por cada dos familias de conjuntos: ^{[2] : 58}

${\displaystyle \operatorname {Growth} (H_{1}\cup H_{2},m)\leq \operatorname {Growth} (H_{1},m)+\operatorname {Growth} (H_{2},m)}$

Dimensión VC

La dimensión VC de se define según estos dos casos: ${\displaystyle H}$

• En el caso del polinomio , = el entero más grande para el cual . ${\displaystyle \operatorname {VCDim} (H)=n-1}$ ${\displaystyle d}$ ${\displaystyle \operatorname {Growth} (H,d)=2^{d}}$
• En el caso exponencial . ${\displaystyle \operatorname {VCDim} (H)=\infty }$

Así que si y sólo si . ${\displaystyle \operatorname {VCDim} (H)\geq d}$ ${\displaystyle \operatorname {Growth} (H,d)=2^{d}}$

La función de crecimiento puede considerarse como un refinamiento del concepto de dimensión VC. La dimensión VC solo nos dice si es igual o menor que , mientras que la función de crecimiento nos dice exactamente cómo cambia en función de . ${\displaystyle \operatorname {Growth} (H,d)}$ ${\displaystyle 2^{d}}$ ${\displaystyle \operatorname {Growth} (H,m)}$ ${\displaystyle m}$

Otra conexión entre la función de crecimiento y la dimensión VC está dada por el lema de Sauer-Shelah : ^{[3] : 49}

Si , entonces: ${\displaystyle \operatorname {VCDim} (H)=d}$

Para todos : ${\displaystyle m}$ ${\displaystyle \operatorname {Growth} (H,m)\leq \sum _{i=0}^{d}{m \choose i}}$

En particular,

Para todos : ${\displaystyle m>d+1}$ ${\displaystyle \operatorname {Growth} (H,m)\leq (em/d)^{d}=O(m^{d})}$

Entonces, cuando la dimensión VC es finita, la función de crecimiento crece polinomialmente con . ${\displaystyle m}$

Este límite superior es estricto, es decir, para todo lo que existe con dimensión VC tal que: ^{[2] : 56} ${\displaystyle m>d}$ ${\displaystyle H}$ ${\displaystyle d}$

${\displaystyle \operatorname {Growth} (H,m)=\sum _{i=0}^{d}{m \choose i}}$

Entropía

Mientras que la función de crecimiento está relacionada con el tamaño máximo de intersección, la entropía está relacionada con el tamaño promedio de intersección: ^{[1] : 272–273}

${\displaystyle \operatorname {Entropy} (H,m)=E_{|C_{m}|=m}{\big [}\log _{2}(|H\cap C_{m}|){\big ]}}$

El tamaño de la intersección tiene la siguiente propiedad. Para cada familia de conjuntos : ${\displaystyle H}$

${\displaystyle |H\cap (C_{1}\cup C_{2})|\leq |H\cap C_{1}|\cdot |H\cap C_{2}|}$

Por eso:

${\displaystyle \operatorname {Entropy} (H,m_{1}+m_{2})\leq \operatorname {Entropy} (H,m_{1})+\operatorname {Entropy} (H,m_{2})}$

Además, la secuencia converge a una constante cuando . ${\displaystyle \operatorname {Entropy} (H,m)/m}$ ${\displaystyle c\in [0,1]}$ ${\displaystyle m\to \infty }$

Además, la variable aleatoria se concentra cerca de . ${\displaystyle \log _{2}{|H\cap C_{m}|/m}}$ ${\displaystyle c}$

Aplicaciones en la teoría de la probabilidad

Sea un conjunto en el que se define una medida de probabilidad . Sea una familia de subconjuntos de (= una familia de eventos). ${\displaystyle \Omega }$ ${\displaystyle \Pr }$ ${\displaystyle H}$ ${\displaystyle \Omega }$

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

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

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

${\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 }$

que 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 , 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}$ ${\displaystyle H}$

Un corolario de esto es que, si la función de crecimiento es polinómica en (es decir, existe alguna tal que ), entonces la probabilidad anterior se acerca a 1 cuando . Es decir, la familia disfruta de convergencia uniforme en probabilidad . ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle \operatorname {Growth} (H,m)\leq m^{n}+1}$ ${\displaystyle m\to \infty }$ ${\displaystyle H}$

Referencias

1. Vapnik, VN; Chervonenkis, A. Ya. (1971). "Sobre la convergencia uniforme de frecuencias relativas de eventos con sus probabilidades". Teoría de la probabilidad y sus aplicaciones . 16 (2): 264. doi :10.1137/1116025.Se trata de una traducción al inglés, realizada por B. Seckler, del artículo ruso: "Sobre la convergencia uniforme de las frecuencias relativas de los acontecimientos con sus probabilidades". Dokl. Akad. Nauk . 181 (4): 781. 1968.La traducción fue reproducida como: Vapnik, VN; Chervonenkis, A. Ya. (2015). "Sobre la convergencia uniforme de frecuencias relativas de eventos con sus probabilidades". Medidas de complejidad . p. 11. doi :10.1007/978-3-319-21852-6_3. ISBN 978-3-319-21851-9.
2. Mohri, Mehryar ; Rostamizadeh, Afshin; Talwalkar, Ameet (2012). Fundamentos del aprendizaje automático . EE. UU., Massachusetts: MIT Press. ISBN 9780262018258., especialmente la Sección 3.2
3. Shalev-Shwartz, Shai; Ben-David, Shai (2014). Comprender el aprendizaje automático: de la teoría a los algoritmos . Cambridge University Press. ISBN 9781107057135.