TL;DR
This paper introduces a novel method for automatically detecting feature interactions in machine learning datasets by evaluating the accuracy of learning algorithms on random subsets of features. By comparing observed accuracy to a Bayesian expectation, they identify synergistic feature combinations and demonstrate how these can be used to construct new, more informative features, leading to improved model performance.
What Problem Does This Paper Address?
Applying machine learning to real-world problems often hinges on effective feature representation. A significant challenge is "feature interaction," where the relevance of one feature to predicting the target class depends on the values of other features. This makes it difficult for standard algorithms, which often make greedy decisions based on individual features, to learn effectively. Traditional "wrapper" and "filter" methods for feature selection can struggle to uncover these complex dependencies. The paper aims to provide an automated way to identify these interactions and leverage them for feature engineering, a process that has historically relied heavily on domain expertise.
Methods
The core of the paper is a method for detecting feature interactions by evaluating learning algorithm performance on random feature subsets.
- Operational Definition of Interaction: An interaction is defined as a set of features where the observed accuracy of a learning algorithm (specifically, decision trees in this work) using all features in the set is higher than expected.
- Bayesian Expectation: To establish this "expected" accuracy, the authors employ a Bayesian analysis. They treat learners built on different feature subsets as independent components and combine their predictions probabilistically to estimate the expected accuracy of the combined set. This method accounts for the probabilities of misclassification from each component learner.
- Apical Interactions: To make the search more tractable, they focus on "apical interactions." This is an interaction where the most accurate single feature within a subset is crucial for the interaction to manifest. This simplifies the search by focusing on the top-performing features.
- Random Sampling for Search: Exhaustive search for interactions is computationally infeasible. The paper proposes sampling larger random subsets of features than the interaction order being sought. This increases the probability of encountering the interacting subset within the sampled larger set.
- Optimized Sampling Schedule: A key contribution is a method for organizing this random sampling to be fair and efficient within a limited time budget. This involves determining an optimal subset size and number of repetitions based on a parameter
gammathat controls the growth rate of sampled subset sizes. - Feature Construction: Once an interaction is detected, a new feature is constructed. This involves building a decision tree using the interacting features, pruning it, and then extracting a Disjunctive Normal Form (DNF) expression from the positive leaves. This DNF expression represents the discovered interaction and is used as a new feature.
Datasets
The authors evaluated their approach on three benchmark datasets from the UC Irvine repository:
- Congressional-voting (with the "physician-fee-freeze" feature removed)
- Census (a subset of 1000 examples)
- Heart-disease
Key Insights and Ideas
- Interactions as Non-Independence: The paper frames feature interactions as a manifestation of non-independence among features, which violates assumptions of simpler models like Naive Bayes but can be exploited by more complex ones.
- Random Sampling as a Scalable Solution: The core insight is that random sampling of larger feature subsets can efficiently uncover interactions that would be missed by exhaustive search, especially for higher-order interactions.
- Apical Interactions Simplify Search: Focusing on apical interactions significantly reduces the search space by leveraging the performance of the best individual features.
- Feature Construction as a Direct Benefit: The method doesn't just detect interactions; it actively uses them to create new features, directly improving the learning algorithm's performance.
- Time-Constrained Search Optimization: The development of a sampling schedule that balances search completeness with computational time is a crucial practical contribution.
Key Results
- The method successfully discovered feature interactions on the three benchmark datasets.
- Constructing new features from these detected interactions led to significant improvements in the accuracy of the C4.5 decision-tree algorithm.
- Voting database: Accuracy increased by up to 5.4% (Z=4.91, p<0.05) for one constructed feature.
- Census database: Accuracy increased by up to 3.7% (Z=2.50) for one constructed feature.
- Heart Disease database: Accuracy increased by up to 8.4% (Z=4.25) for one constructed feature.
- The proposed random sampling approach significantly reduces the computational cost compared to exhaustive search, allowing for effective interaction discovery within practical time limits. For example, searching for 4-way interactions among 20 features could be done in 4991 units of time with
gamma = 0.55, compared to 22,800 units for exhaustive search.
Limitations and Future Work
- Algorithm Dependency: The authors acknowledge that feature interactions are dependent on the learning algorithm being used. An interaction detected for decision trees might not be relevant for other algorithms like neural networks.
- Statistical Significance of Constructed Features: While paired T-tests were used to assess the significance of accuracy improvements from constructed features, the authors note that these can sometimes lead to high Type I errors and that more robust methods are being explored.
- Future Work: The paper suggests exploring more robust statistical tests for evaluating constructed features. The method could also be extended to other learning algorithms beyond decision trees. Further research into optimizing the sampling schedule and interaction detection for different types of interactions is also implied.
Summary updated