Name
Title | ||
|---|---|---|
Beyond Banditron: A Conservative and Efficient Reduction for Online Multiclass Prediction with Bandit Setting Model |
Abstract | ||
|---|---|---|
In this paper, we consider a recently proposed supervised learning problem, called online multiclass prediction with bandit setting model. Aiming at learning from partial feedback of online classification results, i.e. “true” when the predicting label is right or “false” when the predicting label is wrong, this new kind of problems arouses much of researchers’ interest due to its close relations to real world internet applications and human cognitive procedure. While some algorithms have been brought forward, we propose a novel algorithm to deal with such problems. First, we reduce the multiclass prediction problem to binary based on Conservative one-versus-all others Reduction scheme; Then Online Passive-Aggressive Algorithm is embedded as binary learning algorithm to solve the reduced problem. Also we derive a pleasing cumulative mistake bound for our algorithm and a time complexity bound linear to the sample size. Further experimental evaluation on several real world multiclass datasets including RCV1, MNIST, 20 Newsgroups and USPS shows that our method outperforms the existing algorithms with a great improvement. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/ICDM.2009.36 | ICDM |
Keywords | Field | DocType |
real world multiclass,reduced problem,online passive-aggressive algorithm,online multiclass prediction,existing algorithm,multiclass prediction problem,beyond banditron,conservative one-versus-all,efficient reduction,bandit setting model,novel algorithm,online classification result,real world internet application,encoding,probability density function,algorithm design and analysis,internet,learning artificial intelligence,time complexity,data mining,predictive models,prediction algorithms,supervised learning,cumulant,sample size | Data mining,MNIST database,Algorithm design,Computer science,Supervised learning,Artificial intelligence,Time complexity,Machine learning,Encoding (memory),The Internet,Binary number,Multiclass classification | Conference |
ISSN | Citations | PageRank |
1550-4786 | 3 | 0.42 |
References | Authors | |
12 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chen, Guangyun | 1 | 27 | 1.85 |
| Gang Chen | 2 | 7 | 3.05 |
| Jianwen Zhang | 3 | 319 | 14.74 |
| Shuo Chen | 4 | 183 | 10.56 |
| Changshui Zhang | 5 | 5506 | 323.40 |