Comprendre les mathématiques derrière la réduction de dimension dans la reconnaissance faciale (1)

Lisez mes preuves adaptées aux débutants pour explorer l’application de l’algèbre linéaire

La réduction de dimension est une technique courante en informatique que la plupart d’entre vous ont probablement rencontrée d’une manière ou d’une autre, mais tout le monde ne comprend pas comment elle est déduite mathématiquement. Dans cette série d’articles, je vais vous guider à travers l’algèbre linéaire derrière la réduction de dimension à travers un exemple simple de reconnaissance faciale. En plus de comprendre les mathématiques, vous verrez également comment la réduction de dimension peut être utile pour simplifier la tâche de reconnaissance d’image. En particulier, je parlerai des vecteurs propres / valeurs propres, du théorème spectral et de l’analyse en composantes principales.

Pourquoi une réduction de dimension est nécessaire

Pour vous rafraîchir la mémoire sur la réduction des dimensions, commençons par un exemple hypothétique. Le département de communication du Middlebury College stocke 3 000 photos prises par chaque étudiant du Middlebury College. La directrice du département a récemment trouvé une photo d’un étudiant dans un journal local et elle voulait savoir si cet étudiant appartenait à Middlebury.

Concevoir un modèle efficace de reconnaissance faciale est difficile, grâce à la nature multidimensionnelle des images. Si nous limitons la portée de notre discussion aux images en noir et blanc, nous pouvons penser à une image de m × n pixels comme une matrice remplie de nombres réels entre 0 (noir) et 255 (blanc). Chaque matrice a une dimension de m × n, chaque pixel représentant une dimension.

Si nous supposons que chaque photo d’élève a une dimension de 1 600 × 1 200 et que nous comparons la nouvelle image avec chacune des 3 000 photos pixels par pixels, nous devrons effectuer 3 000 × 1 600 × 1 200 = 5 760 000 000 de comparaisons. Notre objectif est de réduire la dimension des photos des élèves sans perdre (ou avec une perte minimisée de) la variance capturée. Avant de me plonger dans les étapes spécifiques, je veux d’abord présenter le concept de base de la variance.

Un aperçu intuitif de la variance

La variance est la moyenne de la différence au carré de la moyenne. Par exemple, étant donné une liste de nombres réels x_1 ... x_n , nous définissons la variance comme:

Dans cette application, la variance est ce qui distingue le nez plat d’une personne du nez crochu d’une autre personne. Nous voulons que la variance parmi les 3000 photos des élèves de Middlebury soit aussi élevée que possible, car une variance élevée améliore la précision de la reconnaissance. Intuitivement, la variance augmente avec le nombre de dimensions. Il est plus facile d’identifier la photo de votre ami si vous recevez une image complète plutôt que de simples pixels autour du nez. Pourtant, certaines dimensions peuvent être répétitives. Par exemple, les pixels côte à côte peuvent avoir des valeurs très similaires, car ils capturent le même type de variance du visage.

Rappelez-vous que dans notre exemple, le directeur a commencé avec 1 600 × 1 200 = 1 920 000 dimensions. Dans la partie restante de cet article, je montrerai comment un changement de base peut nous aider à réduire le nombre de dimensions à t & lt; 1.920,00 sans perdre aucune variance. Dans le prochain article, je montrerai comment l’analyse en composantes principales peut réduire davantage le nombre de dimensions à m ≪ t tout en préservant la majeure partie de la variance.

Construction de la matrice de covariance

Commençons par construire un véritable espace vectoriel contenant toutes les images des élèves. Nous convertissons chaque matrice de l’image de l’étudiant en un vecteur ligne en concaténant ses pixels lignes par lignes. Par exemple, si K₁ représente l’image de l’élève 1, alors:

Ensuite, nous combinons les vecteurs de ligne k₁… k₃₀₀₀ ensemble pour former une matrice de 3 000 × 1 920 000 K_all . Chaque colonne de K_all représente une dimension (correspondant à un pixel) et chaque ligne représente un vecteur de visage kᵢ . Ensemble, tous les vecteurs de ligne de K_all forment notre espace de visage ℝ¹⁹²⁰⁰⁰⁰:

Pour souligner les différences entre les images et pour simplifier les calculs futurs, nous calculons d’abord le vecteur de visage moyen , c’est-à-dire la valeur moyenne de chaque pixel sur les 3 000 images de visage. Ensuite, nous normalisons chaque vecteur de visage kᵢ en soustrayant le vecteur de visage moyen de ce vecteur. Soit vᵢ le vecteur de différence de face iᵗʰ après normalisation, alors:

De même, nous combinons les vecteurs de différence de face v₁… v₃₀₀₀ pour former la matrice de variance A. Chaque colonne de A représente une dimension et chaque ligne représente un vecteur de différence de face:

Pour maximiser la variance avec le moins de dimensions, nous voulons que chaque dimension soit indépendante, c’est-à-dire que la variance capturée dans la dimension x ne doit pas chevaucher la variance capturée dans la dimension y. En mathématiques, la covariance est le concept qui mesure la variabilité conjointe de deux dimensions. La formule de covariance indique que:

Dans notre cas, puisque nous avons normalisé nos vecteurs de visage x̄ = ȳ = 0 , nous pouvons directement calculer la covariance entre dimension x et y par le produit scalaire des colonnes x et y de la variance matrice A. Soit d_x et d_y les colonnes xᵗʰ et yᵗʰ de A (correspondant aux pixels x et y). Soit également α ⅟3000, l’inverse du nombre de lignes dans A, alors:

Pour établir la covariance entre deux dimensions dans la matrice A, nous construisons la matrice de covariance C. Soit dᵢ la colonne iᵗʰ de la matrice A:

Combinez les équations 2 et 3, nous avons:

La matrice de covariance C est symétrique, car nous pouvons déduire de l’équation 2 que:

Les entrées diagonales de C indiquent la variance sur chaque dimension.

Changement de base orthogonale: le théorème spectral

Une fois que nous avons construit la matrice de covariance C, nous voulons trouver une nouvelle base orthogonale sous laquelle Cov (x, y) = 0, pour tout x et y représentés dans la nouvelle base et x ≠ y. Cette nouvelle base est optimale puisque l’utilité de la variance sur chaque dimension serait maximisée, car il n’y aurait pas de chevauchement de variance entre les dimensions. Grâce au Théorème Spectral et à la symétrie de C que nous avons montré, nous pouvons effectuer un changement de base sur C:

où D est une matrice diagonale réelle et Q est une matrice orthogonale. Les valeurs propres de C apparaissent sur la diagonale de D. Les colonnes de Q, q₁, q₂,…, q₁₉₂₀₀₀₀ sont les vecteurs propres orthonormés correspondants qui composent la nouvelle base orthonormée que nous désirons.

Par un changement de base, q₁, q₂,…, q₁₉₂₀₀₀₀ forment maintenant une nouvelle base orthonormée de notre espace des faces, la covariance entre deux dimensions quelconques de cette base étant de 0. Selon le Théorème spectral, cette base orthogonale se trouve être une base propre. Nous pouvons vérifier que cette base propre est orthogonale car D est une matrice diagonale, ce qui rend Cov (x, y) = 0, pour tout x et y représentés dans la base et x ≠ y.

Jusqu’à présent, nous avons éliminé la covariance entre les dimensions. Pourtant, les lecteurs attentifs peuvent remarquer que nous avons toujours le même nombre de dimensions, puisque la nouvelle base orthogonale se compose de 1 920 000 vecteurs propres et chaque vecteur propre couvre une dimension. Si tel est le cas, comment la construction d’une base propre orthogonale nous aide-t-elle à réduire la dimension? Il s’avère que nous pouvons supprimer en toute sécurité tous les vecteurs propres de la base propre orthogonale si ces vecteurs propres correspondent à une valeur propre nulle, car ils ne contribuent pas à la variance totale. Pour vérifier cette affirmation, je vais procéder pour prouver que la variance sur la dimension parcourue par chaque vecteur propre est égale à la valeur propre associée à ce vecteur propre ( Lemme 1 ), de sorte que la valeur propre nulle indique une variance nulle. Si vous ne souhaitez pas voir la preuve détaillée, vous pouvez passer à la section suivante.

Lemme 1: Soit u un vecteur propre de la base propre orthonormée de la matrice C = α AᵗA, où α est l’inverse du nombre de lignes dans A. Soit λ la valeur propre correspondante de u. Soit le v_1...v_n les vecteurs lignes normalisés de A. Soit σᵤ² la variance de v_1 ... v_n sur la dimension étendue par u. Nous affirmons que σᵤ² = λ.

Pour prouver le Lemme 1 , soit pᵢ le poids projeté de vᵢ sur la dimension enjambée par u, selon la formule de projection orthogonale, sous le produit intérieur euclidien:

Soit p le vecteur de mesure projeté contenant p_1 ... p_n :

Depuis que v_1 ... v_n a été normalisé, v_1 + ... + v_n = 0 . Par conséquent:

Selon la formule de variance:

Combinez les équations 6 et 8, nous avons:

Rappelez-vous que pour deux vecteurs v et w de même longueur:

Combinez les équations 9 et 10, nous avons:

Combinez les équations 9 et 11, nous avons:

Après avoir prouvé le Lemme 1 , nous avons maintenant confirmé que la suppression des vecteurs propres avec une valeur propre nulle n’affecterait pas la variance. De plus, la variance totale capturée dans l’espace des faces est la somme de toutes les valeurs propres de C.

Conversion entre AᵗA et AAᵗ

Jusqu’à présent, nous avons prouvé que les vecteurs propres à valeur propre nulle ne contribuent pas à la variance. Si nous supprimons t vecteurs propres à valeur propre nulle de la base propre de C, le sous-espace T formé par les vecteurs propres restants n’aurait qu’une dimension de 1,920,000 - t , mais T capturerait la même quantité de variance que notre l’espace du visage d’origine, qui a une dimension de 1 920 000. La question est: comment maximiser t et réduire ainsi autant de dimensions que possible?

Soit Cᵗ = αAAᵗ. On remarque que Cᵗ n’a qu’une dimension de 3000 × 3000, nettement inférieure à celle de C = αAᵗA. Ainsi, nous procédons en explorant la relation entre Cᵗ et C.Selon le théorème spectral, Cᵗ possède également une base propre orthonormée, car il est clair que Cᵗ est symétrique:

Si nous pouvons prouver que tout vecteur propre dans C avec une valeur propre non nulle a un vecteur propre correspondant dans Cᵗ avec la même valeur propre, nous pouvons montrer que la somme des valeurs propres dans C est la même que la somme des valeurs propres dans le plus petit Cᵗ. À la lumière du lemme 1, nous pouvons démontrer que la base propre de Cᵗ capture la même quantité de variance que la base propre de C. Par conséquent, nous pouvons maximiser t jusqu’à 1 920 000–3 000 = 1 917 000. Par conséquent, nous pouvons former un sous-espace T de dimension 3 000, qui porte la même quantité de variance avec notre espace facial original de 1 920 000 dimensions.

Nous procédons à la démonstration de l’affirmation ci-dessus que tout vecteur propre en C avec une valeur propre non nulle a un vecteur propre correspondant en Cᵗ avec la même valeur propre:

Lemme 2: Si q est un vecteur propre de α AᵗA (α ≠ 0) avec une valeur propre λ non nulle, alors Aq est un vecteur propre de α AAᵗ de même valeur propre λ.

Pour prouver le lemme 2 , soit q un vecteur propre de α AᵗA qui correspond à une valeur propre λ non nulle:

Nous devons encore prouver que Aq ≠ 0. Si Aq = 0, alors:

Cependant, le fait que q soit un vecteur propre avec une valeur propre λ non nulle implique que q ≠ 0 et λ ≠ 0. Une contradiction est donc apparue. Par conséquent, Aq ≠ 0. La preuve est complète.

Par la même logique, si q est un vecteur propre de Cᵗ, alors Aᵗq est le vecteur propre correspondant de C, puisque (αAᵗA) Aᵗq = Aᵗ (αAAᵗ) q = Aᵗλq = λ (Aᵗq). Soit maintenant x₁… x₃₀₀₀ la base propre du Cᵗ beaucoup plus petit. À la lumière du Lemme 2 , nous pouvons reconvertir x₁… x₃₀₀₀ en vecteurs propres dans C en multipliant chacun par Aᵗ. Soit tᵢ le vecteur propre en C qui partage la même valeur propre avec xᵢ en Cᵗ, alors:

En conséquence, t₁… t₃₀₀₀ forment le sous-espace T que nous avons introduit auparavant et qui capture la même quantité de variance que notre espace facial d’origine. Si notre objectif est de réduire la dimension sans perdre de variance. nous pouvons nous arrêter ici et laisser T être notre dernier sous-espace propre. Nous appelons chaque vecteur propre t₁… t₃₀₀₀ une face propre.

Résumé et aperçu de l’article suivant

Dans cet article, notre objectif était de préserver toute la variance de l’espace du visage. En contrepartie, nous devions encore inclure des dimensions avec des variances relativement faibles, ce qui augmentait la difficulté de calcul. Si nous sommes prêts à sacrifier une perte mineure de variance en échange de gains importants d’efficacité de calcul, nous pouvons réduire davantage la dimension du sous-espace de la face propre en ne sélectionnant que les dimensions avec les plus grandes variances. Dans le prochain article, je présenterai comment faire cela grâce à l’analyse en composantes principales (ACP). Comme cet article, je me concentrerai sur la preuve mathématique de l’ACP. Pour conclure cette série, je parlerai également de la façon de projeter des photos originales d’étudiants sur les sous-espaces de faces propres que nous créerons via PCA.

Référence:

[1] j2kun. Eigenfaces, pour la reconnaissance faciale. https://jeremykun.com/2011/07/27/eigenfaces .

[2] Peter Olver et Chehrzad Shakiban. Algèbre linéaire appliquée. Springer, 2006

[3] Matthew Turk et Alex Pentland. Eigenfaces pour la reconnaissance. pages 71–86. Journal of Cogni-tive Neuroscience, 1991.

[4] Photo de couverture créditée sur https://yutsumura.com/