jmlr jmlr2011 jmlr2011-28 jmlr2011-28-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Peilin Zhao, Steven C.H. Hoi, Rong Jin
Abstract: In most kernel based online learning algorithms, when an incoming instance is misclassified, it will be added into the pool of support vectors and assigned with a weight, which often remains unchanged during the rest of the learning process. This is clearly insufficient since when a new support vector is added, we generally expect the weights of the other existing support vectors to be updated in order to reflect the influence of the added support vector. In this paper, we propose a new online learning method, termed Double Updating Online Learning, or DUOL for short, that explicitly addresses this problem. Instead of only assigning a fixed weight to the misclassified example received at the current trial, the proposed online learning algorithm also tries to update the weight for one of the existing support vectors. We show that the mistake bound can be improved by the proposed online learning method. We conduct an extensive set of empirical evaluations for both binary and multi-class online learning tasks. The experimental results show that the proposed technique is considerably more effective than the state-of-the-art online learning algorithms. The source code is available to public at http://www.cais.ntu.edu.sg/˜chhoi/DUOL/. Keywords: online learning, kernel method, support vector machines, maximum margin learning, classification
Antoine Bordes, Seyda Ertekin, Jason Weston, and L´ on Bottou. Fast kernel classifiers with online e and active learning. Journal of Machine Learning Research, 6:1579–1619, 2005. Antoine Bordes, L´ on Bottou, Patrick Gallinari, and Jason Weston. Solving multiclass support e vector machines with larank. In Proceedings of the 24th International Conference on Machine learning (ICML’07), pages 89–96, 2007. Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. Gert Cauwenberghs and Tomaso Poggio. Incremental and decremental support vector machine learning. In Advances in Neural Information Processing Systems 13 (NIPS), pages 409–415, 2000. Giovanni Cavallanti, Nicol` Cesa-Bianchi, and Claudio Gentile. Tracking the best hyperplane with o a simple budget perceptron. Machine Learning, 69(2-3):143–167, 2007. Nicol` Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge University o Press, 2006. Nicol` Cesa-Bianchi, Alex Conconi, and Claudio Gentile. On the generalization ability of on-line o learning algorithms. IEEE Trans. on Inf. Theory, 50(9):2050–2057, 2004. Koby Crammer and Yoram Singer. On the algorithmic implementation of multiclass kernel-based vector machines. Journal of Machine Learning Research, 2:265–292, 2001. Koby Crammer and Yoram Singer. Ultraconservative online algorithms for multiclass problems. Journal of Machine Learning Research, 3:951–991, 2003. Koby Crammer and Yoram Singer. Loss bounds for online category ranking. In Proceedings of the 18th Annual Conference on Learning Theory (COLT’05), pages 48–62, 2005. Koby Crammer, Jaz S. Kandola, and Yoram Singer. Online classification on a budget. In Advances in Neural Information Processing Systems (NIPS), 2003. Koby Crammer, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwartz, and Yoram Singer. Online passive-aggressive algorithms. Journal of Machine Learning Research, 7:551–585, 2006. Koby Crammer, Mark Dredze, and Fernando Pereira. Exact convex confidence-weighted learning. In Advances in Neural Information Processing Systems (NIPS), pages 345–352, 2008. Koby Crammer, Alex Kulesza, and Mark Dredze. Adaptive regularization of weight vectors. In Advances in Neural Information Processing Systems (NIPS), 2009. Ofer Dekel, Shai Shalev-Shwartz, and Yoram Singer. The forgetron: A kernel-based perceptron on a budget. SIAM J. Comput., 37(5):1342–1372, 2008. ISSN 0097-5397. Mark Dredze, Koby Crammer, and Fernando Pereira. Confidence-weighted linear classification. In Proceedings of the 25th International Conference on Machine Learning (ICML’08), pages 264–271, 2008. 1614 D OUBLE U PDATING O NLINE L EARNING Michael Fink, Shai Shalev-Shwartz, Yoram Singer, and Shimon Ullman. Online multiclass learning by interclass hypothesis sharing. In Proceedings of the 25th International Conference on Machine learning (ICML’06), pages 313–320, 2006. Yoav Freund and Robert E. Schapire. Large margin classification using the perceptron algorithm. Mach. Learn., 37(3):277–296, 1999. Claudio Gentile. A new approximate maximal margin classification algorithm. Journal of Machine Learning Research, 2:213–242, 2001. Jyrki Kivinen and Manfred K. Warmuth. Additive versus exponentiated gradient updates for linear prediction. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing (STOC’95), pages 209–218, 1995. Jyrki Kivinen, Alex J. Smola, and Robert C. Williamson. Online learning with kernels. In Advances in Neural Information Processing Systems (NIPS), pages 785–792, 2001. Yi Li and Philip M. Long. The relaxed online maximum margin algorithm. In Advances in Neural Information Processing Systems (NIPS), pages 498–504, 1999. Francesco Orabona, Joseph Keshet, and Barbara Caputo. The projectron: a bounded kernel-based perceptron. In Proceedings of the Twenty-Fifth International Conference on Machine Learning (ICML’08), pages 720–727, 2008. Frank Rosenblatt. The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65:386–407, 1958. Shai Shalev-Shwartz. Online learning:theory, algorithms, and applications. In Ph.D thesis, 2007. Shai Shalev-Shwartz and Yoram Singer. Online learning meets optimization in the dual. In Proceedings of the 19th Annual Conference on Learning Theory (COLT’06), pages 423–437, 2006. Shai Shalev-Shwartz and Yoram Singer. A primal-dual perspective of online learning algorithms. Machine Learning, 69(2-3):115–142, 2007. Vladimir N. Vapnik. Statistical Learning Theory. Wiley, 1998. Jason Weston and Antoine Bordes. Online (and offline) on an even tighter budget. In Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics (AISTATS’05), pages 413–420, 2005. Peilin Zhao, Steven C. H. Hoi, and Rong Jin. Duol: A double updating approach for online learning. In Advances in Neural Information Processing Systems 22 (NIPS), pages 2259–2267, 2009. 1615