An Improved Branch-and-Bound Method for Maximum Monomial Agreement
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 classifiers using boosting methods involves a maximum agreement subproblem at each iteration, although such subproblems are typically solved by heuristic methods. Here, we describe an exact branch and bound method for maximum agreement over Boolean monomials, improving on the earlier work of Goldberg and Shan (2007). 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.
Keywords: branch-and-bound, monomials, maximum agreement, machine learning, Boolean functions
Category 1: Integer Programming (0-1 Programming )
Category 2: Applications -- Science and Engineering (Data-Mining )
Category 3: Combinatorial Optimization (Branch and Cut Algorithms )
Citation: RUTCOR Research Report #14-2009, Rutgers Center for Operations Research, 640 Bartholomew Rd, Piscataway, NJ 08854, USA, October 2009.
Entry Submitted: 11/08/2009
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|