Improved Branch and Bound Methods for Maximum Monomial Agreement

Noam Goldberg

(joint work with Jonathan Eckstein)

Abstract:

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.