Towards Large-scale and Ultrahigh Dimensional Feature Selection via Feature Generation

In many real-world applications such as text mining, it is desirable to select the most relevant features or variables to improve the generalization ability, or to provide a better interpretation of the prediction models. {In this paper, a novel adaptive feature scaling (AFS) scheme is proposed by introducing a feature scaling {vector $\d \in [0, 1]^m$} to alleviate the bias problem brought by the scaling bias of the diverse features.} By reformulating the resultant AFS model to semi-infinite programming problem, a novel feature generating method is presented to identify the most relevant features for classification problems. In contrast to the traditional feature selection methods, the new formulation has the advantage of solving extremely high-dimensional and large-scale problems. With an exact solution to the worst-case analysis in the identification of relevant features, the proposed feature generating scheme converges globally. More importantly, the proposed scheme facilitates the group selection with or without special structures. Comprehensive experiments on a wide range of synthetic and real-world datasets demonstrate that the proposed method {achieves} better or competitive performance compared with the existing methods on (group) feature selection in terms of generalization performance and training efficiency. The C++ and MATLAB implementations of our algorithm can be available at \emph{http://c2inet.sce.ntu.edu.sg/Mingkui/robust-FGM.rar}.