Lower Bounds on Complexity of Shallow Perceptron Networks

Autoři: RNDr. Věra Kůrková, DSc.
Rok vydání: 2016
Typ publikace: Konferenční příspěvek (mezinárodní konf.)
Periodikum: Engineering Applications of Neural Networks
Projekty: Modelová složitost neuronových, radiálních a jádrových sítí
Bibliografická citace: KŮRKOVÁ, Věra. Lower Bounds on Complexity of Shallow Perceptron Networks. In: JAYNE, C., ILIADIS, L., eds. Engineering Applications of Neural Networks. Cham: Springer, 2016, S. 283-294. Communications in Computer and Information Science, 629. ISBN 978-3-319-44187-0. ISSN 1865-0929
Dostupné z: doi:10.1007/978-3-319-44188-7_21
DOI: 10.1007/978-3-319-44188-7_21
ID: 460704

Abstrakt

Model complexity of shallow (one-hidden-layer) perceptron networks computing multivariable functions on finite domains is investigated. Lower bounds are derived on growth of the number of network units or sizes of output weights in terms of variations of functions to be computed. A concrete construction of a class of functions which cannot be computed by perceptron networks with considerably smaller numbers of units and output weights than the sizes of the function’s domains is presented. In particular, functions on Boolean d-dimensional cubes are constructed which cannot be computed by shallow perceptron networks with numbers of hidden units and sizes of output weights depending on d polynomially. A subclass of these functions is described whose elements can be computed by two-hidden-layer networks with the number of units depending on d linearly.