Using 10 billion features to train a prediction model with 100 inputs seems like an overkill. The data can be better utilized by splitting into multiple batches, training several models and ensembling them.

Thank you for your answer. For classification and regression I would like to use supervised models. Anyhow, can you propose any implementation of random forest, decision tree, etc. for my dataset size? The conventional implementations do not cope with this amount of data.

To deal with the curse of dimensionality you should do pre-processing of your data first, then think about ANN, DT, etc.

Basically, there are two general approaches used for dataset volume reduction: 1) dimensionality reduction such as PCA and 2) size deduction such as K-means clustering, etc.

The following links are useful:

http://featureselection.asu.edu/software.php

https://www.researchgate.net/post/Are_these_feature_selection_methods_the_state_of_the_art/3

https://www.researchgate.net/post/How_to_beat_the_curse_of_dimensionality?_tpcectx=profile_questions

Thanks. I already thought about dataset size reduction. But is it convenient to cluster the datapoints before applying machine learning algorithms?

And, is there a clustering implementation (library), which can deal with this huge amount of data?

The following article (PDF is available online) and the cited references there provide some answers and  give you new ideas. 

M.A. Shayegan and S. Aghabozorgi. A New Dataset Size Reduction Approach for PCA-Based Classification in OCR Application, Mathematical Problems in Engineering,  Volume 2014, Article ID 537428, 14 pages. 

Good Luck.

-M.O.

http://dx.doi.org/10.1155/2014/537428

Extreme Learning Machines 

http://www.ntu.edu.sg/home/egbhuang/

https://www.researchgate.net/publication/40684804_OP-ELM_optimally_pruned_extreme_learning_machine

Article OP-ELM: Optimally pruned extreme learning machine

Thank you for your answers. From my point of view online machine learning methods and online clustering methods are most promising.

Can you suggest any online machine learning or online clustering methods?

Your original data are relatively low dimension so dimensionality reduction is not important.

For clustering, there are on-line algorithms which can generate a statistical abstract of your data which will have good properties relatively to your original data.  In particular, clustering the abstract will give you a good clustering of your original data.

See for instance, this paper by Shindler, Myerson and Wong

http://papers.nips.cc/paper/4362-fast-and-accurate-k-means-for-large-datasets

For linear regression on a problem that is billions of rows by thousands of columns, you can construct the normal equation in a single pass over the data.  That, in turn, will give you a decent solution for your problem.

For non-linear regression, with or without regularization and for linear regression with regularization, you can use various forms of parallel stochastic gradient descent (SGD) to solve your problem.  The H2O package from 0xdata has an implementation of this that should work for you if you can fit your data into memory.  In your case, each 1000 element row of data is likely to require 0.1-8kB of memory.  Your 10 billion row example will thus require somewhere between 1 and 80TB of memory if you want it to be completely resident.  The low end of this range is very easy to arrange these days and the high end is not at all implausible if it is commercially worthwhile to solve this system.  If you can devote this much memory to your problem, then you will be able to solve your problem in a stunningly short time.

If your data exceeds memory, then parallel SGD is likely the best answer.  It is just harder to find really excellent implementations of solvers for this.

Why not take samples of 10,000 ? -- Train your model on one, come to a conclusion, ...then train the model on another (and another, and yet another-- several such) and compare your conclusions across these different samples. [If very different, try with samples of 100,000 !]

...In fact that's how we (humans) get trained in this earth-- we make decisions and recognize features (of very many different nature of men and women, or other species, or even inanimate objects) by looking at just a handful of their specimens, instead of this whole earth-ful of things and beings.

Just a short note of caution: If there are very different kinds of samples, you may, instead of a random sample, think of taking a representative sample-- proportionately from different similar groups (may be in the form of clusters). That increases the generalizing capacity of even small samples !

@Ted Dunning: Thank you for your dataset size approximations. Indeed, I need to think about storage. It will not be simple to share the features with collaborators :) The H2O package is a very good suggestion. Thank you for that.

@Partha Dey: Thank you for your suggestion. If I divide my dataset such that each set contains 100,000 samples, I will still have 100,000 sets. Do you want me to train 100,000 models and compare all of them? That might take some years. Or should I stop after a few models? But then I wouldn't consider most of the data at all. Is this human inspired learning method superior? Can you provide sources?

If there is a model in your data set, a random sample of n=10000 (say) should give you a good estimate of the model. You may repeat this several times to confirm the stability of the model. If this not happens, try with a greater value of n.

Thank you for your contribution.

So you are basically saying that 1 millionth (10,000/10^10) of my dataset should already estimates the model? Can you provide any sources that confirm your suggestions?

your used PCA for reducing Dimension of feature it provide very less   Dimension  of feature. in MATLAB principle component  Analysis function are ready exit.

Whether 10^4 or 10^5 random objects from your dataset will suffice to build a decent model depends entirely on the problem. However, there is a simple experiment which will give you useful information. Train and test several instances with different training set sizes and compare accuracies. You will probably see that the accuracy (or whichever heuristic you prefer) increases with the training set size, but at a declining rate.  At some point, maybe at 10^3 and maybe at 10^10, there is no significant benefit in increasing the training set size.

If you really need to take advantage of all your 10^10 objects, classifier fusion and ensemble classifiers is a possibility. Since the training complexity is super-linear, training two classifiers on N samples is cheaper than training one on 2N samples. If you train m instances on different training sets, you can use the m classifier outputs as input to yet another classifier (that's fusion simply put). In this way, you can break down the training set hierarchically into groups, and thereby reduce the complexity.

You have a total of 2^40 features, and there is no getting around that that is going to take a significant amount of time, CPU and memory to handle, regardless of what you want to do with it, but to me it sounds within reason if high-performance computing resources are available.

It is an interesting problem. I would be curious to learn more.

Using 10 billion features to train a prediction model with 100 inputs seems like an overkill. The data can be better utilized by splitting into multiple batches, training several models and ensembling them.

interesting!

Try this simple method if your data are heavy tailed: http://en.wikipedia.org/wiki/Head/tail_Breaks

Jiang B. (2015a), Head/tail breaks for visualization of city structure and dynamics, Cities, 43, 69-77, Preprint: http://arxiv.org/ftp/arxiv/papers/1501/1501.03046.pdf

The problem is not your data set, it 's just matter of defining inside of the program, since the capacity of ram is limited and it doesn't support this data set. The solution can be separating into different data-set which seems to be boring and time consuming or using "tall array" and "matfile" in matlab to make it readable.

Hans George's suggest to build models on a small amount of data and look for convergence is an excellent one. If the models don't agree on held out data, then add more of the data.

You are very likely to get a good model with far less than 10 billion training samples. Credit card fraud models are often trained with a few hundred parameters and they usually only require a few million training examples to get high quality. It isn't unusual to selectively downsample over-represented target values (usually non-fraud for fraud detection) so the actual training happens on even fewer samples.

And even if you do want to train on all the data, modern stochastic gradient descent implementations will handle that many samples pretty easily. In fact, it is common to simply watch the error on held-out samples and to stop training without reference to whether all the training data has been seen. Once you are done, you are done.

Ted Dunning It's not always true to break down data set into different small data set since it depends on input parameters. Let's take examples, imagine we're supposed to compute depth of scour at bridge piers, in this situation one of our parameters is the diameter of pier which should be repeated in every experiment to collect data and for 1000 simulations we have just one pier diameter while we should have 20 simulations with different piers to collect our data set. Now if we want to break it down into different sets, we will suffer from the lack of diversity in sets to train better.

Regards

Hossein

@Hossein Amini

You are right that lack of diversity will be a problem. I should have been more clear that I was assuming random sampling of cases from the entire dataset.

That will, of course, do no good if the entire huge dataset is itself too homogeneous unless that homogeneity is a feature of the real world. For instance, in your example, it might seem a problem that your data cover a numerically narrow range of pier sizes and completely lack examples of piers more than a kilometer thick.

Without domain knowledge this might seem like a problem, but, in fact, it is no more than the way bridge are. We don't care what our model does in cases that cannot happen, other than as a hypothetical case.