Voilà, je souhaite implémenter une LSI (Latent Sementic Indexing : http://en.wikipedia.org/wiki/Latent_semantic_analysis ) dans une appli intranet faite en php/mysql.
Mon principal problème réside dans le temps de calcul de la SVD de la matrice termes-documents. En effet, j'ai réussi à trouver une lib php (Jama) qui implémente le calcul de la SVD. Pour une matrice 500x500 (tests), il me faut 20 mins de tps de calcul sur un PIV 2.6 Ghz. Or ma véritable matrice de termes-docs doit faire 2500x2500 => après qq tests pour estimer le tps de calcul, j'ai trouvé 1.7 jour si j'ai 1.5-2 Go de RAM!
Je pense qu'avec un .exe (pour Linux), y'aurait moyen de bien réduire le temps de calcul.
D'où mes questions :
- est-ce-que vous connaissez un programme compilé (c/c++ par ex) pour Linux (éventuellement pour Windows) à qui on peut passer en ligne de commande un fichier texte contenant la matrice dont on veut calculer la SVD et qui donne en sortie, dans des fichiers texte, les matrices U, Sigma et V?
- si y'a pas de tel programme, y'a t'il un moyen de découper le problème en pbs plus petits calculer la SVD de matrices plus petites et par des transformations (mais lesquelles?) en déduire la SVD de la matrice initiale?
- en désespoir de cause, faut-il que je réduise la taille de ma matrice en ne prenant qu'un échantillon de documents?
- existe t-il une autre solution à laquelle je n'ai pas pensé?
 
Autre pb : une fois que j'ai ma SVD, quelle est la forme de stockage la plus appropriée pour stocker mes matrices U, Sigma et V? dans des fichiers csv (environ 200 Mo par fichier ) qui seront lus par php lorsqu'un de mes scripts en aura besoin ou dans des tables mysql?
Le but étant de pouvoir transformer une requête d'un utilisateur (mots) en un document via le résultat de la SVD puis de calculer la proximité (via le cosinus) du vecteur obtenu avec le vecteur reconstruit par la SVD de chaque document (ce vecteur reconstruit étant stocké dans la bd une fois pour toute).
Question : quel est le meilleur type de données dans mysql pour stocker un vecteur colonne de dim 2500?
 
Merci par avance pour votre aide

ça a pas l'air d'inspirer grand monde mon pb, là

Je vais peut etre poser une question bete  mais n'aurai tu pas intérêt a partir sur une solution prévue pour faire des recherches plutot qu'une BDD ?  
je pense en particulier a lucene ( moteur de recherche libre )  
 
tu gagnera du temps a faire tes calculs en C/C++ par rapport a du php , c'est sur, mais ca va quand meme etre long  
 
pour le reste, je ne connais pas assez l'algo pour t'aider

je n'ai pas écarté totalement Lucene ou Mnogosearch mais ce sont tous les 2 des moteurs de recherche "classiques" reposant sur de l'indexation et des requêtes à base de mots clés. Ils ne prennent absolument pas en compte l'aspect sémantique des mots ni leur contexte d'utilisation.
 
ex : dans un document sur le cyclisme, on va trouver dans ce contexte d'utilisation les mots "vélo", "guidon", "pédale"... Dans un autre doc aussi sur le cyclisme, on aura peut-être plus "bicyclette" mais toujours "guidon" et "pédale" ).
 
Sur cet exemple, si tu cherches avec des mots-clés et que tu mets que "vélo", tu n'auras qu'1 doc et pas les 2 car le synonyme de "vélo" ("bicyclette" ) sera occulté. Avec une LSI, normalement, non.
 
Par contre, pour l'aspect c/c++, je suis d'accord avec toi, ça me ferait gagner beaucoup de temps. Si je pouvais trouver un .exe qui me calcule ma svd, je suis preneur

Pour la SVD, j'ai utilisé la librairie Boost en c++. Marche nickel.
 
À noter cependant que l'algo SVD est un algo en N². On ne peut donc pas dépasser les quelques milliers de mots sans exploser la mémoire et le temps de calcul d'un PC.
Pour utiliser SVD sur de grandes échelles, il ne faut donc pas indexer des mots, mais des concepts, donc utiliser une BDD mot -> vecteur concept .
 
Sinon, utiliser une SVD pour trier des résultats partiellements triés via une autre méthode plus rapide (genre SQL...) permet de classer un jeu de résultat, de façon assez convainquante, tout en limitant les calculs. Un essai sur la requête 'paris + louvre' permet de reclasser les résultats de Google par pertinence: le sites sur le musée en premier, le spam des hotels, restaurants & commerces alentours en deuxième.

eh, SVD, c'est l'implantation LAPACK en fortran qu'il faut privilégier (à moins que boost en fournisse qu'un wrapper).
LPP (http://lpp.sourceforge.net) fournti le wrapper C ou C++ kivabien btw

Pas tant que ça

Boost implémente très bien cet algo en C++, et de trois façons différentes.
 
Et si, il faut beaucoup de temps pour calculer une SVD. Il nécessite de toutes façons un espace de stockage de nombre_de_mots*nombre_de_pages, soit pour donner un ordre de grandeur: pour indexer 1000 documents, contenant 10000 mots, il faut en utilisant des nombres flottants 32 bits: 10^(3+4) *4octets = 38 méga de RAM. Pour 10000 documents: presque 4 gigas. Bref, en pratique ça tient pas en RAM pour plus de quelques milliers de docs.
 
Il y a des solutions alternatives pour contourner ce problème, mais je ne les ai pas testés. C'est d'utiliser un réseau de neurones (ou autre système d'auto-apprentissage) et de lui faire apprendre à calculer une SVD. On se rends compte en effet que sur les 32bits des nombres en virgule flottante, la précision finale de la SVD ne dépasse pas 3 chiffres décimaux. Les 32bits sont superflus. Des méthodes d'approximation peuvent être appliqués.

 
Je suis comme St Thomas, je ne crosi que ce je benchmark
 

Ca par contre, efefctivement c'est moche.
 

Oh, interessant, des liens sur ce genre d'astuce, ou c'ets du NR de base ?

J'ai lu ça sur wikipedia En:
http://en.wikipedia.org/wiki/Latent_semantic_analysis
 

 
Ce qui me fait penser que c'est une méthode qui devrait fonctionner est ce problème de précision de calcul: il y a des bits en trop, donc a fortiori il existe des méthodes d'approximations. Par exemple, en utilisant 12 chiffres (float32) de précision pour la matrice d'entrée sur une SVD 10*100, la précision du résultat n'est qu'a 3 chiffres significatifs.
 
Tu trouvera plus d'info en farfouillant sur wikipedia, du côté de SVD.

merki pour le toyo

Sinon, pour reprendre le problème de base, recherche de docs par mot-clés, il y a des méthodes plus faciles, et qui donnent d'aussi bons résultats si l'on a le contrôle par avance sur les documents à indexer.
 
Si tu indexe des trucs trouvés sur l'internet, LSI/LSA est meileur. Maintenant, si tu indexe des documents dont tu connais déjà le sujet, dont tu sais que ces documents sont cohérents (c'est à dire qu'ils parlent d'un sujet particulier sans jamais être hors-sujet), alors utilise plutôt la sémantique vectorielle. C'est beaucoup plus simple et léger à calculer, et ça donne d'aussi bons résultats dans beaucoup de cas. Voir: http://fr.wikipedia.org/wiki/S%C3% [...] ectorielle .
 
Enfin, tu peux diviser le problème en deux parties:
- trouver les docs contenant les mots-clés
- trier les résultat
Auquel cas, la pertinence de la recherche sera définie par le tri, et non par la selection des documents. LSA devient alors abordable sur un ensemble de docs restreint.
Mais aussi, c'est à ce moment que tu peux choisir de trier non pas en fonction du contenu des docs, mais en fonction de critères associés, comme pour les moteurs de recherche le nombre de fois où le doc est consulté, ou comme sur certains sites e-commerces en fonction du CA rapporté par le produit.
 
+ d'info et de reflexion approfondie sur le sujet de tri de documents utilisé par Google: http://www.google.com/technology/pigeonrank.html

Très intéressant cet article : http://www.dcs.shef.ac.uk/~genevieve/gorrell_webb.pdf
Pour l'instant, je l'ai lu qu'en diagonale. Cela dit, je n'ai aps bien compris comment on calcule "Nepoch" qui apparaît dans la dernière formule permettant de calculer Cij

hmm.. je dirais que c'est à prendre avec des pincettes..
il explique dans l'article qu'on est pas obligé de tenir compte du rééquilibrage des poids par la fonction log. C'est la même chose pour l'histoire des époques.
 
Il s'agit de diviser le corpus en epoques (disons, tranches), et de traiter incrémentalement ces tranches, afin de retrouver d'une part une équation en forme de log, d'autre part de limiter l'analyse aux mots dont la fréquence est supérieure à 1/nombre_mots_par_epoque. Une sorte de filtre passe-haut incrémental, avec une fenêtre de la taille d'une époque. Nepoch est simplement le nombre de tranches traitées jusqu'à présent.
 
LSA/LSI n'est pas le seul algo à prendre en considération la fréquence des mots relatif au corpus. Le problème lorsque l'on tient compte de ça est qu'il faut faire des tests pratiques sur un corpus-type pour fixer les valeurs telles que la taille d'une époque.
 
Pour illustrer le problème, j'ai l'habitude de raconter l'histoire de l'internet shadock:
Les shadocks avaient créé un internet. Mais ils n'avaient pas de moteur de recherche, aussi il fallait parfois surfer sur des millions de pages avant de trouver la bonne. Le professeur Shadocko proposa de construire un moteur de recherche selon le paradigme: "plus un mot est rare, plus il est important.". Les shadocks se mirent donc à construire un moteur de recherche à l'aide d'un ingénieux tri à pompe déssiné par le professeur shadocko. Mais voilà, l'internet shadock était quand même bien fait, et il n'y avait pas beaucoup de fautes d'orthographes. Aussi, le moteur de recherche shadock faisait apparaître en premier les pages avec des fautes. Pour remédier au problème, les shadocks mirent en place un correcteur orthographique à pompe afin de corriger toutes les pages. Ainsi, il y avait les shadocks qui pompaient pour trier les résultats, ceux qui pompaient pour corriger les fautes, et il n'y avait finalement que peu de shadocks qui avaient le temps de surfer. Et les shadocks pompèrent, pompèrent et repompèrent.
 
Voilà, cette histoire de fréquence consiste à dire: plus les mots sont rares, plus ils sont importants, dans une certaine limite. Pour trouver la limite qui-va-bien, faut faire des tests.

ok, merci pour cette explication