PhD proposal: Reasoning with positive and negative cases

PhD subject proposed by Emmanuel Nauer and Jean Lieber,(Emmanuel.Nauer@loria.fr) and Jean Lieber (Jean.Lieber@loria.fr)
UL, CNRS, Inria, Loria, F-54000 Nancy

Scientific Context.

Case-based reasoning (CBR [1]) is a reasoning model relying on a case base BC where a case is a representation of a problem-solving experience, generally given by a pair (pb; sol(pb)) where pb is a problem in a given application domain and sol(pb) is a solution of pb. For example, in the cooking domain, a problem can be pb_pineapple = “I want a recipe with pineapple.” and a solution could be a pineapple pie recipe.  A source case is a case (srce; sol(srce)) of BC. A CBR session takes as input a new problem, the target problem tgt and is usually decomposed into the following steps. First, the source case (srce; sol(srce)) that is the closest one to tgt is selected (retrieval step). Then, sol(srce) is modified into a solution sol(tgt) of tgt (adaptation step). After that, the newly formed case (tgt; sol(tgt)) is proposed to the user (validation step) and, if validated, stored in BC (memorization step). For example, if a cooking CBR system is queried with tgt = pb_pineapple, a recipe of apple pie may be found (if there are no source case more similar to tgt than that) and then it can be adapted by substituting apples by pineapples (changing the quantities—3 apples would correspond to a portion of a pineaple—and making other adjustments).

For this purpose, a CBR system usually uses a knowledge base constituted of four knowledge containers [2]: BC, the domain ontology, the similarity (i.e., retrieval knowledge) and the adaptation knowledge (often represented by adaptation rules). In order to enrich this knowledge base, knowledge acquisition methods and tools (with experts and/or from data) have been studied. For example, we have studied adaptation knowledge acquisition using knowledge discovery techniques [3, 4].
This classical schema for CBR (or one of its variants) is based on the implicit assumption that the source cases are positive cases: they are assumed to be satisfying (in a sense that is largely domain-dependent: in cooking, a positive case corresponds to a recipe that is appreciated by many people). Now, there exist also negative cases, in particular the cases (tgt; sol(tgt)) proposed by adaptation but rejected at the validation time. Such cases are not considered by a classical CBR system, which is a waste of potentially useful knowledge units. One way to overcome this difficulty is to initiate an interaction with  the expert to correct the negative case and learn knowledge units that avoid the reproduction of errors. This approach has been developed, it is effective, but it is costly in term of human-machine interaction [5, 6].

Objective of the thesis.

The objective of this thesis is to consider these negative cases, once labelled as such, as knowledge units for themselves for future CBR sessions. The main idea is that the case base is partitionned in BC = BC+ U BC- and that a source case is used in a different way according to the fact that it is positive (member of BC+) or negative (member of BC-). A new schema for CBR might have to be built, but here are ideas on how to re-consider the various components of a CBR system to take into account these two types of cases:

Retrieval The idea could be to retrieve the closest positive source case (srce+; sol(srce+)) and the closest negative source case (srce-; sol(srce-)). If classical retrieval is implemented with the help of a similarity measure, should there be two such measures?

Adaptation The principle could be to reuse (srce+; sol(srce+)) and to “avoid” (srce-; sol(srce-)). In a formalism with logical negation for problems and solutions, does avoiding the negative case amount to reuse (NOT srce-; NOT sol(srce-))? Another logical way to see it would be to use belief change operations: belief revision is used for some approaches to adaptation [7] and could be used for reusing (srce+; sol(srce+)), but another belief change operations, like contraction could be used for avoiding (srce-; sol(srce-)).

Validation and memorization The interactive validation process should remain the same: the newly formed case (tgt; sol(tgt)) is either tagged as positive or negative. Then, memorization would store (tgt; sol(tgt)) in any situation, but choose to put it in BC+ or BC- according to the result of its validation.

Knowledge acquisition methods and tools

For each knowledge container, the question raised is on how to handle the positive/negative cases:
Case base Beside the negative cases learnt through the (in)validation-memorization process, should there be particular effort to acquire negative cases? If so, should these cases be chosen close to positive cases?

Domain ontology Each positive case is supposed to be consistent with the domain ontology: indeed, the domain ontology may be seen as a set of necessary conditions for a case to be valid. By contrast, a negative case does not have to be inconsistent with the domain ontology: otherwise, this would mean that the ontology would be complete (in the logical sense), which is unusual in CBR. However, negative cases could be used to learn knowledge units to improve the domain ontology: each time a case is labelled as negative, the domain ontology can be specialized in order to be inconsistent with this case. This can be likened to the classical problem of learning with positive and negative examples in machine learning [8].

Similarity As mentionned above, retrieval of the closest positive case and retrieval of a closest negative source case may be of different natures. Therefore, this difference can reflect on the acquisition of retrieval knowledge.

Adaptation knowledge A classical way of adaptation knowledge learning consists in mining the case base for differences between source cases and then in interpreting the result in terms of adaptation rules. The question here is how this principle can be modified to take into account both positive and negative cases?

Application Context.

This thesis must be validated in a practical application. For this purpose two applications of CBR developed within our team are considered. The first one is TAAABLE in the cooking domain, which solves problems as the ones mentionned in the examples above. Some negative cases have already been collected: they are recipes that users consider to be bad. The second one is a starting application in medical diagnosis based on nuclear image reports. In this application, a negative case would be a faulty diagnosis.

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.

To candidate, the following documents are required:

  • Curriculum Vitae;
  • Motivation letter;
  • Copy of diplomas and marks for License and Master (or 5 last years);
  • Master’s thesis (or equivalent) if already completed, or a description of your work in progress;
  • At least one recommendation letter from who supervises you during your master’s internship (the letters of recommendation must be sent directly to the thesis supervisors).

En ce moment

Logo du CNRS
Logo Inria
Logo Université de Lorraine