How to build a predictive model with a billion of sparse features? I am making a model to learn a dataset which has a big feature number and sparse samples (I am planning to use logistic regression). The feature number can be as big as 1,000,000,000. It is sparse meaning that there are a lot of zeros than ones (maybe one out of one thousand is one and others are zero). To deal with this dataset I should do some dimensionality reduction, or the machine can not deal with the model, and also I want to find some method to deal with the sparseness. So my questions are:


*

*How to do reduce the dimension?

*How to deal with the sparseness?
 A: An alternative to dimensionality reduction is to use the hashing trick to train a classifier on the entire feature set without reduction beforehand.* The Vowpal Wabbit pwoject--er, project--is an implementation of various learning algorithms using the hashing trick to speed up computation:

VW is the essence of speed in machine learning, able to learn from terafeature datasets with ease. Via parallel learning, it can exceed the throughput of any single machine network interface when doing linear learning, a first amongst learning algorithms.

I don't know if VW will end up being right for you (if you have billions of features, a lot of your choices may end up being dictated by software engineering considerations), but hopefully it's a pointer in the right direction!
* Well, the hashing trick is technically a kind of dimensionality reduction, but only in a very silly sense.
A: Traditionally, principal components analysis (PCA) is used for dimensionality reduction (in a mathematical sense). However, if you care about latent constructs (factors) that your features (indicators or items, in factor analysis and latent variable modeling terminology) represent and measure, then exploratory factor analysis (EFA) and/or confirmatory factor analysis (CFA) are appropriate. For more on this, check my answer here on Cross Validated site: https://stats.stackexchange.com/a/96160/31372.
Modeling a phenomena in terms of latent constructs (factors) has an additional benefit, since this approach allows further reduction in dimensionality and modeling at a higher level of abstraction (but you still will be able to get information on features/indicators, if this is needed).
In regard to the biased samples, as you called them, I think that you're talking about sparse data. If that is the case, read my answer here on Data Science site: https://datascience.stackexchange.com/a/918/2452.
UPDATE: Several people expressed their concerns about my suggestion of using PCA for a data set with such a very large (10^9) number of features. Despite not having direct experience of working with such types of data sets, I stand by my answer and provide a small subset of existing tools and research ("tip of the iceberg"), supporting my suggestion (in particular, focusing on applying using PCA in the cloud, including clusters, which should address the volume issues, as well as parallelizing PCA, including using GPUs, which should address the timing issues):


*

*mlpack - scalable ML library (C++; provides R bindings): http://www.mlpack.org/about.html (supports PCA functionality: http://www.mlpack.org/doxygen.php?doc=classmlpack_1_1pca_1_1PCA.html)

*Distributed and scalable PCA in the cloud: http://www.reef-project.org/wp-content/uploads/2014/01/2013-NIPS-BigLearn-DistributedAndScalablePCAinTheCloud.pdf

*Robust and scalable algorithms for big data analytics: http://www.dtc.umn.edu/resources/bd_giannakis.pdf

*PCA for large data sets with parallel data summarization: http://www2.cs.uh.edu/~ordonez/w-2014-DAPD-udfsvd.pdf

*Parallelization of PCA on scalable multi-core architecture: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5423039

*Parallel GPU implementation of iterative PCA algorithms: http://arxiv.org/abs/0811.1081
