In this paper, we present a novel semidefinite programming approach for multiple-instance learning. We first formulate the multiple-instance learning as a combinatorial maximum margin optimization problem with additional instance selection constraints within the framework of support vector machines. Although solving this primal problem requires non-convex programming, we nevertheless can then derive an equivalent dual formulation that can be relaxed into a novel convex semidefinite programming (SDP). The relaxed SDP has free parameters where T is the number of instances, and can be solved using a standard interior-point method. Empirical study shows promising performance of the proposed SDP in comparison with the support vector machine approaches with heuristic optimization procedures.

Additional Metadata
Persistent URL
Series Lecture Notes in Computer Science
Guo, Y. (2009). Max-margin Multiple-Instance Learning via Semidefinite Programming. In Lecture Notes in Computer Science. doi:10.1007/978-3-642-05224-8_9