Conjuntos constructibles y Conjuntos cuestores : Teoría de la Intersección y primeras interacciones con la Teoría de Aprendizaje Computacional

Abstract

Esta tesis establece conexiones entre la Geometría Algebraica y la Teoría de Aprendizaje Computacional. En primer lugar, cerramos la Teoría de la Intersección para conjuntos constructibles, aportando dos nociones de grado que satisfacen la Desigualdad de Bézout. Estos resultados nos permiten refinar y extender las técnicas de J. Heintz y C. P. Schnorr para obtener cotas finas sobre la existencia y densidad de conjuntos cuestores. Posteriormente, exploramos las conexiones entre familias de conjuntos constructibles, conjuntos cuestores y la teoría de Vapnik– Chervonenkis. Para ello, generalizamos la noción de Erzeugungsgrad de J. Heintz al caso constructible. Empleando esta noción, demostramos que la dimensión de Vapnik–Chervonenkis de una familia de clasificadores constructibles está linealmente acotada, salvo por unas cantidades logarítmicas basadas en la Teoría de la Intersección, por la dimensión de Krull del espacio de parámetros. Usando la relación anterior, estudiamos la probabilidad de encontrar conjuntos cuestores de longitud apropiada en variedades evasivas de dimensión positiva. Aplicamos los resultados anteriores al análisis de redes neuronales con función de activación racional. Finalmente, abordamos el aprendizaje multiclase. En este contexto, introducimos una nueva noción, el grado de salida promedio, y demostramos que se trata de un invariante central. Además, llevamos a cabo un estudio detallado de la noción de pseudo-cubo y de la técnica del shifting.

This thesis establishes connections between Algebraic Geometry and Computational Learning Theory. First, we complete the Intersection Theory for constructible sets by introducing two notions of degree that satisfy Bézout’s Inequality. These results allow us to refine and extend the techniques of J. Heintz and C. P. Schnorr to obtain sharp bounds on the existence and density of correct test sequences. Next, we explore the connections between families of constructible sets, correct test sequences and the Vapnik–Chervonenkis theory. To this end, we generalize the notion of Erzeugungsgrad, introduced by J. Heintz, to the constructible case. Using this notion, we prove that the Vapnik–Chervonenkis dimension of a family of constructible classifiers is, up to logarithmic factors based on Intersection Theory, linearly bounded by the Krull dimension of the parameter space. Using the previous relation, we analyze the density of short correct test sequences in evasive varieties of positive dimension. We then apply our results to the study of neural networks with rational activation function. Finally, we address multiclass learning. In this context, we introduce a new notion, the expected outdegree, and prove that it is a central invariant. Additionally, we provide a detailed study of the notion of pseudo-cube and the shifting technique.