Curse of dimensionality • Hacker News Board

I seem to remember F-tests or something like that when I did multi-dimensional variant analysis as part of my statistical geography courses back in the day.

Even though you may have data along 7 or 8 dimensions, you may be able to develop a statistcal model that captures 95% predictive value using only 3 or 4 dimensions (but the 3 or 4 dimensions do not co-relate perectly to any of the 7 or 8 dimensions you've collected), instead each predictive dimension is based on part of each of the others.

Or if I summarize: the underlying (statistically useful) dimensionality of a dataset can be smaller than the number of variables collected as many of the variables co-relate with each other.

Re: Curse of dimensionality

#15

Post by jimbokun » Thu, May 31, 2012, 2:06 AM UTC

arjunnarayan wrote: post #8

Here's my best attempt at a simple.wikipedia.org article. In accordance with both simple.wikipedia.org rules and the oft-repeated Einstein/Feynman/Michael Scott quotes about explaining things to 5-year olds being the best sign of understanding something yourself, I've kept the vocabulary simple: Feel free to remix and rework the text to improve it. "Machine learning" is often the problem of taking a bunch of data and…

I think that's a great explanation! However, I do have some exposure to the topic, so I would be interested to know if it makes sense to someone totally new to the subject.

Re: Curse of dimensionality

#16

Post by pacala » Thu, May 31, 2012, 2:24 AM UTC

arjunnarayan wrote: post #8

Here's my best attempt at a simple.wikipedia.org article. In accordance with both simple.wikipedia.org rules and the oft-repeated Einstein/Feynman/Michael Scott quotes about explaining things to 5-year olds being the best sign of understanding something yourself, I've kept the vocabulary simple: Feel free to remix and rework the text to improve it. "Machine learning" is often the problem of taking a bunch of data and…

Why not cluster one dimension at a time? K-means will meaningfully cluster for 2 of these dimensions and fail for the other 998. Measure how good the separation is and stick with the best X dimensions.

Re: Curse of dimensionality

#17

Post by arjunnarayan » Thu, May 31, 2012, 3:27 AM UTC

pacala wrote: post #16

arjunnarayan wrote: post #8

Here's my best attempt at a simple.wikipedia.org article. In accordance with both simple.wikipedia.org rules and the oft-repeated Einstein/Feynman/Michael Scott quotes about explaining things to 5-year olds being the best sign of understanding something yourself, I've kept the vocabulary simple: Feel free to remix and rework the text to improve it. "Machine learning" is often the problem of taking a bunch of data and…

Why not cluster one dimension at a time? K-means will meaningfully cluster for 2 of these dimensions and fail for the other 998. Measure how good the separation is and stick with the best X dimensions.

Yes that will work. But, there are 1000C2 such combinations (that is, O(2^n)), and you have to try them all since you don't know which two dimensions are needed. And you cannot do each of the 100 separately in one-dimension and later hope to "combine" them together. In fact, you might not even know that it is 2 of the dimensions that are special. Maybe it is 7. So you have to try each of the 2^100 combinations separately. The algorithm you propose is not polynomial in the number of features.

Re: Curse of dimensionality

#18

Post by kylebrown » Thu, May 31, 2012, 4:02 AM UTC

Another reference to PRML I presume?

To this page, I'd add a direct link to Mahalanobis Distance. I was just harping about MD in some HN comments the other day on a Bayes article. There's no pictoral representation on the wiki page, but it is intuitive and its one of those simple concepts with foundational implications.

MD rests on the assumption of gaussian/normal population. The math is straightforward, starting with the covariance matrix. The original (Rubine 1991) gesture recognizer used the MD of some 16 feature vectors between an input gesture and the collection of trained gestures.

Re: Curse of dimensionality

#19

Post by pangram » Thu, May 31, 2012, 4:09 AM UTC

pacala wrote: post #16

arjunnarayan wrote: post #8

Here's my best attempt at a simple.wikipedia.org article. In accordance with both simple.wikipedia.org rules and the oft-repeated Einstein/Feynman/Michael Scott quotes about explaining things to 5-year olds being the best sign of understanding something yourself, I've kept the vocabulary simple: Feel free to remix and rework the text to improve it. "Machine learning" is often the problem of taking a bunch of data and…

Why not cluster one dimension at a time? K-means will meaningfully cluster for 2 of these dimensions and fail for the other 998. Measure how good the separation is and stick with the best X dimensions.

There are a variety of techniques to reduce the dimensionality of data (i.e., Principal Component Analysis, among other ways), and you can get better results sometimes by running K-means (or whatever) on the dimensionally-reduced data.

Re: Curse of dimensionality

#20

Post by scottfr » Thu, May 31, 2012, 4:38 AM UTC

sageikosa wrote: post #14

I seem to remember F-tests or something like that when I did multi-dimensional variant analysis as part of my statistical geography courses back in the day. Even though you may have data along 7 or 8 dimensions, you may be able to develop a statistcal model that captures 95% predictive value using only 3 or 4 dimensions (but the 3 or 4 dimensions do not co-relate perectly to any of the 7 or 8 dimensions you've collec…

Principle Component Analysis is the main example of this:

http://en.wikipedia.org/wiki/Principal_component_analysis