I wonder if it'd make sense to put the module in decomposition/?

Good job on bootstrapping this PR, @ogrisel!

I am not sure about moving to decomposition. It is mostly data independent. I think I should first finish the remaining bullet points on the TODO list and then discuss where to put this module.

Shouldn't this be in the feature_selection submodule? Or in a new module dimensionality_reduction?

Thanks for the typos @larsmans, I will address them asap. As for the right package, I have no idea :) We will have to discuss this on the ML once the rest of this PR is merge ready.

On Sat, Oct 01, 2011 at 05:18:03PM -0700, Olivier Grisel wrote:

TODO before merge

• write narrative doc

Make sure that both in the docstring and in the narrative doc, you stress
the usecase: the scikit is becoming richer and richer, and we want to
guide the users as much as much.

Thanks for the poule!

I was skimming through "Fast and Accurate k-means for Large Datasets" (NIPS 2011) and what caught my attention is that they're using RP for fast approximate neighbor search (to avoid comparing each point with K clusters). The paper was quite vague so I had a quick look at the code and apparently this is what they are doing:

• project centers to 1 dimension (i.e. on the real line) via random projection
• sort the centers
• project point to 1 dimension
• find the 2 centers between which the point is via binary search
  • if the point is farthest to the left or to the right, then just pick the center next to it
  • if the point is between 2 centers, find the closest center between the two using exact search (i.e. in the original space)

That seems like a very aggressive approximation to me but we could try it during the sprint. Instead of considering just two centers, we can consider a window for more flexibility (once we know between which centers the point is, we readily know the other closest centers since the centers are sorted).

Code and paper: http://web.engr.oregonstate.edu/~shindler/kMeansCode/

Interesting but I would rather like to focus on the text extraction / random projection / hashing vectorizer part during the sprint personally.

What is the state of this pull request?
Is there plan to incorporate denser random projections such Gaussian and binomial?

It's a bit stalled but I would like to revive it if I can find the time.

We could introduce dense random projections but I don't see any real life application as the projection matrix would be too big to fit in memory for real life dimensionality reduction tasks.

Do you have some need in this area in particular?

Yes, I am highly interested in random projection technique as a data transformation technique
(expansion and/or reduction). And in this context, Gaussian and binomial dense random projection
are baseline algorithms.

Indeed in my current project, the storage of the random projection matrix is not my bottleneck.

Edit: Note also that in compressed sensing, dense Gaussian and binomial random projections are well studied.
Edit 2: I think strongly to help you to finish this pull request if you accept.

@arjoly please feel free to branch it on your repo and issue a new pull request from here to add the dense Gaussian and binomial baselines then, either in the same class or a in a new class of the same module.

I was also thinking of dropping the hashing-based, implicit sparse random projection. While it allows for simulating the sparse RP without materialization the random matrix in memory, I think it's too CPU intensive to be competitive in real word applications.

Maybe @mblondel has an opinion on the latter.

BTW, I am pretty proud of the narrative documentation and the JL lemma related plots.

I'm personally fine either way (with or without dense gaussian).

I was referring to the option to remove the random_dot function that implements sparse random projection using murmurhash on the fly instead of pre-allocating a sparse random matrix in memory.

At the moment the two options are possible but the hash variant seems useless in practice (too slow to be useful compared to the pre-allocated variant) and hence I was thinking of removing that part of the code to make it simpler.

@ogrisel +1 for removal if it seems useless in practice. Besides, it's not published work, right?

Nope, but it's just an alternative implementation of the sparse random projection: it's mathematically equivalent to materializing the random matrix in memory.

It could probably be sped-up to be fast enough to be useful by rewriting it in cython at some point but it's low priority for me so we should not hold back this old PR because of that. So @arjoly please feel free to remove random_dot function and the materialize=False option in your own branch.

Ok, thanks for the clarification.

All right, I am going to open a new pull request shortly.

@ogrisel Can you explain why you use murmurhash3_32 instead of numpy.random?

@ogrisel Can you explain why you use murmurhash3_32 instead of numpy.random?

It would have been possible to use numpy.random.RandomState(seed=original_feature_idx).randint(n_target_features - 1) but it's probably a lot more overhead than a single call to murmurhash3_32 + a modulo operation.

Closed by @arjoly and @ogrisel in #1438. Thanks folks.