Abstract
In machine learning, feature engineering—specifically the creation of feature crosses—is a critical step for enhancing the predictive power of linear models. However, identifying the optimal set of features to cross is a combinatorial problem of immense complexity. This paper provides a rigorous theoretical analysis of the feature cross search problem. We demonstrate that while the general search problem is NP-hard and difficult to approximate, it becomes a monotone submodular optimization problem under the Naïve Bayes assumption. This allows for a greedy search strategy with a guaranteed $(1 - 1/e)$-approximation ratio, providing a theoretical foundation for common industry heuristics.
Introduction
Linear models remain a cornerstone of industrial machine learning due to their scalability, interpretability, and efficiency. Despite these strengths, they are inherently limited by their inability to capture non-linear interactions between features. To overcome this, practitioners often use feature crosses: the combination of two or more categorical features (e.g., Country and Language) into a single joint feature.
While effective, the search space for these crosses is vast. For a dataset with $n$ features, selecting $k$ features to cross results in $\binom{n}{k}$ possibilities. Evaluating every combination is computationally prohibitive. This research addresses the fundamental question: Is there an efficient, principled way to find the optimal feature cross?
The Complexity of Feature Crossing
The authors first establish the inherent difficulty of the problem. By utilizing a reduction from the $k$-densest subgraph problem, they prove that the general feature cross search problem is not only NP-hard but also extremely difficult to approximate. Specifically, no polynomial-time algorithm can provide a high-quality approximation ratio unless the Exponential Time Hypothesis is false. This result formally justifies why exhaustive search is impractical for large-scale feature engineering.
A Tractable Path: The Naïve Bayes Assumption
To find a mathematically tractable solution, the researchers adopt the Naïve Bayes assumption, which posits that features are conditionally independent given the class label. While this assumption is rarely perfectly met in real-world data, empirical evidence from domains like NLP (e.g., Reuters-21578, Newsgroup) and software defect prediction suggests it is often a robust approximation for feature selection tasks.
Submodularity and the Greedy Guarantee
The core technical breakthrough of the paper is proving that, under the Naïve Bayes assumption, the maximum Area Under the Curve (AUC) is a monotone submodular function. Submodularity is a property of set functions characterized by "diminishing returns": adding an element to a smaller set provides a greater or equal marginal gain than adding it to a larger set.
This property is transformative for the search problem. For monotone submodular functions, a simple greedy algorithm—which iteratively selects the single best feature to add to the cross—is guaranteed to achieve a solution that is at least $(1 - 1/e) \approx 63\%$ of the global optimum. This provides the first rigorous theoretical justification for the greedy heuristics used in production systems like Google’s Autocross.
Mathematical Foundations
The proof of submodularity involves sophisticated mathematical tools from harmonic analysis and probability theory:
- AUC as Geometric Distance: The authors characterize the AUC as the total variation distance between two product measures. This shifts the problem from a discrete search to a geometric analysis of probability distributions.
- Harmonic Analysis: By applying Bochner’s theorem and Fourier transforms, the authors prove the positive semi-definiteness of a specific kernel matrix. This step is crucial in establishing the submodular nature of the objective function.
- The Commutator Concept: They introduce a "signed measure" (the difference between two probability distributions) to represent the information gain achieved by crossing features.
Discussion and Limitations
While the $(1 - 1/e)$ guarantee is a significant theoretical milestone, it relies on the conditional independence of features. In datasets where features are highly redundant (e.g., Zip Code and City), the submodularity property may weaken, potentially impacting the greedy algorithm's performance. Furthermore, this work focuses on optimizing a single feature cross; extending these guarantees to the simultaneous selection of multiple distinct crosses remains an open area for future research.
Conclusion
"Feature Cross Search via Submodular Optimization" bridges the gap between empirical feature engineering and theoretical computer science. By proving that feature cross selection is submodular under specific conditions, the authors provide a mathematical safety net for practitioners, ensuring that greedy search strategies are not just intuitive, but theoretically sound.
Summary updated