Source

REX 2011 @PilotSystems&Libération / rook.rst

Full commit

Rook

Rook est une application web qui complète l'expérience utilisateurs de twitter. Notamment à l'aide de mini-application qui rendent accessible des fonctions de twitter autrement difficile d'accès. Il s'agit d'une application developpée par Pilot Systems sur laquelle je suis intervenu en tant que consultant fonctionnel et technique. Je devais penser à de nouvelles fonctionnalités et proposer des moyens afin de les implémenter.

La proposition est de reproduire le mur personnalisé de facebook et de regrouper les tweets par thème comme le fait Google News.

La premiere étape a été de dresser un état de l'art dans le domaine de la recommandation de contenu. Je me suis rendu compte que le domaine de recherche à l'origine de ce type d'algorithme provenait le plus souvent de l'intelligence artificielle et plus particulièrement du domaine des machines apprenantes ou algorithme d'aide à la décision. J'ai continué mes lectures dans ce domaine. Les machines apprenantes utilisent différents types d'algorithmes parfois basés sur des statistiques parfois sur des mathématiques discrètes. Il y a une partie des algorithmes qui utilisent de l'information sémantique tiré d'un traitement automatique de la langue. La catégorisation est aussi un problème qui peut-être resolue à l'aide d'une machine apprenante.

A partir de ces connaissances j'ai developpé un programme cible qui doit permettre d'implémenter la recommandation de contenu en minimisant l'effet de démarrage à froid dans le cadre d'une implémentation dans Rook.

Ce chapitre est partagé en trois parties, dans un premier temps je décris la base de connaissance et son support, ensuite les différentes méthodes qui permettront de faire de la recommandation sur cette base de donnée, pour finir par un bilan sur le travail fait.

Base de connaissances

Connaissances

Les messages sur twitter ne font que 140 caractères, difficile dans ce cas de réaliser une analyse sémantique ou même statistique à l'aide d'un algorithme tel que LDA [1].

FIXME refaire la phrase en citant les études Un système apprenant a besoin d'informations, certains algorithmes fonctionnent mieux avec un grand nombre de donnée [2] et les algorithmes pour résoudre des problèmes avec de très nombreuses données existent [3].

Nous désirons donc maximiser la quantité d'informations que nous capturons de l'environnement social twitter de l'utilisateur ainsi que de son intéraction avec l'application.

En entrée du systeme, nous avons l'environnement social, les tweets (ainsi que les hashtag) et toutes les intéractions avec les tweet:

  • personnes suivies
  • personnes suivantes
  • tweet dont hashtags
  • retweet(s) et les personne(s) qui retweete(nt)
  • réponse(s) et les personne(s) qui reponde(nt)
  • lu ou non
  • heure du tweet
  • mise en favoris

Ceci ne résoud pas le problème de l'analyse sémantique des tweets. En effet, avoir un grand nombre de données est une chose, et pouvoir les corellers en est une autre. Pour nous aider dans ce travail nous allons augmenter notre base de connaissances issue du web certaines ressources facilement exploitable tel que wikipedia à travers dbpedia autres ressources catégoriser par de dmoz ou Yahoo. L'idée est de permettre d'enrichir le tweet avec des documents que l'on sait similaires à l'aide d'une recherche full-text [5].

Les données que nous allons devoir recueillir sont de natures différentes, elles nécessiteront un grand nombre de tables et de connexions, d'autre part en tant que projet de recherche il est agréable de savoir que l'ajout d'attribut et de nouvelle connexion est facile.

Bases

J'ai établi la matrice de comparaison des bases MySQL, PostgreSQL, Neo4j, OrientDB et MongoDB.

OrientDB remplit le plus de conditions à priori car je n'ai pas reussi à determiner le niveau ACID de Neo4j.

  MySQL, PostgreSQL Neo4j OrientDB MongoDB
Tuning et maintenance documenté oui      
Schema-less   oui oui oui
Nouvelles connexions facile à créer   oui oui  
ACID oui X oui
au niveau
document
License GPL AGPLv3 Apache AGPLv3

Système intelligent

Notre besoin est de regrouper par catégorie les articles et de donner une note aux tweet entrant d'un utilisateur. C'est deux problèmes distincts mais qui peuvent se recouper dans le cardre de la mise en place d'un système apprenant.

Categorisation

Il existe différentes méthodes pour faire de la catégorisation.

On peut utiliser des informations sémantiques présentant des sites par regroupement thématique. Par exemple un blog qui a un lien depuis bitbucket a de forte chance d'être un blog technique. De plus, un compte twitter qui est lié depuis un blog, lui même lié depuis bitbucket a de forte chance d'avoir un contenu technique. De cette façon nous pouvons construire un système qui permet de déterminer une ou des catégories pour chaque site en implémentant un algorithme logique ou en utilisant une machine apprenante supervisée.

Une machine apprenante supervisée est un algorithme apprenant qui prend en entrée un document et des catégories. Elle associe les documents aux catégories et permet de générer des descripteurs pour des documents nouveaux.

Une méthode non-supervisée peut être utilisée de deux façons; d'une part sur les tweets étendus à l'aide de [5] ou alors en prenant comme document l'ensemble des poids sur les arêtes qui lient un noeud au reste du graphe.

Le défaut des deux méthodes précédentes et qu'il est difficile de comprendre pourquoi ce resultat a été donné.

Couplés à la méthode décrite dans [5] en utilisant [6] il est possible d'implémenter un algorithme de type PageRank [7] qui génére des catégories comme réponse. Cette algorithme à le bénéfice de pouvoir être expliquer.

Mur personnalisé

L'implémentation du mur personnalisé peut se faire à l'aide des mêmes methodes que celle utilisées précédemment.

Le point qui a retenu mon attention est celui de l'implémentation de la machine apprenante qui resoudra ce problème. Un très grand nombre de données peuvent être soumis à l'algorithme rendant son calcul non praticable, c'est la malédiction dimentionnelle. L'optimisation présentit est la génération d'un graphe de descripteurs pour chaque documents déjà present dans la base à l'aide du résultat de la catégorisation. Un document pour cette machine apprenante est le vecteur des contributions de chaques categories à un tweet. On peut réduire la dimension de l'espace de projection en fonction des ressources.

Bilan

TODO