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.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-niu14, title = {Transductive Learning with Multi-class Volume Approximation}, author = {Niu, Gang and Dai, Bo and Plessis, Christoffel and Sugiyama, Masashi}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {1377--1385}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/niu14.pdf}, url = {https://proceedings.mlr.press/v32/niu14.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Transductive Learning with Multi-class Volume Approximation %A Gang Niu %A Bo Dai %A Christoffel Plessis %A Masashi Sugiyama %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-niu14 %I PMLR %P 1377--1385 %U https://proceedings.mlr.press/v32/niu14.html %V 32 %N 2 %X 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.
RIS
TY - CPAPER TI - Transductive Learning with Multi-class Volume Approximation AU - Gang Niu AU - Bo Dai AU - Christoffel Plessis AU - Masashi Sugiyama BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/06/18 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-niu14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 2 SP - 1377 EP - 1385 L1 - http://proceedings.mlr.press/v32/niu14.pdf UR - https://proceedings.mlr.press/v32/niu14.html AB - 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. ER -
APA
Niu, G., Dai, B., Plessis, C. & Sugiyama, M.. (2014). Transductive Learning with Multi-class Volume Approximation. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(2):1377-1385 Available from https://proceedings.mlr.press/v32/niu14.html.

Related Material