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

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

稀疏决策树优化是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.

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

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.

这项工作将重新审视关节波束形成（BF）和天线选择（AS）问题，以及其在不完美的通道状态信息（CSI）下的稳健光束成型（RBF）版本。在射频链的数量（RF）链的数量小于发射器上的天线元件的情况下，出现了此类问题，这已成为大型阵列时代的关键考虑。关节（r）bf \＆作为问题是一个混合整数和非线性程序，因此发现{\ it最佳解决方案}通常是昂贵的，即使不是完全不可能。绝大多数先前的作品都使用基于连续优化的近似来解决这些问题 - 但是这些近似不能确保解决方案的最佳性甚至可行性。这项工作的主要贡献是三倍。首先，提出了一个有效的{\ it分支和绑定}（b \＆b）解决感兴趣问题的框架。利用现有的BF和RBF求解器，表明B \＆B框架保证了所考虑的问题的全球最优性。其次，为了加快潜在昂贵的B \＆B算法，提出了一种基于机器学习（ML）的方案，以帮助跳过B \＆B搜索树的中间状态。学习模型具有{\ it图形神经网络}（GNN）的设计，该设计对无线通信中通常遇到的挑战有抵抗力，即，培训和测试中问题大小的变化（例如，用户数量）的变化（例如，用户数量）阶段。第三，提出了全面的性能特征，表明基于GNN的方法在合理的条件下保留了B \＆B的全球最佳性，其复杂性可降低。数值模拟还表明，基于ML的加速度通常可以相对于B \＆b实现速度的速度。

线性回归是统计和相关字段中的基本建模工具。在本文中，我们研究了线性回归的重要变体，其中预测响应对部分不匹配。我们使用优化公式同时学习基础回归系数和与错配相对应的置换。问题的组合结构导致计算挑战。我们建议并研究一种简单的贪婪本地搜索算法，以解决这种优化问题，该算法具有强大的理论保证和具有吸引力的计算绩效。我们证明，与样本和特征的数量和问题数据的某些假设相比，在适当的不匹配对数的缩放缩放下；我们的本地搜索算法以线性速率收敛到几乎最佳的解决方案。特别是，在无嘈杂的情况下，我们的算法以线性收敛速率收敛到全局最佳解决方案。基于此结果，我们证明了参数估计误差的上限。我们还提出了一个近似的本地搜索步骤，使我们能够将方法扩展到更大的实例。我们进行数值实验，以收集有关我们理论结果的进一步见解，并与现有方法相比显示出令人鼓舞的性能增长。

符合使用机器学习的不断增长的趋势，帮助解决组合优化问题，一个有希望的想法是通过使用学习的策略来改善混合整数编程（MIP）分支和绑定树内的节点选择。以前使用模仿学习的工作指示通过学习自适应节点搜索顺序来获取节点选择策略的可行性。相比之下，我们的模仿学习策略仅专注于学习节点的孩子中的哪一个选择。我们介绍了一个脱机方法，用于在两个设置中学习这样的策略：一个通过致力于修剪节点的启发式;一个是从叶子精确和背溯以保证找到最佳整数解决方案的备用。前一个设置对应于困扰期间的儿童选择器，而后者则类似于潜水启发式。我们在热情和确切的设置中将策略应用于流行的开源求解器SCIP。五个MIP数据集的经验结果表明，我们的节点选择策略比文献中最先进的先例更快地导致解决方案。虽然我们在精确解决方案的时间内没有击败高度优化的SCIP状态基准节点选择器，但如果预测模型的准确性足够，我们的启发式政策比所有基线都具有始终如一的最佳最优性差距。此外，结果还表明，当应用时间限制时，我们的启发式方法发现比测试大多数问题中所有基线的更好的解决方案。我们通过表明学习的政策模仿了SCIP基线来解释结果，但没有后者早期的暴跌中止。我们的建议是，尽管对文献的清晰改进，但这种MIP儿童选择器在更广泛的方法中更好地使用MIP分支和束缚树决策。

$ k $ -means和$ k $ -median集群是强大的无监督机器学习技术。但是，由于对所有功能的复杂依赖性，解释生成的群集分配是挑战性的。 Moshkovitz，Dasgupta，Rashtchian和Frost [ICML 2020]提出了一个优雅的可解释$ K $ -means和$ K $ -Median聚类型号。在此模型中，具有$ k $叶子的决策树提供了集群中的数据的直接表征。我们研究了关于可解释的聚类的两个自然算法问题。 （1）对于给定的群集，如何通过使用$ k $叶的决策树找到“最佳解释”？ （2）对于一套给定的点，如何找到一个以美元的决策树，最小化$ k $ -means / median目标的可解释的聚类？要解决第一个问题，我们介绍了一个新的可解释群集模型。我们的型号受到强大统计数据的异常值概念的启发，是以下情况。我们正在寻求少数积分（异常值），其删除使现有的聚类良好可解释。为了解决第二个问题，我们开始研究Moshkovitz等人的模型。从多元复杂性的角度来看。我们严格的算法分析揭示了参数的影响，如数据的输入大小，尺寸，异常值的数量，簇数，近似比，呈现可解释的聚类的计算复杂度。

决策树是广泛使用的分类和回归模型，因为它们的解释性和良好的准确性。诸如购物车的经典方法基于贪婪的方法，但最近致力于最佳决策树的关注。我们研究了BlanQuero等人提出的非线性连续优化制剂。 （EJOR，Vol.284,2020; Cor，Vol.132,2021）（稀疏）最佳随机分类树。不仅适用于特征选择，还非常重要，而且还可以提高解释性。我们首先考虑基于$ l_ {0} $'norm“的凹形近似的替代方法来缩小这样的树木。与$ l_1 $和$ l _ {\ infty} $ scalalization，在24个数据集中获得了有希望的结果。然后，我们在多变量随机分类树的VC维度上获得界限。最后，由于培训是对大型数据集的计算挑战，我们提出了一般的分解方案和它的有效版本。在较大数据集上的实验表明，所提出的分解方法能够为了显着降低培训时间而不影响精度。

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

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.

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

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

随着优化软件的显着改进，几十年前似乎棘手的大规模问题的解决方案现在已成为日常任务。这将更多的现实应用程序纳入了优化器的范围。同时，解决优化问题通常是将解决方案付诸实践时较小的困难之一。一个主要的障碍是，可以将优化软件视为黑匣子，它可能会产生高质量的解决方案，但是当情况发生变化时，可以创建完全不同的解决方案，从而导致对优化解决方案的接受率低。这种可解释性和解释性的问题在其他领域（例如机器学习）引起了极大的关注，但在优化方面却不那么关注。在本文中，我们提出了一个优化框架，以得出本质上具有易于理解的解释性规则的解决方案，在哪些情况下应选择解决方案。我们专注于代表解释性规则的决策树，我们提出了整数编程公式以及一种启发式方法，以确保我们的方法即使在大规模问题上也适用。使用随机和现实世界数据的计算实验表明，固有的可解释性成本可能很小。

分层聚类研究将数据集的递归分区设置为连续较小尺寸的簇，并且是数据分析中的基本问题。在这项工作中，我们研究了Dasgupta引入的分层聚类的成本函数，并呈现了两个多项式时间近似算法：我们的第一个结果是高度电导率图的$ O（1）$ - 近似算法。我们简单的建筑绕过了在文献中已知的稀疏切割的复杂递归常规。我们的第二个和主要结果是一个US（1）$ - 用于展示群集明确结构的宽族图形的近似算法。该结果推出了以前的最先进的，该现有技术仅适用于从随机模型产生的图表。通过对合成和现实世界数据集的实证分析，我们所呈现的算法的实证分析表明了我们的工作的重要性，以其具有明确定义的集群结构的先前所提出的图表算法。

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.

高斯流程优化是一类成功的算法（例如GP-UCB），以通过顺序评估优化黑盒功能。然而，对于具有连续域的功能，高斯过程优化必须依赖于空间的固定离散化，或者在每个评估中解决非凸优化子问题的解决方案。第一种方法可能会对性能产生负面影响，而第二种方法则需要沉重的计算负担。第三种选项最近理论上学习，是自适应地离散功能域。尽管这种方法避免了额外的非凸优化成本，但整体计算复杂性仍然令人望而却步。诸如GP-UCB的算法具有$ O（t ^ 4）$的运行时间，其中$ t $是迭代的数量。在本文中，我们介绍了ADA-BKB（自适应预算的核化强盗），是一种无遗憾的高斯过程优化算法，用于连续域上的功能，可在$ O（t ^ 2 d_ \ text {eff} ^ 2）$ ，$ d_ \ text {eff} $是探索空间的有效维度，其通常小于$ t $。我们将我们的理论调查结果与合成非凸函数的实验以及超参数优化的真实问题进行了证实，确认了所提出的方法的良好实际表现。

\ textit {约束路径发现}的经典问题是一个经过充分研究但充满挑战的主题，在各个领域，例如沟通和运输等各个领域的应用。权重限制了最短路径问题（WCSPP），作为仅具有一个侧面约束的约束路径查找的基本形式，旨在计划成本最佳路径，其权重/资源使用受到限制。鉴于问题的双标准性质（即处理路径的成本和权重），解决WCSPP的方法具有一些带有双目标搜索的共同属性。本文在约束路径查找和双目标搜索中利用了最新的基于A*的最新技术，并为WCSPP提供了两种精确的解决方案方法，两者都可以在非常大的图表上解决硬性问题实例。我们从经验上评估了算法在新的大型和现实的问题实例上的性能，并在时空指标中显示出它们比最新算法的优势。本文还调查了优先级队列在被a*的约束搜索中的重要性。我们通过对逼真的和随机图进行了广泛的实验来展示，基于桶的队列没有打破打盘的方式可以有效地改善详尽的双标准搜索的算法性能。