Institute of Information Theories and Applications FOI ITHEA
The goal of the paper is to estimate misclassification probability for decision function by training
sample. Here are presented results of investigation an empirical risk bias for nearest neighbours, linear and
decision tree classifier in comparison with exact bias estimations for a discrete (multinomial) case. This allows to
find out how far Vapnik–Chervonenkis risk estimations are off for considered decision function classes and to
choose optimal complexity parameters for constructed decision functions. Comparison of linear classifier and
decision trees capacities is also performed.
* The work is supported by RFBR, grant 04-01-00858-a