Combinatorial shell bounds for generalization ability

1. V. N. Vapnik and A. Y. Chervonenkis, “On the Uniform Convergence of Relative Frequencies of E vents to Their Probabilities,” Theory Probab. Its Appl. 16, 264–280 (1971).

   Article  MATH  Google Scholar 

2. L. G. Valiant, “A Theory of the Learnable,” in Proc. 16th Ann. ACM Symp. On Theory of Computing—ACM (Boston, 1984), pp. 436–445.

3. O. Bousquet, S. Boucheron, and G. Lugosi, “Introduction to Statistical Learning Theory,” in Advanced Lectures in Machine Learning (Springer, 2004), pp. 169–207.

4. S. Boucheron, O. Bousquet, and G. Lugosi, “Theory of Classification: Some Recent Advances,” ESAIM Probab. Stat. 9, 323–375 (2005).

   Article  MATH  MathSciNet  Google Scholar 

5. D. Haussler, N. Littlestone, and M. Warmuth, “Predicting (0, 1)-Functions on Randomly Drawn Points,” in Ann. IEEE Symp. On Foundations of Computer Science (White Plains, NY, 1988), pp. 100–109.

   Google Scholar 

6. R. Valliant, A. H. Dorfman, and R. M. Royall, Finite Population Sampling and Inference: A Prediction Approach (Wiley, 2000).

7. K. V. Vorontsov, “Combinatorial Probability and the Tightness of Generalization Bounds,” Pattern Recognit. Image Anal. 18, No. 2, 243–259 (2008).

   Article  Google Scholar 

8. D. A. Kochedykov, “Combinatorial Generalization Bounds Using the Splitting of Hypothesis Spaces” in Proc. Contemporary Problems of Fundamental and Applied Sciences (Moscow, 2008).

9. K. V. Vorontsov, “Splitting and Similarity Phenomena in the Sets of Classifiers and Their Effect on the Probability of Overfitting,” Pattern Recognit. Image Anal. 19, No. 3, 412–420 (2009).

   Article  Google Scholar 

10. K. V. Vorontsov, “Tight Bounds for the Probability of Overfitting,” Dokl. Math. 80, No. 3, 793–796 (2009).

    Article  MATH  Google Scholar 

11. D. Kochedykov, “Connective Structures in Hypothesis Space and Generalization Bounds” in Proc. Conf. Mathematical Methods of Pattern Recognition (Suzdal, 2009) [in Russian].

12. K. V. Vorontsov, “Exact Combinatorial Bounds on the Probability of Overfitting for Empirical Risk Minimization,” Pattern Recognit. Image Anal. 20, No. 3, 269–285 (2010).

    Article  Google Scholar 

13. J. Langford and D. McAllester, “Computable Shell Decomposition Bounds,” J. Mach. Learn. Res. 5, 529–547 (2004).

    MathSciNet  Google Scholar 

14. J. Langford, “Quantitatively Tight Sample Complexity Bounds,” PhD. Thesis (Carnegie Mellon Univ., 2002).

15. V. N. Vapnik, Statistical Learning Theory (Wiley, 1998).

16. N. L. Johnson, S. Kotz, and A. W. Kemp, Univariate Discrete Distributions (Wiley Intersci., 1992).

17. D. A. Kochedykov, “A Combinatorial Approach to Hypotheses Similarity in Generalization Bounds,” (2010)—submitted.

18. D. Hush and C. Scovel, “Concentration of Hypergeometric Distribution,” Stat. Probab. Lett. 75, No. 2, 127–132 (2005).

    Article  MATH  MathSciNet  Google Scholar 

19. D. Haussler, M. Kearns, H. S. Seung and N. Tishby, “Rigorous Learning Curve Bounds from Statistical Mechanics,” Mach. Learn., No. 25, 195–236 (1996).

20. T. SHeffer and T. Joachims, “Expected Model Analisys for Model Selection,” in Proc. Int. Conf. on Model Selection (1999).

21. M. Anthony and P. Bartlett, Learning in Neural Networks: Theoretical Foundations (Cambridge Univ. Press, 1999).

22. C. B. Barber, D. Dobkin, and H. Huhdanpaa, “The Quickhull Algorithm for Convex Hulls,” ACM Trans. Math. Software 22, No. 4, 469–483 (1996).

    Article  MATH  MathSciNet  Google Scholar 

Download references