article · 2009
Online learning by ellipsoid method
Liu Yang, Rong Jin, Jieping Ye
Cited by 33Abstract and details only
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.
Cite this paper
Yang, L., Jin, R., & Ye, J. (2009). Online learning by ellipsoid method. https://doi.org/10.1145/1553374.1553521
Yang, Liu, et al. “Online learning by ellipsoid method.” 2009, pp. 1153–60, https://doi.org/10.1145/1553374.1553521.
Yang, Liu, Rong Jin, and Jieping Ye. 2009. “Online learning by ellipsoid method.” https://doi.org/10.1145/1553374.1553521.
Yang, L., Jin, R. and Ye, J. (2009) ‘Online learning by ellipsoid method’. Available at: https://doi.org/10.1145/1553374.1553521.
@article{yang2009online,
title = {{Online learning by ellipsoid method}},
author = {Yang, Liu and Jin, Rong and Ye, Jieping},
pages = {1153--1160},
year = {2009},
doi = {10.1145/1553374.1553521}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.