Lehrstuhl Mathematik & InformatikPAB-Decisions for Boolean and Real-Valued Features
Abstract. In this paper, we investigate the problem of classifying objects which are given by feature vectors with Boolean or real entries. Our aim is to "(efficiently) learn probably almost optimal classifications" from examples. A classical approach in pattern recognition uses empirical estimations of the Bayesian discriminant functions for this purpose. We analyze this approach for different classes of distribution functions: In the Boolean case we look at the k-th order Bahadur-Lazarsfeld expansions and k-th order Chow expansions and in the continous case at the class of normal distributions. In all cases, we obtain polynomial upper bounds for the required sample size. The bounds for the Boolean case improve and extend results from [FPS91].
References:
[FPS91] P. Fischer, S. Pölt, H. U. Simon,
Probably almost bayes decisions,
in "The 1991 Workshop on Computational Learning Theory", Morgan Kaufmann,
San Mateo, CA, 1991.