Safe RuleFit: Learning Optimal Sparse Rule Model by Meta Safe Screening
This work addresses the computational bottleneck in selecting optimal rule sets for sparse rule models, which is incremental as it extends existing safe screening techniques to handle multiple features.
The authors tackled the problem of learning optimal sparse rule models, which was computationally intractable due to the large number of possible rules, by proposing Safe RuleFit (SRF) with meta safe screening (mSS) to efficiently screen out multiple features, resulting in improved computational efficiency as demonstrated in numerical experiments.
We consider the problem of learning a sparse rule model, a prediction model in the form of a sparse linear combination of rules, where a rule is an indicator function defined over a hyper-rectangle in the input space. Since the number of all possible such rules is extremely large, it has been computationally intractable to select the optimal set of active rules. In this paper, to solve this difficulty for learning the optimal sparse rule model, we propose Safe RuleFit (SRF). Our basic idea is to develop meta safe screening (mSS), which is a non-trivial extension of well-known safe screening (SS) techniques. While SS is used for screening out one feature, mSS can be used for screening out multiple features by exploiting the inclusion-relations of hyper-rectangles in the input space. SRF provides a general framework for fitting sparse rule models for regression and classification, and it can be extended to handle more general sparse regularizations such as group regularization. We demonstrate the advantages of SRF through intensive numerical experiments.