Geometrical Complexity of Classification Problems

Friday, October 7, 2005 - 1:25pm - 3:00pm
Vincent 570
Tin Kam Ho (Alcatel-Lucent Technologies Bell Laboratories)
Pattern recognition seeks to identify and model regularities in empirical data by algorithmic processes. Successful application of the established methods requires good understanding of their behavior and also how well they match the application context. Difficulties can arise from either the intrinsic complexity of a problem or a mismatch of methods to problems. We describe some measures that can characterize the intrinsic complexity of a classification problem and its relationship to classifier performance. The measures revealed that a collection of real-world problems can span an interesting continuum between those easily learnable to those with no learning possible. We discuss our results on identifying the domains of dominant competence of several popular classifiers in this measurement space.