  This paper proposes algorithms for learning two-level Boolean rules in
Conjunctive Normal Form (CNF, i.e. AND-of-ORs) or Disjunctive Normal Form (DNF,
i.e. OR-of-ANDs) as a type of human-interpretable classification model, aiming
for a favorable trade-off between the classification accuracy and the
simplicity of the rule. Two formulations are proposed. The first is an integer
program whose objective function is a combination of the total number of errors
and the total number of features used in the rule. We generalize a previously
proposed linear programming (LP) relaxation from one-level to two-level rules.
The second formulation replaces the 0-1 classification error with the Hamming
distance from the current two-level rule to the closest rule that correctly
classifies a sample. Based on this second formulation, block coordinate descent
and alternating minimization algorithms are developed. Experiments show that
the two-level rules can yield noticeably better performance than one-level
rules due to their dramatically larger modeling capacity, and the two
algorithms based on the Hamming distance formulation are generally superior to
the other two-level rule learning methods in our comparison. A proposed
approach to binarize any fractional values in the optimal solutions of LP
relaxations is also shown to be effective.
