Relationship between the accuracy of classifier error estimation and complexity of decision boundary

Error estimation is a crucial part of classification methodology and it becomes problematic with small samples. We demonstrate here that the complexity of the decision boundary plays a key role on the performance of error estimation methods. First, a model is developed which quantifies the complexity of a classification problem purely in terms of the geometry of the decision boundary, without relying on the Bayes error. Then, this model is used in a simulation study to analyze the bias and root-mean-square (RMS) error of a few widely used error estimation methods relative to the complexity of the decision boundary: resubstitution, leave-one-out, 10-fold cross-validation with repetition, 0.632 bootstrap, and bolstered resubstitution, in two- and three-dimensional spaces. Each estimator is implemented with three classification rules: quadratic discriminant analysis (QDA), 3-nearest-neighbor (3NN) and two-layer neural network (NNet). The results show that all the estimation methods lose accuracy as complexity increases.

► The complexity of the decision boundary in classification affects error estimation.
► A model is developed which quantifies the complexity of the decision boundary.
► Performance of error estimation relative to complexity is studied via the model.
► Results show that all estimation methods lose accuracy as complexity increases.