November 9, 2001
We define a measure for the complexity of Boolean functions related to their implementation in neural networks, and in particular close related to the generalization ability that could be obtained through the learning process. The measure is computed through the calculus of the number of neighbor examples that differ in their output value. Pairs of these examples have been previously shown to be part of the minimum size training set needed to obtain perfect generalization in feedforward neural networks. The main advantage of the proposed measure, in comparison to existing ones, is the way in which the measure is evaluated, as it can be computed from the definition of the function itself, independently of its implementation. The validity of the proposal is analyzed through numerical simulations performed on different feedforward neural networks architectures, and a good agreement is obtained between the predicted complexity and the generalization ability for different classes of functions. Also an interesting analogy was found between the proposed complexity measure and the energy function of ferromagnetic systems, that could be exploited, by use of the existing results and mathematical tools developed within a statistical mechanics framework, to explore in a more rigorous way the properties of Boolean functions when implemented on neural networks. We conjecture that the proposed measure could help as an useful tool for carrying a systematic study of the computational capabilities of neural networks, essentially by permitting an easy and reliable classification of Boolean functions. Possible extensions of the work are also discussed.
Similar papers 1
April 1, 2001
The information processing abilities of a multilayer neural network with a number of hidden units scaling as the input dimension are studied using statistical mechanics methods. The mapping from the input layer to the hidden units is performed by general symmetric Boolean functions whereas the hidden layer is connected to the output by either discrete or continuous couplings. Introducing an overlap in the space of Boolean functions as order parameter the storage capacity if f...
March 13, 2023
We introduce a new notion of complexity of functions and we show that it has the following properties: (i) it governs a PAC Bayes-like generalization bound, (ii) for neural networks it relates to natural notions of complexity of functions (such as the variation), and (iii) it explains the generalization gap between neural networks and linear schemes. While there is a large set of papers which describes bounds that have each such property in isolation, and even some that have ...
February 7, 2012
We study two measures of the complexity of heterogeneous extended systems, taking random Boolean networks as prototypical cases. A measure defined by Shalizi et al. for cellular automata, based on a criterion for optimal statistical prediction [Shalizi et al., Phys. Rev. Lett. 93, 118701 (2004)], does not distinguish between the spatial inhomogeneity of the ordered phase and the dynamical inhomogeneity of the disordered phase. A modification in which complexities of individua...
March 7, 2016
We explore a definition of complexity based on logic functions, which are widely used as compact descriptions of rules in diverse fields of contemporary science. Detailed numerical analysis shows that (i) logic complexity is effective in discriminating between classes of functions commonly employed in modelling contexts; (ii) it extends the notion of canalisation, used in the study of genetic regulation, to a more general and detailed measure; (iii) it is tightly linked to th...
May 21, 2021
The subject of this textbook is the analysis of Boolean functions. Roughly speaking, this refers to studying Boolean functions $f : \{0,1\}^n \to \{0,1\}$ via their Fourier expansion and other analytic means. Boolean functions are perhaps the most basic object of study in theoretical computer science, and Fourier analysis has become an indispensable tool in the field. The topic has also played a key role in several other areas of mathematics, from combinatorics, random graph ...
August 1, 2023
We investigate the descriptive complexity of a class of neural networks with unrestricted topologies and piecewise polynomial activation functions. We consider the general scenario where the running time is unlimited and floating-point numbers are used for simulating reals. We characterize these neural networks with a rule-based logic for Boolean networks. In particular, we show that the sizes of the neural networks and the corresponding Boolean rule formulae are polynomially...
September 18, 2020
There is currently a rapid increase in the number of challenge problem, benchmarking datasets and algorithmic optimization tests for evaluating AI systems. However, there does not currently exist an objective measure to determine the complexity between these newly created domains. This lack of cross-domain examination creates an obstacle to effectively research more general AI systems. We propose a theory for measuring the complexity between varied domains. This theory is the...
April 3, 2020
A nearest neighbor representation of a Boolean function is a set of positive and negative prototypes in $R^n$ such that the function has value 1 on an input iff the closest prototype is positive. For $k$-nearest neighbor representation the majority classification of the $k$ closest prototypes is considered. The nearest neighbor complexity of a Boolean function is the minimal number of prototypes needed to represent the function. We give several bounds for this measure. Separa...
February 1, 2024
Dominant areas of computer science and computation systems are intensively linked to the hypercube-related studies and interpretations. This article presents some transformations and analytics for some example algorithms and Boolean domain problems. Our focus is on the methodology of complexity evaluation and integration of several types of postulations concerning special hypercube structures. Our primary goal is to demonstrate the usual formulas and analytics in this area, g...
May 10, 2023
The $\textit{von Neumann Computer Architecture}$ has a distinction between computation and memory. In contrast, the brain has an integrated architecture where computation and memory are indistinguishable. Motivated by the architecture of the brain, we propose a model of $\textit{associative computation}$ where memory is defined by a set of vectors in $\mathbb{R}^n$ (that we call $\textit{anchors}$), computation is performed by convergence from an input vector to a nearest nei...