Learnability of min-max pattern classifiers

Abstract This paper introduces the class of ihresholded mm-max functions and studies their learning underthe probably approximately correct (PAC) model introduced by Valiant. These functions can be usedas pattern classifiers of both real-valued and binary-valued feature vectors. They are a lattice-theoreticgeneralization of Boolean functions and are also related to three-layer perceptrons and morphologicalsignal operators. Several subclasses of the thresholded mm-max functions are shown to be learnableunder the PAC model. 1 Introduction In the field of machine learning there have been many theoretical advancements on distribution-free learningof Boolean functions. This learning framework is also known as the probably approximately correct (PA C)model, pioneered by Valiant (1984) and further developed by him and other researchers. There is alreadya wealth of literature about the PAC learning model; examples include Valiant (1984,1985), Blumer etal. (1987,1989), Haussler (1990), Kearns, Li, Pitt & Valiant (1987), Kearns (1990), Rivest (1990), andSchapire (1991). Most of the results in PAC learning deal with Boolean functions. If such functions areused as (Boolean) pattern classifiers, then the input features must be binary-valued. Although this maybe sufficient for classifying high-level predicate-like features, most of the pattern recognition applications,for example in computer speech and object recognition, involve real-valued feature vectors. For example,Figure 1 shows morphological size histograms of binary character images, which we have experimentallyfound to be promising real-valued features for character recognition; the values of the normalized sizehistograms are real numbers in [0, 1].In this paper, we present a class of classifiers, called thresholded rain-max functions, which can accept asinputs both real-valued and binary-valued feature vectors. Each input variable to these functions is in therange [0, 1], in contrast to {O, 1} for the Boolean classifiers. Moreover, these thresholded mm-max functionsare natural generalizations of the Boolean functions, because they are based on MIN/MAX operationswhich are the lattice-theoretic counterparts of Boolean AND/OR operations on real numbers. Althoughthere exist many types of classifiers for real-valued data, the class of thresholded mm-max functions hasthe appealing property that many of its large subclasses are PAC learnable (as will be shown later).Another motivation for working with the thresholded mm-max functions is their close relation to a largeclass of nonlinear signal/image operators known as morphological filters, which are defined via mm-maxoperations on their inputs. As discussed in Serra (1982) and Maragos & Schafer (1990), these mm-maxmorphological operators can be applied to a broad variety offeature extraction and shape analysis/detectiontasks in images or arbitrary geometrical objects. Hence, learning of the thresholded mm-max functionsprovides an ability for automated training of the above feature extraction and shape analysis/detectionsignal operators.This paper is organized as follows: In Section 2, we define the mm-max functions and their thresh-olded counterparts. A discussion of their relations with Boolean classifiers and three-layer perceptrons isincluded. We also investigate aspects of their representation power using techniques from mathematicalmorphology. Section 3 provides a brief summary of prior results from PAC learning used in later sectionsfor proving learnability of subclasses of thresliolded mm-max functions. This is followed by three sectionsthat contain the major learnability results of this paper. Section 4 discusses the learnability of a subclass