Online Performance-Improvement Algorithms
CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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.
- Computer Programming and Software