Transductive Learning with Multi-class Volume Approximation
This work addresses a limitation in transductive learning for multi-class scenarios, though it appears incremental as it builds directly on existing volume approximation methods.
The paper tackles the problem of extending the large volume principle from binary to multi-class and other transductive learning settings, resulting in a method with a globally optimal solution computable in O(n^3) time and showing promising experimental performance.
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 extend it naturally to a more general definition which can be applied to several transductive problem settings, such as multi-class, multi-label and serendipitous learning. Even though the resultant learning method involves a non-convex optimization problem, the globally optimal solution is almost surely unique and can be obtained in O(n^3) time. We theoretically provide stability and error analyses for the proposed method, and then experimentally show that it is promising.