Some Discriminant-based PAC Algorithms

A classical approach in multi-class pattern classication is the following. Estimate prob-ability distributions that generated the observations for each label class, and then label new instances by applying the Bayes classier to the estimated distributions. That approach pro-vides more useful information than just a class label; it also provides estimates of the conditional distribution of class labels, in situations where there is class overlap. We would like to know whether it is harder to build accurate classiers via this approach, than by techniques that may process all data with distinct labels together. In this paper we make that question precise by considering it in the context of PAC learnability. We propose two restrictions on the PAC learning framework that are intended to correspond with the above approach, and consider their relationship with standard PAC learning. Our main restriction of interest leads to some interesting algorithms that show that it is not more demanding that various other well-known restrictions on PAC learning. An alternative slightly milder restriction turns out to be almost equivalent to unrestricted PAC learning