nips nips2009 nips2009-63 nips2009-63-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Peilin Zhao, Steven C. Hoi, Rong Jin
Abstract: In most online learning algorithms, the weights assigned to the misclassified examples (or support vectors) remain unchanged during the entire learning process. This is clearly insufficient since when a new misclassified example is added to the pool of support vectors, we generally expect it to affect the weights for the existing support vectors. In this paper, we propose a new online learning method, termed Double Updating Online Learning, or DUOL for short. Instead of only assigning a fixed weight to the misclassified example received in 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 significantly improved by the proposed online learning method. Encouraging experimental results show that the proposed technique is in general considerably more effective than the state-of-the-art online learning algorithms. 1
Cavallanti, G., Cesa-Bianchi, N., & Gentile, C. (2007). Tracking the best hyperplane with a simple budget perceptron. Machine Learning, 69, 143–167. Cesa-Bianchi, N., Conconi, A., & Gentile, C. (2004). On the generalization ability of on-line learning algorithms. IEEE Trans. on Inf. Theory, 50, 2050–2057. Cesa-Bianchi, N., & Gentile, C. (2006). Tracking the best hyperplane with a simple budget perceptron. COLT (pp. 483–498). Cheng, L., Vishwanathan, S. V. N., Schuurmans, D., Wang, S., & Caelli, T. (2006). Implicit online learning with kernels. NIPS (pp. 249–256). Crammer, K., Dekel, O., Keshet, J., Shalev-Shwartz, S., & Singer, Y. (2006). Online passiveaggressive algorithms. JMLR, 7, 551–585. Crammer, K., Kandola, J. S., & Singer, Y. (2003). Online classification on a budget. NIPS. Crammer, K., & Singer, Y. (2003). Ultraconservative online algorithms for multiclass problems. JMLR, 3, 951–991. Dekel, O., Shalev-Shwartz, S., & Singer, Y. (2005). The forgetron: A kernel-based perceptron on a fixed budget. NIPS. Dekel, O., Shalev-Shwartz, S., & Singer, Y. (2008). The forgetron: A kernel-based perceptron on a budget. SIAM J. Comput., 37, 1342–1372. Fink, M., Shalev-Shwartz, S., Singer, Y., & Ullman, S. (2006). Online multiclass learning by interclass hypothesis sharing. ICML (pp. 313–320). Freund, Y., & Schapire, R. E. (1999). Large margin classification using the perceptron algorithm. Mach. Learn., 37, 277–296. Gentile, C. (2001). A new approximate maximal margin classification algorithm. JMLR, 2, 213–242. Kivinen, J., Smola, A. J., & Williamson, R. C. (2001a). Online learning with kernels. NIPS (pp. 785–792). Kivinen, J., Smola, A. J., & Williamson, R. C. (2001b). Online learning with kernels. NIPS (pp. 785–792). Li, Y., & Long, P. M. (1999). The relaxed online maximum margin algorithm. NIPS (pp. 498–504). Orabona, F., Keshet, J., & Caputo, B. (2008). The projectron: a bounded kernel-based perceptron. ICML (pp. 720–727). Rosenblatt, F. (1958). The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65, 386–407. Shalev-Shwartz, S., & Singer, Y. (2006). Online learning meets optimization in the dual. COLT (pp. 423–437). Weston, J., & Bordes, A. (2005). Online (and offline) on an even tighter budget. AISTATS (pp. 413–420). Yang, L., Jin, R., & Ye, J. (2009). Online learning by ellipsoid method. ICML (p. 145). 9