Démonstration10 min

Le plafond, et d'où il vient

Pourquoi ce premier modèle cesse de progresser, et pourquoi ce n'est pas un problème de réglage.

Le premier modèle se trompe huit cent sept fois sur dix mille, et il cesse de progresser très tôt. Ou bien il est mal réglé, et mieux l'entraîner suffirait, ou bien sa forme même lui interdit de faire mieux, et il faudrait alors en changer. Les deux se soignent si différemment qu'il vaut mieux savoir laquelle est vraie avant de dépenser un paramètre de plus. Laquelle est-ce ?

Le milieu est une entrée comme les autres, et le modèle la classe comme les autres. La paire est prise parmi les

982

images de

4

du jeu de test, dont

921

que les deux modèles lisent

4

, dans l'ordre des indices.

Ce qu'un modèle linéaire ne peut pas répondre

Ses dix scores $\mathbf{z}=W\mathbf{x}+\mathbf{b}$ dépendent de l'image par un produit matriciel et une addition, et pas davantage. L'usage appelle un tel modèle linéaire, bien que l'ajout de $\mathbf{b}$ le rende à proprement parler affine, et le cours garde ce nom d'usage.

Le $\mathrm{softmax}$ qui suit ne déplace pas la plus grande des dix coordonnées, donc il ne change pas la classe prédite : tout ce qui suit se lit sur $\mathbf{z}$ seul. Cela se voit sur $(6.3)$ , où les dix coordonnées se divisent par le même dénominateur, si bien que les comparer revient à comparer leurs numérateurs, et l'exponentielle étant croissante, à comparer les $z_{k}$ .

On note enfin $R_{c}$ l'ensemble des images que ce modèle range dans la classe $c$ . Les mesures qui suivent comptent les paires dont les deux images tombent dans la même région, et la démonstration les écrira $R_{k}$ , avec $k=c+1$ , pour indexer les coordonnées à partir de $1$ .

Deux $4$, leur milieu, et ce que le modèle linéaire en dit · cours/lecon2/mesures.py, section 5

      image de test n°115, classe 4
      image de test n°668, classe 4
      leur milieu ( x_115 + x_668 ) / 2

                            image 115   image 668   milieu
      MODELE 1, lineaire           4          4         4

Lecture

Le milieu est l'image moyenne des deux, pixel par pixel : $\tfrac{1}{2}(\mathbf{x}_{115}+\mathbf{x}_{668})\in[0,1]^{784}$ . C'est une entrée comme les autres, et le modèle la classe comme les autres.

Ce modèle peut-il réussir les trois, ou sa troisième réponse est-elle déjà fixée par les deux premières ?

La mesure ci-dessous le compare à un autre, appelé modèle 3 parce qu'il vient en troisième dans une série de quatre que la page 11 récapitule. Celui-là porte entre ses deux étapes de calcul une fonction que la page 9 construit et nomme $\mathrm{ReLU}$  ; ici, il ne sert qu'à montrer que le compte obtenu n'est pas nul par nature.

Entre deux images de la même classe, le modèle linéaire ne peut pas changer d'avis en chemin. Le réseau à ReLU, lui, le peut : c'est toute la différence entre les deux familles, et la page la démontre ensuite.

0:00 / 0:25

La question, mesurée sur $5\,000$ paires · cours/lecon2/mesures.py, section 5

    5000 paires d'images de MEME classe, 500 par classe,
    tirees dans les 10 000 images de test, graine 0.

  -- MODELE 1, lineaire ----------------------------------------------------
      paires dont les DEUX extremites sont dans R_c   4250 sur 5000
      parmi elles, milieu classe AILLEURS              0   (0.00 %)
      sur TOUTES les paires, milieu classe ailleurs    121   (2.42 %)

Lecture

Zéro sur $4\,250$ : chaque fois que les deux extrémités reçoivent la même classe, le milieu la reçoit aussi, sans une seule exception.
La dernière ligne quitte les $4\,250$ et compte sur les $5\,000$ paires de départ : $121$ fois, soit $2{,}42\,\%$ , le milieu reçoit une classe autre que celle des deux images qui l'encadrent. Ce n'est pas la même question que la ligne au-dessus, et ce compte ne contredit rien.
La graine $0$ fixe le tirage des paires, de sorte que deux exécutions comparent les mêmes images.
La troisième réponse est donc fixée par les deux premières, et un compte nul sur $4\,250$ tirages n'est pas un bon résultat mais la marque d'une contrainte. Il reste à dire laquelle.

D'où vient le zéro

Partie convexeconvex set: Une partie $C\subseteq\mathbb{R}^{d}$ telle que pour tous $u,v\in C$ et tout $t\in[0,1]$ , $(1-t)u+tv\in C$ . Le segment joignant deux points de $C$ reste entièrement dans $C$ .

Région de décisiondecision region: Pour $k\in[\![1,K]\!]$ , l'ensemble $R_{k}$ des entrées dont le score $z_{k}$ est au moins aussi grand que les neuf autres. Les inégalités y sont larges, si bien que deux régions se touchent sur les ex æquo écartés page 6 ; hors de ces frontières, $R_{k}$ est exactement l'ensemble des entrées classées $k-1$ . Comme le dénominateur de $(6.3)$ est le même pour les dix coordonnées et que l'exponentielle est croissante, $\arg\max_{k}a_{k}=\arg\max_{k}z_{k}$ : les régions se lisent aussi bien sur $\mathbf{a}$ que sur $\mathbf{z}$ , et il est plus simple de les lire sur $\mathbf{z}$ .

DérivationLes régions de décision de la famille

\mathbf{x}\mapsto W\mathbf{x}+\mathbf{b}

sont convexes (proposition 2)

Hypothèses

Le modèle est $\mathbf{z}(\mathbf{x})=W\mathbf{x}+\mathbf{b}$ , avec $\mathbf{w}_{k}^{\mathsf{T}}$ la ligne $k$ de $W$ .
$R_{k}=\{\mathbf{x}\in\mathbb{R}^{784}\ :\ z_{k}(\mathbf{x})\geq z_{j}(\mathbf{x})\ \ \forall j\in[\![1,K]\!]\}$ .

Propriétés utilisées

Pour $\boldsymbol{\alpha}\in\mathbb{R}^{784}$ et $\beta\in\mathbb{R}$ , le demi-espace fermé $\{\mathbf{x}:\boldsymbol{\alpha}^{\mathsf{T}}\mathbf{x}+\beta\geq 0\}$ , c'est-à-dire l'un des deux côtés d'un plan, est convexe
Une intersection quelconque de parties convexes est convexe

Étapes

On écrit la différence de deux scores. Chaque $z_{k}$ est une forme affine de $\mathbf{x}$ , c'est-à-dire un produit scalaire suivi de l'ajout d'une constante, et une différence de deux formes affines en est une aussi :
$z_{k}(\mathbf{x})-z_{j}(\mathbf{x})=(\mathbf{w}_{k}-\mathbf{w}_{j})^{\mathsf{T}}\mathbf{x}+(b_{k}-b_{j})$
Linéarité : $\mathbf{w}_{k}^{\mathsf{T}}\mathbf{x}-\mathbf{w}_{j}^{\mathsf{T}}\mathbf{x}=(\mathbf{w}_{k}-\mathbf{w}_{j})^{\mathsf{T}}\mathbf{x}$ .
$R_{k}=\bigcap_{j\neq k}\ \big\{\mathbf{x}\in\mathbb{R}^{784}\ :\ (\mathbf{w}_{k}-\mathbf{w}_{j})^{\mathsf{T}}\mathbf{x}+(b_{k}-b_{j})\geq 0\big\}$
La condition $z_{k}\geq z_{j}$ pour tout $j$ se réécrit comme la conjonction de $K-1$ inégalités affines.
Chacun de ces $K-1$ ensembles est un demi-espace fermé, donc convexe. $R_{k}$ en est l'intersection, donc $R_{k}$ est convexe. C'est même un polyèdre convexe : une intersection finie de demi-espaces.
Vérification directe de la convexité d'un demi-espace : si $\boldsymbol{\alpha}^{\mathsf{T}}u+\beta\geq 0$ et $\boldsymbol{\alpha}^{\mathsf{T}}v+\beta\geq 0$ , alors pour $t\in[0,1]$ , $\boldsymbol{\alpha}^{\mathsf{T}}\big((1-t)u+tv\big)+\beta=(1-t)(\boldsymbol{\alpha}^{\mathsf{T}}u+\beta)+t(\boldsymbol{\alpha}^{\mathsf{T}}v+\beta)\geq 0$ comme somme de deux termes positifs.

Résultat

\forall k\in[\![1,K]\!],\ \ R_{k}\ \text{est un polyèdre convexe de }\mathbb{R}^{784}

Interprétation

La propriété ne dépend ni de $W$ , ni de $\mathbf{b}$ , ni de la façon dont ils ont été choisis. Elle est vraie pour tous les modèles de la famille, y compris le meilleur d'entre eux. Ce n'est donc pas une observation sur le modèle mesuré : c'est une contrainte sur ce que cette famille peut faire.

Ce que ce résultat ne dit pas

La proposition ne dit pas que la famille est mauvaise, ni combien d'erreurs elle fera : elle dit une forme.
Elle cesse d'être vraie dès qu'une fonction non affine s'insère entre deux étapes de calcul. La page 9 le démontre, et la mesure ci-dessous le vérifie.

Corollaire. Soient $\mathbf{u}$ et $\mathbf{v}$ deux images que le modèle classe toutes deux dans la classe $k-1$ , c'est-à-dire $\mathbf{u},\mathbf{v}\in R_{k}$ . Leur milieu $\tfrac{1}{2}(\mathbf{u}+\mathbf{v})$ appartient alors à $R_{k}$ et se trouve donc classé dans la même classe, puisque c'est le cas $t=1/2$ de la définition de la convexité.

Le compte de $4\,250$ paires devait par conséquent valoir zéro, et une seule exception aurait invalidé la proposition 2 : aucun modèle de cette famille, quel que soit son entraînement, ne peut classer deux images en $k-1$ et leur milieu ailleurs.

Le même essai, avec le réseau à ReLU

Le même protocole, et la même paire · cours/lecon2/mesures.py, section 5

  -- MODELE 3, avec ReLU ---------------------------------------------------
      paires dont les DEUX extremites sont dans R_c   4816 sur 5000
      parmi elles, milieu classe AILLEURS              69   (1.43 %)
      sur TOUTES les paires, milieu classe ailleurs    89   (1.78 %)

                            image 115   image 668   milieu
      MODELE 1, lineaire           4          4         4
      MODELE 3, avec ReLU          4          4         9

Lecture

Le modèle 3 est celui que la page 9 construira, en glissant entre les deux couches une fonction qui n'est pas affine ; il est mesuré ici pour montrer que le compte précédent n'était pas nul par accident.
$69$ sur $4\,816$ , là où le modèle linéaire donnait $0$ sur $4\,250$ . Les deux comptes sortent du même protocole, sur les mêmes paires : ce qui les sépare est la famille de fonctions, pas le tirage.
La dernière ligne des deux tableaux compte autre chose et va dans l'autre sens, $89$ contre $121$ , simplement parce que le modèle 3 classe mieux : il laisse moins de paires avec une extrémité fautive. Seules les deuxièmes lignes se comparent.
Sur la paire de cette page, le réseau à ReLU lit un $9$ entre les deux $4$ . Aucun modèle linéaire ne donne ce triplet de réponses, quel que soit son entraînement, et le corollaire dit pourquoi.
Ses régions ne sont donc pas convexes. La proposition 4, page 9, dira d'où vient cette liberté ; elle est mesurée ici, elle n'est pas encore expliquée.

Un seul gabarit par classe

La même limite se lit sans géométrie, directement sur $(4.2)$ . Le score de la classe $k-1$ vaut $\mathbf{w}_{k}^{\mathsf{T}}\mathbf{x}+b_{k}$ , c'est-à-dire une mesure de ressemblance entre l'image et un motif fixé, le gabarit $G_{k}=\mathrm{vec}^{-1}(\mathbf{w}_{k})$ de la ligne $k$ . La classe entière est donc résumée par une seule image de référence.

Un chiffre ne se résume pas à un motif

Un $4$ fermé, dont les deux traits obliques se rejoignent, et un $4$ ouvert, dont ils ne se rejoignent pas, sont tous deux des $4$ sans porter d'encre aux mêmes endroits, et il en va de même d'un $7$ barré et d'un $7$ qui ne l'est pas.

Il faudrait donc un gabarit unique qui marque bien sur les deux variantes, et un gabarit unique dépense ses valeurs extrêmes là où il sépare le mieux sa classe des neuf autres : celui du $4$ mesuré page 4 place son minimum en $(4,14)$ , tout en haut de la grille, et n'a plus rien à dire sur la fermeture de la boucle, qui est pourtant ce qui distingue les deux variantes.

Vérification rapide n° 14

Sur un modèle, les images de test n°9025 et n°3231, toutes deux de classe $1$ , sont toutes deux prédites $1$ . Leur milieu est prédit $8$ .

a
Que peut-on conclure sur ce modèle, et par quel énoncé exactement ?
b
Cette observation dit-elle quelque chose sur la qualité du modèle ?
c
Si les deux extrémités avaient été prédites $1$ et $7$ , la même conclusion tiendrait-elle ?

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

Reste une question que cette page ne tranche pas. Si une famille plus riche fait mieux, que trouve-t-elle que celle-ci ne trouvait pas ? La page 11 y répond, avec une mesure et non avec une intuition.

Démonstration10 min

Le plafond, et d'où il vient

Pourquoi ce premier modèle cesse de progresser, et pourquoi ce n'est pas un problème de réglage.

Le milieu est une entrée comme les autres, et le modèle la classe comme les autres. La paire est prise parmi les

982

images de

4

du jeu de test, dont

921

que les deux modèles lisent

4

, dans l'ordre des indices.

Ce qu'un modèle linéaire ne peut pas répondre

Deux $4$, leur milieu, et ce que le modèle linéaire en dit · cours/lecon2/mesures.py, section 5

      image de test n°115, classe 4
      image de test n°668, classe 4
      leur milieu ( x_115 + x_668 ) / 2

                            image 115   image 668   milieu
      MODELE 1, lineaire           4          4         4

Lecture

Le milieu est l'image moyenne des deux, pixel par pixel : $\tfrac{1}{2}(\mathbf{x}_{115}+\mathbf{x}_{668})\in[0,1]^{784}$ . C'est une entrée comme les autres, et le modèle la classe comme les autres.

Ce modèle peut-il réussir les trois, ou sa troisième réponse est-elle déjà fixée par les deux premières ?

0:00 / 0:25

La question, mesurée sur $5\,000$ paires · cours/lecon2/mesures.py, section 5

    5000 paires d'images de MEME classe, 500 par classe,
    tirees dans les 10 000 images de test, graine 0.

  -- MODELE 1, lineaire ----------------------------------------------------
      paires dont les DEUX extremites sont dans R_c   4250 sur 5000
      parmi elles, milieu classe AILLEURS              0   (0.00 %)
      sur TOUTES les paires, milieu classe ailleurs    121   (2.42 %)

Lecture

Zéro sur $4\,250$ : chaque fois que les deux extrémités reçoivent la même classe, le milieu la reçoit aussi, sans une seule exception.
La dernière ligne quitte les $4\,250$ et compte sur les $5\,000$ paires de départ : $121$ fois, soit $2{,}42\,\%$ , le milieu reçoit une classe autre que celle des deux images qui l'encadrent. Ce n'est pas la même question que la ligne au-dessus, et ce compte ne contredit rien.
La graine $0$ fixe le tirage des paires, de sorte que deux exécutions comparent les mêmes images.
La troisième réponse est donc fixée par les deux premières, et un compte nul sur $4\,250$ tirages n'est pas un bon résultat mais la marque d'une contrainte. Il reste à dire laquelle.

D'où vient le zéro

Partie convexeconvex set: Une partie $C\subseteq\mathbb{R}^{d}$ telle que pour tous $u,v\in C$ et tout $t\in[0,1]$ , $(1-t)u+tv\in C$ . Le segment joignant deux points de $C$ reste entièrement dans $C$ .

Région de décisiondecision region: Pour $k\in[\![1,K]\!]$ , l'ensemble $R_{k}$ des entrées dont le score $z_{k}$ est au moins aussi grand que les neuf autres. Les inégalités y sont larges, si bien que deux régions se touchent sur les ex æquo écartés page 6 ; hors de ces frontières, $R_{k}$ est exactement l'ensemble des entrées classées $k-1$ . Comme le dénominateur de $(6.3)$ est le même pour les dix coordonnées et que l'exponentielle est croissante, $\arg\max_{k}a_{k}=\arg\max_{k}z_{k}$ : les régions se lisent aussi bien sur $\mathbf{a}$ que sur $\mathbf{z}$ , et il est plus simple de les lire sur $\mathbf{z}$ .

DérivationLes régions de décision de la famille

\mathbf{x}\mapsto W\mathbf{x}+\mathbf{b}

sont convexes (proposition 2)

Hypothèses

Le modèle est $\mathbf{z}(\mathbf{x})=W\mathbf{x}+\mathbf{b}$ , avec $\mathbf{w}_{k}^{\mathsf{T}}$ la ligne $k$ de $W$ .
$R_{k}=\{\mathbf{x}\in\mathbb{R}^{784}\ :\ z_{k}(\mathbf{x})\geq z_{j}(\mathbf{x})\ \ \forall j\in[\![1,K]\!]\}$ .

Propriétés utilisées

Pour $\boldsymbol{\alpha}\in\mathbb{R}^{784}$ et $\beta\in\mathbb{R}$ , le demi-espace fermé $\{\mathbf{x}:\boldsymbol{\alpha}^{\mathsf{T}}\mathbf{x}+\beta\geq 0\}$ , c'est-à-dire l'un des deux côtés d'un plan, est convexe
Une intersection quelconque de parties convexes est convexe

Étapes

On écrit la différence de deux scores. Chaque $z_{k}$ est une forme affine de $\mathbf{x}$ , c'est-à-dire un produit scalaire suivi de l'ajout d'une constante, et une différence de deux formes affines en est une aussi :
$z_{k}(\mathbf{x})-z_{j}(\mathbf{x})=(\mathbf{w}_{k}-\mathbf{w}_{j})^{\mathsf{T}}\mathbf{x}+(b_{k}-b_{j})$
Linéarité : $\mathbf{w}_{k}^{\mathsf{T}}\mathbf{x}-\mathbf{w}_{j}^{\mathsf{T}}\mathbf{x}=(\mathbf{w}_{k}-\mathbf{w}_{j})^{\mathsf{T}}\mathbf{x}$ .
$R_{k}=\bigcap_{j\neq k}\ \big\{\mathbf{x}\in\mathbb{R}^{784}\ :\ (\mathbf{w}_{k}-\mathbf{w}_{j})^{\mathsf{T}}\mathbf{x}+(b_{k}-b_{j})\geq 0\big\}$
La condition $z_{k}\geq z_{j}$ pour tout $j$ se réécrit comme la conjonction de $K-1$ inégalités affines.
Chacun de ces $K-1$ ensembles est un demi-espace fermé, donc convexe. $R_{k}$ en est l'intersection, donc $R_{k}$ est convexe. C'est même un polyèdre convexe : une intersection finie de demi-espaces.
Vérification directe de la convexité d'un demi-espace : si $\boldsymbol{\alpha}^{\mathsf{T}}u+\beta\geq 0$ et $\boldsymbol{\alpha}^{\mathsf{T}}v+\beta\geq 0$ , alors pour $t\in[0,1]$ , $\boldsymbol{\alpha}^{\mathsf{T}}\big((1-t)u+tv\big)+\beta=(1-t)(\boldsymbol{\alpha}^{\mathsf{T}}u+\beta)+t(\boldsymbol{\alpha}^{\mathsf{T}}v+\beta)\geq 0$ comme somme de deux termes positifs.

Résultat

\forall k\in[\![1,K]\!],\ \ R_{k}\ \text{est un polyèdre convexe de }\mathbb{R}^{784}

Interprétation

Ce que ce résultat ne dit pas

La proposition ne dit pas que la famille est mauvaise, ni combien d'erreurs elle fera : elle dit une forme.
Elle cesse d'être vraie dès qu'une fonction non affine s'insère entre deux étapes de calcul. La page 9 le démontre, et la mesure ci-dessous le vérifie.

Le même essai, avec le réseau à ReLU

Le même protocole, et la même paire · cours/lecon2/mesures.py, section 5

  -- MODELE 3, avec ReLU ---------------------------------------------------
      paires dont les DEUX extremites sont dans R_c   4816 sur 5000
      parmi elles, milieu classe AILLEURS              69   (1.43 %)
      sur TOUTES les paires, milieu classe ailleurs    89   (1.78 %)

                            image 115   image 668   milieu
      MODELE 1, lineaire           4          4         4
      MODELE 3, avec ReLU          4          4         9

Lecture

Le modèle 3 est celui que la page 9 construira, en glissant entre les deux couches une fonction qui n'est pas affine ; il est mesuré ici pour montrer que le compte précédent n'était pas nul par accident.
$69$ sur $4\,816$ , là où le modèle linéaire donnait $0$ sur $4\,250$ . Les deux comptes sortent du même protocole, sur les mêmes paires : ce qui les sépare est la famille de fonctions, pas le tirage.
La dernière ligne des deux tableaux compte autre chose et va dans l'autre sens, $89$ contre $121$ , simplement parce que le modèle 3 classe mieux : il laisse moins de paires avec une extrémité fautive. Seules les deuxièmes lignes se comparent.
Sur la paire de cette page, le réseau à ReLU lit un $9$ entre les deux $4$ . Aucun modèle linéaire ne donne ce triplet de réponses, quel que soit son entraînement, et le corollaire dit pourquoi.
Ses régions ne sont donc pas convexes. La proposition 4, page 9, dira d'où vient cette liberté ; elle est mesurée ici, elle n'est pas encore expliquée.

Un seul gabarit par classe

Un chiffre ne se résume pas à un motif

Vérification rapide n° 14

Sur un modèle, les images de test n°9025 et n°3231, toutes deux de classe $1$ , sont toutes deux prédites $1$ . Leur milieu est prédit $8$ .

a
Que peut-on conclure sur ce modèle, et par quel énoncé exactement ?
b
Cette observation dit-elle quelque chose sur la qualité du modèle ?
c
Si les deux extrémités avaient été prédites $1$ et $7$ , la même conclusion tiendrait-elle ?

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