Max-margin Multiple-Instance Learning via Semidefinite Programming

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