Source-linked AI summary
Supervised Feature Selection via Dependence Estimation
Le Song, Alex Smola, Arthur Gretton, Karsten Borgwardt, Justin Bedo
TL;DR
Supervised feature selection must identify informative, potentially nonlinear relationships while controlling the cost and difficulty associated with many features. The paper uses HSIC to estimate feature-label dependence and approximates subset selection with BAHSIC, a backward-elimination filter. BAHSIC unifies binary, multiclass, and regression selection, with theoretical support from unbiasedness and convergence properties and good reported performance on artificial and real-world data.
Problem
Feature selection needs criteria that detect linear and nonlinear feature-label dependence and remain concentrated for generalisation, while many-feature data increase collection, interpretation, and computational costs.
Method
BAHSIC selects features by backward elimination, maximising HSIC-based dependence between the selected data and labels independently of a particular classifier.
Results
BAHSIC provides a unified framework for binary, multiclass, and regression feature selection, with good performance and competitive runtime on artificial and real-world data.
Takeaways & Limitations
Kernel choice lets BAHSIC accommodate different supervised-learning problems and subsume many existing feature-selection methods as special cases.
Takeaways & Limitations
The criterion requires detecting desired dependence and concentration with respect to the underlying measure; the paper identifies these as requirements for reliable selection.
Abstract
from arXiv · showhide
We introduce a framework for filtering features that employs the Hilbert-Schmidt Independence Criterion (HSIC) as a measure of dependence between the features and the labels. The key idea is that good features should maximise such dependence. Feature selection for various supervised learning problems (including classification and regression) is unified under this framework, and the solutions can be approximated using a backward-elimination algorithm. We demonstrate the usefulness of our method on both artificial and real world datasets.
1 Introduction
The paper formulates supervised feature selection as choosing a small, informative subset whose dependence with labels supports prediction. It proposes BAHSIC, a classifier-independent backward-elimination method based on HSIC that applies across major supervised-learning tasks.
- Feature selection reduces data dimensionality, potentially lowering collection, interpretation, computation, and generalisation burdens.
- The selection problem chooses a subset T from full feature set S, bounded by t, using a relevance criterion Q(T).
- A suitable criterion should detect linear and nonlinear dependence and remain concentrated so detected dependence transfers to test data.
- HSIC measures dependence with kernels, avoids density estimation, has uniform convergence guarantees, and satisfies the stated criterion requirements.
- BAHSIC performs backward elimination using HSIC, selecting features independently of a particular classifier and thereby simplifying interpretation and computation.
- BAHSIC directly handles binary classification, multiclass classification, and regression, while kernel choices let it subsume existing methods as special cases.
2 Measures of Dependence
This section defines HSIC through kernelized feature maps and establishes theoretical properties supporting its use for feature selection. The empirical estimator is unbiased, concentrated, and consistent enough to support repeated feature selection and dependence assessment.
- HSIC uses RKHS feature maps for broad domains, including real-valued data, vectors, class labels, strings, and graphs, with dependence represented by a cross-covariance operator.
- HSIC can be written using kernel expectations, and feature selection applies it to measure dependence between a selected feature subset and labels.
- Universal kernels detect any dependence, whereas non-universal kernels may target particular dependence types, such as second-order dependence with a linear kernel.
- The empirical HSIC estimator is unbiased, contrasting with mutual information methods that may require bias correction.
- HSIC converges in probability at rate 1/√m, and its concentration follows under bounded, nonnegative kernels.
- These properties imply empirical HSIC closely reflects population HSIC, supporting consistent feature selection across repeated samples and significance testing of dependence.
3 Feature Selection via HSIC
BAHSIC selects features by repeatedly eliminating the least relevant subset according to HSIC, then ranking eliminated features so the final entries are most relevant. Kernel parameters can be adapted during selection, and removing 10% of the current features balances speed and feature quality in the reported experiments.
- With a linear data kernel, forward and backward selection are equivalent because the objective decomposes into individual coordinates, although backward elimination generally yields better features.
- BAHSIC recursively eliminates the least relevant features and appends them to an ordered list, whose final t elements solve the feature-selection problem.Features near the end of S† have higher relevance to the learning task.
- The algorithm selects an elimination set I by maximizing HSIC after removing I from the current feature set.
- BAHSIC adapts the data-kernel parameter σ through a policy such as optimization over candidate values; fixed prior kernel parameters can omit this step.
- Removing 10% of the current features at each iteration was a reported compromise between computational speed and feature quality.
4 Connections to Other Approaches
The paper relates HSIC-based selection to MMD and KTA through a specific binary-classification label kernel. Under that choice, maximizing HSIC also maximizes MMD and KTA, but the equivalence does not generally extend beyond that setting.
- For binary classification, MMD compares the class-conditional distributions, while KTA tests correlation between data and labels using tr KL / ∥K∥∥L∥.An unnormalised KTA variant uses tr KL for computational convenience.
- With the label kernel l(y, y′) = ρ(y)ρ(y′), where ρ encodes positive and negative class membership, MMD and KTA are closely related to HSIC.
- Maximizing HSIC also maximizes MMD and KTA under the specified binary-classification kernel.
- The HSIC–MMD–KTA equivalence does not generally hold for multiclass, regression, or generic binary classification.
5 Variants of BAHSIC
BAHSIC variants combine a data kernel with task-specific label kernels to address binary classification, multiclass classification, and regression. The experiments instantiate these variants as BIN, MUL, and REG, with incremental kernel updates providing a further speedup for the RBF-based cases.
- BAHSIC variants use a Gaussian data kernel while varying the label kernel to create selectors for binary classification, multiclass classification, and regression.
- Multiclass classification (MUL): The multiclass variant MUL applies a linear kernel to label vectors constructed from the class sample counts.For class i, mi is the number of samples in that class, and 1mi denotes an all-ones vector of length mi.
- Regression (REG): The regression variant REG applies a Gaussian RBF kernel to labels, fixing its width σ to the median distance between sample points.
- For these variants, BAHSIC can be accelerated by incrementally updating the RBF kernel matrix instead of recomputing all pairwise distances.The squared distance decomposes across dimensions, so each dimensional contribution is computed once and subsequently subtracted during updates.
- The experiments refer to the three BAHSIC instances as BIN, MUL, and REG, and instantiate FOHSIC with the same kernels.
6 Experimental Results
Experiments evaluate BAHSIC on artificial, real-world, and brain-computer-interface datasets. BAHSIC captures nonlinear feature dependencies, performs competitively with specialized selectors, and selects meaningful BCI frequency features.
- Experimental design: Three experiment sets assess BAHSIC on artificial datasets, real-world datasets, and a brain-computer-interface dataset.The studies examine algorithmic properties, comparisons with other methods, and whether selected BCI features are meaningful.
- Artificial datasets: BAHSIC with nonlinear kernels correctly identifies the two relevant Binary XOR dimensions even at small sample sizes, unlike FOHSIC, Pearson’s correlation, and mutual information.The competing criteria evaluate features independently and therefore miss nonlinear interactions between features.
- Artificial datasets: BAHSIC, FOHSIC, and mutual information select the correct multiclass features across sample sizes, whereas Pearson’s correlation succeeds only with large samples.The fourth class interferes with the linear correlation detected from the other three collinear classes.
- Artificial datasets: In nonlinear regression, BAHSIC and FOHSIC quickly converge to the correct features as sample size increases, while Pearson’s correlation and mutual information perform only slightly better than random.With increasing sample size, BAHSIC ranks the relevant features almost correctly in its first iteration.
- Real-world datasets: Real-world comparisons use five- and ten-feature subsets evaluated by a common Gaussian-kernel SVM with 10-fold cross-validation.Classification uses error rate, while regression uses percentage of variance not explained.
7 Conclusion
The paper concludes that BAHSIC uses HSIC-based dependence maximization with backward elimination to provide a unified feature-selection framework. It supports binary, multiclass, and regression problems while performing well on artificial and real-world data.
- Conclusion: BAHSIC selects feature subsets by maximizing dependence between data and labels using a backward-elimination procedure.The framework is based on HSIC and is presented as a filter method.
- Conclusion: The framework applies across supervised-learning forms including binary classification, multiclass classification, and regression.The same feature-selection interpretation is used across these tasks.
- Conclusion: BAHSIC demonstrates good performance compared with specialized methods on artificial and real-world datasets and is competitive in runtime.The conclusion attributes theoretical justification to the empirical HSIC estimate’s absence of bias and convergence properties.
Appendix
The appendix derives HSIC estimators by constructing unbiased estimates for distinct expectation terms and combining their kernel-matrix forms. It also relates biased HSIC estimates to MMD and Kernel Target Alignment.
- Estimator construction: Theorem 1 constructs unbiased estimators for the three expectation structures appearing in the HSIC expression.These include fully coupled, partially decoupled, and fully independent expectations.
- Estimator construction: Independent expectations are replaced by averages over index tuples in which each index occurs exactly once.For r independent random variables, the relevant tuple sets have cardinality given by the Pochhammer symbol (m)r.
- Estimator construction: Linear combinations of the empirical terms involving tr K L, 1⊤K L 1, and 1⊤K 1 1⊤L 1 yield the expected value of HSIC[F, G, Z].The appendix collects these terms after forming the required expectation combinations.
- Connections to related criteria: The biased estimators of MMD and HSIC are identical up to a constant factor, and the MMD estimate has bias O(m−1).The argument transfers the O(m−1) bias bound from the centered HSIC expression to the corresponding MMD estimate.
- Connections to related criteria: For equal class sizes, Kernel Target Alignment normalization becomes irrelevant and yields the corresponding MMD term.This establishes the same connection for Kernel Target Alignment under the stated class-balance condition.