Yanjun Han, Institute of Automation, Chinese Academy of Sciences, China
Jue Wang, Institute of Automation, Chinese Academy of Sciences, China

Links

Session:
Springer Link:

Abstract

In this paper $\ell_{1}$ regularization is introduced into relational learning to produce sparse rule combination. In other words, as few as possible rules are contained in the final rule set. Furthermore, we design a rule complexity penalty to encourage rules with fewer literals. The resulted optimization problem has to be formulated in an infinite dimensional space of horn clauses $R_m$ associated with their corresponding complexity $\mathcal{C}_m$. It is proved that if a locally optimal rule is generated at each iteration, the final obtained rule set will be globally optimal. The proposed meta-algorithm is applicable to any single rule generator. We bring forward two algorithms, namely, $\ell_1$FOIL and $\ell_1$Progol. Empirical analysis is carried on ten real world tasks from bioinformatics and cheminformatics. The results demonstrate that our approach offers competitive prediction accuracy while the interpretability is straightforward.