\( \newcommand{\R}{\mathbb{R}} \newcommand{\Rp}{\mathbb{R_+}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Rn}{\mathbb{R}^n} \newcommand{\N}{\mathbb{N}} \renewcommand{\to}{\rightarrow} \newcommand{\from}{\colon} \renewcommand{\Vec}{\mathsf{vec}} \newcommand{\Ker}{\mathrm{Ker}} \renewcommand{\Im}{\mathrm{Im}} \newcommand{\rang}{\mathrm{rang}} \newcommand{\O}{\mathcal{O}} \newcommand{\C}{\mathcal{C}} \newcommand{\U}{\mathcal{U}} \newcommand{\x}{\mathbf{x}} \newcommand{\z}{\mathbf{z}} \newcommand{\w}{\mathbf{w}} \newcommand{\a}{\mathbf{a}} \newcommand{\dpartial}[2]{{\partial #1 \over \partial #2}} \newcommand{\d}{\mathbf{d}} \)

Réseaux de Neurones

Programmation pour l’IA

Florent Capelli

Université d’Artois, CRIL

Un peu d’histoire

Dartmouth Summer Research Project 1956

Organisé par Shannon, Minsky, Rochester et McCarthy.

Naissance du terme “Intelligence Artificielle” :

Artificial intelligence comprises methods, tools, and systems for solving problems that normally require the intelligence of humans. The term intelligence is always defined as the ability to learn effectively, to react adaptively, to make proper decisions, to communicate in language or images in a sophisticated way, and to understand.

Deux approches s’opposent :

Approche Biologique

“Imiter” le cerveau.

Le neurone formel

Un neurone formel calcule :

  • \(f(\sum_{i=1}^n w_i x_i)\): comment trouver les “meilleurs” \(w_i\) pour modéliser une fonction donnée?
  • \(f\) s’appelle la fonction d’activation
  • \(\w = w_1,\dots,w_n\) sont les paramètres

Notation matricielle: \(f(\w^T\x)\)

On ajoute parfois un paramètre de plus: le bias. On a alors \(f(\w^T\x+b)\).

Neurone et classification binaire

On cherche un séparateur linéaire !

Hiver de l’IA

1969, Minsky et Papert montre les limites du neurone formel : on ne sépare que des choses linéairement.

Ne peut calculer \(parite(x_1,\dots,x_n)\) qui vaut vraie si le nombre de \(x_i\) mis à 1 est pair.

Fin des années 70, l’excitation initiale retombe et les financements se font plus rares :

Pendant l’hiver

Les idées développées sont cependant un terreau fertile pour l’informatique en général

Réseau de neurones (artificiels)

Imiter le cerveau et ses connexions

Comment “apprendre” une structure constituée de 80 milliards de neurones et leurs connexions ?

Technologie de l’époque très loin de cela.

Réseaux de neurones

Intêret pour les réseaux de neurones renouvelé :

Un GPU (ou carte graphique, crédit : Henry Mühlpfordt)
  • Avancée technologique ont permis de passer à une échelle supérieur (GPU)
  • Applications très prometteuses (reconnaissance d’images, transformers, etc.). Voir AlexNet (2012).
  • Données d’apprentissage bien plus facile d’accès (internet)

Quelques références

Apprentissage machine, Clé de l’Intelligence Artificielle, Rémi Gilleron
Deep Learning
The Little Book of Deep Learning, François Fleuret

Le plan aujourd’hui

Le cas à un neurone

Classification

On a \(S = (\x^1, y^1), \dots, (\x^k, y^k)\) exemples avec \(y^j \in \{-1,1\}\). On veut classifier avec un neurone :

g x1 x₁ signe signe x1->signe w₁ dots … dots->signe x2 xₙ x2->signe wₙ
  • Comment trouver les bons paramètres pour les données ?
    • On définit une fonction d’erreur (loss): \(L(\w; S)\)
    • On cherche \(\w\) qui minimise \(L(\w;S)\)
    • On utilise la descente de gradient

Exemple: erreur quadratique \(L(\w;S) = \sum_{i=1}^k (signe(\w^T\x^i) - y^i)^2\).

Fonctions d’activation

ReLU(x) = max(0,x)
g x1 x₁ signe ReLU x1->signe w₁ dots … dots->signe x2 xₙ x2->signe wₙ

Inuition: on introduit des portes calcul simulant de façon continue un “if-then-else”.

Sigmoïde : \sigma(x) = {1 \over 1 + e^{-x}}
g x1 x₁ signe σ x1->signe w₁ dots … dots->signe x2 xₙ x2->signe wₙ

Inuition: on lisse la fonction \(signe_0(x) = \begin{cases} 0 \text{ si } x<0 \\ 1 \text{ sinon. }\end{cases}\)

Régression logistique

Étant donné \(\x\), on veut apprendre la probabilité que \(\x\) soit classé dans la classe \(y \in \{0,1\}\):

\[ Pr(y | \x)\]

On cherche \(Pr(0|\x)\) sous la forme \(\sigma(\w^T\x) = {1 \over 1+e^{\sum_{i=1}^n w_i x_i}}\)

Régression logistique : erreur

Étant donné un jeu de données \(S = (\x^1,y^1), \dots, (\x^m,y^m)\) et \(\w\), comment estimer l’erreur de \(\sigma(\w^T\x)\) sur \(S\)?

La vraissemblance de l’hypothèse avec \(S\) est définie par le produit des erreurs sur chaque exemple de \(S\), soit :

\[V(\w;S) = \prod_{i=1}^m \begin{cases}\sigma(\w^T\x_i) \text{ si } y^i = 1 \\ 1-\sigma(\w^T\x_i) \text{ si } y^i=0 \end{cases}\]

On définit alors l’erreur comme \(E_V(\w;S) = {1 \over V(\w;S)}\) et on cherche à la minimiser.

Régression logistique : log-vraissemblance

Problème : \(E_V(\w;S)\) n’a pas des bonnes propriétés de stabilité numérique ; des grandes erreurs sur des données erronées ont une grande influence sur sa valeur. On préfère minimiser le log de l’expression vu précédemment.

\[E_{\log}(\w;S) = -\sum_{i=1}^m \begin{cases}\log \sigma(\w^T\x^i) \text{ si } y^i = 1 \\ \log(1-\sigma(\w^T\x^i)) \text{ si } y^i=0 \end{cases}\]

Qu’on peut aussi s’écrire :

\[E_{\log}(\w;S) = -\sum_{i=1}^m y^i\log \sigma(\w^T\x^i) + (1-y^i)\log(1-\sigma(\w^T\x^i)) \]

Pssst… on reconnaît l’entropie définie pour les arbres de décision !

Régression logistique : minimisation de l’erreur

Comme \(x \mapsto -\log(x)\) est convexe, on a que \(E_{\log}(\w;S)\) est convexe:

Comme on a \(\dpartial{\sigma(z)}{z} = \sigma(z)(1-\sigma(z))\) :

\[\dpartial{\log \sigma(\w^T\x)}{w_j} = {x_j (1-\sigma(\w^T\x))(\sigma(\w^T\x)) \over \sigma(\w^T\x)} = x_j (1-\sigma(\w^T\x))\]

\[\dpartial{(1-\log \sigma(\w^T\x))}{w_j} = {-x_j (1-\sigma(\w^T\x))(\sigma(\w^T\x)) \over 1-\sigma(\w^T\x)} = -x_j \sigma(\w^T\x)\]

Régression logistique : gradient

Pour un exemple \(\x,y\), on a alors :

Si \(y=1\): \(\dpartial{\log \sigma(\w^T\x)}{w_j} = {x_j (1-\sigma(\w^T\x))(\sigma(\w^T\x)) \over \sigma(\w^T\x)} = x_j (1-\sigma(\w^T\x))\)

Si \(y=0\): \(\dpartial{(1-\log \sigma(\w^T\x))}{w_j} = {-x_j (1-\sigma(\w^T\x))(\sigma(\w^T\x)) \over 1-\sigma(\w^T\x)} = -x_j \sigma(\w^T\x)\)

Dans les deux cas: \(x_j(y-\sigma(\w^T\x)\).

Donc le gradient \(\Delta E_{\log} = -\sum_{(\x,y) \in S} \x (y-\sigma(\w^T\x))\)

Ou encore, si \(X\) est la matrice \(m \times n\) dont les lignes sont \(\x \in S\) :

\[\Delta E_{\log} = -(Y - \sigma(X \times \w)) \times X\]

Généralisation à \(p\) classes

Comment faire une régression logistique qui permette d’estimer \(P(y|\x)\) quand \(y \in \{c_1,\dots,c_p\}\) peut prendre \(p>2\) valeurs ?

On utilise une fonction softmax, c’est-à-dire qu’on cherche des vecteurs \(\w^1,\dots,\w^p\) tels que pour \(1 \leq k \leq p\)

\[P(c_k|\x) = {e^{\w^k \x} \over \sum_{l=1}^p e^{\w^l \x}}\]

g x1 x₁ N σ x1->N w₁ dots … dots->N x2 xₙ x2->N wₙ
Régression logistique
g cluster_g Softmax layer x1 x₁ N1 exp x1->N1 w₁¹ N2 exp x1->N2 w₁² N3 exp x1->N3 w₁³ x2 x₂ x2->N1 w₂¹ x2->N2 w₂² x2->N3 w₂³ moyenne moyenne N1->moyenne N2->moyenne N3->moyenne dot moyenne->dot
Régression multiclasse (softmax)

Réseaux de neurones

Réseau de neurones

g F1 ReLU w1F3 2 F1->w1F3 w1F4 -1 F1->w1F4 F2 ReLU w2F3 1 F2->w2F3 w2F4 -1 F2->w2F4 F3 σ y₁ y₁ F3->y₁ F4 ReLU y₂ y₂ F4->y₂ w1F1 2.5 w1F1->F1 w2F1 -1 w2F1->F1 w1F2 -1 w1F2->F2 w2F2 1 w2F2->F2 w1F3->F3 w2F3->F3 w1F4->F4 w2F4->F4 x₁ x₁ x₁->w1F1 x₁->w1F2 x₂ x₂ x₂->w2F1 x₂->w2F2

Un réseau de neurones définie donc :

  • une fonction de \(\R^n \rightarrow \R^k\)
  • un modèle : la structure du réseau est fixé, les poids sur les arêtes (en vert sur la figure) peuvent être modifiés.

On cherche des bons poids pour simuler une fonction \(f \from \R^n \to \R^k\) dont on connaît des exemples.

Comportement non-linéaire

On considère le problème de classification suivant (non linéairement séparable) : \[signe(x_1 \cdot x_2)\]

XOR

Démo : https://playground.tensorflow.org/

La non linéarité des fonctions d’activation permet d’apprendre des séparateurs plus complexes.

Entraînement des réseaux de neurones

Descente de gradient

Essentiellement un gradient stochastique :

Convergence

Pas de garanties de convergence vers minimum global, mais en pratique “ça marche”.

Conditions de réussite :

Défi : calculer \(\Delta E\) efficacement !

Calcul du gradient : composition

Rappel chain rule : \(f(g(x))' = f'(g(x)) g'(x)\).

Autre formulation :

Calcul du gradient

Réseau de neurones \(R(X;W)\) avec les neurones \(N_1,\dots,N_p\): dépends des paramètres \[W = w_1^{N_1}, \dots, w_{k_1}^{N_1}, \dots, w_1^{N_p}, \dots, w_{k_p}^{N_p}\]

Erreur quadratique : \(E(W;S) = \sum_{(\x,y) \in S} (R(\x;W)-y)^2\).

\(\dpartial{E}{w} = \sum_{(\x,y) \in S} 2(R(\x;W)-y) \dpartial{R}{w}\)

Pour faire une descente de gradient, on doit être capable de dériver le réseau \(R\) par rapport à \(w\) (en de nombreux point \(\x\)).

Calcul récursif

Un neurone \(N\) calcule \(g_N = f_N(\w^N \z)\) où \(z_i\) est lui-même le résultat d’un réseau de neurones.

On peut calculer récursivement le gradient d’un réseau de neurones.

Calcul efficace ?

Attention, si on le fait naïvement :

g N0 N₀(w₀) N1 N₁ N0->N1 N2 N₂ N0->N2 N3 N₃ N1->N3 N2->N3

On va devoir calculer \(\dpartial{N_3}{w_0}\)

  • On doit calculer récursivement \(\dpartial{N_1}{w_0}\) et \(\dpartial{N_2}{w_0}\)
  • Récursivement : on calcule \(\dpartial{N_0}{w_0}\)… deux fois.
g N0 N₀(w₀) N1 N₁ N0->N1 N2 N₂ N0->N2 N3 N₃ N1->N3 N4 N₄ N1->N4 N2->N3 N2->N4 N5 N₅ N3->N5 N6 N₆ N3->N6 N4->N5 N4->N6 N7 N₇ N5->N7 N6->N7

Pour calculer \(\dpartial{N_7}{w_0}\) on va calculer \(\dpartial{N_0}{w_0}\)… 8 fois (une fois par chemin).

Solution 1 : on ajoute un cache ; si on veut calculer \(\dpartial{N_0}{w_0}\), on vérifie si cela n’a pas déjà été fait dans la cache. Si oui, on prend la valeur du cache. Si non, on exécute l’appel récursif.

Solution 2 : on découpe le réseau en couches ; on voit que le gradient d’une couche ne dépend que des gradients de la couche précédentes et on utilise cela pour le calcul. C’est l’algorithme de backpropagation. Voir semaine prochaine !