Deep learning and curse of dimensionalty

Question

From "] Learning Deep Architectures for AI". see: http://www.iro.umontreal.ca/~lisa/pointeurs/TR1312.pdf (see section 3.1)

"The local generalization issue is directly connected to the literature on the curse of dimensionality, but the results we cite show that what matters for generalization is not dimensionality, but instead the number of “variations” of the function we wish to obtain after learning. For example, if the function represented by the model is piecewise-constant (e.g. decision trees), then the question that matters is the number of pieces required to approximate properly the target function. There are connections between the number of variations and the input dimension: one can readily design families of target functions for which the number of variations is exponential in the input dimension, such as the parity function with d inputs."

Anyone care to explicate? Or try to reword this paragraph. Or give examples.

(And is he saying that decision trees are piecewise-constant?)

Answer 1

Why are decision trees piecewise constant? What trees essentially do is to partition the input space. The samples that fall into a partition then perform a vote to form a prediction for a new sample in their partition space, e.g. the mean.

What Bengio means is that these kinds of models are problematic, because there are some classes of functions, which are "antagonist" to this assumption: they vary a lot, depending on the input size, and thus make decision trees a pure choice.

Mind that this seems like an artifical argument: apparently he does not give concrete examples of such functions and where they matter in the real world. Still, there is lots of evidence that this is true, since DL methods tend to "beat" trees on many benchmarks of complicated functions (vision, audio, natural language).