Rappels mathématiques

Ce cours suppose acquis trois autres cours: Analyse I, Algèbre linéaire et Probabilités et statistique. Il n'en utilise pourtant qu'une petite partie, mais il l'utilise sans arrêt, et souvent sous une forme que ces cours n'ont pas mise en avant: un gradient par rapport à un vecteur de paramètres, une matrice ${\tilde{X}}^{\top }\tilde{X}$ dont on regarde les valeurs propres, une covariance entre deux caractéristiques, une vraisemblance que l'on maximise. Cette annexe rassemble ces outils, dans la notation du cours.

Elle ne remplace pas les cours d'origine. Les énoncés dont la preuve tient en quelques lignes sont démontrés; les autres sont admis, avec la raison et le chapitre où les retrouver. Les exemples reprennent les jeux de données du cours, en particulier les loyers du jeu A (données fictives, construites pour le cours), pour que chaque formule ait déjà une valeur que vous connaissez. La dernière section indique quel chapitre emprunte quoi.

Vecteurs et matrices

Deux lectures du produit d'une matrice par un vecteur reviennent à chaque chapitre, et il vaut la peine de les avoir toutes deux en tête. Par lignes, la composante $i$ de $X\mathbf{w}$ est le produit scalaire de la ligne $i$ avec $\mathbf{w}$: c'est la prédiction ${\mathbf{x}}_i^{\top }\mathbf{w}$ du modèle linéaire pour l'exemple $i$. Par colonnes, $X\mathbf{w}$ est une combinaison des colonnes de $X$ de coefficients :

où ${\mathbf{c}}_j\in {\mathbb{R}}^n$ est la colonne $j$ (toutes les valeurs de la caractéristique $j$) et ${\mathbf{e}}_i$ le $i$-ième vecteur de la base canonique. La même dualité vaut pour la transposée: la composante de est le produit scalaire de la colonne avec . C'est sous cette forme qu'apparaissent tous les gradients du cours, au chapitre 3 comme au chapitre 4: une caractéristique par composante, pondérée par les écarts.

Le reste du calcul matriciel — produit, inverse, rang, noyau — est celui d'Algèbre linéaire, chapitres 2 et 5. Retenez seulement le théorème du rang: pour $A\in {\mathbb{R}}^{n\times p}$, $\dim \ker A+\mathrm{rang}A=p$; et qu'une matrice carrée est inversible si et seulement si son noyau est réduit à $\{0\}$.

Produit scalaire, normes et projections

Démonstration. Si $\mathbf{y}=0$, les deux membres sont nuls. Sinon, le polynôme $P(t)=\Vert \mathbf{x}+t\mathbf{y}{\Vert }^2=\Vert \mathbf{y}{\Vert }^2{t}^2+2({\mathbf{x}}^{\top }\mathbf{y})t+\Vert \mathbf{x}{\Vert }^2$ est positif ou nul pour tout ; son discriminant réduit est donc négatif ou nul, ce qui est l'inégalité. Il est nul exactement quand a une racine , c'est-à-dire quand .

L'inégalité autorise à définir l'angle entre deux vecteurs non nuls, et le cours en utilise le cosinus sous le nom de similarité cosinus (cosine similarity, chapitre 13):

Elle vaut 1 pour deux vecteurs de même direction et de même sens, 0 pour deux vecteurs orthogonaux. Le chapitre 3 tire de la même inégalité que le gradient est la direction de plus forte montée (théorème 3.1).

Le théorème de Pythagore, $\Vert \mathbf{x}+\mathbf{y}{\Vert }^2=\Vert \mathbf{x}{\Vert }^2+\Vert \mathbf{y}{\Vert }^2$ pour $\mathbf{x}$ orthogonal à $\mathbf{y}$, se lit sur le développement $\Vert \mathbf{x}+\mathbf{y}{\Vert }^2=\Vert \mathbf{x}{\Vert }^2+2{\mathbf{x}}^{\top }\mathbf{y}+\Vert \mathbf{y}{\Vert }^2$. Il suffit à établir le résultat central de la régression linéaire.

Démonstration. Un vecteur est orthogonal à tout $E$ si et seulement s'il est orthogonal à chacune des colonnes qui l'engendrent, c'est-à-dire si $A^{\top }(\mathbf{y}-A\hat{\mathbf{c}})=0$: c'est l'équation annoncée. Si elle a lieu, pour $\mathbf{z}\in E$ le vecteur $\hat{\mathbf{y}}-\mathbf{z}$ est dans , donc orthogonal à , et Pythagore appliqué à donne l'identité; son second terme ne s'annule que pour . Pour , l'équation devient . L'existence d'une solution est établie au chapitre 2 (théorème 2.2).

Avec $A=\tilde{X}$, ce sont les équations normales du chapitre 2, et l'identité est (2.10). La lecture géométrique complète, avec la matrice de projection $\tilde{X}({\tilde{X}}^{\top }\tilde{X}{)}^{-1}{\tilde{X}}^{\top }$, est dans , chapitre 7, et dans la section «La lecture géométrique: une projection» du chapitre 2.

Valeurs propres et matrices symétriques

Le calcul à la main, la diagonalisation et ses obstacles sont dans Algèbre linéaire, chapitres 9 et 10. La lettre $\lambda$ sert à deux usages dans le cours, que le contexte sépare toujours: une valeur propre, ici et aux chapitres 3 et 13, et le paramètre de régularisation de la ridge et du lasso, au chapitre 6, dans l'exemple A.6 et l'exercice A.1. Le cours n'a besoin que du cas où tout se passe bien: les matrices symétriques, qui sont précisément celles qu'il rencontre — hessiennes, matrices ${\tilde{X}}^{\top }\tilde{X}$, matrices de covariance, matrices de noyau.

Démonstration (partielle). Nous montrons seulement que deux vecteurs propres associés à des valeurs propres distinctes $\lambda \ne \mu$ sont orthogonaux. Par symétrie, $\lambda {\mathbf{q}}^{\top }\mathbf{r}=(A\mathbf{q}{)}^{\top }\mathbf{r}={\mathbf{q}}^{\top }{A}^{\top }\mathbf{r}={\mathbf{q}}^{\top }A\mathbf{r}=\mu {\mathbf{q}}^{\top }\mathbf{r}$, donc et . Que les valeurs propres soient réelles et qu'il y ait assez de vecteurs propres pour former une base demande une récurrence sur la dimension; nous l' (, chapitre 11).

L'écriture $A=Q\Lambda Q^{\top }$ dit que, dans la base des ${\mathbf{q}}_j$, la matrice agit coordonnée par coordonnée: si $\mathbf{v}={\sum }_j{u}_j{\mathbf{q}}_j$, alors . C'est tout l'argument de convergence de la descente de gradient au chapitre 3 (théorème 3.5), où la suite des itérés se découple en suites géométriques, et de l'analyse en composantes principales au chapitre 13.

Démonstration. Écrivons $\mathbf{v}={\sum }_j{u}_j{\mathbf{q}}_j$ dans la base propre orthonormée. Alors ${\mathbf{v}}^{\top }A\mathbf{v}={\sum }_j{\lambda }_j{u}_j^2$ et , et l'encadrement vient de . Si toutes les valeurs propres sont positives ou nulles, la borne de gauche donne ; si l'une est négative, . Même raisonnement avec des inégalités strictes pour le cas défini positif. Enfin, si alors , donc quand est définie positive.

Démonstration. $(X^{\top }X{)}^{\top }=X^{\top }X$, et ${\mathbf{v}}^{\top }{X}^{\top }X\mathbf{v}=\Vert X\mathbf{v}{\Vert }^2\ge 0$. Si , alors , donc ; la réciproque est immédiate. La forme est donc strictement positive sur tout si et seulement si n'a que la solution nulle, c'est-à-dire si les colonnes sont indépendantes.

Ce petit théorème porte une bonne partie du cours. Il dit que l'erreur quadratique moyenne est convexe (théorème 3.4), que la hessienne $\frac{1}{n}{\tilde{X}}^{\top }D\tilde{X}$ de l'entropie croisée l'est aussi (théorème 4.3, avec $D^{1/2}\tilde{X}$ à la place de ), que la matrice de la ridge est définie positive pour (théorème 6.3), et que les matrices de covariance et les matrices de noyau du chapitre 9 ont des valeurs propres positives ou nulles.

Décomposition en valeurs singulières

Le théorème spectral ne s'applique qu'aux matrices carrées symétriques. Une matrice de données $X\in {\mathbb{R}}^{n\times d}$ n'est ni l'un ni l'autre; elle a pourtant une décomposition du même esprit.

Démonstration (partielle). L'existence est admise (Algèbre linéaire, chapitre 12): on la construit en diagonalisant $X^{\top }X$, symétrique et semi-définie positive (théorèmes A.3 et A.5), puis en posant ${\mathbf{u}}_j=X{\mathbf{v}}_j/{\sigma }_j$ pour et en complétant. Une fois la décomposition écrite, la relation avec se vérifie en une ligne: , avec ; c'est une diagonalisation orthogonale de . Et donne colonne par colonne .

Le symbole $\Sigma$ désigne ici la matrice des valeurs singulières, comme dans toute la littérature; ailleurs dans le cours il désigne une matrice de covariance. Le contexte tranche toujours.

Deux usages dans le cours. Le chapitre 2 rappelle que les bibliothèques résolvent les moindres carrés par une décomposition de $\tilde{X}$ plutôt qu'en formant ${\tilde{X}}^{\top }\tilde{X}$, dont le conditionnement est le carré de celui de $\tilde{X}$ — c'est la relation ${\lambda }_j(X^{\top }X)={\sigma }_j^2$. Le chapitre 13 obtient l'analyse en composantes principales par la décomposition de la matrice centrée, avec pour les valeurs propres de , et en déduit la meilleure approximation de rang (théorème 13.5 d'Eckart–Young, admis là-bas).

Le gradient d'une fonction de plusieurs variables

L'existence des dérivées partielles ne suffit pas à la différentiabilité; il suffit en revanche qu'elles existent et soient continues (Analyse II, chapitre 3). Toutes les fonctions de coût du cours — polynômes, exponentielles, logarithmes de quantités positives, sigmoïdes — sont dans ce cas, sauf aux points anguleux de la perte absolue, de la perte charnière et de la fonction ReLU, que les chapitres concernés traitent à part.

Démonstration. Par la définition A.6 avec $\mathbf{h}=t\mathbf{u}$, $J(\mathbf{\theta }+t\mathbf{u})-J(\mathbf{\theta })=t\nabla J(\mathbf{\theta }{)}^{\top }\mathbf{u}+o(t)$; on divise par et on fait tendre vers 0.

Deux conséquences géométriques. Le gradient est orthogonal aux lignes de niveau: le long d'une courbe où $J$ est constante, la dérivée directionnelle dans la direction de la tangente est nulle. Et parmi les directions unitaires, $\nabla J^{\top }\mathbf{u}$ est maximal pour $\mathbf{u}$ colinéaire au gradient, par Cauchy–Schwarz (théorème 3.1). La figure A.2, plus bas, montre les deux faits.

Pour dériver une composée, il faut la règle de la chaîne. Elle s'énonce avec la matrice jacobienne d'une application $\mathbf{g}:{\mathbb{R}}^p\to {\mathbb{R}}^m$, la matrice $J_{\mathbf{g}}(\mathbf{\theta })\in {\mathbb{R}}^{m\times p}$ de coefficients : une ligne par composante de , une colonne par variable.

La formule générale est admise (Analyse II, chapitre 4): sa preuve consiste à composer les deux approximations affines de la définition A.6 et à contrôler les restes, ce qui n'apprend rien d'utile ici. Les cas particuliers en découlent: la jacobienne de $\mathbf{\gamma }$ est la colonne ${\mathbf{\gamma }}^{\prime }(t)$, celle de $\mathbf{\theta }\mapsto A\mathbf{\theta }+\mathbf{b}$ est $A$, et celle de $\mathbf{\theta }\mapsto {\mathbf{\theta }}^{\top }\mathbf{x}$ est la ligne .

Le cas 1 est celui des chapitres 3 et 4 (démonstrations des théorèmes 3.1 et 3.3); le cas 3, avec $\ell$ l'entropie croisée et ${\ell }^{\prime }(z)=\sigma (z)-y$, donne le gradient (4.8) de la régression logistique. La forme générale, appliquée couche après couche, est la rétropropagation du chapitre 10: le gradient par rapport aux paramètres d'une couche s'obtient en multipliant le gradient par rapport à sa sortie par la transposée d'une jacobienne.

Gradients par rapport à un vecteur ou à une matrice

On écrit ${\nabla }_{\mathbf{w}}$ pour préciser la variable de dérivation. Les quatre formules suivantes suffisent pour tous les modèles linéaires du cours.

Démonstration. ${\mathbf{a}}^{\top }\mathbf{w}={\sum }_k{a}_k{w}_k$ a pour dérivée partielle $a_j$ par rapport à . Dans , la variable apparaît dans les termes où et dans ceux où ; la dérivée partielle vaut . Avec on obtient . Enfin avec , de gradient ; par le cas 2 de la règle de la chaîne, le gradient est .

La dernière formule, divisée par $n$, est le gradient de l'erreur quadratique moyenne du théorème 3.2. On peut aussi l'obtenir sans règle de la chaîne, en développant $\Vert X\mathbf{w}-\mathbf{y}{\Vert }^2={\mathbf{w}}^{\top }{X}^{\top }X\mathbf{w}-2{\mathbf{y}}^{\top }X\mathbf{w}+{\mathbf{y}}^{\top }\mathbf{y}$ et en appliquant les deux premières formules avec , symétrique, et : on trouve . Les deux chemins arrivent au même endroit, ce qui est un bon contrôle.

Une formule de gradient se vérifie toujours numériquement, et c'est une habitude à prendre avant de faire confiance à un calcul fait à la main: le chapitre 10 en fait la vérification standard de la rétropropagation. On compare chaque dérivée partielle à une différence centrée $(J(\mathbf{\theta }+h{\mathbf{e}}_j)-J(\mathbf{\theta }-h{\mathbf{e}}_j))/(2h)$, dont l'erreur est de l'ordre de (, chapitre 9, formule de Taylor) — et nulle, aux arrondis près, pour une fonction quadratique.

Les réseaux du chapitre 10 ont des paramètres rangés en matrices $W^{[\ell ]}$. Le gradient par rapport à une matrice se définit coefficient par coefficient.

Démonstration. ${\mathbf{u}}^{\top }W\mathbf{v}={\sum }_{j,k}{u}_j{w}_{jk}{v}_k$, dont la dérivée par rapport à est , le coefficient de . Pour le cas général, ne dépend de que par le terme , et n'intervient dans aucun autre ; par la règle de la chaîne, . Avec , .

Le produit $\mathbf{\delta }{\mathbf{x}}^{\top }$ d'une colonne par une ligne est une matrice de rang 1, appelée produit extérieur. La rétropropagation (chapitre 10) donne exactement cette forme pour chaque couche: le gradient de la perte par rapport à $W^{[\ell ]}$ est ${\mathbf{\delta }}^{[\ell ]}({\mathbf{a}}^{[\ell -1]}{)}^{\top }$, l'erreur de la couche multipliée par l'activation qui y entre.

Hessienne, développement de Taylor et convexité

Démonstration. Le cas général est admis (Analyse II, chapitre 5): il résulte de la formule de Taylor d'Analyse I appliquée à $t\mapsto J(\mathbf{\theta }+t\mathbf{h})$, dont la dérivée seconde vaut ${\mathbf{h}}^{\top }H\mathbf{h}$ par deux applications de la règle de la chaîne. Pour la quadratique, le théorème A.9 donne $\nabla J=\frac{1}{2}(A+A^{\top })\mathbf{\theta }-\mathbf{b}=A\mathbf{\theta }-\mathbf{b}$, dont la jacobienne est . En développant, , en utilisant par symétrie; c'est le développement, sans reste.

Le développement dit qu'au voisinage de tout point, une fonction régulière ressemble à une quadratique, dont la hessienne fixe la forme. Si $A$ est définie positive et ${\mathbf{\theta }}^{\ast }=A^{-1}\mathbf{b}$, la quadratique s'écrit $J(\mathbf{\theta })=J({\mathbf{\theta }}^{\ast })+\frac{1}{2}(\mathbf{\theta }-{\mathbf{\theta }}^{\ast }{)}^{\top }A(\mathbf{\theta }-{\mathbf{\theta }}^{\ast })$. Dans la base propre de , de coordonnées centrées en , la ligne de niveau est l'ellipse (l'ellipsoïde en dimension ) : ses axes sont portés par les vecteurs propres et ses demi-axes valent . Une grande valeur propre donne une direction et un axe court; une petite valeur propre, une direction et un axe long.

Le signe de la hessienne décide de la nature d'un point critique, comme le signe de la dérivée seconde en une variable.

Démonstration. Le point 3, avec la caractérisation de la convexité par la hessienne, est le théorème 3.3 du chapitre 3, démontré là-bas. Pour les points 1 et 2, le développement A.11 en ${\mathbf{\theta }}^{\ast }$ se réduit à $J({\mathbf{\theta }}^{\ast }+\mathbf{h})-J({\mathbf{\theta }}^{\ast })=\frac{1}{2}{\mathbf{h}}^{\top }H\mathbf{h}+o(\Vert \mathbf{h}{\Vert }^2)$. Si est définie positive, le théorème A.4 minore le terme principal par avec , qui l'emporte sur le reste pour petit; le contrôle précis du reste est (, chapitre 7). Si est indéfinie, croît dans la direction d'un vecteur propre de valeur propre positive et décroît dans celle d'un vecteur propre de valeur propre négative. La réciproque se lit sur les restrictions , qui ont un minimum local en .

Espérance, variance et covariance

Les propriétés de base — linéarité de l'espérance, $\mathrm{Var}(aX+b)=a^2\mathrm{Var}(X)$ — sont dans Probabilités et statistique, chapitres 3 et 5. Une identité mérite d'être isolée, parce que le cours la rencontre trois fois.

Démonstration. Notons $\mu =\mathbb{E}[X]$ et écrivons $X-c=(X-\mu )+(\mu -c)$. En développant le carré, $\mathbb{E}[(X-c{)}^2]=\mathbb{E}[(X-\mu {)}^2]+2(\mu -c)\mathbb{E}[X-\mu ]+(\mu -c{)}^2$, et le terme du milieu est nul car .

Appliquée à la loi empirique d'un échantillon, l'identité dit que la constante qui minimise l'erreur quadratique moyenne est la moyenne (chapitre 1). Appliquée à la prédiction $\hat{f}(\mathbf{x})$ d'une méthode entraînée sur des données aléatoires, avec $c$ la vraie valeur, elle donne la décomposition biais–variance du chapitre 6. Et appliquée à un estimateur, elle dit que son erreur quadratique moyenne est sa variance plus le carré de son biais.

Démonstration. 1. ${\mathbf{a}}^{\top }\mathbf{x}-{\mathbf{a}}^{\top }\mathbf{\mu }={\mathbf{a}}^{\top }(\mathbf{x}-\mathbf{\mu })$, donc $\mathrm{Var}({\mathbf{a}}^{\top }\mathbf{x})=\mathbb{E}[{\mathbf{a}}^{\top }(\mathbf{x}-\mathbf{\mu })(\mathbf{x}-\mathbf{\mu }{)}^{\top }\mathbf{a}]={\mathbf{a}}^{\top }\Sigma \mathbf{a}$ par linéarité, et une variance est positive ou nulle. Pour , c'est le théorème A.5 appliqué à . Développer le produit dans la définition. L'indépendance donne (, chapitre 7); pour la réciproque, uniforme sur et ont une covariance sans être indépendantes. Par bilinéarité et 3, , et .

Le point 4 explique pourquoi un gradient stochastique sur un mini-lot de $b$ exemples tirés indépendamment est moins bruité qu'un gradient sur un seul exemple, d'un facteur $b$ en variance (chapitre 3, exercice 3.4); l'exercice A.3 montre ce qu'il devient quand les variables sont corrélées, le cas du bagging au chapitre 8. Le point 1 est le point de départ de l'analyse en composantes principales: la variance des données projetées sur une direction unitaire $\mathbf{a}$ est ${\mathbf{a}}^{\top }S\mathbf{a}$, que le théorème A.4 borne par la plus grande valeur propre de $S$ (chapitre 13).

La loi normale et le maximum de vraisemblance

Les propriétés de la loi normale sont dans Probabilités et statistique, chapitre 6, et le cas vectoriel au chapitre 7. Retenez les ordres de grandeur, calculés avec la fonction d'erreur: une variable normale tombe à moins d'un écart type de son espérance avec probabilité $68,27$ %, à moins de deux avec $95,45$ %, à moins de trois avec $99,73$ %. Une valeur à plus de trois écarts types est donc rare, environ 0,3 % des cas, et c'est pourquoi les moindres carrés, qui supposent implicitement un bruit normal (théorème 2.5), réagissent si fort aux valeurs aberrantes. Dans le cas vectoriel, les lignes de niveau de la densité sont des ellipses d'axes portés par les vecteurs propres de $\Sigma$, comme celles de la figure A.2 avec ${\Sigma }^{-1}$ à la place de $A$; c'est le modèle des mélanges gaussiens du chapitre 12.

Maximiser $\ln L$, c'est minimiser $-\frac{1}{n}\ln L$, la log-vraisemblance négative moyenne: c'est sous cette forme que la vraisemblance devient une fonction de perte. Le chapitre 2 en tire les moindres carrés (bruit normal), le chapitre 4 l'entropie croisée (étiquette de Bernoulli), le chapitre 12 l'algorithme EM.

Démonstration. 1. $\ln L(\mu ,{\sigma }^2)=-\frac{n}{2}\ln (2\pi {\sigma }^2)-\frac{1}{2{\sigma }^2}{\sum }_i(x_i-\mu {)}^2$. À fixé, maximiser revient à minimiser , minimale en (théorème A.13 appliqué à la loi empirique). Avec , la fonction a pour dérivée , positive puis négative: elle est maximale en . C'est le calcul de la démonstration du théorème 2.5. Avec , , de dérivée , qui s'annule en , est positive avant et négative après.

L'estimateur ${\hat{\sigma }}^2$ divise par $n$ et sous-estime la variance en moyenne: $\mathbb{E}[{\hat{\sigma }}^2]=\frac{n-1}{n}{\sigma }^2$ (exercice A.5). Les propriétés des estimateurs — biais, convergence — sont dans , chapitre 10.

Ce que les chapitres empruntent à cette annexe

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Références

• Deisenroth, M. P., Faisal, A. A. et Ong, C. S., Mathematics for Machine Learning, Cambridge University Press, 2020 (algèbre linéaire, calcul vectoriel, probabilités et optimisation, écrits pour l'apprentissage automatique).
• Goodfellow, I., Bengio, Y. et Courville, A., Deep Learning, MIT Press, 2016, chap. 2 (algèbre linéaire), chap. 3 (probabilités) et chap. 4 (calcul numérique, hessienne et conditionnement).
• Bishop, C. M., Pattern Recognition and Machine Learning, Springer, 2006, chap. 2 (lois de probabilité, loi normale vectorielle) et annexe C (propriétés des matrices).
• Murphy, K. P., Probabilistic Machine Learning: An Introduction, MIT Press, 2022, chap. 7 (algèbre linéaire) et chap. 4 (estimation, maximum de vraisemblance).
• Azencott, C.-A., Introduction au Machine Learning, Dunod, 2ᵉ éd., 2022 (en français, avec ses rappels mathématiques).