Online Multiclass Classification Based on Prediction Margin for Partial Feedback
We consider the problem of online multiclass classification with partial feedback, where an algorithm predicts a class for a new instance in each round and only receives its correctness. Although several methods have been developed for this problem, recent challenging real-world applications require further performance improvement. In this paper, we propose a novel online learning algorithm inspired by recent work on learning from complementary labels, where a complementary label indicates a class to which an instance does not belong. This allows us to handle partial feedback deterministically in a margin-based way, where the prediction margin has been recognized as a key to superior empirical performance. We provide a theoretical guarantee based on a cumulative loss bound and experimentally demonstrate that our method outperforms existing methods which are non-margin-based and stochastic.
Code (0)
등록된 구현이 없습니다.
Tasks
ClassificationGeneral ClassificationSimilar Papers 제목 키워드 기반
The price of bandit information in multiclass online classification
We consider two scenarios of multiclass online learning of a hypothesis class $H\subseteq Y^X$. In the {\em full information} scenario, the learner is exposed to instances together with their labels. In the {\em bandit} …
ClassificationGeneral ClassificationOpen-Ended Question AnsweringOnline Algorithms for Multiclass Classification using Partial Labels
In this paper, we propose online algorithms for multiclass classification using partial labels. We propose two variants of Perceptron called Avg Perceptron and Max Perceptron to deal with the partial labeled data. We als…
AvgClassificationGeneral ClassificationUnified Binary and Multiclass Margin-Based Classification
The notion of margin loss has been central to the development and analysis of algorithms for binary classification. To date, however, there remains no consensus as to the analogue of the margin loss for multiclass classi…
Binary ClassificationClassificationFormMulticlass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes
In this paper we study the problem of multiclass classification with a bounded number of different labels $k$, in the realizable setting. We extend the traditional PAC model to a) distribution-dependent learning rates, a…
Predtron: A Family of Online Algorithms for General Prediction Problems
Modern prediction problems arising in multilabel learning and learning to rank pose unique challenges to the classical theory of supervised learning. These problems have large prediction and label spaces of a combinatori…
Binary ClassificationClassificationGeneral ClassificationLearning-To-Rank