CMU-CS-01-132 Computer Science Department School of Computer Science, Carnegie Mellon University
Probabilistic and On-line Methods in Machine Learning Adam Kalai May 2001 Ph.D. Thesis
CMU-CS-01-132.ps
On the surface, the three on-line machine learning problems analyzed in this thesis may seem unrelated. The first is an on-line investment strategy introduced by Tom Cover. We begin with a simple analysis that extends to the case of fixed-percentage transaction costs. We then describe an efficient implementation that runs in time polynomial in the number of stocks. The second problem is k-fold cross validation, a popular technique in machine learning for estimating the error of a learned hypothesis. We show that this is a valid technique by comparing it to the hold-out estimate. Finally, we discuss work towards a dynamically-optimal adaptive binary search tree algorithm. 44 pages
| |
Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |