language: en

Measuring the Difficulty of Specific Learning Problems

Chris Thornton
Cognitive and Computing Sciences University of Sussex
Brighton BN1 9QN UK
Email: Chris.Thornton@cogs.susx.ac.uk

[Tel: (44)1273 678856]

May 21, 2003

Abstract 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.

1 Introduction