Démonstration8 min

L'algorithme, et sa vérification

L'algorithme complet, et la vérification qu'il calcule bien ce qu'il prétend calculer.

Six égalités ont été posées sur une seule image, et rassemblées dans l'ordre elles forment un algorithme. Combien de fois faut-il alors traverser le réseau pour obtenir ses cent mille dérivées, et comment sait-on qu'elles sont justes ?

En haut, sous la mention par différences finies centrées, une rangée serrée de quatre-vingts traits verticaux suivie de trois points de suspension, puis le compte : deux cent trois mille cinq cent quarante propagations avant, pour un seul exemple. Sous un trait, la mention par rétropropagation, une flèche grise qui va vers la droite étiquetée un aller, une flèche de brique qui revient vers la gauche étiquetée un retour, et à droite la mention un au lieu de deux cent trois mille cinq cent quarante. En pied, la mention que le rapport ne dépend d'aucune machine. — Le peigne n'est pas dessiné en entier : quatre-vingts traits pour deux cent mille passages, et c'est déjà illisible.

Le compte du haut est celui de la formule (4.1), deux propagations par coefficient ; celui du bas est ce que l'algorithme des pages 3 à 9 demande.

Ce rapport ne dépend ni de la machine, ni du langage, ni de la charge : les durées de la fin de page, elles, en dépendent toutes.

L'aller

\mathbf{z}^{[1]}=W^{[1]}\mathbf{x}+\mathbf{b}^{[1]},\quad \mathbf{a}^{[1]}=\mathrm{ReLU}\big(\mathbf{z}^{[1]}\big),\quad \mathbf{z}^{[2]}=W^{[2]}\mathbf{a}^{[1]}+\mathbf{b}^{[2]},\quad \mathbf{a}^{[2]}=\mathrm{softmax}\big(\mathbf{z}^{[2]}\big)

(4.12)

Rien de neuf : c'est le réseau du chapitre 2. Ce qui est neuf, c'est qu'on garde

\mathbf{x}

\mathbf{z}^{[1]}

\mathbf{a}^{[1]}

\mathbf{a}^{[2]}

Le retour

\begin{aligned}\boldsymbol{\delta}^{[2]}&=\mathbf{a}^{[2]}-\mathbf{y} &&(10\times 1)\\ \mathrm{grad}_{\mathbf{b}^{[2]}}\,\ell&=\boldsymbol{\delta}^{[2]} &&(10\times 1)\\ \mathrm{grad}_{W^{[2]}}\,\ell&=\boldsymbol{\delta}^{[2]}\big(\mathbf{a}^{[1]}\big)^{\mathsf{T}} &&(10\times 128)\\ \boldsymbol{\delta}^{[1]}&=\Big[\big(W^{[2]}\big)^{\mathsf{T}}\boldsymbol{\delta}^{[2]}\Big]\odot\mathrm{ReLU}'\big(\mathbf{z}^{[1]}\big) &&(128\times 1)\\ \mathrm{grad}_{\mathbf{b}^{[1]}}\,\ell&=\boldsymbol{\delta}^{[1]} &&(128\times 1)\\ \mathrm{grad}_{W^{[1]}}\,\ell&=\boldsymbol{\delta}^{[1]}\mathbf{x}^{\mathsf{T}} &&(128\times 784)\end{aligned}

(4.13)

Six lignes, dans l'ordre où elles s'enchaînent : la formule (4.2), admise, pour la première, la proposition 3 pour la deuxième, la proposition 4 pour la troisième, la formule (4.9) pour la quatrième, et pour les deux dernières les mêmes propositions 3 et 4, portées une couche plus bas par la formule (4.10).

PythonL'algorithme, tel qu'il tourne dans cours/lecon4/mesures.py

1def avant(theta, x):                     # x : (784,)2    z1 = theta["W1"] @ x + theta["b1"]   # (128, 784)(784,) -> (128,)3    a1 = np.maximum(z1, 0.0)             # (128,)4    z2 = theta["W2"] @ a1 + theta["b2"]  # (10, 128)(128,)  -> (10,)5    a2 = softmax(z2)                     # (10,)6    return {"x": x, "z1": z1, "a1": a1, "z2": z2, "a2": a2}7 8def arriere(theta, cache, c):9    d2   = cache["a2"] - onehot(c)              # (10,)     proposition 110    g_W2 = np.outer(d2, cache["a1"])            # (10, 128) proposition 411    g_b2 = d2                                   # (10,)     proposition 312    g_a1 = theta["W2"].T @ d2                   # (128,)    proposition 613    d1   = g_a1 * (cache["z1"] > 0.0)           # (128,)    formule 4.914    g_W1 = np.outer(d1, cache["x"])             # (128, 784) proposition 415    g_b1 = d1                                   # (128,)     proposition 316    return {"W1": g_W1, "b1": g_b1, "W2": g_W2, "b2": g_b2}

Le commentaire de droite nomme, pour chaque ligne du retour, la proposition qui l'établit, sauf la première, qui est la formule (4.2) admise page 3. Le programme calcule $\mathrm{grad}_{W^{[2]}}$ avant $\mathrm{grad}_{\mathbf{b}^{[2]}}$ , ce que rien n'interdit puisque les deux ne dépendent que de $\boldsymbol{\delta}^{[2]}$ .

Ce qu'il faut garder entre l'aller et le retour

Quantité gardée	Taille	Employée par
$\mathbf{x}$	$784$	$\mathrm{grad}_{W^{[1]}}\,\ell=\boldsymbol{\delta}^{[1]}\mathbf{x}^{\mathsf{T}}$
$\mathbf{z}^{[1]}$	$128$	$\mathrm{ReLU}'(\mathbf{z}^{[1]})$ , la porte
$\mathbf{a}^{[1]}$	$128$	$\mathrm{grad}_{W^{[2]}}\,\ell=\boldsymbol{\delta}^{[2]}(\mathbf{a}^{[1]})^{\mathsf{T}}$
$\mathbf{a}^{[2]}$	$10$	$\boldsymbol{\delta}^{[2]}=\mathbf{a}^{[2]}-\mathbf{y}$

Soit $1\,050$ nombres à retenir, contre $101\,770$ coefficients dans le réseau, et c'est tout ce qu'il met en mémoire : il ne recalcule rien, il se souvient. Le programme garde en outre $\mathbf{z}^{[2]}$ , dont le retour ne se sert pas. Un procédé qui ne garderait rien devrait refaire la propagation avant à chaque dérivée, et l'on retomberait sur les différences finies.

La vérification

160 dérivées confrontées aux différences finies · cours/lecon4/mesures.py, mesure 2

  epsilon = 1e-05
  50 coefficients tirés dans chaque bloc PARMI CEUX DE DÉRIVÉE NON NULLE.

      bloc    non nuls / total    contrôlés   écart rel. médian   écart rel. max   écart abs. max
      W1         10716 / 100352            50          9.87e-11         6.62e-09         1.10e-11
      b1            57 / 128               50          9.44e-11         4.57e-09         2.35e-11
      W2           570 / 1280              50          2.13e-10         7.01e-09         2.02e-11
      b2            10 / 10                10          3.70e-11         1.52e-10         9.41e-12

  coefficients contrôlés                       160
  ÉCART RELATIF MAXIMAL SUR LES 160            7.013e-09
  écart relatif médian sur les 160             1.192e-10
  écart ABSOLU maximal sur les 160             2.354e-11

  -- Les dérivées nulles le sont aussi par différences finies --------------
  coefficients de dérivée analytique nulle contrôlés   150
  dont la différence finie vaut exactement zéro        150

Lecture

L'écart relatif maximal vaut $7{,}0\cdot 10^{-9}$ sur $160$ coefficients, et c'est le juge que le chapitre 3 a posé : les identités donnent, à huit chiffres significatifs près, ce que donne la définition même de la dérivée.
Le tirage est restreint aux dérivées non nulles, et c'est délibéré : la mesure 8 montre que $89{,}32\,\%$ des coefficients de $W^{[1]}$ ont une dérivée exactement nulle, et les tirer au hasard dans ce bloc ferait passer le contrôle neuf fois sur dix sans rien contrôler.
Les dérivées nulles sont contrôlées à part, et elles le sont aussi numériquement, puisque $150$ coefficients sur $150$ donnent une différence finie exactement nulle. Ce n'est pas une coïncidence : perturber un poids qui part d'un neurone éteint ne change pas la sortie du réseau, donc pas la perte.
$b^{[2]}$ est le seul bloc exhaustif, ses dix coefficients étant tous contrôlés sans qu'aucun soit tiré, et son écart maximal de $1{,}5\cdot 10^{-10}$ est aussi le plus petit des quatre.

D'où vient le peu qui reste

L'écart absolu ne dépend pas de la dérivée · mesure 2, suite

  |dérivée| médiane des 160 coefficients contrôlés   0.0448
  |dérivée| du coefficient d'écart relatif maximal    2.35e-03
  écart ABSOLU médian, dérivées sous la médiane       4.63e-12
  écart ABSOLU médian, dérivées au-dessus             5.68e-12
  écart RELATIF médian, dérivées sous la médiane      3.19e-10
  écart RELATIF médian, dérivées au-dessus            4.91e-11
  plancher d'annulation, eps_machine x l / (2 eps)    1.56e-11

Lecture

L'écart absolu médian est le même de part et d'autre, $4{,}6\cdot 10^{-12}$ pour les petites dérivées et $5{,}7\cdot 10^{-12}$ pour les grandes : il ne dépend pas de la dérivée qu'on mesure.
L'écart relatif, lui, varie d'un facteur $6{,}5$ , $3{,}2\cdot 10^{-10}$ pour les petites dérivées contre $4{,}9\cdot 10^{-11}$ pour les grandes, parce que c'est le même écart absolu divisé par un dénominateur plus petit.
La cause est nommée et chiffrée : $\ell\approx 1{,}41$ est calculée à $\varepsilon_{\text{machine}}\approx 2{,}2\cdot 10^{-16}$ près, et la soustraction de deux valeurs voisines divisée par $2\varepsilon=2\cdot 10^{-5}$ amplifie cette incertitude d'un facteur $5\cdot 10^{4}$ . Le plancher vaut $1{,}56\cdot 10^{-11}$ : les écarts absolus médians sont en dessous d'un facteur trois, et les maximaux du même ordre que lui.
Ce n'est donc pas un défaut de l'algorithme mais une propriété de la mesure, et le coefficient qui affiche le plus grand écart relatif a une dérivée de $2{,}35\cdot 10^{-3}$ , dix-neuf fois plus petite que la médiane $0{,}0448$ .

Ce que l'algorithme économise

Le coût comparé · cours/lecon4/mesures.py, mesure 7

  -- Le compte des propagations, qui ne dépend d'aucune machine ------------
  coefficients du réseau                              101770
  différences finies centrées, propagations avant     203540
  rétropropagation, propagations avant                1
  rétropropagation, propagations arrière              1
  rapport des propagations avant                      203540

  -- Le temps unitaire, meilleur de trois séries de 2 000 appels -----------
  une propagation avant seule                    226.4 us
  un gradient complet par rétropropagation       2384.1 us

  -- Le même gradient par différences finies -------------------------------
  estimation, 203540 x le temps d'une propagation   46.1 s
  mesure réelle de la boucle complète            42.9 s
  écart entre l'estimation et la mesure          8 %

  -- Le rapport ------------------------------------------------------------
  différences finies / rétropropagation, estimé  19329
  différences finies / rétropropagation, mesuré  17975

Lecture

Le nombre qui compte est le premier, $203\,540$ propagations avant contre une seule, et il ne dépend ni de la machine, ni du langage, ni de la charge : c'est $2p$ contre $1$ , et il vaudrait $2\,000$ sur un réseau de mille coefficients comme il vaut $203\,540$ sur celui-ci.
Les durées dépendent en revanche de la machine et de sa charge, et celles reproduites ici viennent d'une exécution sur une machine chargée : elles ne valent pas comme mesure de performance, seulement comme ordre de grandeur.
L'estimation $2p\times t_{\text{avant}}$ et la mesure réelle de la boucle s'accordent à $8\,\%$ , ce qui confirme que la boucle de différences finies ne fait rien d'autre que $203\,540$ propagations avant.
Le rapport mesuré, $\approx 1{,}8\cdot 10^{4}$ , est plus petit que $203\,540$ parce qu'une passe arrière n'est pas gratuite : elle refait de l'algèbre, dont deux produits extérieurs. C'est un facteur constant, et non un facteur qui croît avec $p$ .

Vérification rapide n° 48

Sur les $160$ coefficients contrôlés, l'écart absolu médian vaut $4{,}63\cdot 10^{-12}$ pour les dérivées sous la médiane et $5{,}68\cdot 10^{-12}$ pour celles au-dessus. L'écart relatif médian, lui, vaut $3{,}19\cdot 10^{-10}$ contre $4{,}91\cdot 10^{-11}$ .

a
Pourquoi le rapport s'inverse-t-il d'une ligne à l'autre ? Répondre en écrivant la définition de l'écart relatif.
b
Le plancher d'annulation vaut $\varepsilon_{\text{machine}}\,\ell/(2\varepsilon)=1{,}56\cdot 10^{-11}$ . Que deviendrait-il si l'on prenait $\varepsilon=10^{-8}$ au lieu de $10^{-5}$ , et est-ce une bonne idée ?

Aucune réponse à cliquer : il y a un calcul à faire.

Démonstration8 min

L'algorithme, et sa vérification

L'algorithme complet, et la vérification qu'il calcule bien ce qu'il prétend calculer.

Le compte du haut est celui de la formule (4.1), deux propagations par coefficient ; celui du bas est ce que l'algorithme des pages 3 à 9 demande.

Ce rapport ne dépend ni de la machine, ni du langage, ni de la charge : les durées de la fin de page, elles, en dépendent toutes.

L'aller

\mathbf{z}^{[1]}=W^{[1]}\mathbf{x}+\mathbf{b}^{[1]},\quad \mathbf{a}^{[1]}=\mathrm{ReLU}\big(\mathbf{z}^{[1]}\big),\quad \mathbf{z}^{[2]}=W^{[2]}\mathbf{a}^{[1]}+\mathbf{b}^{[2]},\quad \mathbf{a}^{[2]}=\mathrm{softmax}\big(\mathbf{z}^{[2]}\big)

(4.12)

Rien de neuf : c'est le réseau du chapitre 2. Ce qui est neuf, c'est qu'on garde

\mathbf{x}

\mathbf{z}^{[1]}

\mathbf{a}^{[1]}

\mathbf{a}^{[2]}

Le retour

\begin{aligned}\boldsymbol{\delta}^{[2]}&=\mathbf{a}^{[2]}-\mathbf{y} &&(10\times 1)\\ \mathrm{grad}_{\mathbf{b}^{[2]}}\,\ell&=\boldsymbol{\delta}^{[2]} &&(10\times 1)\\ \mathrm{grad}_{W^{[2]}}\,\ell&=\boldsymbol{\delta}^{[2]}\big(\mathbf{a}^{[1]}\big)^{\mathsf{T}} &&(10\times 128)\\ \boldsymbol{\delta}^{[1]}&=\Big[\big(W^{[2]}\big)^{\mathsf{T}}\boldsymbol{\delta}^{[2]}\Big]\odot\mathrm{ReLU}'\big(\mathbf{z}^{[1]}\big) &&(128\times 1)\\ \mathrm{grad}_{\mathbf{b}^{[1]}}\,\ell&=\boldsymbol{\delta}^{[1]} &&(128\times 1)\\ \mathrm{grad}_{W^{[1]}}\,\ell&=\boldsymbol{\delta}^{[1]}\mathbf{x}^{\mathsf{T}} &&(128\times 784)\end{aligned}

(4.13)

PythonL'algorithme, tel qu'il tourne dans cours/lecon4/mesures.py

1def avant(theta, x):                     # x : (784,)2    z1 = theta["W1"] @ x + theta["b1"]   # (128, 784)(784,) -> (128,)3    a1 = np.maximum(z1, 0.0)             # (128,)4    z2 = theta["W2"] @ a1 + theta["b2"]  # (10, 128)(128,)  -> (10,)5    a2 = softmax(z2)                     # (10,)6    return {"x": x, "z1": z1, "a1": a1, "z2": z2, "a2": a2}7 8def arriere(theta, cache, c):9    d2   = cache["a2"] - onehot(c)              # (10,)     proposition 110    g_W2 = np.outer(d2, cache["a1"])            # (10, 128) proposition 411    g_b2 = d2                                   # (10,)     proposition 312    g_a1 = theta["W2"].T @ d2                   # (128,)    proposition 613    d1   = g_a1 * (cache["z1"] > 0.0)           # (128,)    formule 4.914    g_W1 = np.outer(d1, cache["x"])             # (128, 784) proposition 415    g_b1 = d1                                   # (128,)     proposition 316    return {"W1": g_W1, "b1": g_b1, "W2": g_W2, "b2": g_b2}

Ce qu'il faut garder entre l'aller et le retour

Quantité gardée	Taille	Employée par
$\mathbf{x}$	$784$	$\mathrm{grad}_{W^{[1]}}\,\ell=\boldsymbol{\delta}^{[1]}\mathbf{x}^{\mathsf{T}}$
$\mathbf{z}^{[1]}$	$128$	$\mathrm{ReLU}'(\mathbf{z}^{[1]})$ , la porte
$\mathbf{a}^{[1]}$	$128$	$\mathrm{grad}_{W^{[2]}}\,\ell=\boldsymbol{\delta}^{[2]}(\mathbf{a}^{[1]})^{\mathsf{T}}$
$\mathbf{a}^{[2]}$	$10$	$\boldsymbol{\delta}^{[2]}=\mathbf{a}^{[2]}-\mathbf{y}$

La vérification

160 dérivées confrontées aux différences finies · cours/lecon4/mesures.py, mesure 2

  epsilon = 1e-05
  50 coefficients tirés dans chaque bloc PARMI CEUX DE DÉRIVÉE NON NULLE.

      bloc    non nuls / total    contrôlés   écart rel. médian   écart rel. max   écart abs. max
      W1         10716 / 100352            50          9.87e-11         6.62e-09         1.10e-11
      b1            57 / 128               50          9.44e-11         4.57e-09         2.35e-11
      W2           570 / 1280              50          2.13e-10         7.01e-09         2.02e-11
      b2            10 / 10                10          3.70e-11         1.52e-10         9.41e-12

  coefficients contrôlés                       160
  ÉCART RELATIF MAXIMAL SUR LES 160            7.013e-09
  écart relatif médian sur les 160             1.192e-10
  écart ABSOLU maximal sur les 160             2.354e-11

  -- Les dérivées nulles le sont aussi par différences finies --------------
  coefficients de dérivée analytique nulle contrôlés   150
  dont la différence finie vaut exactement zéro        150

Lecture

L'écart relatif maximal vaut $7{,}0\cdot 10^{-9}$ sur $160$ coefficients, et c'est le juge que le chapitre 3 a posé : les identités donnent, à huit chiffres significatifs près, ce que donne la définition même de la dérivée.
Le tirage est restreint aux dérivées non nulles, et c'est délibéré : la mesure 8 montre que $89{,}32\,\%$ des coefficients de $W^{[1]}$ ont une dérivée exactement nulle, et les tirer au hasard dans ce bloc ferait passer le contrôle neuf fois sur dix sans rien contrôler.
Les dérivées nulles sont contrôlées à part, et elles le sont aussi numériquement, puisque $150$ coefficients sur $150$ donnent une différence finie exactement nulle. Ce n'est pas une coïncidence : perturber un poids qui part d'un neurone éteint ne change pas la sortie du réseau, donc pas la perte.
$b^{[2]}$ est le seul bloc exhaustif, ses dix coefficients étant tous contrôlés sans qu'aucun soit tiré, et son écart maximal de $1{,}5\cdot 10^{-10}$ est aussi le plus petit des quatre.

D'où vient le peu qui reste

L'écart absolu ne dépend pas de la dérivée · mesure 2, suite

  |dérivée| médiane des 160 coefficients contrôlés   0.0448
  |dérivée| du coefficient d'écart relatif maximal    2.35e-03
  écart ABSOLU médian, dérivées sous la médiane       4.63e-12
  écart ABSOLU médian, dérivées au-dessus             5.68e-12
  écart RELATIF médian, dérivées sous la médiane      3.19e-10
  écart RELATIF médian, dérivées au-dessus            4.91e-11
  plancher d'annulation, eps_machine x l / (2 eps)    1.56e-11

Lecture

L'écart absolu médian est le même de part et d'autre, $4{,}6\cdot 10^{-12}$ pour les petites dérivées et $5{,}7\cdot 10^{-12}$ pour les grandes : il ne dépend pas de la dérivée qu'on mesure.
L'écart relatif, lui, varie d'un facteur $6{,}5$ , $3{,}2\cdot 10^{-10}$ pour les petites dérivées contre $4{,}9\cdot 10^{-11}$ pour les grandes, parce que c'est le même écart absolu divisé par un dénominateur plus petit.
La cause est nommée et chiffrée : $\ell\approx 1{,}41$ est calculée à $\varepsilon_{\text{machine}}\approx 2{,}2\cdot 10^{-16}$ près, et la soustraction de deux valeurs voisines divisée par $2\varepsilon=2\cdot 10^{-5}$ amplifie cette incertitude d'un facteur $5\cdot 10^{4}$ . Le plancher vaut $1{,}56\cdot 10^{-11}$ : les écarts absolus médians sont en dessous d'un facteur trois, et les maximaux du même ordre que lui.
Ce n'est donc pas un défaut de l'algorithme mais une propriété de la mesure, et le coefficient qui affiche le plus grand écart relatif a une dérivée de $2{,}35\cdot 10^{-3}$ , dix-neuf fois plus petite que la médiane $0{,}0448$ .

Ce que l'algorithme économise

Le coût comparé · cours/lecon4/mesures.py, mesure 7

  -- Le compte des propagations, qui ne dépend d'aucune machine ------------
  coefficients du réseau                              101770
  différences finies centrées, propagations avant     203540
  rétropropagation, propagations avant                1
  rétropropagation, propagations arrière              1
  rapport des propagations avant                      203540

  -- Le temps unitaire, meilleur de trois séries de 2 000 appels -----------
  une propagation avant seule                    226.4 us
  un gradient complet par rétropropagation       2384.1 us

  -- Le même gradient par différences finies -------------------------------
  estimation, 203540 x le temps d'une propagation   46.1 s
  mesure réelle de la boucle complète            42.9 s
  écart entre l'estimation et la mesure          8 %

  -- Le rapport ------------------------------------------------------------
  différences finies / rétropropagation, estimé  19329
  différences finies / rétropropagation, mesuré  17975

Lecture

Le nombre qui compte est le premier, $203\,540$ propagations avant contre une seule, et il ne dépend ni de la machine, ni du langage, ni de la charge : c'est $2p$ contre $1$ , et il vaudrait $2\,000$ sur un réseau de mille coefficients comme il vaut $203\,540$ sur celui-ci.
Les durées dépendent en revanche de la machine et de sa charge, et celles reproduites ici viennent d'une exécution sur une machine chargée : elles ne valent pas comme mesure de performance, seulement comme ordre de grandeur.
L'estimation $2p\times t_{\text{avant}}$ et la mesure réelle de la boucle s'accordent à $8\,\%$ , ce qui confirme que la boucle de différences finies ne fait rien d'autre que $203\,540$ propagations avant.
Le rapport mesuré, $\approx 1{,}8\cdot 10^{4}$ , est plus petit que $203\,540$ parce qu'une passe arrière n'est pas gratuite : elle refait de l'algèbre, dont deux produits extérieurs. C'est un facteur constant, et non un facteur qui croît avec $p$ .

Vérification rapide n° 48

a
Pourquoi le rapport s'inverse-t-il d'une ligne à l'autre ? Répondre en écrivant la définition de l'écart relatif.
b
Le plancher d'annulation vaut $\varepsilon_{\text{machine}}\,\ell/(2\varepsilon)=1{,}56\cdot 10^{-11}$ . Que deviendrait-il si l'on prenait $\varepsilon=10^{-8}$ au lieu de $10^{-5}$ , et est-ce une bonne idée ?

Aucune réponse à cliquer : il y a un calcul à faire.