In search of targeted-complexity problems

Currently available real-world problems do not cover the whole complexity space and, therefore, do not allow us to thoroughly test learner behavior on the border of its domain of competence. Thus, the necessity of developing a more suitable testing scenario arises. With this in mind, data complexity analysis has shown promise in characterizing difficulty of classification problems through a set of complexity descriptors which used in artificial data sets generation could supply the required framework to refine and design learners. This paper, then, proposes the use of instance selection based on an evolutionary multiobjective technique to generate data sets that meet specific characteristics established by such complexity descriptors. These artificial targeted-complexity problems, which capture the essence of real-world structures, may help to define a set of benchmarks that contributes to test the properties of learners and to improve them.