Publications 2007

Consistent feature selection for pattern recognition in polynomial time
R. Nilsson, J.M., Peña, J. Björkegren and J. Tegnér
Journal of Machine Learning Research, 8(March):589-612, 2007
R. Nilsson, J.M., Peña, J. Björkegren and J. Tegnér
Bioinformatics; Classification; Learning theory; Markov blanket; Relevance
2007
​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.


ISSN: 15324435

Consistent feature selection for pattern recognition in polynomial time.pdfConsistent feature selection for pattern recognition in polynomial time.pdf