Machine Learning as Massive Search

Machine Learning as Massive Search by Richard B. Segal Chairperson of Supervisory Committee: Associate Professor Oren Etzioni Department of Computer Science and Engineering Machine learning is the inference of general patterns from data. Machine-learning algorithms search large spaces of potential hypotheses for the hypothesis that best fits the data. Since the search space for most induction problems grows exponentially in the number of features used to describe the data, most induction algorithms use greedy search to minimize search cost. Greedy search is a polynomial-time algorithm that achieves its efficiency by exploring only a tiny fraction of all hypotheses. While greedy search has good performance, it often misses the best hypotheses. This thesis proposes massive search as an alternative to greedy search. Massive search aggressively searches as many hypotheses as possible in the time available. Since massive search explores a larger portion of the hypothesis space, it is less ..