Clinical decision requires reasoning in the presence of imperfect data. DTs are a well-known decision support tool, owing to their interpretability, fundamental in safety-critical contexts such as medical diagnosis. However, learning DTs from uncertain data leads to poor generalization, and generating predictions for uncertain data hinders prediction accuracy. Several methods have suggested the potential of probabilistic decisions at the internal nodes in making DTs robust to uncertainty. Some approaches only employ probabilistic thresholds during evaluation. Others also consider the uncertainty in the learning phase, at the expense of increased computational complexity or reduced interpretability. The existing methods have not clarified the merit of a probabilistic approach in the distinct phases of DT learning, nor when the uncertainty is present in the training or the test data. We present a probabilistic DT approach that models measurement uncertainty as a noise distribution, independently realized: (1) when searching for the split thresholds, (2) when splitting the training instances, and (3) when generating predictions for unseen data. The soft training approaches (1, 2) achieved a regularizing effect, leading to significant reductions in DT size, while maintaining accuracy, for increased noise. Soft evaluation (3) showed no benefit in handling noise.

Decision trees (DTs) are a widely used prediction tool, owing to their interpretability. Standard learning methods follow a locally-optimal approach that trades off prediction performance for computational efficiency. Such methods can however be far from optimal, and it may pay off to spend more computational resources to increase performance. Monte Carlo tree search (MCTS) is an approach to approximate optimal choices in exponentially large search spaces. Since exploring the space of all possible DTs is computationally intractable, we propose a DT learning approach based on MCTS. To bound the branching factor of MCTS, we limit the number of decisions at each level of the search tree, and introduce mechanisms to balance exploration, DT size and the statistical significance of the predictions. To mitigate the computational cost of our method, we employ a move pruning strategy that discards some branches of the search tree, leading to improved performance. The experiments show that our approach outperformed locally optimal search in 20 out of 31 datasets, with a reduction in DT size in most of the cases.