Large Margin Partial Label Machine

Partial label learning (PLL) is a multi-class weakly supervised learning problem where each training instance is associated with a set of candidate labels but only one label is the ground truth. The main challenge of PLL is how to deal with the label ambiguities. Among various disambiguation techniques, large margin (LM)-based algorithms attract much attention due to their powerful discriminative performance. However, existing LM-based algorithms either neglect some potential candidate labels in constructing the margin or introduce auxiliary estimation of class capacities which is generally inaccurate. As a result, their generalization performances are deteriorated. To address the above-mentioned drawbacks, motivated by the optimistic superset loss, we propose an LM Partial LAbel machiNE (LM-PLANE) by extending multi-class support vector machines (SVM) to PLL. Compared with existing LM-based disambiguation algorithms, LM-PLANE considers the margin of all potential candidate labels without auxiliary estimation of class capacities. Furthermore, an efficient cutting plane (CP) method is developed to train LM-PLANE in the dual space. Theoretical insights into the effectiveness and convergence of our CP method are also presented. Extensive experiments on various PLL tasks demonstrate the superiority of LM-PLANE over existing LM based and other representative PLL algorithms in terms of classification accuracy.