Online learning by ellipsoid method

ABSTRACT

In this work, we extend the ellipsoid method, which was originally designed for convex optimization, for online learning. The key idea is to approximate by an ellipsoid the classification hypotheses that are consistent with all the training examples received so far. This is in contrast to most online learning algorithms where only a single classifier is maintained at each iteration. Efficient algorithms are presented for updating both the centroid and the positive definite matrix of ellipsoid given a misclassified example. In addition to the classical ellipsoid method, an improved version for online learning is also presented. Mistake bounds for both ellipsoid methods are derived. Evaluation with the USPS dataset and three UCI data-sets shows encouraging results when comparing the proposed online learning algorithm to two state-of-the-art online learners.

REFERENCES

• 1: Amit, Y., Shalev-Shwartz, S., & Singer, Y. (2007). Online classification for complex problems using simultaneous projections. In Advances in Neural Information Processing Systems (pp. 17--24).
• 2: Crammer, K. (2004). Online learning of complex categorial problems. Doctoral dissertation, Hebrew Univeristy of Jerusalem.
• 3: 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
• 4: Koby Crammer , Yoram Singer, On the algorithmic implementation of multiclass kernel-based vector machines, The Journal of Machine Learning Research, 2, 3/1/2002
• 5: Koby Crammer , Yoram Singer, Ultraconservative online algorithms for multiclass problems, The Journal of Machine Learning Research, 3, p.951-991, 3/1/2003 [doi>10.1162/jmlr.2003.3.4-5.951]
• 6: 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]
• 7: Claudio Gentile, A new approximate maximal margin classification algorithm, The Journal of Machine Learning Research, 2, 3/1/2002
• 8: Claudio Gentile , Manfred K. Warmuth, Linear hinge loss and average margin, Proceedings of the 1998 conference on Advances in neural information processing systems II, p.225-231, July 1999
• 9: Adam J. Grove , Nick Littlestone , Dale Schuurmans, General Convergence Results for Linear Discriminant Updates, Machine Learning, v.43 n.3, p.173-210, June 2001 [doi>10.1023/A:1010844028087]
• 10: Mark Herbster , Massimiliano Pontil , Lisa Wainer, Online learning over graphs, Proceedings of the 22nd international conference on Machine learning, p.305-312, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102390]
• 11: 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]
• 12: Kivinen, J., Smola, A. J., & C. Williamson, R. (2002). Online learning with kernels. IEEE Transactions on Signal Processing, 52, 2165--2176.
• 13: Yi Li , Philip M. Long, The Relaxed Online Maximum Margin Algorithm, Machine Learning, v.46 n.1-3, p.361-387, 2002 [doi>10.1023/A:1012435301888]
• 14: N. Littlestone, Mistake bounds and logarithmic linear-threshold learning algorithms, University of California at Santa Cruz, Santa Cruz, CA, 1990
• 15: Rosenblatt, F. (1958). The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65, 386--407.
• 16: Shalev-Shwartz, S., & Singer, Y. (2006). Online learning meets optimization in the dual. Proc. of the 19th Annual Conf. on Learning Theory (pp. 423--437).
• 17: Shor, N. (1977). Cut-off method with space extension in convex programming problems. Cybernetics, 12, 94--94.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Convex programming
      G.1.8 Partial Differential Equations
          Subjects: Elliptic equations

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation
  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, Theory