在任何给定的机器学习问题中，可能有许多模型可以很好地解释数据。但是，大多数学习算法仅返回这些模型中的一种，使从业者没有实用的方法来探索替代模型，这些模型可能具有超出损失函数中可以表达的内容的理想属性。 Rashomon集是所有这些几乎最佳模型的集合。 Rashomon集可能非常复杂，尤其是对于高度非线性功能类，允许复杂的交互项，例如决策树。我们提供了第一种完全列举稀疏决策树的Rashomon设置的技术；实际上，我们的工作提供了针对高度非线性离散功能类别的非平凡问题的所有Rashomon设置的首次列举。这使用户可以在所有近似同样好的模型中对模型选择的前所未有的控制水平。我们在专门的数据结构中表示Rashomon集，该数据结构支持有效的查询和采样。我们显示了Rashomon集的三个应用：1）它可用于研究一组几乎最佳树的重要性（与一棵树相对），2）Rashomon设置的精确度使Rashomon集可以枚举Rashomon集合。平衡的精度和F1得分，以及3）完整数据集的Rashomon集可以用于生产仅使用数据集的子集构建的Rashomon集。因此，我们能够检查新镜头问题的Rashomon集合，使用户能够选择模型，而不是受到仅产生单个模型的算法的摆布。

稀疏决策树优化是AI自成立以来的最基本问题之一，并且是可解释机器学习核心的挑战。稀疏的决策树优化是计算地的艰难，尽管自1960年代以来稳定的努力，但在过去几年中才突破问题，主要是在找到最佳稀疏决策树的问题上。然而，目前最先进的算法通常需要不切实际的计算时间和内存，以找到一些真实世界数据集的最佳或近最优树，特别是那些具有多个连续值的那些。鉴于这些决策树优化问题的搜索空间是大规模的，我们可以实际上希望找到一个稀疏的决策树，用黑盒机学习模型的准确性竞争吗？我们通过智能猜测策略来解决这个问题，可以应用于基于任何最优分支和绑定的决策树算法。我们表明，通过使用这些猜测，我们可以通过多个数量级来减少运行时间，同时提供所得树木可以偏离黑匣子的准确性和表现力的界限。我们的方法可以猜测如何在最佳决策树错误的持续功能，树的大小和下限上进行换算。我们的实验表明，在许多情况下，我们可以迅速构建符合黑匣子型号精度的稀疏决策树。总结：当您在优化时遇到困难时，就猜测。

Regression trees are one of the oldest forms of AI models, and their predictions can be made without a calculator, which makes them broadly useful, particularly for high-stakes applications. Within the large literature on regression trees, there has been little effort towards full provable optimization, mainly due to the computational hardness of the problem. This work proposes a dynamic-programming-with-bounds approach to the construction of provably-optimal sparse regression trees. We leverage a novel lower bound based on an optimal solution to the k-Means clustering algorithm in 1-dimension over the set of labels. We are often able to find optimal sparse trees in seconds, even for challenging datasets that involve large numbers of samples and highly-correlated features.

决策树学习是机器学习中广泛使用的方法，在需要简洁明了的模型的应用中受到青睐。传统上，启发式方法用于快速生产具有相当高准确性的模型。然而，一个普遍的批评是，从精度和大小方面，所产生的树可能不一定是数据的最佳表示。近年来，这激发了最佳分类树算法的发展，这些算法与执行一系列本地最佳决策的启发式方法相比，在全球范围内优化决策树。我们遵循这一工作线，并提供了一种基于动态编程和搜索的最佳分类树的新颖算法。我们的算法支持对树的深度和节点数量的约束。我们方法的成功归因于一系列专门技术，这些技术利用了分类树独有的属性。传统上，最佳分类树的算法受到了高运行时的困扰和有限的可伸缩性，但我们在一项详细的实验研究中表明，我们的方法仅使用最先进的时间所需的时间，并且可以处理数十个数据集的数据集在数千个实例中，提供了几个数量级的改进，并特别有助于实现最佳决策树的实现。

决策树是机器学习工具箱中最有用和最受欢迎的方法之一。在本文中，我们考虑了学习最佳决策树的问题，这是一个组合优化问题，该问题具有挑战性。文献中的一种常见方法是使用贪婪的启发式方法，这可能不是最佳的。最近，人们对使用各种方法（例如，基于整数编程，动态编程）学习最佳决策树已经引起了重大兴趣 - 为了实现计算可伸缩性，这些方法中的大多数都集中在具有二进制功能的分类任务上。在本文中，我们提出了一种基于分支机构（BNB）的新离散优化方法，以获得最佳决策树。与现有的定制方法不同，我们考虑具有连续功能的回归和分类任务。我们方法基础的基本思想是基于特征分布的分位数来拆分搜索空间 - 导致沿BNB迭代的基础优化问题的上限和下限。与现有的各种真实数据集中的浅最佳树相比，我们提出的算法Quant-BNB显示出显着的加速。

本文考虑了在分解正常形式（DNF，ANDS的DNF，ANDS，相当于判定规则集）或联合正常形式（CNF，ORS）作为分类模型的联合正常形式的学习。为规则简化，将整数程序配制成最佳贸易分类准确性。我们还考虑公平设定，并扩大制定，以包括对两种不同分类措施的明确限制：机会平等和均等的赔率。列生成（CG）用于有效地搜索候选条款（连词或剖钉）的指数数量，而不需要启发式规则挖掘。此方法还会绑定所选规则集之间的间隙和培训数据上的最佳规则集。要处理大型数据集，我们建议使用随机化的近似CG算法。与三个最近提出的替代方案相比，CG算法主导了16个数据集中的8个中的精度简单折衷。当最大限度地提高精度时，CG与为此目的设计的规则学习者具有竞争力，有时发现明显更简单的解决方案，这些解决方案不太准确。与其他公平和可解释的分类器相比，我们的方法能够找到符合较严格的公平概念的规则集，以适度的折衷准确性。

尽管对连续数据的归一流流进行了广泛的研究，但直到最近才探索了离散数据的流量。然而，这些先前的模型遭受了与连续流的局限性。最值得注意的是，由于离散函数的梯度不确定或零，因此不能直接优化基于流动的模型。先前的作品近似离散功能的伪级，但不能在基本层面上解决该问题。除此之外，与替代离散算法（例如决策树算法）相比，反向传播可能是计算繁重的。我们的方法旨在减轻计算负担，并通过基于决策树开发离散流程来消除对伪级的需求，这是基于有效的基于树的基于有效的树的方法进行分类和回归的离散数据。我们首先定义了树结构化置换（TSP），该置换量（TSP）紧凑地编码离散数据的排列，其中逆向易于计算；因此，我们可以有效地计算密度值并采样新数据。然后，我们提出了一种决策树算法来构建TSP，该TSP通过新标准在每个节点上学习树结构和排列。我们从经验上证明了我们在多个数据集上方法的可行性。

We develop the first fully dynamic algorithm that maintains a decision tree over an arbitrary sequence of insertions and deletions of labeled examples. Given $\epsilon > 0$ our algorithm guarantees that, at every point in time, every node of the decision tree uses a split with Gini gain within an additive $\epsilon$ of the optimum. For real-valued features the algorithm has an amortized running time per insertion/deletion of $O\big(\frac{d \log^3 n}{\epsilon^2}\big)$, which improves to $O\big(\frac{d \log^2 n}{\epsilon}\big)$ for binary or categorical features, while it uses space $O(n d)$, where $n$ is the maximum number of examples at any point in time and $d$ is the number of features. Our algorithm is nearly optimal, as we show that any algorithm with similar guarantees uses amortized running time $\Omega(d)$ and space $\tilde{\Omega} (n d)$. We complement our theoretical results with an extensive experimental evaluation on real-world data, showing the effectiveness of our algorithm.

我们查看模型可解释性的特定方面：模型通常需要限制在大小上才能被认为是可解释的，例如，深度5的决策树比深度50中的一个更容易解释。但是，较小的模型也倾向于高偏见。这表明可解释性和准确性之间的权衡。我们提出了一种模型不可知论技术，以最大程度地减少这种权衡。我们的策略是首先学习甲骨文，这是培训数据上高度准确的概率模型。 Oracle预测的不确定性用于学习培训数据的抽样分布。然后，对使用此分布获得的数据样本进行了可解释的模型，通常会导致精确度明显更高。我们将抽样策略作为优化问题。我们的解决方案1具有以下关键的有利属性：（1）它使用固定数量的七个优化变量，而与数据的维度（2）无关，它是模型不可知的 - 因为可解释的模型和甲骨文都可能属于任意性模型家族（3）它具有模型大小的灵活概念，并且可以容纳向量大小（4）它是一个框架，使其能够从优化领域的进度中受益。我们还提出了以下有趣的观察结果：（a）通常，小型模型大小的最佳训练分布与测试分布不同； （b）即使可解释的模型和甲骨文来自高度截然不同的模型家族，也存在这种效果：我们通过使用封闭的复发单位网络作为甲骨文来提高决策树的序列分类精度，从而在文本分类任务上显示此效果。使用字符n-grams； （c）对于模型，我们的技术可用于确定给定样本量的最佳训练样本。

分类链是一种用于在多标签分类中建模标签依赖性的有效技术。但是，该方法需要标签的固定静态顺序。虽然理论上，任何顺序都足够了，实际上，该订单对最终预测的质量具有大量影响。动态分类链表示每个实例对分类的想法，可以动态选择预测标签的顺序。这种方法的天真实现的复杂性是禁止的，因为它需要训练一系列分类器，以满足标签的每种可能置换。为了有效地解决这个问题，我们提出了一种基于随机决策树的新方法，该方法可以动态地选择每个预测的标签排序。我们凭经验展示了下一个标签的动态选择，通过在否则不变的随机决策树模型下使用静态排序。 ％和实验环境。此外，我们还展示了基于极端梯度提升树的替代方法，其允许更具目标的动态分级链训练。我们的结果表明，该变体优于随机决策树和其他基于树的多标签分类方法。更重要的是，动态选择策略允许大大加速培训和预测。

我们为学习限制建立了混合整数优化的广泛方法论基础。我们提出了一种用于数据驱动决策的端到端管道，其中使用机器学习直接从数据中学习限制和目标，并且培训的模型嵌入在优化配方中。我们利用许多机器学习方法的混合整数优化 - 焦点，包括线性模型，决策树，集合和多层的感知。对多种方法的考虑允许我们捕获决策，上下文变量和结果之间的各种潜在关系。我们还使用观察结果的凸船体来表征决策信任区域，以确保可信的建议并避免推断。我们有效地使用列生成和聚类来纳入这个表示。结合域驱动的约束和客观术语，嵌入式模型和信任区域定义了处方生成的混合整数优化问题。我们将此框架实施为从业者的Python包（OptiCl）。我们展示了化疗优化和世界食物计划规划中的方法。案例研究说明了在生成高质量处方的框架中的框架，由信任区域添加的值，加入多个机器学习方法以及包含多个学习约束的框架。

In recent years there has been growing attention to interpretable machine learning models which can give explanatory insights on their behavior. Thanks to their interpretability, decision trees have been intensively studied for classification tasks, and due to the remarkable advances in mixed-integer programming (MIP), various approaches have been proposed to formulate the problem of training an Optimal Classification Tree (OCT) as a MIP model. We present a novel mixed-integer quadratic formulation for the OCT problem, which exploits the generalization capabilities of Support Vector Machines for binary classification. Our model, denoted as Margin Optimal Classification Tree (MARGOT), encompasses the use of maximum margin multivariate hyperplanes nested in a binary tree structure. To enhance the interpretability of our approach, we analyse two alternative versions of MARGOT, which include feature selection constraints inducing local sparsity of the hyperplanes. First, MARGOT has been tested on non-linearly separable synthetic datasets in 2-dimensional feature space to provide a graphical representation of the maximum margin approach. Finally, the proposed models have been tested on benchmark datasets from the UCI repository. The MARGOT formulation turns out to be easier to solve than other OCT approaches, and the generated tree better generalizes on new observations. The two interpretable versions are effective in selecting the most relevant features and maintaining good prediction quality.

We introduce a new rule-based optimization method for classification with constraints. The proposed method takes advantage of linear programming and column generation, and hence, is scalable to large datasets. Moreover, the method returns a set of rules along with their optimal weights indicating the importance of each rule for learning. Through assigning cost coefficients to the rules and introducing additional constraints, we show that one can also consider interpretability and fairness of the results. We test the performance of the proposed method on a collection of datasets and present two case studies to elaborate its different aspects. Our results show that a good compromise between interpretability and fairness on the one side, and accuracy on the other side, can be obtained by the proposed rule-based learning method.

我们提出了一种改善机器学习（ML）决策树（DTS）的准确性拦截权衡的方法。特别是，我们将最大的满足技术应用于计算最低纯DTS（MPDT）。我们提高了先前方法的运行时，并证明这些MPDT可以优于ML Framework Sklearn生成的DTS的准确性。

随着机器学习变得普遍，减轻培训数据中存在的任何不公平性变得至关重要。在公平的各种概念中，本文的重点是众所周知的个人公平，该公平规定应该对类似的人进行类似的对待。虽然在训练模型（对处理）时可以提高个人公平性，但我们认为在模型培训（预处理）之前修复数据是一个更基本的解决方案。特别是，我们表明标签翻转是改善个人公平性的有效预处理技术。我们的系统IFLIPPER解决了限制了个人公平性违规行为的最小翻转标签的优化问题，当培训数据中的两个类似示例具有不同的标签时，发生违规情况。我们首先证明问题是NP-HARD。然后，我们提出了一种近似的线性编程算法，并提供理论保证其结果与标签翻转数量有关的结果与最佳解决方案有多近。我们还提出了使线性编程解决方案更加最佳的技术，而不会超过违规限制。实际数据集上的实验表明，在看不见的测试集的个人公平和准确性方面，IFLIPPER显着优于其他预处理基线。此外，IFLIPPER可以与处理中的技术结合使用，以获得更好的结果。

目的：我们研究使用机器学习（ML）模型的可解释的累入预测，并在预测能力，稀疏性和公平性方面分析性能。与以前的作品不同，本研究列举了输出概率而不是二进制预测的可解释模型，并使用定量公平定义来评估模型。本研究还研究了模型是否可以横跨地理位置概括。方法：我们在佛罗里达州和肯塔基州的两个不同的刑事核查数据集上生成了黑盒和可解释的ML模型。我们将这些模型的预测性能和公平与目前用于司法系统中使用的两种方法进行了比较，以预测审前常规率：Arnold PSA和Compas。我们评估了所有模型的预测性能，可以在两次跨越两次预测六种不同类型犯罪的模型。结果：几种可解释的ML模型可以预测常规和黑盒ML模型，比Compas或Arnold PSA更准确。这些模型在实践中可能有用。类似于Arnold PSA，这些可解释模型中的一些可以作为一个简单的表格写入。其他可以使用一组可视化显示。我们的地理分析表明ML模型应分开培训，以便单独的位置并随时间更新。我们还为可​​解释模型提供了公平分析。结论：可解释的机器学习模型可以在预测准确性和公平性方面表现，也可以表现，也可以表现，也可以执行不可解释的方法和目前使用的风险评估尺度。机器学习模型对于单独培训，可以更准确地进行不同的位置，并保持最新。

我们提出了仅使用总人群统计数据来推断给定分类器的公平性和准确性的方法。当无法获得单个分类数据时，例如，当无法访问分类器或代表性的个人级验证集时，这是必要的。我们研究有关均衡的赔率标准的公平性，我们将其推广到多类分类。我们提出了有关该标准的不公平性的度量，该标准量化了不公平处理的人群的比例。然后，我们显示如何仅使用汇总标签统计信息（例如每个子人群中每个标签的预测率，以及每个标签的真实速率），如何获得给定分类器的不公平和误差的推断。我们为二进制分类器和多类分类器提供了推理程序，对于每个子人群中的混淆矩阵以及未知的情况下更具挑战性的情况而言。我们报告了代表不同应用的数据集的实验，这些实验证明了所提出方法的有效性和广泛使用。

决策树是分类和回归的强大工具，吸引了许多在机器学习新兴领域工作的研究人员。决策树比其他方法的优点之一是它们的解释性，通常比其他相对无法解释的更高精度方法更喜欢。二进制分类树具有两种类型的顶点：（i）分支顶点，这些顶点恰好有两个孩子，并且在一组离散功能上评估了数据点； （ii）为数据点的叶顶点提供了离散的预测。可以通过求解旨在（i）最大化正确分类数据的数量的生物目标优化问题来获得最佳的二进制分类树，并（ii）最小化分支顶点的数量。在本文中，我们提出了四个用于设计最佳二进制分类树的混合整数线性优化（MILO）公式：两种基于流动的配方和基于两切的配方。我们在提议的配方与Aghaei等人的最强Milo配方之间提供了理论比较。 （2021）。我们对13个公开数据集进行了实验，以显示模型的扩展能力以及使用Pareto前沿的生物原始方法的强度。我们的代码和数据可在GitHub上找到。

Shap（Shapley添加说明）值是解释机器学习模型的主要工具之一，具有强大的理论保证（一致性，本地准确性）以及广泛的实现和用例。即使计算形状值通常需要指数时间，也要在基于树的模型上进行多项式时间。尽管加速很大，但Treeshap仍然可以主导具有数百万或更多条目的数据集上行业级的机器学习解决方案的计算时间，从而导致事后模型诊断和解释服务延迟。在本文中，我们介绍了两种新算法，即快速Treeshap V1和V2，旨在提高大型数据集的Treeshap的计算效率。我们从经验上发现，快速的Treeshap V1的速度比Treeshap快1.5倍，同时保持内存成本不变。同样，由于昂贵的Treeshap步骤的预先摄入的前，快速Treeshap V2比Treeshap快2.5倍，其成本略高。我们还表明，快速的Treeshap V2非常适合多时间模型解释，从而使新传入样品的解释更高。

即使机器学习算法已经在数据科学中发挥了重要作用，但许多当前方法对输入数据提出了不现实的假设。由于不兼容的数据格式，或数据集中的异质，分层或完全缺少的数据片段，因此很难应用此类方法。作为解决方案，我们提出了一个用于样本表示，模型定义和培训的多功能，统一的框架，称为“ Hmill”。我们深入审查框架构建和扩展的机器学习的多个范围范式。从理论上讲，为HMILL的关键组件的设计合理，我们将通用近似定理的扩展显示到框架中实现的模型所实现的所有功能的集合。本文还包含有关我们实施中技术和绩效改进的详细讨论，该讨论将在MIT许可下发布供下载。该框架的主要资产是其灵活性，它可以通过相同的工具对不同的现实世界数据源进行建模。除了单独观察到每个对象的一组属性的标准设置外，我们解释了如何在框架中实现表示整个对象系统的图表中的消息推断。为了支持我们的主张，我们使用框架解决了网络安全域的三个不同问题。第一种用例涉及来自原始网络观察结果的IoT设备识别。在第二个问题中，我们研究了如何使用以有向图表示的操作系统的快照可以对恶意二进制文件进行分类。最后提供的示例是通过网络中实体之间建模域黑名单扩展的任务。在所有三个问题中，基于建议的框架的解决方案可实现与专业方法相当的性能。