Titre du document / Document title

On a generalization complexity measure for boolean functions

Auteur(s) / Author(s)

FRANCO Leonardo ⁽¹⁾ ; ANTHONY Martin ⁽²⁾ ;

Affiliation(s) du ou des auteurs / Author(s) Affiliation(s)

⁽¹⁾ Department of Experimental Psychology University of Oxford South Parks Road, Oxford OX1 3UD, ROYAUME-UNI
⁽²⁾ Department of Mathematics London School of Economics and Political Science, London WC2A 2AE, ROYAUME-UNI

Résumé / Abstract

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 two components. The first of these 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. We also explore the existence of very complex Boolean functions, considering, in particular, the symmetric Boolean functions.

Source / Source

Congrès
2004 International Joint Conference on Neural Networks :   ( proceedings )  ( Budapest, Hungary, 25-29 July, 2004 )
International Joint Conference on Neural Networks, Budapest , HONGRIE (25/07/2004)
2004  [Note(s) : XLVII-3302 p., ] (19 ref.), [Notes: "IEEE Catalog Number: 04CH37541"--T.p. verso] ISBN 0-7803-8359-1 ;  Illustration : Illustration ;

Langue / Language

Anglais

Editeur / Publisher

IEEE, Piscataway NJ, ETATS-UNIS  (2004) (Monographie)

Mots-clés anglais / English Keywords

Symmetric function

;

Complex function

;

Neural network

;

Boolean function

;

Function decomposition

;

Complexity measure

;

Mots-clés français / French Keywords

Fonction symétrique

;

Fonction complexe

;

Réseau neuronal

;

Fonction booléenne

;

Décomposition fonction

;

Mesure complexité

;

Mots-clés espagnols / Spanish Keywords

Función simétrica

;

Función compleja

;

Red neuronal

;

Función booliana

;

Descomposición función

;

Medida complexidad

;

Localisation / Location

INIST-CNRS, Cote INIST : Y 38777(1), 35400013873618.1680