Max-margin multiple-instance learning via semidefinite programming

Abstract. In this paper, we present a novel semidefinite programming approach for multiple-instance learning. We first formulate the multiple-instance learning as a combinatorial maximummargin optimization prob-lem with additional instance selection constraints within the framework of support vector machines. Although solving this primal problem re-quires 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 O(T) free pa-rameters where T is the number of instances, and can be solved using a standard interior-point method. Empirical study shows promising per-formance of the proposed SDP in comparison with the support vector machine approaches with heuristic optimization procedures.