The assumption of classifiers is that features are independent. When dimensionality is increased the probability that this assumption be violated is increased, because more correlation shows up between group of features.  These group of features are in fact hidden principal components of the system. This is why dimensionality reduction techniques like PCA are helpful.

I like to equate this to number of variables vs number of equations problem. To solve for the variables, you need at least as many equations. I tend to see each dimension as a variable and the available amount of data as equations.

Use head/tail breaks to filter out big data; see this paper http://arxiv.org/abs/1501.03046

Machine Learning (ML) techniques

• Decision Trees and
• Support Vector Machines

The evidence for arguments in research, theory, hypothesis, assumption, dogma etc., is a manipulation for recognizing this junction using computational intelligent techniques have problems characterized by high noise affecting "comprehensiveness" and "performance".

http://www.icmc.usp.br/~mcmonard/public/wobLG2002.pdf

K-nearest neighbors is a good technique to think about to understand the curse of dimensionality. Suppose we have a fixed number of data points, say N = 1000. Now imagine we have some random predictor values that real values between 0 and 1. If we want to do a 5 nearest neighbor estimation with 1 predictor value, then we can make a prediction using measurements from a small neighborhood. As the number of predictors increases, the size of the neighborhood increases. So our model is rapidly loosing precision as we increase the number of predictors and we start trying to make out of sample predictions based on the average of in sample data that get progressively farther away.  

We can retrieve that lost precision at the cost of more data, but we would need a lot of data as we get to higher dimensions.

I've attached some plots to try to illustrate these points. Compare the neighborhood size for 11 nearest neighbors in 1 vs 2 dimensions. We can reduce the neighborhood size with more data, but the amount of data required to achieve the same granularity grows rapidly (exponentially!) in the number of dimensions.

The assumption of classifiers is that features are independent. When dimensionality is increased the probability that this assumption be violated is increased, because more correlation shows up between group of features.  These group of features are in fact hidden principal components of the system. This is why dimensionality reduction techniques like PCA are helpful.

I am not sure I agree with the premise. If I use support vector machines for a text classification task, my final model performs better with 20.000 features than with 2.000 features and it performs better with 2.000 features than with 200 features. The biggest problem for me is computation time.

I observed this trend in the use of K-means and Self Organising Map for the clustering of 1000 dimensioned Bag-of Word models of images. A simple explanation for this is that there was no prior information to base the choice of features used for the image modelling, therefore the presence of some features adversely affect classification accuracies. I solved the problem using PCA and PLSA to reduce the dimension. the use of PCA or PLSA allows the detection of important features upon which the classification can be based thereby improving the classification by more than 20% of its the values recorded without dimension reduction.

Dear Yahya,

The problem you mentioned is not only for the big data but in any dataset you may find that once the dimensionality of the data increases, as its consequence, complexity of the problem, i.e., Hypothesis space, will increase. Any increase in complexity of the pattern to be learned will make the training more time consuming and will negatively affect the accuracy. In case of the accuracy, presence of bad/irrelevant features in the dataset will have its own contribution as well. In addition to all this, since you have more features, your records are larger (volume in number of bytes) and consequently data transfer will take a longer time and your ML system will perform slower.

Regards

Peyman   

I wished there was uniformly simple explanation (i.e., one which I can honestly claim I fully understand.)

However, prediction "deteriorates" because of the interplay of geometry and combinatorics. Arguably, playing into this is the fact that the volume of the N-dimensional sphere -> 0 as N -> 00 (infinity), and the convergence is "exponentially fast".

So imagine you have to predict points in the N-space by choosing N-dimensional unit spheres (radius=1). A good model may very well capture most points (you've trained against) but will invariably fail to capture new points supplied by the unknown mechanism which produces the points.  

Vapnik-Chevronenkis theory provides a good framework to study classes of predictors (Boosting/stumps, SVM, ANN, Logit, etc.) but the philosophy nonetheless lies somewhere in the convex combination of said n-dimensional Euclidian geometry and combinatorics...  

Cheers,

Joe

Dear Mr Yahya,

Feature selection is a machine learning tool that may help in the case of big data.

Also, you can refer to the second link (chapter 12) to see some proposed extensions to machine learning methods for large scale problems.

http://dl.acm.org/citation.cfm?id=944968

http://infolab.stanford.edu/~ullman/mmds/book.pdf

Kasper Christensen:

In text-mining due to the noisy characteristics of data. the majority proportion of data is noise. For this reason by increasing the number of features, accuracy is improved.

For this reason if we apply PCA for dimensionality reduction in text mining, opposed to the other applications it is suggested to remove the initial PCs  (largest noise components) [1].

[1] Bullinaria, John A., and Joseph P. Levy. "Extracting semantic representations from word co-occurrence statistics: stop-lists, stemming, and SVD." Behavior research methods 44.3 (2012): 890-907.

http://dx.doi.org/10.3758/s13428-011-0183-8

I work with sensors in smart homes. The performance deteriorates simply because not all sensors are relevant to the classification. So instead of using all sensors, one need to find out which sensors are the best to train the classifier.

You can do this using a Feature Selection algorithm. They can (1) give you the best attribute subset or (2) order the attributes according to their relevance.

I think you know about the curse of dimensionality . I states that if you want to to train a classifier with a lot of attributes you need a lot of data. There is something very similar that might help you with your question. The Hughes effect or Hughes phenomenon that the performance decreases as the number of attributes increases given a fixed amount of data. I could read more about it if it interests you.

First of all, let me thank all who have contributed to this post. I just want to share with you one thought which I have drawn from your replies. Based on your replies, I think the interpretation of the premise "ML approaches deteriorates with the increase of dimensionality" is (approach-domain) dependent, therefore, it should not be judged in isolation of a prior knowledge of the specification of domain and the used approach.

With this in mind I understood

Hadi, Peyman, and Marcelo replies which are domain-dependent interpretation ( features dependency and relevance) of the premise,

Abbas and Shane who agreed with the premise based on their experience with KNN, Praveen and Joseph who provided a mathematical interpretation of the premise.

Finally I think Kasper provided a good evidence on my thought that the interpretation of the premise should be (approach-domain) dependent. in conversely to the premise, he found SVM for text classification benefits from the increase of dimensionality in text classification.

Please comment.