Do We Need to Observe Features to Perform Feature Selection?

Abstract

Many feature selection methods were developed in the past, but in the core, they all work the same way you pass a set of features to the algorithm and get a reduced set of the features. But can we perform a non-trivial feature selection without first observing the features? This is an important question because if we were actually able to predict feature importance before observing the features, we would reduce computation requirements of all stages of machine learning process beginning with feature engineering. In this article, we argue that it is possible to predict feature importance before feature vector observation. The trick is that we use meta-features about the features to perform the feature selection. We evaluate the concept on 15 relational databases. On average, it was enough to generate the top decile of all features to get the same model accuracy as if we generated all features and passed them to the model.

Keywords

• meta-learning
• feature engineering
• feature selection
• relational database
• propositionalization

-

Data in relational databases are in the form of many tables, but common classification algorithms require input data in the form of a single table. Propositionalization solves this discrepancy by converting data from the form of many tables into a single table.

But there are two significant problems with the propositionalization [ 3 ]. It produces a lot of features. And many of them are redundant. These two issues result in high computational requirements during both, propositionalization and classification.

Contrary to the common approach (e.g., [ 10 ], [ 7 ], [ 8 ]), we deal with these two issues by performing feature selection before the propositionalization and not after the propositionalization. The key idea is that we collect metadata about the attributes in the database (e.g., attribute data type), meta-data about the feature generative functions (e.g., id of the feature function), calculate landmarking features on a small subset of all features and pass their performance to a meta-learner, which predicts the optimal order, in which the remaining features should be calculated. 2.1

Meta-learning for Feature Engineering

Meta-learning was originally concerned with algorithm selection[21]. Nevertheless, Nargesian [ 16 ] trained a neural network to predict, which feature transformations are going to improve the accuracy of a classifier based on the feature histograms.

We extend the idea of using the data-based meta-features (in Nargesian’s case a histogram) for feature engineering with landmarking. 2.2

Meta-learning for Feature Selection

Reif [ 20 ] applies meta-learning to accelerate forward selection. The key concept is that the performance of all candidate feature subsets in each forward step is first estimated with a meta-learner. And only the top x percent of the candidates get evaluated on the data to get the true subset performance. Based on the reported results, it is sufficient to evaluate only the top 10% of all candidate subsets on the data to get results comparable to classical forward selection.

The difference between our approach and Reif’s approach is that Reif calculates meta-features from the features, while we calculate meta-features directly from the attributes that are used to calculate the features (in Figure 1 we use only the left table, while Reif uses the right table). Consequently, in Reif’s case, we have to calculate the features first, to perform feature selection. While in our case, we can perform the feature selection before feature calculation. 3

Method

A high-level schema of our approach is in Figure 2. The whole process is divided into two phases. During the offline phase, meta-features and feature performance are collected on many databases and passed to a meta-learner as training data. During the online phase, the trained meta-learner is used to rank candidate features in the descending order of their estimated utility. Following paragraphs define the feature utility.

There are many properties that a feature should posses [ 12 ], but we focus on predicting properties measurable directly from the data: relevance to the task, redundancy to other features and runtime of the feature calculation. function ( 1 i d 1 2 3 3 . . . . . . . . . . . . efatur + 4 3 space problem into a single-instance problem solvable with a common attribute value classifier. In this trivial example, the feature space contains only a single feature vector but it may generally contain thousands of feature vectors.

A numerical feature f1 is redundant to numerical feature f2 if a linear transformation from f1 to f2 and back exists.

We use this (weaker) definition of redundancy instead of the identity of the features because it corresponds better with the notion of redundancy in many models (e.g., in logistic regression with one shot encoding of categorical features). To speed up the identification of redundant features, we use Chi2 as a hash function to identify potential redundant features [19, Section 2.1]. 3.1

Feature Utility

We calculate features1 in descending order of the estimated relevance/runtime ratio [ 1 ] since we prefer to calculate highly relevant and fast features first. Furthermore, we penalize the feature i proportionally to the estimated probability that the feature is redundant pˆi. Because each dataset has a different proportion of redundant features (see Table 1) and the tested meta-learning models had difficulties to model these differences, we employ median thresholding instead of a fixed threshold: utilityi = (pˆi > median(pˆ) ? 1 − pˆi : 1) relevancei runtimei , (1) where redundancy is a vector of estimated redundancy probabilities for a database.

1In the production, we would calculate only the top n features that we would use to build a production classifier. But to demonstrate the meaningfulness of such approach, we calculate all features.

Experiment

Data

We used 15 databases listed in Table 1 from relational repository [ 15 ]. 4.2 For propositionalization, we used Relaggs [ 9 ], which was modified to work with 31 different feature (generative) functions, listed in Figure 2. The detail description of the employed feature functions is at http:// predictorfactory.com. We employ three sources of meta-features: landmarking features, database meta-data and feature function meta-data. Landmarking features Just like the accuracy of a few classifiers can be used as meta-features for the recommendation of the best classifier on the data (e.g., [ 18 ]), we define a subset of feature functions as landmarking feature functions for the recommendation of the best features.

Without loss of generality, we used following set of landmarking features: Direct field (a simple copy of the value), Aggregate (e.g., min, max,...), WOE (Weight of Evidence), Count (of tuples), Aggregate WOE, Time aggregate since. These feature functions were selected for their low runtime (see Table 11 in the appendix) and good coverage of different data types (numerical/character/temporal) and relationships between the label and the data (1:1/1:n). Note that we do not use multivariate feature functions for landmarking due to the potential combinatorial explosion. Database meta-data Basic descriptive and statistical metafeatures are frequently employed in meta-learning (e.g., [ 11 ]) and we do not differ in this respect. A noteworthy difference is that we do not calculate statistics of the attributes but rather reuse statistics maintained by the relational database for query plan optimization [ 14 ]. This slight deviation allows us to collect estimates of the statistics in time independent on the count of tuples (records) in the database.

Feature function meta-data Feature function meta-data consists of feature function name (e.g., Aggregate) and feature function parameters (e.g., min). 4.4

Measures

Anytime algorithm We formulate feature engineering as anytime algorithm [25], which aims to deliver the best subset of calculated features in any time. The quality of anytime algorithm can be expressed with a performance profile, where we measure quality of the solution at the given time (see example in Figure 3). To assign a single number to the performance profile, we calculate the area between the archived curve a(t) and the expected random curve r(t) (which we obtain from averaging the curve from many random permutations), divided by the area between the perfect curve p(t) and the expected random curve r(t):

R a(t)dt − R r(t)dt POP = R p(t)dt − R r(t)dt (2) where t is time. The obtained ratio then represents the “percentage of perfect” solution [ 2 ]. In our case, a(t), r(t) and p(t) are the Chi2 of the feature calculated at time t. The only difference between these functions is then the order, in which the features are calculated. The perfect feature ordering is based on a complete knowledge of relevance, redundancy and runtime of all the features. While archived ordering is based only on the estimates of these feature properties (the only exception are landmarking features, which are calculated in a pseudorandom order).

Mutagenesis, POP=0.595 100 80 e c an 60 v e le 40 R 20 0 0 10 20 30 Runtime [s]

Perfect Archived Random 95% PI Diagonal 40 Individual models To assess the ability of relevance and runtime prediction models to rank, we use Spearman correlation (ρ). The quality of redundancy estimation (a classification task) is evaluated with area under receiver operating characteristic curve (AUROC).

Permutation testing To assess, whether the obtained performance profiles are significantly better than random, we generate 1,000 random orderings of the features to estimate 95% prediction intervals. The obtained accuracies are depicted in Table 3. Since the difference between the models is not significant, we use GLM for all following experiments. 5.2

Feature Importance

Relevance The most important meta-features for feature relevance prediction is the average relevance of the landmarking features on individual attributes and the type of the employed feature function (see Table 4).

Redundancy There are two main sources of redundant features [ 10 ]: redundancy in the input data and redundancy introduced by the feature functions. The redundancy in the input data is covered by landmarking landmark_is_redundant and data_type. While the introduced redundancy is explained with feature_function and feature_parameters (see Table 5).

Runtime The runtime of a feature function calculation is a function of two factors: the type of the feature function and data property. Nevertheless, these two factors are dominated by the landmarking landmark_runtime (see Table 6). 5.3

Percentage of Perfect

The quality of anytime learning for all 15 datasets is reported in Table 7 in the penultimate column. 6 6.1

Discussion

What is the contribution of the individual models to POP?

To evaluate the contribution of the individual models to POP, we performed an experiment with a 2-level full factorial design for presence/absence of runtime, relevance and redundancy models (8 combinations in total) on all databases. To deal with the variability across databases (some are easier than others), we treat the database name as a random factor.

Conclusion: The result of the factor analysis is in Table 8. As expected, the intercept is not significantly different from zero, since POP measure should on average be 0 when we randomly rank the features. The biggest contributions to the accuracy are from redundancy and relevance prediction. The interaction between redundancy and relevance has a negative estimate because we do not reward calculation of redundant features even if they are highly relevant. Hence, prediction of the relevance helps only on the subset of unique features from the set of all candidate features. 6.2

What is the effect of meta-learning on model accuracy?

To evaluate the effectivity of the meta-learning, we iteratively train a classification model on increasing percentage of the top features, as estimated with meta-learning. As the classification model, we use a decision tree because it can model interactions between the features, it is undemanding on data preprocessing and it is reasonably fast. As the evaluation measure, we use misclassification error as all databases have reasonably balanced classes in the label.

An example of the obtained curve is depicted in Figure 4, where we can observe that the decision tree slightly overfits when we use all the features. Nevertheless, forward selection still outperforms meta-learning feature selection, as it can observe all the features (our approach does not) and it is a wrapper (our approach is a filter [ 5 ]).

Financial

Meta-learning (AUC=0.23) Random (AUC=0.33) All features

Forward selection 20

40 60 Percentage of used features 80 100

Conclusion: The result of the factor analysis is in Table 9. Prediction of relevance significantly reduces misclassification error. Prediction of runtime insignificantly increases the misclassification error, because this evaluation does not reward fast features. Redundancy prediction does not significantly decrease the classification error. Based on our inspection of the results, this is because this evaluation rewards early discovery of a few highly relevant features much higher (since the best possible decision tree may use just a few features) than it penalizes redundancy (a redunTo analyze the importance of the three categories of the meta-features (landmarking, database, feature-function), we design an experiment, in which we vary the set of the used meta-features.

Conclusion: Based on the results reported in Table 10, only landmarking meta-features help to significantly2 reduce the count of features that have to be engineered to reach model accuracy obtained on all features. Table 10 also tells us that if all meta-features are used, it is in average sufficient to engineer only the top 8.25% of the features to match or surpass the classification accuracy of the model trained on all features. features. Based on Wilcoxon signed-rank test, we have to reject the null hypothesis that the additional features do not improve accuracy (p-value = 0.00048). The median improvement is 1.2 percent point in classification accuracy (average improvement is 2.7 percent point).

Conclusion: The additional features improve the accuracy of the model over the accuracy of the model build only on the landmarking features by a small but significant amount. 6.5

Feature Selection vs. Feature Meta-learning

The described feature meta-learning bears similarity with filter-type feature selection methods likeCorrelated Feature Selection (CFS)[ 6 ] and Minimum Redundancy Maximum Relevance (mRMR)[ 17 ]. Both these methods attempt to quickly select relevant non-redundant features. And so does our method. But in comparison to these methods, we perform feature selection before the feature engineering. Difficulty It can be argued that feature meta-learning is at least as difficult problem as feature selection since we can always convert feature selection problem to feature meta-learning by throwing away the computed features (and recalculating them on request). 6.6

Limitations

We performed experiments only on relational data and features from propositionalization. Propositionalization is known to produce a lot of duplicate features (38% on average on the tested databases) and many of the features are irrelevant to the task (64% on average on the tested databases based on backward selection). These properties make it possible to obtain substantial gains from feature selection. However, the performed experiments do not tell us how the described approach is going to generalize on non-relational data.

Another limitation of the reported work is that it ignores interactions between the feature vectors in the downstream model. This can reduce the accuracy of the downstream model because a univariate oraculum meta-learner would not recommend calculation of features that are useful only in the combination with other features (a trivial example where this may happen is XOR problem [ 13 ]). Possible solutions to this problem are briefly mentioned in the future work Section 7. 6.7

Applications

Feature meta-learning is desirable in domains, where a single universal approach to feature extraction does not exist or is not known ahead. An exemplary domain are relational data, which may contain highly diverse content ranging from structured to unstructured data.

Additionally, feature selection before feature engineering is applicable to complex or large data, where it is not feasible or convenient to calculate and evaluate all possible features due to limited resources. 7

Conclusion

In this article, we evaluated an idea of performing feature selection before feature engineering. To guide the search, we exploited meta-learning. Nargesian [ 16 ] used meta-features calculated from the original data. But we found out that landmarking meta-features work better. When we evaluated the implementation on 15 databases, we concluded that it is on average enough to engineer only the top decile of features to get accuracy comparable to accuracy obtained on all features. This finding is similar to Reif’s [ 20 ] finding, who applied meta-learning to feature selection. However, Reif performs feature selection after feature engineering while we perform feature selection before feature engineering. 7.1

Future Work

In this exploratory work, we optimize an ersatz measure called POP, which is easy to reason about. One possible extension of this work is to improve individual components of the meta-learning model. For example, we can detect redundancy based on a fuzzy comparison of equal-height histograms estimated with the database engine or quantile sketch. With this change, we would detect duplicates that are identical up to a monotonic transformation, leading to better alignment with models that are invariant to monotonic transformations of the features (e.g., decision trees in theory). Or we could replace the redundancy detection with a precomputed correlation matrix describing similarities between the feature functions [24, p. 148]. Alternatively, we could estimate a transition matrix describing the optimal order in which to apply feature functions (or give up on the given attribute). To improve non-redundancy and relevance together, we could train a fast model (e.g., naive Bayes) on streaming features (e.g., [23] or [22, p. 19]). The possibilities are vast.

Another possible direction is to directly optimize the measure we are interested in (e.g., improvement to model’s AUROC over time). This can be done by training a single model (e.g., [ 16 ]). And this article provides an extended set of meta-features, on which such model could be trained. 8

Acknowledgement

We would like to thank Adéla Blažková for her help. We furthermore thank the anonymous reviewers, their comments helped to improve this paper. The reported research has been supported by the Grant Agency of the Czech Technical University in Prague (SGS17/210/OHK3/3T/18) and the Czech Science Foundation (GACˇ R 18-18080S).

Appendix

Reproducibility

The used code is published at:

https://github.com/janmotl/metalearning. The used databases are published at:

https://relational.fit.cvut.cz. Aggregate frame Time aggregate diff Time diff Time day part Time since Null ratio Time frequency Existential count Slope Time WOE Time is weekend Time part Text length Intercept Correlation Time aggregate Aggregate text length Aggregate range Duplicate ratio Aggregate distinct Time range Coefficient of variation Time aggregate since event Direct field Distinct count Aggregate Log product Time aggregate since Count WOE Aggregate WOE −2.11 −1.53 −0.92 −1.33 −0.89 −0.99 −0.17 −0.67 −0.49

0.51 −1.03 −0.45 −0.76 1.42 1.32 0.57 −0.24 0.34 0.32 0.56 0.06 0.36 0.19 0.26 0.21 0.49 0.62 1.25 0.30 1.27 1.04

References

[1] S. M. Abdulrahman and P. Brazdil . Measures for combining accuracy and time for meta-learning . CEUR Workshop Proc ., 1201 : 49 - 50 , 2014 .

[2] T. Brandenburger and A. Furth. Cumulative Gains Model Quality Metric . J. Appl. Math. Decis. Sci. , 2009 : 1 - 14 , 2009 .

[3] L. De Raedt . Inductive Logic Programming , volume 1446 of Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, 1998 .

[4] R. O. Duda , P. E. Hart , and D. G. Stork. Pattern Classification . Wiley Interscience, 2 edition , 2000 .

[5] I. Guyon , J. Weston , S. Barnhill , and V. Vapnik . An Introduction to Variable and Feature Selection Isabelle . Mach. Learn., 46 ( 1 /3): 389 - 422 , 2002 .

[6] M. A. Hall . Correlation-based Feature Selection for Machine Learning . PhD thesis , The University of Waikato, 1999 .

[7] J. M. Kanter . Deep Feature Synthesis: Towards Automating Data Science Endeavors . IEEE DSAA , 2015 .

[8] C. S. Kheau , R. Alfred , and L. H. Keng . Dimensionality Reduction in Data Summarization Approach to Learning Relational Data . ACIIDS, 7802 : 166 - 175 , 2013 .

[9] M.-A. Krogel and S. Wrobel . Transformation-Based Learning Using Multirelational Aggregation . In ILP , pages 142 - 155 . Springer, London, 2001 .

[10] M.-A. Krogel and S. Wrobel . Propositionalization and Redundancy Treatment . In Databases, Doc. Inf. Fusion, Hannover, 2002 . CEUR.

[11] C. Lemke , M. Budka , and B. Gabrys . Metalearning: a survey of trends and technologies . Artif. Intell., 44 ( 1 ): 117 - 130 , 2015 .

[12] A. McNab and D. A. Ladd . Information quality: The importance of context and trade-offs . In Proc. Annu. Hawaii Int. Conf. Syst. Sci. , pages 3525 - 3532 , 2014 .

[13] M. Minsky and S. A. Papert. Perceptrons. An Introduction to Computational Geometry . MIT, jan 1969 .

[14] J. Motl and P. Kordík . Foreign Key Constraint Identification in Relational Databases . In ITAT , pages 106 - 111 . CEUR, 2017 .

[15] J. Motl and O. Schulte . The CTU Prague Relational Learning Repository. arXiv, page 7 , nov 2015 .

[16] F. Nargesian , H. Samulowitz , U. Khurana , E. B. Khalil , and D. Turaga . Learning Feature Engineering for Classification . IJCAI, ( August ): 2529 - 2535 , 2017 .

[17] H. Peng , F. Long , and C. Ding . Feature selection based on mutual information criteria of max-dependency, maxrelevance, and min-redundancy . IEEE TPAMI , 27 ( 8 ): 1226 - 1238 , aug 2005 .

[18] B. Pfahringer , H. Bensusan , and C. Giraud-Carrier . MetaLearning by Landmarking Various Learning Algorithms . In ICML, volume 951 , pages 743 - 750 , 2000 .

[19] A. Popescul and L. H. Ungar . Structural Logistic Regression for Link Analysis . MRDM, ( August ): 92 - 106 , 2003 .

[20] M. Reif and F. Shafait . Efficient feature size reduction via predictive forward selection . Pattern Recognit ., 47 ( 4 ): 1664 - 1673 , 2014 .