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.

本文介绍了一种基于子模优化的学习规则集的方法，将子问题转化为特征子集选择任务并利用子模函数差值的思想使得问题更易解决，实验结果表明这种方法简单、可扩展且具有较好效果。

学习可解释的决策规则集：一种次模优化方法

Learning Interpretable Decision Rule Sets: A Submodular Optimization Approach

Answering complex logical queries on large-scale incomplete knowledge graphs
(KGs) is a fundamental yet challenging task. Recently, a promising approach to
this problem has been to embed KG entities as well as the query into a vector
space such that entities that answer the query are embedded close to the query.
However, prior work models queries as single points in the vector space, which
is problematic because a complex query represents a potentially large set of
its answer entities, but it is unclear how such a set can be represented as a
single point. Furthermore, prior work can only handle queries that use
conjunctions ($\wedge$) and existential quantifiers ($\exists$). Handling
queries with logical disjunctions ($\vee$) remains an open problem. Here we
propose query2box, an embedding-based framework for reasoning over arbitrary
queries with $\wedge$, $\vee$, and $\exists$ operators in massive and
incomplete KGs. Our main insight is that queries can be embedded as boxes
(i.e., hyper-rectangles), where a set of points inside the box corresponds to a
set of answer entities of the query. We show that conjunctions can be naturally
represented as intersections of boxes and also prove a negative result that
handling disjunctions would require embedding with dimension proportional to
the number of KG entities. However, we show that by transforming queries into a
Disjunctive Normal Form, query2box is capable of handling arbitrary logical
queries with $\wedge$, $\vee$, $\exists$ in a scalable manner. We demonstrate
the effectiveness of query2box on three large KGs and show that query2box
achieves up to 25% relative improvement over the state of the art.

提出了一种基于嵌入的查询框架，使用矢量空间嵌入复杂逻辑查询，将查询表示为盒子并将合取作为盒子交集表示，而将极限作为在 DNF（析取正规形式）中转换后处理。