PAB-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 continuous 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

• And87: T. Anderson. An Introduction to Multivariate $tatzstical Analysis. John Wiley, New York, 1987.
• AP92: S. Anoulova and S. P51t. Pab-decisions on continous distributed features, to be published as technical report, University of Dortmund, 1992.
• ATW91: Naoki Abe , Manfred K. Warmuth , Jun-ichi Takeuchi, Polynomial learnability of probabilistic concepts with respect to the Kullback-Leibler divergence, Proceedings of the fourth annual workshop on Computational learning theory, p.277-289, August 05-07, 1991, Santa Cruz, California, United States
• BEHW89: Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
• DH73: R.O. Duda and P.E. Hart. Pattern Classification and Scene Analysis. John Wiley, New York, 1973.
• Dui76: R. Duin. A sample size dependent error bound. In 3rd International Conference on Pattern Recognition, 1976.
• FPS91: Paul Fisher , Stefan Pölt , Hans Ulrich Simon, Probably almost Bayes decisions, Proceedings of the fourth annual workshop on Computational learning theory, p.88-96, August 05-07, 1991, Santa Cruz, California, United States
• FW70: D. Faddejew and W.Faddejewa. Numerische Methoden der Linearen Algebra. Oldenbourg Verlag, Munich, 1970.
• Gan86: F. Gantmacher. Matrizentheorie. Springer- Verlag, Berlin, 1986.
• Hau89: D. Haussler. Generalizing the pac model: Sample size bounds from metric dimensionbased uniform convergence results. In 30th Annual Symposium on Foundations of Computer Sciences. Morgan Kaufmann, San Mateo, CA, 1989.
• JK70: N.L. Johnson and S. Kotz. Continous Univariate Distributions - 1. Houghton Mifflin Company, Boston, 1970.
• KS90: M.J. Kearns and P~.E Schapire. Efficient distribution free learning of probabilistic concepts. In 31st Annual Symposium on Foundations of Computer Sciences. Computer Society Press of the IEEE, Washington, D.C., 1990.
• Pet87: V. Petrov. Limit Theorems for Sums of Indepedndet Random Variables (in Russian). Nauka, Moskau, 1987.
• Yam90: Kenji Yamanishi, A learning criterion for stochastic rules, Proceedings of the third annual workshop on Computational learning theory, p.67-81, August 06-08, 1990, Rochester, New York, United States

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical

Additional Classification:
  G. Mathematics of Computing

General Terms:
Theory, Verification