Meilleure approximation de rang k

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
Elias
Habitué(e)
Messages: 367
Enregistré le: 07 Fév 2016, 19:20

Meilleure approximation de rang k

par Elias » 04 Avr 2016, 12:41

Salut à tous,

on part du théorème suivant :

Théorème 1:

Soit . Il existe , et tels que : (où désigne l'ensemble des matrices orthogonales et la transposée de ). La matrice vérifie :
il existe et tels que pour tout : et tous les autres coefficients de sont nuls (en gros , la partie de est diagonale et il y a des 0 partout ailleurs). On a en fait
Une telle décomposition d'une matrice A est dite décomposition en valeurs singulières de A.

Remarque : ce théorème généralise le théorème spectral pour les matrices symétriques.

Théorème 2:

Soit et . Pour tout , il existe une matrice telle que et telle que :
où l'inf est pris sur l'ensemble des matrices de rang k et où désigne la norme matricielle subordonnée à la norme euclidienne :
si où dans cette écriture, désigne la norme euclidienne sur et .

De plus, le théorème nous précise comment obtenir la matrice . On commence par écrire la décomposition en valeurs singulières de et il suffit de prendre pour la matrice est la matrice de obtenue à partir deen ne conservant que les k premières valeurs singulières et en remplaçant partout ailleurs par des 0.

De plus, on peut remarquer que cette distance minimale vaut : .

J'en arrive donc à mes questions :

- philosophiquement, qu'est-ce que ça représente ? J'ai une matrice A disons de taille 20 x 12 . J'ai donc 12 vecteurs colonnes de R^20. Supposons que cette matrice soit de rang plein, donc de rang 12. Je décide de faire sa réduction au rang 2. J'obtiens une matrice A2 de rang 2. Quelles sont les relations entre les vecteurs colonnes de A et les nouveaux vecteurs colonnes de A2 ?

J'ai fait le test sous scilab avec la matrice suivante :
Code: Tout sélectionner
A  =
 
    0.    0.    0.    0.    0.    0.    0.    1.    0.    1.    0.    1. 
    0.    0.    0.    0.    0.    0.    1.    0.    0.    0.    0.    0. 
    1.    0.    0.    0.    1.    0.    1.    0.    0.    0.    0.    0. 
    1.    1.    1.    0.    0.    1.    0.    0.    0.    0.    0.    0. 
    1.    0.    0.    1.    0.    0.    0.    0.    1.    0.    1.    0. 
    0.    0.    0.    0.    0.    0.    0.    1.    0.    0.    0.    0. 
    0.    0.    0.    0.    0.    0.    0.    0.    0.    1.    1.    1. 
    0.    1.    0.    0.    0.    0.    0.    0.    0.    0.    0.    0. 
    0.    0.    0.    1.    0.    1.    0.    0.    0.    0.    0.    0. 
    0.    0.    0.    0.    0.    0.    0.    0.    0.    0.    1.    0. 
    0.    0.    0.    0.    0.    0.    0.    1.    1.    0.    0.    0. 
    1.    0.    0.    0.    0.    0.    0.    0.    0.    0.    0.    0. 
    0.    0.    0.    0.    1.    0.    1.    0.    0.    0.    0.    0. 
    0.    0.    0.    1.    1.    0.    0.    0.    0.    0.    0.    0. 
    0.    1.    1.    0.    0.    1.    0.    0.    0.    0.    0.    0. 
    0.    0.    0.    0.    0.    1.    0.    0.    0.    0.    0.    0. 
    0.    0.    1.    0.    0.    0.    0.    0.    0.    0.    0.    0. 
    0.    0.    0.    1.    0.    0.    0.    0.    0.    0.    0.    0. 
    0.    0.    0.    0.    0.    0.    0.    0.    0.    1.    0.    0. 
    0.    0.    0.    0.    0.    0.    0.    0.    0.    0.    0.    1.


J'obtiens ceci comme meilleure approximation de rang 2 :

Code: Tout sélectionner
 column 1 to 5
 
    0.2184534  - 0.2481437  - 0.2481437    0.3250913    0.2236214 
    0.0855795    0.0234518    0.0234518    0.0763173    0.0489316 
    0.4364533    0.2040311    0.2040311    0.3535053    0.2224910 
    0.7483175    0.8807608    0.8807608    0.3815228    0.2113031 
    0.6535278    0.1708952    0.1708952    0.5862633    0.3762926 
    0.0581388  - 0.0628975  - 0.0628975    0.0851897    0.0585068 
    0.2956006  - 0.2215876  - 0.2215876    0.3915984    0.2659962 
    0.1528939    0.2282770    0.2282770    0.0575121    0.0276853 
    0.3797097    0.3288249    0.3288249    0.2435406    0.1450665 
    0.1352860  - 0.0363414  - 0.0363414    0.1516969    0.1008816 
    0.1573045  - 0.0660670  - 0.0660670    0.1864579    0.1249321 
    0.240948     0.1528939    0.1528939    0.1781281    0.1099258 
    0.1955053    0.0511371    0.0511371    0.1753773    0.1125651 
    0.2880539    0.0851974    0.0851974    0.2542300    0.1626935 
    0.5073695    0.7278668    0.7278668    0.2033947    0.1013772 
    0.2015816    0.2713128    0.2713128    0.0883705    0.0460065 
    0.1528939    0.2282770    0.2282770    0.0575121    0.0276853 
    0.1781281    0.0575121    0.0575121    0.1551701    0.0990600 
    0.0801573  - 0.0926231  - 0.0926231    0.1199508    0.0825573 
    0.0801573  - 0.0926231  - 0.0926231    0.1199508    0.0825573 
 
         column  6 to 10
 
  - 0.2397759    0.1685005    0.3467502    0.2846638    0.495472   
    0.0378908    0.0376481    0.0441056    0.0507575    0.0621975 
    0.2854790    0.1721591    0.1607512    0.2163485    0.2249121 
    1.0695171    0.1703738  - 0.1280360    0.1035817  - 0.1947870 
    0.2804007    0.2894256    0.3430427    0.3917364    0.4839290 
  - 0.0603798    0.0441056    0.0898939    0.0741772    0.1284281 
  - 0.1997026    0.2011663    0.3823932    0.3276933    0.5456215 
    0.2713128    0.0234518  - 0.0628975  - 0.0031695  - 0.0926231 
    0.4136804    0.1142081    0.0248100    0.1120232    0.0302527 
  - 0.0203065    0.0767713    0.1255370    0.1172068    0.1785776 
  - 0.0496248    0.0948632    0.1640711    0.1482728    0.2336714 
    0.2015816    0.0855795    0.0581388    0.0991658    0.0801573 
    0.0838973    0.0865797    0.1026125    0.1171828    0.1447547 
    0.1343771    0.1252489    0.1436966    0.1676934    0.2025080 
    0.8679355    0.0847944  - 0.1861747    0.0044160  - 0.2749443 
    0.3253098    0.0378908  - 0.0603798    0.0107550  - 0.0896981 
    0.2713128    0.0234518  - 0.0628975  - 0.0031695  - 0.0926231 
    0.0883705    0.0763173    0.0851897    0.1012682    0.1199508 
  - 0.0896981    0.0621975    0.1284281    0.1052433    0.1835219 
  - 0.0896981    0.0621975    0.1284281    0.1052433    0.1835219 
 
         column 11 to 12
 
    0.4826922    0.495472   
    0.0767713    0.0621975 
    0.3129389    0.2249121 
    0.0422968  - 0.1947870 
    0.5938927    0.4839290 
    0.1255370    0.1284281 
    0.5468583    0.5456215 
  - 0.0363414  - 0.0926231 
    0.1313904    0.0302527 
    0.1897031    0.1785776 
    0.2427437    0.2336714 
    0.1352860    0.0801573 
    0.1776529    0.1447547 
    0.2525785    0.2025080 
  - 0.0929892  - 0.2749443 
  - 0.0203065  - 0.0896981 
  - 0.0363414  - 0.0926231 
    0.1516969    0.1199508 
    0.1785776    0.1835219 
    0.1785776    0.1835219 


J'ai essayé de mesurer le niveau de similarité entre une colonne j de A et une colonne j de A2 (pour j allant de 1 à 12). J'ai donc mesuré en quelque sorte le cosinus de l'angle formé entre chaque vecteur colonne j de A avec le vecteur colonne j de A2 (avec la formule<u,v>= ||u|| x ||v|| x cos(u,v)) pour voir si ceux ci étant proches mais j'obtiens :

Code: Tout sélectionner
  0.7209796 
    0.7824970 
    0.7824970 
    0.5565977 
    0.4073285 
    0.8179919 
    0.3143177 
    0.4474801 
    0.5196197 
    0.6389093 
    0.6659465 
    0.6389093


Il faudrait avoir des quantités proches de 1 pour dire que les colonnes de A2 sont similaires à celles de A.

Ma question est donc un peu imprécise mais que représente vraiment cette réduction à un rang donné ?

Vous pouvez arrêter de lire à ce moment là si vous avez de quoi m'aider (si vous n'avez pas trop le temps de lire le reste). Je vous remercie d'avance !

Mon problème de base est en fait le suivant :
On considère un ensemble de termes (par exemple, l'ensemble des mots de la langue française, il y en a environ 300 000) . On considère aussi un ensemble de documents . Chaque document est écrit à l'aide des termes . Un document (pour dans ) est donc décrit comme un vecteur de . Chaque composante (pour ) de vaut 1 si le terme apparaît dans et 0 sinon.
On note .
Etant donnée une requête de l'utilisateur (constituée de quelques termes), le but est de créer un moteur de recherche performant. C'est à dire un moteur de recherche qui à l'issue de la requête de l'utilisateur, donne les documents pertinents en rapport avec la requête.

Une requête q étant une ensemble de termes, on la représente comme un vecteur de . Chaque document j va alors être analysé pour voir si celui ci a un rapport avec la requête q de la façon suivante.

Etant donné un document j, on va analyser le vecteur q et le vecteur Dj et on va attribuer un score de similarité entre q et Dj qu'on va noter sj compris entre 0 et 1. L'idéal étant q = Dj auquel cas on aura sj=1. Le pire étant que q et Dj n'aient aucune composante en commun (vecteurs orthogonaux dans ce cas car q et Dj n'ont que des 0 ou des 1) donc sj=0.

En fait, on définit sj comme le cosinus de l'angle formé entre Dj et q , plus précisément :


On retient en général le document D_j si sj est plus grand qu'un certain seuil (0.8 par exemple).

Le problème est que ce moteur de recherche ne prend pas en compte le fait que deux mots peuvent avoir exactement le même sens ou au moins des sens très voisins (voiture et automobile par exemple). On voudrait pouvoir extraire automatiquement ce type d'informations de la matrice afin de ne pas oublier des documents sémantiquement pertinents pour la requête de l'utilisateur.

En remplaçant (presque) D par sa meilleure approximation de rang k dans le calcul de sj, miracle, plus de problème de sémantique, tout est pris en compte.

J'ai pu constater sur un exemple que ça fonctionne bien mais alors je ne comprends pas du tout pourquoi, pour moi c'est tout simplement magique...
Pseudo modifié : anciennement Trident2.



 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 31 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite