INF311 : Calcul Scientifique
Factorisation Matricielle
Algorithmes à Écrire :
-Méthode de résolution exacte sur grandes matrices
creuses(SVD)
-Descente de gradient stochastique (SGD)
-Optimisation alternée
-Algorithme multiplicatif
Membres de groupe :
TAGNE TALLA IDRISS CHANEL 19M2351
NZOMUTCHA TAFFOR SEVERIN WILFRIED 19M2157
NSEGUE ROMAIN STEVE BIENVENU 22Y1026
NGANDJOUNG NEALI JACQUES LANDRY 19M2946
DOGMO GATSI REINE 21U2391
Enseignant :
Dr Messi
I. Méthode de Résolution pour une
grande matrice Creuse
(Décomposition Singulière)
i. Principe de la méthode
Le principe de la factorisation dans cette méthode repose sur la détermination de valeurs singulières
(Rappel : On appelle valeur singulière de Y toute racine carrée d'une valeur propre de YTY,
autrement dit tout réel positif σ tel qu'il existe un vecteur unitaire u dans Km et un vecteur
unitaire v dans Kn vérifiant :
YTu = σv et Yv = σu
Les vecteurs u et v sont appelés vecteur singulier à gauche et vecteur singulier à droite pour σ,
respectivement.
)
de matrices YTY ou YYT et des vecteurs Singuliers des matrices YTY et de YYT. .
Cet Algorithme vise à écrire un matrice Y sous la forme UEVT où U est la matrice des vecteurs
singuliers à gauche de la matrice Y , E la matrice des valeurs singulières et V la matrice des
vecteurs singuliers à droite de la matrice Y .
ii. Programme Matlab
iii. Vérification De L’algorithme
Voici un exemple pratique d’une matrices Décomposer suivant l’algorithme SVD(Singlar Value
Decomposition). Prit sur [Link]
Voici pour ce même cas le résultat de notre algorithme
Pourquoi les matrices U et V ne sont-elles pas les même que dans l’exemple ?:
Ces matrices ne sont pas les même en fait car aux valeurs singulière de Y on peut avoir plusieurs
vecteurs singuliers ( les valeurs singulières sont dégénérer).
II. Descente de gradient
stochastique (SGD)
A. Présentation
La SGD est très utile lorsque le coût est différenciable en termes de complexité temporelle
Problème :
Ici, le problème de minimiser le coût se pose d’où l’équation :
Ce qui donne une bonne interpretation du cout car est différentiable.
Sont les formules de mise a jours.
B. Code MATLAB :
function [U, V] = matrixFactorizationSGD(Y, K, alpha, beta, num_iter)
% Factorisation matricielle par descente de gradient stochastique
% Entrées :
% Y : Matrice d'évaluation des utilisateurs (n_users x n_items)
% K : Nombre de dimensions des facteurs latents
% alpha : Taux d'apprentissage (learning rate)
% beta : Terme de régularisation (penalty term)
% num_iter : Nombre d'itérations
[n_users, n_items] = size(Y);
% Initialisation des matrices U (facteurs utilisateurs) et V (facteurs items)
U = rand(n_users, K); % n_users x K
V = rand(n_items, K); % n_items x K
% Parcours sur un nombre défini d'itérations
for iter = 1:num_iter
for i = 1:n_users
for j = 1:n_items
if Y(i, j) > 0 % Seule condition si l'utilisateur a noté cet item
% Calcul de l'erreur entre la valeur réelle et la prédiction
prediction = U(i, :) * V(j, :)';
error = Y(i, j) - prediction;
% Mise à jour des facteurs latents avec la descente de gradient
U(i, :) = U(i, :) + alpha * (2 * error * V(j, :) - beta * U(i, :));
V(j, :) = V(j, :) + alpha * (2 * error * U(i, :) - beta * V(j, :));
end
end
end
% Optionnel : Calcul du coût (erreur quadratique moyenne)
cost = 0;
for i = 1:n_users
for j = 1:n_items
if Y(i, j) > 0
prediction = U(i, :) * V(j, :)';
cost = cost + (Y(i, j) - prediction)^2;
% Ajout de la régularisation
cost = cost + (beta / 2) * (sum(U(i, :).^2) + sum(V(j, :).^2));
end
end
end
fprintf('Itération %d : Coût = %f\n', iter, cost);
end
end
III. Optimisation alternée
iv. Qu'est-ce que la factorisation matricielle ?
La factorisation matricielle consiste à décomposer une matrice en un produit de deux matrices de
plus faibles dimensions. Cette technique est largement utilisée dans l'apprentissage automatique,
notamment pour la recommandation de produits, l'analyse de données et la compression d'images.
L'algorithme d'optimisation alternée
L'algorithme d'optimisation alternée est une méthode itérative utilisée pour résoudre des problèmes
d'optimisation multivariables. Dans le contexte de la factorisation matricielle, il consiste à optimiser
alternativement les deux matrices facteurs.
v. Principe général :
a. Initialisation: On initialise aléatoirement les deux matrices
facteurs.
b. Itérations:
• Étape 1: On fixe la première matrice et on optimise la seconde par rapport à une
fonction de coût.
• Étape 2: On fixe la seconde matrice et on optimise la première.
• Arrêt: On répète les étapes 1 et 2 jusqu'à convergence d'un critère d'arrêt (nombre
d'itérations, variation de la fonction de coût...).
Comment implémenter l'algorithme ?
c. Choisir une fonction de coût:
• La fonction de coût mesure l'écart entre la matrice originale et le produit des deux matrices
facteurs.
• Une fonction de coût couramment utilisée est la norme Frobenius de la différence entre les
deux matrices.
d. Choisir un algorithme d'optimisation:
• Pour chaque étape d'optimisation, on peut utiliser différents algorithmes comme la descente
de gradient, la méthode des moindres carrés ou des algorithmes spécifiques pour des
problèmes de factorisation matricielle.
vi. Implémenter l'algorithme:
• Initialiser les matrices facteurs.
• Tant que le critère d'arrêt n'est pas atteint :
• Fixer la première matrice et optimiser la seconde.
• Fixer la seconde matrice et optimiser la première.
vii. Principe de fonctionnement:
e. Initialisation: On initialise aléatoirement les deux matrices
facteurs P et Q.
f. Itérations:
• •Étape 1: On fixe Q et on met à jour P en minimisant une fonction de coût
(typiquement la norme de Frobenius de l'erreur).
• Étape 2: On fixe P et on met à jour Q de la même manière.
g. Arrêt: On répète les étapes 1 et 2 jusqu'à convergence d'un
critère d'arrêt (nombre
d'itérations, variation de la fonction de coût)
viii. Implémentation sous Matlab :
i. Explication du code :
• Initialisation: Les matrices P et Q sont initialisées aléatoirement.
• Boucle principale: On itère un nombre donné de fois ou jusqu'à ce que l'erreur soit
inférieure à un seuil.
• Mise à jour de P et Q: Pour chaque élément non nul de la matrice R, on calcule l'erreur et
on met à jour les éléments correspondants de P et Q en utilisant une règle de mise à jour
basée sur la descente de gradient.
• Calcul de l'erreur: L'erreur est calculée comme la somme des carrés des différences entre
les éléments de R et les éléments correspondants du produit P*Q.
IV. Algorithme multiplicatif
1. L’idee generale :
Est de progresser dans le processus d’optimisation en multipliant les paramètres a
optimiser(qui tendra vers la valeur 1) a chaque itération.
Objectif :
Chercher a factoriser Y apparentent a R(n*p) sous forme U*V avec U appartenant R(n*d) et V
appartenant R(d*p) par l’approche du gradient.
Les Réglés :
La mise a jours de U et V sont observer a travers les formules
(*, --) Est le produit de Hadamart
Fonction de d’erreur
Ici nous utilisons l’erreur quadratique pour mesurer les erreurs. Cette préférences est du au
fait la fonction quadratique est interprétable du point de vu mathématique.
Contrainte
L’algorithme multiplicatif marche uniquement si l’on applique certain contrainte :
Y >= 0
U >= 0
V >= 0
Particularité et application et utilisation de l’algorithme dans le monde réel
Déjà cette méthode de factorisation est dite non négative car elle sont plus efficace et
adapte au valeurs positive dans les matrices de données.
Les systèmes de complexions, l’ordonnancement sont quelques exemples d’application de
cette algorithme ou encore faire de la décomposition du signal.
Étude de complexité :
2. L’algorithme ici marche en code MATLAB
function [W, H] = nmf_multiplicative(V, rank, max_iter)
% Input:
% V: Input matrix (non-negative) to factorize, size m x n
% rank: Number of latent features (columns of W, rows of H)
% max_iter: Maximum number of iterations
[m, n] = size(V);
% Initialize W and H with random non-negative values
W = rand(m, rank);
H = rand(rank, n);
% Set tolerance for convergence
tol = 1e-4;
% Loop for the maximum number of iterations
for iter = 1:max_iter
% Update H using multiplicative update rule
H = H .* (W' * V) ./ (W' * W * H + tol);
% Update W using multiplicative update rule
W = W .* (V * H') ./ (W * (H * H') + tol);
% Compute the reconstruction error (optional, for monitoring)
reconstruction = W * H;
error = norm(V - reconstruction, 'fro'); % Frobenius norm
% Display the error every 10 iterations
if mod(iter, 10) == 0
fprintf('Iteration %d, Reconstruction error: %.4f\n', iter, error);
end
% Stop if the change in error is below the tolerance
if error < tol
break;
end
end
end