Online Performance-Improvement Algorithms
Abstract
The results presented in this thesis contribute to two areas of computer science: machine learning and on-line algorithms. One limitation of current theoretical approaches to learning is that most of them involve function approximation, i.e., the learner improves the accuracy of its approximation to an unknown function as it sees more samples of the function. This thesis presents algorithms for improving performance at other tasks, such as navigation and paging. Specifically, these algorithms are online algorithms whose competitiveness improves when repeatedly applied to the same problem. The design of such algorithms is a new challenge in the area of online algorithms: the algorithms must not only be competitive on each application, but must also acquire useful information to improve their future competitiveness. We present a general framework based on task systems for studying such algorithms.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1994
- Accession Number
- ADA285162
Entities
People
- Prasad Chalasani
Organizations
- Carnegie Mellon University