La función de crecimiento , también llamada coeficiente de ruptura o número de ruptura , mide la riqueza de una familia determinada . Se utiliza especialmente en el contexto de la teoría del aprendizaje estadístico , donde mide la complejidad de una clase de hipótesis. 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
Dejar ser una familia de conjuntos (un conjunto de conjuntos) yun conjunto. Su intersección se define como la siguiente familia de conjuntos:
El tamaño de la intersección (también llamado índice ) de con respecto a es . Si un conjunto posee elementos, entonces el índice es como máximo . Si el índice es exactamente 2 m, entonces el conjunto se dice que está destrozado por , porque contiene todos los subconjuntos de , es decir:
La función de crecimiento mide el tamaño de como una función de . Formalmente:
Definición de clase de hipótesis
Equivalentemente, dejemos ser una clase de hipótesis (un conjunto de funciones binarias) y un juego con elementos. La restricción de a es el conjunto de funciones binarias en que se puede derivar de : [3] : 45
La función de crecimiento mide el tamaño de como una función de : [3] : 49
Ejemplos de
1. El dominio es la línea real. El set-familiacontiene todas las medias líneas (rayos) desde un número dado hasta el infinito positivo, es decir, todos los conjuntos de la forma para algunos . 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í. Por lo tanto:. [1] : Ej.1 Lo mismo es cierto si contiene medias líneas abiertas, medias líneas cerradas o ambas.
2. El dominio es el segmento. El set-familiacontiene todos los conjuntos abiertos. Para cualquier conjunto finito de números reales, la intersección contiene todos los subconjuntos posibles de . Existen tales subconjuntos, entonces . [1] : Ej. 2
4. El dominio es la línea real. El set-familia contiene todos los intervalos reales, es decir, todos los conjuntos de la forma para algunos . Para cualquier conjunto de números reales, la intersección contiene todas las ejecuciones de entre 0 y elementos consecutivos de . El número de carreras de este tipo es, entonces .
Polinomio o exponencial
La propiedad principal que hace que la función de crecimiento sea interesante es que puede ser polinomial o exponencial, nada intermedio.
La siguiente es una propiedad del tamaño de la intersección: [1] : Lem.1
Si, por algún conjunto de tamaño , y para algunos , -
entonces, existe un subconjunto de tamaño tal que .
Esto implica la siguiente propiedad de la función de crecimiento. [1] : Th.1 Para cada familia hay dos casos:
El caso exponencial : idénticamente.
El caso del polinomio : está mayorizado por , dónde es el número entero más pequeño para el que .
Otras propiedades
Límite superior trivial
Para cualquier finito :
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.
Límite superior exponencial
Para cualquier no vacío :
Es decir, la función de crecimiento tiene un límite superior exponencial.
Decimos que un conjunto-familia rompe un conjunto si su intersección contiene todos los posibles subconjuntos de , es decir . Si destroza de tamaño , luego , que es el límite superior.
Intersección cartesiana
Defina la intersección cartesiana de dos familias de conjuntos como:
La dimensión VC de se define según estos dos casos:
En el caso del polinomio , = el entero más grande para cual .
En el caso exponencial.
Entonces si y solo si .
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 .
Otra conexión entre la función de crecimiento y la dimensión VC viene dada por el lema de Sauer-Shelah : [3] : 49
Si , luego:
para todos :
En particular,
para todos :
así que cuando la dimensión VC es finita, la función de crecimiento crece polinomialmente con .
Este límite superior es estrecho, es decir, para todos existe con dimensión VC tal que: [2] : 56
Entropía
Mientras que la función de crecimiento está relacionada con el tamaño máximo de la intersección, la entropía está relacionada con el tamaño medio de la intersección: [1] : 272-273
El tamaño de la intersección tiene la siguiente propiedad. Para cada set-family:
Por eso:
Además, la secuencia converge a una constante Cuándo .
Además, la variable aleatoria se concentra cerca .
Aplicaciones en teoría de probabilidades
Dejar ser un conjunto en el que una medida de probabilidadse define. Dejar ser familia de subconjuntos de (= una familia de eventos).
Supongamos que elegimos un conjunto eso contiene elementos de , donde cada elemento se elige al azar de acuerdo con la medida de probabilidad , independientemente de los demás (es decir, con reemplazos). Para cada evento, comparamos las siguientes dos cantidades:
Su frecuencia relativa en , es decir, ;
Su probabilidad .
Nos interesa la diferencia, . Esta diferencia satisface el siguiente límite superior:
En palabras: la probabilidad de que para todos los eventos en, la frecuencia relativa está cerca de la probabilidad, está delimitada por una expresión que depende de la función de crecimiento de .
Un corolario de esto es que, si la función de crecimiento es polinomial en (es decir, existen algunos tal que ), entonces la probabilidad anterior se aproxima a 1 cuando . Es decir, la familiadisfruta de una convergencia uniforme en probabilidad .
Referencias
^ a b c d e f g h Vapnik, VN; Chervonenkis, A. Ya. (1971). "Sobre la convergencia uniforme de frecuencias relativas de eventos a sus probabilidades". Teoría de la probabilidad y sus aplicaciones . 16 (2): 264. doi : 10.1137 / 1116025 . Esta es una traducción al inglés, por B. Seckler, del periódico ruso: "Sobre la convergencia uniforme de frecuencias relativas de eventos a sus probabilidades". Dokl. Akad. Nauk . 181 (4): 781. 1968. La traducción se reprodujo como: Vapnik, VN; Chervonenkis, A. Ya. (2015). "Sobre la convergencia uniforme de frecuencias relativas de eventos a sus probabilidades". Medidas de complejidad . pag. 11. doi : 10.1007 / 978-3-319-21852-6_3 . ISBN 978-3-319-21851-9.
^ a b c dMohri, Mehryar ; Rostamizadeh, Afshin; Talwalkar, Ameet (2012). Fundamentos del aprendizaje automático . Estados Unidos, Massachusetts: MIT Press. ISBN 9780262018258., especialmente la Sección 3.2
^ a b c dShalev-Shwartz, Shai; Ben-David, Shai (2014). Comprensión del aprendizaje automático: de la teoría a los algoritmos . Prensa de la Universidad de Cambridge. ISBN 9781107057135.