Datum-Wise Classification: A Sequential Approach to Sparsity

Introduction

Feature Selection is one of the main contemporary problems in Machine Learning and has been approached from many directions. One modern approach to feature selection in linear models consists in minimizing an $L_{0}$ regularized empirical risk. This particular risk encourages the model to have a good balance between a low classification error and high sparsity (where only a few features are used for classification). As the $L_{0}$ regularized problem is combinatorial, many approaches such as the LASSO try to address the combinatorial problem by using more practical norms such as $L_{1}$. These approaches have been developed with two main goals in mind: restricting the number of features for improving classification speed, and limiting the used features to the most useful to prevent overfitting. These classical approaches to sparsity aim at finding a sparse representation of the features space that is global to the entire dataset.

We propose a new approach to sparsity where the goal is to limit the number of features per datapoint, thus datum-wise sparse classification (DWSC). This means that our approach allows the choice of features used for classification to vary relative to each datapoint; data points that are easy to classify can be inferred on without looking at very many features, and more difficult datapoints can be classified using more features. The underlying motivation is that, while classical approaches balance between accuracy and sparsity at the dataset level, our approach optimizes this balance at the individual datum level, thus resulting in equivalent accuracy at higher overall sparsity. This kind of sparsity is interesting for several reasons: First, simpler explanations are always to be preferred as per Occam’s Razor. Second, in the knowledge extraction process, such datum-wise sparsity is able to provide unique information about the underlying structure of the data space. Typically, if a dataset is organized onto two different subspaces, the datum-wise sparsity principle will allows the model to automatically choose to classify using only the features of one or another of the subspace.

DWSC considers feature selection and classification as a single sequential decision process. The classifier iteratively chooses which features to use for classifying each particular datum. In this sequential decision process, datum-wise sparsity is obtained by introducing a penalizing reward when the agent chooses to incorporate an additional feature into the decision process. The model is learned using an algorithm inspired by Reinforcement Learning .

The contributions of the paper are threefold: (i.) We propose a new approach where classification is seen as a sequential process where one has to choose which features to use depending on the input being inferred upon. (ii.) This new approach results in a model that obtains good performance in terms of classification while maximizing datum-wise sparsity, i.e. the mean number of features used for classifying the whole dataset. It also naturally handles multi-class classification problems, solving them by using as few features as possible for all classes combined. (iii.) We perform a series of experiments on 14 different corpora and compare the model with those obtained by the LARS , and a $L_{1}$-regularized SVM, thus providing a qualitative study of the behaviour of our algorithm.

The paper is organized as follow: First, we define the notion of datum-wise sparse classifiers and explain the interest of such models in Section 2. We then describe our sequential approach to classification and detail the learning algorithm and the complexity of such an algorithm in Section 3. We describe how this approach can be extended to multi-class classification in Section 4. We detail experiments on 14 datasets, and also give a qualitative analysis of the behaviour of this model in Section 6. The related work is given in Section 7.

Datum-Wise Sparse Classifiers

where $\Delta$ is the loss associated to a prediction error.

This empirical risk minimization problem does not consider any prior assumption or constraint concerning the form of the solution and can result in overfitting models. Moreover, when facing a very large number of features, obtained solutions usually need to perform computations on all the features for classifying any input, thus negatively impacting the model’s classification speed. We propose a different risk minimization problem where we add a penalization term that encourages the obtained classifier to classify using on average as few features as possible. In comparison to classical $L_{0}$ or $L_{1}$ regularized approaches where the goal is to constraint the number of features used at the dataset level, our approach performs sparsity at the datum level, allowing the classifier to use different features when classifying different inputs. This results in a datum-wise sparse classifier that, when possible, only uses a few features for classifying easy inputs, and more features for classifying difficult or ambiguous ones.

We consider a different type of classifier function that, in addition to predicting a label $y$ given an input $\mathbf{x}$, also provides information about which features have been used for classification. Let us denote $\mathcal{Z}=\{0;1\}^{n}$. We define a datum-wise classification function $f$ of parameters $\theta$ as:

where $y$ is the predicted output and $\mathbf{z}$ is a $n$-dimensional vector $\mathbf{z}=(z^{1},...,z^{n})$, where $z^{i}=1$ implies that feature $i$ has been taken into consideration for computing label $y$ on datum $\mathbf{x}$. By convention, we denote the predicted label as $y_{\theta}(\mathbf{x})$ and the corresponding $\mathbf{z}$-vector as $z_{\theta}(\mathbf{x})$. Thus, if $z_{\theta}^{i}(\mathbf{x})=1$, feature $i$ has been used for classifying $\mathbf{x}$ into category $y_{\theta}(\mathbf{x})$.

This definition of data-wise classifiers has two main advantages: First, as we will see in the next section, because $f_{\theta}$ can explain its use of features with $z_{\theta}(\mathbf{x})$, we can add constraints on the features used for classification. This allows us to encourage datum-wise sparsity which we define below. Second, while this is not the main focus of our article, analysis of $z_{\theta}(\mathbf{x})$ gives a qualitative explanation of how the classification decision has been made, which we study in Section 6. Note that the way we define datum-wise classification is an extension to the usual definition of a classifier.

Datum-wise sparsity is obtained by adding a penalization term to the empirical loss defined in equation (1) that limits the average number of features used for classifying:

The term $\|z_{\theta}(\mathbf{x_{i}})\|_{0}$ is the $L_{0}$ norm The $L_{0}$ ’norm’ is not a proper norm, but we will refer to it as the $L_{0}$ norm in this paper, as is common in the sparsity community. of $z_{\theta}(\mathbf{x_{i}})$, i.e. the number of features selected for classifying $\mathbf{x_{i}}$, that is, the number of elements in $z_{\theta}(\mathbf{x_{i}})$ equal to 1. In the general case, the minimization of this new risk results in a classifier that on average selects only a few features for classifying, but may use a different set of features w.r.t to the input being classified. We consider this to be the crux of the DWSC model: the classifier takes each datum into consideration differently during the inference process.

Note that the optimization of the loss defined in equation (2) is a combinatorial problem that cannot be easily solved. In the next section of this paper, we propose an original way to deal with this problem, based on a Markov Decision Process.

Datum-Wise Sparse Sequential Classification

A set of states $\mathcal{X}\times\mathcal{Z}$, where state $(\mathbf{x},\mathbf{z})$ corresponds to the state where the agent is currently classifying datum $\mathbf{x}$ and has selected features specified by $\mathbf{z}$. The number of currently selected features is thus $\|\mathbf{z}\|_{0}$.

A set of actions $\mathcal{A}$ where $\mathcal{A}(\mathbf{x},\mathbf{z})$ denotes the set of possible actions in state $(\mathbf{x},\mathbf{z})$. We consider two types of actions:

$\mathcal{A}_{f}$ is the set of feature selection actions $\mathcal{A}_{f}=\{\mathbf{f_{1}},\ldots,\mathbf{f_{n}}\}$ such that, for $a\in\mathcal{A}_{f},a=\mathbf{f_{j}}$ corresponds to choosing feature $j$. Action $\mathbf{f_{j}}$ corresponds to a vector with only the $j^{\mbox{\scriptsize{}th}}$ element equal to 1, i.e. $\mathbf{f_{j}}=(0,\ldots,1,\ldots,0)$. Note that the set of possible feature selection actions on state $(\mathbf{x},\mathbf{z})$, denoted $\mathcal{A}_{f}(\mathbf{x},\mathbf{z})$, is equal to the subset of currently unselected features, i.e. $\mathcal{A}_{f}(\mathbf{x},\mathbf{z})=\{\mathbf{f_{j}},\text{ s.t. }z_{j}=0\}$.

$\mathcal{A}_{y}$ is the set of classification actions $\mathcal{A}_{y}=\mathcal{Y}$, that correspond to assigning a label to the current datum. Classification actions stop the sequential decision process.

A transition function defined only for feature selection actions (since classification actions are terminal):

where $\mathbf{z^{\prime}}$ is an updated version of $\mathbf{z}$ such that $\mathbf{z^{\prime}}=\mathbf{z}+\mathbf{f_{j}}$.

We define a parameterized policy $\pi_{\theta}$, which, for each state $(\mathbf{x},\mathbf{z})$, returns the best action as defined by a scoring function $s_{\theta}(\mathbf{x},\mathbf{z},a)$:

The policy $\pi_{\theta}$ decides which action to take by applying the scoring function to every action possible from state $(\mathbf{x},\mathbf{z})$ and greedily taking the highest scoring action. The scoring function reflects the overall quality of taking action $a$ in state $(\mathbf{x},\mathbf{z})$, which corresponds to the total reward obtained by taking action $a$ in $(\mathbf{x},\mathbf{z})$ and thereafter following policy $\pi_{\theta}$This corresponds to the classical Q-function in Reinforcement Learning.:

Here $(r_{\theta}^{t}\mid(\mathbf{x},\mathbf{z}),a)$ corresponds to the reward obtained at step $t$ while having started in state $(\mathbf{x},\mathbf{z})$ and followed the policy with parameterization $\theta$ for $t$ steps. Taking the sum of these rewards gives us the total reward from state $(\mathbf{x},\mathbf{z})$ until the end of the episode. Since the policy is deterministic, we may refer to a parameterized policy using simply $\theta$. Note that the optimal parameterization $\theta^{*}$ obtained after learning (see Sec. 3.3) is the parameterization that maximizes the expected reward in all state-action pairs of the process.

In practice, the initial state of such a process for an input $\mathbf{x}$ corresponds to an empty $\mathbf{z}$ vector where no feature has been selected. The policy $\theta$ sequentially picks, one by one, a set of features pertinent to the classification task, and then chooses to classify once enough features have been considered.

0.2 Reward

If $a$ corresponds to a feature selection action, then the reward is $-\lambda$.

If $a$ corresponds to a classification action i.e. $a=y$, we have:

In practice, we set $\lambda<<1$ to avoid situations where classifying incorrectly is a better decision than choosing multiple features.

1 Reward Maximization and Loss Minimization

As explained in section 2, our ultimate goal is to find the parameterization $\theta^{*}$ that minimizes the datum-wise empirical loss defined in equation (2). The training process for the MDP described above is the maximization of a reward function. Let us therefore show that maximizing the reward function is equivalent to minimizing the datum-wise empirical loss.

where $\pi_{\theta}(\mathbf{x_{i}},\mathbf{z}_{\theta}^{(t)})$ is the action taken at time $t$ by the policy $\pi_{\theta}$ for the training example $\mathbf{x_{i}}$.

Such an equivalence between risk minimization and reward maximization shows that the optimal classifier $\theta^{*}$ corresponds to the optimal policy in the MDP defined previously. This equivalence allows us to use classical MDP resolution algorithms in order to find the best classifier. We detail the learning procedure in Section 3.3.

2 Inference and Approximated Decision Processes

Due to the infinite number of possible inputs $\mathbf{x}$, the number of states is also infinite. Moreover, the reward function $r(\mathbf{x},\mathbf{z},a)$ is only known for the values of $\mathbf{x}$ that are in the training set and cannot be computed for any other input. For these two reasons, it is not possible to compute the score function for all state-action pairs in a tabular manner, and this function has to be approximated.

The scoring function that underlies the policy $s_{\theta}(\mathbf{x},\mathbf{z},a)$ is approximated with a linear model Although non-linear models such as neural networks may be used, we have chosen to restrict ourselves to a linear model to be able to properly compare performance with that of other state-of-the-art linear sparse models.:

and the policy defined by such a function consists in taking in state $(\mathbf{x},\mathbf{z})$ the action $a^{\prime}$ that maximizes the scoring function i.e $a^{\prime}=\operatorname*{argmax}_{a\in\mathcal{A}}\langle\Phi(\mathbf{x},\mathbf{z},a);\theta\rangle$.

Due to their infiniteness, the state-action pairs are represented in a feature space. We note $\Phi(\mathbf{x},\mathbf{z},a)$ the featurized representation of the $(\mathbf{x},\mathbf{z}),a$ state-action pair. Many definitions may be used for this feature representation, but we propose a simple projection: we restrict the representation of $\mathbf{x}$ to only the selected features. Let $\mu(\mathbf{x},\mathbf{z})$ be the restriction of $\mathbf{x}$ according to $\mathbf{z}$:

To be able to differentiate between an attribute of $\mathbf{x}$ that is not yet known, and an attribute that is simply equal to 0, we must keep the information present in $\mathbf{z}$. Let $\phi(\mathbf{x},\mathbf{z})=(\mathbf{z},\mu(\mathbf{x},\mathbf{z}))$ be the intermediate representation that corresponds to the concatenation of $\mathbf{x}$ with $\mathbf{z}$. Now we simply need to keep the information present in $a$ in a manner that allows each action to be easily distinguished by a linear classifier. To do this we use the block-vector trick which consists in projecting $\phi(\mathbf{x},\mathbf{z})$ into a higher dimensional space such that the position of $\phi(\mathbf{x},\mathbf{z})$ inside the global vector $\Phi(\mathbf{x},\mathbf{z},,a)$ is dependent on action $a$:

In $\Phi(\mathbf{x},\mathbf{z},a)$, the block $\phi(\mathbf{x},\mathbf{z})$ is at position $i_{a}\cdot|\phi(\mathbf{x},\mathbf{z})|$ where $i_{a}$ is the index of action $a$ in the set of all the possible actions. Thus, $\phi(\mathbf{x},\mathbf{z})$ is offset by an amount dependent on the action $a$.

3 Learning

The goal of the learning phase is to find an optimal policy parameterization $\theta^{*}$ which maximizes the expected reward, thus minimizing the datum-wise regularized loss defined in (2). As explained in Section 3.2, we cannot exhaustively explore the state space during training, and therefore we use a Monte-Carlo approach to sample example states from the learning space. We use the Approximate Policy Iteration (API) algorithm with rollouts . Sampling state-action pairs according to a previous policy $\pi_{\theta^{(t-1)}}$, API consists in iteratively learning a better policy $\pi_{\theta^{(t)}}$ by way of the Bellman equation. The API With Rollouts algorithm is composed of three main steps that are iteratively repeated:

The algorithm begins by sampling a set of random states: the $\mathbf{x}$ vector is sampled from a uniform distribution in the training set, and $\mathbf{z}$ is also sampled using a uniform binomial distribution.

For each state in the sampled state, the policy $\pi_{\theta^{(t-1)}}$ is used to compute the expected reward of choosing each possible action from that state. We now have a feature vector $\Phi(\mathbf{x},\mathbf{z},a)$ for each state-action pair in the sampled set, and the corresponding expected reward denoted $R_{\theta^{(t-1)}}(\mathbf{x},\mathbf{z},a)$.

The parameters $\theta^{(t)}$ of the new policy are then computed using classical linear regression on the set of states — $\Phi(\mathbf{x},\mathbf{z},a)$ — and corresponding expected rewards — $R_{\theta^{(t-1)}}(\mathbf{x},\mathbf{z},a)$ — obtained previously. The generalizing capacity of the classifier gives an estimated score to state-action pairs even if we have never visited them.

After a certain number of iterations, the parameterized policy converges to a final policy $\pi$ which is used for inference.

Preventing Overfitting in the Sequential Model

In section 3.0.1, we explain the process by which, at each step, we either choose a new feature or classify the current datum. This process is at the core of DWSC but can suffer from overfitting if the number of features is larger than the number of training examples. In such a case, DWSC would tend to learn to select the more specific features for each training example. In classical $L_{1}$ regularization models that are not datum-wise, the classifier must use the same set of features for classifying any data and thus overly specific features are not chosen because they usually appear in only a few training examples.

We propose a very simple variant of the general model that allows us to avoid overfitting. We still allow DWSC to choose how many features to use before classifying an input $x$, but we constrain it to choose the features in the same order for all the inputs. For that, we constrain the score of the feature selection actions to depend only on the vector $\mathbf{z}$ of the state $(\mathbf{x},\mathbf{z})$. An example of the effect of such a constraint is presented in Fig. 2. This constraint is handled in the following manner:

where $s_{\theta}(\mathbf{x},\mathbf{z},a)=s_{\theta}(\mathbf{z},a)$ implies that the score is computed using only the values of $\mathbf{z}$ and $a$ — $\mathbf{x}$ is ignored. This corresponds to having two different types of state-action feature vectors $\Phi$ depending on the type of action:

Although this constraint forces DWSC to choose the features in the same order, it will still automatically learn the best order in which to choose the features, and when to stop adding features and classify. However, it will avoid choosing very different features sets for classifying different inputs (the first features chosen will be common to all the inputs being classified) and thus avoid the overfitting problem.

Complexity Analysis

As explained in section 3.3, the learning method is based on Reinforcement Learning with Rollouts. Such an approach is expensive in term of computations because it needs — at each iteration of the algorithm — to simulate trajectories in the decision process, and then to learn the scoring function $s_{\theta}$ based on these trajectories. Without giving the details of the computation, the complexity of each iteration is $O(N_{s}\cdot(n^{2}+c))$, where $N_{s}$ is the number of states used for rollouts (which in practice is proportional to the number of training examples), $n$ is the number of features and $c$ is the number of possible categories. This implies a learning method which is quadratic w.r.t. the number of features; the proposed approach is not able to deal with problems with thousands of possible features. Breaking this complexity is an active research perspective with some leads.

Inference on an input $\mathbf{x}$ consists in sequentially choosing features, and then classifying $\mathbf{x}$. At step $t$, one has to perform $(n-t)+c$ linear computations in order to choose the best action, where $(n-t)+c$ is the number of possible actions when $t$ features have already been acquired. The inference complexity is thus $O(N_{f}\cdot(n+c))$, where $N_{f}$ is the mean number of features chosen by the system before classifying. In fact, due to the shape of the $\Phi$ function presented in Section 3.2 and the linear nature of $s_{\theta}$, the score of the actions can be efficiently incrementally computed at each step of the process by just adding the contribution of the newly added feature. The complexity is thus reduced to $O(n+c)$. Moreover, the constrained model which results in ordering the features, has a lower complexity of $O(c)$ because in that case, the model does not have to choose between the different remaining features, and has only the choice to classify or get the next feature w.r.t. to the learned order. If the learning complexity of our model is higher than baseline global linear methods, the inference speed is very close for the unconstrained model, and equivalent for the constrained one. In practice, most of the baseline methods choose a subset of variables in a couple seconds to a couple minutes, whereas our method takes from a dozen minutes to an hour, depending on the number of features and categories. In practice inference is indeed of the same speed, which is in our opinion the important factor.

Experiments

Experiments were run on 14 different datasets obtained from the LibSVM Websitehttp://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/. Ten of these datasets correspond to a binary classification task, four to a multi-class problem. The datasets are described in Table 1. For each dataset, we randomly sampled different training sets by taking from $5\%$ to $75\%$ of the examples as training examples, with the remaining examples being kept for testing. We performed experiments with three different models: L1-SVM was used as a baseline linear model with $L_{1}$ regularizationUsing LIBLINEAR .. LARS was used to obtain the optimal solution of the LASSO problem for all values of the regularization coefficient $\lambda$ at onceWe use the implementation from the authors of the LARS, available in R.. Datum-Wise Sequential Model (DWSM) was tested with the two versions presented above: (i) DWSM-Un is the original unconstrained model and (ii) DWSM-Con is the constrained model for preventing overfitting.

For the evaluation, we used a classical accuracy measure which corresponds to $1-\textit{error rate}$ on the test set of each dataset. We perform 3 training/testing set splits of a given dataset to obtain averaged figures. The sparsity has been measured as the proportion of features not used for $L_{1}$-SVM and LARS in binary classification, and the mean proportion of features not used to classify testing examples in DWSM. For multi-class problems where one LARS/SVM model is learned for each category, the sparsity is the proportion of features that have not been used in any of the models.

For the sequential experiments, the number of rollout states (step 1 of the learning algorithm) has been set to 2,000 and the number of policy iterations has been fixed to 10. Note that experiments with more rollout states and/or more iterations give similar results. Experiments were made using an alpha mixture policy with $\alpha=0.9$ to ensure the stability of the learning process. We tested the different models with different values of $\lambda$ which controls the sparsity. Note that even with a $\lambda=0$ value, contrary to the baseline models, the DWSM model does not use all of the features for classification.

For each corpus and each training size, we have computed sparsity/accuracy curves showing the performance of the different models w.r.t. to the sparsity of the solution. Only two representative curves are given in Figure 3. To summarize the performances over all the datasets, we give the accuracy of the different models for three levels of sparsity in tables 2 and 3. Due to a lack of space, these tables do not present the LARS’ performance, which are equivalent to the performances of the $L_{1}$-SVM. Note that in order to obtain the accuracy for a given level of sparsity, we have computed a linear interpolation on the different curves obtained for each corpus and each training size. This linear interpolation allows us to compare the baseline sparsity methods — that choose a fixed number of features — with the average number of features chosen by DWSC. This compares the average amount of information considered by each classifier. We believe this approach still provides a good appreciation of the algorithm’s capacities.

Table 2 shows that, for a sparsity level of 80%, the DWSM-Un and the DWSM-Con models outperform the baseline $L_{1}$-SVM classifier. This is particularly true for 7 of the 10 datasets while the results are more ambiguous on the three others datasets: breast, ionosphere and sonar. For a sparsity of 40%, similar results are obtained. Depending on the corpus and the training size, different configurations are observed. Some datasets can be easily classified using only a few features, such as australian for example. In that case, our approach gives similar results in comparison to $L_{1}$ methods (see Figure 3–left). For some other datasets, our method clearly outperforms baseline methods (Figure 3–right). On the splice dataset, our model is better than the best (non-sparse) SVM using only less than 20% of the features on average. This is due to the fact that our sequential process, which solves a different classification problem, is more appropriate for some particular datasets, particularly when the distribution of the data is split up amongst distinct subspaces. In this case, our model is able to choose more appropriate features for each input.

When using small training sets with some datasets — sonar or ionosphere — where overfitting is observed (accuracy decreases with more features used), the DWSM-Con seems to be a better choice than the unconstrained version and thus is a version of the algorithm that is well-suited when the number of learning examples is small.

Concerning the multi-class problems, similar effects can be observed (see Table 3). The model seems particularly interesting when the number of categories is high, as in segment and vowel. This is due to the fact that the average sparsity is optimized by the sequential model for the multi-class problem while $L_{1}$-SVM and LARS, which need to learn one model for each category, perform separate sparsity optimizations for each class.

Figure 4 gives some qualitative results. First, from the left histogram, one can see that some features are used in 100% of the decisions. This illustrates the ability of the model to detect important features that must be used for decision. Note that many of these features are also used by the $L_{1}$-SVM and the LARS models. The sparsity gain in comparison to the baseline model is obtained through the features 1 and 9 that are only used in about 20% of decisions. From the right histogram, one can see that the DWSM model mainly classifies using 1, 2, 3 or 10 features, showing that the model is able to adapt its behaviour to the difficulty of classifying a particular input. This is confirmed by the green and violet histograms that show that for incorrect decisions (i.e. very difficult inputs) the classifier almost always acquires all the features before classifying. These difficult inputs seem to have been identified, but the set of features is not sufficient for a good understanding. This behaviour opens appealing research directions concerning the acquisition and creation of new features (see Section 8).

Related Work

Our sequential decision problem defines both feature selection and classification tasks. In this sense, our approach resembles an embedded approach. In practice, however, the final classifier for each single datapoint remains a separate entity, a sort of black-box classifying machine upon which performance is evaluated. Additionally, the learning algorithm is free to navigate over the entire combinatorial feature space. In this sense our approach resembles a wrapper method.

There has been some work using similar formalisms , but with different goals and lacking in experimental results. Sequential decision approaches have been used for cost-sensitive classification with similar models . There have also been applications of Reinforcement Learning to optimize anytime classification . We have previously looked at using Reinforcement Learning for finding a stopping point in feature quantity during text classification .

Finally, in some sense, DWSC has some similarity with decision trees as each new datapoint that is labeled is following a different path in the feature space. However, the underlying mechanism is quite different both in term of inference procedure and learning criterion. There has been some work in using RL for generating decision trees , but that approach is still tied to decision tree construction heuristics and the end product remains a decision tree.

Conclusion

In this article we introduced the concept of datum-wise classification, where we learn both a classifier and a sparse representation of the data that is adaptive to each new datum being classified. We took an approach to sparsity that considers the combinatorial space of features, and proposed a sequential algorithm inspired by Reinforcement Learning to solve this problem. We showed that finding an optimal policy for our Reinforcement Learning problem is equivalent to minimizing the $L_{0}$ regularized loss of our classification problem. Additionally we showed that our model works naturally on multi-class problems, and is easily extended to avoid overfitting on datasets where the number of features is larger than the number of examples. Experimental results on 14 datasets showed that our approach is indeed able to increase sparsity while maintaining equivalent classification accuracy.

References