.png){kind=icon}
.png){kind=icon}
Return
Multiclass classification with bandit feedback using adaptive regularization
.png){kind=icon}
OA
AI
DOI：10.1007/s10994-012-5321-8.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We present a new multiclass algorithm in the bandit framework, where after making a prediction, the learning algorithm receives only partial feedback, i.e., a single bit indicating whether the predicted label is correct or not, rather than the true label. Our algorithm is based on the second-order Perceptron, and uses upper-confidence bounds to trade-off exploration and exploitation, instead of random sampling as performed by most current algorithms. We analyze this algorithm in a partial adversarial setting, where instances are chosen adversarially, while the labels are chosen according to a linear probabilistic model which is also chosen adversarially. We show a regret of , which improves over the current best bounds of in the fully adversarial setting. We evaluate our algorithm on nine real-world text classification problems and on four vowel recognition tasks, often obtaining state-of-the-art results, even compared with non-bandit online algorithms, especially when label noise is introduced.
Keywords:
Online learning
Upper confidence bound
Regret
Journal
IF:
2.9
Papers:
2.6K
Citations:
3.4W