| Computational Power of Neural Networks: A Kolmogorov Complexity Characterization (2007) | |||||||||||||||||
Abstract | |||||||||||||||||
| The computational power of recurrent neural networks is shown to depend ultimately on the amount of information encoded in the constants (weights) of the network. The information is characterized by a variant of resource-bounded Kolmogorov complexity, in which the time dimension allows for efficiency considerations. We reveal a proper hierarchy of nonuniform complexity classes associated with networks, having weights of increasing Kolmogorov complexity. Key words: Neural Networks, Turing Machines. Kolmogorov Complexity. 1 Introduction We provide a novel but very natural view on the theory of nonuniform complexity in informationtheoretic terms. We focus on the classical recurrent neural networks, consisting of a finite number of simple processors, each of which computes a scalar ---real-valued--- function of an integrated input. This scalar function, or "activation," is meant to reflect the graded response of biological neurons to the net sum of excitatory and inhibitory inputs affectin... | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||