Learning sparse optimal rule fit by safe screening
  In this paper, we consider linear prediction models in the form of a sparse
linear combination of rules, where a rule is an indicator function defined over
a hyperrectangle in the input space. Since the number of all possible rules
generated from the training dataset becomes extremely large, it has been
difficult to consider all of them when fitting a sparse model. In this paper,
we propose Safe Optimal Rule Fit (SORF) as an approach to resolve this problem,
which is formulated as a convex optimization problem with sparse
regularization. The proposed SORF method utilizes the fact that the set of all
possible rules can be represented as a tree. By extending a recently
popularized convex optimization technique called safe screening, we develop a
novel method for pruning the tree such that pruned nodes are guaranteed to be
irrelevant to the prediction model. This approach allows us to efficiently
learn a prediction model constructed from an exponentially large number of all
possible rules. We demonstrate the usefulness of the proposed method by
numerical experiments using several benchmark datasets.
