Daniël Vos

Room 4.E.420 / Building 28

Van Mourik Broekmanweg 6

2628 XE Delft

The Netherlands

Hi, I’m Daniël, a PostDoc at the algorithmics research group at the Delft University of Technology. My research is mainly on the trustworthiness of machine learning models, and I have a special fondness for decision tree models. I particularly enjoy working on the discrete optimization problems that appear when training and verifying decision tree models. For example, with our method ROCT we turned the problem of training robust decision trees against adversarial examples into combinatorial optimization which can then be solved with MILP or MaxSAT solvers. In our project OMDT, we were able to find optimal decision tree strategies for Markov Decision Processes (MDPs).

I strongly believe that we should be able to understand machine learning models that we deploy for critical applications. I worry that typical neural networks using post-hoc XAI methods give us a false sense of understanding. Therefore, I am also working on methods to train extremely small models with performance similar to that of more massive ones. My goal is to make every model as simple as possible.

Next to my academic life, I love strength training, rowing, and field hockey. I also organize Delft’s hacking team, currently one of the highest-placed teams from the Netherlands on CTFTime.

selected publications

arXiv

Optimizing Interpretable Decision Tree Policies for Reinforcement Learning

Daniël Vos, and Sicco Verwer

arXiv preprint arXiv:2408.11632 2024

Abs HTML PDF

Reinforcement learning techniques leveraging deep learning have made tremendous progress in recent years. However, the complexity of neural networks prevents practitioners from understanding their behavior. Decision trees have gained increased attention in supervised learning for their inherent interpretability, enabling modelers to understand the exact prediction process after learning. This paper considers the problem of optimizing interpretable decision tree policies to replace neural networks in reinforcement learning settings. Previous works have relaxed the tree structure, restricted to optimizing only tree leaves, or applied imitation learning techniques to approximately copy the behavior of a neural network policy with a decision tree. We propose the Decision Tree Policy Optimization (DTPO) algorithm that directly optimizes the complete decision tree using policy gradients. Our technique uses established decision tree heuristics for regression to perform policy optimization. We empirically show that DTPO is a competitive algorithm compared to imitation learning algorithms for optimizing decision tree policies in reinforcement learning.
IJCAI

Optimal Decision Tree Policies for Markov Decision Processes

Daniël Vos, and Sicco Verwer

International Joint Conference on Artificial Intelligence 2023

Abs HTML PDF

Interpretability of reinforcement learning policies is essential for many real-world tasks but learning such interpretable policies is a hard problem. Particularly, rule-based policies such as decision trees and rules lists are difficult to optimize due to their non-differentiability. While existing techniques can learn verifiable decision tree policies, there is no guarantee that the learners generate a policy that performs optimally. In this work, we study the optimization of size-limited decision trees for Markov Decision Processes (MPDs) and propose OMDTs: Optimal MDP Decision Trees. Given a user-defined size limit and MDP formulation, OMDT directly maximizes the expected discounted return for the decision tree using Mixed-Integer Linear Programming. By training optimal tree policies for different MDPs we empirically study the optimality gap for existing imitation learning techniques and find that they perform sub-optimally. We show that this is due to an inherent shortcoming of imitation learning, namely that complex policies cannot be represented using size-limited trees. In such cases, it is better to directly optimize the tree for expected return. While there is generally a trade-off between the performance and interpretability of machine learning models, we find that on small MDPs, depth 3 OMDTs often perform close to optimally.
ECML-PKDD

Adversarially Robust Decision Tree Relabeling

Daniël Vos, and Sicco Verwer

European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases 2022

Abs PDF

Decision trees are popular models for their interpretation properties and their success in ensemble models for structured data. How- ever, common decision tree learning algorithms produce models that suf- fer from adversarial examples. Recent work on robust decision tree learn- ing mitigates this issue by taking adversarial perturbations into account during training. While these methods generate robust shallow trees, their relative quality reduces when training deeper trees due the methods be- ing greedy. In this work we propose robust relabeling, a post-learning procedure that optimally changes the prediction labels of decision tree leaves to maximize adversarial robustness. We show this can be achieved in polynomial time in terms of the number of samples and leaves. Our results on 10 datasets show a significant improvement in adversarial accu- racy both for single decision trees and tree ensembles. Decision trees and random forests trained with a state-of-the-art robust learning algorithm also benefited from robust relabeling.
AAAI

Robust optimal classification trees against adversarial examples

Daniël Vos, and Sicco Verwer

AAAI Conference on Artificial Intelligence 2022

Abs HTML PDF

Decision trees are a popular choice of explainable model, but just like neural networks, they suffer from adversarial examples. Existing algorithms for fitting decision trees robust against adversarial examples are greedy heuristics and lack approximation guarantees. In this paper we propose ROCT, a collection of methods to train decision trees that are optimally robust against user-specified attack models. We show that the min-max optimization problem that arises in adversarial learning can be solved using a single minimization formulation for decision trees with 0-1 loss. We propose such formulations in Mixed-Integer Linear Programming and Maximum Satisfiability, which widely available solvers can optimize. We also present a method that determines the upper bound on adversarial accuracy for any model using bipartite matching. Our experimental results demonstrate that the existing heuristics achieve close to optimal scores while ROCT achieves state-of-the-art scores.
ICML

Efficient training of robust decision trees against adversarial examples

Daniël Vos, and Sicco Verwer

International Conference on Machine Learning 2021

Abs HTML PDF

Current state-of-the-art algorithms for training robust decision trees have high runtime costs and require hours to run. We present GROOT, an efficient algorithm for training robust decision trees and random forests that runs in a matter of seconds to minutes. Where before the worst-case Gini impurity was computed iteratively, we find that we can solve this function analytically to improve time complexity from O(n) to O(1) in terms of n samples. Our results on both single trees and ensembles on 14 structured datasets as well as on MNIST and Fashion-MNIST demonstrate that GROOT runs several orders of magnitude faster than the state-of-the-art works and also shows better performance in terms of adversarial accuracy on structured data.