Systèmes experts et réseaux bayésiens

Aujourd’hui le réseau Internet, et plus spécifiquement le web, est de plus en plus utilisé et de plus en plus complet. Les sites web sont nombreux et leur taille est souvent grandissante. Le risque de se perdre dans un site et de ne plus comprendre ce que l’on lit (surcharge coginitive) a donné lieu il y a un peu plus de dix ans à des recherches sur les hypermédias adaptables et adaptatifs [JAC 06]. On dit qu’un hypermédia est adaptable lorsqu’il permet à l’utilisateur de spécifier son profil, ses centres d’intérêt, ses préférences, etc. afin que le site lui proposent uniquement des informations qui l’intéressent. C’est par exemple ce que fait un utilisateur lorsqu’il utilise des portails d’agrégation d’informations (tel que iGoogle). Mais c’est aussi ce que l’on retrouve sur des sites plus institutionnels tel que celui de l’INSA . Dans ce dernier cas, l’utilisateur a la possibilité de spécifier s’il est un candidat (étudiant qui va postuler à l’INSA), un parent, un enseignant/chercheur, un ancien élève ou un professionnel. Les liens proposés sont alors en rapport avec le profil.

Les hypermédias adaptatifs quant à eux sont des hypermédias qui se modifient automatiquement en fonction de l’utilisateur. Cette adaptation peut être le résultat d’une évaluation de l’utilisateur, il doit dans ce cas répondre à un ou plusieurs questionnaires pour le cerner. C’est par exemple le cas des hypermédias adaptatifs pédagogiques. L’apprenant au cours de sa navigation est régulièrement questionné quant à sa compréhension du cours. Ainsi le système peut prendre des décisions concernant les informations qu’il va afficher ou des liens qu’il va proposer. Mais cette adaptation peut aussi être issue d’une analyse de son comportement, qui peut être sa navigation dans le site ou des actions qu’il effectue. Par exemple aujourd’hui de nombreux sites d’achats en ligne vous proposent de nouveaux articles à acheter en fonction de ce que vous avez déjà achetés et de ce qu’ont achetés d’autres utilisateurs qui vous « ressemblent ».

Quelque soit le système utilisé, l’adaptation se fait aussi bien au niveau du contenu des pages qu’au niveau des liens. L’adaptation de navigation est l’adaptation la plus courante. Elle passe par la modification des liens de la page qui est destinée à l’utilisateur avant qu’elle lui soit envoyée. Plusieurs techniques sont utilisées [Bru 98], comme le guidage direct (l’ajout d’un bouton « suivant »), l’ordonnancement des liens (afin d’organiser les liens hypertextes de la page en fonction de leur importance pour l’utilisateur), le masquage des liens (qui enlève les liens hypertextes dont la destination ne peut être comprise ou n’est pas intéressante pour l’utilisateur), ou encore l’annotation des liens (qui permet d’indiquer à l’utilisateur l’objectif du document cible). Attention toutefois à ne pas assimiler adaptation au fait de modifier les liens hypertextes d’un site web dynamiquement. Par exemple, le site web que nous avons utilisé pour notre étude, c’est-à-dire le site web Hypergeo, génère des liens hypertextes au sein des pages avant de les envoyer à l’utilisateur. Toutefois, l’ajout de ces liens est indépendant de l’utilisateur qui utilise le site, et n’est fonction que des articles présents dans le système, afin uniquement d’améliorer l’interconnectivité entre ces derniers. L’adaptation de contenu quant à elle, consiste à modifier les informations présentées par chaque page. Cette adaptation est plus complexe car elle requiert de modéliser les informations que le site présente, de posséder plusieurs médias pour présenter une notion et de vérifier si l’agencement des médias sélectionnés est cohérent [Del 00].

Systèmes experts et réseaux bayésiens 

La construction de systèmes capables d’apprendre, d’analyser et de réagir comme l’être humain est un rêve de l’homme depuis qu’il a inventé la machine. Nous allons nous intéresser aux systèmes experts qui ont donné beaucoup d’espoir et ont donc été l’objet d’une production scientifique importante.

Systèmes experts

Un système à base de connaissances est un système informatique utilisant des connaissances déjà acquises pour résoudre des problèmes ou pour aider l’homme à prendre des décisions dans un domaine donné [Ake 10]. La connaissance est définie par « les faits, les informations, ou les compétences que la personne acquière par l’expérience ou l’éducation » . Un système expert est un cas particulier de systèmes à base de connaissances où cette base est construite à partir de l’expertise humaine. L’objectif d’un système expert est donc de modéliser les connaissances et le raisonnement de l’expert. Autrement dit, son but est de reproduire les compétences d’un expert pour résoudre un problème. Ce système doit donc connaître des faits dans le domaine d’expertise, être capable de les traiter et de déterminer la réponse la plus adaptée au problème. Historiquement l’un des premiers systèmes experts est MYCIN [Buc 84] qui a été créé en 1974. Il a été construit pour diagnostiquer les infections bactériennes. Un deuxième exemple est PROSPECTOR (1978) qui a pour objectif d’aider à évaluer la qualité d’un site géologique en vue d’une exploitation minière [McC 96].

Historique

Dès la fin des années 60 et le début des années 70, la recherche autour des systèmes experts a été très active et a donné lieu à de nombreuses publications et à l’implantation de nombreux systèmes. Une des raisons de cet engouement était le fait que les algorithmes classiques en intelligence artificielle (tels que les algorithmes de parcours de solutions de type min − max, A∗, etc.) ne permettaient pas de résoudre certains problèmes liés à l’expertise, au diagnostique, etc. La communauté scientifique pensait qu’avec ces nouveaux systèmes nous pourrions aider, conseiller, voire remplacer les experts, comme les médecins, les géologues, ou encore les enseignants lorsque l’on a voulu adosser à ces systèmes des systèmes d’apprentissage. Par exemple les systèmes d’enseignement GUIDON [Cla 83] puis GUIDON2 [Cla 86] utilisaient les systèmes expert MYCIN et NEOMYCIN  . Parallèlement à des logiciels spécifiques, plusieurs langages de programmation logique ont vu le jour, comme par exemple la famille des langages Prolog, dont la première version a été créé en 1973 par Colmerauer et al. [Col 73]. Jusqu’au milieu des années 80, les systèmes experts représentaient le futur de l’informatique, ils ont même fait l’objet d’un programme du gouvernement japonais en tant que fondement théorique pour la création des ordinateurs de cinquième génération.

Cycle de développement d’un système expert 

La création d’un système expert commence par le recueil de l’expertise d’un ou plusieurs experts. Les techniques et les méthodes afférentes à cette étape sont issues de l’ingénierie des connaissances. Les professionnels de ce domaine sont des informaticiens, spécialistes en intelligence artificielle. Ils discutent avec les experts et les observent durant leur résolution de problème. Cette expertise doit ensuite être formalisée. On obtient alors des informations ou des relations qui sont toujours vraies dans le domaine étudié, c’est ce que l’on nomme les faits, et des compétences de déduction que l’on nomme les règles. Quelques fois, certaines connaissances « heuristiques », des bonnes pratiques, peuvent aussi être formalisées.

Par la suite, en fonction de ce que l’on demandera au système, l’une des deux techniques de résolution de problèmes que sont le « chaînage avant » ou le «chaînage arrière » (et quelque fois un mixte de ces deux techniques) est choisie. Enfin, une fois développés, les systèmes experts doivent être validés. Cette validation peut être effectuée « à la main », à partir d’exemples concrets. Mais à l’image des outils de tests unitaires en génie logiciel, des framework de tests de systèmes experts ont été développés dans les années 80 [OLe 88].

Limites des systèmes experts

Aujourd’hui, à par quelques exemples célèbres comme le système MEPRA qui permet d’aider à la prévention des risques d’avalanche, les systèmes experts ne sont plus beaucoup étudiés et utilisés. En effet, créer un système expert est un processus coûteux et est difficilement évolutif. Coûteux à développer car formaliser l’expertise d’un domaine est un problème complexe qui peut prendre beaucoup de temps. Difficilement évolutifs car la modification, la suppression ou l’ajout de règles peut entraîner des dysfonctionnements. Or il existe peu de domaines qui n’évoluent pas. Mais surtout, dans le monde réel, il est rare que l’on puisse toujours répondre aux questions sans aucun doute ou de représenter les faits de manière exacte. Dès lors, l’incertitude et l’approximation ont besoin d’être représentées aussi bien au niveau des faits qu’au niveau des règles. Ceci ne peut pas être représenté avec la logique utilisé par les systèmes experts classiques, il faut donc d’autres mécanismes de représentation de ces informations. Plusieurs techniques ont été proposées comme par exemple la logique floue, les facteurs de certitudes, les réseaux bayésiens, etc.

Réseaux bayésiens

Les réseaux bayésiens mixent la théorie des graphes avec celle des probabilités [Pea 88]. Un réseau bayésien est composé d’un graphe orienté acyclique. Les liens entre les nœuds représentent les dépendances entre eux (la probabilité conditionnelle). Plus formellement, le réseau bayésien est défini par [Nai 04] :

– un graphe orienté acyclique G = (X, E), où X est l’ensemble des nœuds du graphe et E l’ensemble des arcs entre les nœuds,
– un espace probabiliste fini (Ω, Z, p),
– un ensemble de variables aléatoires définies sur (Ω, Z, p) et associées aux nœuds du graphe .

Table des matières

Introduction
1 Systèmes experts et réseaux bayésiens
1.1 Introduction
1.2 Systèmes experts
1.2.1 Historique
1.2.2 Cycle de développement d’un système expert
1.2.3 Architecture d’un système expert
1.2.3.1 Base de connaissance
1.2.3.2 Moteur d’inférence
1.2.4 Limites des systèmes experts
1.3 Réseaux bayésiens
1.3.1 Structure du réseau bayésien
1.3.2 Définition de la probabilité conditionnelle
1.3.3 Inférence
1.3.4 Exemple
1.4 Conclusion
2 Apprentissage supervisé et Apprentissage non supervisé
2.1 Introduction
2.2 Distance, dissimilarité et similarité
2.3 Apprentissage non supervisé (clustering)
2.3.1 Kmeans
2.3.2 Carte de Kohonen
2.4 Apprentissage supervisé (classification)
2.4.1 Algorithme des k plus proches voisins
2.4.2 SVM, le séparateur à vaste marge (Support Vector Machine)
2.4.2.1 Problème linéairement séparable
2.4.2.2 Cas non linéairement séparable
2.5 Évaluation de la qualité de la similarité et de la classification
2.5.1 Évaluation de la mesure d’une similarité
2.5.1.1 Matrice de Gram
2.5.1.2 Méthodes de visualisation de données
2.5.2 Évaluation d’une classification
2.6 Conclusion
3 Web Usage Mining et son utilisation sur les traces d’Hypergéo
3.1 Introduction
3.2 WUM : Web Usage Mining
3.2.1 Collecte et prétraitement des données
3.2.2 Découverte de modèle
3.2.2.1 Cluster mining
3.2.2.2 Association rule mining
3.2.2.3 Sequential pattern mining
3.3 Utilisations du WUM pour l’adaptation des hypermédias
3.4 Motifs caractéristiques
3.4.1 Identification et fouille des motifs caractéristiques
3.4.1.1 Méthode des arbres des motifs fréquents (FP-tree)
3.4.1.2 Analyse du FP-tree (la méthode FP-tree growth)
3.4.2 Fonction d’identification à base de réseaux bayésiens
3.4.2.1 Réseaux bayésiens naïfs et réseaux bayésiens naïfs multi-net
3.4.2.2 Construction des réseaux bayésiens pour les motifs caractéristiques
3.4.2.3 Identification d’un nouvel utilisateur
3.5 Contexte : le site web Hypergéo
3.5.1 Organisation
3.5.2 Système de publication SPIP
3.5.3 Recueil des données
3.6 Applications des motifs caractéristiques à Hypergéo
3.7 Conclusion
4 Dissimilarités entre traces basées sur la similarité entre éléments
Conclusion

Lire le rapport complet