Latent Dirichlet Allocation (LDA) et Google

L'étude de l'algorithme du LDA (Allocation de Dirichlet latente) est la nouvelle tendance chez les webmasters. Il lève une part du secret de l'algorithme du moteur de recherche de Google et explique en partie comment sont sélectionnées les liens dans les pages de résultats.

Cette tendance a été lancée par le site Seomoz.org lorsqu'il a proposé un outil permettant d'évaluer une page Web en lui appliquant cet algorithme. Cet outil fournit un score de pertinence par rapport à une requête, plus elle est pertinente et plus elle est supposée bien figurer dans les résultats des moteurs de recherche.
La validité du score a été vérifiée expérimentalement.

Le mot Dirichlet vient de Johann Peter Gustav Lejeune Dirichlet, Mathématicien allemand ayant étudié en France et cotoyé les mathématiciens français du 19ème siècle , qui a fait des travaux dans le domaine de l'analyse complexe et les lois de probabilité.
L'algorithme LDA a été décrit pour la première fois par David Blei en 2003 qui a publié un article qu'héberge l'université de Princeton: Latent Dirichlet Allocation.
Un document intitulé Online Inference of Topics with Latent Dirichlet Allocation publié par l'université de Berkeley en 2008 compare les avantages relatifs de deux algorithmes de LDA.

Qu'est-ce que le LDA?

Le LDA a un but essentiel de classement, il permet d'associer un contexte à un document à partir des mots contenus dans ce document, lesquels mots pris individuellement pourraient appartenir à des contextes différents.
Par exemple le mot robot peut faire allusion à un programme (robot de moteur de recherche), ou à une machine (robot androïde). L'analyse des mots proches de ce mot dans une page permet de dire si la page ou le paragraphe parlent de programmes ou de machines.
Les moteurs de recherche définissent un contexte à partir d'une requête et des habitudes de l'internaute, des pages précédemment visitées. Il leur reste alors à trouver des pages contenant les mots-clés de la requête, mais dans le contexte de l'internaute et le LDA s'applique alors aux pages dans l'index.

L'algorithme est un modèle Bayésien, il vise donc à déterminer la probabilité d'une hypothèse. Puisqu'il s'agit d'associer un mot-clé ou un groupe à un contexte, l'hypothèse est le contexte, et il y a en plusieurs en concurrence.
On utilise par ailleurs en informatique les inférences bayésien et l'on entraîne des bots par exemple pour créer un filtre contre le spam.
Entraîner un algorithme de moteur de recherche de la même manière peut s'avérer plus efficace qu'utiliser un code prédéfini.

Citation (Griffiths et Steyver):

Latent Dirichlet Allocation (Blei et al, 2003) est un puissant algorithme d'apprentissage pour, de façon automatique et conjointe, classer des mots dans des contextes et des documents dans des mélanges de contextes. Il a été appliqué avec succès pour modéliser les changements dans les domaines scientifiques au cours du temps.

LDA et optimisation

Seomoz a créé son outil après avoir constaté une corrélation entre les résultats de Google et cet algorithme. La conclusion est que Google intègre le LDA dans son algorithme, qui est lui plus vaste et incorpore de nombreux autres critères.
Le LDA est essentiellement basé sur le contenu. L'algorithme de Google contient des critères sur le contenu, mais aussi des critères indépendants de celui, notamment le nombre de liens qui pointent sur une page.
L'expérience montre que les premiers liens dans les pages de résultats de Google ont un contenu plus pertinent que ceux qui viennent après.

Pour utiliser au mieux cet algorithme, le mieux est de renforcer le contexte d'une page, par rapport à la requête à laquelle on veut répondre en ajoutant des mots en rapport avec les mots-clés déjà en rapport avec cette requête.

Mais il convient d'éviter certains écueils...
Ce que LDA n'est pas:

La répétition d'un mot-clé n'apporte rien, mais la répétition du contexte à l'inverse peut être utile. Des groupes de mots-clés relatif à un sujet, par exemple aux programmes, ou aux machines, trouvés plusieurs fois dans la page, peuvent améliorer son positionnement.

Documents et code