[BibTeX] [RIS]
The Curse of Dimensionality for Local Kernel Machines
Type of publication: Techreport
Citation: Bengio-localfailure-TR-2005
Number: 1258
Year: 2005
Institution: Département d'informatique et recherche opérationnelle, Université de Montréal
URL: http://www.iro.umontreal.ca/~l...
Abstract: We present a series of theoretical arguments supporting the claim that a large class of modern learning algorithms based on local kernels are sensitive to the curse of dimensionality. These include local manifold learning algorithms such as Isomap and LLE, support vector classifiers with Gaussian or other local kernels, and graph-based semisupervised learning algorithms using a local similarity function. These algorithms are shown to be local in the sense that crucial properties of the learned function at x depend mostly on the neighbors of x in the training set. This makes them sensitive to the curse of dimensionality, well studied for classical non-parametric statistical learning. 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.
Userfields: topics={HighDimensional,Kernel,Unsupervised},cat={T},
Keywords:
Authors Bengio, Yoshua
Delalleau, Olivier
Le Roux, Nicolas
Added by: [ADM]
Total mark: 0
Attachments
  • tr1258.pdf
Notes
    Topics