Articles

Le problème XOR dans les réseaux neuronaux.

Introduction
C’est le premier d’une série de posts explorant les implémentations de réseaux neuronaux artificiels (ANN). Le but de l’article est d’aider le lecteur à avoir une intuition des concepts de base avant de passer aux implémentations algorithmiques qui suivront.

Aucune connaissance préalable n’est supposée, bien que, dans un souci de brièveté, toute la terminologie ne soit pas expliquée dans l’article. Au lieu de cela, des hyperliens sont fournis vers Wikipédia et d’autres sources où une lecture supplémentaire peut être nécessaire.

C’est un grand sujet. Les ANN ont une grande variété d’applications et peuvent être utilisés pour l’apprentissage supervisé, non supervisé, semi-supervisé et par renforcement. Et ce, avant d’aborder les architectures spécifiques aux problèmes au sein de ces catégories. Mais il faut bien commencer quelque part, alors pour réduire le champ d’application, nous allons commencer par l’application des ANN à un problème simple.

Le problème XOr
Le problème XOr, ou « exclusif ou », est un problème classique dans la recherche sur les ANN. C’est le problème de l’utilisation d’un réseau neuronal pour prédire les sorties des portes logiques XOr étant donné deux entrées binaires. Une fonction XOr doit renvoyer une valeur vraie si les deux entrées ne sont pas égales et une valeur fausse si elles sont égales. Toutes les entrées possibles et les sorties prédites sont présentées dans la figure 1.

XOr est un problème de classification et un problème pour lequel les sorties attendues sont connues à l’avance. Il est donc approprié d’utiliser une approche d’apprentissage supervisé.

En surface, XOr semble être un problème très simple, cependant, Minksy et Papert (1969) ont montré que c’était un gros problème pour les architectures de réseaux neuronaux des années 1960, connues sous le nom de perceptrons.

Perceptrons
Comme tous les ANN, le perceptron est composé d’un réseau d’unités, qui sont analogues aux neurones biologiques. Une unité peut recevoir une entrée d’autres unités. Ce faisant, elle prend la somme de toutes les valeurs reçues et décide si elle va transmettre un signal aux autres unités auxquelles elle est connectée. C’est ce qu’on appelle l’activation. La fonction d’activation utilise un moyen ou un autre pour réduire la somme des valeurs d’entrée à 1 ou 0 (ou à une valeur très proche de 1 ou 0) afin de représenter l’activation ou son absence. Une autre forme d’unité, connue sous le nom d’unité de biais, s’active toujours, envoyant typiquement un 1 codé en dur à toutes les unités auxquelles elle est connectée.

Les perceptrons comprennent une seule couche d’unités d’entrée – dont une unité de biais – et une seule unité de sortie (voir figure 2). Ici, une unité de biais est représentée par un cercle pointillé, tandis que les autres unités sont représentées par des cercles bleus. Il existe deux unités d’entrée sans biais représentant les deux valeurs d’entrée binaires pour XOr. N’importe quel nombre d’unités d’entrée peut être inclus.

Le perceptron est un type de réseau feed-forward, ce qui signifie que le processus de génération d’une sortie – connu sous le nom de propagation vers l’avant – circule dans une direction de la couche d’entrée à la couche de sortie. Il n’existe aucune connexion entre les unités de la couche d’entrée. Au lieu de cela, toutes les unités de la couche d’entrée sont connectées directement à l’unité de sortie.

Une explication simplifiée du processus de propagation vers l’avant est que les valeurs d’entrée X1 et X2, ainsi que la valeur de biais de 1, sont multipliées par leurs poids respectifs W0..W2, et analysées vers l’unité de sortie. L’unité de sortie prend la somme de ces valeurs et emploie une fonction d’activation – typiquement la fonction de pas de Heavside – pour convertir la valeur résultante en un 0 ou un 1, classant ainsi les valeurs d’entrée comme 0 ou 1.

C’est le réglage des variables de poids qui donne à l’auteur du réseau le contrôle du processus de conversion des valeurs d’entrée en une valeur de sortie. Ce sont les poids qui déterminent où est tracée la ligne de classification, la ligne qui sépare les points de données en groupes de classification. Si tous les points de données d’un côté d’une ligne de classification se voient attribuer la classe 0, tous les autres sont classés 1.

Une limitation de cette architecture est qu’elle n’est capable de séparer les points de données qu’avec une seule ligne. Ceci est regrettable car les entrées XOr ne sont pas linéairement séparables. Ceci est particulièrement visible si vous tracez les valeurs d’entrée XOr sur un graphique. Comme le montre la figure 3, il n’y a aucun moyen de séparer les prédictions 1 et 0 avec une seule ligne de classification.

Perceptrons multicouches
La solution à ce problème est d’aller au-delà de l’architecture monocouche en ajoutant une couche supplémentaire d’unités sans aucun accès direct au monde extérieur, appelée couche cachée. Ce type d’architecture – illustré à la figure 4 – est un autre réseau feed-forward connu sous le nom de perceptron multicouche (MLP).

Il convient de noter qu’un MLP peut avoir un nombre quelconque d’unités dans ses couches d’entrée, cachées et de sortie. Il peut également y avoir un nombre quelconque de couches cachées. L’architecture utilisée ici est conçue spécifiquement pour le problème XOr.

Similaire au perceptron classique, la propagation vers l’avant commence par la multiplication des valeurs d’entrée et de l’unité de biais de la couche d’entrée par leurs poids respectifs, cependant, dans ce cas, il y a un poids pour chaque combinaison d’entrée (y compris l’unité de biais de la couche d’entrée) et d’unité cachée (à l’exclusion de l’unité de biais de la couche cachée). Les produits des valeurs de la couche d’entrée et de leurs poids respectifs sont analysés comme entrée des unités sans biais de la couche cachée. Chaque unité cachée sans biais invoque une fonction d’activation – généralement la fonction sigmoïde classique dans le cas du problème XOr – pour réduire la somme de ses valeurs d’entrée à une valeur comprise entre 0 et 1 (généralement une valeur très proche de 0 ou 1). Les sorties de chaque unité de couche cachée, y compris l’unité de biais, sont ensuite multipliées par un autre ensemble de poids respectifs et envoyées à une unité de sortie. L’unité de sortie analyse également la somme de ses valeurs d’entrée à travers une fonction d’activation – encore une fois, la fonction sigmoïde est appropriée ici – pour renvoyer une valeur de sortie comprise entre 0 et 1. C’est la sortie prédite.

Cette architecture, bien que plus complexe que celle du réseau perceptron classique, est capable de réaliser une séparation non linéaire. Ainsi, avec le bon ensemble de valeurs de poids, il peut fournir la séparation nécessaire pour classer avec précision les entrées XOr.

Backpropagation
L’éléphant dans la pièce, bien sûr, est comment on pourrait arriver à un ensemble de valeurs de poids qui assurent que le réseau produit la sortie attendue. En pratique, essayer de trouver manuellement un ensemble acceptable de poids pour un réseau MLP serait une tâche incroyablement laborieuse. En fait, elle est NP-complète (Blum et Rivest, 1992). Cependant, il est heureusement possible d’apprendre automatiquement un bon ensemble de valeurs de poids par un processus connu sous le nom de rétropropagation. Ce processus a été démontré pour la première fois comme fonctionnant bien pour le problème XOr par Rumelhart et al. (1985).

L’algorithme de rétropropagation commence par comparer la valeur réelle sortie par le processus de propagation avant à la valeur attendue, puis se déplace en arrière à travers le réseau, en ajustant légèrement chacun des poids dans une direction qui réduit la taille de l’erreur d’un petit degré. La propagation avant et arrière est ré-exécutée des milliers de fois sur chaque combinaison d’entrée jusqu’à ce que le réseau puisse prédire avec précision la sortie attendue des entrées possibles en utilisant la propagation avant.

Pour le problème xOr, 100 % des exemples de données possibles sont disponibles pour être utilisés dans le processus de formation. Nous pouvons donc nous attendre à ce que le réseau formé soit 100% précis dans ses prédictions et il n’y a pas besoin de se préoccuper de questions telles que le biais et la variance dans le modèle résultant.

Conclusion
Dans ce post, le problème classique ANN XOr a été exploré. Le problème lui-même a été décrit en détail, ainsi que le fait que les entrées pour XOr ne sont pas linéairement séparables dans leurs catégories de classification correctes. Une solution non linéaire – impliquant une architecture MLP – a été explorée à un haut niveau, ainsi que l’algorithme de propagation vers l’avant utilisé pour générer une valeur de sortie du réseau et l’algorithme de rétropropagation, qui est utilisé pour former le réseau.

Le prochain post de cette série présentera une mise en œuvre Java de l’architecture MLP décrite ici, y compris tous les composants nécessaires pour former le réseau à agir comme une porte logique XOr.

Blum, A. Rivest, R. L. (1992). La formation d’un réseau neuronal à 3 nœuds est NP-complète. Neural Networks, 5(1), 117-127.