Related Experiment Video
Updated: Aug 8, 2026

Generating Strictly Controlled Stimuli for Figure Recognition Experiments
Published on: March 18, 2019
The influence of oppositely classified examples on the generalization complexity of Boolean functions
Leonardo Franco1, Martin Anthony
1Departamento de Lenguajes y Ciencias de la Computación, Universidad de Málaga, Campus de Teatinos S/N, 29071 Málaga, Spain. lfranco@lcc.uma.es
Abstract:
In this paper, we analyze Boolean functions using a recently proposed measure of their complexity. This complexity measure, motivated by the aim of relating the complexity of the functions with the generalization ability that can be obtained when the functions are implemented in feed-forward neural networks, is the sum of a number of components. We concentrate on the case in which we use the first two of these components. The first is related to the "average sensitivity" of the function and the second is, in a sense, a measure of the "randomness" or lack of structure of the function. In this paper, we investigate the importance of using the second term in the complexity measure, and we consider to what extent these two terms suffice as an indicator of how difficult it is to learn a Boolean function. We also explore the existence of very complex Boolean functions, considering, in particular, the symmetric Boolean functions.
Related Concept Videos
Fundamental Theorem of Algebra
Theorems of Pappus and Guldinus: Problem Solving
Types of Functions II
Introduction to One-to-one Functions
Generalization, Discrimination, and Extinction
Generalization occurs when a behavior reinforced in one context is performed in similar situations. For instance, a student who studies diligently for calculus and receives excellent grades might apply the same study habits to psychology and history, expecting similar results. Generalization shows how learning in one setting can influence behavior in...
Graphical Representation of Inequalities