LEARNING CLASSES OF LINEARLY SEPARABLE BOOLEAN FUNCTIONS FROM POSITIVE EXAMPLES
Paola Campadelli, Anna Morpurgo · International Journal of Foundations of Computer Science · 1992
This paper deals with learnability from positive examples of subclasses of linearly separable boolean functions in the framework of the probably approximately correct learning model. We prove that classes of functions defined by binary threshold neurons with n inputs and g(n) unknown weights are learnable in polynomial time iff g(n)=O(log n) and give an upper and a lower bound on the sample size.