PaperlayerView exact revision on arXiv

Source-linked AI summary

Effective Discriminative Feature Selection with Non-trivial Solutions

Hong Tao, Chenping Hou, Feiping Nie, Yuanyuan Jiao, Dongyun Yi

arXiv:1504.05408v1cs.LG

TL;DR

High-dimensional data make irrelevant and redundant features costly and potentially harmful, motivating supervised feature selection that preserves discriminative information. The paper combines LDA with row-sparse ℓ2,p regularization, avoids LDFS's trivial solution, and develops an algorithm whose objective decreases monotonically for 0 < p ≤ 2. Experiments on varied real-world data sets report advantages for selecting discriminative features and removing redundancy.

  • Problem

    High-dimensional data contain irrelevant and redundant features that increase processing requirements and can harm efficiency, over-fitting, and prediction performance.

  • Method

    DFS combines LDA with row-sparse ℓ2,1 regularization, constrains transformation vectors to avoid the trivial zero solution, and extends the formulation to ℓ2,p regularization.

  • Results

    Experiments on various real-world data sets illustrate DFS's advantages, while its algorithm monotonically decreases the objective and converges for 0 < p ≤ 2.

  • Takeaways & Limitations

    DFS jointly selects the most discriminative features and removes redundant ones while offering different p values to fit sparsity requirements.

Abstract

from arXiv · show

Feature selection and feature transformation, the two main ways to reduce dimensionality, are often presented separately. In this paper, a feature selection method is proposed by combining the popular transformation based dimensionality reduction method Linear Discriminant Analysis (LDA) and sparsity regularization. We impose row sparsity on the transformation matrix of LDA through ${\ell}_{2,1}$-norm regularization to achieve feature selection, and the resultant formulation optimizes for selecting the most discriminative features and removing the redundant ones simultaneously. The formulation is extended to the ${\ell}_{2,p}$-norm regularized case: which is more likely to offer better sparsity when $0<p<1$. Thus the formulation is a better approximation to the feature selection problem. An efficient algorithm is developed to solve the ${\ell}_{2,p}$-norm based optimization problem and it is proved that the algorithm converges when $0<p\le 2$. Systematical experiments are conducted to understand the work of the proposed method. Promising experimental results on various types of real-world data sets demonstrate the effectiveness of our algorithm.

I. INTRODUCTION

The paper addresses high-dimensional supervised feature selection by combining LDA with row-sparse regularization, aiming to select discriminative features while removing redundancy. It avoids LDFS's trivial zero solution, extends the formulation to ℓ2,p regularization, proves convergence for 0 < p ≤ 2, and evaluates DFS on real-world data sets.

  • Motivation: High-dimensional data contain irrelevant and redundant features that increase processing costs and can harm efficiency, over-fitting, and prediction performance.Dimensionality reduction is therefore an important preprocessing stage.
  • Motivation: Feature selection preserves original variable semantics and can require collecting or computing only the selected features, unlike feature transformation.
  • Prior work and gap: Existing LDFS uses LDA's discriminative information and learning mechanism to select features jointly, but its formulation has a trivial all-zero solution.The zero solution can undermine feature selection, while feature ranking methods such as Fisher Score do not handle feature interaction and redundancy.
  • Proposed method: DFS constrains LDA transformation vectors to be uncorrelated and replaces ℓ∞,1 regularization with ℓ2,1 minimization to avoid the trivial solution while jointly selecting discriminative, nonredundant features.The ℓ2,1 formulation is described as easier to solve and still supports feature selection.
  • Optimization and evaluation: An efficient algorithm is developed for the ℓ2,p optimization problem, with a proof that its objective decreases monotonically for 0 < p ≤ 2.The paper also evaluates DFS systematically on various real-world data sets.

III. LINEAR DISCRIMINANT FEATURE SELECTION REVISITED

This section revisits LDA-based feature selection by linking transformation-matrix structure to selected features, then examines LDFS’s sparsity formulation and its trivial zero solution. It also explains computational and formulation issues in the prior approach underlying LDFS.

  • LDA review: LDA seeks directions that separate samples from different classes while keeping samples within the same class close.Its objective uses within-class and between-class scatter matrices, with St = Sb + Sw.
  • Feature-selection structure: A feature is removed when its corresponding row in transformation matrix A is all zero, because it then contributes nothing to XA.This row-wise interpretation preserves the semantic correspondence between data features and transformation coefficients.
  • LDFS formulation: LDFS promotes row sparsity by applying an ℓ∞-norm within each row and an ℓ1-norm across rows, so increasing γ removes more features.The regularizer pushes every element of selected rows toward zero through the row maximum magnitude.
  • Prior approach: The prior ℓ∞-norm approach uses dummy variables and box constraints, then applies a Quasi-Newton method whose gradient evaluation is computationally expensive.The cited formulation represents each row’s maximum absolute coefficient with auxiliary variables.
  • Trivial solution: The LDFS formulation in (11) has a trivial all-zero solution, established in Proposition 1.Scaling any solution by a nonzero constant with magnitude below one improves the objective, yielding the zero solution.
  • Trivial solution: At the zero solution, LDFS loses feature-selection ability; increasing γ experimentally can produce a nonzero solution, but it may not be optimal.The implementation makes rows nearly zero by requiring their maximum absolute value to be below 0.01.

IV. DISCRIMINATIVE FEATURE SELECTION BASED ON ℓ2,p-NORM REGULARIZATION

DFS addresses LDFS's trivial solution and computational burden by enforcing uncorrelated transformation vectors and replacing ℓ∞,1-norm regularization with a generalized ℓ2,p-norm formulation.

  • DFS constrains LDA transformation vectors to be uncorrelated and adopts ℓ2,1-norm regularization to avoid the trivial solution more easily.The formulation is generalized to ℓ2,p-norm regularization for different sparsity requirements.
  • The proposed unified algorithm is designed for both convex and non-convex regularized cases and is proved convergent when 0 < p ≤ 2.

A. Discriminative Feature Selection Based on ℓ2,1-Norm Regularization

The ℓ2,1-regularized DFS formulation combines discriminative feature learning with row sparsity, selecting relevant features while automatically removing redundant ones.

  • ℓ2,1-norm regularization is chosen because it supports an easier iterative solution while retaining row-level feature-selection behavior.Its relationship to ℓ∞,p-norm regularization motivates the reformulation.
  • DFS constrains the transformation matrix by A^T S_t A = I to prevent arbitrary scaling and the all-zero solution.
  • After learning A*, features are ranked by the magnitude of their corresponding transformation-matrix rows, and the highest-ranked features are selected.
  • DFS jointly accounts for feature relevance and interactions while eliminating redundant features during objective minimization.Adding correlated redundant features increases the ℓ2,1 penalty without improving the discriminative term.

B. ℓ2,p-Norm Regularized Discriminative Feature Selection

The ℓ2,p formulation relaxes the difficult ℓ2,0 feature-selection problem, trading convexity against sparsity and solving the resulting optimization through an iterative eigenproblem-based algorithm.

  • Exact LDA-based feature selection is an ℓ2,0-norm minimization problem, but it is difficult because it is NP-hard.
  • For 0 < p < 1, ℓ2,p-norm regularization is expected to produce sparser solutions than ℓ2,1-norm regularization, while p = 1 recovers the DFS formulation.
  • The parameter p trades sparsity against convexity: values closer to zero better approximate feature selection, whereas ℓ2,1 is the closest convex approximation to ℓ2,0.
  • The algorithm alternates between solving a generalized eigenproblem for A and updating the diagonal matrix D until convergence.The method covers both convex and non-convex regularization cases.
  • When the number of features exceeds the number of samples, St is regularized as St + αI to ensure a nonsingular scatter matrix.

V. DISCUSSIONS

The discussion analyzes DFS through convergence behavior, computational complexity, and parameter determination.

  • DFS is analyzed across convergence behavior, time complexity, and parameter selection.

A. Algorithm Analysis

The algorithm’s objective decreases monotonically under the update rules and converges to a local optimum when 0 < p ≤ 2. Sequential transformation matrices are also compared using a divergence metric to assess whether final results change substantially.

  • The proof relies on an inequality established for nonzero vectors when 0 < p ≤ 2.
  • When 0 < p ≤ 2, Algorithm 1 converges to a local optimum of the objective.
  • The objective function decreases monotonically at every iteration because the update rules preserve a non-increasing objective.
  • A divergence metric between successive transformation matrices indicates whether the final results change drastically.

B. Time Complexity

The main computational cost is solving a generalized eigen-problem, while empirical convergence requires only several iterations, supporting practical scalability.

  • O(d^3) approximately is the time complexity of solving the generalized eigen-problem, the most time-consuming operation.
  • Empirical results show that convergence is fast, requiring only several iterations and scaling well in practice.

C. Parameter Selection

The experiments evaluate DFS across diverse data sets using classification accuracy and redundancy rate, while parameter selection relies mainly on cross-validation and grid search.

  • Parameter selection is commonly performed by grid search using cross-validation accuracy, although experience is sometimes used.
  • DFS uses reduced dimensionality l = c − 1, while γ controls the trade-off between discrimination and sparsity.
  • The study evaluates DFS with a toy example, comparisons against five filter methods, different p values, varying γ, convergence, and computational time.
  • Six public data sets span image, gene-expression, and spoken-letter recognition tasks, with standardized zero-mean data normalized by standard deviation.
  • Accuracy measures classification performance, while redundancy rate measures redundancy among selected features; an ideal selector achieves high accuracy with few redundant features.
  • Classification uses a linear kernel with C = 1 and 5-fold cross validation, reporting the average accuracy across folds.
  • Redundancy rate is the average correlation across selected feature pairs, with larger values indicating greater expected redundancy.

B. A Toy Example

DFS is evaluated through a toy visualization and comparisons with filter-based feature selection methods, measuring classification accuracy and redundancy. It generally achieves strong accuracy while selecting features jointly to account for discriminative power and redundancy.

  • B. A Toy Example: DFS preferentially selects eyes, nose, and mouth features in ORL images; with only 64 selected features, these regions are already clear.The toy example reconstructs test images using progressively larger selected-feature sets.
  • C. Comparison between DFS and Other Filter-type Feature Selection Algorithms: DFS is compared with BAHSIC, Laplacian Score, mRMR, ReliefF, and Trace Ratio using classification accuracy and redundancy rate.The experiments evaluate selected feature subsets with an SVM classifier and report results for multiple subset sizes.
  • C. Comparison between DFS and Other Filter-type Feature Selection Algorithms: 8.07% to 19.35% improvement on COLON separates DFS from the best result of the other methods.Across data sets and subset sizes, DFS consistently outperforms the other five methods on average; its relative improvements over mRMR or Laplacian Score are 7.96%, 9.92%, 7.31%, and 6.22% for 20, 40, 60, and 80 features.
  • C. Comparison between DFS and Other Filter-type Feature Selection Algorithms: DFS-selected feature subsets consistently have low redundancy, and DFS more successfully combines high classification accuracy with low redundancy than the other methods.The paper notes that redundancy often decreases as more features are selected, despite redundancy arising from inter-correlation among selected features.
  • C. Comparison between DFS and Other Filter-type Feature Selection Algorithms: Higher discriminative power does not necessarily imply lower redundancy, and lower redundancy does not necessarily imply higher discriminative power.This conclusion follows from combining the classification-accuracy and redundancy-rate comparisons.
  • C. Comparison between DFS and Other Filter-type Feature Selection Algorithms: DFS combines discriminant analysis with ℓ2,p-norm regularization to select features jointly, considering feature interactions while promoting discriminative and nonredundant subsets.The optimization is described as selecting the most discriminative features and removing redundant ones simultaneously.

D. Comparison of DFS with Different p Values

The study varies p in DFS to examine the trade-off between sparsity and convexity. Smaller p values can produce better results in some settings, but classification accuracy does not improve monotonically as p decreases.

  • D. Comparison of DFS with Different p Values: Smaller p produces a sparser representation, while the study evaluates p ∈ {0.001, 0.01, 0.1, 1} to seek sparser solutions.Although the algorithm converges for p ∈ (0, 2], experiments restrict p to 0 < p ≤ 1.
  • D. Comparison of DFS with Different p Values: On ORL, DFS results for p = 0.001, 0.01, 0.1, and 1 are very close, with DFS(p = 1) slightly behind above 65 selected features.On USPS, fractional p values outperform p = 1 in specified feature-count ranges.
  • D. Comparison of DFS with Different p Values: On ISOLET5, DFS with p < 1 consistently surpasses DFS(p = 1).This provides the clearest reported advantage for positive fractional p values.
  • D. Comparison of DFS with Different p Values: Classification accuracy does not monotonically increase as p decreases, despite smaller p producing sparser representations.The paper attributes this pattern possibly to local-optimum guarantees in non-convex cases and difficulty selecting the optimal regularization parameter γ for each p.

E. Impact of γ on The Performance of DFS

DFS performance depends on the regularization parameter γ, while its optimization converges rapidly across tested p values. The method’s computational cost is influenced by repeated eigen-decomposition, and parameter selection remains an open issue.

  • Effect of γ: Increasing γ first raises and then lowers classification accuracy for both p = 0.1 and p = 1 across all tested data sets.The performance variance from γ is comparable to that caused by changing the number of selected features.
  • Effect of γ: DFS(p = 1) and DFS(p = 0.1) show similar performance-variance trends with γ but have different optimal γ values.The extent of γ sensitivity differs across ORL, COLON, and ISOLET5.
  • Effect of γ: When few features are selected, DFS performance is more sensitive to γ.This makes regularization tuning especially consequential in low-feature settings.
  • Convergence: For p = 0.1, 0.5, and 1, DFS objectives decrease monotonically and converge to fixed values, while consecutive transformation matrices converge toward zero divergence.On COIL20 and COLON, all three settings converge within 20 iterations.
  • Time comparison: DFS takes longer than some baselines because eigen-decomposition is the most time-consuming operation and is repeated at every iteration.The computational-time comparison covers COIL20 and ISOLET5; BAHSIC also incurs high cost because it iteratively renews its data kernel matrix.
  • Future work: Choosing parameter values remains an open problem, alongside improving treatment of singular total scatter matrices and extending DFS to nonlinear kernel LDA.The paper identifies these as directions for future work.
Loading 1504.05408v1…