Improving on-line learning
Mesterharm, Chris · Rutgers University Community Repository (Rutgers University) · 2007
In this dissertation, we consider techniques to improve the performance and applicability of algorithms used for on-line learning. We organize these techniques according to the assumptions they make about the generation of instances. Our first assumption is that theinstances are generated by a fixed distribution. Many algorithms are designed to perform well when instances are generated by an adversary;we give two techniques to modify these algorithms to improve performance when the instances are instead generated by a distribution. We validate these techniques with extensive experiments using a wide range of real world data sets. Our second assumption isthat the target concept the algorithm is attempting to learn changes over time. We give a modification of the Winnow algorithm and show ithas good bounds for tracking a shifting concept when instances are generated by an adversary. We also consider the case that the instances are generated by a shifting distribution. We applyvariations of the previous fixed distribution techniques and show, with real data derived experiments, that these techniques continue tosignificantly improve performance. Last, we assume that the labels for instances may be delayed for a number of trials. We give techniques to modify an on-line algorithm so that it has good performance even when the labels are delayed. We derive upper-bounds on the performance of these modifications and show through lower-bounds that these modifications are close to optimal.