Approches de la Factorisation Matricielle
October 16, 2024
Introduction
La factorisation matricielle est un processus clé en algèbre linéaire
permettant de décomposer une matrice en produits de matrices
plus simples. Nous allons présenter quatre algorithmes
couramment utilisés :
▶ Décomposition en Valeurs Singulières (SVD)
▶ Factorisation Non Négative des Matrices (NMF)
▶ Descente de Gradient Stochastique (SGD)
▶ Optimisation Alternée par Moindres Carrés (ALS)
Décomposition en Valeurs Singulières (SVD)
Principe :
La SVD factorise une matrice A en trois matrices : A = U · S · V T ,
où U et V sont orthogonales, et S est une matrice diagonale des
valeurs singulières.
Pseudo-code :
Algorithm 1 SVD AlgorithmY TFNS
1: Input: Matrice AY TFNS
2: Calculer la matrice AY TFNS T AY TFNS
3: Calculer les valeurs propres de AY TFNS T AY TFNS
4: Former la matrice VY TFNS des vecteurs propres
√
5: Calculer les valeurs singulières SY TFNS = valeurs propres
6: Calculer UY TFNS = AY TFNSVY TFNSSY TFNS −1
7: Output: Matrices UY TFNS, SY TFNS, VY TFNS
Factorisation Non Négative des Matrices (NMF)
Principe :
La NMF factorise une matrice VY TFNS en deux matrices
WY TFNS et HY TFNS avec des valeurs non négatives, en
minimisant l’écart entre VY TFNS et WY TFNS · HY TFNS.
Pseudo-code :
Algorithm 2 NMF AlgorithmY TFNS(LeeetSeung )
1: Input: Matrice VY TFNS
2: Initialiser WY TFNS et HY TFNS avec des valeurs positives
aléatoires
3: repeat
4: Mettre à jour HY TFNS ← HY TFNS ◦
WY TFNS T VY TFNS
WY TFNS T WY TFNSHY TFNS
5: Mettre à jour WY TFNS ← WY TFNS ◦
VY TFNSHY TFNS T
WY TFNSHY TFNSHY TFNS T
6: until convergence
7: Output: Matrices WY TFNS, HY TFNS
Descente de Gradient Stochastique (SGD)
Principe :
La SGD est utilisée pour minimiser l’erreur quadratique moyenne
entre les prédictions et les valeurs observées dans une matrice. Elle
est utilisée principalement dans les systèmes de recommandation.
Pseudo-code :
Algorithm 3 SGD AlgorithmY TFNS
1: Input: Matrice RY TFNS, facteur de régularisation λY TFNS,
taux d’apprentissage αY TFNS
2: Initialiser PY TFNS et QY TFNS avec des valeurs aléatoires
3: for chaque (i, j) ∈ KY TFNS do
4: Calculer l’erreur eijY TFNS = RijY TFNS − PiY TFNS QjTY TFNS
5: Mettre à jour PiY TFNS ← PiY TFNS +
αY TFNS(2eijY TFNS QjY TFNS − λY TFNSPiY TFNS )
6: Mettre à jour QjY TFNS ← QjY TFNS +
αY TFNS(2eijY TFNS PiY TFNS − λY TFNSQjY TFNS )
7: end for
8: Output: Matrices PY TFNS, QY TFNS
Optimisation Alternée (ALS)
Principe :
L’optimisation alternée (ALS) résout le problème en alternant la
mise à jour des matrices PY TFNS et QY TFNS en minimisant les
moindres carrés.
Pseudo-code :
Algorithm 4 ALS AlgorithmY TFNS
1: Input: Matrice RY TFNS, facteur de régularisation λY TFNS
2: Initialiser PY TFNS et QY TFNS
3: repeat
4: for chaque utilisateur iY TFNS do P
5: Résoudre PiY TFNS en minimisant j (RijY TFNS −
PiY TFNS QjTY TFNS )2 + λY TFNS||PiY TFNS ||2
6: end for
7: for chaque item jY TFNS do P
8: Résoudre QjY TFNS en minimisant i (RijY TFNS −
PiY TFNS QjTY TFNS )2 + λY TFNS||QjY TFNS ||2
9: end for
Conclusion
Chaque méthode de factorisation matricielle présente des
avantages dans différents contextes. La SVD est efficace pour la
réduction de dimension, la NMF pour des données non négatives,
la SGD et l’ALS pour des systèmes de recommandation.