# 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:

1. How to do reduce the dimension?

2. How to deal with the sparseness?

• What you call "biased" is actually called "sparse"; you might want to edit. Also, if you have 1 trillion features, how many samples do you have (probably a lot less)? And also, what do you want to do after dimensionality reduction? – amoeba Dec 6 '14 at 14:00
• How large is the dataset relative to the number of features? – Emre Dec 6 '14 at 20:24
• How are your features biased? – Sycorax Dec 6 '14 at 21:57
• @amoeba 1)The sample number is much bigger than the feature number and the data is stored in a sparse matrix. In fact, each example may have less than 100 features and others will be 0. So it is a very sparse matrix. 2)I want to do Logistic Regression after the dimensionality reduction or find some way to predict the test set. – maple Dec 7 '14 at 2:35

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.

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):

• Speaking practically, how would you run a FA on one trillion features? – amoeba Dec 6 '14 at 14:03
• @amoeba: Firstly, the number in OP's question is a billion (10^9), not a trillion (10^12). Secondly and most importantly, I would first perform PCA one or more times to subsequently reduce dimensionality to feasible numbers, then analyzed left features, hypothesized factor structure and performed EFA and/or CFA. – Aleksandr Blekh Dec 6 '14 at 15:04
• I though that whoever downvoted my answer would take a moment to support that action with an explanation on what particularly is wrong, considering my clarification in the comment above... – Aleksandr Blekh Dec 7 '14 at 5:32
• It was not me who downvoted, but how to run PCA on a dataset with over a billion features and over a billion samples (as specified by the OP), is also not clear to me. – amoeba Dec 7 '14 at 9:36
• @amoeba: Thank you. Please see UPDATE section in my answer, which I added in order to address PCA scalability concerns of you and others. – Aleksandr Blekh Dec 7 '14 at 11:38