Cross-validation for binary classification by real-valued functions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Cross-validation for binary classification by real-valued functions: theoretical analysis

Full text

Pdf (1.49 MB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the eleventh annual conference on Computational learning theory table of contents

Madison, Wisconsin, United States

Pages: 218 - 229

Year of Publication: 1998

ISBN:1-58113-057-0

Authors

Martin Anthony	Department of Mathematics, London School of Economics, Houghton Street, London WC2A 2AE, U.K.
Sean B. Holden	Department of Computer Science, University College London, Gower Street, London WC1E 6BT, U.K.

Sponsors

University of Wisconsin : University of Wisconsin
UC @ Santa Cruz : UC @ Santa Cruz
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 16, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/279943.279987 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	N. Alon, S. Ben-David, N. Cesa-Bianchi, and D. Haussler. Scale-sensitive dimensions, uniform convergence, and learnability. In Proceedings of the Symposium on Foundations of Computer Science. IEEE Press, 1993.
	2	Martin Anthony, Probabilistic ’generalization‘ of functions and dimension-based uniform convergence results, Statistics and Computing, v.8 n.1, p.5-14, 1998 [doi>10.1023/A:1008801224333]
	3	Martin Anthony , Norman Biggs, Computational learning theory: an introduction, Cambridge University Press, New York, NY, 1992
	4	Martin M. Anthony , Peter Bartlett, Learning in Neural Networks: Theoretical Foundations, Cambridge University Press, New York, NY, 1999
	5	Martin Anthony , Peter L. Bartlett, Function learning from interpolation, Proceedings of the Second European Conference on Computational Learning Theory, p.211-221, March 13-15, 1995
	6	Martin Anthony , John Shawe-Taylor, A result of Vapnik with applications, Discrete Applied Mathematics, v.47 n.3, p.207-217, Dec. 21, 1993 [doi>10.1016/0166-218X(93)90126-9]
	7	P. Bartlett. The sample complexity of pattern classification with neural networks: the size of the weights is more important that the size of the network. Report, Department of Systems Engineering, Australian National University, May 1997.
	8	P. Bartlett. For valid generalisation, the size of the weights is more important than the size of the network. In Advances in Neural Information Processing Systems, 9. Morgan Kaufmann, 1996.
	9	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]
	10	B. Cheng and D. M. Titterington. Neural networks: a review from a statistical perspective. Statistical Science, 9(1):2-54, 1994.
	11	David Cohn , Gerald Tesauro, How tight are the Vapnik-Chervonenkis bounds?, Neural Computation, v.4 n.2, p.249-269, March 1992 [doi>10.1162/neco.1992.4.2.249]
	12	R. O. Duda and P. E. Hart. Pattern Classification and Scene Analysis. John Wiley, 1973.
	13	David Haussler, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Information and Computation, v.100 n.1, p.78-150, Sept. 1992 [doi>10.1016/0890-5401(92)90010-D]
	14	Sean B. Holden, PAC-like upper bounds for the sample complexity of leave-one-out cross-validation, Proceedings of the ninth annual conference on Computational learning theory, p.41-50, June 28-July 01, 1996, Desenzano del Garda, Italy [doi>10.1145/238061.238067]
	15	S. B. Holden. Cross-validation and the PAC learning model. Research Note RN/96/64, Department of Computer Science, University College London, December 1996.
	16	S. B. Holden. On Algorithmic Stability and the Analysis of the Cross-Validation and Holdout Estimates. Research Note RN/97/73, Department of Computer Science, University College London.
	17	Sean B. Holden , Mahesan Niranjan, On the practical applicability of VC dimension bounds, Neural Computation, v.7 n.6, p.1265-1288, Nov. 1995 [doi>10.1162/neco.1995.7.6.1265]
	18	Michael J. Kearns , Robert E. Schapire , Linda M. Sellie, Toward efficient agnostic learning, Proceedings of the fifth annual workshop on Computational learning theory, p.341-352, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130424]
	19	Michael Kearns , Dana Ron, Algorithmic stability and sanity-check bounds for leave-one-out cross-validation, Proceedings of the tenth annual conference on Computational learning theory, p.152-162, July 06-09, 1997, Nashville, Tennessee, United States [doi>10.1145/267460.267491]
	20	M. J. Kearns and R. E. Schapire. Efficient distributionfree learning of probabilistic concepts. In Proc. of the 31st Symposium on the Foundations of Comp. Sci., pages 382-391. IEEE Computer Society Press, Los Alamitos, CA, 1990.
	21	D. Pollard. Convergence of Stochastic Processes. Springer-Vefiag, 1984.
	22	N. Sauer. On the density of families of sets. Journal of Combinatorial Theory (A), 13:145-147, 1972.
	23	J. Shawe-Taylor, P. Bartlett. R.C. Williamson, M. Anthony. Structural risk minimisation over datadependent hierarchies. To appear, IEEE Transactions on Information Theory.
	24	G.T. Toussaint. Bibliography on estimation of misctassification. IEEE Transactions on Information Theory, 20(4):472-479, 1974.
	25	L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
	26	Vladimir Vapnik, Estimation of Dependences Based on Empirical Data: Springer Series in Statistics (Springer Series in Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 1982
	27	V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probab. and its Applications, 16(2):264-280, 1971.

CITED BY 2

	Avrim Blum , Adam Kalai , John Langford, Beating the hold-out: bounds for K-fold and progressive cross-validation, Proceedings of the twelfth annual conference on Computational learning theory, p.203-208, July 07-09, 1999, Santa Cruz, California, United States
	Yoshua Bengio , Yves Grandvalet, No Unbiased Estimator of the Variance of K-Fold Cross-Validation, The Journal of Machine Learning Research, 5, p.1089-1105, 12/1/2004