Efficient bandit algorithms for online multiclass prediction

ABSTRACT

This paper introduces the Banditron, a variant of the Perceptron [Rosenblatt, 1958], for the multiclass bandit setting. The multiclass bandit setting models a wide range of practical supervised learning applications where the learner only receives partial feedback (referred to as "bandit" feedback, in the spirit of multi-armed bandit models) with respect to the true label (e.g. in many web applications users often only provide positive "click" feedback which does not necessarily fully disclose a true label). The Banditron has the ability to learn in a multiclass classification setting with the "bandit" feedback which only reveals whether or not the prediction made by the algorithm was correct or not (but does not necessarily reveal the true label). We provide (relative) mistake bounds which show how the Banditron enjoys favorable performance, and our experiments demonstrate the practicality of the algorithm. Furthermore, this paper pays close attention to the important special case when the data is linearly separable --- a problem which has been exhaustively studied in the full information setting yet is novel in the bandit setting.

REFERENCES

• 1: Rosa I. Arriaga , Santosh Vempala, An algorithmic theory of learning: Robust concepts and random projection, Machine Learning, v.63 n.2, p.161-182, May 2006 [doi>10.1007/s10994-006-6265-7]
• 2: P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. Gambling in a rigged casino: the adversarial multi-armed bandit problem. In Proceedings of the 36th Annual FOCS, 1998.
• 3: Koby Crammer , Yoram Singer, Ultraconservative online algorithms for multiclass problems, The Journal of Machine Learning Research, 3, p.951-991, 3/1/2003
• 4: Koby Crammer , Ofer Dekel , Joseph Keshet , Shai Shalev-Shwartz , Yoram Singer, Online Passive-Aggressive Algorithms, The Journal of Machine Learning Research, 7, p.551-585, 12/1/2006
• 5: R. O. Duda and P. E. Hart. Pattern Classification and Scene Analysis. Wiley, 1973.
• 6: A. Elisseeff and J. Weston. A kernel method for multi-labeled classification. In Advances in Neural Information Processing Systems 14, 2001.
• 7: Michael Fink , Shai Shalev-Shwartz , Yoram Singer , Shimon Ullman, Online multiclass learning by interclass hypothesis sharing, Proceedings of the 23rd international conference on Machine learning, p.313-320, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143884]
• 8: Abraham D. Flaxman , Adam Tauman Kalai , H. Brendan McMahan, Online convex optimization in the bandit setting: gradient descent without a gradient, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 9: Yoav Freund , Robert E. Schapire, Large Margin Classification Using the Perceptron Algorithm, Machine Learning, v.37 n.3, p.277-296, Dec. 1999 [doi>10.1023/A:1007662407062]
• 10: Jyrki Kivinen , Manfred K. Warmuth, Exponentiated gradient versus gradient descent for linear predictors, Information and Computation, v.132 n.1, p.1-63, Jan. 10, 1997 [doi>10.1006/inco.1996.2612]
• 11: R. D. Kleinberg. Nearly tight bounds for the continuumarmed bandit problem. NIPS, 2004.
• 12: J. Langford and T. Zhang. The epoch-greedy algorithm for contextual multi-armed bandits. NIPS, 2007.
• 13: Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
• 14: F. Rosenblatt, The perception: a probabilistic model for information storage and organization in the brain, Neurocomputing: foundations of research, MIT Press, Cambridge, MA, 1988
• 15: Shai Shalev-Shwartz , Yoram Singer, A primal-dual perspective of online learning algorithms, Machine Learning, v.69 n.2-3, p.115-142, December 2007 [doi>10.1007/s10994-007-5014-x]
• 16: V. N. Vapnik. Statistical Learning Theory. Wiley, 1998.
• 17: J. Weston and C. Watkins. Support vector machines for multi-class pattern recognition. In Proceedings of the Seventh European Symposium on Artificial Neural Networks, April 1999.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance