2014 SimultaneousFeatureandFeatureGr

• (Xiang et al., 2014) ⇒ Shuo Xiang, Tao Yang, and Jieping Ye. (2014). “Simultaneous Feature and Feature Group Selection through Hard Thresholding.” In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2014) Journal. ISBN:978-1-4503-2956-9 doi:10.1145/2623330.2623662

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222014%22+Simultaneous+Feature+and+Feature+Group+Selection+through+Hard+Thresholding
• http://dl.acm.org/citation.cfm?id=2623330.2623662&preflayout=flat#citedby

Quotes

Author Keywords

• Bi-level learning; com- binatorics; data mining; dynamic programming; feature selection; optimization; supervised learning

Abstract

Selecting an informative subset of features has important applications in many data mining tasks especially for high-dimensional data. Recently, simultaneous selection of features and feature groups (a.k.a bi-level selection) becomes increasingly popular since it not only reduces the number of features but also unveils the underlying grouping effect in the data, which is a valuable functionality in many applications such as bioinformatics and web data mining. One major challenge of bi-level selection (or even feature selection only) is that computing a globally optimal solution requires a prohibitive computational cost. To overcome such a challenge, current research mainly falls into two categories. The first one focuses on finding suitable continuous computational surrogates for the discrete functions and this leads to various convex and nonconvex optimization models. Although efficient, convex models usually deliver sub-optimal performance while nonconvex models on the other hand require significantly more computational effort. Another direction is to use greedy algorithms to solve the discrete optimization directly. However, existing algorithms are proposed to handle single-level selection only and it remains challenging to extend these methods to handle bi-level selection. In this paper, we fulfill this gap by introducing an efficient sparse group hard thresholding algorithm. Our main contributions are: (1) we propose a novel bi-level selection model and show that the key combinatorial problem admits a globally optimal solution using dynamic programming; (2) we provide an error bound between our solution and the globally optimal under the RIP (Restricted Isometry Property) theoretical framework. Our experiments on synthetic and real data demonstrate that the proposed algorithm produces encouraging performance while keeping comparable computational efficiency to convex relaxation models.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2014 SimultaneousFeatureandFeatureGr	Jieping Ye Shuo Xiang Tao Yang			Simultaneous Feature and Feature Group Selection through Hard Thresholding				10.1145/2623330.2623662		2014