Trading Complexity for Sparsity in Random Forest Explanations
  Random forests have long been considered as powerful model ensembles in
machine learning. By training multiple decision trees, whose diversity is
fostered through data and feature subsampling, the resulting random forest can
lead to more stable and reliable predictions than a single decision tree. This
however comes at the cost of decreased interpretability: while decision trees
are often easily interpretable, the predictions made by random forests are much
more difficult to understand, as they involve a majority vote over hundreds of
decision trees. In this paper, we examine different types of reasons that
explain "why" an input instance is classified as positive or negative by a
Boolean random forest. Notably, as an alternative to sufficient reasons taking
the form of prime implicants of the random forest, we introduce majoritary
reasons which are prime implicants of a strict majority of decision trees. For
these different abductive explanations, the tractability of the generation
problem (finding one reason) and the minimization problem (finding one shortest
reason) are investigated. Experiments conducted on various datasets reveal the
existence of a trade-off between runtime complexity and sparsity. Sufficient
reasons - for which the identification problem is DP-complete - are slightly
larger than majoritary reasons that can be generated using a simple linear-
time greedy algorithm, and significantly larger than minimal majoritary reasons
that can be approached using an anytime P ARTIAL M AX SAT algorithm.
