On learning a union of half spaces

It is proved that no such approach to evading the CAP can work, and a new, fast algorithm is given for learning unions of half spaces in fixed dimension, suggesting a generalization of this approach which naively would avoid a credit assignment problem and learn in time polynomial in dimension.

Abstract

In Valiant's protocol for learning, the classes of functions which are known learnable in polynomial time are all trivial in the sense that they require no solution of a credit assignment problem (CAP)—either they can be learned using one type of example only (positive or negative), or they are learned by straightforward application of linear programming, or they are constructed so as to be learned by a greedy algorithm. Conversely, there is no natural class of finite Vapnik-Chervonenkis dimension known not to be learnable in polynomial time. We study therefore the learnability of a simple, nontrivial class of concepts: unions of half spaces. We give a new, fast algorithm for learning unions of half spaces in fixed dimension. We suggest a generalization of this approach which naively would avoid a credit assignment problem and learn in time polynomial in dimension. We then prove, however, that no such approach to evading the CAP can work. The proof of this theorem rules out as well a natural approach to solving the CAP. We believe that these results clarify why the learning problem is inherently difficult and hope to extend them to a proof that the class of unions of half spaces is fundamentally unlearnable. We also present, in an appendix, new lower bounds on the number of examples necessary for learning from one type of example.