On the Limitation of Kernel Dependence Maximization for Feature Selection

The Hilbert-Schmidt Independence Criterion (HSIC), introduced initially in [GBSS05], is a measure quantifying the dependence between two random variables, $X$, and $Y$, using positive (semi)definite kernels. A positive semidefinite kernel $k$, simply called a kernel, on a set $\mathcal{X}$ is a symmetric function $k:\mathcal{X}\times\mathcal{X}\to\mathbb{R}$ that requires the sum $\sum_{i=1}^{n}\sum_{j=1}^{n}c_{i}c_{j}k(x_{i},x_{j})$ to be nonnegative for any $n$ distinct points $x_{1},x_{2},\ldots,x_{n}\in\mathcal{X}$ and any real numbers $\{c_{1},c_{2},\ldots,c_{n}\}$. A kernel $k$ is called a positive definite kernel when this sum equals $0$ if and only if all $c_{i}$ are zero.

We are ready to give a formal definition of HSIC, following [GBSS05, SSG⁺12].

The HSIC is always non-negative (${\rm HSIC}(X;Y)\geq 0$) for every probability distribution $\mathbb{Q}$ and positive semidefinite kernels $k_{X}$ and $k_{Y}$ [GBSS05, SSG⁺12]. Clearly, ${\rm HSIC}(X;Y)=0$ whenever $X$ and $Y$ are independent. Additionally, when the kernels $k_{X}$ and $k_{Y}$ in the Definition 1.1 are characteristic kernels in the sense of [FGSS07, Section 2.2] or [SFL11, Definition 6], then ${\rm HSIC}(X;Y)=0$ if and only if $X$ and $Y$ are independent (see [GBSS05, Theorem 4], and [SFL11, Section 2.3] for the statement). Characteristic kernels enable HSIC to capture all modes of dependence between $X$ and $Y$. Non-characteristic kernels can also be plugged into the definition of HSIC, equation (1.3), but they may fail to detect some forms of dependence between $X$ and $Y$ i.e. it is possible that ${\rm HSIC}(X;Y)=0$ but $X$ and $Y$ are not independent.

Our counterexamples apply to a wide range of HSIC through various choices of kernels $k_{X}$ and $k_{Y}$. Two requirements on the kernels $k_{X}$ and $k_{Y}$ are needed throughout the paper. The first requires that $k_{X}$ is a radially symmetric positive definite kernel.

The integral representation of $\phi_{X}$ in Assumption 1 is motivated by Schoenberg’s fundamental work [Sch38]. Given a real-valued function $\phi_{X}$, for the mapping $(x,x^{\prime})\mapsto\phi_{X}(\left\|{x-x^{\prime}}\right\|_{2}^{2})$ to qualify as a positive definite kernel on $\mathbb{R}^{m}$ for every dimension $m\in\mathbb{N}$, the representation $\phi_{X}(z)=\int_{0}^{\infty}e^{-tz}\mu(dt)$ must hold for some nonnegative finite measure $\mu$ not concentrated at zero [Sch38]. Two concrete examples satisfying Assumption 1 are the Gaussian kernel where $\phi_{X}(z)=\exp(-z)$, and the Laplace kernel where $\phi_{X}(z)=\exp(-\sqrt{z})$.

Assumption 1 ensures that the mapping $(x,x^{\prime})\mapsto\phi_{X}(\left\|{x-x^{\prime}}\right\|_{2}^{2})$ is a kernel on $\mathbb{R}^{m}$ for every dimension $m\in\mathbb{N}$. This property is useful when working with ${\rm HSIC}(X_{S};Y)$ because the dimension of the feature vector $X_{S}$ is varying with the size of $S$ and may not equal to $p$. As a side remark, the kernel $(x,x^{\prime})\mapsto\phi_{X}(\left\|{x-x^{\prime}}\right\|_{2}^{2})$ is a characteristic kernel on $\mathbb{R}^{m}$ for every dimension $m\in\mathbb{N}$ under Assumption 1 [SFL11, Proposition 5].

Our second requirement is that the kernel $k_{Y}$ is either a function of $|y-y^{\prime}|$ or a function of $yy^{\prime}$.

For $k_{Y}(y,y^{\prime})=\phi_{Y}(|y-y^{\prime}|)$ to be a positive semidefinite kernel, $\phi_{Y}(0)\geq\phi_{Y}(1)$ must hold, as $\phi_{Y}(0)-\phi_{Y}(1)=\sum_{i,j=1}^{2}c_{i}c_{j}k_{Y}(y_{i},y_{j})\geq 0$ where $c_{1}=1,c_{2}=-1,y_{1}=1,y_{2}=0$. Likewise, for $k_{Y}(y,y^{\prime})=\phi_{Y}(yy^{\prime})$ to be a positive semidefinite kernel, $\phi_{Y}(1)\geq\phi_{Y}(-1)$ must be true. Thus the inequalities in Assumption 2 are only slightly stricter than the requirement that $k_{Y}$ is a positive semidefinite kernel. Assumption 2 is very mild since it includes both characteristic kernels such as the Gaussian kernel $k_{Y}(y,y^{\prime})=\exp(-(y-y^{\prime})^{2})$ and Laplace kernel $k_{Y}(y,y^{\prime})=\exp(-|y-y^{\prime}|)$ as well as non-characteristic kernels such as the inner product kernel $k_{Y}(y,y^{\prime})=yy^{\prime}$.

Our counterexamples apply to any kernel $k_{X},k_{Y}$ obeying Assumptions 1 and 2. Thus, it applies to a wide range of ${\rm HSIC}$, including those nonparametric dependence measures utilizing characteristic kernels $k_{X}$ and $k_{Y}$ to capture all types of dependence (say, when $k_{X}$ and $k_{Y}$ are both Gaussian kernels). In these cases, ${\rm HSIC}(X;Y)=0$ if and only if $X$ and $Y$ are independent.

Throughout the remainder of the paper, we operate with two kernels $k_{X},k_{Y}$ on $\mathbb{R}^{p}$ and $\mathbb{R}$ that meet Assumptions 1 and 2, respectively. Our main results (counterexamples) for HSIC are applicable to any such kernels.

Given the covariates $X\in\mathbb{R}^{p}$ and the response $Y\in\mathbb{R}$, with $(X,Y)\sim\mathbb{P}$, in this paper we study the population level statistical properties of the solution set $S_{*}$ of the following HSIC maximization procedure:

$$S_{*}=\mathop{\rm argmax}_{S:S\subseteq\{1,2,\ldots,p\}}{\rm HSIC}(X_{S};Y),$$

(1.4)

where ${\rm HSIC}(X_{S};Y)$ is defined through the kernels $k_{X;|S|}$ and $k_{Y}$. Here the kernel $k_{X;|S|}$ on $\mathbb{R}^{|S|}$ is induced by the original kernel $k_{X}$ on $\mathbb{R}^{p}$ in the following way (recall $\phi_{X}$ in the definition of $k_{X}$):

$$k_{X;|S|}(x,x^{\prime})=\phi_{X}(\left\|{x-x^{\prime}}\right\|_{2}^{2})~{}~{}\text{for $x,x^{\prime}\in\mathbb{R}^{|S|}$}.$$

For transparency, following Definition 1.1 we can write down the definition:

$$\begin{split}{\rm HSIC}(X_{S},Y)&=\mathbb{E}[k_{X;|S|}(X_{S},X_{S}^{\prime})\cdot k_{Y}(Y,Y^{\prime})]+\mathbb{E}[k_{X;|S|}(X_{S},X_{S}^{\prime})]\cdot\mathbb{E}[k_{Y}(Y,Y^{\prime})]\\ &~{}~{}~{}~{}-2\mathbb{E}\left[\mathbb{E}[k_{X;|S|}(X_{S},X_{S}^{\prime})|X^{\prime}]\cdot\mathbb{E}[k_{Y}(Y,Y^{\prime})|Y^{\prime}]\right],\end{split}$$

(1.5)

where $(X,Y)$, $(X^{\prime},Y^{\prime})$ denote independent draws from $\mathbb{P}$. This definition of ${\rm HSIC}(X_{S},Y)$ is natural, and aligns with its proposed use for feature selection, e.g., [SBB⁺07].

Our main result shows that the feature subset $X_{S_{*}}$, chosen by maximizing ${\rm HSIC}$ as in equation (1.4) can fail to capture the explanatory relationship between $X$ and $Y$.

Theorem 1.1 cautions against relying on HSIC maximization for feature selection. The reader might wonder whether it is the combinatorial structure in defining the maximizer $S_{*}$ that is responsible for the failure observed in Theorem 1.1. To clarify the nature of the problem, we explore a continuous version of the combinatorial objective in equation (1.4). Below, we use $\odot$ to represent coordinate-wise multiplication between vectors; for instance, given a vector $\beta\in\mathbb{R}^{p}$, and covariates $X\in\mathbb{R}^{p}$, the product $\beta\odot X$ yields a new vector in $\mathbb{R}^{p}$ with its $i$th coordinate $(\beta\odot X)_{i}=\beta_{i}X_{i}$.

Now we consider HSIC maximization through a continuous optimization:

$$S_{*,{\rm cont}}=\mathop{\rm supp}(\beta_{*})~{}~{}\text{where}~{}~{}\beta_{*}=\mathop{\rm argmax}_{\beta:\left\|{\beta}\right\|_{\ell_{q}}\leq r}{\rm HSIC}(\beta\odot X;Y)$$

(1.6)

where ${\rm HSIC}(\beta\odot X,Y)$ measures the dependence between the weighted feature $\beta\odot X\in\mathbb{R}^{p}$ and the response $Y\in\mathbb{R}$, utilizing the kernels $k_{X}$ and $k_{Y}$ on $\mathbb{R}^{p}$ and $\mathbb{R}$, respectively:

$$\begin{split}{\rm HSIC}(\beta\odot X,Y)&=\mathbb{E}[k_{X}(\beta\odot X,\beta\odot X^{\prime})\cdot k_{Y}(Y,Y^{\prime})]+\mathbb{E}[k_{X}(\beta\odot X,\beta\odot X^{\prime})]\cdot\mathbb{E}[k_{Y}(Y,Y^{\prime})]\\ &~{}~{}~{}~{}-2\mathbb{E}\left[\mathbb{E}[k_{X}(\beta\odot X,\beta\odot X^{\prime})|X^{\prime}]\cdot\mathbb{E}[k_{Y}(Y,Y^{\prime})|Y^{\prime}]\right].\end{split}$$

(1.7)

In its definition (1.6), we first find the weight vector $\beta_{*}\in\mathbb{R}^{p}$ that maximizes the HSIC dependence measure between the response $Y$ and the weighted covariates $\beta\odot X$, and then use the support set of $\beta_{*}$ (the set of indices corresponding to non-zero coordinates of $\beta_{*}$) to define the feature set $S_{*,{\rm cont}}$. Note that imposing a norm constraint on the weights $\beta$—$\left\|{\beta}\right\|_{\ell_{q}}\leq r$ where $\left\|{\cdot}\right\|_{\ell_{q}}$ denotes the $\ell_{q}$ norm for $q\in[1,\infty]$ and $r<\infty$—ensures the existence of a well-defined maximizer $\beta_{*}$.

Theorem 1.1 and Theorem 1.2 show that care must be taken when using HSIC for feature selection. Notably, the requirement that the dimension $p\geq 2$ is essential for Theorem 1.1 and Theorem 1.2 to hold. This necessity follows from a positive result on HSIC maximization when using characteristic kernels $k_{X},k_{Y}$: the output feature set $X_{S_{*}}$ (or $X_{S_{*,{\rm cont}}}$) will be dependent with $Y$ unless $X$ and $Y$ are independent.

If we use the discrete maximization approach (1.4), then ${\rm HSIC}(X_{S_{*}};Y)\geq{\rm HSIC}(X;Y)>0$. This implies that $X_{S_{*}}$ and $Y$ are dependent because by definition of ${\rm HSIC}$, ${\rm HSIC}(X_{S_{*}};Y)=0$ if $X_{S_{*}}$ and $Y$ are independent. Similarly, if we use the continuous HSIC maximization approach (1.6), then ${\rm HSIC}(\beta_{*}\odot X,Y)>0$ which then implies $X_{S_{*},{\rm cont}}$ and $Y$ cannot be independent. ∎

To conclude, while intuitively appealing, using HSIC maximization for feature selection may inadvertently exclude variables necessary for fully understanding the response $Y$.

In the literature, there are two primary approaches to employing kernel-based nonparametric (conditional) dependence measures between variables for feature selection.

The first approach, directly relevant to our work, is to maximize the dependence measure between the response variable $Y$ and the feature subset $X_{S}$. In this paper, we focus on Hilbert Schmidt Independence Criterion (HSIC), a popular kernel-based nonparametric dependence measure [GBSS05]. Unlike many other dependence measures, HSIC allows easy estimation from finite samples with parametric $1/\sqrt{n}$ convergence rates where $n$ is the sample size [GBSS05]. Since its introduction, HSIC has become a popular tool for feature selection. This HSIC maximization method, formulated as equation (1.4), was developed by [SSG⁺07] and has been applied in diverse fields such as bioinformatics [SBB⁺07, GT18]. Subsequent works [MDF10, SSG⁺12] proposed continuous relaxations of this formulation to facilitate computation. Our main findings, Theorem 1.1 and Theorem 1.2, provide concrete counterexamples advising caution when selecting features via HSIC maximization, as one may miss features needed for fully understanding the response $Y$.

The second approach minimizes the kernel conditional dependence between $Y$ and $X$ given the feature subset $X_{S}$ [FGSS07, FBJ09, CSWJ17, CLLR23]. Remarkably, this approach ensures that the selected feature subset $X_{S_{*}}$ contains all features necessary to fully explain the response $Y$, as guaranteed by the conditional independence $Y\perp X\mid X_{S_{*}}$. This theoretical guarantee is achieved under a nonparametric setup without assuming specific parametric distribution models for the data $(X,Y)$ [FBJ09]. However, computing the kernel conditional dependence measures required by this approach is more computationally demanding than calculating the HSIC used in the maximization approach due to the need for kernel matrix inversions [FGSS07].

Notably, our main findings elucidate a distinction between these two kernel-based feature selection strategies. The maximization approach, which we study in this paper, does not enjoy the same conditional independence guarantee as the minimization approach. Our counterexamples in Theorem 1.1 and Theorem 1.2 demonstrate that the HSIC maximization approach can fail to select critical variables needed to fully explain the response $Y$, highlighting a tradeoff between computational effort and the ability to recover all important variables.

To clarify, our research focuses on maximizing HSIC for feature selection as described in equation (1.4). It is important to note that there are alternative methods of employing HSIC in feature selection, such as HSIC-Lasso described in [YJS⁺14], which involves selecting features through a least square regression that applies $\ell_{1}$ penalties to the feature weights. HSIC-Lasso, though sharing a commonality in nomenclature with HSIC, is fundamentally a regression method, which differs from the dependence maximization strategy we explore here in equation (1.4). Our counterexamples do not extend to HSIC-Lasso.

Finally, consider the recent developments in feature selection for binary labels $Y\in\{\pm 1\}$, where a feature subset $S$ is selected by maximizing the Maximum Mean Discrepancy (MMD) between the conditional distributions $\mathcal{L}(X_{S}\mid Y=1)$ and $\mathcal{L}(X_{S}\mid Y=-1)$ over $S$ [WDX23, MKB⁺23]. Given the established connections between MMD and HSIC in the literature, e.g., [SSG⁺07, Theorem 3], our counterexamples in Theorem 1.1 and Theorem 1.2—developed under conditions with binary response $Y$ (see the proofs in Section 2)—have further implications for these MMD-based feature selection methods. We intend to report these implications and discuss methodological developments in a follow-up paper.

We establish Theorem 1.1 and Theorem 1.2 for the case $p=2$.

For our counterexample, we construct a family of distributions $\mathbb{P}_{\Delta}$ parameterized by a vector $\Delta$. Our proof proceeds by showing that there exists a vector $\Delta$ such that if the data $(X,Y)$ follows the distribution $\mathbb{P}_{\Delta}$, then the conclusions of Theorem 1.1 and Theorem 1.2 hold.