4 ms·

Just a thought: When Cover & Hart proved that the error for k-NN classification is no worse than twice the Bayes (optimal) error, "machine learning" as a phras

by apathy 9y ago

Just a thought: When Cover & Hart proved that the error for k-NN classification is no worse than twice the Bayes (optimal) error, "machine learning" as a phrase had not yet been observed in the wild. http://ieeexplore.ieee.org/document/1053964/ http://ieeexplore.ieee.org/document/1053964/ EE, CS, stats -- these are your fundamentals...

taeric 9y ago
This feels like a more significant result than it appears to get. I'm guessing the problem then comes down solely to defining a distance metric that you can easily/quickly evaluate? Or is this merely the upper bound and many folks do markedly better nowdays?
- highd 9y ago
  The result is in the large sample limit, which is pretty much never the case for high dimensional datasets like the ones most popular for ML these days (images, audio, text). It doesn't mean what the parent thinks it means.
  - taeric 9y ago
    Ah, so that means it doesn't mean what I also took it to mean. :) Know a good reading on this?
  - apathy 9y ago
    You are proposing that a reduced dimensional projection of a large dataset cannot approach this limit? I.e. expose the underlying low rank of nearly any huge sparse data matrix with an SVD or NMF. Enable fast recovery with a shitty (CS-wise) hash function. Recover most of the information about an observation's neighbors in a fraction of the time taken by many other approaches. What's popular for ML benchmarking these days is not necessarily the same as what's needed for a specific application. It's a useful proof to keep in mind before prematurely optimizing with overly complicated approaches.
    - highd 9y ago
      You are of course free to try simple dimensionality reduction and nearest neighbors, and if that works on your problem that's fantastic. To the research community, though, problems where approaches like that work were considered "solved" decades ago. And of course, in industry, if there's a chance of that working it's tried. But no one's building self driving cars with PCA and LSH.
aub3bhat 9y ago
Umm that's a beautiful theoretical result no doubt. But in practice the choice of the "space" that determines the neighborhood, matters more than anything else on the top of that space. Also as another commenter pointed out the result is applicable when infinite labeled samples are present, which is almost never. IMHO the reason Machine Learning is NOT Stats or Information theory because these beautiful fundamental result were found to be futile in practice.

by apathy 9y ago

taeric 9y ago

This feels like a more significant result than it appears to get. I'm guessing the problem then comes down solely to defining a distance metric that you can easily/quickly evaluate? Or is this merely the upper bound and many folks do markedly better nowdays?

highd 9y ago
The result is in the large sample limit, which is pretty much never the case for high dimensional datasets like the ones most popular for ML these days (images, audio, text). It doesn't mean what the parent thinks it means.
- taeric 9y ago
  Ah, so that means it doesn't mean what I also took it to mean. :) Know a good reading on this?
- apathy 9y ago
  You are proposing that a reduced dimensional projection of a large dataset cannot approach this limit? I.e. expose the underlying low rank of nearly any huge sparse data matrix with an SVD or NMF. Enable fast recovery with a shitty (CS-wise) hash function. Recover most of the information about an observation's neighbors in a fraction of the time taken by many other approaches. What's popular for ML benchmarking these days is not necessarily the same as what's needed for a specific application. It's a useful proof to keep in mind before prematurely optimizing with overly complicated approaches.
  - highd 9y ago
    You are of course free to try simple dimensionality reduction and nearest neighbors, and if that works on your problem that's fantastic. To the research community, though, problems where approaches like that work were considered "solved" decades ago. And of course, in industry, if there's a chance of that working it's tried. But no one's building self driving cars with PCA and LSH.

aub3bhat 9y ago

Umm that's a beautiful theoretical result no doubt. But in practice the choice of the "space" that determines the neighborhood, matters more than anything else on the top of that space. Also as another commenter pointed out the result is applicable when infinite labeled samples are present, which is almost never. IMHO the reason Machine Learning is NOT Stats or Information theory because these beautiful fundamental result were found to be futile in practice.