DocumentCode :
2710541
Title :
Direct Zero-Norm Optimization for Feature Selection
Author :
Huang, Kaizhu ; King, Irwin ; Lyu, Michael R.
Author_Institution :
Dept. of Eng. Math., Univ. of Bristol, Bristol
fYear :
2008
fDate :
15-19 Dec. 2008
Firstpage :
845
Lastpage :
850
Abstract :
Zero-norm, defined as the number of non-zero elements in a vector, is an ideal quantity for feature selection. However, minimization of zero-norm is generally regarded as a combinatorially difficult optimization problem. In contrast to previous methods that usually optimize a surrogate of zero-norm, we propose a direct optimization method to achieve zero-norm for feature selection in this paper. Based on Expectation Maximization (EM), this method boils down to solving a sequence of Quadratic Programming problems and hence can be practically optimized in polynomial time. We show that the proposed optimization technique has a nice Bayesian interpretation and converges to the true zero norm asymptotically, provided that a good starting point is given. Following the scheme of our proposed zero-norm, we even show that an arbitrary-norm based Support Vector Machine can be achieved in polynomial time. A series of experiments demonstrate that our proposed EM based zero-norm outperforms other state-of-the-art methods for feature selection on biological microarray data and UCI data, in terms of both the accuracy and the learning efficiency.
Keywords :
expectation-maximisation algorithm; optimisation; support vector machines; UCI data; biological microarray data; direct zero-norm optimization; expectation maximization; feature selection; polynomial time; quadratic programming problems; support vector machine; Bayesian methods; Computer science; Data engineering; Data mining; Machine learning; Mathematics; Optimization methods; Polynomials; Quadratic programming; Support vector machines;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Data Mining, 2008. ICDM '08. Eighth IEEE International Conference on
Conference_Location :
Pisa
ISSN :
1550-4786
Print_ISBN :
978-0-7695-3502-9
Type :
conf
DOI :
10.1109/ICDM.2008.60
Filename :
4781189
Link To Document :
بازگشت