SVM for learning with label proportions
Felix X. Yu, Dong Liu, Sanjiv Kumar, Tony Jebara, Shih‐Fu Chang · 2013
We study the problem of learning with la-bel proportions in which the training data is provided in groups and only the propor-tion of each class in each group is known. We propose a new method called proportion-SVM, or ∝SVM, which explicitly models the latent unknown instance labels together with the known group label proportions in a large-margin framework. Unlike the existing works, our approach avoids making restric-tive assumptions about the data. The ∝SVM model leads to a non-convex integer program-ming problem. In order to solve it efficiently, we propose two algorithms: one based on simple alternating optimization and the other based on a convex relaxation. Extensive ex-periments on standard datasets show that ∝SVM outperforms the state-of-the-art, es-pecially for larger group sizes. 1.