Measuring the Difficulty of Specific Learning Problems
Chris Thornton · Connection Science · 1995
Existing complexity measures from contemporary learning theory cannot be conveniently applied to specific learning problems (e.g. training sets). Moreover, they are typically non-generic, i.e. they necessitate making assumptions about the way in which the learner will operate. The lack of a satisfactory, generic complexity measure for learning problems poses difficulties for researchers in various areas; the present paper puts forward an idea which may help to alleviate these. It shows that supervised learning problems fall into two generic complexity classes, only one of which is associated with computational tractability. By determining which class a particular problem belongs to, we can thus effectively evaluate its degree of generic difficulty.