Material Detail

Capacity Control for Partially Ordered Feature Sets

Capacity Control for Partially Ordered Feature Sets

This video was recorded at European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD), Bled 2009. Partially ordered feature sets appear naturally in classification settings with structured instances. For example, when the instances are graphs and the features represent subgraph-occurrence-checks, the features can be partially ordered according to an "is subgraph of" relation. We investigate how the redundancy in such datasets affects the capacity control behavior of linear classification methods. While the capacity does not decrease in general, we derive better capacity bounds for distributions, which assign lower probabilities to instances in the lower levels of the feature hierarchy. For itemset, subsequence and subtrees, the capacity is finite even for data with an infinite number of features. We validate these results empirically and show that the limited capacity of linear classifiers makes underfitting rather than overfitting the more prominent capacity control problem. To avoid underfitting, we propose substructure classes with "elastic edges", and we demonstrate how such broad feature classes can be used with large datasets.


  • User Rating
  • Comments
  • Learning Exercises
  • Bookmark Collections
  • Course ePortfolios
  • Accessibility Info

More about this material


Log in to participate in the discussions or sign up if you are not already a MERLOT member.