Timezone: »

Learning Interpretable Decision Rule Sets: A Submodular Optimization Approach
Fan Yang · Kai He · Linxiao Yang · Hongxia Du · Jingbang Yang · Bo Yang · Liang Sun


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.

Author Information

Fan Yang (DAMO Academy, Alibaba Group)
Kai He (Alibaba Group)
Linxiao Yang (University of Electronic Science and Technology of China, Tsinghua University)
Hongxia Du (Alibaba Group)
Jingbang Yang (Tongji University)
Bo Yang (Renmin University of China)
Liang Sun (Alibaba Group)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors