Why are kernel methods with RBFs effective for handwritten digits (letters) classification?

Question

The question emerged while reading Ch. 3 of Rasmussen & Williams http://www.gaussianprocess.org/gpml/. In the end of this chapter, the authors gave results for the problem of handwritten digits classification (16x16 greyscale pictures); features are 256 pixel intensities + bias. I was surprised that in such a high-dimensional problem, 'metric' methods, like Gaussian processes with squared exponential kernel, or SVM with the same kernel, behave quite nice. Also, I heard sometimes that SVM is good for [essentially bag-of-word] text classification. Why aren't they suffering from the curse of dimensionality?

Answer 1

Curse of dimensinality: In fact they do! This is completely a computational issue, and not related to their performance. It is just, they are designed to be efficient. If you thousands of samples into GP, it will get SO slow (basically a matrix inverse).

Good result: This is complicated. Not one can give exact answer why something works better on a specific problem. It depends on many factors, like the behaviour of the inputs, the tuning of the parameters and the optimizations, luck and noise, etc.