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

Abstract

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.