Calculabilité neuronale des fonctions booléennes

L'idée que l'on puisse faire du calcul neuronal avec un réseau simple (avec ) fut lancée immédiatement après la guerre mais la question de calculabilité des fonctions booléennes par des réseaux neuronaux a longtemps freiné leur développement. Considérons en effet le cas élémentaire de la fonction ``où exclusif'', noté traditionnellement XOR, et représentons par 1 la valeur logique vrai et par -1 la valeur logique faux. La table de vérité de la fonction XOR est donnée dans la table suivante :

a	b	a XOR b
1	1	-1
1	-1	1
-1	1	1
-1	-1	-1

Table de vérité de la fonction XOR.

L'espace des entrées contient donc deux sites et les configurations possibles sont tandis que l'espace des sorties contient un seul site. Supposons en outre que le réseau ne contient aucune couche intermédiaire : alors et . Pour pouvoir implanter effectivement la fonction XOR il faut être capable de satisfaire simultanément les inégalités linéaires suivantes

On peut facilement se convaincre que ces inégalités sont incompatibles. Ceci tient au fait que la partition du domaine en deux régions connexes de signe constant pour le produit ne peut pas se faire par des relations linéaires. On dit que la fonction XOR n'est pas linéairement séparable.

Ce n'est que lorsque le modèle en couches a été inventé que le calcul neuronal a pris un nouvel essor. On peut en effet montrer que toute fonction booléenne de arguments peut être implantée par un réseau avec une seule couche intermédiaire () en choisissant , et . L'exemple de la fonction XOR a cependant montré que certaines fonctions booléennes peuvent être implantées plus efficacement que ne l'exige le théorème précédent.