The Curse of Dimensionality for Local Learning

Опубликовано 6 сентября 2016, 5:36

We present a series of arguments supporting the claim that a large class of modern learning algorithms based on local kernels are highly sensitive to the curse of dimensionality. These algorithms include in particular local manifold learning algorithms such as Isomap and LLE, and support vector classifiers with Gaussian or other local kernels. The results show that these algorithms are local in the sense that crucial properties of the learned function at X depend on the neighbors of X in the training set. This makes them highly sensitive to the curse of dimensionality, well studied for classical non-parametric statistical learning algorithms. There is a large class of data distributions for which non-local solutions could be expressed compactly and potentially be learned with few examples, but which will require a large number of local bases and therefore a large number of training examples when using a local learning algorithm. We present evidence that non-local learning is possible without strong prior knowledge.