3 ms·

In theory, aren't decision trees universal approximators like Neural Networks?

by zump 10y ago

argonaut 10y ago
Yes. And in theory, k-nearest-neighbors is also a universal approximator. (Being a universal approximator doesn't tell you much since so many ML algos are).
- zump 10y ago
  On MNIST KNN will get you 95% but a deep net will get 98+. I find that interesting.
  - argonaut 10y ago
    On MNIST KNN with clever feature engineering will get you 99.4%, and a crazy deep net ensemble will get you 99.8%. I'm not sure what your point is. MNIST is the todo list of machine learning - it's a necessary but not sufficient condition for knowing which algos are good. In other words it's only useful for finding out which algos aren't good (e.g. if your code only gets 90% on MNIST you know there's a bug, but if your code gets 99% on MNIST it doesn't really mean much).
- srean 10y ago
  This [D]NN are "universal approximator" claim that gets trotted around really gets my goat. Sorry I have to vent now, and its no fault of my parent post or grand parent post. Its not that we were short of universal approximators. As far as learning is concerned, whether the class is universal or not has little or no import. For the sake of argument lets even assume that there is no noise in the training set [in other words I having a white horse on wings with a horn on its forehead that shoots laser beams with its eyes and farts indigo rainbows]. There will be infinitely many functions that passes through your training points and not all of them will have the same error on an unseen point. Learning is a very different ball game compared to approximation. "Universal", but in what class of functions ? All differentiable functions ? (the typical NN is restricted to this class), all continuous functions ? all measurable functions ? all computable functions ? Its surely not _all_ functions Here is a function: +1 on rational and -1 on irrational, can it approximate that ? here's another that is harder, +1 on a non-measurable set and -1 on a measurable set. You say these functions don't matter, indeed, I would be scared if they did matter. But it shows the real deal is characterizing that class of functions that "matter".
visarga 10y ago
Random forests don't get to be as 'deep' as NNs.
nl 10y ago
Yes, but there's no free lunch[1]. In theory, on average over all possible problems all algorithms are the same. In practice, that's a pretty useless piece of information, since the only thing that matters is your problem. Tabular data, and not huge amounts? Tree-based systems are your friend. Vast amounts of binary data (or increasingly text)? Deep neural networks will get you the best result. [1] https://en.wikipedia.org/wiki/No_free_lunch_theorem https://en.wikipedia.org/wiki/No_free_lunch_theorem

In theory, aren't decision trees universal approximators like Neural Networks?

by zump 10y ago

In theory, aren't decision trees universal approximators like Neural Networks?

Yes. And in theory, k-nearest-neighbors is also a universal approximator. (Being a universal approximator doesn't tell you much since so many ML algos are).

zump 10y ago
On MNIST KNN will get you 95% but a deep net will get 98+. I find that interesting.
- argonaut 10y ago
  On MNIST KNN with clever feature engineering will get you 99.4%, and a crazy deep net ensemble will get you 99.8%. I'm not sure what your point is. MNIST is the todo list of machine learning - it's a necessary but not sufficient condition for knowing which algos are good. In other words it's only useful for finding out which algos aren't good (e.g. if your code only gets 90% on MNIST you know there's a bug, but if your code gets 99% on MNIST it doesn't really mean much).
srean 10y ago
This [D]NN are "universal approximator" claim that gets trotted around really gets my goat. Sorry I have to vent now, and its no fault of my parent post or grand parent post. Its not that we were short of universal approximators. As far as learning is concerned, whether the class is universal or not has little or no import. For the sake of argument lets even assume that there is no noise in the training set [in other words I having a white horse on wings with a horn on its forehead that shoots laser beams with its eyes and farts indigo rainbows]. There will be infinitely many functions that passes through your training points and not all of them will have the same error on an unseen point. Learning is a very different ball game compared to approximation. "Universal", but in what class of functions ? All differentiable functions ? (the typical NN is restricted to this class), all continuous functions ? all measurable functions ? all computable functions ? Its surely not _all_ functions Here is a function: +1 on rational and -1 on irrational, can it approximate that ? here's another that is harder, +1 on a non-measurable set and -1 on a measurable set. You say these functions don't matter, indeed, I would be scared if they did matter. But it shows the real deal is characterizing that class of functions that "matter".

visarga 10y ago

Random forests don't get to be as 'deep' as NNs.

nl 10y ago

Yes, but there's no free lunch[1]. In theory, on average over all possible problems all algorithms are the same. In practice, that's a pretty useless piece of information, since the only thing that matters is your problem. Tabular data, and not huge amounts? Tree-based systems are your friend. Vast amounts of binary data (or increasingly text)? Deep neural networks will get you the best result. [1] https://en.wikipedia.org/wiki/No_free_lunch_theorem https://en.wikipedia.org/wiki/No_free_lunch_theorem