InferenceBot/CheckerBot
Le code pour le bot est disponible sur https://github.com/mj2905/InferenceBot. Il suffit de lancer le fichier python main.py, puis de taper autorun lorsqu'une entrée utilisateur est demandée.
La déduction est un principe en intelligence artificielle qui permet d’obtenir de nouvelles informations en se basant sur des faits, et des règles déjà établies. Pour la réalisation de ce projet, nous avons divisé le travail à accomplir en trois parties, chacune pouvant être modulée, afin de pouvoir être étendue par la suite :
- Le “wiki scraping” (récupération des informations), qui nous permet de lire directement récupérer des informations en provenance du wiki. En l'occurrence, pour notre bot, ces informations correspondent aux différents faits qui seront utilisés pour déduire d’autres faits.
- Le moteur d’inférence, qui va inférer des informations à partir de ce qui lui est fourni en entrée.
- Le “wiki writing” (écriture des informations sur le wiki) qui va écrire les faits déduits, considérés comme utiles, dans le wiki.
Le wiki scraping
Les objectifs fixés pour la récupération des données sur le wiki étaient les suivants:
- Modularité: étendre le code du programme pour récupérer davantage de faits doit être facile.
- Flexibilité: de petits écarts dans le format d'une ligne ne doivent pas faire échouer l'extraction des faits.
- Abstraction: la récupération des données ne doit pas présenter de couplage avec le reste du programme.
Pour réaliser les objectifs ci-dessus, nous avons implémenté le bot de la façon suivante. Tout d’abord, il récupère la liste des URLs récemment modifiées par des utilisateurs agréés. Il regroupe ensuite les adresses en paquet de dix et ouvre un nombre équivalent de connexions HTTP pour récupérer les données relatives aux pages. Pour ouvrir des connexions en parallèle nous créons plusieurs "threads" qui s'exécutent de manière concurrente. La raison qui nous a poussé à choisir cette approche parallélisée est que l'obtention des données demande un temps beaucoup plus élevé que leur traitement. Il est donc judicieux de chercher à en minimiser l'impact.
Une fois les données HTML acquises, le bot les analyse séquentiellement dans le but d'y trouver de potentiels concepts intéressants. Comme mentionné précédemment, le temps requis par ce traitement séquentiel des données est négligeable par rapport au temps nécessaire pour les obtenir. L'analyse des données consiste à trouver des correspondances entre des "regular expressions" (abrégées en 'regex') python et des sous parties du texte. L'utilisation des regex nous permet d'obtenir une certaine marge de tolérance vis-à-vis des entrées mal formatées par les utilisateurs. En effet, il est possible d'obtenir des correspondances même lorsque des caractères de formatages tels que ceux utilisés pour les dates: (.-/) sont manquants ou mal placés.
Il est important de noter qu'à ce stade il n'existe pas de lien trivial entre les chaînes de caractères extraites du wiki et les objets utilisés par le moteur d'inférence. Afin de découpler le résultat du scraping du fonctionnement du reste du programme, le scraper instancie des objets (au sens de la programmation orientée-objet) correspondants au concepts recherchés. Ces objets servent d'abstraction pour le moteur d'inférence qui peut alors traiter les données sans se soucier de leur format sous-jacent.
Lorsque l'algorithme de scraping prend fin, nous obtenons un objet, appelé WikiPage, regroupant l'ensemble des concepts extraits pour une page donnée. Une série de WikiPages sont ensuite liés par une nouvelle structure, appelée WikiData, qui représente l'ensemble de tous les concepts extraits de toutes les pages visitées.
Finalement, puisque le moteur d'inférence n'est pas directement dépendant du processus d'obtention des données, il est facile d'étendre l'ensemble des concepts à extraire. Cela se fait en définissant de nouvelles regex ainsi que des structures de données adéquates pour accueillir les informations obtenues du wiki. Nous remplissons ainsi les objectifs fixés pour la récupération des données.
Le moteur d’inférence
Ici, il s’agit d’obtenir des faits à partir d’autres faits et règles. Nous avons utilisé un algorithme d’intelligence artificielle appelé “chaînage avant”, qui nous permet d’effectuer ces déductions. L’algorithme a la forme suivante :
Q = faits existants
Solutions = liste vide
Règles = règles existantes
tant que Q n’est pas vide:
fait = premier élément de Q
si fait n’est pas dans Solutions:
ajouter fait à Solutions
# Vérifie si des règles sont déclenchées par le nouveau fait.
pour chaque règle dans Règles:
si le fait satisfait une des conditions de règle,
et que l’ensemble des faits déduits (Solutions)
peut satisfaire l’ensemble des autres conditions de cette même règle:
ajouter la conclusion de la règle à Q
renvoyer Solutions
Cet algorithme utilise plusieurs éléments de base : Les faits, qui sont des éléments basique dans notre algorithme, et qui peuvent contenir des variables. Des exemple de faits seraient : père(Paul, Pierre) ou oncle(?A, Jean) avec ?A une variable. Les règles, qui suivent la logique des prédicats, et doivent appartenir à l’ensemble des clauses de Horn. Cet ensemble correspond à tout prédicat sous la forme d’une disjonction de littéraux qui sont tous négatifs, sauf au plus un des littéraux qui peut être positifs. Cela nous permet d’avoir des règles de la forme not(A) or not(B) or … or Z, ce qui peut être réécrit sous la forme (A et B et …) => Z. Nous commençons donc à comprendre comment et pourquoi nous pouvons ajouter la conclusion de la règle (notre Z) à l’ensemble des faits déduits, si l’ensemble des conditions de cette règle (A, B, …) sont satisfaites.
De plus, comme des variables sont impliquées dans nos règles (en effet, nous ne savons pas à l’avance pour qui/quoi ces règles s’appliqueront), nous devons utiliser un algorithme d’unification, qui va pouvoir mettre ensemble deux faits qui peuvent être unifiés, à la manière d’une reconnaissance de motif (pattern matching), et renvoyer l’association des variables identifiées comme définies.
== La génération de Graphe de parenté
La génération des graphes de parenté se fait avec 2 types de prédicats:
- Les Mariages ( Mariage de X et Y)
- Les Parents ( La mère de Secundinus Aurelianus est Laelia Eumenius)
Ainsi on peut générer des arbres généalogiques qui seront inscrits dans les discussions de chaque personne concernée. On peut constater qu’un moteur d’inférence n’est pas nécessaire pour générer les graphes. Les graphes sont générés à l’aide d’une bibliothèque GraphViz et d’un standard de représentation des graphes, le langage DOT.
Le wiki writer
Cette étape nous permet de directement écrire sur le wiki les informations utiles obtenues. Etant donné qu’un grand nombre de faits sont déduits, même des faits intermédiaires sans doutes inutiles, il faut pouvoir trier ce qui est obtenu. Ainsi, nous disons que par défaut, aucun fait n’est écrit, sauf certains spécifiés. C’est pour cette raison que nous ne retrouvons en sortie que les faits Erreur de date, Erreur de recontre, Erreur d’élection… Par la suite, étant donné que nous obtenons des informations utiles, mais pas très lisibles, il faut passer par une étape de transcription de l’erreur brute vers une erreur plus compréhensible pour la personne/le bot qui se chargera de modifier la page par la suite.
Nous avions choisi d’écrire directement dans la page InferenceBot - Output. Cependant, après la discussion du mardi 2 mai, utiliser la page discussions nous a semblé être une bonne idée, étant donné que notre bot serait plus utile si il avertissait directement les personnes concernées, plutôt que de les obliger à venir voir la page contenant toutes les erreurs du wiki, afin de voir s'ils ont des problèmes dans leurs pages. C'est pour cette raison que nous écrivons dans cette page, en suivant le format suivant :
== InferenceBot == * fait 1 * fait 2 ... * fait N ----
Tout ce qui précède et tout ce qui suit cette section est conservé. De plus, si la section n'existe pas dans la page de discussion, le bot va la créer (en conservant encore le reste du contenu) à la page discussion.
De plus, étant donné que nous créons les arbres généalogiques de personnes du wiki, il nous faut écrire ces images sur le wiki. De même que pour les faits inférés, nous écrivons dans une section spéciale de la page discussion de la personne. Cette section s'appelle InferenceBotPicture, et contient toutes les images d'arbres généalogiques contenus dans la page (par exemple, pour la page mariage, il peut y en avoir plusieurs).
Afin de faire cette écriture, il nous faut importer premièrement l'image dans le wiki sous le nom Fichier:*nom_de_l'image*, puis mettre un lien de la forme
[[Fichier:*nom_de_l'image*]]
dans chacune des pages l'utilisant. Pour générer le nom de l'image, nous utilisons une méthode de hash des noms des personnes contenues dans cet arbre généalogique. Ceci fonctionne bien, mais a la fâcheuse tendance d'écrire beaucoup d'images différentes sur le site (ralentissant le bot), et de réécrire plusieurs fois les mêmes images entre les différents lancements du bot. De plus, comme nous n'avons pas de pouvoir de suppression d'images, il ne nous est pas possible de supprimer les nombreuses pages créées quand les images ne sont plus utilisées.
Exemple d’Output
Nous avons créé plusieurs pages de test afin de vérifier le comportement de notre bot. Les pages sont Secundinus_Aurelianus, Pompilius_Iuvenalis et Laurentinus_Porcius.
Nous avons directement pu obtenir les informations suivantes sur les pages Discussion:Secundinus_Aurelianus, Discussion:Pompilius_Iuvenalis et Discussion:Laurentinus_Porcius.
Ainsi, comme nous pouvons le voir sur cet exemple provenant de la page Discussion:Secundinus_Aurelianus, le bot d’inférence a pu déduire plusieurs erreurs, comme une erreur de naissance (qui devrait se dérouler avant la mort, pas comme ici); une erreur de rencontre, où deux personnes se sont rencontrées en même temps à deux endroits différents; ainsi que plusieurs dates de mort.
Évaluation des performances
Actuellement, les règles du bot d’inférence se focalisent principalement sur des erreurs de contenu (incohérences dans les dates ou des lieux p.ex.). Sachant que les pages pertinentes du wikipast (donc pas celles crées par des attaques de bots) ont été créées méticuleusement par un étudiant, il est rare qu’elle contiennent de telles erreurs. C’est pourquoi le bot ne génère pas beaucoup d’erreurs autres que celles provoquées par les pages de test. Cependant, nous pensons qu’il est utile d’avoir un tel bot lorsque le nombre de pages augmente et lorsque des utilisateurs et bots commencent à modifier les pages des autres utilisateurs. En effet, il est beaucoup plus facile de faire des erreurs en modifiant les pages d’autres utilisateurs.
Le nombre de faits et d'erreurs inférés dépend aussi du nombre de règles implémentées. Comme indiqué dans la description du bot, il est facile d’ajouter des règles grâce à la modularité de son implémentation. Une des limites de notre bot est le nombre de règles que le responsable du bot doit créer si il veut obtenir des conclusions intéressantes. Cette structure basée sur les règles est aussi un point faible. En effet, le bot construit des prédicats seulement lorsque l'entrée du wiki correspond à un format particulier (ordre des mots par exemple). Le manque de structure de certains types d'entrées rend parfois impossible la création de règle d'inférence.
Concernant le temps nécessaire à l’inférence des faits/erreurs par le bot, il faut savoir que la puissance et le nombre de connexions de l’ordinateur/serveur utilisé sont des facteurs importants. Le bot, lorsqu’il est exécuté sur un ordinateur portable, prend actuellement quelques minutes pour scraper tout le Wikipast et inférer les faits/erreurs. Nous avons implémenté l’utilisation de multiples connexions (réglable simplement) pour scraper plus rapidement, car il s’agit d'une partie prenant une grosse partie du temps total d’exécution (autour de 100 secondes en conditions réelles). L’inférence des faits/erreurs était peu coûteuse lorsque nous avions peu de règles et de faits, cependant à force d'ajouter un grand nombre de faits, par exemple pour détecter que deux lieux ou deux dates sont différentes, étant donné que le temps d’exécution est polynomial selon le nombre d'entrées, nous avons remarqué un certain ralentissement lors des derniers tests, étant donné le grand nombre de faits à traiter et les nouvelles règles ajoutées au projet. Le temps d'écriture est aussi non négligeable à l'heure actuelle, puisqu'il n'a pas été parallélisé, et ne profite pas (encore) d'optimisations afin d'éviter une lecture coûteuse de la page.
Récemment, nous nous sommes heurté au problème suivant : maintenant que nous générons des arbres généalogiques et que nous avons des erreurs qui peuvent impliquer plus d'une page, et que nous réécrivons sur ce qui avait été écrit auparavant dans la section discussions, il nous faut scraper toutes les pages. Si ce n'était pas le cas, il pourrait y avoir des faits existants qui ne seraient pas visibles étant donné que nous ne prendrions que les faits provenant de pages récemment modifiées. Ainsi, les images et les faits ne seraient pas tout à fait justes, ce qui n'est pas acceptable.
Nous avons trouvé que notre bot avait des conflits, surtout avec le bot TangoBot. Les pages de test de notre bot ont des entrées qui se ressemblent à la date ou au lieu près, car nous testons différentes règles qui se concentrent sur les dates, lieux et personnes. TangoBot supprime ce qu'il considère être trop ressemblant et réduit considérablement nos pages de test.