Sparse decision trees are one of the most common forms of interpretable
models. While recent advances have produced algorithms that fully optimize
sparse decision trees for prediction, that work does not address policy design,
because the algorithms cannot handle weighted data samples. Specifically, they
rely on the discreteness of the loss function, which means that real-valued
weights cannot be directly used. For example, none of the existing techniques
produce policies that incorporate inverse propensity weighting on individual
data points. We present three algorithms for efficient sparse weighted decision
tree optimization. The first approach directly optimizes the weighted loss
function; however, it tends to be computationally inefficient for large
datasets. Our second approach, which scales more efficiently, transforms
weights to integer values and uses data duplication to transform the weighted
decision tree optimization problem into an unweighted (but larger) counterpart.
Our third algorithm, which scales to much larger datasets, uses a randomized
procedure that samples each data point with a probability proportional to its
weight. We present theoretical bounds on the error of the two fast methods and
show experimentally that these methods can be two orders of magnitude faster
than the direct optimization of the weighted loss, without losing significant
accuracy.

本研究提出了三种算法来高效地稀疏加权决策树优化，解决了算法无法处理加权数据样本的问题，这在影响个体数据点上的倒数概率加权方面有重要应用.

用于最优治疗方案和最优策略设计的加权稀疏决策树快速优化

Fast Optimization of Weighted Sparse Decision Trees for use in Optimal Treatment Regimes and Optimal Policy Design

Given thousands of equally accurate machine learning (ML) models, how can
users choose among them? A recent ML technique enables domain experts and data
scientists to generate a complete Rashomon set for sparse decision trees--a
huge set of almost-optimal interpretable ML models. To help ML practitioners
identify models with desirable properties from this Rashomon set, we develop
TimberTrek, the first interactive visualization system that summarizes
thousands of sparse decision trees at scale. Two usage scenarios highlight how
TimberTrek can empower users to easily explore, compare, and curate models that
align with their domain knowledge and values. Our open-source tool runs
directly in users' computational notebooks and web browsers, lowering the
barrier to creating more responsible ML models. TimberTrek is available at the
following public demo link: this https URL.

TimberTrek 是一款交互式可视化系统，可帮助机器学习从业人员在大规模的稀疏决策树集合中探索、比较和筛选满足其领域知识和价值观的模型，从而提高模型的解释性和责任性。

TimberTrek：交互可视化探索和整理稀疏决策树

TimberTrek: Exploring and Curating Sparse Decision Trees with Interactive Visualization

In any given machine learning problem, there may be many models that could
explain the data almost equally well. However, most learning algorithms return
only one of these models, leaving practitioners with no practical way to
explore alternative models that might have desirable properties beyond what
could be expressed within a loss function. The Rashomon set is the set of these
all almost-optimal models. Rashomon sets can be extremely complicated,
particularly for highly nonlinear function classes that allow complex
interaction terms, such as decision trees. We provide the first technique for
completely enumerating the Rashomon set for sparse decision trees; in fact, our
work provides the first complete enumeration of any Rashomon set for a
non-trivial problem with a highly nonlinear discrete function class. This
allows the user an unprecedented level of control over model choice among all
models that are approximately equally good. We represent the Rashomon set in a
specialized data structure that supports efficient querying and sampling. We
show three applications of the Rashomon set: 1) it can be used to study
variable importance for the set of almost-optimal trees (as opposed to a single
tree), 2) the Rashomon set for accuracy enables enumeration of the Rashomon
sets for balanced accuracy and F1-score, and 3) the Rashomon set for a full
dataset can be used to produce Rashomon sets constructed with only subsets of
the data set. Thus, we are able to examine Rashomon sets across problems with a
new lens, enabling users to choose models rather than be at the mercy of an
algorithm that produces only a single model.

首次提供了一种完整枚举稀疏决策树中 Rashomon set 的技术，并通过特定的数据结构提供高效的查询和抽样，该技术可以使用户在精度相近的所有模型中实现无前提选择，并展示了三个应用，包括研究变量的重要性、平衡精度和 F1 得分的 Rashomon set 的枚举以及使用完整数据集产生只使用数据子集构建的 Rashomon set。