  A falling rule list is a probabilistic decision list for binary
classification, consisting of a series of if-then rules with antecedents in the
if clauses and probabilities of the desired outcome ("1") in the then clauses.
Just as in a regular decision list, the order of rules in a falling rule list
is important -- each example is classified by the first rule whose antecedent
it satisfies. Unlike a regular decision list, a falling rule list requires the
probabilities of the desired outcome ("1") to be monotonically decreasing down
the list. We propose an optimization approach to learning falling rule lists
and "softly" falling rule lists, along with Monte-Carlo search algorithms that
use bounds on the optimal solution to prune the search space.
