View in EDS

Erzeugungsgrad, VC-dimension and neural networks with rational activation function.

Saved in:
Bibliographic Details
Title: Erzeugungsgrad, VC-dimension and neural networks with rational activation function.
Authors: Pardo, Luis Miguel1 (AUTHOR) luis.m.pardo@gmail.com, Sebastián, Daniel2 (AUTHOR) danielsesan@gmail.com
Source: Applicable Algebra in Engineering, Communication & Computing. Mar2026, Vol. 37 Issue 2, p389-471. 83p.
Subjects: Artificial neural networks, Intersection theory, Algebraic varieties, Computational learning theory
Abstract: The notion of Erzeugungsgrad was introduced by Joos Heintz in (Theoret Comput Sci 24:239–277, 1983) to bound the number of non-empty cells occurring after a process of quantifier elimination. We extend this notion and the combinatorial bounds of Theorem 2 in Heintz (1983) using the degree for constructible sets defined in Pardo and Sebastián (J Complex 68:101588, 2022). We show that the Erzeugungsgrad is the key ingredient to connect affine Intersection Theory over algebraically closed fields and the VC-Theory of Computational Learning Theory for families of classifiers given by parameterized families of constructible sets. In particular, we prove that the VC-dimension and the Krull dimension are linearly related up to logarithmic factors based on Intersection Theory. Using this relation, we study the density of correct test sequences in evasive varieties. We apply these ideas to analyze parameterized families of neural networks with rational activation function. [ABSTRACT FROM AUTHOR]
Copyright of Applicable Algebra in Engineering, Communication & Computing is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:The notion of Erzeugungsgrad was introduced by Joos Heintz in (Theoret Comput Sci 24:239–277, 1983) to bound the number of non-empty cells occurring after a process of quantifier elimination. We extend this notion and the combinatorial bounds of Theorem 2 in Heintz (1983) using the degree for constructible sets defined in Pardo and Sebastián (J Complex 68:101588, 2022). We show that the Erzeugungsgrad is the key ingredient to connect affine Intersection Theory over algebraically closed fields and the VC-Theory of Computational Learning Theory for families of classifiers given by parameterized families of constructible sets. In particular, we prove that the VC-dimension and the Krull dimension are linearly related up to logarithmic factors based on Intersection Theory. Using this relation, we study the density of correct test sequences in evasive varieties. We apply these ideas to analyze parameterized families of neural networks with rational activation function. [ABSTRACT FROM AUTHOR]
ISSN:09381279
DOI:10.1007/s00200-025-00723-4