Offre de thèse : Raisonner avec des cas positifs et négatifs

Sujet de thèse proposé par Emmanuel Nauer (Emmanuel.Nauer@loria.fr) et Jean Lieber (Jean.Lieber@loria.fr)

Contexte scientifique

Le raisonnement à partir de cas (RàPC [1]) est un modèle de raisonnement s’appuyant sur une base de cas BC où un cas est une expérience de résolution de problème généralement sous la forme d’une paire (pb; sol(pb)) où pb est un problème dans un domaine d’application donné et sol(pb) est une solution pour pb. Par exemple, dans le domaine de la cuisine, un problème peut être pb_ananas =“Je veux une recette avec de l’ananas.” et une solution serait une recette de tarte à l’ananas. Un cas source est un cas (srce; sol(srce)) de BC.
Un processus de RàPC prend en entrée un nouveau problème, le problème cible cible et est habituellement décomposé en plusieurs phases. Premièrement, le cas source (srce; sol(srce)) qui est le plus similaire à cible est sélectionné (phase de remémoration). sol(srce) est alors modifié en une solution sol(cible) de cible (phase d’adaptation). Ce nouveau cas généré (cible; sol(cible)) est ensuite proposé à l’utilisateur (phase de validation) et, s’il est validé, stocké dans BC (phase de mémorisation). Par exemple, si un système de RàPC culinaire est interrogé avec cible = pb_ananas, une recette de tarte aux pommes peut être trouvé et être adapté en remplaçant les pommes par de l’ananas (d’autres ajustements peuvent également être réalisés, comme par exemple, la modification des quantités, 3 pommes correspondraient à un ananas entier).

 

Un système de RàPC utilise habituellement une base de connaissances constitué de quatre conteneurs de connaissances [2] : BC, une ontologie du domaine, des connaissances de similarité (pour la recherche des cas similaires) et des connaissances d’adaptation (souvent représentées par des règles d’adaptation). Pour enrichir cette base de connaissances, des méthodes et des outils d’acquisition de connaissances (avec des experts et/ou à partir de données) ont été développées. Par exemple, nous avons étudié l’acquisition de connaissances d’adaptation reposant sur des techniques d’extraction de connaissances à partir de données [3, 4].

 

Ce schéma classique de RàPC (ou une de ces variantes) est fondé sur l’hypothèse implicite que les cas sources sont des cas positifs : ils sont considérés comme étant satisfaisants (e.g. en cuisine, un cas positif correspond à une recette qui est appréciée par plusieurs personnes). Maintenant, il existe également des cas négatifs, en particulier les cas (cible; sol(cible)) proposés par l’adaptation mais rejetés lors de la phase de validation. De tels cas ne sont habituellement pas considérés par un système de RàPC, alors qu’ils sont des unités de connaissances potentiellement intéressantes à exploiter.

Une façon d’appréhender la prise en compte de ces cas négatifs est d’initier une interaction avec l’expert pour corriger les cas négatifs et apprendre des unités de connaissances qui empêcheront de reproduire des erreurs. Cette approche a été développée et implémentée mais est coûteuse sur l’aspect de l’interaction homme-machine [5, 6].

Objectif de la thèse.

L’objectif de cette thèse est de considérer les cas négatifs, une fois identifiés comme tels, comme des unités de connaissances à part entière pour les sesssions de RàPC à venir. L’idée principale est que la base de cas est partitionnée en BC = BC+ U BC- et qu’un cas source est utilisé de façon différenciée s’il est un cas positif (appartenant à BC+) ou s’il est un cas négatif (appartenant à BC-). Un nouveau schéma pour le RàPC pourrait être défini à partir des idées suivantes, qui permettraient de reconsidérer comment les différents composants d’un système de RàPC pourraient prendre en compte ces deux types de cas :
Remémoration L’idée pourrait être de rechercher le cas positif le plus proche (srce+; sol(srce+)) et le cas négatif le plus proche (srce-; sol(srce-)). Si une remémoration classique est implémentée avec une mesure de similarité, devrait-il y avoir deux mesures ?

Adaptation Le principe pourrait être de réutiliser (srce+; sol(srce+)) et d’éviter (srce-; sol(srce-)). Dans un formalisme avec négation logique pour représenter les problèmes et les solutions, est-ce que éviter le cas source négatif revient à utiliser (NOT srce-;NOTsol(srce-)) ? Une autre façon logique à considérer serait d’utiliser des opérations de révision des croyances : la révision des croyances est utilisée dans certaines approches d’adaptation [7] et pourrait servir pour utiliser (srce+; sol(srce+)), tandis que d’autres opérateurs de révision des croyances, comme la contraction, pourraient servir à éviter (srce-; sol(srce-)).
Validation and mémorisation Le processus de validation interactif devrait rester le même : le nouveau cas généré (cible; sol(cible)) est étiqueté comme positif ou négatif. La mémorisation stockerait alors toujours (cible; sol(cible)) mais le placerait soit dans BC+, soit dans BC-, selon l’étiquette attribuée lors de la validation.

Méthodes et outils d’acquisition de connaissances

Pour chaque conteneur de connaissances, la question soulevée est comment gérer les cas positifs/négatifs :

Base de cas  Au delà des cas négatifs appris à travers le processus de validation-mémorisation, devrait-il y avoir un effort particulier pour acquérir des cas négatifs ? Et si tel est le cas, doivent-ils être choisis proches des cas positifs ?

Ontologie du domaine Chaque cas positif est supposé être consistant avec l’ontologie du domaine. En effet, l’ontologie du domaine peut-être vue comme un ensemble de conditions nécessaires pour qu’un cas soit valide. À l’opposé, un cas négatif ne doit pas être inconsistant avec l’ontologie du domaine : cela signifierait que l’ontologie serait complète (au sens logique), ce qui est inhabituel en RàPC. Cependant, les cas négatifs pourraient être utilisés pour apprendre des unités de connaissances pour améliorer l’ontologie du domaine : chaque fois qu’un cas est étiqueté comme négatif, l’ontologie du domaine pourrait être spécialisée dans le but d’être inconsistante avec ce cas. Ceci est lié au problème classique d’apprentissage sur des exemples positifs et négatifs en apprentissage automatique [8].

Similarité Comme mentionné précédemment, la remémoration du cas source positif le plus similaire et du cas source négatif le plus similaire peut être de différentes natures. C’est pourquoi, cette différence peut se répercuter sur l’acquisition des connaissances de similarité.

Connaissances d’adaptation Une façon classique d’acquérir des connaissances d’adaptation consiste à extraire de la base de cas les différences entre cas sources et d’interpréter les résultats comme des règles d’adaptation. La question ici est comment ce principe peut-il être modifié pour prendre en compte à la fois les cas positifs et les cas négatifs ?

Contexte applicatif.

Cette thèse doit être validée à travers une application concrète. Pour cela, deux applications de RàPC développées au sein de l’équipe sont à considérer. La première est TAAABLE dans le domaine culinaire, qui résoud des problèmes comme ceux mentionnés dans les exemples précédents. Certains cas négatifs ont déjà été collectés ; il s’agit de recettes jugées mauvaises par des utilisateurs. La seconde est une application récente de diagnostic médical à partir de de comptes-rendus d’images nucléaires. Dans cette application, un cas négatif correspond à une erreur de diagnostic.

References

[1] C. K. Riesbeck and R. C. Schank. Inside Case-Based Reasoning. Lawrence Erlbaum Associates, Inc., Hillsdale, New Jersey, 1989.
[2] M. Richter and R. Weber. Case-based reasoning: a textbook. Springer Science & Business Media, 2013.
[3] M. d’Aquin, F. Badra, S. Lafrogne, J. Lieber, A. Napoli, and L. Szathmary. Case Base Mining for Adaptation Knowledge Acquisition. In M. M. Veloso, editor, Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI’07), pages 750–755. Morgan Kaufmann, Inc., 2007.
[4] Emmanuelle Gaillard, Jean Lieber, and Emmanuel Nauer. Adaptation knowledge discovery for cooking using closed itemset extraction. In The Eighth International Conference on Concept Lattices and their Applications – CLA 2011, Nancy, France, October 2011.
[5] A. Cordier, B. Fuchs, J. Lieber, and A. Mille. Failure Analysis for Domain Knowledge Acquisition in a Knowledge-Intensive CBR System. In Proceedings of the 7th International Conference on Case-Based Reasoning, LNCS 4626, pages 463–477, Belfast, 2007. Springer.
[6] F. Badra, A. Cordier, and J. Lieber. Opportunistic Adaptation Knowledge Discovery. In Case-Based Reasoning Research and Development (ICCBR 2009), 2009. 60–74.
[7] J. Cojan and J. Lieber. Applying Belief Revision to Case-Based Reasoning. In H. Prade and G. Richard, editors, Computational Approaches to Analogical Reasoning: Current Trends, volume 548 of Studies in Computational Intelligence, pages 133 – 161. Springer, 2014.
[8] R. Michalski, J. Carbonell, and T. Mitchell. Machine learning: An artificial intelligence approach. Springer Science & Business Media, 2013.

Documents nécessaires pour postuler :

  • CV ;
  • Lettre de motivation ;
  • Copie des diplômes et relevés de notes pour Licence et Master (ou les 5 dernières années) ;
  • Mémoire de Master (ou équivalent) si déjà complété, ou une description des travaux en cours ;
  • Au moins une lettre de recommandation de la personne qui vous encadre (a encadré) durant votre stage de master (les lettres de recommandation doivent être envoyées directement aux encadrants de thèse).

En ce moment

Logo du CNRS
Logo Inria
Logo Université de Lorraine