  Rule sets are highly interpretable logical models in which the predicates for
decision are expressed in disjunctive normal form (DNF, OR-of-ANDs), or,
equivalently, the overall model comprises an unordered collection of if-then
decision rules. In this paper, we consider a submodular optimization based
approach for learning rule sets. The learning problem is framed as a subset
selection task in which a subset of all possible rules needs to be selected to
form an accurate and interpretable rule set. We employ an objective function
that exhibits submodularity and thus is amenable to submodular optimization
techniques. To overcome the difficulty arose from dealing with the
exponential-sized ground set of rules, the subproblem of searching a rule is
casted as another subset selection task that asks for a subset of features. We
show it is possible to write the induced objective function for the subproblem
as a difference of two submodular (DS) functions to make it approximately
solvable by DS optimization algorithms. Overall, the proposed approach is
simple, scalable, and likely to be benefited from further research on
submodular optimization. Experiments on real datasets demonstrate the
effectiveness of our method.
