5
$\begingroup$

We normally have fairly large datasets to model on, just to give you an idea:

  • over 1M features (sparse, average population of features is around 12%);
  • over 60M rows.

A lot of modeling algorithms and tools don't scale to such wide datasets.

So we're looking for a dimensionality reduction implementation that runs distributely (i.e. in Spark/Hadoop/ etc). We think to bring number of features down to several thousand.

Since PCA operate on matrix multiplication, which don't distribute very well over a cluster of servers, we're looking at other algorithms or probably, at other implementations of distributed dimensionality reduction.

Anyone ran into similar issues? What do you do to solve this?

There is a Cornell/Stanford Abstract on "Generalized Low-Rank Models" http://web.stanford.edu/~boyd/papers/pdf/glrm.pdf that talks specifically into this:

  1. page 8 "Parallelizing alternating minimization" tells how it can be distributed;
  2. also page 9 "Missing data and matrix completion" talks how sparse/ missing data can be handled.

GLRM although seems to be what we are looking for, but we can't find good actual implementations of those ideas.

Update 7/15/2018: Another Abstract is Fast Randomized SVD from Facebook (read here http://tygert.com/spark.pdf ) and also idea to do low-rank matrix approximation using ALS - http://tygert.com/als.pdf . Although there is no clear way how to use them now - see discussion at https://github.com/facebook/fbpca/issues/6

Any other ideas how to tackle this? Other available GLRM or other distributed dimensionalaity reduction implementations?

$\endgroup$
  • 1
    $\begingroup$ research.fb.com/fast-randomized-svd $\endgroup$ – Emre Jul 11 '18 at 21:27
  • $\begingroup$ thanks @Emre for referencing that article! that led to a discussion with Mark Tygert at github.com/facebook/fbpca/issues/6 - it seems we can't currently use fbpca as is in a distributed fashion. $\endgroup$ – Tagar Jul 16 '18 at 5:41
  • 1
    $\begingroup$ Maybe you could try make use of t-SNE. github.com/saurfang/spark-tsne $\endgroup$ – Krystian Kulig Jul 16 '18 at 21:36
  • $\begingroup$ Thank you for the link! It seems t-SNE is more suited for data visualization tasks than for our use case where we still want to keep as much variance as possible for modeling (see above that we're planning to bring down number features to several thousand). t-SNE focus is reducing down to 2-dimensions so it can be visualized. See lvdmaaten.github.io/tsne - "Can I use t-SNE to embed data in more than two dimensions? Well, yes you can, but there is a catch. The key characteristic of t-SNE is that it solves a problem known as the crowding problem. The extent to which this problem ..." $\endgroup$ – Tagar Jul 16 '18 at 22:06
  • 2
    $\begingroup$ How about online PCA? $\endgroup$ – Carl Rynegardh Jul 18 '18 at 23:33
1
+50
$\begingroup$

From the problem description what strikes me most relevant is the X-wing like autoencoder. Basically you have 2 neural nets that could have any of the popular neural net architectures like fully connected, convolutional and pooling layers or even sequential units like LSTM/GRU, the encoder and the decoder. If the encoding dimension is much smaller than the original one it could be used as a lower dimension representation of the input. The decoder is used to retrieve the original dimension/information. There are many types of autoencoders but for this use case you can take a look at sparse and denoising autoencoders. You could read more about autoencoders in the deep learning book: https://www.deeplearningbook.org/contents/autoencoders.html

I don't really understand why you definitely need to do the training process distributed but even for that there are distributed implementations of Tensorflow so you could do some research on the Tensorflow docs. Also if you want to learn a new framework Uber's Horovod is a distributed framework for writing Tensorflow solutions: https://github.com/uber/horovod

One last comment that I would like to make is about the underlying dimension of the data. You mentioned that an acceptable dimension would be in the thousands. In my experience sparse data reside in much smaller manifolds. So I would suggest to treat the encoding dimension as a hyper-parameter and optimize for the corresponding loss function.

$\endgroup$
  • $\begingroup$ Thanks for the answer! I have to read up on "X-wing like autoencoder". Answers to your questions: 1) we need to go distributed because factorization/ PCA etc on 1M features X 60M rows is hardly possible to imaging running on a single machine (because of memory constraint to the main part); 2) On target of several thousands principal components - it's empirical but we'd be glad to go even lower if models' performance down the pipe wouldn't be bad. Totally understood on target number of variables being a hyperparameter. Not sure I got your comment on optimizing loss function - please elaborate. $\endgroup$ – Tagar Jul 23 '18 at 3:21
  • $\begingroup$ 1) Depending on the machine that you have available you could read from a file system like HDFS and make the computations on memory - you just need to have the appropriate batch size, 2) For example if you have a squared loss function you would want to have the least error for the corresponding complexity of the system that you introduced (always compare equally deep architectures for loss function, see why ResNets exist). $\endgroup$ – Giannis M. Bakagiannis Jul 24 '18 at 3:55
2
$\begingroup$

There is principal component analysis (PCA) in Spark's Machine Learning Library (MLlib).

$\endgroup$
  • $\begingroup$ Spark's PCA has some issues as described in tygert.com/spark.pdf : 1) numerical issues - "will without warning return left singular vectors that are far from numerically orthonormal"; 2) also it seems can't handle sparse data well like for example GLRM does; our dataset is super wide and only 12% populated (see above numbers) so we can't do missing value imputation for example. $\endgroup$ – Tagar Jul 16 '18 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.