Online 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 also propose Avg Pegasos and Max Pegasos, which are extensions of Pegasos algorithm. We also provide mistake bounds for Avg Perceptron and regret bound for Avg Pegasos. We show the effectiveness of the proposed approaches by experimenting on various datasets and comparing them with the standard Perceptron and Pegasos.
Code (0)
등록된 구현이 없습니다.
Tasks
AvgClassificationGeneral ClassificationSimilar Papers 제목 키워드 기반
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 bee…
ClassificationGeneral ClassificationThe 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 AnsweringRamsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem
This work continues to investigate the link between differentially private (DP) and online learning. Alon, Livni, Malliaris, and Moran (2019) showed that for binary concept classes, DP learnability of a given class impli…
General ClassificationPAC learningInformative Label Missingness in Multiclass Classification Information Geometry and Excess Risk
Informative label missingness can change the usual efficiency ordering between completely and partially labelled classifiers because the pattern of missing labels may itself carry information about the classification mod…
Online Agnostic Multiclass Boosting
Boosting is a fundamental approach in machine learning that enjoys both strong theoretical and practical guarantees. At a high-level, boosting algorithms cleverly aggregate weak learners to generate predictions with arbi…
Binary Classification