Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Apprentissage automatique et réseaux de neurones

Le perceptron et les réseaux multicouches : théorème de Novikoff, XOR et approximation universelle

Le perceptron et le théorème de convergence de Novikoff démontré, le problème du XOR, les réseaux multicouches et les fonctions d'activation, le théorème d'approximation universelle, une expérience sur 100 graines concernant la taille du réseau.

https://www.electronics-engineering.com/fr/perceptron-reseaux-multicouches-xor-approximation-universelle/

Pas encore de vote : soyez le premier à noter cette page.

Un réseau de neurones est une fonction construite en composant de nombreuses fonctions simples, les neurones : chacun calcule une somme pondérée de ses entrées et la fait passer par une fonction non linéaire. Cette leçon part du neurone le plus simple, le perceptron de Rosenblatt (1958), démontre qu’il apprend en un nombre fini de pas quand les classes sont séparables par une droite, montre pourquoi une seule couche ne suffit pas (le problème du XOR) et introduit les réseaux multicouches, avec le théorème d’approximation universelle et une expérience qui montre à quel point la taille du réseau compte.

Le perceptron

Le perceptron classe une entrée \mathbf x dans deux classes, +1 et -1, avec le signe d’une somme pondérée : \hat y = \text{sign}(\mathbf w^T\mathbf x + b). Géométriquement, la frontière entre les classes est l’hyperplan \mathbf w^T\mathbf x + b = 0 (une droite en deux dimensions). L’algorithme d’apprentissage est très simple : on parcourt les exemples et, quand l’un est mal classé, on déplace le vecteur des poids vers lui,

    \[ \text{if } y_i(\mathbf w^T\mathbf x_i) \le 0:\quad \mathbf w \leftarrow \mathbf w + y_i\mathbf x_i \]

(l’ordonnée à l’origine b est incluse dans \mathbf w en ajoutant à \mathbf x une composante constante 1).

Théorème (Novikoff, 1962). S’il existe un vecteur unitaire \mathbf u qui sépare les données avec une marge \gamma \gt  0, c’est-à-dire y_i\,\mathbf u^T\mathbf x_i \ge \gamma pour tout i, et que \|\mathbf x_i\| \le R, le perceptron fait au plus (R/\gamma)^2 corrections.

Démonstration. On suit deux grandeurs après k corrections, en partant de \mathbf w_0 = 0. La projection sur \mathbf u croît d’au moins \gamma à chaque correction : \mathbf u^T\mathbf w_{k+1} = \mathbf u^T\mathbf w_k + y_i\mathbf u^T\mathbf x_i \ge \mathbf u^T\mathbf w_k + \gamma, donc \mathbf u^T\mathbf w_k \ge k\gamma. La norme, elle, croît peu : \|\mathbf w_{k+1}\|^2 = \|\mathbf w_k\|^2 + 2y_i\mathbf w_k^T\mathbf x_i + \|\mathbf x_i\|^2 \le \|\mathbf w_k\|^2 + R^2, parce que la correction n’a lieu que si y_i\mathbf w_k^T\mathbf x_i \le 0 ; donc \|\mathbf w_k\|^2 \le kR^2. Par l’inégalité de Cauchy-Schwarz, k\gamma \le \mathbf u^T\mathbf w_k \le \|\mathbf w_k\| \le \sqrt k\,R, c’est-à-dire k \le (R/\gamma)^2. ∎

La borne ne dépend ni du nombre d’exemples ni de la dimension de l’espace, mais seulement de la « distance » entre les classes par rapport à leur étendue. Dans une expérience avec 167 points séparables avec une marge de 0,15, le perceptron a fait 11 corrections en 3 passages sur les données ; la borne de Novikoff était 421 : le théorème est un pire cas, la pratique fait en général bien mieux.

Le perceptron sur des données séparables
Les points bleus et rouges sont les deux classes ; la droite noire est la frontière trouvée par le perceptron après 11 corrections, qui sépare parfaitement les deux classes.

La limite d’une couche : le XOR

Le perceptron trouve une droite, mais de nombreux problèmes ne sont pas séparables par une droite. Le plus simple est le XOR (ou exclusif) : la sortie vaut 1 si exactement l’une des deux entrées vaut 1. Les points (0, 1) et (1, 0) doivent être d’un côté, (0, 0) et (1, 1) de l’autre : aucune droite ne peut le faire. Minsky et Papert l’ont souligné en 1969, et la recherche sur les réseaux de neurones a ralenti pendant des années.

La solution est d’ajouter une couche cachée : les neurones cachés transforment les entrées en de nouvelles variables dans lesquelles le problème devient séparable. Deux neurones cachés suffisent : l’un peut calculer « au moins une vaut 1 » (OR), l’autre « les deux valent 1 » (AND), et la sortie « OR mais pas AND ».

Le problème du XOR
Les quatre points du carré : (0,1) et (1,0) appartiennent à la classe 1, en bleu, (0,0) et (1,1) à la classe 0, en rouge. Aucune droite ne les sépare ; les deux droites en pointillés des neurones cachés délimitent une bande qui ne contient que les points bleus.

Les réseaux multicouches

Un réseau multicouche (perceptron multicouche, MLP) applique en séquence des transformations linéaires et des non-linéarités :

    \[ \mathbf h_1 = \phi(W_1\mathbf x + \mathbf b_1),\quad \mathbf h_2 = \phi(W_2\mathbf h_1 + \mathbf b_2),\quad \dots,\quad \hat{\mathbf y} = W_L\mathbf h_{L-1} + \mathbf b_L \]

La fonction d’activation \phi est essentielle : sans elle, la composition de transformations linéaires est encore linéaire et le réseau ne serait pas plus puissant qu’une seule couche. Les plus utilisées :

  • la sigmoïde \sigma(z) = 1/(1 + e^{-z}) et la tangente hyperbolique \tanh z : lisses, mais elles « saturent » pour de grands |z|, où la dérivée est presque nulle ;
  • la ReLU \max(0, z) : très simple, de dérivée 1 pour z \gt  0, elle ne sature pas dans un sens. C’est le choix par défaut depuis 2012 ;
  • des variantes lisses comme la GELU et la SiLU, utilisées dans les transformers.

Théorème d’approximation universelle (Cybenko 1989, Hornik 1991). Un réseau à une seule couche cachée et à fonction d’activation non polynomiale peut approcher avec une erreur arbitrairement petite toute fonction continue sur un ensemble fermé et borné, pourvu qu’il ait assez de neurones.

Idée de la démonstration (pour une variable, avec la sigmoïde). Une sigmoïde très raide \sigma(k(x - a)) est presque un échelon en a ; la différence de deux échelons est un « rectangle » entre a et c. Une fonction continue peut être approchée par une fonction en escalier (des sommes de rectangles) avec une erreur aussi petite que l’on veut, en rétrécissant les marches ; chaque rectangle coûte deux neurones. ∎

Le théorème dit que le réseau peut représenter la fonction, pas que la descente de gradient la trouvera, ni combien de neurones il faut (ils peuvent être très nombreux). En pratique, les réseaux profonds, avec de nombreuses couches de largeur modérée, représentent des fonctions utiles avec bien moins de paramètres qu’un réseau large peu profond : chaque couche construit des caractéristiques plus abstraites à partir de celles de la couche précédente.

Une expérience : quelle taille doit avoir le réseau

On entraîne le XOR par descente de gradient à partir de poids aléatoires, en répétant avec 100 graines différentes, et l’on compte combien de fois le réseau apprend vraiment la fonction :

neurones cachésXOR résolu
249 fois sur 100
392 fois sur 100
498 fois sur 100

Avec deux neurones cachés, la solution existe, mais la moitié du temps la descente de gradient s’arrête dans un minimum local (par exemple avec une sortie de 0,5 sur deux des quatre cas). En ajoutant des neurones, le paysage de l’erreur devient plus facile à parcourir et presque tout point de départ mène à une solution. C’est l’une des raisons pour lesquelles les réseaux modernes ont bien plus de paramètres que ce qui serait nécessaire en théorie.

import numpy as np

X = np.array([[0, 0], [0, 1], [1, 0], [1, 1]], float)
y = np.array([0, 1, 1, 0], float)                          # XOR
sig = lambda z: 1 / (1 + np.exp(-z))

def train(hidden, seed, steps=10000, eta=0.5):
    g = np.random.default_rng(seed)
    W1, b1 = g.normal(0, 1, (2, hidden)), np.zeros(hidden)
    W2, b2 = g.normal(0, 1, hidden), 0.0
    for _ in range(steps):
        h = np.tanh(X @ W1 + b1)                           # hidden layer
        out = sig(h @ W2 + b2)
        d2 = out - y                                       # gradient of cross-entropy + sigmoid
        dh = np.outer(d2, W2) * (1 - h ** 2)               # derivative of tanh
        W2 -= eta * h.T @ d2; b2 -= eta * d2.sum()
        W1 -= eta * X.T @ dh; b1 -= eta * dh.sum(0)
    return sig(np.tanh(X @ W1 + b1) @ W2 + b2)

for hidden in (2, 3, 4):
    solved = sum(np.all(np.abs(train(hidden, s) - y) < 0.1) for s in range(100))
    print(f"{hidden} hidden neurons: XOR solved {solved} times out of 100")
print("example with 3 neurons:", np.round(train(3, 0), 3))

Le calcul du gradient écrit ici à la main, pour une couche cachée, se généralise à un nombre quelconque de couches avec la rétropropagation (backpropagation), sujet de la leçon suivante.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x