Boosting Theory Towards Practice: Recent Developments in Decision Tree Induction and the Weak Learning Framework

摘要

One of the original goals of computational learning theory was that of formulating models that permit meaningful compartisons between the different machine learning heuristics that are used in practice (Kearns et al., 1987). Despite the other successes of computational learning theory, this goal has proven elusive. Empirically successful machine learning algorithms such as C4.5 and the backpropagation algorithm for neural networks have not met the criteria of the well-known Probably Approximately Correct (PAC) model (Valiant, 1984) and its variants, and thus such models are of little use in drawing distinctions among the heuristics used in applications. Conversely, the algorithms suggested by computational learning theory are usually to limited in various ways to find wide application.