Sparsity and Complexity of Networks Computing Highly-Varying Functions

Authors: Věra Kůrková
Publication year: 2018
Publication type: Konferenční příspěvek (mezinárodní konf.)
Periodical: Artificial Neural Networks and Machine Learning – ICANN 2018. Proceedings, Part III
Projects: Capabilities and limitations of shallow and deep networks
Bibliographic citation: KŮRKOVÁ, Věra. Sparsity and Complexity of Networks Computing Highly-Varying Functions. In: KŮRKOVÁ, V., MANOLOPOULOS, Y., HAMMER, B., ILIADIS, L., MAGLOGIANNIS, I., eds. Artificial Neural Networks and Machine Learning – ICANN 2018. Proceedings, Part III. Cham: Springer, 2018, S. 534-543. Lecture Notes in Computer Science, 11141. ISBN 978-3-030-01423-0. ISSN 0302-9743
Dostupné z: doi:10.1007/978-3-030-01424-7_52.
DOI: 10.1007/978-3-030-01424-7_52
ID: 493825

Abstract

Approximative measures of network sparsity in terms of norms tailored to dictionaries of computational units are investigated. Lower bounds on these norms of real-valued functions on finite domains are derived. The bounds are proven by combining the concentration of measure property of high-dimensional spaces with characterization of dictionaries of computational units in terms of their capacities and coherence measured by their covering numbers. The results are applied to dictionaries used in neurocomputing which have power-type covering numbers. Probabilistic results are illustrated by a concrete construction of a class of functions, computation of which by perceptron networks requires large number of units or it is unstable due to large output weights.