Motivated by clinical tasks where acquiring certain features such as FMRI or blood tests can be expensive, we address the problem of test-time elicitation of features. We formulate the problem of costaware feature elicitation as an optimization problem with trade-of between performance and feature acquisition cost. Our experiments on three real-world medical tasks demonstrate the eficacy and efectiveness of our proposed approach in minimizing costs and maximizing performance.
• Supervised learning → Budgeted learning; Feature selection; • Applications → Healthcare.
cost sensitive learning, supervised learning, classification
In supervised classification setting, every instance has a fixed
feature vector and a discriminative function is learnt on such
fixedlength feature vector and it’s corresponding class variable. However,
a lot of practical problems like healthcare, network domains,
designing survey questionnaire [
Our problem is motivated by such a cost-aware setting where the assumption is that prediction time features have an acquisition cost and adheres to a strict budget. Consider a patient visiting a doctor for some potential diagnosis of a disease. For such a patient, information like age, gender, ethnicity and other demographic features are easily available at zero cost. However, various lab tests that the patient needs to undergo incurs cost. So, a training model should be able to identify the most relevant (i.e. those which are most informative, yet least costly) lab tests that are required for each specific patient. The intuition of this work is that diferent patients, depending on their history, ethnicity, age and gender, may require diferent tests for reasonably accurate prediction. We build on the intuition that given certain observed features like one’s demographic details, the most important features for a patient depends on the important features for similar patients. Based on this intuition, we find out similar data points in the observed feature space and identify the important feature subsets of these similar instances by employing a greedy information theoretic feature selector objective.
Our contributions in this work are as follows: (1) formalize the problem as a joint optimization problem of selecting the best feature subset for similar data points and optimizing the loss function using the important feature subsets. (2) account for acquisition cost in both the feature selector objective and classifier objective to balance the trade-of between acquisition cost and model performance. (3) empirically demonstrate the efectiveness of the proposed approach on three real-world medical data sets. 2
The related work on cost-sensitive feature selection and learning
can be categorized into the following four broad approaches.
Tree based budgeted learning: Prediction time elicitation of
features under a cost budget has been widely studied in literature. A
lot of work has been done in tree based models [
Adaptive classification and dynamic feature discovery: Our
work also draws inspiration from Nan al.’s work [
Feature elicitation using Reinforcement learning: There is
another line of work along the sequential decision making
literature [
Active Feature Acquisition: Our problem set-up is also inspired
by work along active feature acquisition [
Our contributions: Although the problem of prediction time feature elicitation has been explored in literature from various directions and with various assumptions, we come up with an intuitive solution to this problem and formulate the problem in a two step optimization framework. We incorporate acquisition cost in both the feature selector and model objectives to balance the performance and cost trade-of. The problem set up is naturally applicable in real world health care and other domains where the knowledge of the observed features also needs to be accounted while selecting the elicitable features . 3 3.1
Given: A dataset {(1, 1), · · ·, (, )} with each ∈ R as the feature set. Each feature has an associated cost .
Objective: Learn a discriminative model which is aware of the feature costs and can balance the trade-of between feature acquisition cost and model performance.
We make an additional assumption here that there is a subset of features which have 0 cost. These could be, for example, demographic information (e.g. age, gender, etc) in a medical domain which are easily available/less cumbersome to obtain as compared to other features. In other words, we can partition the feature set F = O ∪ E where O are the zero cost observed features and E are the elicitable features which can be acquired at a cost. We also assume that the training data is completely available with all features (i.e. the cost for all the features has already been paid). The goal is to use these observed features to find similar instances in the training set and identify the important feature subsets for each of these clusters based on a feature selector objective function which balances the trade-of between choosing the important features and the cost at which these features are acquired. 3.2
As a first step, we cluster the training instances based on just the observed zero cost feature set O. The intuition is that instances with similar features will also have similar characteristics in terms of which elicitable features to order. For example, in a medical application, whether to request for a blood test or a ct-scan will depend on factors such as age, gender, ethnicity and whether patients with similar demographic features had requested these tests. Also, since the feature set O, comes at zero cost, we assume that for unseen test instances, this feature set is observed.
We propose a model which consists of a parameterized feature selector module ( , E , ) which takes in a set of input instances belonging to the cluster based on the feature set O and produces a subset of most important features for the classification task. The feature selection model is based on an information- theoretic objective function and is augmented with the feature cost to account for the trade of between model performance and acquisition cost at test-time. The output feature subset from the feature selector module are used to update the parameters of the classifier. The optimization framework is shown in Figure 1
selector module selects the best subset of features for each cluster
of training data based on an information theoretic objective score.
Since at test time, we do not know the elicitable feature subset E
(since the goal of feature selection is in the first place to find the
truly necessary features for learning). Hence we propose to use the
closest set of instances in the training data to the current instance.
Since we assume that the training data has already been elicited,
we have all the features observed in the training data. We compute
this distance just based on the observed feature set O. We cluster
the training data based on the observed features into m clusters
1, 2, · · · . Next, we use the Minimum-Redundancy-Maximum
Relevance (MRMR) feature Selection paradigm [
| Õ
E ∈ − Õ
©2 E ∈ « |
4 − | Õ
(E ) E ∈
{z cost penalty } Õ
(E ; ) E ∈
{z max. relevance } 3 (E ; E ) −
{z
min. redundancy
Õ
E ∈
(E ; E | )ª®
¬
}
(1)
where (E ; ) is the mutual information between the random
variable E (feature) and (target). In the above equation, the feature
subset is grown greedily using a greedy optimization strategy
maximizing the above objective function. In equation 1, E denotes
a single feature from the elicitable set E that is considered for
evaluation based on the subset grown so far. The first term is the
mutual information between each feature and the class variable .
In a discriminative task, this value should be maximized. The
second term is the pairwise mutual information between each feature
to be evaluated and the features already added to the feature subset
. This value needs to be minimized for selecting informative
features. The third term is called the conditional redundancy [
In the problem setup, since the 0 cost feature subset is always present, we always consider the observed feature subset O in addition to the most important feature subset as returned by the Feature selector objective. We also account for the knowledge of the observed features while growing the informative feature subset through greedy optimization. Specifically, while calculating the pairwise mutual information between the features and the conditional redundancy term (second and third term of equation 1), we also evaluate the mutual information of the features with these observed features. It is to be noted that in cases where the observed features are not discriminative enough of the target, the feature selector module ensures that the elicitable features with maximum relevance to the target variable are picked.
Optimization Problem: The cost aware feature selector ( , E , ) for a given set of instance E belonging to a specific cluster solves the following optimization problem:
= argmax ⊆ E ( , E , )
For a given instance (, ), we denote (, , , ) as the loss function using a subset of the features as obtained from the Feature selector optimization problem. The optimization problem for learning the parameters of a classifier can be posed as: min Õ (, , , ) + 1 ( ) + 2 || ||2 =1 the cluster to which a set of instances belong and is defined as: where 1 and 2 are hyper-parameters. In the above equation, is the parameter of the model and can be updated by standard gradient based techniques. This loss function takes into account the important feature subset for each cluster and updates the parameter accordingly. The classifier objective also consists of a cost term denoted by ( ) to account for the cost of the selected feature subset. For hard budget on the elicited features, the cost component in the model objective can be considered. In case of a cost budget, this component can be ignored because the elicited feature subset adheres to a fixed cost and hence, this term is constant. 3.3
(CAFE) in Algorithm 1. CAFE takes as input set of training examples E, the zero cost feature set O, the elicitable feature subset E, a cost vector ∈ R and a budget . Each element in the training set E consists of a tuple (, ) where ∈ R is the feature vector and y is the label.
The training instances E are clustered based on just the observed feature set O using K-means clustering (Cluster). For every cluster , the training instances belonging to the cluster is assigned to the set E and is passed to the Feature Selector module (lines 6-8). The FeatureSelector function takes E , parameter , the feature subsets O and E, cost vector and a predefined budget as input and returns the most important feature subset X corresponding to a cluster . A greedy optimization technique is used to grow the feature subset of every cluster based on the feature selector objective function defined in Equation 1. The FeatureSelector terminates once the budget is exhausted or the mutual information score becomes negative. Once all the important feature subsets are obtained for all the | | clusters, the model objective function is optimized as mentioned in Equation 3 for all the training instances using the important feature subsets for the clusters to which the training instances belong (lines 12-18). All the remaining features are imputed by using either 0 or any other imputation model before training the model. The final training model G(EO∪ , , ) is an unified model used to make predictions for a test-instance consisting of just the observed feature subset O. 4
We did experiments with 3 real world medical data sets. The intuition of CAFE makes more sense in medical domains, hence our choice of data sets. However, the idea can be applied to other domains ranging from logistics to resource allocation task. Table 2 jots down the various features of the data sets used in our experiments. Below are the details of the 3 real data sets, we use for our experiments. (2) (3)
Marker Initiative (PPMI) [
X = {∅} ⊲ Stores best feature subsets of each cluster for = 1 to | | do ⊲ Repeat for every cluster E = GetClusterMember(E, , )
⊲ get the data points belonging to each cluster X = FeatureSelector(E , , O, E, , ) ⊲ Parameterized feature selector for each cluster
X = X ∪ {X ∪ O} end for for = 1 to | | do ⊲ Repeat for every cluster X = GetFeatureSubset(X, )
⊲ Get the feature subset for each cluster for = 1 to |E | do ⊲ Repeat for every data point in cluster 16: Optimize ( , , X , , ) 17: ⊲ Optimize the objective function in Equation 3 18: Update ⊲ Update the model parameter 19: end for 20: end for
return G(EO∪ , , ) ⊲ G is the training model built on E
21: end function
2. Alzheimer’s disease prediction: The Alzheimer’s Disease
NeuroIntiative (ADNI1) is a study that aims to test whether various
clinical, FMRI and biomarkers can be used to predict the early onset
of Alzheimer’s disease. In this data set, we consider the
demographics of the patients as observed and zero cost features and the FMRI
image data and cognitive score data as unobserved and elicitable
features.
3. Rare disease prediction This data set is created from survey
questionnaires [
Evaluation Methodology: All the data sets were partitioned
into a 80:20 train-test split. Hyper parameters like the number of
clusters on the observed features were picked by doing 5 fold cross
validation on all the data sets. The optimal number of clusters
picked were 6 for ADNI, 9 for Rare disease data set and 7 for the
PPMI data set. For the results reported in Table 1, we considered a
hard budget on the number of elicitable features and set it to half
of the total number of features in the respective data set. We use
Kmeans clustering as the underlying clustering algorithm. For all the
reported results, we use an underlying Support Vector Machine [
Baselines: We consider 3 baselines for evaluating CAFE and CAFE-I: (1) using the observed and zero cost features to update the training model denoted as OBS (2) using a random subset of ifxed number of elicitable features and all the observed features to update the training model denoted as RANDOM. For this baseline, the results are averaged over 10 runs. (3) using the information theoretic feature selector score as defined in Equation 1 to select the ’k’ best elicitable features on the entire data without any cluster consideration along with the observed features denoted as KBEST. We keep the value of ’k’ to be the same as that used by CAFE. Although some of the existing methods could be potential baselines, none of these methods match the exact setting of our problem, hence we do not compare our method against them.
Results: We aim to answer the following questions: Q1: How does CAFE and CAFE-I with hard budget on features compare against the standard baselines? Q2: How does the cost-sensitive version of CAFE and CAFE-I fare against the cost-sensitive baseline KBEST?
The results reported in Table 1 suggests both CAFE and CAFEI significantly outperform the other baselines in almost all the metrics for Rare disease and PPMI data set. For ADNI, CAFE and CAFE-I outperform the other baselines in clinically relevant recall metric while KBEST performs the best for the other metrics. The reason for this is that in ADNI, since, the elicitable features are image features and we discretize the image features to calculate the information gain for the feature selector module, the granular level feature information is lost because of this discretization and hence the drop in performance. For the experiments in Table 1, we keep the budget to be approximately half of the total number Rare disease of features for all the methods. On an average, CAFE-I performs better than CAFE across all the data sets because of the underlying imputation model which helps in better treatment of the missing values as against replacing all the features by 0. This answers Q1 afirmatively.
In Figure 3, we compare the cost version of CAFE and CAFE-I against KBEST. Cost version takes into account the cost of individual features and accounts for them as penalty in the feature selector module. Hence, in this version of CAFE, a cost budget is used as opposed to hard budget on the number of elicitable features. We generate the cost vector by sampling each cost component uniformly from (0,1). For PPMI and Rare disease, we can see that cost sensitive CAFE performs consistently better than KBEST with increasing cost budget. In the PPMI data set, the greedy optimization of the feature selector objective on the entire data set lead to elicitation of just 1 feature, beyond that the information gain was negative, hence the performance of PPMI across various cross budget remains the same. CAFE on the other hand was able to select important feature subsets for various clusters based on the observed features related to gait and postures. For ADNI data set, CAFE performs better than KBEST only in recall. The reason for this is the same as mentioned above. This helps in answering Q2 afirmatively.
Lastly, Figure 2 shows the efect of increasing cluster on the validation recall for the Rare disease data set. As can be seen, for smaller number of clusters, the recall is very low and increases to an optimum for 9 clusters. This helps us in understanding the fact that forming clusters based on observed important features helps CAFE in selecting diferent feature subsets for diferent clusters, thus helping the learning procedure.
In this paper, we pose the prediction time feature elicitation problem as an optimization problem by employing a cluster specific feature selector to choose the best feature subset and then optimizing the training loss. We show the efectiveness of our approach in real data sets where the problem set up is intuitive. Future work includes learning the parameters of the feature selector module and jointly optimizing the feature selector and model parameters for a more robust framework and adding more constraints to optimization.
SN & SD gratefully acknowledge the support of NSF grant IIS1836565. Any opinions, findings and conclusion or recommendations are those of the authors and do not necessarily reflect the view of the US government.