![](https://csd.cmu.edu/sites/default/files/styles/full_width_focal_point/public/graduate.png.webp?itok=Wsy3nMEH)
Adam Kalai
Thesis Title:
Probabilistic and On-line Methods in Machine Learning
Degree Type:
Ph.D. in Computer Science
Advisor(s):
Avrim Blum
Graduated:
May
2001
Abstract:
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.
Thesis Committee:
Avrim Blum (Chair)
Manuel Blum
Danny Sleator
Santosh Vempala
Randy Bryant, Head, Computer Science Department
James Morris, Dean, School of Computer Science
Keywords: Algorithms, on-line algorithms, machine learning, O.S.
CMU-CS-01-132.pdf (577.28 KB) ( 44 pages)Copyright Notice