Improved Branch and Bound Methods for Maximum Monomial Agreement
(joint work with Jonathan Eckstein)
The NP-hard Maximum Monomial Agreement (MMA) problem consists of finding
a single logical conjunction that best fits a weighted dataset of "positive" and "negative"
binary vectors.Computing a classifier by boosting methods in machine learning
involves a maximum agreement subproblem at each iteration, although typically
high-dimensional subproblems have been solved by heuristic methods. Here, we describe
an exact branch and bound method for maximum agreement over Boolean monomials,
improving on earlier work of Goldberg and Shan. In particular, we develop a tighter upper
bounding function and an improved branching procedure that exploits knowledge of the bound
and the dataset, while having a lower branching factor. Experimental results show that the new
method is able to solve larger problem instances and runs faster within a linear programming
boosting procedure applied to medium-sized datasets from the UCI repository.