Please use this identifier to cite or link to this item:
|Title:||On-line evaluation and prediction using linear functions||Authors:||Long, Philip M.||Issue Date:||1997||Citation:||Long, Philip M. (1997). On-line evaluation and prediction using linear functions. Proceedings of the Annual ACM Conference on Computational Learning Theory : 21-31. ScholarBank@NUS Repository.||Abstract:||We propose a model for situations where an algorithm needs to make a sequence of choices to minimize an evaluation function, but where the evaluation function must be learned on-line as it is being used. We describe algorithms for learning linear evaluation functions in this model, and prove performance bounds for them that hold in the worst case. Each bound is on the expectation, with respect to an algorithm`s randomization, of the sum of differences between the costs of the choices the algorithm makes and the best choices available. The bounds are in terms of the extent to which a linear model is appropriate, the number of alternatives to choose from, and the number of choices that need to be made. Ideas from the above analysis yield new absolute loss bounds for learning linear functions in the standard on-line prediction model. These bounds are on difference between the sum of absolute prediction errors made by the learning algorithm, and the best sum of absolute prediction errors that can be obtained by fixing a linear function in the given class. Known results imply that our bounds on this difference cannot be improved by more than a constant factor.||Source Title:||Proceedings of the Annual ACM Conference on Computational Learning Theory||URI:||http://scholarbank.nus.edu.sg/handle/10635/99573|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Sep 21, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.