Analyses of instance-based learning algorithms

This paper presents PAC-learning analyses for instance-based learning algorithms for both symbolic and numeric-prediction tasks. The algorithms analyzed employ a variant of the k-nearest neighbor pattern classifier. The main results of these analyses are that the IB1 instance-based learning algorithm can learn, using a polynomial number of instances, a wide range of symbolic concepts and numeric functions. In addition, we show that a bound on the degree of difficulty of predicting symbolic values may be obtained by considering the size of the boundary of the target concept, and a bound on the degree of difficulty in predicting numeric values may be obtained by considering the maximum absolute value of the slope between instances in the instance space. Moreover, the number of training instances required by IBl is polynomial in these parameters. The implications of these results for the practical application of instance-based learning algorithms are discussed