In:
INFORMS Journal on Computing, Institute for Operations Research and the Management Sciences (INFORMS), Vol. 24, No. 2 ( 2012-05), p. 328-341
Abstract:
The 𝒩 𝒫 -hard maximum monomial agreement problem consists of finding a single logical conjunction that is most consistent with or “best fits” a weighted data set of “positive” and “negative” binary vectors. Computing weighted voting classifiers using boosting methods involves a maximum agreement subproblem at each iteration, although such subproblems are typically solved in practice 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 [Goldberg, N., C. Shan. 2007. Boosting optimal logical patterns. Proc. 7th SIAM Internat. Conf. Data Mining, SIAM, Philadelphia, 228–236]. Specifically, we develop a tighter upper bounding function and an improved branching procedure that exploits knowledge of the bound and the particular data set, 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 data sets from the UCI Machine Learning Repository. The new algorithm also runs much faster than applying a commercial mixed-integer programming solver, which uses linear programming relaxation-based bounds, to an integer linear programming formulation of the problem.
Type of Medium:
Online Resource
ISSN:
1091-9856
,
1526-5528
DOI:
10.1287/ijoc.1110.0459
Language:
English
Publisher:
Institute for Operations Research and the Management Sciences (INFORMS)
Publication Date:
2012
detail.hit.zdb_id:
2070411-2
detail.hit.zdb_id:
2004082-9
SSG:
3,2
Permalink
