Learning With Label Proportions via NPSVM

Recently, learning from label proportions (LLPs), which seeks generalized instance-level predictors merely based on bag-level label proportions, has attracted widespread interest. However, due to its weak label scenario, LLP usually falls into a transductive learning framework accounting for an intractable combinatorial optimization issue. In this paper, we propose a brand new algorithm, called LLPs via nonparallel support vector machine (LLP-NPSVM), to facilitate this dilemma. To harness satisfactory data adaption, instead of transductive learning fashion, our scheme determined instance labels according to two nonparallel hyper-planes under the supervision of label proportion information. In a geometrical view, our approach can be interpreted as an alternative competitive method benefiting from large margin clustering. In practice, LLP-NPSVM can be efficiently addressed by applying two fast sequential minimal optimization paths iteratively. To rationally support the effectiveness of our method, finite termination and monotonic decrease of the proposed LLP-NPSVM procedure were essentially analyzed. Various experiments demonstrated our algorithm enjoys rapid convergence and robust numerical stability, along with best accuracies among several recently developed methods in most cases.