  This paper considers generalized linear models using rule-based features,
also referred to as rule ensembles, for regression and probabilistic
classification. Rules facilitate model interpretation while also capturing
nonlinear dependences and interactions. Our problem formulation accordingly
trades off rule set complexity and prediction accuracy. Column generation is
used to optimize over an exponentially large space of rules without
pre-generating a large subset of candidates or greedily boosting rules one by
one. The column generation subproblem is solved using either integer
programming or a heuristic optimizing the same objective. In experiments
involving logistic and linear regression, the proposed methods obtain better
accuracy-complexity trade-offs than existing rule ensemble algorithms. At one
end of the trade-off, the methods are competitive with less interpretable
benchmark models.
