Optimal feature selection for nonlinear data using branch-and-bound in kernel space

Journal article

Publication Details

Author(s): Ring M, Eskofier B
Journal: Pattern Recognition Letters
Publisher: Elsevier
Publication year: 2015
Volume: 68
Pages range: 56-62
ISSN: 0167-8655


Branch-and-bound (B&B) feature selection finds optimal feature subsets without performing an exhaustive search. However, the classification accuracy achievable with optimal B&B feature subsets is often inferior compared to the accuracy achievable with other algorithms that guarantee optimality. We argue this is due to the existing criterion functions that define the optimal feature subset but may not conceive inherent nonlinear data structures. Therefore, we propose B&B feature selection in Reproducing Kernel Hilbert Space (B&B-RKHS). This algorithm employs two existing criterion functions (Bhattacharyya distance, Kullback-Leibler divergence) and one new criterion function (mean class distance), however, all computed in RKHS. This enables B&B-RKHS to conceive inherent nonlinear data structures. The algorithm was experimentally compared to the popular wrapper approach that has to use an exhaustive search to guarantee optimality. The classification accuracy achieved with both methods was comparable. However, runtime of B&B-RKHS was superior using the two existing criterion functions and even completely out of reach using the new criterion function (about 60 times faster on average). Therefore, this paper proposes an efficient algorithm if feature subsets that guarantee optimality have to be selected in data sets with inherent nonlinear structures.

FAU Authors / FAU Editors

Eskofier, Björn Prof. Dr.
Stiftungs-Juniorprofessur für Sportinformatik (Digital Sports)
Ring, Matthias
Lehrstuhl für Informatik 14 (Maschinelles Lernen und Datenanalytik)

How to cite

Ring, M., & Eskofier, B. (2015). Optimal feature selection for nonlinear data using branch-and-bound in kernel space. Pattern Recognition Letters, 68, 56-62. https://dx.doi.org/10.1016/j.patrec.2015.08.007

Ring, Matthias, and Björn Eskofier. "Optimal feature selection for nonlinear data using branch-and-bound in kernel space." Pattern Recognition Letters 68 (2015): 56-62.


Last updated on 2018-19-04 at 03:04