Online Classification with Predictions
We study online classification when the learner has access to predictions about future examples. We design an online learner whose expected regret is never worse than the worst-case regret, gracefully improves with the quality of the predictions, and can be significantly better than the worst-case regret when the predictions of future examples are accurate. As a corollary, we show that if the learner is always guaranteed to observe data where future examples are easily predictable, then online learning can be as easy as transductive online learning. Our results complement recent work in online algorithms with predictions and smoothed online classification, which go beyond a worse-case analysis by using machine-learned predictions and distributional assumptions respectively.
Code (0)
등록된 구현이 없습니다.
Tasks
ClassificationSimilar Papers 제목 키워드 기반
Interpreting the Predictions of Complex ML Models by Layer-wise Relevance Propagation
Complex nonlinear models such as deep neural network (DNNs) have become an important tool for image classification, speech recognition, natural language processing, and many other fields of application. These models howe…
General Classificationimage-classificationImage Classificationspeech-recognition+1Going beyond accuracy: estimating homophily in social networks using predictions
In online social networks, it is common to use predictions of node categories to estimate measures of homophily and other relational properties. However, online social network data often lacks basic demographic informati…
General ClassificationOnline 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 ClassificationExplaining Classes through Word Attribution
In recent years, several methods have been proposed for explaining individual predictions of deep learning models, yet there has been little study of how to aggregate these predictions to explain how such models view cla…
ClassificationDeep LearningGenre classificationtext-classification+1Scalable Multilabel Prediction via Randomized Methods
Modeling the dependence between outputs is a fundamental challenge in multilabel classification. In this work we show that a generic regularized nonlinearity mapping independent predictions to joint predictions is suffic…
General ClassificationPrediction