Consistent feature selection for pattern recognition in polynomial time

Roland Nilsson*, José M. Peña, Johan Björkegren, Jesper Tegnér

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

130 Scopus citations


We analyze two different feature selection problems: finding a minimal feature set optimal for classification (MINIMAL-OPTIMAL) vs. finding all features relevant to the target variable (ALL-RELEVANT). The latter problem is motivated by recent applications within bioinformatics, particularly gene expression analysis. For both problems, we identify classes of data distributions for which there exist consistent, polynomial-time algorithms. We also prove that ALL-RELEVANT is much harder than MINIMAL-OPTIMAL and propose two consistent, polynomial-time algorithms. We argue that the distribution classes considered are reasonable in many practical cases, so that our results simplify feature selection in a wide range of machine learning tasks.

Original languageEnglish (US)
Pages (from-to)589-612
Number of pages24
JournalJournal of Machine Learning Research
StatePublished - Mar 2007
Externally publishedYes


  • Bioinformatics
  • Classification
  • Learning theory
  • Markov blanket
  • Relevance

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence


Dive into the research topics of 'Consistent feature selection for pattern recognition in polynomial time'. Together they form a unique fingerprint.

Cite this