Bounds for Validation

Article type: Research Article

Authors: Jaworski, Wojciech

Affiliations: Faculty of Mathematics, Computer Science and Mechanics Warsaw University, Banacha 2, 02-097 Warsaw, Poland. E-mail: [email protected]

Abstract: In this paper we derive the bounds for Validation (known also as Hold-Out Estimate and Train-and-Test Method). We present the best possible bound in the case of 0–1 valued loss function. We also provide the tables where the least sample size is calculated that is necessary for obtaining the bound for a given estimation rate and reliability of estimation. For an arbitrary bounded loss function we present the optimal bound approximation with any given accuracy.

Keywords: computational learning theory, model assessment, hold-out estimate, train-and-test, validation, Bernoulli sums

Journal: Fundamenta Informaticae, vol. 70, no. 3, pp. 261-275, 2006