Thesis of my students (4)

Cette thèse décrit la mise en place d'un Intelligent Tutoring System (ITS) dans le logiciel de soutien scolaire de la société Paraschool pour aider les élèves à naviguer sur le site, parmi plusieurs milliers d'items et exercices. Le système est maintenant opérationnel et les versions successives ont été testées en ligne sur maintenant 250.000 utilisateurs accédant au site depuis Internet.

L'optimisation par Hommilière développée dans cette thèse découle d'un premier essai d'utilisation d'un algorithme d'Optimisation par Colonie de Fourmis (OCF) qui a montré ses limites. Contrairement aux fourmis artificielles, les utilisateurs ne sont pas contrôlables : il ne faut pas compter sur un altruisme excessif de leur part, ils ont une activité discontinue (vacances), ils nécessitent un parcours pédagogique personnalisé, ... Bref, les modifications devant être apportées à l'OCF étaient telles qu'il a fallu se rendre à l'évidence que l'utilisation collective d'élèves humains à des fins d'optimisation était un paradigme différent que nous avons appelé Optimisation par Hommilière.

Une deuxième contribution de cette thèse est la mise en place d'un système de notation automatique permettant d'évaluer automatiquement élèves et exercices, fondé sur la notation ELO utilisée dans le monde des échecs.

Outre un puissant outil de suggestion d'exercices, le système a montré qu'il est aussi un très puissant outil de vérification du bon fonctionnement du logiciel d'e-learning, capable de détecter dans les exercices non seulement des erreurs syntaxiques, mais aussi sémantiques, ainsi que des erreurs pédagogiques de positionnement de l'exercice dans un niveau donné.

Pour finir, l'application à l'e-learning de l'Optimisation par Hommilière présentée dans cette thèse n'est qu'un cas particulier. Tous les sites Web fréquentés en temps réel par de nombreux utilisateurs peuvent bénéficier de cette technique pour optimiser leur contenu, leur structure, et s'assurer de leur bon fonctionnement.

L'inflation des quantités de documents disponibles sous forme électronique, sur internet et dans les intranets d'entreprises a entrainé au cours des annéees 1990-2000 le développement d'outils de stockage et de gestion des données électroniques à grande échelle. Parmis ceux-ci, les moteurs de recherche textuelle (text-retrieval) ont désormais une place centrale dans le traitement et la diffusion des informations.

Grâce à des outils sémantiques et linguistiques élaborés, les solutions de recherche textuelle sont devenues très efficaces. Cependant, les particularités des utilisateurs, et l'effort que ceux-ci doivent fournir pour interpréter les résultats de leurs recherches, opposent une dernière barrière à l'amélioration des performances. Les approches statistiques, fondées sur des modèles cognitifs des utilisateurs pour interagir au mieux avec eux, ont prouvé leur efficacité dans des situations au contexte sémantique simple. Mais elles ne permettent pas encore aux outils d'extraction textuelle de répondre de manière personnaliséee et adaptable à des demandes complexes.

L'approche développée dans cette thèse est fondée sur une spécialisation du comportement des outils pour chaque utilisateur. Les modèles cognitifs ne suffisent pas à décrire les comportements des utilisateurs de manière assez complète pour déterminer le traitement le plus adapté des requêtes. Partant de cette constatation, nous avons élaboré un modèle des traitements de requêtes possibles, sans hypothèse a-priori sur le comportement des utilisateurs. Le traitement spécifique à chacun d'eux, contenu dans un profil personnalisé, est adapté dynamiquement grâce à l'historique des documents consultés par l'utilisateur à l'issue des requêtes. Il s'agit d'un problème d'optimisation extrêmement complexe.

L'optimisation des profils est réalisée à l'aide d'un algorithme évolutionnaire, qui maximise une mesure empirique de satisfaction de l'utilisateur. La méthode de programmation génétique parisienne que nous avons développée fait évoluer une population de modules, composants élémentaires de règles de transformation des requêtes. Ces règles sont utilisées pour réécrire les requêtes, ensuite transmise à un moteur de recherche standard permettant de former des listes de documents. De manière invisible pour l'utilisateur, l'évaluation des modules provient de l'analyse des consultations de documents, et fournit à l'algorithme évolutionnaire les informations permettant la mise à jour du profil utilisateur.

Un prototype fonctionnel, Elise, implémente ces mécanismes, bien adaptés à une intégration dans le contexte des intranets et des outils d'extraction textuelle. Si la performance d'Elise, liée aux opinions des utilisateurs, est d'évaluation délicate, les résultats obtenus prouvent qu'Elise a des capacités d'adaptation et de créativité, contrairement aux systèmes traditionnels. Le prototype Elise a permis de prouver la faisabilité de l'approche évolutionnaire interactive pour l'extraction textuelle. L'étape siuvante d'intégration dans un cadre industriel du prototype ne nécessite plus que l'intégration d'outils sémantiques et d'analyse textuelle plus performants, et l'amélioration de l'efficacité algorithmique de certains composants.

La dissimulation d'information est une discipline qui repose à la fois sur le traitement d'image et la cryptographie. Cette thèse s'articule autour de ces deux axes. En ce qui concerne le traitement d'images, les approches fractales présentent une certaine originalité car elles n'agissent ni dans le domaine spatial, ni dans le domaine fréquentiel. Certaines solutions reposent sur un algorithme de compression fractale, dont le point fondamental est la résolution du problème inverse pour les systèmes de fonctions itérées (IFS). Il s'agit, étant donnée une image, de déterminer un IFS dont cette image est l'attracteur. Dans cette perspective, nous développons une méthode d'optimisation stochastique de type évolutionnaire. Ces stratégies cherchent à résoudre des problèmes d'optimisation en s'inspirant du principe d'évolution des espèces. Nous l'adaptons à des situations qui autorisent la reconstruction de la solution à partir d'un sous-ensemble de la population. L'avantage de cette approche est que les individus de la population ne sont plus mis au rebut dès qu'un de leurs chromosomes ne convient pas. Cependant, cet algorithme reste calculatoirement trop coûteux, bien que les résultats obtenus soient meilleurs que ceux des méthodes classiques. Par ailleurs, nous analysons des éléments pour la constitution d'un schéma de tatouage à base de spectres multifractals. La particularité de ces derniers est d'analyser et de répertorier l'irrégularité locale des points d'une image vis-à-vis d'une mesure de référence. Si nos tests montrent une bonne robustesse de l'information de régularité, nous n'avons néanmoins pas pu déterminer un critère suffisamment distinctif pour les mesures de référence. Nous étendons alors les expériences réalisées précédemment pour proposer une méthode d'évaluation automatique des schémas de tatouage. Pour cela, nous avons développé Stirmark Benchmark qui repose sur de nombreux tests (transformations géométriques, marquage multiple, taux de fausses alarmes, etc). Ce logiciel, initialement prévu pour des images, a également été adapté pour des fichiers audios. L'élaboration de ce logiciel nous a montré l'importance du protocole dans lequel s'inscrit le schéma proposé. Pour étudier cette relation, nous appliquons les principaux concepts cryptographiques à la dissimulation d'information. Bien que les problématiques différent, nous constatons que certaines notions s'intègrent directement dans le schéma (preuve à divulgation nulle de connaissance ou partage de secret) alors que d'autres correspondent plutôt au protocole (aspect asymétrique ou signature numérique). La dissimulation d'information s'intéresse également à la recherche de canaux cachés. Après avoir analysé les solutions antérieures proposées sur un réseau, nous montrons que la couche Applications du modèle OSI offre un terrain propice grâce au protocole SSH qui contient deux canaux cachés.

Le domaine de la simulation moléculaire a pour but de simuler un ensemble de particules en interaction représentant un système physico-chimique. Les algorithmes de Monte Carlo par chaîne de Markov appliqués dans ce cas peuvent rencontrer des problèmes d'efficacité statistique analogues à celles rencontrés par la dynamique moléculaire lors de la simulation de molécules complexe, comme par exemple des polymères. Le but étant d'échantillonner l'ensemble des configurations possibles, en accord avec la distribution de Boltzmann-Gibbs, l'efficacité statistique de tels algorithmes réside dans la capacité à fournir plus rapidement des états décorrélés couvrant l'espace des congigurations, constituant ainsi un échantillonnage statistiquement valide. Nous nous sommes intéressés aux possibilités offertes par l'évolution artificielle (EA, classe d'algorithmes d'optimisation stochastique inspirés du principe biologique de l'évolution darwinienne) pour contribuer à améliorer cette efficacité. Ayant exploré l'utilisation de différentes mesures comme critère d'optimisation, nous avons identifié les fréquences relatives des différents mouvements de Monte Carlo, applicables conjointement lors d'une même simulation, comme degrés de liberté pouvant être optimisés. Nous avons combiné des simulations parallèles avec un serveur génétique afin d'effectuer un échantillonnage tout en optimisant simultanément les fréquences des mouvements de Monte Carlo. Nos simulations ont montré qu'il était possible d'obtenir des améliorations par rapport à des réglages de références, pour les critéres considérés. Adaptant cet outil au cadre du Monte Carlo avec thermalisation parallèle (parallel tempering) nous avons pu améliorer certains de ses paramètres et indiqué des pistes pour améliorer encore le choix des températures additionnelles.