Exact and empirical estimation of misclassification probability

MachineLearning manuscript No. (will be inserted by the editor) Abstract We discuss the problem of risk estimation in the classification problem, with specific focus on finding distributions that maximize the confidence intervals of risk estimation. We derived simple analytic approximations for the maximum bias of empirical risk for histogram classifier. We carry out a detailed study on using these analytic estimates for empirical estimation of risk. Keywords data mining · machine learning · misclassification probability · overfitting · confidence interval · statistical estimate 1 Introduction The study of overfitting is one of the most important research directions in the area of machine learning. This problem arises from common disadvantage of more complex decision rules relative to the simpler ones when the sample size is not very large.