Source-linked AI summary
Generalized Fisher Score for Feature Selection
Quanquan Gu, Zhenhui Li, Jiawei Han
TL;DR
Independent Fisher-score ranking can yield suboptimal feature subsets by overlooking feature combinations and redundancy. The paper proposes a generalized Fisher score that jointly selects features through an optimization framework, and benchmark experiments report better performance than Fisher score and other state-of-the-art methods.
Problem
Independent Fisher-score selection can miss informative feature combinations and retain redundant features, producing suboptimal subsets.
Method
The generalized Fisher score jointly selects features by maximizing a lower bound of traditional Fisher score, reformulating the problem as QCLP solved with cutting planes and alternating regression-based optimization.
Results
The proposed method outperforms Fisher score and other feature-selection methods on benchmark data sets; with 10 features, it achieves about 80% accuracy versus roughly 50% for original Fisher score.
Takeaways & Limitations
Generalized Fisher score provides a feature-selection approach that accounts for feature combinations and redundancy within supervised filter-based selection.
Takeaways & Limitations
The theorem-equivalence result requires centered data, and its optimal projection matrix can differ from that of the original optimization problem.
Abstract
from arXiv · showhide
Fisher score is one of the most widely used supervised feature selection methods. However, it selects each feature independently according to their scores under the Fisher criterion, which leads to a suboptimal subset of features. In this paper, we present a generalized Fisher score to jointly select features. It aims at finding an subset of features, which maximize the lower bound of traditional Fisher score. The resulting feature selection problem is a mixed integer programming, which can be reformulated as a quadratically constrained linear programming (QCLP). It is solved by cutting plane algorithm, in each iteration of which a multiple kernel learning problem is solved alternatively by multivariate ridge regression and projected gradient descent. Experiments on benchmark data sets indicate that the proposed method outperforms Fisher score as well as many other state-of-the-art feature selection methods.
1 Introduction
Feature selection reduces high-dimensionality problems, but independent feature ranking can miss useful combinations and retain redundant features. The paper introduces a generalized Fisher score that selects feature subsets jointly while addressing these shortcomings.
- Filter methods rank features before learning, whereas wrapper and embedded methods depend more directly on the eventual learning algorithm.
- Fisher score is a widely used supervised criterion that seeks feature subsets separating different classes while keeping same-class points close.
- Feature selection reduces computational cost and removes irrelevant or redundant features in high-dimensional data.
- Independent scoring is suboptimal because it can miss low-scoring features that form strong combinations and retain highly correlated redundant features.
- The proposed generalized Fisher score jointly selects features to maximize a lower bound of traditional Fisher score while considering combinations and eliminating redundancy.
2 A Brief Review of Fisher Score
The standard Fisher-score heuristic ranks features independently, which can produce suboptimal selections because it ignores feature combinations and redundancy. These limitations motivate a generalized criterion.
- The Fisher score heuristic computes each feature's score independently and selects the top-m features.
- Independent ranking can discard features with low individual scores but high combined scores.
- The heuristic cannot handle redundant features, so correlated features may be selected together unnecessarily.
- These shortcomings motivate the generalized Fisher score proposed in the paper.
3 The Proposed Method
The proposed method generalizes Fisher score by jointly selecting features through a lower-bound optimization, then solves the resulting problem with QCLP, cutting planes, and alternating optimization.
- 3.2 Generalized Fisher Score: For fixed p, the generalized Fisher-score criterion is equivalent to a regularized discriminant-analysis problem, while optimizing p is difficult.The equivalence motivates a regression-based solution, although the optimal W can differ between the two formulations and requires centered X.
- 3.1 Equivalent Formulation of Fisher Score: The method uses a binary indicator vector p with p_i ∈ {0, 1} and p^T1 = m to represent selecting exactly m features.The selected features are encoded through diag(p) in the equivalent Fisher-score formulation.
- 3 The Proposed Method: The generalized Fisher score jointly selects features by maximizing a lower bound of the traditional Fisher-score objective.The lower-bound formulation addresses the combinatorial difficulty of directly maximizing the equivalent Fisher-score problem.
- 3.3 The Dual Problem: The optimization is reformulated as a QCLP and relaxed into a multiple kernel learning problem with d feature-associated base kernels.An additional variable θ is introduced to make the reformulation practical when the number of features is very large.
- 3.4 Optimization: The multiple kernel learning problem alternates multivariate ridge regression for V with projected gradient descent for kernel weights λ.The ridge-regression subproblem can be solved efficiently with iterative conjugate-gradient methods such as LSQR.
- 3.5 Cutting Plane Acceleration: Cutting planes maintain a polynomial-sized working constraint set by adding the most violated constraint until convergence.The most violated feature-selection vector is found from the m largest coefficients in O(m log d) time, while ridge regression scales linearly with n.
4 Experiments
Experiments compare generalized Fisher score with established feature-selection criteria across UCI, ORL, and USPS recognition tasks. GFS consistently performs best, especially when jointly selecting discriminative and nonredundant features.
- 4.1 UCI Data Sets: Fisher score remains competitive, matching or exceeding other feature-selection methods on 3 out of 4 UCI data sets.This supports Fisher criterion’s strong performance relative to the alternative criteria evaluated.
- 4.2 Face Recognition: On ORL, generalized Fisher score outperforms the other feature-selection methods as the number of selected features varies.Recognition accuracy is plotted against the number of selected features, with GFS controlled indirectly through m.
- 4.2 Face Recognition: GFS improves face recognition by selecting feature combinations and discarding redundant features, producing more distributed and discriminative facial pixel selections.Its selected pixels concentrate around facial regions such as the eyebrows, eye corners, nose, and mouth, whereas Fisher score selections are skewed toward nonface regions.