Exploring applications of learning theory to pattern matching and dynamic adjustment of tcp acknowledgement delays
This student's dissertation, entitled Exploring Applications of Learning Theory to Pattern Matching and Dynamic Adjustment of TCP Acknowledgment Delays has been examined by the undersigned committee of ve faculty members and has received full approval for acceptance in partial fullllment of the requirements for the degree Doctor of Science. Learning theory is a subarea of machine learning that applies results from theoretical computer science, including complexity theory and algorithm design and analysis. In learning theory we rigorously study the eeciency and predictive performance of learning algorithms. While applications of machine learning are well-known, results from learning theory are just beginning to enter the practical arena. The purpose of this dissertation is to develop learning theory algorithms and take initial steps toward modifying them and applying them to practical problems. Here we look at two problems. One is learning geometric patterns, with a preliminary investigation of the learning algorithms' applicability to pattern matching, particularly landmark matching for robot navigation. The other area we study is dynamically adjusting acknowledgment delays in the transmission control protocol (TCP). Here the learning comes in when we attempt to predict TCP packet arrivals to enhance the performance of the algorithms that are adjusting the delays. For the problem of learning geometric patterns, we present three algorithms, all provably eecient and with guaranteed bounds on their error. Two of the algorithms are batch-style algorithms that learn one-dimensional patterns and one algorithm is on-line and can eeciently learn patterns in any xed dimension. Simulation results for the rst two algorithms are also presented, including some runs on real robot vision data. For the acknowledgment delay problem, we rst give two objective functions for measuring an algorithm's performance. These functions measure performance by taking a weighted average of the number of acknowledgments sent and the amount of extra latency introduced by delaying the acknowledgments. We then present two on-line algorithms for this problem, and prove that under certain circumstances they are guaranteed to work well. Simulation results are also provided, contrasting our algorithms with ones currently used in practice. We then perform a preliminary investigation of applying tools from learning theory to the problem of predicting TCP packet arrivals, in hopes of improving the performance of our algorithms on real network traac.