page 1  (10 pages)
2to next section

Lazy Induction Triggered by CBR

Mario Lenz
GMD-FIRST, Rudower Chaussee 5, 12489 Berlin

Abstract. In recent years, case-based reasoning has been demonstrated
to be highly useful for problem solving in complex domains.
Also, mixed paradigm approaches emerged for combining CBR and induction
techniques aiming at verifying the knowledge and/or building an
efficient case memory. However, in complex domains induction over the
whole problem space is often not possible or too time consuming. In this
paper, an approach is presented which (owing to a close interaction with
the CBR part) attempts to induce rules only for a particular context,
i.e. for a problem just being solved by a CBR{oriented system. These
rules may then be used for indexing purposes or similarity assessment
in order to support the CBR process in the future.

Keywords: Case-based reasoning, rule induction, lazy induction.

1 Introduction

Although case-based reasoning (CBR) has been demonstrated to be highly useful for problem solving in complex domains, there are also shortcuts of this approach. In particular, if case bases grow it becomes harder to access cases efficiently and to verify the knowledge encoded within the case base itself and in additional data structures (such as indices).

To overcome this, mixed paradigm approaches emerged in recent years which try to combine mainly inductive learning methods and CBR. The basic idea is that by learning rules from the stored cases several goals could be achieved: Firstly, extracted rules can be used to (indirectly) verify the case memory. Secondly, induced decision trees allow for an efficient retrieval of cases relevant in a particular problem situation. Thirdly, if induced rules cover a set of cases, the latter could be removed from memory and thus the case base could be kept relatively small.

In contrast to the work published elsewhere (cf. section 2), we present an approach that combines CBR and induction, too, but gives priority to the CBR process | both, for the problem solving and the learning task: In a nutshell, rules will only be induced if suggested by a CBR classification process. In order to present the underlying ideas we have to characterize some fundamental rule- and case-oriented learning and problem solving methods in section 2 before we introduce our technique of lazy induction triggered by CBR in section 3 and illustrate the ideas with some examples from the Travel Agency domain. Finally, we discuss relation to other work in section 4, and sketch problems to be solved in the near future in section 5.

To avoid misunderstandings: The term mixed paradigm mentioned above refers to techniques where CBR and other methods are combined in order to extract knowledge contained within the cases which can be used for verification purposes or for the construction of an efficient case memory. We do not consider work here where two or more co-reasoners exist for problem solving such as described e.g. in [17, 18, 19].