Démonstration8 min

Le lot complet, et le mini-lot

Ce que coûte un pas calculé sur tout le jeu, et ce que le mini-lot y change.

Le risque empirique est une moyenne sur tout le jeu, et son gradient aussi. La descente honnête calcule cette somme entière à chaque pas. Mesurons ce qu'elle coûte, et ce qu'elle rapporte.

\mathcal{L}_{\mathcal{D}}(\theta)=\frac{1}{N}\sum_{n=1}^{N}\ell\big(\theta;x^{(n)},y^{(n)}\big), \qquad \operatorname{grad}_{\theta}\mathcal{L}_{\mathcal{D}}=\frac{1}{N}\sum_{n=1}^{N}\operatorname{grad}_{\theta}\ell^{(n)}

L'obstacle, prouvé

python cours/lecon3/experiences.py E2

  N = 60000   B = 64   p = 101770

  Cout d'UNE mise a jour (mediane, apres passe a blanc) :
    lot COMPLET     6049.4 ms   soit  100.82 us par exemple
    MINI-LOT          45.2 ms   soit  705.48 us par exemple

    Par exemple, le lot complet est 7.0 x PLUS efficace :
    une grande multiplication de matrices exploite mieux le cache.
    Et pourtant il ne produit qu'UNE mise a jour, contre 937.

  Ce que chacun obtient pour UN passage sur les 60000 exemples, eta = 0.5 :
    methode             mises a jour    duree   perte test   precision
    lot complet                    1    7.32s       2.3103      0.1258
    mini-lots B=64               937   29.92s       0.2546      0.9273

Lecture

Le lot complet est plus efficace par exemple : $100{,}82\ \mu s$ contre $705{,}48\ \mu s$ , un facteur $7{,}0$ en sa faveur. Une grande multiplication de matrices amortit mieux les accès mémoire. Le grief contre lui n'est donc pas le coût arithmétique.
Le grief est ailleurs : pour le même parcours des données, il produit une mise à jour au lieu de 937.
Le résultat est sans appel : $0{,}1258$ de précision de test, contre $0{,}1000$ pour un tirage au hasard entre dix classes. Après avoir vu les 60 000 exemples, le réseau n'a rien appris.

Le cahier des charges

Ce que la solution devra satisfaire

	Critère	Pourquoi
(C1)	Le coût d'une mise à jour ne doit pas dépendre de $N$	sinon le nombre de mises à jour par heure s'effondre quand le jeu grandit
(C2)	La direction utilisée doit être en moyenne le gradient complet	sinon on optimise autre chose, et on ne sait plus quoi
(C3)	L'erreur commise doit être contrôlable par un réglage	sinon on ne peut pas arbitrer entre vitesse et précision
(C4)	Le coût mémoire ne doit pas dépendre de $N$	$60\,000\times784$ en flottants 64 bits fait déjà 376 Mo

Le candidat naïf, mis en échec

Le candidat le plus simple répond à (C1) et (C4) sans effort : puisque le lot complet coûte cher, tirons une fois pour toutes un petit sous-échantillon, et travaillons dessus. C'est le premier réflexe, et il faut le tuer avec une mesure, pas avec un argument.

python cours/lecon3/experiences.py E3 · 937 mises à jour, coût identique

  sous-echantillon fige : 937 mises a jour, meme cout de calcul
    sur les 64 exemples figes : perte 0.0036   precision 1.0000
    sur le jeu de test        : perte 1.3899   precision 0.5990

  mini-lots frais : 937 mises a jour, meme cout de calcul
    sur les 64 exemples figes : perte 0.3925   precision 0.9062
    sur le jeu de test        : perte 0.2664   precision 0.9208

  Ecart de precision de test : 0.9208 - 0.5990 = +0.3218

Lecture

Le candidat figé atteint $1{,}0000$ sur ses propres 64 exemples, perte $0{,}0036$ : il les a appris par cœur. Et $0{,}5990$ sur le test.
Le détail qui tranche : les mini-lots frais font moins bien que le figé sur ces 64 exemples précis ( $0{,}9062$ contre $1{,}0000$ ) et beaucoup mieux partout ailleurs.
Le candidat naïf viole (C2) : la direction qu'il suit est le gradient exact d'une autre fonction, celle qui ne porte que sur ses 64 exemples.

Deux panneaux. À gauche, la précision de test du lot complet sur six passages : elle part de 0,1258, reste sous 0,25 pendant trois passages, et atteint 0,6132 au sixième. À droite, deux courbes à nombre de mises à jour égal : les mini-lots frais montent à 0,92, le sous-échantillon figé plafonne à 0,60 dès la deux-centième mise à jour. — (a) Le lot complet finit par apprendre : il lui faut simplement 937 fois plus de passages. (b) Figer le lot coûte 0,3218 de précision, et la courbe est plate dès le début : ce n'est pas de la lenteur, c'est un plafond.

La solution, dérivée du cahier des charges

(C1) et (C4) imposent un lot de taille $B$ fixe, indépendante de $N$ . (C2) impose que ce lot soit retiré à chaque pas, et de façon uniforme. Cela suffit à tout démontrer.

DérivationLe gradient de mini-lot est sans biais

Hypothèses

$\mathcal{B}$ est tiré uniformément parmi les parties de taille $B$ de $\{1,\dots,N\}$
$g_{\mathcal{B}}$ est la moyenne des gradients individuels sur $\mathcal{B}$

Point de départ

g_{\mathcal{B}}=\frac{1}{B}\sum_{n=1}^{N}\mathbb{1}\{n\in\mathcal{B}\}\ \operatorname{grad}\ell^{(n)}

Propriétés utilisées

La linéarité de l'espérance
La symétrie du tirage uniforme : tous les indices jouent le même rôle

Étapes

Le tirage étant uniforme, la probabilité d'appartenance ne dépend pas de $n$ . Comme la somme de ces probabilités vaut l'espérance du cardinal, c'est-à-dire $B$ :
$\sum_{n=1}^{N}\mathbb{P}(n\in\mathcal{B})=B \quad\Longrightarrow\quad \mathbb{P}(n\in\mathcal{B})=\frac{B}{N}$
symétrie, puis comptage
Par linéarité de l'espérance, appliquée à la somme finie :
$\mathbb{E}[g_{\mathcal{B}}]=\frac{1}{B}\sum_{n=1}^{N}\frac{B}{N}\operatorname{grad}\ell^{(n)}=\frac{1}{N}\sum_{n=1}^{N}\operatorname{grad}\ell^{(n)}$
linéarité de l'espérance ; les facteurs B se simplifient

Résultat

\mathbb{E}\big[g_{\mathcal{B}}(\theta)\big]=\operatorname{grad}_{\theta}\mathcal{L}_{\mathcal{D}}(\theta) \quad \text{pour tout } \theta

Interprétation

Le critère (C2) est satisfait exactement, pas approximativement, et pour toute taille de lot, y compris $B=1$ . Le mini-lot ne donne pas « à peu près » la bonne direction : il donne une direction dont la moyenne est la bonne. C'est ce qui autorise à faire beaucoup de pas médiocres plutôt qu'un pas parfait.

DérivationSon écart quadratique décroît en un sur B

Hypothèses

Tirage avec remise : les $B$ tirages sont indépendants et de même loi
$s^{2}$ est la moyenne des carrés des écarts entre gradients individuels et gradient complet

Point de départ

g_{\mathcal{B}}-\operatorname{grad}\mathcal{L}_{\mathcal{D}}=\frac{1}{B}\sum_{i=1}^{B}v_i, \qquad v_i=\operatorname{grad}\ell^{(n_i)}-\operatorname{grad}\mathcal{L}_{\mathcal{D}}

Propriétés utilisées

Les $v_i$ sont de moyenne nulle, par la dérivation précédente
L'indépendance des tirages annule les termes croisés

Étapes

On développe le carré de la norme de la moyenne :
$\mathbb{E}\Big\|\frac{1}{B}\sum_{i=1}^{B}v_i\Big\|^{2}=\frac{1}{B^{2}}\sum_{i=1}^{B}\sum_{j=1}^{B}\mathbb{E}\langle v_i,v_j\rangle$
bilinéarité du produit scalaire
Pour $i\neq j$ , l'indépendance et la moyenne nulle annulent le terme. Il ne reste que les $B$ termes diagonaux, chacun égal à $s^2$ .
$=\frac{1}{B^{2}}\sum_{i=1}^{B}\mathbb{E}\|v_i\|^{2}=\frac{B\,s^{2}}{B^{2}}=\frac{s^{2}}{B}$
indépendance et moyenne nulle

Résultat

\big\|g_{\mathcal{B}}-\operatorname{grad}\mathcal{L}_{\mathcal{D}}\big\|_{\text{RMS}}=\frac{s}{\sqrt{B}}

Interprétation

Le critère (C3) est satisfait, et le réglage est $B$ . Mais le rendement est décroissant : quadrupler $B$ ne divise l'erreur que par deux, alors qu'il quadruple le coût. C'est l'argument quantitatif en faveur des petits lots.

Ce que ce résultat ne dit pas

La preuve suppose un tirage avec remise. Sans remise, s'ajoute le facteur de population finie $\frac{N-B}{N-1}$ , compris entre $0{,}983$ et $1$ pour $N=60\,000$ et $B\le1024$ : indétectable dans nos mesures, mais il existe.

python cours/lecon3/experiences.py E4 · 200 tirages par taille de lot

  ||grad complet|| = 0.863256   (reference)

       B   ||moyenne - complet||   ecart quadratique moyen   x sqrt(B)
       1                0.334587                  5.876873      5.8769
       4                0.303096                  2.923644      5.8473
      16                0.122570                  1.455154      5.8206
      64                0.062213                  0.725300      5.8024
     256                0.024452                  0.363179      5.8109
    1024                0.014276                  0.186764      5.9764

Lecture

Colonne 2, à ne pas surinterpréter. Elle tend vers zéro, mais ce n'est pas un biais : la proposition dit que le biais est exactement nul. C'est l'erreur résiduelle de Monte-Carlo sur une moyenne de 200 tirages, qui vaut environ l'écart divisé par $\sqrt{200}$ . Pour $B=64$ : $0{,}7253/\sqrt{200}=0{,}0513$ , et l'on mesure $0{,}0622$ . Même ordre.
Colonne 4 : l'écart multiplié par $\sqrt{B}$ vaut $5{,}88$ , $5{,}85$ , $5{,}82$ , $5{,}80$ , $5{,}81$ , $5{,}98$ sur trois ordres de grandeur de $B$ . La loi en $1/\sqrt{B}$ est vérifiée, et la constante $s\approx5{,}8$ est mesurée.
La remontée à $B=1024$ est du bruit : avec 200 répétitions, l'erreur type relative est d'environ $5\,\%$ , et l'écart observé est de $3\,\%$ .
Le chiffre à retenir : $s\approx5{,}8$ pour un gradient complet de norme $0{,}863$ . Le bruit d'un gradient à un seul exemple est près de sept fois plus grand que le signal, et pourtant cela fonctionne, parce que ce bruit est de moyenne nulle et que les pas sont nombreux.

Verdict

Candidat	(C1)	(C2)	(C3)	(C4)	Verdict
Lot complet	✗	✓	✗	✗	rejeté : $0{,}1258$ après un passage
Sous-échantillon figé	✓	✗	✗	✓	rejeté : $0{,}5990$ contre $0{,}9208$
Mini-lot retiré à chaque pas	✓	✓	✓	✓	retenu

(C1) coût borné, mesuré plus haut · (C2) sans biais, prouvé · (C3) erreur réglable en s sur racine de B, mesurée · (C4) mémoire bornée, par construction.

\theta_{t+1}=\theta_{t}-\eta\,\frac{1}{B}\sum_{n\in\mathcal{B}_t}\operatorname{grad}_{\theta}\ell^{(n)}(\theta_t), \qquad \mathcal{B}_t \text{ tiré uniformément}, \ |\mathcal{B}_t|=B

(2)

La descente de gradient stochastique par mini-lots. Le mot « stochastique » ne désigne pas une approximation grossière : il désigne un estimateur sans biais dont on contrôle la variance.

Vérification rapide n° 10

On mesure $s\approx5{,}80$ et un gradient complet de norme $0{,}863$ .

a
Quelle taille de lot faudrait-il pour que l'écart quadratique moyen tombe à $10\,\%$ de la norme du gradient complet ? Donne le calcul.
b
Sachant qu'un exemple coûte environ $100\ \mu s$ en lot complet, combien de temps coûterait alors une mise à jour ? Compare aux 45 ms du mini-lot à $B=64$ , et conclus.

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

Démonstration8 min

Le lot complet, et le mini-lot

Ce que coûte un pas calculé sur tout le jeu, et ce que le mini-lot y change.

Le risque empirique est une moyenne sur tout le jeu, et son gradient aussi. La descente honnête calcule cette somme entière à chaque pas. Mesurons ce qu'elle coûte, et ce qu'elle rapporte.

\mathcal{L}_{\mathcal{D}}(\theta)=\frac{1}{N}\sum_{n=1}^{N}\ell\big(\theta;x^{(n)},y^{(n)}\big), \qquad \operatorname{grad}_{\theta}\mathcal{L}_{\mathcal{D}}=\frac{1}{N}\sum_{n=1}^{N}\operatorname{grad}_{\theta}\ell^{(n)}

L'obstacle, prouvé

python cours/lecon3/experiences.py E2

  N = 60000   B = 64   p = 101770

  Cout d'UNE mise a jour (mediane, apres passe a blanc) :
    lot COMPLET     6049.4 ms   soit  100.82 us par exemple
    MINI-LOT          45.2 ms   soit  705.48 us par exemple

    Par exemple, le lot complet est 7.0 x PLUS efficace :
    une grande multiplication de matrices exploite mieux le cache.
    Et pourtant il ne produit qu'UNE mise a jour, contre 937.

  Ce que chacun obtient pour UN passage sur les 60000 exemples, eta = 0.5 :
    methode             mises a jour    duree   perte test   precision
    lot complet                    1    7.32s       2.3103      0.1258
    mini-lots B=64               937   29.92s       0.2546      0.9273

Lecture

Le lot complet est plus efficace par exemple : $100{,}82\ \mu s$ contre $705{,}48\ \mu s$ , un facteur $7{,}0$ en sa faveur. Une grande multiplication de matrices amortit mieux les accès mémoire. Le grief contre lui n'est donc pas le coût arithmétique.
Le grief est ailleurs : pour le même parcours des données, il produit une mise à jour au lieu de 937.
Le résultat est sans appel : $0{,}1258$ de précision de test, contre $0{,}1000$ pour un tirage au hasard entre dix classes. Après avoir vu les 60 000 exemples, le réseau n'a rien appris.

Le cahier des charges

Ce que la solution devra satisfaire

	Critère	Pourquoi
(C1)	Le coût d'une mise à jour ne doit pas dépendre de $N$	sinon le nombre de mises à jour par heure s'effondre quand le jeu grandit
(C2)	La direction utilisée doit être en moyenne le gradient complet	sinon on optimise autre chose, et on ne sait plus quoi
(C3)	L'erreur commise doit être contrôlable par un réglage	sinon on ne peut pas arbitrer entre vitesse et précision
(C4)	Le coût mémoire ne doit pas dépendre de $N$	$60\,000\times784$ en flottants 64 bits fait déjà 376 Mo

Le candidat naïf, mis en échec

python cours/lecon3/experiences.py E3 · 937 mises à jour, coût identique

  sous-echantillon fige : 937 mises a jour, meme cout de calcul
    sur les 64 exemples figes : perte 0.0036   precision 1.0000
    sur le jeu de test        : perte 1.3899   precision 0.5990

  mini-lots frais : 937 mises a jour, meme cout de calcul
    sur les 64 exemples figes : perte 0.3925   precision 0.9062
    sur le jeu de test        : perte 0.2664   precision 0.9208

  Ecart de precision de test : 0.9208 - 0.5990 = +0.3218

Lecture

Le candidat figé atteint $1{,}0000$ sur ses propres 64 exemples, perte $0{,}0036$ : il les a appris par cœur. Et $0{,}5990$ sur le test.
Le détail qui tranche : les mini-lots frais font moins bien que le figé sur ces 64 exemples précis ( $0{,}9062$ contre $1{,}0000$ ) et beaucoup mieux partout ailleurs.
Le candidat naïf viole (C2) : la direction qu'il suit est le gradient exact d'une autre fonction, celle qui ne porte que sur ses 64 exemples.

La solution, dérivée du cahier des charges

(C1) et (C4) imposent un lot de taille $B$ fixe, indépendante de $N$ . (C2) impose que ce lot soit retiré à chaque pas, et de façon uniforme. Cela suffit à tout démontrer.

DérivationLe gradient de mini-lot est sans biais

Hypothèses

$\mathcal{B}$ est tiré uniformément parmi les parties de taille $B$ de $\{1,\dots,N\}$
$g_{\mathcal{B}}$ est la moyenne des gradients individuels sur $\mathcal{B}$

Point de départ

g_{\mathcal{B}}=\frac{1}{B}\sum_{n=1}^{N}\mathbb{1}\{n\in\mathcal{B}\}\ \operatorname{grad}\ell^{(n)}

Propriétés utilisées

La linéarité de l'espérance
La symétrie du tirage uniforme : tous les indices jouent le même rôle

Étapes

Le tirage étant uniforme, la probabilité d'appartenance ne dépend pas de $n$ . Comme la somme de ces probabilités vaut l'espérance du cardinal, c'est-à-dire $B$ :
$\sum_{n=1}^{N}\mathbb{P}(n\in\mathcal{B})=B \quad\Longrightarrow\quad \mathbb{P}(n\in\mathcal{B})=\frac{B}{N}$
symétrie, puis comptage
Par linéarité de l'espérance, appliquée à la somme finie :
$\mathbb{E}[g_{\mathcal{B}}]=\frac{1}{B}\sum_{n=1}^{N}\frac{B}{N}\operatorname{grad}\ell^{(n)}=\frac{1}{N}\sum_{n=1}^{N}\operatorname{grad}\ell^{(n)}$
linéarité de l'espérance ; les facteurs B se simplifient

Résultat

\mathbb{E}\big[g_{\mathcal{B}}(\theta)\big]=\operatorname{grad}_{\theta}\mathcal{L}_{\mathcal{D}}(\theta) \quad \text{pour tout } \theta

Interprétation

DérivationSon écart quadratique décroît en un sur B

Hypothèses

Tirage avec remise : les $B$ tirages sont indépendants et de même loi
$s^{2}$ est la moyenne des carrés des écarts entre gradients individuels et gradient complet

Point de départ

g_{\mathcal{B}}-\operatorname{grad}\mathcal{L}_{\mathcal{D}}=\frac{1}{B}\sum_{i=1}^{B}v_i, \qquad v_i=\operatorname{grad}\ell^{(n_i)}-\operatorname{grad}\mathcal{L}_{\mathcal{D}}

Propriétés utilisées

Les $v_i$ sont de moyenne nulle, par la dérivation précédente
L'indépendance des tirages annule les termes croisés

Étapes

On développe le carré de la norme de la moyenne :
$\mathbb{E}\Big\|\frac{1}{B}\sum_{i=1}^{B}v_i\Big\|^{2}=\frac{1}{B^{2}}\sum_{i=1}^{B}\sum_{j=1}^{B}\mathbb{E}\langle v_i,v_j\rangle$
bilinéarité du produit scalaire
Pour $i\neq j$ , l'indépendance et la moyenne nulle annulent le terme. Il ne reste que les $B$ termes diagonaux, chacun égal à $s^2$ .
$=\frac{1}{B^{2}}\sum_{i=1}^{B}\mathbb{E}\|v_i\|^{2}=\frac{B\,s^{2}}{B^{2}}=\frac{s^{2}}{B}$
indépendance et moyenne nulle

Résultat

\big\|g_{\mathcal{B}}-\operatorname{grad}\mathcal{L}_{\mathcal{D}}\big\|_{\text{RMS}}=\frac{s}{\sqrt{B}}

Interprétation

Ce que ce résultat ne dit pas

La preuve suppose un tirage avec remise. Sans remise, s'ajoute le facteur de population finie $\frac{N-B}{N-1}$ , compris entre $0{,}983$ et $1$ pour $N=60\,000$ et $B\le1024$ : indétectable dans nos mesures, mais il existe.

python cours/lecon3/experiences.py E4 · 200 tirages par taille de lot

  ||grad complet|| = 0.863256   (reference)

       B   ||moyenne - complet||   ecart quadratique moyen   x sqrt(B)
       1                0.334587                  5.876873      5.8769
       4                0.303096                  2.923644      5.8473
      16                0.122570                  1.455154      5.8206
      64                0.062213                  0.725300      5.8024
     256                0.024452                  0.363179      5.8109
    1024                0.014276                  0.186764      5.9764

Lecture

Colonne 2, à ne pas surinterpréter. Elle tend vers zéro, mais ce n'est pas un biais : la proposition dit que le biais est exactement nul. C'est l'erreur résiduelle de Monte-Carlo sur une moyenne de 200 tirages, qui vaut environ l'écart divisé par $\sqrt{200}$ . Pour $B=64$ : $0{,}7253/\sqrt{200}=0{,}0513$ , et l'on mesure $0{,}0622$ . Même ordre.
Colonne 4 : l'écart multiplié par $\sqrt{B}$ vaut $5{,}88$ , $5{,}85$ , $5{,}82$ , $5{,}80$ , $5{,}81$ , $5{,}98$ sur trois ordres de grandeur de $B$ . La loi en $1/\sqrt{B}$ est vérifiée, et la constante $s\approx5{,}8$ est mesurée.
La remontée à $B=1024$ est du bruit : avec 200 répétitions, l'erreur type relative est d'environ $5\,\%$ , et l'écart observé est de $3\,\%$ .
Le chiffre à retenir : $s\approx5{,}8$ pour un gradient complet de norme $0{,}863$ . Le bruit d'un gradient à un seul exemple est près de sept fois plus grand que le signal, et pourtant cela fonctionne, parce que ce bruit est de moyenne nulle et que les pas sont nombreux.

Verdict

Candidat	(C1)	(C2)	(C3)	(C4)	Verdict
Lot complet	✗	✓	✗	✗	rejeté : $0{,}1258$ après un passage
Sous-échantillon figé	✓	✗	✗	✓	rejeté : $0{,}5990$ contre $0{,}9208$
Mini-lot retiré à chaque pas	✓	✓	✓	✓	retenu

(C1) coût borné, mesuré plus haut · (C2) sans biais, prouvé · (C3) erreur réglable en s sur racine de B, mesurée · (C4) mémoire bornée, par construction.

\theta_{t+1}=\theta_{t}-\eta\,\frac{1}{B}\sum_{n\in\mathcal{B}_t}\operatorname{grad}_{\theta}\ell^{(n)}(\theta_t), \qquad \mathcal{B}_t \text{ tiré uniformément}, \ |\mathcal{B}_t|=B

(2)

La descente de gradient stochastique par mini-lots. Le mot « stochastique » ne désigne pas une approximation grossière : il désigne un estimateur sans biais dont on contrôle la variance.

Vérification rapide n° 10

On mesure $s\approx5{,}80$ et un gradient complet de norme $0{,}863$ .

a
Quelle taille de lot faudrait-il pour que l'écart quadratique moyen tombe à $10\,\%$ de la norme du gradient complet ? Donne le calcul.
b
Sachant qu'un exemple coûte environ $100\ \mu s$ en lot complet, combien de temps coûterait alors une mise à jour ? Compare aux 45 ms du mini-lot à $B=64$ , et conclus.

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