Teorema de Cover

El teorema de Cover es un enunciado de la teoría del aprendizaje computacional y una de las principales motivaciones teóricas para el uso de métodos de núcleo no lineal en aplicaciones de aprendizaje automático . Recibe su nombre del teórico de la información Thomas M. Cover , quien lo enunció en 1965, refiriéndose a él como el teorema de la función de conteo .

Sea el número de conjuntos homogéneamente linealmente separables de${\displaystyle N}$puntos en${\displaystyle d}$Las dimensiones se definen como una función de conteo.${\displaystyle C(N,d)}$del número de puntos${\displaystyle N}$y la dimensionalidad${\displaystyle d}$El teorema establece que${\displaystyle C(N,d)=2\sum _{k=0}^{d-1}{\binom {N-1}{k}}}$.

Se requiere, como condición necesaria y suficiente, que los puntos estén en posición general . Dicho de otro modo, esto significa que los puntos deben ser lo más linealmente independientes (no alineados) posible. Esta condición se cumple con probabilidad 1 o casi con seguridad para conjuntos de puntos aleatorios, mientras que puede incumplirse fácilmente para datos reales, ya que estos suelen estar estructurados en variedades de menor dimensionalidad dentro del espacio de datos.

La función${\displaystyle C(N,d)}$sigue dos regímenes diferentes dependiendo de la relación entre${\displaystyle N}$y${\displaystyle d}$.

• Para${\displaystyle N\leq d+1}$, la función es exponencial en${\displaystyle N}$Esto significa esencialmente que cualquier conjunto de puntos etiquetados en posición general y en número no mayor que la dimensionalidad + 1 es linealmente separable; en jerga, se dice que un clasificador lineal rompe cualquier conjunto de puntos con${\displaystyle N\leq d+1}$Esta cantidad límite también se conoce como la dimensión de Vapnik-Chervonenkis del clasificador lineal.

• Para${\displaystyle N>d+1}$, la función de conteo comienza a crecer de forma menos que exponencial. Esto significa que, dada una muestra de tamaño fijo${\displaystyle N}$, para dimensionalidad mayor${\displaystyle d}$Es más probable que un conjunto aleatorio de puntos etiquetados sea linealmente separable. Por el contrario, con dimensionalidad fija, para tamaños de muestra mayores el número de conjuntos linealmente separables de puntos aleatorios será menor, o en otras palabras, la probabilidad de encontrar una muestra linealmente separable disminuirá con${\displaystyle N}$.

Una consecuencia del teorema es que, dado un conjunto de datos de entrenamiento que no es linealmente separable , se puede, con alta probabilidad, transformarlo en un conjunto de entrenamiento linealmente separable proyectándolo en un espacio de mayor dimensión mediante alguna transformación no lineal , o:

Es más probable que un problema complejo de clasificación de patrones, planteado de forma no lineal en un espacio de alta dimensión, sea linealmente separable que en un espacio de baja dimensión, siempre que dicho espacio no esté densamente poblado.

Por inducción con la relación recursiva$${\displaystyle C(N+1,d)=C(N,d)+C(N,d-1).}$$Para demostrar que, con fijo${\displaystyle N}$, aumentando${\displaystyle d}$puede convertir un conjunto de puntos de no separables a separables, se puede utilizar un mapeo determinista : supongamos que hay${\displaystyle N}$puntos. Elévelos sobre los vértices del simplex en el${\displaystyle N-1}$espacio real dimensional. Dado que cada partición de las muestras en dos conjuntos es separable por un separador lineal , se deduce la propiedad.

El artículo de 1965 contiene varios teoremas.

Teorema 6: Sea${\textstyle X\cup \{y\}=\left\{x_{1},x_{2},\cdots ,x_{N},y\right\}}$estar en${\textstyle \phi }$-posición general en${\textstyle d}$-espacio, donde${\textstyle \phi =\left(\phi _{1},\phi _{2},\cdots ,\phi _{d}\right)}$. Entonces${\textstyle y}$es ambiguo con respecto a${\textstyle C(N,d-1)}$dicotomías de${\textstyle X}$relativo a la clase de todos${\textstyle \phi }$-superficies.

Corolario: Si cada uno de los${\textstyle \phi }$-dicotomías separables de${\textstyle X}$tiene igual probabilidad, entonces la probabilidad${\textstyle A(N,d)}$eso${\textstyle y}$es ambiguo con respecto a un aleatorio${\textstyle \phi }$-dicotomía separable de${\textstyle X}$es${\displaystyle {\frac {C(N,d-1)}{C(N,d)}}}$.

Si${\displaystyle N/d\to \beta }$, entonces en el límite de${\displaystyle N\to \infty }$, esta probabilidad converge a${\displaystyle \lim _{N}A(N,d)={\begin{cases}1,&0\leq \beta \leq 2\\{\frac {1}{\beta -1}},&\beta \geq 2\end{cases}}}$.

Esto puede interpretarse como un límite en la capacidad de memoria de una sola unidad de perceptrón .${\displaystyle d}$es el número de pesos de entrada al perceptrón. La fórmula establece que en el límite de grande${\displaystyle d}$, el perceptrón casi con certeza sería capaz de memorizar hasta${\displaystyle 2d}$etiquetas binarias, pero casi con toda seguridad no logran memorizar nada más que eso. ( MacKay 2003 , p. 490) 

• Máquina de vectores de soporte
• Método del núcleo

• Haykin, Simon (2009). Redes neuronales y máquinas de aprendizaje (Tercera  ed.). Upper Saddle River, Nueva Jersey: Pearson Education Inc. pp. 232–236 . ISBN  978-0-13-147139-9.
• Cover, TM (1965). "Propiedades geométricas y estadísticas de sistemas de desigualdades lineales con aplicaciones en el reconocimiento de patrones" (PDF) . IEEE Transactions on Electronic Computers . EC-14 (3): 326–334 . doi : 10.1109/pgec.1965.264137 . S2CID 18251470. Archivado del original (PDF) el 20 de diciembre de 2019. 
• Mehrotra, K.; Mohan, CK; Ranka, S. (1997). Elementos de redes neuronales artificiales (2.ª  ed.). MIT Press. ISBN 0-262-13328-8.(Sección 3.5)
• MacKay, David JC (2003). "40. Capacidad de una sola neurona". Teoría de la información, inferencia y algoritmos de aprendizaje . Cambridge: Cambridge University Press. ISBN 978-0-521-64298-9.