CMU-CS-01-132Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-01-132
Adam Kalai May 2001 Ph.D. Thesis
CMU-CS-01-132.ps
Keywords: Algorithms, on-line algorithms, machine learning, O.S.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 |