Trace Ratio Optimization With Feature Correlation Mining for Multiclass Discriminant Analysis

Forough Rezaei Boroujeni, Sen Wang, Zhihui Li, Nicholas West, Bela Stantic, Lina Yao, Guodong Long

Introduction

Dimensionality reduction is a critical preprocessing step for high-dimensional data, such as genomic sequences and high-resolution images. While Fisher’s Linear Discriminant Analysis (FLDA) is a standard tool for this task, it often struggles in multiclass scenarios due to the "class separation problem." FLDA tends to over-optimize for class pairs that are already easily separable, leading to significant overlap among more challenging, closely situated classes. This paper, presented at AAAI 2018, introduces the TRLN framework to address these limitations by rethinking class separation metrics and incorporating robust regularization.

The TRLN Framework

The proposed TRLN (Trace Ratio with $\ell_{2,1}$-norm) method introduces two key innovations to solve the class separation problem:

1. Weighted Harmonic Mean Optimization

Standard multiclass LDA methods typically maximize the arithmetic or geometric mean of pairwise separation ratios. However, these averages can be dominated by a few large values, leaving some classes poorly separated. TRLN instead maximizes the weighted harmonic mean. By minimizing the sum of the reciprocals of pairwise trace ratios, the optimization process is forced to prioritize the "weakest links"—the class pairs that are hardest to separate. This ensures a "no class left behind" approach to subspace projection.

2. $\ell_{2,1}$-norm Regularization

To handle noise and perform effective feature selection, TRLN incorporates an $\ell_{2,1}$-norm penalty. This encourages row-sparsity in the transformation matrix, effectively identifying the most discriminative features. Crucially, this regularization allows the model to "mine" feature correlations, which is particularly beneficial in biological datasets where biomarkers often exhibit high redundancy.

Experimental Results

The TRLN method was rigorously tested against state-of-the-art baselines, including FLDA, aPAC, HMSS, and GMSS, across 12 diverse datasets spanning biological and image processing domains.

Classification Performance

TRLN consistently outperformed competing methods, especially as the number of classes increased. For instance, on the TOX_171 dataset, TRLN achieved an accuracy of 96.96%, a substantial improvement over FLDA's 81.17%. Similar gains were observed in biological datasets like CLL_SUB_111, where TRLN led the next best method by approximately 11%.

Comparison of classification accuracy across different target dimensions (m) for TRLN and baseline methods on eight datasets.

As shown in the figure above, TRLN (red line) maintains superior or competitive accuracy across a wide range of target dimensions ($m$). Its performance is particularly robust in datasets with many classes, such as Yale and ORL.

Convergence and Efficiency

Despite the non-convex nature of the objective function, the authors developed an efficient iterative solver. Empirical results demonstrate that the algorithm converges rapidly, typically reaching stability within 4 to 10 iterations.

Convergence behavior of the TRLN iterative algorithm across various biological and image datasets.

The convergence plots illustrate the objective value decreasing sharply and stabilizing quickly across multiple datasets, confirming the practical feasibility of the TRLN framework for real-world applications.

Discussion and Limitations

While TRLN shows significant promise, it is not without limitations. Its performance can degrade when the target dimension ($m$) is extremely low (e.g., $m=1$), where simpler methods sometimes prove more robust. Additionally, the regularization parameter $\alpha$ requires careful tuning, as the optimal value varies by dataset and target dimension.

Conclusion

By combining harmonic mean optimization with correlation-aware regularization, TRLN provides a robust solution to the multiclass separation problem in dimensionality reduction. Its ability to handle high-dimensional, noisy data while ensuring all class pairs are adequately separated makes it a powerful tool for complex classification tasks in bioinformatics and computer vision.

Summary updated

Abstract

Fisher's linear discriminant analysis is a widely accepted dimensionality reduction method, which aims to find a transformation matrix to convert feature space to a smaller space by maximising the between-class scatter matrix while minimising the within-class scatter matrix. Although the fast and easy process of finding the transformation matrix has made this method attractive, overemphasizing the large class distances makes the criterion of this method suboptimal. In this case, the close class pairs tend to overlap in the subspace. Despite different weighting methods having been developed to overcome this problem, there is still a room to improve this issue. In this work, we study a weighted trace ratio by maximising the harmonic mean of the multiple objective reciprocals. To further improve the performance, we enforce the l 2,1 -norm to the developed objective function. Additionally, we propose an iterative algorithm to optimise this objective function. The proposed method avoids the domination problem of the largest objective, and guarantees that no objectives will be too small. This method can be more beneficial if the number of classes is large. The extensive experiments on different datasets show the effectiveness of our proposed method when compared with four state-of-the-art methods.
BibTeX
@inproceedings{boroujeni2018trace,
  author = {Forough Rezaei Boroujeni and Sen Wang and Zhihui Li and Nicholas West and Bela Stantic and Lina Yao and Guodong Long},
  title = {{Trace Ratio Optimization With Feature Correlation Mining for Multiclass Discriminant Analysis}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11805},
}
Figure