Simple Stopping Criteria for Information Theoretic Feature Selection

Abstract

Feature selection aims to select the smallest feature subset that yields the minimum generalization error. In the rich literature in feature selection, information theory-based approaches seek a subset of features such that the mutual information between the selected features and the class labels is maximized. Despite the simplicity of this objective, there still remain several open problems in optimization. These include, for example, the automatic determination of the optimal subset size (i.e., the number of features) or a stopping criterion if the greedy searching strategy is adopted. In this paper, we suggest two stopping criteria by just monitoring the conditional mutual information (CMI) among groups of variables. Using the recently developed multivariate matrix-based Rényi’s $\alpha$-entropy functional, which can be directly estimated from data samples, we showed that the CMI among groups of variables can be easily computed without any decomposition or approximation, hence making our criteria easy to implement and seamlessly integrated into any existing information theoretic feature selection methods with a greedy search strategy.

1. Introduction

Feature selection aims to find the smallest feature subset that yields the minimum generalization error [1]. As a fundamental problem in machine learning and statistics communities, feature selection is relevant to understand better the classification problem at hand in many applications, such as medical decision making, economics, and engineering [2]. Consequently, it also has a large impact on interpretability or explainability, which is totally missing in most current deep learning techniques [3]. Ever since the pioneering work of Battiti [4], information theoretic feature selection has been extensively investigated in signal processing and machine learning communities (e.g., [5,6,7]). Given a set of F features $S=\{x_1,x_2,\cdots ,x_F\}$ (each $x_i$ denotes an attribute) and their corresponding class labels y, these methods seek a subset of informative attributes $S^{\star }\subset S$, such that the mutual information (MI) between $S^{\star }$ and y (i.e., $\mathbf{I}(S^{\star };y)$) is maximized [8].

Despite the simplicity of this objective, several open problems still remain in information theoretic feature selection. These include, for example, the reliable estimation of $\mathbf{I}(S^{\prime };y)$ in high-dimensional space, in which $S^{\prime }$ denotes an arbitrary subset of S [8,9]. In fact, $S^{\prime }$ may contain both continuous and discrete variables, whereas y is a discrete variable. There is no universal agreement on the definition of MI between a discrete variable and a group of mixed variables, let alone its estimation [10]. Therefore, almost all existing information theoretic feature selection methods estimate $\mathbf{I}(S^{\prime };y)$ by first discretizing the feature space and then approximating $\mathbf{I}(S^{\prime };y)$ with low-order MI quantities, such as relevancy $\mathbf{I}(x_i;y)$, joint relevancy $\mathbf{I}(\{x_i,x_j\};y)$, conditional relevancy $\mathbf{I}(x_i;y|x_j)$, redundancy $\mathbf{I}(x_i;x_j)$, conditional redundancy $\mathbf{I}(x_i;x_j|y)$, and synergy [11]. These low-order MI quantities only capture the low-order feature dependency and, hence, severely limit the performance of existing information theoretic feature selection methods [12]. Interested readers can check Reference [8] for a systemic review of 17 popular low-order information theoretic criteria in the last two decades. Apart from MI estimation, another challenging problem, which also impacts performance greatly, is the automatic determination of the optimal size of $S^{\star }$. This is because most of the information theoretic feature selection methods do not have a stopping criterion [1]. Hence, the user must find criteria to estimate the best number of features.

Regarding the first problem, our recent work [13] suggested that $\mathbf{I}(S^{\prime };y)$ can be efficiently estimated using the normalized eigenspectrum of a Hermitian matrix of the projected data in the reproducing kernel Hilbert space (RKHS). In this paper, we expand on the topic of Reference [13] and illustrate that the novel multivariate matrix-based Rényi’s $\alpha$-entropy functional also enables simple strategies to guide the early stopping in the greedy search procedure of information theoretic feature selection methods.

Before presenting our methods, we first briefly review related work and also point out a common issue in most previous methods. Perhaps the most acknowledged stopping criterion for information theoretic feature selection is that the value of $\mathbf{I}(S^{\prime };y)$ stops increasing or reaches its maximum [14,15]. Given a new feature $x^{\prime }$, this rule suggests that we should stop selection if $\mathbf{I}(\{S^{\prime },x^{\prime }\};y)\le \mathbf{I}(S^{\prime };y)$. An alternative approach is using the concept of the Markov blanket (MB) [16,17]. By definition, the MB M of a target variable y is the smallest subset of S such that y is conditional independent of the rest of the variables $S-M$, i.e., $y\perp (S-M)|M$ [1]. From the perspective of information theory, this rule indicates that we should stop selection if the conditional mutual information (CMI) $\mathbf{I}\left(\right\{S-M\};y|M)$ is zero.

Despite their simplicity, both rules are overoptimistic and cannot be applied in practice. In fact, by the chain rule of mutual information [18], we have:

$$\mathbf{I}(\{S^{\prime },x^{\prime }\};y)=\mathbf{I}(S^{\prime };y)+\mathbf{I}(x^{\prime };y|S^{\prime }),$$

(1)

and:

$$\mathbf{I}\left(\right\{S-M\};y|M)=\mathbf{I}(S;y)-\mathbf{I}(M;y).$$

(2)

According to Equations (1) and (2), the feature selection is stopped if and only if the CMI item $\mathbf{I}(x^{\prime };y|S^{\prime })$ or $\mathbf{I}\left(\right\{S-M\};y|M)$ is zero. Unfortunately, since CMI is always non-negative [18] and rarely reduces to zero in practice due to statistical variation and chance agreement between variables [19], we always have $\mathbf{I}(\{S^{\prime },x^{\prime }\};y)>\mathbf{I}(S^{\prime };y)$ and $\mathbf{I}\left(\right\{S-M\};y|M)>0$. That is to say, the maximum value of $\mathbf{I}(S^{\prime };y)$ is exactly $\mathbf{I}(S;y)$ and a perfect MB of y is perhaps the feature set S itself.

Admittedly, one can say that we can stop the selection if the increment of $\mathbf{I}(S^{\prime };y)$ or the decrement of $\mathbf{I}(\{S-S^{\prime }\};y|S^{\prime })$ approaches zero with a tiny residual. Unfortunately, since we still do not have a reliable estimator of MI and CMI in high-dimensional space (before [13]), it is hard for us to measure or determine how small the residual terms are.

To the best of our knowledge, there are only two methods in the literature that can stop the greedy search. François et al. [14] suggested monitoring the value of $\mathbf{I}(S^{\prime };y)$ using a permutation test [20]. Specifically, suppose the new feature selected in the current iteration is $x^{\mathrm{cand}}$, the authors create a random permutation of $x^{\mathrm{cand}}$ (without permuting the corresponding y), denoted ${\tilde{x}}^{\mathrm{cand}}$. If $\mathbf{I}(\{S^{\prime },x^{\mathrm{cand}}\};y)$ is not significantly larger than $\mathbf{I}(\{S^{\prime },{\tilde{x}}^{\mathrm{cand}}\};y)$, $x^{\mathrm{cand}}$ can be discarded and the feature selection is stopped. Moreover, François et al. also suggested using the k-nearest neighbors (KNN) estimator [21] to estimate $\mathbf{I}(S^{\prime };y)$. However, their results indicated that this estimator may result in negative CMI quantities no matter the selection of k. Vinh et al. [19], on the other hand, proposed monitoring the increment of $\mathbf{I}(S^{\prime };y)$ after adding $x^{\mathrm{cand}}$ (i.e., $\mathbf{I}({\tilde{x}}^{\mathrm{cand}};y|S^{\prime })$) using ${\chi }^2$ distribution. If $\mathbf{I}(x^{\mathrm{cand}};y|S^{\prime })$ is smaller than a threshold obtained from the ${\chi }^2$ distribution at a certain significance level, the feature selection is stopped. However, one should note that the ${\chi }^2$ distribution assumption holds if and only if $\mathbf{I}({\tilde{x}}^{\mathrm{cand}};y|S^{\prime })=0$ [19,22]. Unfortunately, as we emphasized earlier, the CMI quantity rarely reduces to zero in practice. This is also the reason why Vinh’s method is likely to severely underestimate the require number of features, as is illustrated in the experiments.

Different from previous work, we suggest using the novel multivariate matrix-based Rényi’s $\alpha$-entropy functional [23] to estimate MI and CMI in high-dimensional space. We also present two simple stopping criteria based on these new estimators. To summarize, our main contributions are twofold:

• Efficient stopping criteria for feature selection are still missing in the literature. We present two rules based on the new estimators of information theoretic descriptors of Rényi’s $\alpha$-entropy in RKHS. One should note that the properties, utilities, and possible applications of these new estimators are rather new and mostly unknown to practitioners;
• Our criteria are extremely simple and flexible. First, the proposed tests and stopping criteria can be incorporated into any sequential feature selection procedure, such as mutual information-based feature selection (MIFS) [4] and maximum-relevance minimum-redundancy (MRMR) [24]. Second, benefiting from the higher accuracy of the estimation, we demonstrated that one can simply use a threshold in a heuristic manner, which is very valuable for practitioners across different domains.

2. Simple Stopping Criteria for Information Theoretic Feature Selection

In this section, we start with a brief introduction to the recently proposed matrix-based Rényi’s $\alpha$-entropy functional and its multivariate extension [13]. The novel definition yields two simple stopping criteria as presented below.

2.1. Matrix-Based Rényi’s $\alpha$-Entropy Functional and Its Multivariate Extension

In information theory, a natural extension of the well-known Shannon’s entropy is Rényi’s $\alpha$-order entropy [25]. For a random variable X with probability density function (PDF) $f\left(x\right)$ in a finite set $\mathcal{X}$, the $\alpha$-entropy ${\mathbf{H}}_{\alpha }\left(X\right)$ is defined as:

$${\mathbf{H}}_{\alpha }\left(f\right)=\frac{1}{1-\alpha }log{\int }_{\mathcal{X}}{f}^{\alpha }\left(x\right)dx.$$

(3)

Based on this entropy definition, Rényi then proposed a divergence measure ($\alpha$-relative entropy) between random variables with PDFs f and g:

$${\mathbf{D}}_{\alpha }\left(f\right|\left|g\right)=\frac{1}{\alpha -1}log{\int }_{\mathcal{X}}f\left(x\right){\left(\frac{f\left(x\right)}{g\left(x\right)}\right)}^{\alpha -1}dx.$$

(4)

Rényi’s entropy and divergence have a long track record of usefulness in information theory and its applications [26]. Unfortunately, the accurate PDF estimation impedes its more widespread adoption in data driven science. To solve this problem, References [13,23] suggest similar quantities that resemble quantum Rényi’s entropy [27] in terms of the normalized eigenspectrum of the Hermitian matrix of the projected data in RKHS, thus estimating the entropy and joint entropy among two or multiple variables directly from data without PDF estimation. For brevity, we directly give the definition.

Definition 1.

Let $\kappa :\mathcal{X}\times \mathcal{X}\mapsto \mathbb{R}$ be a real valued positive definite kernel that is also infinitely divisible [28]. Given $X=\{x^1,x^2,\dots ,x^n\}$ and the Gram matrix K obtained from κ on all pairs of exemplars, that is, ${\left(K\right)}_{ij}=\kappa (x^i,x^j)$, a matrix-based analogue to Rényi’s α-entropy for X can be defined, using a normalized positive definite (NPD) matrix A of size $n\times n$ and trace 1, by:

$${\mathbf{S}}_{\alpha }\left(A\right)=\frac{1}{1-\alpha }{log}_2\left(\mathrm{tr}\left(A^{\alpha }\right)\right)=\frac{1}{1-\alpha }{log}_2\left[\sum _{i=1}^n{\lambda }_i{\left(A\right)}^{\alpha }\right],$$

(5)

where $A_{ij}=\frac{1}{n}\frac{K_{ij}}{\sqrt{K_{ii}{K}_{jj}}}$ and ${\lambda }_i\left(A\right)$ denotes the i-th eigenvalue of A.

The matrix functional in Equation (5) bears a lot of resemblance to well-known operational quantities from quantum information theory [27], where the density matrix (operator) $\rho$ can be employed to compute expectation over an observable represented by the operator A as $\langle A\rangle =\mathrm{tr}\left(\rho A\right)$. For instance, the quantum extensions of Rényi’s entropy [29,30] is given by:

$${\mathbf{S}}_{\alpha }\left(\rho \right)=\frac{1}{1-\alpha }log\left[\mathrm{tr}\left({\rho }^{\alpha }\right)\right].$$

(6)

Although some properties of Equation (6) also apply to Equation (5), the matrix-based estimation is very different, since it deals with the Gram matrix obtained from pairwise evaluations of a positive definite kernel from data samples. Consequently, this novel definition not only involves the functional, but also the kernels employed to construct positive definite matrix.

Definition 2.

Given a collection of n samples ${\{s_i=(x_1^i,x_2^i,\cdots ,x_k^i)\}}_{i=1}^n$, where the superscript i denotes the sample index, each sample contains k ($k\ge 2$) measurements $x_1\in {\mathcal{X}}_1$, $x_2\in {\mathcal{X}}_2$, ⋯, $x_k\in {\mathcal{X}}_k$ obtained from the same realization, and the positive definite kernels ${\kappa }_1:{\mathcal{X}}_1\times {\mathcal{X}}_1\mapsto \mathbb{R}$, ${\kappa }_2:{\mathcal{X}}_2\times {\mathcal{X}}_2\mapsto \mathbb{R}$, ⋯, ${\kappa }_k:{\mathcal{X}}_k\times {\mathcal{X}}_k\mapsto \mathbb{R}$, let us denote $X_l=\{x_l^1,x_l^2,\cdots ,x_l^n\}(1\le l\le k)$ containing the l-th measurement of all samples, the Rényi’s α-order joint-entropy among k variables (denote here ${\mathbf{J}}_{\alpha }(X_1,X_2,\cdots ,X_k)$) can be defined using the following matrix-based analogue:

$${\mathbf{J}}_{\alpha }(X_1,X_2,\cdots ,X_k)={\mathbf{S}}_{\alpha }\left(\frac{A_1\odot A_2\odot \cdots \odot A_k}{\mathrm{tr}(A_1\odot A_2\odot \cdots \odot A_k)}\right),$$

(7)

where ${\left(A_1\right)}_{ij}={\kappa }_1(x_1^i,x_1^j)$, ${\left(A_2\right)}_{ij}={\kappa }_2(x_2^i,x_2^j)$, ⋯, ${\left(A_k\right)}_{ij}={\kappa }_k(x_k^i,x_k^j)$, and ⊙ denotes the Hadamard product.

The following two corollaries (proved in Reference [13]) serve as a foundation for our Definition 2. Specifically, Corollary 1 indicates that the joint entropy of a set of variables is greater than or equal to the maximum of all of the individual entropies of the variables in the set, whereas Corollary 2 suggests that the joint entropy of a set of variable is less than or equal to the sum of the individual entropies of the variables in the set.

Corollary 1.

Let $\left[C\right]$ be the index set $\{1,2,\cdots ,C\}$. We partition $\left[C\right]$ into two complementary subsets $\mathbf{s}$ and $\tilde{\mathbf{s}}$. For any $\mathbf{s}\subset \left[C\right]$, denote all indices in $\mathbf{s}$ with $s_1,s_2,\cdots ,s_{\left|\mathbf{s}\right|}$, where $|·|$ stands for cardinality. Similarly, denote all indices in $\tilde{\mathbf{s}}$ with ${\tilde{s}}_1,{\tilde{s}}_2,\cdots ,{\tilde{s}}_{|\tilde{\mathbf{s}}|}$. Also let $A_1$, $A_2$, ⋯, $A_C$ be C $n\times n$ positive definite matrices with trace 1 and non-negative entries, and ${\left(A_1\right)}_{ii}={\left(A_2\right)}_{ii}=\cdots ={\left(A_C\right)}_{ii}=\frac{1}{n}$, for $i=1,2,\cdots ,n$. Then, the following two inequalities hold:

$$\begin{array}{c}\hfill {\mathbf{S}}_{\alpha }\left(\frac{A_1\odot A_2\odot \cdots \odot A_C}{\mathrm{tr}(A_1\odot A_2\odot \cdots \odot A_C)}\right)\le {\mathbf{S}}_{\alpha }\left(\frac{A_{s_1}\odot A_{s_2}\odot \cdots \odot A_{s_{\left|\mathbf{s}\right|}}}{\mathrm{tr}(A_{s_1}\odot A_{s_2}\odot \cdots \odot A_{s_{\left|\mathbf{s}\right|}})}\right)+{\mathbf{S}}_{\alpha }\left(\frac{A_{{\tilde{s}}_1}\odot A_{{\tilde{s}}_2}\odot \cdots \odot A_{{\tilde{s}}_{|\tilde{\mathbf{s}}|}}}{\mathrm{tr}(A_{{\tilde{s}}_1}\odot A_{{\tilde{s}}_2}\odot \cdots \odot A_{{\tilde{s}}_{|\tilde{\mathbf{s}}|}})}\right),\end{array}$$

(8)

$$\begin{array}{c}\hfill {\mathbf{S}}_{\alpha }\left(\frac{A_1\odot A_2\odot \cdots \odot A_C}{\mathrm{tr}(A_1\odot A_2\odot \cdots \odot A_C)}\right)\ge max\left[{\mathbf{S}}_{\alpha }\left(\frac{A_{s_1}\odot A_{s_2}\odot \cdots \odot A_{s_{\left|\mathbf{s}\right|}}}{\mathrm{tr}(A_{s_1}\odot A_{s_2}\odot \cdots \odot A_{s_{\left|\mathbf{s}\right|}})}\right),{\mathbf{S}}_{\alpha }\left(\frac{A_{{\tilde{s}}_1}\odot A_{{\tilde{s}}_2}\odot \cdots \odot A_{{\tilde{s}}_{|\tilde{\mathbf{s}}|}}}{\mathrm{tr}(A_{{\tilde{s}}_1}\odot A_{{\tilde{s}}_2}\odot \cdots \odot A_{{\tilde{s}}_{|\tilde{\mathbf{s}}|}})}\right)\right].\end{array}$$

(9)

Corollary 2.

Let $A_1$, $A_2$, ⋯, $A_C$ be C $n\times n$ positive definite matrices with trace 1 and non-negative entries, and ${\left(A_1\right)}_{ii}={\left(A_2\right)}_{ii}=\cdots ={\left(A_C\right)}_{ii}=\frac{1}{n}$, for $i=1,2,\cdots ,n$. Then, the following two inequalities hold:

$${\mathbf{S}}_{\alpha }\left(\frac{A_1\odot A_2\odot \cdots \odot A_C}{\mathrm{tr}(A_1\odot A_2\odot \cdots \odot A_C)}\right)\le {\mathbf{S}}_{\alpha }\left(A_1\right)+{\mathbf{S}}_{\alpha }\left(A_2\right)+\cdots +{\mathbf{S}}_{\alpha }\left(A_C\right),$$

(10)

$${\mathbf{S}}_{\alpha }\left(\frac{A_1\odot A_2\odot \cdots \odot A_C}{\mathrm{tr}(A_1\odot A_2\odot \cdots \odot A_C)}\right)\ge max[{\mathbf{S}}_{\alpha }\left(A_1\right),{\mathbf{S}}_{\alpha }\left(A_2\right),\cdots ,{\mathbf{S}}_{\alpha }\left(A_C\right)].$$

(11)

2.2. Stopping Criteria Based on Conditional Mutual Information

Denote $\{x_1,x_2,\cdots ,x_k\}$, the selected features in $S^{\prime }$, $\{x_1^{\prime },x_2^{\prime },\cdots ,x_m^{\prime }\}$, the remaining features in $S-S^{\prime }$, given the entropy and joint entropy estimators shown in Equations (5)–(7), the MI between y and $S^{\prime }$ (i.e., $\mathbf{I}(S^{\prime };y)$) and the CMI between y and $S-S^{\prime }$ conditioning on $S^{\prime }$ (i.e., $\mathbf{I}(\{S-S^{\prime }\};y|S^{\prime })$), with analogue properties to Shannon’s definition of MI and CMI (by Shannon’s definition, $\mathbf{I}(S^{\prime };y)=\mathbf{H}\left(S^{\prime }\right)+\mathbf{H}\left(y\right)-\mathbf{H}(S^{\prime },y)$ and $\mathbf{I}(\{S-S^{\prime }\};y|S^{\prime })=\mathbf{H}(S-S^{\prime },S^{\prime })+\mathbf{H}(y,S^{\prime })-\mathbf{H}(S-S^{\prime },y,S^{\prime })-\mathbf{H}\left(S^{\prime }\right)$, where $\mathbf{H}$ denotes entropy or joint entropy), which can be estimated with Equations (12) and (13), respectively, where $A_1$, $A_2$, ⋯, $A_k$, B, $C_1$, $C_2$, ⋯, $C_m$ denote the Gram matrices evaluated over $x_1$, $x_2$, ⋯, $x_k$, y, $x_1^{\prime }$, $x_2^{\prime }$, ⋯, $x_m^{\prime }$, respectively, and ⊙ denotes the Hadamard product.

$${\mathbf{I}}_{\alpha }(B;\{A_1,A_2,\cdots ,A_k\})={\mathbf{S}}_{\alpha }\left(B\right)+{\mathbf{S}}_{\alpha }\left(\frac{A_1\odot A_2\odot \cdots \odot A_k}{\mathrm{tr}(A_1\odot A_2\odot \cdots \odot A_k)}\right)-{\mathbf{S}}_{\alpha }\left(\frac{A_1\odot A_2\odot \cdots \odot A_k\odot B}{\mathrm{tr}(A_1\odot A_2\odot \cdots \odot A_k\odot B)}\right),$$

(12)

$$\begin{array}{cc}\hfill {\mathbf{I}}_{\alpha }(\{C_1,C_2,\cdots ,C_m\};B|\{A_1,A_2,\cdots ,A_k\})& ={\mathbf{S}}_{\alpha }\left(\frac{A_1\odot A_2\odot \cdots \odot A_k\odot C_1\odot C_2\odot \cdots \odot C_m}{\mathrm{tr}(A_1\odot A_2\odot \cdots \odot A_k\odot C_1\odot C_2\odot \cdots \odot C_m)}\right)\hfill \\ & +{\mathbf{S}}_{\alpha }\left(\frac{B\odot A_1\odot A_2\odot \cdots \odot A_k}{\mathrm{tr}(B\odot A_1\odot A_2\odot \cdots \odot A_k)}\right)\hfill \\ & \hfill -{\mathbf{S}}_{\alpha }\left(\frac{A_1\odot A_2\odot \cdots \odot A_k\odot B\odot C_1\odot C_2\odot \cdots \odot C_m}{\mathrm{tr}(A_1\odot A_2\odot \cdots \odot A_k\odot B\odot C_1\odot C_2\odot \cdots \odot C_m)}\right)-{\mathbf{S}}_{\alpha }\left(\frac{A_1\odot A_2\odot \cdots \odot A_k}{\mathrm{tr}(A_1\odot A_2\odot \cdots \odot A_k)}\right).\end{array}$$

(13)

As can be seen, the multivariate matrix-based Rényi’s $\alpha$-entropy functional enables simple estimation of both MI and CMI in high-dimensional space, no matter the data characteristics (e.g., continuous or discrete) in each dimension. In contrast to previous definitions on Rényi’s $\alpha$-mutual information [31] that stem from a probabilistic perspective using expectations over PDFs, Equations  (12) and (13) directly estimate MI and CMI in RKHS. Benefiting from these elegant expressions, suppose the new feature selected in the current iteration is $x^{\mathrm{cand}}$, we present two simple criteria to guide the early stopping of the greedy search. Specifically, we aim to test the “goodness-of-fit” of the MB condition, i.e., $S-S^{\prime }$ is the MB of y given $S^{\prime }$. Intuitively, if $\mathbf{I}(\{S-S^{\prime }-x^{\mathrm{cand}}\};y|\{S^{\prime },x^{\mathrm{cand}}\})$ approaches zero, the MB condition is approximately satisfied.

Criterion I.

If $\mathbf{I}(\{S-S^{\prime }-x^{\mathrm{cand}}\};y|\{S^{\prime },x^{\mathrm{cand}}\})\le \epsilon$, where $\epsilon$ refers to a tiny threshold, then we should stop the selection. We term this criterion CMI-heuristic, since $\epsilon$ is a heuristic value.

Criterion II.

Motivated by Reference [14], in order to quantify how $x^{\mathrm{cand}}$ affects the MB condition, we created a random permutation of $x^{\mathrm{cand}}$ (without permuting the corresponding y), denoted ${\tilde{x}}^{\mathrm{cand}}$. If $\mathbf{I}(\{S-S^{\prime }-x^{\mathrm{cand}}\};y|\{S^{\prime },x^{\mathrm{cand}}\})$ is not significantly smaller than $\mathbf{I}(\{S-S^{\prime }-{\tilde{x}}^{\mathrm{cand}}\};y|\{S^{\prime },{\tilde{x}}^{\mathrm{cand}}\})$, $x^{\mathrm{cand}}$ can be discarded and the feature selection is stopped. We term this criterion CMI-permutation (see Algorithm 1 for more details, where $\mathbb{1}$ is an indicator function which is 1 if its argument is true and 0 otherwise.).

Algorithm 1 CMI-permutation

Input: Feature set S; Selected feature subset $S^{\prime }$; Class labels y; Selected feature in the current iteration $x^{\mathrm{cand}}$; Permutation number P; Significance level $\theta$. Output: decision (Stop selection or Continue selection).   1: Estimate $\mathbf{I}(\{S-S^{\prime }-x^{\mathrm{cand}}\};y|\{S^{\prime },x^{\mathrm{cand}}\})$ with Equation (13).   2: for$i=1$ to P do   3:     Randomly permute $x^{\mathrm{cand}}$ to obtain ${\tilde{x}}_i^{\mathrm{cand}}$.   4:     Estimate $\mathbf{I}(\{S-S^{\prime }-{\tilde{x}}_i^{\mathrm{cand}}\};y|\{S^{\prime },{\tilde{x}}_i^{\mathrm{cand}}\})$ with Equation (13).   5: end for   6: if$\frac{{\sum }_{i=1}^P\mathbb{1}[\mathbf{I}(\{S-S^{\prime }-x^{\mathrm{cand}}\};y|\{S^{\prime },x^{\mathrm{cand}}\})\ge \mathbf{I}(\{S-S^{\prime }-{\tilde{x}}_i^{\mathrm{cand}}\};y|\{S^{\prime },{\tilde{x}}_i^{\mathrm{cand}}\})]}{P}\le \theta$then   7:     decision←Continue selection.   8: else   9:     decision←Stop selection. 10: end if 11: returndecision

3. Experiments and Discussions

We compared our two criteria with existing ones [14,19] on 10 well-known public datasets used in previous feature selection research [8,19], covering a wide variety of sample-feature ratios and a range of multiclass problems. The detailed properties of these datasets, including the number of features (F), the number of examples (N), and the number of classes (C), are available in Reference [8]. We refer the criterion in Reference [19] $\Delta \mathrm{MI}$-${\chi }^2$, since it monitors the increment of MI $\mathbf{I}(S^{\prime };y)$ (i.e., $\mathbf{I}(x^{\mathrm{cand}};y|S^{\prime })$) with ${\chi }^2$ distribution. We refer the criterion in Reference [14] MI-permutation, since it uses the permutation test to quantify the impact of $x^{\mathrm{cand}}$ on $\mathbf{I}(S^{\prime };y)$. Throughout this paper, we selected $\epsilon ={10}^{-4}$ in CMI-heuristic and used the multivariate matrix-based Rényi’s $\alpha$-entropy functional to estimate all MI quantities in MI-permutation. The baseline information feature selection method used in this paper is from Reference [13], which directly optimizes $\mathbf{I}(S^{\prime };y)$ in a greedy manner without any decomposition or approximation. An example for different stopping criteria on the dataset waveform is shown in Figure 1.

To provide a comprehensive evaluation, we tested the performance of the novel Rényi’s $\alpha$-entropy estimator with $\alpha =1.01$ (to approximate Shannon’s definition) and $\alpha =2$ (i.e., the quadratic information quantities that have been widely applied in information theoretic learning [26]). Moreover, we also tested the performance of different statistical tests with significance level $\theta =0.95$ and $\theta =0.99$, but since the results are very similar, herein, we only report results with $\theta =0.95$. The quantitative results, under different values of $\alpha$, are summarized in

Table 1. The number of selected features (#F) and the bootstrap classification accuracy (acc.) comparison for CMI-heuristic and CMI-permutation against different stopping criteria. We set $\alpha =1.01$ for Rényi’s $\alpha$-entropy functional. All criteria are ranked based on the difference between their selected number of features and the optimal values. The best two ranks are marked with green and blue, respectively. The average rank across all datasets is reported in the bottom line. The value behind the name of each dataset indicates the total number of features.

	CMI-Heuristic			CMI-Permutation			$\mathbf{\Delta }$MI-${\mathit{\chi }}^2$ [19]			MI-Permutation [14]			“Optimal”
	#F	acc.	rank	#F	acc.	rank	#F	acc.	rank	#F	acc.	rank	#F	acc.
waveform (21)	11	84.7 ± 1.8	1	4	78.3 ± 1.8	3	3	76.1 ± 1.8	4	5	80.2 ± 1.8	2	11	84.7 ± 1.8
breast (30)	2	92.3 ± 1.7	1	2	92.3 ± 1.7	1	2	92.3 ± 1.7	1	2	92.3 ± 1.7	1	2	95.2 ± 1.2
heart (13)	13	81.7 ± 3.5	4	4	80.4 ± 3.3	1	2	76.9 ± 3.8	3	4	80.4 ± 3.3	1	6	82.6 ± 3.0
spect (22)	22	80.6 ± 3.6	4	11	82.1 ± 3.3	1	1	80.1 ± 3.3	3	7	81.1 ± 3.3	2	11	82.1 ± 3.3
ionosphere (34)	15	83.3 ± 2.8	1	7	81.8 ± 2.8	2	1	76.7 ± 3.2	4	7	81.8 ± 2.8	2	33	85.3 ± 3.0
parkinsons (22)	12	85.2 ± 3.7	1	4	85.0 ± 3.2	2	1	85.1 ± 3.5	4	4	85.0 ± 3.2	2	9	86.5 ± 3.4
semeion (256)	59	86.1 ± 1.3	1	20	77.7 ± 1.5	2	4	49.6 ± 1.7	4	20	77.7 ± 1.5	2	73	93.3 ± 1.3
Lung (325)	5	74.2 ± 7.7	3	10	73.9 ± 8.0	2	1	46.5 ± 7.5	4	13	79.1 ± 7.9	1	41	84.3 ± 6.5
Lympth (4026)	6	81.3 ± 5.8	1	248	88.7 ± 6.1	3	2	62.8 ± 6.5	2	249	88.9 ± 6.2	4	70	90.7 ± 5.4
Madelon (500)	3	69.5 ± 1.6	2	2	59.5 ± 1.6	3	4	76.7 ± 1.5	1	2	59.5 ± 1.6	3	4	76.7 ± 1.5
average rank			1.9			2.0			3.0			2.0

and

Table 2. The number of selected features (#F) and the bootstrap classification accuracy (acc.) comparison for CMI-heuristic and CMI-permutation against different stopping criteria. We set $\alpha =2$ for Rényi’s $\alpha$-entropy functional. All criteria are ranked based on the difference between their selected number of features and the optimal values. The best two ranks are marked with green and blue, respectively. The average rank across all datasets is reported in the bottom line. The value behind the name of each dataset indicates the total number of features.

	CMI-Heuristic			CMI-Permutation			$\mathbf{\Delta }$MI-${\mathit{\chi }}^2$ [19]			MI-Permutation [14]			“Optimal”
	#F	acc.	rank	#F	acc.	rank	#F	acc.	rank	#F	acc.	rank	#F	acc.
waveform (21)	17	84.2 ± 1.9	1	4	78.2 ± 2.1	2	3	76.1 ± 2.0	4	4	78.2 ± 2.1	2	11	84.7 ± 1.8
breast (30)	1	90.9 ± 1.5	2	1	90.9 ± 1.5	2	2	95.2 ± 1.2	1	1	90.9 ± 1.5	2	2	95.2 ± 1.2
heart (13)	6	82.6 ± 3.0	1	1	55.0 ± 4.4	3	2	76.9 ± 3.8	2	1	55.0 ± 4.4	3	6	82.6 ± 3.0
spect (22)	17	80.2 ± 4.2	1	2	78.2 ± 3.2	3	1	79.6 ± 3.2	4	3	79.1 ± 3.2	2	11	81.4 ± 4.2
ionosphere (34)	18	84.7 ± 2.9	1	8	81.9 ± 3.5	2	1	76.4 ± 3.9	4	8	81.9 ± 3.5	2	33	85.3 ± 3.0
parkinsons (22)	13	83.7 ± 3.7	1	4	84.6 ± 3.2	2	1	77.0 ± 5.0	4	3	84.6 ± 3.4	3	9	86.0 ± 3.9
semeion (256)	53	85.5 ± 1.1	1	40	82.7 ± 1.4	2	4	49.6 ± 1.7	4	40	82.7 ± 1.4	2	73	93.3 ± 1.3
Lung (325)	9	76.1 ± 7.9	2	5	74.2 ± 7.7	3	1	46.5 ± 7.5	4	11	73.0 ± 7.1	1	41	84.3 ± 6.5
Lympth (4026)	8	86.0 ± 5.3	3	65	89.6 ± 5.5	1	2	62.8 ± 6.5	4	64	89.6 ± 5.5	2	70	90.7 ± 5.4
Madelon (500)	3	69.5 ± 1.6	2	1	52.4 ± 1.7	3	4	76.7 ± 1.5	1	1	52.4 ± 1.7	3	4	76.7 ± 1.5
average rank			1.5			2.3			3.2			2.2

. For each criterion, we reported the number of selected features and the average classification accuracy across 100 bootstrap runs. In each run, N bootstrap samples are drawn for the training set, while the unselected samples serve as the test set. Same as in Reference [8], we used the linear support vector machine (SVM) [32] as the baseline classifier. To give a reference, we defined the “optimal” number of features (an unknown parameter) as the one that yields the maximum bootstrap accuracy or first achieves a bootstrap accuracy with no statistical difference to the maximum value (evaluated by paired t-test with significance level $0.05$), and ranked all the criteria based on the difference between their estimated number of features and the optimal one.

As can be seen, $\Delta \mathrm{MI}$-${\chi }^2$ is likely to severely underestimate the number of features, accompanied by the lowest bootstrap accuracy. One possible reason is that $\mathbf{I}(x^{\mathrm{cand}};y|S^{\prime })$ does not precisely fit a ${\chi }^2$ distribution if the MB condition is not satisfied. CMI-permutation and MI-permutation always have the same ranks. This is because $\mathbf{I}(S^{\prime };y)+\mathbf{I}(\{S-S^{\prime }\};y|S^{\prime })=\mathbf{I}(S;y)$, a fixed value. Thus, it is equivalent to monitor the increment of $\mathbf{I}(S^{\prime };y)$ or the decrement of $\mathbf{I}(\{S-S^{\prime }\};y|S^{\prime })$. On the other hand, it is surprising to find that CMI-heuristic performs the best in most datasets. This indicates that although the permutation test is effective to test the MB condition, $\epsilon ={10}^{-4}$ is a reliable threshold to speed up this test, as the permutation test is always time-consuming. If we look deeper, it is also interesting to see that different values of $\alpha$ in Rényi’s entropy affect the results. This is to be expected, because the $\alpha$ is associated with the norm selected in the simplex to find the distance of the PDF to the center of the space. Effectively. different $\alpha$ weights change the effects of the tails, as explained in Reference [26]: Values of $\alpha$ smaller than 1 emphasize the importance of samples in the tails, values larger than 2 emphasize the modes of the distributions, whereas values close to 2 give equal weights to every sample, no matter where it is located in the distribution. Since classification uses a counting norm, values of $\alpha$ lower than 2 should be preferred. This is also the reason CMI-permutation and MI-permutation perform better with $\alpha =1.01$. Finally, the Wilcoxon rank-sum test at $0.1$ significance level, shown in

Table 3. Summary of p-values and decisions (in parentheses) of Wilcoxon rank-sum test at $0.1$ significance level on ranks of our criteria against $\Delta$MI-${\chi }^2$ and MI-permutation. A p-value smaller than $0.1$ indicates rejection of the null hypothesis that two criteria perform equally.

$\mathit{\alpha }=1.01$
	$\mathbf{\Delta }$MI-${\mathit{\chi }}^{\mathbf{2}}$	MI-Permutation
CMI-heuristic	0.0781 (1)	0.5455 (0)
CMI-permutation	0.0561 (1)	0.9036 (0)
$\mathit{\alpha }=\mathbf{2}$
	$\mathbf{\Delta }$MI-${\mathit{\chi }}^{\mathbf{2}}$	MI-Permutation
CMI-heuristic	0.0081 (1)	0.0341 (1)
CMI-permutation	0.0587 (1)	0.7340 (0)

, corroborates our analysis that our criteria perform equally to or slightly better than MI-permutation, but significantly better than $\Delta \mathrm{MI}$-${\chi }^2$.

4. Conclusions

This paper suggests two simple stopping criteria, namely, CMI-heuristic and CMI-permutation, for information theoretic feature selection by monitoring the value of CMI estimated with the novel multivariate matrix-based Rényi’s $\alpha$-entropy functional. Experiments on 10 benchmark datasets indicate that (1) CMI is a more tractable quantity than MI, and (2) the non-parametric test (like the permutation test) is more effective than the parametric test with a prior distribution (like the ${\chi }^2$ distribution), to guide early stopping in feature selection. Moreover, as an alternative to a permutation test, we also demonstrate a tiny threshold is sufficient to test the MB condition, which is very valuable for practitioners across different domains.

In the future, we will investigate the performance of our stopping criteria on big data. This is because with the tremendous growth of dataset sizes and dimensionality, the scalability of most feature selection methods could be jeopardized [33]. This problem is particularly important for our criteria, as the large-scale eigenvalue decomposition is always a challenging problem mathematically [34]. Moreover, we are also interested in testing our criteria on different types of data, including the linked data that is pervasive in social media and bioinformatics [33].