The Curse of Highly Variable Functions for Local Kernel Machines

By Yoshua Bengio, Olivier Delalleau, Nicolas Le Roux. 2005

241 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistical Learning Theory

Citations in the corpus

Better Mixing via Deep Representations (2012, background): “specific function families have shown that choosing a sufficient depth of representation can yield exponential benefits, in terms of size of the model, to represent some functions (H̊astad, 1986; H̊astad and Goldmann, 1991; Bengio et al., 2006; Bengio and LeCun, 2007; Bengio and Delalleau, 2011).”
Representation Learning: A Review and New Perspectives (2012, background): “Examples of such general-purpose priors are the following: • Smoothness: assumes the function to be learned f is s.t. x ≈ y generally implies f(x) ≈ f(y).”
Random Feature Maps for Dot Product Kernels (2012, neutral): “Unfortunately this is almost surely the case with large datasets as demonstrated by several results (Steinwart, 2003, Steinwart and Christmann, 2008, Bengio et al., 2005) which predict an unbounded growth in the support sizes with growing training set sizes.”
Practical Recommendations for Gradient-Based Training of Deep Architectures (2012, background): “…we know that it is suﬃcient to regularize only the output weights in order to constrain capacity: in the limit case of the number of hidden units going to inﬁnity, L2 regularization corresponds to Support Vector Machines (SVM) while L1 regularization corresponds to boosting (Bengio et al. , 2006a).”
Avoiding pathologies in very deep networks (2014, neutral): “Bengio et al. (2006) showed that kernel machines have limited generalization ability when they use a local kernel such as the squared-exp.”
Why Does Unsupervised Pre-training Help Deep Learning? (2010, background): “Much recent research has been devoted to learning algorithms for deep architectures such as Deep Belief Networks and stacks of autoencoder variants with impressive results being obtained in several areas, mostly on vision and language datasets.”
Reinforcement learning for control: Performance, stability, and deep approximators (2018, background): “However, without assumptions in addition to smoothness, it is impossible to learn to approximate certain complex functions in a statistically efficient manner (Bengio et al., 2006).”
Greedy Layer-Wise Training of Deep Networks (2006, methodology): “Yoshua Bengio, Pascal Lamblin, Dan Popovici, Hugo Larochelle U. MontrealNIPS*2006 (Bengio et al 2006): Local kernel machines (= pattern matchers) and decision trees partition the space and may need exponential nb of units, i.e. of examples inefficient at representing highly-varying functions, which…”
An Introduction to Deep Learning (2011, unknown): “Moreover, in the case of highly varying functions, learning algorithms entirely based on local generalization are severely impacted by the curse of dimensionality [2].”
Context-Dependent Pre-Trained Deep Neural Networks for Large-Vocabulary Speech Recognition (2012, background): “In a related vein, [65] also proves an analogous “curse of rapidly-varying functions” for a large class of local kernel machines that include both supervised learning algorithms (e.g., SVMs with Gaussian kernels) and many semi-supervised algorithms and unsupervised manifold learning algorithms.”
Unsupervised Feature Learning and Deep Learning: A Review and New Perspectives (2012, background): “Unfortunately, as argued at length previously (Bengio and Monperrus, 2005; Bengio et al. , 2006a; Bengio and LeCun, 2007; Bengio, 2009; Bengio et al. , 2010), most of these algorithms only exploit the principle of local generalization , i.e., the assumption that the target function (to be learned)…”
Learning Algorithms for the Classification Restricted Boltzmann Machine (2012, methodology): “We provide results for the use of a Gaussian kernel (NP-Gauss) and a data-dependent truncated Gaussian kernel (NP-TruncGauss) used in Bengio et al. (2006a), which essentially outputs zero forpairs of inputs that are not near neighbors.”