Réduction de dimension

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

expliquer pourquoi l'on réduit la dimension d'un jeu de données — visualiser, compresser, débruiter, échapper à la malédiction de la dimension — et ce que l'on accepte de perdre en le faisant;
calculer la matrice de covariance d'un nuage centré et lire, dans ses valeurs propres et ses vecteurs propres, les directions et les quantités de variance du nuage;
démontrer que la première composante principale est le vecteur propre de la plus grande valeur propre, que la variance qu'elle capte vaut $λ_{1}$ , et que maximiser la variance projetée revient à minimiser l'erreur de reconstruction;
projeter et reconstruire des données, choisir un nombre de composantes à partir de la part de variance expliquée, et décider s'il faut standardiser d'abord;
obtenir l'ACP par la décomposition en valeurs singulières, justifier $λ_{j} = σ_{j}^{2} / n$ et énoncer le théorème d'Eckart–Young;
appliquer l'idée de factorisation à une matrice de notes incomplète par moindres carrés alternés et à des plongements de mots, calculer une similarité cosinus, et dire ce que les méthodes linéaires, et les cartes comme t-SNE, ne montrent pas.

Pourquoi réduire la dimension

Les jeux de données fictifs des chapitres précédents avaient une ou deux caractéristiques, pour que chaque calcul se vérifie à la main; les chapitres 10 et 11 ont déjà rencontré des images, et le chapitre 7 des points en dimension 20 et au-delà. Les données réelles ont souvent beaucoup de caractéristiques: une image de $28 \times 28$ pixels en gris est un vecteur de 784 nombres, un questionnaire de satisfaction en compte cinquante, un document décrit par les mots qu'il contient en compte autant que le vocabulaire — des dizaines de milliers. Le chapitre 7 a montré ce que coûte cette abondance à une méthode fondée sur des distances: en grande dimension, sur des points uniformes, le plus proche voisin est presque aussi loin que le plus lointain. Il a aussi indiqué la nuance qui sauve la situation: les données réelles n'occupent presque jamais tout l'espace. Les images plausibles de chiffres manuscrits forment une toute petite partie de l'ensemble des tableaux de 784 nombres; les réponses à cinquante questions sont gouvernées par quelques attitudes de fond. La dimension apparente est grande, la dimension utile est petite.

Réduire la dimension (dimensionality reduction), c'est chercher une représentation des mêmes exemples avec $k$ nombres au lieu de $d$ , $k$ beaucoup plus petit que $d$ , en perdant le moins d'information possible. Dans ce chapitre, $k$ désigne donc le nombre de composantes gardées; ce n'est ni le nombre de voisins $k$ du chapitre 7, ni le nombre de groupes $K$ du chapitre 12. C'est un problème non supervisé (chapitre 1): il n'y a pas d'étiquette, seulement le nuage des $x_{i}$ , et c'est sa propre forme qui décide de ce qui est important. On le fait pour quatre raisons, qui ne demandent pas toutes la même chose.

Visualiser. Un écran a deux dimensions. Représenter cinquante caractéristiques par deux coordonnées bien choisies permet de voir des groupes, des tendances, des exemples aberrants, avant tout modèle.
Compresser. Ranger $k$ nombres par exemple au lieu de $d$ réduit la mémoire et le temps de calcul de tout ce qui suit: une recherche de voisins en $O (nk)$ au lieu de $O (n d)$ par requête (chapitre 7).
Débruiter. Si le signal vit dans quelques directions et le bruit dans toutes, ne garder que les premières écarte une bonne partie du bruit.
Préparer un modèle. Des caractéristiques très corrélées rendent les coefficients d'une régression instables (chapitre 2); quelques combinaisons non corrélées les remplacent avantageusement, au prix de leur interprétation.

Ce chapitre développe la méthode linéaire de référence, l'analyse en composantes principales (principal component analysis, ACP, PCA en anglais), sous ses deux lectures — la direction de plus grande variance et le sous-espace qui reconstruit le mieux les données —, puis son calcul par la décomposition en valeurs singulières. Il montre ensuite que la même idée, «approcher un grand tableau par le produit de deux petits», sert à recommander des films et à représenter des mots par des vecteurs. Il se termine par les limites des méthodes linéaires et par un regard d'ensemble sur le cours.

Question 13.1

Dans lesquelles de ces situations une réduction de dimension non supervisée, comme l'ACP, est-elle un bon premier réflexe? (Plusieurs réponses possibles.)

Plusieurs réponses possibles

Centrer les données et mesurer leur dispersion

Pour fixer les idées, nous suivrons un nuage de dix points dans le plan. Ce sont des données fictives, construites pour le cours: dix étudiants, et leurs points à deux examens notés sur 60, l'analyse ( $x_{1}$ ) et l'algèbre linéaire ( $x_{2}$ ).

Étudiant	1	2	3	4	5	6	7	8	9	10
Analyse $x_{1}$	33	37	34	39	41	38	40	46	45	47
Algèbre $x_{2}$	31	29	33	33	32	36	40	37	40	39

Les moyennes valent $\overset{x}{ˉ}_{1} = 40$ et $\overset{x}{ˉ}_{2} = 35$ . Le point moyen $\overset{ˉ}{x} = (40, 35)$ est le centre de gravité du nuage, et la première chose que fait l'ACP est de s'y placer: on travaille sur les . La raison est simple: la réduction de dimension cherche à décrire comment les exemples les uns des autres, et ce qu'ils ont en commun — la moyenne — se range à part, en nombres une fois pour toutes. Le centrage ne fait rien perdre.

La matrice $S$ est symétrique, puisque $s_{j k} = s_{k j}$ , et semi-définie positive: pour tout vecteur $v$ , $v^{⊤} S v = \frac{1}{n} \sum_{i} (v^{⊤} (x_{i} - \overset{ˉ}{x}))^{2} \geq 0$ . Ces deux propriétés vont tout faire. Elle est la version empirique de la matrice de covariance d'un vecteur aléatoire (Probabilités et statistique, chapitre 7), et l'on y retrouve la convention de ce cours: on divise par , comme pour l'écart type de la standardisation aux chapitres 3 et 7.

La figure 13.1 montre ce que disent les valeurs propres. Le nuage est allongé, et la longueur de chaque flèche est l'écart type des données dans sa direction: les étudiants s'étalent sur environ $\pm 5, 5$ points le long du niveau général et sur $\pm 2, 2$ points seulement le long du profil. Les deux axes sont perpendiculaires, et ils ne sont ni horizontaux ni verticaux: aucune des deux notes, prise seule, ne décrit la direction principale du nuage. C'est pourquoi le dessin respecte la même échelle sur les deux axes; avec des échelles différentes, l'angle droit cesserait de paraître droit.

Projeter sur une direction

Réduire le nuage à une dimension, c'est choisir une droite et remplacer chaque point par sa position sur cette droite. Fixons d'abord la droite passant par le point moyen, de direction unitaire $v$ .

Le score $z_{i}$ est la coordonnée de l'exemple le long de la droite: c'est le nombre unique qui remplace ses $d$ coordonnées. La reconstruction est ce qu'on peut retrouver de l'exemple à partir de ce seul nombre, et l'erreur de reconstruction ce qu'on a perdu. Les scores sont centrés: $\frac{1}{n} \sum_{i} z_{i} = v^{⊤} (\frac{1}{n} \sum_{i} (x_{i} - \overset{ˉ}{x})) = 0$ , si bien que leur variance est bien la moyenne de leurs carrés. Elle se calcule directement à partir de :

\frac{1}{n} i = 1 \sum n z_{i}^{2} = \frac{1}{n} i = 1 \sum n v^{⊤} (x_{i} - \overset{ˉ}{x}) (x_{i} - \overset{ˉ}{x})^{⊤} v = v^{⊤} S v . (13.3)

La variance d'un nuage dans une direction est donc une forme quadratique en cette direction (Algèbre linéaire, chapitre 11). Pour le nuage des examens et $v = (cos t, sin t)$ , elle vaut $21 cos^{2} t + 24 cos t sin t + 14 sin^{2} t$ : 21 à l'horizontale (, la variance de l'analyse), 14 à la verticale.

Il y a deux façons raisonnables de choisir $v$ . La première: garder le plus de variance possible, pour que les scores séparent les exemples autant que les données d'origine. La seconde: perdre le moins possible, c'est-à-dire rendre l'erreur de reconstruction moyenne la plus petite possible. Le théorème suivant dit qu'elles sont une seule et même exigence.

Démonstration. Posons $c_{i} = x_{i} - \overset{ˉ}{x}$ . Par définition, $x_{i} - \hat{x}_{i} = c_{i} - z_{i} v$ , et ce vecteur est orthogonal à :

v^{⊤} (c_{i} - z_{i} v) = v^{⊤} c_{i} - z_{i} ∥ v ∥^{2} = z_{i} - z_{i} = 0.

Le vecteur $c_{i}$ est donc la somme de deux vecteurs orthogonaux, $z_{i} v$ et $c_{i} - z_{i} v$ , et le théorème de Pythagore (Algèbre linéaire, chapitre 7) donne . On fait la moyenne sur : le membre de gauche donne (définition 13.1), et le premier terme de droite donne par (13.3). Comme ne dépend pas de , maximiser l'un des deux termes de droite revient à minimiser l'autre.

Ce théorème est le cœur géométrique de l'ACP, et c'est un théorème de Pythagore. Chaque point est à une certaine distance du point moyen; la droite partage le carré de cette distance en une part «le long» de la droite, que le score conserve, et une part «à travers», que la reconstruction perd. La somme ne dépend pas de la droite. Tourner la droite ne fait que déplacer de la variance d'un compartiment à l'autre — et l'explorateur 13.1 vous laisse le faire.

Explorateur 13.1 · Tourner une direction dans le nuage des examens

Faites tourner la droite autour du point moyen. Chaque étudiant est projeté orthogonalement sur elle: la variance des projections et l'erreur de reconstruction moyenne (le carré moyen des segments tiretés) varient en sens contraire, et leur somme reste à 35, la variance totale. La variance projetée culmine à $λ_{1} = 30$ vers 36,87°, exactement là où l'erreur touche son minimum $λ_{2} = 5$ . Le second curseur choisit un étudiant et montre son triangle rectangle.

Angle de la direction v (degrés)0°

Étudiant mis en évidence8

Variance projetée

21,00

Erreur de reconstruction moyenne

14,00

Somme des deux

35,00

Optimum: angle, λ₁

36,87°, 30,00

Étudiant 8: distance² au point moyen

40,00

Étudiant 8: z² + e²

36,00 + 4,00

Partez de l'angle 0°: la droite est horizontale, la variance projetée vaut 21 — celle de l'analyse seule — et l'erreur 14, celle de l'algèbre. En tournant, la variance projetée monte jusqu'à 30 vers 36,87°, puis redescend jusqu'à 14 à la verticale, et à 126,87° elle touche son minimum 5. La somme affichée ne bouge jamais de 35, et le second curseur montre pourquoi: pour chaque étudiant, le carré de sa distance au point moyen se partage en $z_{i}^{2} + e_{i}^{2}$ , quelle que soit la direction.

On a supposé que la droite passe par le point moyen. C'est sans perte: pour une direction $v$ fixée et une droite $a + t v$ quelconque, l'erreur moyenne vaut l'erreur de la droite parallèle passant par $\overset{ˉ}{x}$ augmentée du carré de la distance de $\overset{ˉ}{x}$ à la droite — c'est l'identité (1.5) du chapitre 1 appliquée à la partie orthogonale à $v$ des vecteurs $x_{i} - a$ . La meilleure droite passe donc toujours par le point moyen, comme la meilleure constante est la moyenne.

L'axe principal n'est pas la droite de régression

La droite des moindres carrés du chapitre 2 et l'axe principal passent tous deux par le point moyen, mais ils ne minimisent pas la même chose. La régression de $x_{2}$ sur $x_{1}$ minimise les écarts verticaux — les erreurs sur la variable à prédire —, l'ACP les distances perpendiculaires, où les deux coordonnées jouent le même rôle. Sur le nuage des examens, la régression de l'algèbre sur l'analyse a pour pente $s_{12} / s_{11} = 12/21 = 0, 5714$ , la régression de l'analyse sur l'algèbre correspond dans le plan à une pente , et l'axe principal a la pente , entre les deux. Choisir l'une ou l'autre droite n'est pas une question de calcul: la régression sert à une variable à partir de l'autre, l'ACP à les deux sans en privilégier aucune.

Question 13.2

Sur le nuage des examens, de covariance $S = (21121214)$ , quelle est la variance projetée sur la direction unitaire $v = (0, 6; 0, 8)$ , en points²?

La première composante principale

Il reste à trouver la meilleure direction. Pour deux caractéristiques, on pourrait dériver $21 cos^{2} t + 24 cos t sin t + 14 sin^{2} t$ par rapport à $t$ . En dimension $d$ , il faut un argument qui ne dépende pas de la dimension, et c'est le théorème spectral qui le fournit.

Une telle base existe toujours: $S$ est symétrique réelle, et le théorème spectral (Algèbre linéaire, chapitre 11) garantit qu'elle est diagonalisable dans une base orthonormée, à valeurs propres réelles. Comme $S$ est semi-définie positive, ses valeurs propres sont de plus positives ou nulles: $λ_{j} = v_{j}^{⊤} S v_{j} \geq 0$ . Le vecteur propre n'est défini qu'au signe près — convient aussi —, si bien que deux logiciels peuvent rendre des composantes de signes opposés: ce n'est pas une erreur, mais il faut s'en souvenir avant d'interpréter un signe.

Démonstration. Décomposons $v$ dans la base orthonormée des vecteurs propres: $v = \sum_{j} c_{j} v_{j}$ avec $c_{j} = v_{j}^{⊤} v$ . Comme la base est orthonormée, . Par linéarité, , puis, encore par orthonormalité,

v^{⊤} S v = (k \sum c_{k} v_{k})^{⊤} (j \sum c_{j} λ_{j} v_{j}) = j = 1 \sum d λ_{j} c_{j}^{2} .

La variance projetée est donc une moyenne pondérée des valeurs propres, de poids $c_{j}^{2} \geq 0$ de somme 1. Une moyenne pondérée ne dépasse pas le plus grand de ses termes: $\sum_{j} λ_{j} c_{j}^{2} \leq λ_{1} \sum_{j} c_{j}^{2} = λ_{1}$ , ce qui est (13.5). Pour , on a et sinon, et la borne est atteinte: . Enfin, si , l'égalité s'écrit , somme de termes positifs, qui impose pour tout , donc . La dernière affirmation découle du théorème 13.1.

Le quotient $v^{⊤} S v / v^{⊤} v$ s'appelle le quotient de Rayleigh, et le théorème dit qu'il est compris entre $λ_{d}$ et $λ_{1}$ ; c'est le même argument qui, au chapitre 3, encadrait la courbure d'une fonction quadratique entre les valeurs propres extrêmes de sa hessienne. Sur le nuage des examens, la démonstration se lit en clair: une direction quelconque mélange le niveau général (variance 30) et le profil (variance 5), dans les proportions et , et sa variance est la moyenne de 30 et de 5 avec ces poids. Aucun mélange ne fait mieux que 30.

Les scores sur $v_{1} = (0, 8; 0, 6)$ se calculent sans racine carrée, puisque $v_{1}$ est rationnel: pour l'étudiant 1, $z_{1} = 0, 8 \cdot (- 7) + 0, 6 \cdot (- 4) = - 8$ . Les dix scores valent

- 8, - 6, - 6, - 2, - 1, - 1, 3, 6, 7, 8,

leur moyenne est nulle et la moyenne de leurs carrés vaut $300/10 = 30 = λ_{1}$ . Les scores sur $v_{2}$ valent $1, - 3, 2, - 1, - 3, 2, 4, - 2, 1, - 1$ , et la moyenne de leurs carrés vaut : c'est l'erreur de reconstruction moyenne, puisqu'en dimension 2 ce qu'on perd en projetant sur est exactement la composante sur . La reconstruction de l'étudiant 1 est , à point de son vrai couple . La figure 13.2 montre aussi le prix de la réduction: les étudiants 2, , et 3, , ont le même niveau général et des profils opposés — le premier meilleur en analyse, le second en algèbre —, et une seule composante ne les distingue plus.

En pratique, on ne résout pas une équation caractéristique de degré $d$ : on calcule les vecteurs propres par une méthode itérative. La plus simple est la puissance itérée (Algèbre linéaire, chapitre 9): on part d'un vecteur quelconque, on le multiplie par $S$ , on le normalise, et l'on recommence. Écrit dans la base propre, un vecteur $\sum_{j} c_{j} v_{j}$ devient après $t$ multiplications ; la composante sur l'emporte sur les autres d'un facteur , et le vecteur normalisé converge vers dès que et . Sur le nuage des examens, l'erreur est divisée par à chaque itération.

Question 13.3

Complétez covariance(points), qui renvoie la matrice de covariance empirique (division par $n$ ) d'une liste de points de dimension $d$ , et puissance_iteree(S, iterations), qui part du vecteur dont toutes les composantes valent 1, le multiplie par S et le normalise iterations fois, puis renvoie le couple (valeur propre, vecteur unitaire), la valeur propre étant $v^{⊤} S v$ . Le programme retrouve la première composante principale du nuage des examens.

composante_principale.py

Plusieurs composantes

Une seule composante suffit rarement. On cherche alors un sous-espace de dimension $k$ , et la réponse prolonge naturellement le théorème 13.2: après $v_{1}$ , la direction de plus grande variance parmi celles qui sont orthogonales à $v_{1}$ est $v_{2}$ , qui capte $λ_{2}$ (exercice 13.5), et ainsi de suite.

Nous admettons l'optimalité parmi tous les sous-espaces: elle repose sur une inégalité due à Ky Fan, dont la démonstration demande un argument d'entrelacement des valeurs propres qui dépasse ce chapitre. Le reste se vérifie directement: l'exercice 13.5 établit les valeurs $\sum_{j \leq k} λ_{j}$ et $\sum_{j > k} λ_{j}$ pour le sous-espace des vecteurs propres, et le théorème 13.1 s'étend sans changement, avec la même preuve par Pythagore, à la projection orthogonale sur un sous-espace. La matrice est le projecteur orthogonal sur l'espace engendré par les colonnes de (Algèbre linéaire, chapitre 7), et les coordonnées de la projection dans la base .

Deux propriétés des composantes méritent d'être retenues. Elles sont non corrélées: la covariance empirique des scores $z_{ij}$ et $z_{ik}$ vaut $v_{j}^{⊤} S v_{k} = λ_{k} v_{j}^{⊤} v_{k} = 0$ pour . L'ACP remplace donc des caractéristiques corrélées par des caractéristiques qui ne le sont plus — ce qui guérit la colinéarité du chapitre 2. Et elles sont : les deux premières composantes d'une ACP sont les mêmes qu'on en garde deux ou dix, si bien qu'on peut calculer quelques composantes et décider ensuite combien en garder.

L'égalité des deux dénominateurs vient de ce que la trace d'une matrice est la somme de ses valeurs propres; elle dit que les $d$ composantes, ensemble, expliquent toute la variance, ce qui est le théorème 13.3 pour $k = d$ . Sur le nuage des examens, $τ_{1} = 30/35 = 85, 71$ %.

Pour voir un vrai choix de $k$ , il faut plus de deux caractéristiques. Construisons un jeu fictif dont nous connaissons la structure: 200 élèves passent six épreuves — analyse, algèbre, physique, français, allemand, anglais. Chaque élève a deux aptitudes cachées, l'une «quantitative» et l'autre «langagière», tirées selon une loi normale; chaque note est une combinaison de ces aptitudes, plus un bruit propre à l'épreuve. On standardise les six notes et l'on calcule toutes les valeurs propres par puissance itérée, en retirant à chaque étape la composante trouvée — c'est la déflation: $S \leftarrow S - λ v v^{⊤}$ a les mêmes vecteurs propres que $S$ , avec la valeur propre $λ$ remplacée par 0, et la puissance itérée trouve alors la suivante.

import math
import random

random.seed(13)
eleves = []
for _ in range(200):
    f1 = random.gauss(0, 1)   # aptitude «quantitative», non observée
    f2 = random.gauss(0, 1)   # aptitude «langues», non observée
    b = [0.6 * random.gauss(0, 1)

lambda1 = 2.8437   part 0.474   cumul 0.474
lambda2 = 1.8439   part 0.307   cumul 0.781
lambda3 = 0.4211   part 0.070   cumul 0.851
lambda4 = 0.3278   part 0.055   cumul 0.906
lambda5 = 0.2965   part 0.049   cumul 0.955
lambda6 = 0.2670   part 0.045   cumul 1.000

Les données étant standardisées, chaque note a une variance 1 et la variance totale vaut 6. Deux valeurs propres se détachent, $2, 84$ et $1, 84$ , qui expliquent ensemble $78, 1$ % de la variance; les quatre suivantes sont petites et proches les unes des autres, entre $0, 27$ et $0, 42$ . C'est exactement la structure que nous avions cachée: deux aptitudes, et du bruit. Nous avons vérifié ces six valeurs par une seconde méthode, une diagonalisation de Jacobi par rotations, qui donne les mêmes quatre décimales.

Combien de composantes garder? Il n'y a pas de réponse universelle, mais trois règles d'usage, à combiner avec du jugement.

Un seuil de variance expliquée. On garde le plus petit $k$ tel que $τ_{k}$ dépasse un seuil fixé d'avance, souvent 90 % ou 95 %. Le seuil est arbitraire; il convient quand l'objectif est la compression.
Le coude. On cherche sur le diagramme des valeurs propres l'endroit où la décroissance s'aplatit: au-delà, chaque composante n'apporte plus que la part de bruit habituelle. Ici, le coude est net après la deuxième composante.
La règle de Kaiser, pour des données standardisées: garder les composantes de valeur propre supérieure à 1, la moyenne, c'est-à-dire celles qui expliquent plus qu'une caractéristique d'origine. Elle donne ici $k = 2$ .

Quand la réduction prépare un modèle supervisé, le meilleur critère n'est aucun des trois: on traite $k$ comme un hyperparamètre et on le choisit par validation croisée sur la performance du modèle (chapitres 5 et 6). Ce qui compte alors n'est pas la variance conservée mais l'erreur de validation obtenue.

Question 13.4

Sur les six épreuves fictives de la figure 13.3, combien de composantes faut-il garder, au minimum, pour expliquer au moins 90 % de la variance totale?

Standardiser ou non

L'ACP cherche les directions de plus grande variance, et la variance dépend des unités. Une caractéristique mesurée en francs a une variance un million de fois plus grande que la même mesurée en milliers de francs; rien n'a changé dans le monde, mais l'ACP la verra un million de fois plus importante. C'est le même phénomène que pour les distances du $k$ -PPV au chapitre 7, et il appelle la même réponse: quand les caractéristiques ont des unités différentes, on les standardise — on centre chaque colonne et on la divise par son écart type — avant l'ACP. La covariance des données standardisées est la matrice de corrélation, de diagonale unité.

Faut-il donc toujours standardiser? Non. Quand toutes les caractéristiques sont dans la même unité et que leurs écarts de variance ont un sens — les points de nos deux examens, les intensités des pixels d'une image, les températures de plusieurs stations —, la standardisation gonflerait des caractéristiques presque constantes, souvent du bruit, au même rang que les autres. On garde alors la covariance. La règle pratique: même unité et variances comparables, on peut garder la covariance; unités différentes, on standardise.

Question 13.5

Une équipe veut réduire 40 caractéristiques, mesurées dans des unités différentes, à quelques composantes avant d'entraîner un classifieur, sans fuite de données. Remettez les étapes dans l'ordre.

Glissez les éléments pour les mettre dans le bon ordre

Calculer la matrice de covariance de l'entraînement standardisé et ses premiers vecteurs propres

Standardiser l'entraînement avec ces statistiques

Projeter le test avec les moyennes, les écarts types et les directions de l'entraînement, puis l'évaluer une seule fois

Calculer moyennes et écarts types des 40 caractéristiques sur l'entraînement

Choisir le nombre de composantes par validation croisée, en refaisant standardisation et ACP dans chaque pli

Mettre de côté l'ensemble de test

La décomposition en valeurs singulières

Calculer $S = \frac{1}{n} X_{c}^{⊤} X_{c}$ puis ses vecteurs propres est correct, mais ce n'est pas ainsi que procèdent les bibliothèques. Elles factorisent directement la matrice centrée $X_{c}$ par la décomposition en valeurs singulières, vue au chapitre 12 d'Algèbre linéaire.

Démonstration. Comme $U$ est orthogonale, $U^{⊤} U = I$ , et

S = \frac{1}{n} X_{c}^{⊤} X_{c} = \frac{1}{n} V Σ^{⊤} U^{⊤} U Σ V^{⊤} = V \frac{Σ ^{⊤} Σ}{n} V^{⊤} .

La matrice $Σ^{⊤} Σ$ est diagonale $d \times d$ , de coefficients $σ_{j}^{2}$ . On a donc écrit $S = V D V^{⊤}$ avec orthogonale et diagonale de coefficients : c'est une diagonalisation de dans une base orthonormée. Ainsi , ce qui donne les directions et (13.9), et l'ordre est le même puisque est croissante sur les réels positifs. Enfin, la matrice des scores a pour coefficient le score , c'est-à-dire , dont la colonne est .

Sur le nuage des examens, les valeurs singulières de la matrice centrée $10 \times 2$ sont $σ_{1} = 300 = 17, 32$ et , et l'on retrouve et . Pourquoi passer par la SVD, si le résultat est le même? Parce que former du problème (Algèbre linéaire, chapitre 12): les petites valeurs singulières, élevées au carré, tombent sous la précision des nombres flottants et se perdent, alors que la SVD les calcule directement sur . Et parce que la SVD donne en une fois les directions et les scores .

La SVD dit aussi ce que vaut la meilleure approximation de rang faible d'un tableau, et c'est la clé de la suite du chapitre. Écrite colonne par colonne, $X_{c} = \sum_{j} σ_{j} u_{j} v_{j}^{⊤}$ est une somme de matrices de rang 1, rangées par importance décroissante. Tronquer la somme après termes donne , dont la ligne est exactement la reconstruction centrée de (13.6).

Ce théorème, publié par Carl Eckart et Gale Young en 1936, est énoncé au chapitre 12 d'Algèbre linéaire; nous l'admettons. Il redit le théorème 13.3 dans le langage des matrices — par (13.9), $\sum_{j > k} σ_{j}^{2} = n \sum_{j > k} λ_{j}$ , fois l'erreur de reconstruction moyenne —, mais il dit aussi davantage: la troncature de la SVD est la meilleure approximation de rang parmi les matrices de ce rang, et pas seulement parmi les projections. Sur les examens, la meilleure matrice de rang 1 laisse une erreur , la somme des dix de la figure 13.2.

L'ACP avec une bibliothèque

Avec scikit-learn, l'ACP s'ajuste sur l'entraînement et s'applique au test en trois lignes; avec numpy, la SVD de la matrice centrée donne tout:

from sklearn.decomposition import PCA
acp = PCA(n_components=2).fit(X_entr)       # moyenne et directions apprises sur l'entraînement
Z_test = acp.transform(X_test)               # scores du test, avec les paramètres de l'entraînement
print(acp.explained_variance_ratio_)         # parts de variance expliquée

import numpy as np
U, s, Vt = np.linalg.svd(X_entr - X_entr.mean(axis

Factorisation matricielle et recommandation

La SVD approche un tableau complet par un produit de deux tableaux minces. Beaucoup de tableaux réels sont incomplets: une plateforme de films connaît la note qu'un utilisateur a donnée aux quelques films qu'il a vus, pas aux milliers d'autres. Recommander, c'est deviner les cases vides. L'idée qui a dominé ce problème depuis la fin des années 2000 est de supposer que le tableau complet est, à peu près, de rang faible: quelques goûts de fond — l'action, le drame, la comédie, des dimensions que personne ne nomme — expliquent l'essentiel des notes.

On ne peut pas simplement appliquer la SVD: elle exige un tableau complet, et remplir les cases vides par une valeur arbitraire — zéro, la moyenne — fait apprendre ce remplissage autant que les vraies notes. La régularisation est indispensable: avec $k$ paramètres par utilisateur et peu de notes chacun, les vecteurs s'ajusteraient exactement aux quelques notes observées et prédiraient n'importe quoi ailleurs — le surapprentissage du chapitre 6 sous une forme nouvelle.

Le coût (13.11) n'est pas convexe en $(P, Q)$ ensemble, à cause du produit $p_{u}^{⊤} q_{i}$ . Mais il l'est en $P$ quand $Q$ est fixé, et réciproquement. C'est l'idée des moindres carrés alternés (alternating least squares, ALS): à $Q$ fixé, le coût se sépare en un problème par utilisateur, qui est une régression ridge (chapitre 6) dont les «caractéristiques» sont les vecteurs des objets qu'il a notés et les «étiquettes» ses notes, de solution

p_{u} = (i \in Ω_{u} \sum q_{i} q_{i}^{⊤} + γ I)^{- 1} i \in Ω_{u} \sum r_{u i} q_{i}, (13.12)

où $Ω_{u}$ est l'ensemble des objets notés par $u$ ; puis on fixe $P$ et l'on met à jour chaque $q_{i}$ par la formule symétrique. Chaque demi-étape minimise exactement $J$ par rapport à un bloc de variables, donc $J$ ne peut pas augmenter — le même argument que pour les deux étapes de Lloyd au chapitre 12 —, et comme $J \geq 0$ , la suite des coûts converge. Elle peut converger vers un minimum local: l'initialisation compte, comme pour les -moyennes.

Exemple 13.3 · Une factorisation de rang 2 par moindres carrés alternés

Cinq utilisateurs U1 à U5 ont noté de 1 à 5 certains de cinq films: F1 et F2 sont des films d'action, F3 et F4 des drames, F5 une comédie. Les données sont fictives; un point d'interrogation marque une note inconnue.

	F1	F2	F3	F4	F5
U1	5	4	1	?	2
U2	4	?	1	1	?
U3	1	1	5	4	?
U4	?	2	4	5	3
U5	5	5	?	2	3

Dix-neuf notes sont connues, six sont à deviner. Prenons $k = 2$ , $γ = 0, 1$ , et des vecteurs de films initiaux $q_{1} = (1, 1)$ , , , , . Mettons à jour U1, qui a noté F1, F2, F3 et F5. La matrice de (13.12) vaut

Il faut lire ces prédictions avec la prudence du chapitre 5. Rien ne garantit qu'elles soient justes: les six cases sont inconnues par construction, et la seule façon d'évaluer une méthode de recommandation est de masquer des notes connues, de les prédire et de mesurer l'erreur. Un autre modèle donne d'autres valeurs: la question 13.6 ajuste un modèle de rang 1 sur les notes centrées et trouve par exemple 4,58 pour la case (U2, F2) au lieu de 3,52. Et deux difficultés propres au domaine restent entières. Le démarrage à froid (cold start): un nouvel utilisateur n'a noté aucun film, son vecteur ne peut pas être appris, et il faut d'autres informations pour commencer. Et les notes manquantes ne manquent pas au hasard: on note surtout les films qu'on a choisi de voir, donc qu'on pensait aimer, et le modèle apprend sur un échantillon biaisé — un cas du biais d'échantillonnage du chapitre 1.

Question 13.6

On ajuste un modèle de rang 1 sur les notes de l'exemple 13.3, après leur avoir retiré la moyenne $\overset{r}{ˉ}$ des notes connues: $r_{u i} - \overset{r}{ˉ} \approx p_{u} q_{i}$ avec des nombres $p_{u}$ et $q_{i}$ . Complétez mise_a_jour(notes, fixes, gamma), qui renvoie pour chaque ligne de notes le nombre $\sum r f / (\sum f^{2} + γ)$ , les sommes portant sur les seules cases observées (celles qui ne valent pas None), f étant le facteur fixe de la colonne. C'est la formule (13.12) pour $k = 1$ . Le programme alterne utilisateurs et films cinquante fois et prédit les six notes manquantes.

recommandation.py

Plonger des mots dans un espace vectoriel

Comment donner à un programme le sens d'un mot? La représentation la plus directe est le vecteur indicateur (one-hot, chapitre 1): avec un vocabulaire de 50 000 mots, chaque mot est un vecteur de 50 000 coordonnées dont une seule vaut 1. Elle a deux défauts. Elle est énorme, et surtout elle est muette: deux vecteurs indicateurs distincts sont toujours orthogonaux, si bien que «chat» est aussi loin de «chien» que de «camion». Il faut une représentation où la géométrie reflète le sens.

L'idée qui le permet est ancienne et linguistique: c'est l'hypothèse distributionnelle, que le linguiste britannique John Rupert Firth résumait en 1957 par la formule souvent citée «you shall know a word by the company it keeps»: deux mots qui apparaissent dans les mêmes contextes ont des sens voisins. On compte donc, sur un grand corpus de textes, combien de fois chaque mot apparaît près de chaque mot de contexte, et l'on obtient une matrice de cooccurrences, énorme et creuse. La factoriser à rang faible, c'est exactement ce que nous venons de faire: chaque mot reçoit un vecteur dense de $k$ nombres — quelques centaines en pratique —, qu'on appelle son plongement (embedding).

On compare des plongements par leur cosinus plutôt que par leur distance parce que la norme d'un vecteur de mot reflète en bonne partie la fréquence du mot, pas son sens: un mot fréquent accumule de grands comptes. Le cosinus ne regarde que la direction.

Exemple 13.4 · Des cooccurrences aux vecteurs de mots

Voici une matrice de cooccurrences fictive, très petite: pour six mots, le nombre de fois où chacun apparaît à proximité de six mots de contexte dans un corpus imaginaire.

	mange	dort	caresse	roule	gare	pédale
chat	4	5	4	0	0	0
chien	5	3	4	1	0	0
lapin	5	2	1	0	0	0
voiture	0	0	0	5	4	0
camion	0	0	0	4	3	0
vélo	0	0	0	3	1	4

(Le chien «roule» une fois: il se roule par terre.) Calculons la SVD de cette matrice $6 \times 6$ , sans la centrer cette fois — on cherche une approximation de rang faible du tableau lui-même, au sens d'Eckart–Young. Ses valeurs singulières valent $11, 38$ ; $8, 80$ ; ; ; ; . La somme des carrés des comptes vaut 230, et les deux premières valeurs singulières en portent %. Gardons et plongeons chaque mot par la ligne correspondante de : chat , chien , lapin , voiture , camion , vélo . La première coordonnée mesure «animal», la seconde «véhicule».

En 2013, Tomas Mikolov et ses collègues ont publié word2vec (Efficient Estimation of Word Representations in Vector Space), une méthode qui n'écrit jamais la matrice de cooccurrences: elle apprend directement les vecteurs, par descente de gradient stochastique (chapitre 3), en entraînant un modèle très simple à prédire les mots du contexte à partir d'un mot (skip-gram) ou un mot à partir de son contexte (CBOW). Le lien avec ce chapitre a été établi l'année suivante par Omer Levy et Yoav Goldberg (Neural Word Embedding as Implicit Matrix Factorization, 2014): la variante skip-gram avec échantillonnage négatif factorise implicitement une matrice d'informations mutuelles entre mots et contextes, décalée d'une constante. Méthode neuronale et factorisation explicite sont deux chemins vers le même objet.

Ces vecteurs ont rendu célèbre une observation: des différences de vecteurs semblent encoder des relations. Le vecteur $m_{roi} - m_{homme} + m_{femme}$ serait proche de $m_{reine}$ . Reproduisons-la sur des vecteurs jouets de dimension 4, pour l'illustration — leurs coordonnées se lisent comme «royauté», «personne», «masculin» et «nourriture», ce qui n'est jamais le cas des coordonnées d'un vrai plongement:

Mot	roi	reine	homme	femme	prince	pomme	palais
royauté	0,8	0,7	0	0,1	0,6	0	0,7
personne	0,5	0,5	0,9	0,9	0,6	0	0
masculin	0,3	−0,3	0,3	−0,3	0,3	0	0
nourriture	0	0,1	0,1	0	0	1	0,1

Le vecteur cible vaut $m_{roi} - m_{homme} + m_{femme} = (0, 9; 0, 5; - 0, 3; - 0, 1)$ . Ses cosinus avec les sept mots, rangés, valent: reine , roi , palais , prince , femme , homme , pomme . «Reine» arrive en tête — et c'est la question 13.7 qui le programme.

Ce que l'analogie montre, et ce qu'elle ne montre pas

L'exemple «roi − homme + femme ≈ reine» est une illustration célèbre, pas une loi des plongements, et il faut en connaître les réserves. Les mots de départ sont exclus. Dans la recherche du mot le plus proche, on écarte par convention «roi», «homme» et «femme»; sans cette exclusion, le mot le plus proche du vecteur cible est souvent l'un d'eux — dans notre exemple jouet, «roi» vient juste après «reine». Les exemples sont choisis. Les analogies qui fonctionnent bien sont celles qu'on montre; beaucoup de relations ne se laissent pas réduire à une différence de vecteurs. Les plongements héritent des biais du corpus. Des vecteurs appris sur des textes réels reproduisent les associations stéréotypées de ces textes, entre métiers et genres par exemple; Bolukbasi et ses collègues l'ont montré dès 2016 dans un article au titre parlant, Man is to Computer Programmer as Woman is to Homemaker?. Ce sont les biais des étiquettes et des données du chapitre 1, sous une forme plus difficile à voir parce qu'ils sont répartis sur des centaines de coordonnées sans nom.

Question 13.7

Complétez cosinus(a, b), qui renvoie la similarité cosinus (13.13) de deux vecteurs, et analogie(a, b, c, vecteurs), qui renvoie le mot dont le vecteur a le plus grand cosinus avec vecteurs[a] - vecteurs[b] + vecteurs[c], en excluant les trois mots a, b et c. Le programme reprend les vecteurs jouets du texte.

analogies.py

Les plongements ont dépassé les mots. Les vecteurs $p_{u}$ et $q_{i}$ de la factorisation matricielle sont des plongements d'utilisateurs et de films; on plonge de même des images, des produits, des molécules, et l'on cherche des objets semblables par le cosinus. Avec des millions de vecteurs de plusieurs centaines de dimensions, cette recherche est la recherche de plus proches voisins du chapitre 7, en grande dimension: elle se fait par les méthodes approchées évoquées à la fin de ce chapitre-là. Les transformeurs du chapitre 11 partent eux aussi d'une table de plongements, une ligne fixe par jeton; ce sont les sorties de leurs couches d'attention qui dépendent du contexte, si bien qu'un même mot y est représenté par un vecteur différent dans chaque phrase.

Les limites des méthodes linéaires

L'ACP cherche un sous-espace: une droite, un plan, un hyperplan. Elle échoue dès que la structure des données est courbe. Prenez des points régulièrement répartis sur un cercle. Ils ne dépendent que d'un seul paramètre, l'angle: leur dimension intrinsèque est 1. Pourtant, leur matrice de covariance vaut $\frac{r ^{2}}{2} I$ — pour $n \geq 3$ points équidistants sur un cercle de rayon $r$ —, ses deux valeurs propres sont égales, et toute droite capte exactement la moitié de la variance. L'ACP ne voit aucune direction privilégiée et ne peut réduire ce nuage à une dimension sans en perdre la moitié. Les données réelles sont souvent ainsi: les images d'un même objet sous différents angles, les phrases qui disent la même chose de diverses façons, forment des surfaces courbes de faible dimension, des , plongées dans un grand espace.

Trois familles de méthodes vont au-delà. L'ACP à noyau (kernel PCA) applique l'astuce du noyau du chapitre 9: elle fait une ACP dans l'espace des caractéristiques $φ (x)$ sans jamais le calculer, en diagonalisant la matrice de Gram centrée $n \times n$ . Les auto-encodeurs, définis au chapitre 11, sont des réseaux de neurones entraînés à reconstruire leur entrée en passant par une couche étroite; on sait qu'un auto-encodeur linéaire entraîné par la perte carrée retrouve le sous-espace des $k$ premières composantes principales — l'ACP est leur cas linéaire —, et les non-linéarités leur permettent de suivre des variétés courbes. Enfin, des méthodes de visualisation comme t-SNE (van der Maaten et Hinton, 2008) et UMAP (McInnes, Healy et Melville, 2018) placent les points dans le plan de façon à préserver leurs voisinages: deux points proches dans l'espace d'origine restent proches sur la carte.

Une carte t-SNE ou UMAP n'est pas une mesure

Ces méthodes produisent des images souvent spectaculaires, faites d'îlots bien séparés. Elles ne préservent que les voisinages locaux, et presque rien d'autre. Les distances entre îlots ne disent pas grand-chose: deux groupes éloignés sur la carte ne sont pas forcément plus différents que deux groupes voisins. La taille d'un îlot n'indique pas la dispersion du groupe: la méthode tend à égaliser les densités. La forme dépend des hyperparamètres — la «perplexité» de t-SNE, le nombre de voisins d'UMAP — et de la graine aléatoire: deux exécutions donnent deux cartes. Et des données sans aucune structure de groupes peuvent produire des îlots. Utilisez-les pour regarder des données et formuler des hypothèses, jamais comme des coordonnées sur lesquelles on calcule des distances, ni comme la preuve qu'il existe des groupes: pour cela, il y a le partitionnement du chapitre 12 et ses critères.

Question 13.8

Une équipe projette 10 000 cellules décrites par 2 000 mesures avec t-SNE et observe trois îlots, dont deux très éloignés du troisième et l'un deux fois plus étalé que les autres. Quelles conclusions sont légitimes à ce stade? (Plusieurs réponses possibles.)

Plusieurs réponses possibles

Ce que le cours a construit

Ce chapitre est le dernier, et il est l'occasion de regarder le chemin parcouru. Treize chapitres ont présenté des dizaines de méthodes; elles reposent sur un nombre étonnamment petit d'idées, que l'on retrouve presque toutes dans ce chapitre.

Un tableau, une perte, une optimisation. Le chapitre 1 a posé le cadre: un tableau de $n$ exemples et $d$ caractéristiques, un modèle qui est une famille de fonctions, une perte qui dit ce que coûte une erreur, et l'entraînement comme minimisation du risque empirique. Presque tout ce qui a suivi en est une instance. La régression linéaire (chapitre 2) minimise une perte carrée, la régression logistique (chapitre 4) une entropie croisée, les machines à vecteurs de support (chapitre 9) une perte charnière régularisée, les réseaux de neurones (chapitres 10 et 11) toutes ces pertes à la fois sur des modèles beaucoup plus souples. Même les méthodes non supervisées ont leur perte: l'inertie pour les $K$ -moyennes (chapitre 12), l'erreur de reconstruction pour l'ACP, le coût (13.11) pour la factorisation. Quand vous rencontrerez une méthode nouvelle, demandez-vous d'abord quel est son modèle, quelle est sa perte et comment on l'optimise: la réponse la situera presque toujours.

L'algèbre linéaire est le langage commun. Les moindres carrés du chapitre 2 sont une projection orthogonale de $y$ sur l'espace des colonnes de $\tilde{X}$ ; l'ACP est une projection orthogonale des exemples sur un sous-espace choisi à partir de $X$ seul. La descente de gradient du chapitre 3 converge à une vitesse fixée par les valeurs propres de la hessienne, et la standardisation l'accélère en les égalisant; l'ACP lit dans les valeurs propres de $S$ la répartition de la variance. La ridge du chapitre 6 rend inversible $\tilde{X}^{⊤} \tilde{X} + λ I^{'}$ en relevant ses plus petites valeurs propres, et l'on peut montrer qu'elle rétrécit le plus les coefficients dans les directions principales de faible variance — celles que l'ACP jetterait. Le même théorème spectral sert partout.

Optimiser, et savoir quand on a trouvé le bon minimum. La descente de gradient (chapitre 3) est l'outil universel; la convexité dit quand elle trouve le minimum global — moindres carrés, régression logistique, SVM — et son absence explique les minima locaux des réseaux de neurones, des $K$ -moyennes et de la factorisation matricielle. L'optimisation alternée est revenue trois fois: les deux étapes de Lloyd et l'algorithme EM au chapitre 12, les moindres carrés alternés dans ce chapitre. Pour Lloyd et pour les moindres carrés alternés, l'argument est le même: chaque étape minimise exactement par rapport à un bloc de variables, donc le coût ne monte jamais. Pour EM, la monotonie vient d'ailleurs: d'une minoration de la log-vraisemblance par l'inégalité de Jensen (théorème 12.6), que chaque étape relève.

L'erreur d'entraînement ment, et toute la méthodologie en découle. Le théorème 1.1 a montré que le risque empirique n'estime honnêtement le risque réel que pour un prédicteur choisi indépendamment des données. D'où l'ensemble de test consulté une seule fois, la validation croisée, les fuites de données (chapitre 5) — et, dans ce chapitre, l'ACP ajustée sur l'entraînement seul. D'où aussi le compromis biais–variance (chapitre 6), qui règle le degré d'un polynôme, le $λ$ de la ridge, le $k$ des voisins (chapitre 7), la profondeur d'un arbre, le nombre de caractéristiques tirées à chaque nœud d'une forêt et le nombre d'itérations du boosting (chapitre 8), la largeur d'un noyau gaussien (chapitre 9), l'arrêt précoce d'un réseau (chapitre 10) et le nombre de composantes quand l'ACP prépare un modèle (chapitre 13). Un hyperparamètre se choisit sur des données que l'entraînement n'a pas vues. Sans étiquettes, ce recours manque: le nombre de groupes du chapitre 12 se choisit sur les mêmes données, par le coude ou la silhouette, et c'est une raison de plus de le tenir pour une hypothèse.

La représentation compte autant que le modèle. Les caractéristiques polynomiales du chapitre 2, la standardisation des chapitres 3 et 7, les noyaux du chapitre 9, les couches cachées des chapitres 10 et 11, et enfin les composantes principales et les plongements de ce chapitre sont autant de façons de changer de représentation pour qu'un modèle simple réussisse. L'apprentissage profond a ceci de particulier qu'il apprend la représentation en même temps que le modèle; les plongements de mots en sont un exemple, et les modèles de langage du chapitre 11 en sont le prolongement.

Les données ne sont pas neutres. Le chapitre 1 a nommé les biais d'échantillonnage, d'étiquetage, de substitution et de rétroaction. Ils sont revenus sous d'autres formes: le taux de base qui ruine une précision (chapitre 5), les notes manquantes qui ne manquent pas au hasard et les associations stéréotypées des plongements dans ce chapitre. Une méthode d'apprentissage reproduit fidèlement ce que contiennent ses données, y compris ce qu'on aurait préféré qu'elle n'apprenne pas, et aucune métrique moyenne ne le révèle à elle seule.

Ce cours a laissé de côté des pans entiers du domaine: l'apprentissage par renforcement, nommé au chapitre 1; l'inférence causale, qui répond aux questions que la corrélation d'un coefficient ne tranche pas (chapitre 2); les modèles probabilistes graphiques; les séries temporelles, où l'hypothèse i.i.d. tombe par construction; la théorie de l'apprentissage, qui borne l'écart entre risque empirique et risque réel pour toute une classe de modèles. Vous avez maintenant les outils pour les aborder: un tableau, une perte, une optimisation, une évaluation honnête — et l'habitude de demander, devant chaque résultat, sur quelles données il a été mesuré.

Synthèse

On réduit la dimension pour visualiser, compresser, débruiter ou préparer un modèle, en représentant chaque exemple par $k$ nombres au lieu de $d$ . L'ACP centre les données, calcule la covariance empirique $S = \frac{1}{n} X_{c}^{⊤} X_{c}$ (symétrique, semi-définie positive) et projette sur ses vecteurs propres. Ici, désigne une valeur propre, et non plus le coefficient de régularisation du chapitre 6.

Série d'exercices du chapitre 13Exercice 1 sur 5

Question 13.9

Un nuage a pour matrice de covariance $S = (10665)$ . Quelle est sa plus grande valeur propre $λ_{1}$ ?

Exercices

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

Exercice 13.1 · Une ACP à la main

On considère les quatre points $(1, - 1)$ , $(3, 1)$ , $(3, 5)$ et $(5, 3)$ du plan (données fictives).

Calculez le point moyen et la matrice de covariance empirique $S$ (division par $n$ ).
Calculez les valeurs propres de et un vecteur propre unitaire pour chacune.

Exercice 13.2 · Unités, standardisation et matrice de corrélation

On considère deux caractéristiques de variances $s_{11}$ , $s_{22}$ et de covariance $s_{12}$ , de coefficient de corrélation $r = s_{12} / s_{11} s_{22}$ .

Exercice 13.3 · La SVD du nuage des examens

On note $X_{c}$ la matrice centrée $10 \times 2$ du nuage des examens, dont les lignes sont les écarts de l'exemple 13.1.

Sans calculer la SVD, déduisez de l'exemple 13.1 et du théorème 13.4 les valeurs singulières $σ_{1}$ et $σ_{2}$ de .

Exercice 13.4 · Un pas de moindres carrés alternés à la main

Deux utilisateurs ont noté trois objets; deux notes manquent (données fictives):

R = (42 ? 1 2 ?) .

Exercice 13.5 · Variance totale, erreur de rang

k

et deuxième composante (démonstration)

Soit $S$ la matrice de covariance empirique d'un nuage de $R^{d}$ , de valeurs propres $λ_{1} \geq \dots \geq λ_{d}$ et de vecteurs propres orthonormés .

Références

Hastie, T., Tibshirani, R. et Friedman, J., The Elements of Statistical Learning, Springer, 2ᵉ éd., 2009, section 14.5 (composantes principales, courbes et surfaces principales).
Bishop, C. M., Pattern Recognition and Machine Learning, Springer, 2006, chap. 12 (variables latentes continues: ACP sous ses deux formulations, ACP probabiliste et à noyau).
Goodfellow, I., Bengio, Y. et Courville, A., Deep Learning, MIT Press, 2016, chap. 2 (décomposition propre, SVD, et l'ACP dérivée comme exemple d'algèbre linéaire).
Pearson, K., «On lines and planes of closest fit to systems of points in space», Philosophical Magazine, 1901.
Mikolov, T., Chen, K., Corrado, G. et Dean, J., «Efficient Estimation of Word Representations in Vector Space», 2013 (l'article qui introduit word2vec).
Koren, Y., Bell, R. et Volinsky, C., «Matrix Factorization Techniques for Recommender Systems», IEEE Computer, 2009.

Paire	lignes brutes	plongements ( $k = 2$ )
chat, chien	0,9459	0,9932
chat, voiture	0,0000	−0,0014
voiture, vélo	0,5819	1,0000
chien, voiture	0,1093	0,1148

Objectifs du chapitre

Pourquoi réduire la dimension

Centrer les données et mesurer leur dispersion

Projeter sur une direction

La première composante principale

Plusieurs composantes

Standardiser ou non

La décomposition en valeurs singulières

Factorisation matricielle et recommandation

Plonger des mots dans un espace vectoriel

Les limites des méthodes linéaires

Ce que le cours a construit

Synthèse

Exercices

Références

Le score

La reconstruction

L'erreur de reconstruction

Un étudiant atypique?