Proceedings

Generalization Bounds for Weighted Binary Classification with Applications to Statistical Verification

Download BibTeX Cite

Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 722-726.

© 2005 International Joint Conferences on Artificial Intelligence

Abstract

We describe an approach to statistically verifying complex controllers. This approach is based on deriving practical Vapnik-Chervonenkis-style (VC) generalization bounds for binary classifiers with weighted loss. An important case is deriving bounds on the probability of false positive. We show how existing methods to derive bounds on classification error can be extended to derive similar bounds on the probability of false positive, as well as bounds in a decision-theoretic setting that allows tradeoffs between false negatives and false positives. We describe experiments using these bounds in statistically verifying computational properties of an iterative controller for an Organic Air Vehicle (OAV).

  1. P. L. Bartlett, S. Boucheron, and G. Lugosi. Model selection and error estimation. Mach. Learn., 48(1-3):85-113, 2002.
  2. P.L. Bartlett, O. Bousquet, and S. Mendelson. Local Rademacher complexities. Annals of Statistics, 2005. To appear.
  3. A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. J. ACM, 36(4):929-965, 1989.
  4. O. Bousquet. A Bennett concentration inequality and its application to suprema of empirical processes. C. R. Acad. Sci. Paris, Ser. I, 334:495-500, 2002.
  5. R. Dudley. Uniform Central Limit Theorems. Cambridge University Press, Cambridge, MA, 1999.
  6. M.R. Elgersma and B.G. Morton. Nonlinear six-degree-of-freedom aircraft trim. Journal of Guidance, Control, and Dynamics, 23(2):305-311, 2000.
  7. D. Haussler. Sphere packing numbers for subsets of Boolean n- cube with bounded Vapnik-Chervonenkis dimension. Journal of Combinatorial Theory (A), 69:217-232, 1995.
  8. V. Koltchinskii and D. Panchenko. Rademacher processes and bounding the risk of function learning. High Dimensional Prob- ability II, 47:443-459, 2000.
  9. V. Koltchinskii. Rademacher penalties and structural risk minimiza- tion. IEEE Transactions on Information Theory, 47(5):1902- 1914, July 2001.
  10. P. Massart. Some applications of concentration inequalities to statis- tics. Annales de la Faculté des Sciences de Toulouse, IX(2):245- 303, 2000.
  11. C. McDiarmid. Concentration. In M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, editors, Probabilistic method for algorithmic discrete mathematics, pages 195-248. Springer- Verlag, New York, 1997.
  12. D. Panchenko. Some extensions of an inequality of Vapnik and Chervonenkis. Electronic Communications in Probability, 7:55- 65, 2002.
  13. N. Sauer. On the density of families of sets. Journal of Combinato- rial Theory, 13:145-147, 1972.
  14. John Shawe-Taylor, Martin Anthony, and N. L. Biggs. Bounding sample size with the Vapnik-Chervonenkis dimension. Discrete Appl. Math., 42(1):65-73, 1993.
  15. M. Talagrand. Sharper bounds for gaussian and empirical processes. Annals of Probability, 22:20-76, 1994.
  16. M. Talagrand. New concentration inequalities for product spaces. Inventiones Mathematicae, 126(3):505-563, 1996.
  17. P. Turney. Types of cost in inductive concept learning. In Workshop on Cost-Sensitive Learning at the Seventeenth International Con- ference on Machine Learning, pages 15-21, Stanford University, California, 2000.
  18. V. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and Its Applications, 16:264-280, 1971.
  19. V. Vapnik. The Nature of Statistical Learning Theory. Springer, second edition, 2000.
  20. M. Vidyasagar. Learning and Generalization, with Applications to Neural Networks. Springer, second edition, 2003.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards