Direction-aware multi-label feature selection via paired signed-deviation lifting

Distance-based multi-label classifiers that rely on a fixed, non-adaptive metric—ML-kNN, RBF-kernel machines with fixed bandwidth, and analogous templates—compare instances through symmetric feature differences and therefore do not encode whether label evidence lies above or below a typical feature value; adaptive metric learning addresses this at the metric level and is complementary to the embedded feature-selection strategy we propose. We propose Paired Signed-Deviation Feature Selection (PSDFS), an embedded multi-label feature-selection method targeted at this family of classifiers. PSDFS splits each feature into above- and below-center nonnegative deviation channels and uses a paired group-sparsity penalty to recover one ranking over the original d features. For fixed fold statistics, the objective is convex in the weights; the multiplicative updates are monotonically non-increasing and satisfy a sublinear O (1/ T ) bound on average suboptimality. On 16 benchmark datasets evaluated with ML-kNN, PSDFS consistently obtains the best average rank among the compared methods on all reported metrics, with Holm–Bonferroni-corrected paired Wilcoxon improvements on Micro-F1 and Macro-F1 against all baselines and on Hamming Loss against all but one. Targeted controls show that the lift improves expressivity under nonnegativity, pairing avoids lift-induced splitting in the reported feature ranking, and the nonnegative constraint is empirically beneficial.