×

Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks. (English) Zbl 0869.68088

Summary: We introduce a new method for proving explicit upper bounds on the VC dimension of general functional basis networks and prove as an application, for the first time, that the VC dimension of analog networks with the sigmoidal activation function \(\sigma(y)= 1/1+ e^{-y}\) is bounded by a quadratic polynomial \(O((Im)^2)\) in both the number \(I\) of programmable parameters, and the number \(m\) of nodes. The proof method of this paper generalizes to much wider class of Pfaffian activation functions and formulas and gives also for the first time polynomial bounds on their VC dimension. We present also some other applications of our method.

MSC:

68T05 Learning and adaptive systems in artificial intelligence

Keywords:

VC dimension
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] M. Anthony, N. Biggs, 1992, Computational Learning Theory: An Introduction, Cambridge Univ. Press, Cambridge; M. Anthony, N. Biggs, 1992, Computational Learning Theory: An Introduction, Cambridge Univ. Press, Cambridge · Zbl 0755.68115
[2] Anthony, M.; Shawa-Taylor, J., A result of Vapnik with applications, Discrete Appl. Math., 47, 207-217 (1993) · Zbl 0801.68147
[3] A. Borodin, P. Tiwari, On the decidability of sparse univariate polynomial interpolation, Proceedings, 22nd ACM STOC, 1990; A. Borodin, P. Tiwari, On the decidability of sparse univariate polynomial interpolation, Proceedings, 22nd ACM STOC, 1990 · Zbl 0774.68067
[4] L. van den Dries, 1992, Tame topology and 0-minimal structures, preprint, University of Illinois, Urbana; L. van den Dries, 1992, Tame topology and 0-minimal structures, preprint, University of Illinois, Urbana
[5] van den Dries, L.; Macintyre, A.; Marker, D., The elementary theory of restricted analytic fields with exponentiation, Ann. of Math., 140, 183-205 (1994) · Zbl 0837.12006
[6] P. Goldberg, M. Jerrum, Bounding the Vapnik Chervonenkis dimension of concept classes parameterized by real, Mach. Learning numbers; P. Goldberg, M. Jerrum, Bounding the Vapnik Chervonenkis dimension of concept classes parameterized by real, Mach. Learning numbers · Zbl 0831.68087
[7] Proc. 6th ACM Workshop on Computational Learning Theory, 1993; Proc. 6th ACM Workshop on Computational Learning Theory, 1993
[8] Hardy, G. H., Properties of logarithmic-exponential functions, Proc. London Math. Soc., 10, 54-90 (1912) · JFM 42.0437.02
[9] Haussler, D., Decision theoretic generalizations of the PAC model for neural net and other learning applications, Inform. Comput., 100, 78-150 (1992) · Zbl 0762.68050
[10] Hertz, J.; Krogh, A.; Palmer, R. G., Introduction to the Theory of Neural Computation (1991), Addison-Wesley: Addison-Wesley Reading
[11] Hirsch, M. W., Differential Topology (1976), Springer-Verlag: Springer-Verlag New York/Berlin · Zbl 0121.18004
[12] M. Karpinski, A. Macintyre, Polynomial bounds for VC dimension of sigmoidal neural networks, Proc. 27th ACM STOC, 1995; M. Karpinski, A. Macintyre, Polynomial bounds for VC dimension of sigmoidal neural networks, Proc. 27th ACM STOC, 1995 · Zbl 0978.68562
[13] Karpinski, M.; Macintyre, A., Bounding VC dimension for neural networks: Progress and prospects (invited lecture), Lecture Notes in Artif. Intell., Vol. 904 (1995)
[14] Karpinski, M.; Werther, T., VC dimension and uniform learnability of sparse polynomials and rational functions, SIAM J. Comput., 22, 1276-1285 (1993) · Zbl 0799.68158
[15] Khovanski, A. G., Fewnomials (1991), Amer. Math. Soc: Amer. Math. Soc Providence
[16] Knight, J.; Pillay, A.; Steinhorn, C., Definable sets and ordered structures II, Trans. Amer. Math. Soc., 295, 593-605 (1986) · Zbl 0662.03024
[17] P. Koiran, E. D. Sontag, Neural networks with Quadratic VC dimension, Advances in Neural Information Processing Systems (NIPS ’95), 1995; P. Koiran, E. D. Sontag, Neural networks with Quadratic VC dimension, Advances in Neural Information Processing Systems (NIPS ’95), 1995
[18] Laskowski, M. C., Vapnik-Chervonenkis classes of definable sets, J. London Math. Soc., 45, 377-384 (1992) · Zbl 0766.60016
[19] Maass, W., Perspectives of current research about the complexity of learning on neural nets, Theoretical Advances in Neural Computation and Learning (1994), Kluwer Academic: Kluwer Academic Amsterdam · Zbl 0835.68097
[20] W. Maass, Bounds for the computational power and learning complexity of analog neural nets, Proc. 25th ACM STOC, 1993; W. Maass, Bounds for the computational power and learning complexity of analog neural nets, Proc. 25th ACM STOC, 1993 · Zbl 1310.68182
[21] W. Maass, Neural nets with superlinear VC-dimension, Proc. of the International Conference on Artificial Neural Networks 1994, ICANN ’94, Berlin, 1994; W. Maass, Neural nets with superlinear VC-dimension, Proc. of the International Conference on Artificial Neural Networks 1994, ICANN ’94, Berlin, 1994 · Zbl 0814.68111
[22] Neural Comput., 6, 875-882 (1994)
[23] W. Maass, G. Schnitger, E. D. Sontag, On the computational power of sigmoidal versus boolean threshold circuits, Proc. 32nd IEEE FOCS, 1991; W. Maass, G. Schnitger, E. D. Sontag, On the computational power of sigmoidal versus boolean threshold circuits, Proc. 32nd IEEE FOCS, 1991 · Zbl 0835.68042
[24] A. J. Macintyre, E. D. Sontag, Finiteness results for sigmoidal neural networks, Proc. 25th ACM STOC, 1993; A. J. Macintyre, E. D. Sontag, Finiteness results for sigmoidal neural networks, Proc. 25th ACM STOC, 1993 · Zbl 1310.68077
[25] Milnor, J., On the Betti numbers of real varieties, Proc. Amer. Math. Soc., 15, 275-280 (1964) · Zbl 0123.38302
[26] Milnor, J., Topology from the Differentiable Viewpoint (1965), Univ. Press of Virginia: Univ. Press of Virginia Charlottesville · Zbl 0136.20402
[27] Sard, A., The measure of the critical points of differentiable maps, Bull. Amer. Math. Soc., 48, 883-890 (1942) · Zbl 0063.06720
[28] J. Shawe-Taylor, 1994, Sample sizes for sigmoidal neural networks, Proc. ACM COLT, 1995, University of London; J. Shawe-Taylor, 1994, Sample sizes for sigmoidal neural networks, Proc. ACM COLT, 1995, University of London
[29] Sontag, E. D., Feedforward nets for interpolation and classification, J. Comput. System Sci., 45, 20-48 (1992) · Zbl 0791.68141
[30] G. Turan, F. Vatan, On the computation of boolean functions by analog circuits of bounded fan-in, Proc. 35th IEEE FOCS, 1994; G. Turan, F. Vatan, On the computation of boolean functions by analog circuits of bounded fan-in, Proc. 35th IEEE FOCS, 1994 · Zbl 0869.68050
[31] Warren, H. E., Lower bounds for approximation by non-linear manifolds, Trans. Amer. Math. Soc., 133, 167-178 (1968) · Zbl 0174.35403
[32] A. J. Wilkie, Model completeness results of restricted Pfaffian functions and the exponential function, J. Amer. Math. Soc.; A. J. Wilkie, Model completeness results of restricted Pfaffian functions and the exponential function, J. Amer. Math. Soc. · Zbl 0892.03013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.