Optimal Decision Lists using SAT
  Decision lists are one of the most easily explainable machine learning
models. Given the renewed emphasis on explainable machine learning decisions,
this machine learning model is increasingly attractive, combining small size
and clear explainability. In this paper, we show for the first time how to
construct optimal "perfect" decision lists which are perfectly accurate on the
training data, and minimal in size, making use of modern SAT solving
technology. We also give a new method for determining optimal sparse decision
lists, which trade off size and accuracy. We contrast the size and test
accuracy of optimal decisions lists versus optimal decision sets, as well as
other state-of-the-art methods for determining optimal decision lists. We also
examine the size of average explanations generated by decision sets and
decision lists.
