Optimal Decision Trees via Search : A Reinforcement Learning framework

Overview & Synopsis

Decision Trees (DTs) are important models due to their interpretability, especially those with small complexity (or size). This thesis brings forth contributions to the Decision Tree optimisation problem under a soft constraint on complexity. We formulate the problem as a Markov Decision Process (MDP), and we divide the thesis into two parts: 1- Learning optimal DTs in a batch setting where a fixed dataset is provided, and 2- Learning optimal DTs in an online setting where we observe a stream of data. Our main contribution in 1- is the development of the algorithm Branches. Branches employs an efficient Dynamic Programming procedure, along with a Branch & Bound pruning strategy that is based on a novel analytical bound we call Purification Bound. We prove theoretically that once Branches terminates, it always returns the optimal DT. Moreover, we analyse its complexity by deriving an upper bound on the number of its evaluation steps, and we show numerically that it is significantly lower than complexity bounds provided in the literature. From the empirical standpoint, Branches outperforms the state of the art, in terms of number of iterations and execution time, on a variety of standard datasets. Branches can be further improved through a C++ implementation as it is amenable to parallel computing. In 2- we provide two new approaches. The first approach is based on a Monte Carlo Tree Search formulation and yields three algorithms UCDT, EGDT and TSDT. These three algorithms satisfy asymptotic convergence guarantees; given an infinite stream of data, they find the optimal DT almost surely. On the other hand, we developed Online-Branches, a generalisation of Branches to the online setting based on a sliding window of fixed size. We show that its probability of optimality, after observing a certain number of samples, converges to 1 exponentially with the size of the sliding window. All the methods we introduced in 2- outperform the state of the art online DTs in terms of prequential accuracy and quality of the final proposed DT.