Transductive Learning with Multi-class Volume Approximation


Gang Niu, Bo Dai, Christoffel Plessis, Masashi Sugiyama ;
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):1377-1385, 2014.


Given a hypothesis space, the large volume principle by Vladimir Vapnik prioritizes equivalence classes according to their volume in the hypothesis space. The volume approximation has hitherto been successfully applied to binary learning problems. In this paper, we propose a novel generalization to multiple classes, allowing applications of the large volume principle on more learning problems such as multi-class, multi-label and serendipitous learning in a transductive manner. Although the resultant learning method involves a non-convex optimization problem, the globally optimal solution is almost surely unique and can be obtained using O(n^3) time. Novel theoretical analyses are presented for the proposed method, and experimental results show it compares favorably with the one-vs-rest extension.

Related Material