Seminars & Events

Mathematics and Computer Science Division
"Sparse Weighted Voting Classifier Selection and its LP Relaxation"

DATE: January 18, 2011
TIME: 10:30 AM - 11:30 AM
SPEAKER: Noam Goldberg Technion – Israel Institute of Technology, LANS Postdoc Interviewee
LOCATION: Building 240 Seminar Room 4301, Argonne National Laboratory
HOST: Sven Leyffer

Description:
We consider a combinatorial optimization problem that generalizes the minimum disagreement halfspace problem; we seek to minimize the number of misclassifications of a weighted voting classifier, plus a penalty proportional to the density of the vector of weights. We prove that the optimum is at least as hard to approximately compute as minimum disagreement halfspace for a large class of penalty parameters. After formulating the problem as a mixed integer program (MIP), we show that common "soft margin" linear programming formulations for constructing weighted voting classifiers are equivalent to the standard LP relaxation of our formulation. We illustrate that this standard LP relaxation can be very weak, with an exponential lower bound on the potential integrality gap. We then prove that augmenting the optimization problem with certain simple valid inequalities tightens the relaxation considerably, yielding a linear upper bound on the gap for all values of the penalty parameter that exceed a sensible lower bound. Finally, we describe a linear programming based boosting algorithm that dynamically generates both cuts and columns for solving our relaxation. We demonstrate the classification performance of our proposed algorithm with experimental results.

Save the event to your calendar [schedule.ics]