Trace Ratio Criterion for Feature Selection

Feiping Nie, Shiming Xiang, Yangqing Jia, Changshui Zhang, Shuicheng Yan

Introduction

In machine learning, high-dimensional datasets often contain irrelevant or redundant features that impede computational efficiency and model accuracy. Feature selection aims to identify the most informative subset of $m$ features. Traditional "filter" methods, such as the Fisher score and Laplacian score, typically rank features individually based on a "ratio of traces" heuristic. However, this approach is mathematically suboptimal for evaluating the collective quality of a feature subset. This paper introduces a "Trace Ratio" criterion that directly optimizes the subset-level score and presents an efficient iterative algorithm guaranteed to find the global optimum.

The Trace Ratio Criterion

The authors propose a general graph-based framework to maximize the Trace Ratio: $$J(W_I) = \frac{tr(W_I^T B W_I)}{tr(W_I^T E W_I)}$$ where $B$ and $E$ represent between-class and within-class scatter matrices, respectively. Unlike the traditional heuristic which sums individual ratios, the Trace Ratio evaluates the ratio of sums, capturing the synergistic effects of the feature subset as a whole.

The Iterative Algorithm

To solve the NP-hard problem of subset selection without exhaustive search, the authors developed an iterative root-finding algorithm. Starting with an initial subset, the algorithm updates the selection by ranking features based on a linear surrogate score $(B - \lambda E)$, where $\lambda$ is the current Trace Ratio.

Convergence of the iterative algorithm to the optimal trace ratio

As illustrated in the figure above, the algorithm converges monotonically to the global optimum $\lambda^*$ in typically 3 to 5 iterations. This efficiency makes it highly practical for real-world applications, as the actual optimization adds negligible overhead compared to the initial construction of the affinity matrices.

Experimental Evaluation and Results

The proposed Subset Fisher Score (S-FS) and Subset Laplacian Score (S-LS) were evaluated against traditional counterparts on UCI datasets and high-dimensional face databases like AT&T and UMIST.

Accuracy comparison on the AT&T dataset

Experimental results demonstrate that subset-level optimization consistently yields higher classification accuracy. On the AT&T dataset, S-FS and S-LS outperform their individual ranking counterparts (F-FS and F-LS) across various feature counts. This confirms that the Trace Ratio effectively captures the collective discriminative power of features, bridging the gap between heuristic ranking and global optimality.

Conclusion

The Trace Ratio criterion provides a theoretically sound and practically efficient alternative to traditional feature selection heuristics. By optimizing the subset-level score directly, the proposed algorithm achieves superior performance with minimal computational cost. Future research directions include extending this framework to kernel-based versions to better address non-linear data relationships.

Summary updated

Abstract

Fisher score and Laplacian score are two popular feature selection algorithms, both of which belong to the general graph-based feature selection framework. In this framework, a feature subset is selected based on the corresponding score (subset-level score), which is calculated in a trace ratio form. Since the number of all possible feature subsets is very huge, it is often prohibitively expensive in computational cost to search in a brute force manner for the feature subset with the maximum subset-level score. Instead of calculating the scores of all the feature subsets, traditional methods calculate the score for each feature, and then select the leading features based on the rank of these feature-level scores. However, selecting the feature subset based on the feature-level score cannot guarantee the optimum of the subset-level score. In this paper, we directly optimize the subset-level score, and propose a novel algorithm to efficiently find the global optimal feature subset such that the subset-level score is maximized. Extensive experiments demonstrate the effectiveness of our proposed algorithm in comparison with the traditional methods for feature selection.
BibTeX
@inproceedings{nie2008trace,
  author = {Feiping Nie and Shiming Xiang and Yangqing Jia and Changshui Zhang and Shuicheng Yan},
  title = {{Trace Ratio Criterion for Feature Selection}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure