TL;DR
This paper introduces a novel feature selection method using a non-convex $l_{p,\infty}$ operator, which combines $l_p$ and $l_\infty$ norms to encourage sparsity. They develop an efficient proximal gradient algorithm to solve this problem, demonstrating its effectiveness in improving classification accuracy on various real-world datasets compared to existing methods.
What Problem Does This Paper Address?
Feature selection is a crucial step in machine learning for identifying the most relevant features, leading to more robust and interpretable models. Traditional methods often rely on convex regularization techniques like $l_1$ or $l_2$ norms. While $l_1$ regularization promotes sparsity (setting some feature weights to zero), it might not always capture the desired structured sparsity. The paper addresses the challenge of developing a feature selection method that can achieve a more accurate estimation of the number of non-zero features, especially in multi-class and multi-label learning scenarios. They propose using a non-convex $l_{p,\infty}$ operator, where $p < 1$, which has the potential to better approximate the true number of active features. However, solving optimization problems with non-convex penalties is notoriously difficult.
Methods
The core of the paper lies in proposing and solving a new optimization problem for feature selection:
$$ \min_W J(W) = f(W) + \lambda \Phi_\lambda(W) $$
where $f(W)$ is a smooth convex loss function (like least squares) and $\Phi_\lambda(W) = \sum_{j=1}^d (\max_{1 \le k \le c} |W_{jk}|)^p$ is the $l_{p,\infty}$ penalty. The key challenge is the non-convexity introduced by the $(\cdot)^p$ term when $p < 1$.
To tackle this, the authors employ a proximal gradient method, a standard technique for solving optimization problems with composite objectives. The main computational bottleneck in this method is solving the proximal operator:
$$ \min_U \|U - A\|_F^2 + \lambda \|U\|_{p,\infty}^p $$
The paper's primary contribution is an efficient algorithm for computing this proximal operator. They decompose the problem into $d$ independent sub-problems, each optimizing a single row of the matrix $W$. For each sub-problem, they derive an analytical solution by leveraging several lemmas that characterize the structure of the optimal solution. This involves sorting the absolute values of the input vector and carefully determining which elements contribute to the maximum. They also provide an algorithm (Algorithm 1) that uses a linear or binary search to find the optimal solution for the proximal operator.
Datasets
The paper evaluates their proposed method on a variety of datasets:
- Multi-class datasets: ALLAML, GLIOMAML, LUNGML, and CARML. These are characterized by high dimensionality and a small number of samples.
- Multi-label datasets: Barcelona, MSRCv2, and TRECVID2005. For these, they extract features like color moments and GIST.
They do not introduce new benchmarks but use widely accepted datasets for evaluating feature selection methods.
Key Insights and Ideas
- Non-convexity for better sparsity estimation: The paper argues that non-convex penalties ($p < 1$) can more accurately approximate the true number of non-zero features, which is a desirable goal for feature selection.
- Efficient proximal operator computation: The core technical innovation is the development of an efficient algorithm to solve the proximal operator associated with the $l_{p,\infty}$ penalty. This is crucial for making the overall optimization tractable.
- Structured sparsity: The $l_{p,\infty}$ penalty encourages structured sparsity, meaning it tends to set entire rows of the weight matrix to zero, effectively selecting or discarding entire features across all classes.
- Impact of parameter 'p': Experiments suggest that smaller values of $p$ (e.g., 0.25, 0.5) generally lead to better classification performance, indicating the benefit of stronger non-convexity.
Key Results
- Improved Classification Accuracy: On both single-label multi-class and multi-label tasks, the proposed $l_{p,\infty}$ feature selection method, particularly with smaller $p$ values, consistently achieved higher classification accuracy (measured by accuracy for kNN/SVM and macro-F1 for multi-label tasks) compared to established methods like F-statistic, ReliefF, mRmR, and $l_{2,1}$ regularization.
- Reduced Residue: For multi-label tasks, the $l_{p,\infty}$ method resulted in significantly smaller residue values (a measure of prediction error) when using the top 20 selected features, indicating better feature subsets.
- Comparison with $l_{2,1}$: The paper explicitly compares their method with $l_{2,1}$ regularization, showing that their $l_{p,\infty}$ approach generally yields better results.
Limitations and Future Work
- Non-convexity guarantees: The authors acknowledge that due to the non-convex nature of the problem when $p < 1$, they cannot guarantee finding the global minimum. The solution might depend on initialization.
- Initialization sensitivity: They observed that different initializations can lead to slightly different selected features when $p < 1$, although the overall performance remains strong.
- Future Work: The paper implicitly suggests exploring more advanced optimization techniques to better handle the non-convexity and potentially find global optima. Further investigation into the theoretical properties of the $l_{p,\infty}$ operator for feature selection could also be a direction.
Summary updated