Second International Workshop on Symbolic-Neural Learning (SNL-2018)

July 5-6, 2018
Nagoya Congress Center (Nagoya, Japan)

Online Multiclass Classification with Partial Feedback based on Complementary Learning

Takuo Kaneko (The University of Tokyo), Masashi Sugiyama (RIKEN/The University of Tokyo), and Issei Sato (The University of Tokyo/RIKEN)

Abstract:

We consider an online multiclass classification problem with partial feedback. In this problem, an algorithm proposes a class at each round, and only receives whether the proposed label is correct or not. In existing algorithms, the choice of the proposed label depends on some sampling strategies in the label space. In this paper, we propose a new online algorithm which chooses the proposed label greedily, i.e., the predicted label by the classifier is always proposed. Our method is inspired by the recently proposed learning from complementary labels—a complementary label indicates a specified class to which an instance does not belong. We provide a theoretical guarantee based on a cumulative loss bound for our proposed algorithm. We also demonstrate our algorithm outperforms existing approaches through experiments with various real-world datasets.