Building Random Forests with Optimal Decision Trees

Decision trees are most often made using the heuristic that a series of locally optimal decisions yields a good final decision tree. Optimal decision trees omit this heuristic and exhaustively search - with many optimization techniques - for the best possible tree. In addition, training an ensemble of decision trees with some randomness has...

Optimal decision trees for the Algorithm Selection Problem: A dynamic programming approach

The Algorithm Selection Problem is a relevant question in computer science that would enable us to predict which algorithm would perform better on a given instance of a problem. <br/>Different solutions have been proposed, either using Mixed Integer Programming or machine learning models, but both suffer from either poor scalability, no...

Individually fair optimal decision trees: Using a dynamic programming approach

In this paper, we tackle the problem of creating decision trees that are both optimal and individually fair. While decision trees are popular due to their interpretability, achieving optimality can be difficult. Existing approaches either lack scalability or fail to consider individual fairness. To address this, we define individual fairness as...

Optimal decision tree using dynamic programming: for the algorithm selection problem

Several algorithms can often be used to solve a complex problem, such as the SAT problem or the graph coloring problem. Those algorithms differ in terms of speed based on the size or other features of the problem. Some algorithms perform much faster on a small size while others perform noticeably better on a larger instance. The optimization...

Improving Existing Optimal Decision Trees Algorithmsby Redefining Their Binarisation Strategy

Optimal decision trees are not easily improvable in terms of accuracy. However, improving the pre-processing of underlying dataset can be the answer to creating more accurate decision trees. In this paper, multiple methods of binarising datasets are considered and the resulting decision trees compared. The binarisation is divided into two stages...

Optimal Regression Trees via Dynamic Programming: Optimization techniques for learning Regression Trees

Decision trees make decisions in a way interpretable to humans, this is important when machines are increasingly used to aid in making high-stakes and socially sensitive decisions. While heuristics have been used for a long time to find decision trees with reasonable accuracy, recent approaches find fully optimal trees. Due to the computational...

Devising Multivariate Splits for Optimal Decision Trees

Decision trees are often desirable for classification/regression tasks thanks to their human-friendly models. Unfortunately, the construction of decision trees is a hard problem which usually implies having to rely on imperfect heuristic methods. Advancements in algorithmics and hardware processing power have rendered globally optimal trees...

SurTree: constructing optimal survival trees with MurTree

Survival analysis revolves around studying and predicting the time it takes for a particular event to occur. In clinical trials on terminal illnesses, this is usually the time from the diagnosis of a patient until their death. Estimating the odds of survival of a new patient can be done by analyzing survival data from past patients in similar...