Mixed integer linear optimization formulations for learning optimal binary classification trees
Decision trees are powerful tools for classification and regression that attract many researchers working in the burgeoning area of machine learning. One advantage of decision trees over other methods is their interpretability, which is often preferred over other higher accuracy methods that are relatively uninterpretable. A binary classification tree has two types of vertices: (i) branching vertices which have exactly two children and where datapoints are assessed on a set of discrete features; and (ii) leaf vertices at which datapoints are given a discrete prediction. An optimal binary classification tree can be obtained by solving a biobjective optimization problem that seeks to (i) maximize the number of correctly classified datapoints and (ii) minimize the number of branching vertices. In this paper, we propose four mixed integer linear optimization (MILO) formulations for designing optimal binary classification trees: two flow-based formulations and two-cut based formulations. We provide theoretical comparisons between our proposed formulations and the strongest flow-based MILO formulation of Aghaei et al. (2021). We conduct experiments on 13 publicly available datasets to show the models' ability to scale and the strength of a biobjective approach using Pareto frontiers. Our code and data are available on GitHub.
Code (1)
Tasks
Binary ClassificationClassificationSimilar Papers 제목 키워드 기반
Tight Mixed-Integer Optimization Formulations for Prescriptive Trees
We focus on modeling the relationship between an input feature vector and the predicted outcome of a trained decision tree using mixed-integer optimization. This can be used in many practical applications where a decisio…
Mixed-Integer Optimisation of Graph Neural Networks for Computer-Aided Molecular Design
ReLU neural networks have been modelled as constraints in mixed integer linear programming (MILP), enabling surrogate-based optimisation in various domains and efficient solution of machine learning certification problem…
Informative Path Planning in Random Fields via Mixed Integer Programming
We present a new mixed integer formulation for the discrete informative path planning problem in random fields. The objective is to compute a budget constrained path while collecting measurements whose linear estimate re…
Trajectory planning with a dynamic obstacle clustering strategy using Mixed-Integer Linear Programming
In this paper we propose a technique that assigns obstacles to clusters used for collision avoidance via Mixed-Integer Programming. This strategy enables a reduction in the number of binary variables used for collision a…
ClusteringCollision AvoidanceModel Predictive ControlTrajectory PlanningMachine Learning Algorithms for Improving Exact Classical Solvers in Mixed Integer Continuous Optimization
Integer and mixed-integer nonlinear programming (INLP, MINLP) are central to logistics, energy, and scheduling, but remain computationally challenging. This survey examines how machine learning and reinforcement learning…
Reinforcement Learning