Today, as increasingly complex predictive models are developed, simple rule
sets remain a crucial tool to obtain interpretable predictions and drive
high-stakes decision making. However, a single rule set provides a partial
representation of a learning task. An emerging paradigm in interpretable
machine learning aims at exploring the Rashomon set of all models exhibiting
near-optimal performance. Existing work on Rashomon-set exploration focuses on
exhaustive search of the Rashomon set for particular classes of models, which
can be a computationally challenging task. On the other hand, exhaustive
enumeration leads to redundancy that often is not necessary, and a
representative sample or an estimate of the size of the Rashomon set is
sufficient for many applications. In this work, we propose, for the first time,
efficient methods to explore the Rashomon set of rule set models with or
without exhaustive search. Extensive experiments demonstrate the effectiveness
of the proposed methods in a variety of scenarios.

本研究提出了一种高效的方法，可在有限的搜索中探索具有或不具有穷尽搜索的规则集模型的 Rashomon 集合。广泛的实验证明了所提方法在各种情况下的有效性。

高效勘探规则集模型的拉肖蒙集合

Efficient Exploration of the Rashomon Set of Rule Set Models

Model explainability is crucial for human users to be able to interpret how a
proposed classifier assigns labels to data based on its feature values. We
study generalized linear models constructed using sets of feature value rules,
which can capture nonlinear dependencies and interactions. An inherent
trade-off exists between rule set sparsity and its prediction accuracy. It is
computationally expensive to find the right choice of sparsity -- e.g., via
cross-validation -- with existing methods. We propose a new formulation to
learn an ensemble of rule sets that simultaneously addresses these competing
factors. Good generalization is ensured while keeping computational costs low
by utilizing distributionally robust optimization. The formulation utilizes
column generation to efficiently search the space of rule sets and constructs a
sparse ensemble of rule sets, in contrast with techniques like random forests
or boosting and their variants. We present theoretical results that motivate
and justify the use of our distributionally robust formulation. Extensive
numerical experiments establish that our method improves over competing methods
-- on a large set of publicly available binary classification problem instances
-- with respect to one or more of the following metrics: generalization
quality, computational cost, and explainability.

通过利用分布鲁棒优化，我们提出了一个新的公式来学习一组规则集的集合，以在保持计算成本低的同时确保良好的泛化性能，并通过构建一个稀疏的规则集合来解决规则集的稀疏性和预测准确性之间的固有权衡。

应用分布鲁棒优化获得可解释的分类模型

Obtaining Explainable Classification Models using Distributionally  Robust Optimization

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.

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