Probabilistic lower bounds for approximation by shallow perceptron networks

被引:23
作者
Kurkova, Vera [1 ]
Sanguineti, Marcello [2 ]
机构
[1] Czech Acad Sci, Inst Comp Sci, Vodarenskou Vezi 2, Prague 18207, Czech Republic
[2] Univ Genoa, DIBRIS, Via Opera Pia 13, I-16145 Genoa, Italy
关键词
Shallow networks; Perceptrons; Model complexity; Lower bounds on approximation rates; Chernoff-Hoeffding bounds; NEURAL-NETWORKS; COMPUTATIONAL MODELS; INEQUALITIES; COMPLEXITY; OPERATORS;
D O I
10.1016/j.neunet.2017.04.003
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Limitations of approximation capabilities of shallow perceptron networks are investigated. Lower bounds on approximation errors are derived for binary-valued functions on finite domains. It is proven that unless the number of network units is sufficiently large (larger than any polynomial of the logarithm of the size of the domain) a good approximation cannot be achieved for almost any uniformly randomly chosen function on a given domain. The results are obtained by combining probabilistic Chernoff-Hoeffding bounds with estimates of the sizes of sets of functions exactly computable by shallow networks with increasing numbers of units. (C) 2017 Elsevier Ltd. All rights reserved.
引用
收藏
页码:34 / 41
页数:8
相关论文
共 47 条
[11]  
Bengio Y., 2007, LARGE SCALE KERNEL M, V34, P1, DOI DOI 10.7551/MITPRESS/7496.003.0016
[12]   Learning Deep Architectures for AI [J].
Bengio, Yoshua .
FOUNDATIONS AND TRENDS IN MACHINE LEARNING, 2009, 2 (01) :1-127
[13]   On the Complexity of Neural Network Classifiers: A Comparison Between Shallow and Deep Architectures [J].
Bianchini, Monica ;
Scarselli, Franco .
IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS, 2014, 25 (08) :1553-1565
[14]   Max-product neural network and quasi-interpolation operators activated by sigmoidal functions [J].
Costarelli, Danilo ;
Vinti, Gianluca .
JOURNAL OF APPROXIMATION THEORY, 2016, 209 :1-22
[15]   Pointwise and uniform approximation by multivariate neural network operators of the max-product type [J].
Costarelli, Danilo ;
Vinti, Gianluca .
NEURAL NETWORKS, 2016, 81 :81-90
[16]   Approximation by Max-Product Neural Network Operators of Kantorovich Type [J].
Costarelli, Danilo ;
Vinti, Gianluca .
RESULTS IN MATHEMATICS, 2016, 69 (3-4) :505-519
[17]   Neural network operators: Constructive interpolation of multivariate functions [J].
Costarelli, Danilo .
NEURAL NETWORKS, 2015, 67 :28-36
[18]   GEOMETRICAL AND STATISTICAL PROPERTIES OF SYSTEMS OF LINEAR INEQUALITIES WITH APPLICATIONS IN PATTERN RECOGNITION [J].
COVER, TM .
IEEE TRANSACTIONS ON ELECTRONIC COMPUTERS, 1965, EC14 (03) :326-&
[19]   OPTIMAL NONLINEAR APPROXIMATION [J].
DEVORE, RA ;
HOWARD, R ;
MICCHELLI, C .
MANUSCRIPTA MATHEMATICA, 1989, 63 (04) :469-478
[20]   On the Curse of Dimensionality in the Ritz Method [J].
Gnecco, Giorgio .
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 2016, 168 (02) :488-509