Sparse v.s. Dense Vector Discussion on Linear Classifier via @mathieuen @ogrisel @atpassos_ml

Olivier Grisel @ogrisel

@atpassos_ml @mathieuen while looped pointer increments for array of structs (index, value) is the way libsvm works http://bit.ly/9mMTWu

Mathieu Blondel @mblondel_ml

@atpassos_ml I suspect that depending on the sparsity of the weight vector, the dumb sparse-dense product may well be faster.

Mathieu Blondel @mblondel_ml

@atpassos_ml I hate Twitter's 140-char limit :)

Olivier Grisel @ogrisel

@mathieuen @atpassos_ml for linear classifiers dense - sparse is probably faster and fits in memory.

Mathieu Blondel @mblondel_ml

@ogrisel between 2 features vectors, sparse-sparse is the way to go but between feature vector and weight vector, sparse-dense may be faster

Olivier Grisel @ogrisel

@mathieuen @atpassos_ml for sparsity inducing manifold learners such as stacked autoencoders, weights matrix of 1e4 x n_features might not

Alexandre Passos @atpassos_ml

@ogrisel @mathieuen Someone should write down the state of the art and benchmarks for sparsity algorithms, as it's often implemented badly

Alexandre Passos @atpassos_ml

@ogrisel @mathieuen Someone should write down the state of the art and benchmarks for sparsity algorithms, as it's often implemented badly

Olivier Grisel @ogrisel

@atpassos_ml @mathieuen sounds like a cool new blog post -hint- -hint- ! :)

Mathieu Blondel @mblondel_ml

@ogrisel @atpassos_ml My intuition is that the merge algo is better if only few dimensions are non zero in both the feat and the weight vect

Mathieu Blondel @mblondel_ml

@ogrisel @atpassos_ml Since it takes time to create benchmarks, a collaborative effort on github would be cool!

Alexandre Passos @atpassos_ml

@mathieuen @ogrisel Precisely, as it only iterates through each nonzero feat or weight element once. If you have sparse weight this helps

Alexandre Passos @atpassos_ml

@mathieuen @ogrisel Precisely, as it only iterates through each nonzero feat or weight element once. If you have sparse weight this helps

Alexandre Passos @atpassos_ml

@mathieuen @ogrisel I'm in, except writing C code to actually test this can be annoying-ish.

Alexandre Passos @atpassos_ml

@mathieuen @ogrisel I'm in, except writing C code to actually test this can be annoying-ish.

Alexandre Passos @atpassos_ml

@mathieuen @ogrisel The problem with merge is the tradeoff between cache-niceness and being able to change the sparsity pattern quickly

Alexandre Passos @atpassos_ml

@mathieuen @ogrisel The problem with merge is the tradeoff between cache-niceness and being able to change the sparsity pattern quickly

Mathieu Blondel @mblondel_ml

@atpassos_ml @ogrisel Bob Carpenter was saying that adding and removing elements to the sparse weight vector at train time was too slow.

Mathieu Blondel @mblondel_ml

@atpassos_ml @ogrisel So training and prediction have different requirements...

Alexandre Passos @atpassos_ml

@mathieuen @ogrisel That's kind of what I was thinking. So any comparison should deal with both scenarios separately

Alexandre Passos @atpassos_ml

@mathieuen @ogrisel That's kind of what I was thinking. So any comparison should deal with both scenarios separately

Olivier Grisel @ogrisel

@mathieuen @atpassos_ml true I forgot about the case when a zero weight starts to be non-zero during training...

Alexandre Passos @atpassos_ml

@ogrisel @mathieuen I'd say the most general impl. is 3 arrays: 1 with values, 2 with indices, 3 with index of the next; sort after k. iters

Alexandre Passos @atpassos_ml

@ogrisel @mathieuen I'd say the most general impl. is 3 arrays: 1 with values, 2 with indices, 3 with index of the next; sort after k. iters

Olivier Grisel @ogrisel

@atpassos_ml @mathieuen interesting: you should learn cython with http://bit.ly/bP5Sqx and implement it, benchmark it and blog it