Representations of highly-varying functions by perceptron networks

Autoři: RNDr. Věra Kůrková, DSc.
Rok vydání: 2013
Typ publikace: Konferenční příspěvek (mezinárodní konf.)
Periodikum: ITAT 2013: Information Technologies - Applications and Theory Workshops, Posters, and Tutorials
Projekty: Učení funkcionálních vztahů z vysoce dimenzionálních dat
Bibliografická citace: KŮRKOVÁ, Věra. Representations of highly-varying functions by perceptron networks. In: VINAŘ, T., HOLEŇA, M., LEXA, M., PEŠKA, L., VOJTÁŠ, P., eds. ITAT 2013: Information Technologies - Applications and Theory Workshops, Posters, and Tutorials. North Charleston: CreateSpace Independent Publishing Platform, 2013, S. 73-76. ISBN 978-1-4909-5208-6.
ID: 396820

Abstrakt

Tractability of representations of multivariable functions by perceptron networks is investigated. There are described classes of functions which cannot be tractably represented by Heaviside perceptron networks in the sense that all their representations by such networks require numbers of units or sizes of output weights depending exponentially on the number of variables d. It is shown that the concept of variational norm from approximation theory can play a role of a measure of such tractability. Existence of large sets of Boolean functions with variations depending on d exponentially is proven. The results are illustrated by an example of a class of Boolean functions defined in terms of their communication matrices.