Learning as optimization
Kevin S. Van Horn · 1994
This dissertation is concerned with inductive learning from examples, and the reduction of learning problems to associated optimization problems. The emphasis is on learning to classify. Theoretical results include (1) examining the application of Occam's Razor in a general learning setting; (2) investigating two optimization problems associated with learning using linear threshold functions, and showing it to be NP-hard to even approximate them to within constant factor; and (3) comparison of the expressive power of decision trees and rule lists. Practical results include a number of methods of randomly generating learning problems on which to compare learning algorithms, and a new rule induction algorithm called BBG. The problem generators allow one to see how a learning algorithm's performance varies as various parameters such as number of examples, size of target hypothesis, or noise level are varied. BBG learns rule lists by combining the greedy choice of the best new rule to insert into the current rule list with a branch-and-bound algorithm to find this best new rule.