Latent Dirichlet allocation

September, 13, 2010
Sylvain

C’est l’ami Tiger qui me l’a  demandé sur Twitter et la foule (enfin une petite foule, presque une “foulette”) en délire en a rajouté, donc voici l’article promis sur la LDA (Latent Dirichlet Allocation). Le billet va être un peu long, je vous conseille donc de vous installer confortablement. J’ai a priori gommé tous les détails techniques et j’ai essayé d’enlever tout le jargon mathématique pour juste garder l’intuition, mais il ne faut pas hésiter à me demander des précisions que j’intégrerais au texte.

Dans ce billet je vais aborder deux aspects complémentaires des techniques statistiques de modélisation des documents textuels : l’aspect génératif, et l’aspect inférence. Comme son nom l’indique le but de l’aspect génératif est de fournir une méthode de description de textes corrects, tant d’un point de vue syntaxique que d’un point de vue sémantique. Dans cette partie du billet, je me verrais obligé de présenter les méthodes plus simples de génération pour expliquer comment l’on arrive à la LDA. L’aspect inférence est lui l’aspect le plus important d’un point de vue moteur : il est celui qui permet de déterminer le sujet d’un texte par la calcul d’un score de similarité à un corpus de documents connus. Il ne faut pas croire que modèle génératif signifie méthode de génération pratique pour faire du contenu BH, loin de là !

Ce qu’il faut retenir de ce billet, c’est que récemment il y a eu une progression dans les modèles de description des documents, et que cette progression va vers des techniques qui embarquent de plus en plus de sémantique. Pour savoir ce que font les moteurs avec la LDA, direction la fin du post !

Quelques notations

Le mot sera notre unité de base, je noterai les mots par la lettre w, avec un indice pour différencier les différents mots. Un document sera donc une suite de mots que je noterai d=(w_{1},\hdots,w_{n}). Les mots sont tirés dans dictionnaire, qui contient v mots.

Une notion importante est celle de corpus. Le corpus sera l’ensemble des mots que l’on considère, dans ce billet un corpus sera désigné par C et sera un ensemble de documents C=\{ d_{1},\hdots,d_{m}\}.

Enfin, puisqu’il s’agit d’étudier des modélisations de documents qui embarquent de la sémantique, la notion de thématique (topic) est de la plus grande importance. Les thématiques seront toujours indiquées par la lettre z, avec des indices lorsqu’il y aura plusieurs thématiques en concurrence.

TF-IDF

Je vous ai déja parlé il y a bien longtemps de la TF-IDF dans un post, ainsi que du modèle vectoriel (et du cosinus de Salton). La TF-IDF (Term Frequency – Inverse Documents Frequency) est une mesure qui permet de faire de la ségrégation entre documents. En effet, si un terme (= mot) a une très haute fréquence dans un document, mais une fréquence basse dans les autres documents du corpus, c’est qu’il s’agit d’un terme important pour caractériser le document en question. En utilisant ensuite le modèle vectoriel, on va caractériser chaque document par un vecteur de valeurs associées à chaque mot, et c’est la comparaison entre les vecteurs qui nous donnera une mesure de la similarité entre documents.

En utilisant cette métrique pour représenter un corpus, on obtiendra une matrice de taille v \times m qui décrit la chose suivante :

tfidf

Pour vous donner une idée, le Français usuel utilise 32 000 mots, et donc si le corpus contient 1 000 000 de documents, la matrice est de taille 32 000 * 1 000 000, ce qui fait

autour de 30 GO !

Il existe des techniques de réduction de la taille de la matrice basées sur l’extraction des caractéristiques importantes, ces techniques sont basées sur la Singular Value Decomposition de la matrice. Elles sont regroupées sont le nom de LSA (Latent Semantic Analysis) dans le cas général et LSI (Latent semantic Indexing) dans le cas de la recherche d’information.

On peut tirer un modèle génératif de ce cadre de modélisation. Qu’est ce que cette bête là ? Il s’agit d’un objet qui est conçu de la façon suivante :

  1. On part du principe que les données (c’est à dire les documents) obéissent à des processus aléatoires dont on ne connait pas nécessairement les paramètres.
  2. On apprend les paramètres qui correspondent le mieux aux données disponibles (par exemple en calculant les fréquences)
  3. On utilise le modèle avec les paramètres appris pour prédire des nouveaux documents cohérents avec ceux observés.

L’avantage des modèles génératifs est qu’ils sont particulièrement bien balisés : on sait les utiliser pour  inférer des informations sur les documents.
Bref, le modèle génératif qui se cache ici est le suivant :

plsi

En pratique un document est souvent sans thématique définie car on ne peux pas tirer au sort une thématique facilement, saud à avoir isoler à l’avance des sous-ensemble de documents qui sont dans des thématiques auparavant identifiése (à la main donc).

pLSI

le modèle pLSI (probabilistic LSI) est un modèle génératif probabiliste.
Le modèle pLSI est intéressant car c’est le premier qui introduit la notion de thématique au sein des documents. En effet, le modèle implique que la probabilité d’apparition d’un mot dans un document est fonction de la probabilité d’apparition du topic et de la probabilité d’appartenance du mot à la thématique. Si je veux écrire ça formellement, cela donne :

prob(w)=\sum_{i=1}^{k} p(z_{i})p(w\mid z_{i}) avec \sum_{i=1}^{k} p(z_{i}) = 1

Cela ne parait pas évident de prime abord, mais avec cela on a la clé pour générer des documents possédant plusieurs thématiques. Ce que j’explicite par un petit dessin :

plsi2

En revanche, le modèle pLSI a de multiples limitations, la première étant que les thématiques sont définies avant le document, et donc qu’un document généré a une thématique principale très marquée par les documents qui sont précédemment connus. Par ailleurs, la génération du document se fait par la probabilité d’appartenance du mot au topic, et non par la probabilité qu’un document contienne un mot d’un topic donné. Pour contrer ces limitations, on peut utiliser la LDA !

LDA

La LDA (Latent Dirichlet Allocation) est basée sur une idée beaucoup plus rusée que la pLSI. En effet, l’idée de base est qu’un document est un mélange probabiliste de thématiques latentes (c’est à dire cachées de nos yeux curieux). Ensuite, chaque thématique est caractérisée par une distribution de probabilité sur les mots qui lui sont associée. On voit donc que l’élément clé est la notion de thématique, c’est à dire que la sémantique est prioritaire sur la syntaxe (la notion de terme ou mot). C’est pour cela que l’approche est beaucoup plus puissante que les approches précédentes.

Par ailleurs, le modèle LDA a été conçu pour éviter que la distribution de probabilités qui sert au choix du topic soit dépendante des documents connus précédemment (cela signifie que le modèle est capable de prendre en compte des documents non connus à l’avance). Tout cela vient de choix techniques pas simple à comprendre. En particulier on mentionne le nom de Dirichlet car une distribution de Dirichlet permet un choix probabiliste efficace sur les distributions multinomiales (au lieu de tirer au sort un topic comme avec la pLSI, on tire d’abord au sort une méthode de tirage au sort sur les thématiques).

Au final, le procédé est le suivant :

lda

La différence avec la pLSI est donc dans l’étape sur le choix du paramètre du tirage au sort sur les topics.

L’intérêt du modèle va bien sur au delà de l’aspect génératif. Le vrai intérêt est bien sur d’inférer les thématiques à partir d’un corpus de documents. Cela se fait très bien de manière approchée, mais c’est très technique (aller donc voir ce qu’en dit Wikipedia, la partie avec les formules est celle sur l’inférence).

Inférence et LDA

Comment utiliser la LDA quand on est un moteur de recherche ? De la manière suivante :

  1. Grâce à la LDA, on extrait des thématiques d’un grand corpus de documents. On va avoir quelques milliers ou plus de topics. On prend ensuite une selection de mots qui paraissent intéressants pour la ségrégation de documents (via une LSI sur le modèle TF-IDF par exemple). chaque couple (mot,topic) est caractérisé par une quantité qui est la probabilité avec laquelle un mot d’un texte est employé avec une signification qui le rattache au topic.
  2. Tous ces couples sont mis dans une matrice MOT \times TOPIC. Chaque mot est alors défini par le vecteur qui donne toutes les probas d’appartenance aux divers topics. Quand on a une requête de plusieurs mots, on peut moyenner les vecteurs pour avoir la proba d’appartenance de la requête aux topics.
  3. Quand on a deux textes (ou un texte et une requête), on peut utiliser le cosinus de Salton, ou la distance de Kullback Leibler entre les vecteurs associés pour mesurer la similarité, et le tour est joué !

Il existe une utilisation exotique : le filtrage de documents (pour la lutte contre le spam) en testant un document (un mail par exemple) face à un filtre (“vous avez gagné à la loterie”, “viagra gratuit”, “porn 4 all”, “enlarge your peniche”, etc.).

Voilà, j’espère que le post vous aura plu, il y a sans doute quelques erreurs et imprécisions, je corrigerai au fur et à mesure celles que je trouve.

Be Sociable, Share!

18 Responses to “Latent Dirichlet allocation”

Merci Sylvain pour ces explications très intéressantes que j’ai mentionnées dans la discussion WebRankInfo sur la LDA : http://forum.webrankinfo.com/latent-dirichlet-allocation-lda-referencement-google-t133167.html

Penses-tu que des moteurs comme Google puissent déjà utiliser la LDA malgré la taille de l’index (et d’autres caractéristiques de l’index) ? Si oui, est-ce plutôt pour détecter du spam, pour mesurer la similarité entre 2 documents (et donc déjouer les techniques de content spinning), ou autre chose ?

Olivier

PS: tu as écrit “le modèle LDA a été conçu pour éviter que la distribution de probabilités qui sert au choix du topic soit indépendante des documents connus précédemment” mais ne faudrait-il pas écrire “le modèle LDA a été conçu pour éviter que la distribution de probabilités qui sert au choix du topic soit dépendante des documents connus précédemment” ?

Olivier Duffez, 14 September 2010 at 8:00

Effectivement utiliser la LDA pour un moteur semble être un challenge d’un point de vue calculatoire. Si c’est utilisé, je pense que c’est actuellement à petite échelle, et donc plutôt sur des contenus suspects (pour confirmer que c’est du spam et/ou duplicate). Mais sans être dans le secret des centres de calcul de l’ami GG c’est difficile à dire, ils ont peut être musclé sérieusement leur infrastructure.

Pour le PS, tu as raison, je viens de faire la modif, merci !

Sylvain, 14 September 2010 at 8:24

Je suis intégralement en accord avec la phrase “Cela ne parait pas évident de prime abord”.

En troisième lecture, c’est moins flou.
Même question qu’Olivier. Ceci est-il mis en oeuvre par un moteur comme Google ?

Si j’ai bien compris, au delà de permettre de lutter contre le spam, c’est aussi un formidable moyen de juger de la pertinence par rapport à une requête.

Sylvain (AxeNet), 14 September 2010 at 8:38

Wow, je ne pensais pas lire un jour avec intérêt un article mentionnant la loi de poisson (car Dieu sait que ça m’a fait ch** par le passé :P).

Bravo, excellent article. Ce n’est pas la première fois que je lis un article technique et intéressant ici, donc je vais surement rajouter ton blog à mon reader quand j’aurai le temps :]

Hoki, 14 September 2010 at 9:35

Merci Sylvain.

C’est toi le meilleur 😉

Q1. Dans Google Instant on peut apercevoir l’usage d’un LDA ?

Q2. loutre = “Ids=25657,25901,26206,26446,26515” voiture = “=17259,17315,23628,23670,23756,24692,24878,24879,25221,25834,25856,25901,26328,26348,26446,26515,26568”

Ci-dessus c’est un copier / coller d’une partie de l’URL sur Google.com avec Instant actif ; est-ce que ça pourrait correspondre aux thématiques du grand corpus de document ?

Jean-Michel de Sousa, 14 September 2010 at 10:22

Merci Sylvain c’est vraiment très clair (bien plus que les pièces déposées 😀 )

Concernant les ressources, il semble que Caffeine ait été la phase préparatoire à l’implémentation de cette méthode. Caffeine est une “refonte” de la structure de Google, et il semble que leur modèle de base de données ait été également modifié (GFS 2).
On pourrait donc envisager qu’ils utilisent maintenant ce procédé.

Maintenant, d’après ce que j’ai compris, ils construisent un index un peu comme un annuaire multi-dimensionnel qui s’alimente automatiquement.
Cette méthode pourrait être utilisée lorsque les résultats générés par leurs précédentes méthodes ne renvoient rien, ou sur des niches particulièrement concurrentielles (à des fins de pertinence ET de lutte contre le spamdexing).
Qu’en penses-tu ?

Mathieu, 14 September 2010 at 10:26

Je n’ai pas encore lu mais merci :p

Aurélien, 14 September 2010 at 15:13

Heureusement que j’ai le WE pour pouvir te lire. Merci
A+
David Cohen

@DWynot, 17 September 2010 at 17:23

Oula ca commence a eter pointu et ennuyeux … donc c’est quelque chose a maitriser ;op. Plus sérieusement c’est uen approche du SEO assez différente de la mienne mais ca tient debout. Bon attention y a certains truc que j’ai pas bien compris – I.E. “cosinus de Salton, ou la distance de Kullback Leibler” la on touche a des choses hors de mon univers

Le Juge, 21 September 2010 at 16:20

Le gnome me signale que je n’ai pas répondu aux questions que l’on me posait ici…

@sylvain Est ce que c’est utilisé par Google ? Bonne question, selon les gars de seomoz oui, mais cela ne parait pas si clair que ça, d’autant qu’il faut une sacré puissance sous la pédale pour appliquer tout ça.

@Mathieu Je suis 100% d’accord avec toi, en tout cas je ferais comme toi, méthode en dernier recours pour les cas difficiles.

@J-M Je pense que c’est plutôt un codage de l’endroit de l’index ou l’on est selon le nombre de caractères tapés ? Quelle était la requête tapée ? et comment cela évolue t-il au fur et à mesure de la frappe de la requête ?

Sylvain, 5 October 2010 at 17:30

@sylvain En fait j’ai utilisé la méthode de test suivante :
1 Ouverture d’un navigateur
2 Vidage de cache
3 Vérification que l’on n’est pas connecté à son compte Google
4 Direction http://www.google.com
5 Copier / Coller de la requête dans le formulaire, puis attente de 3 à 4 secondes que ça s’affiche
6 Copier / Coller de l’URL de Google dans un bloc note
7 Retour à l’étape 1 sauf qu’on ouvre un autre navigateur

Du coup la requête n’évolue pas. Par contre quand on tape lettre par lettre le codage s’affiche une fois et n’évolue plus par la suite que rajoute ou retire des lettres ca reste pareil.

Par exemple la lettre « L » = 17259 et 26885 alors que « Loutre » = 17259, 26425 et 26885.

En poussant le test plus en avant « Lo » = 17259, 24813, 26714 et 27014 | « Lou » = 17259, 18167 et 26885 | « Lout » = 17259, 25260, 25567, 26885 et 27016 | « Loutr » = 17259, 17291, 22881, 25566 et 26714.
Le premier mot dans suggest pour chacun des tests est :
L : Lowes = 17259, 18167, 25567, 26347, 26885, 27001 et 27016
Lo : Lowes
Lou : Louis Vuitton = 17259, 18168, 23756, 24692, 24878, 24879, 26206, 26345, 26854 et 26885
Lout : Lout = 17259, 24416, 26046, 26614 et 26885
Loutr : Loutraki = 17259, 17315, 23628, 23670, 24472, 25834, 26095, 26328, 26562, 26568, 26746, 26761, 26849 et 26885
Loutre : Loutre

A noter que si on tape une lettre seule A, Z ou autre le premier chiffre est toujours 17259

Jean-Michel de Sousa, 6 October 2010 at 18:22

C’est bizarre, je ne vois pas bien à quoi cela peut servir à part à indexer l’endroit ou tu serais dans une structure de données qui servirait à prévoir les prochaines suggestions.

Sylvain, 7 October 2010 at 8:10

Merci pour ce “cours”. Personnellement, j’ai trouvé ça très instructif, et sutout très simple à lire, contrairement à un article scientifique ou autre machin. Ca peut servir de première lecture pour des gens pas très “stat”, comme moi 😉

Mohamed, 29 May 2012 at 16:32

Leave a Reply

Picture: courtesy of Abby Blank