Analysis of Case-Based Representability of Boolean Functions by Monotone Theory
Author: Ken Satoh
Source: Lecture Notes in Artificial Intelligence Vol. 1501, 1998, 179 - 190.
Abstract. Classification is one of major tasks in case-based reasoning(CBR) and many studies have been done for analyzing properties of case-based classification [1, 14, 10, 15, 12, 9, 13, 7]. However, these studies only consider numerical similarity measures whereas there are other kinds of similarity measure for different tasks. Among these measures, HYPO system [2, 3] in a legal domain uses a similarity measure based on set inclusion of differences of attributes in cases.
In this paper, we give an analysis of representability of boolean functions in case-based classification using the above set inclusion based similarity. We show that such case-based classification has a strong connection between monotone theory studied in [4, 11]. Monotone theory is originated from computational learning theory and is used to show learnability of boolean function with polynomial DNF size and polynomial CNF size  and is used for deductive reasoning as well . In this paper, we analyze a case-based representability of boolean functions by using the above relationship between the case-based classification by set inclusion based similarity and the monotone theory. We show that any boolean function is representable by a casebase whose size is bounded in polynomial of its DNF size and its CNF size and thus, k-term DNF, k-clause CNF can be efficiently representable in a casebase using set inclusion similarity.
©Copyright 1998 Springer